Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Can you solve it? The Greplin programming challenge

challenge.greplin.com

Post reply on HN
Print view View original

121–130 of 167 posts

Re: Can you solve it? The Greplin programming challenge

#121

Post by btilly »

Timothee wrote: post #92
cperciva wrote: post #51

Earlier quoted context omitted.

I didn't solve the problems using existing code either. All three are entirely solvable by pencil and paper (or just inspection in the first case).

How do you go about solving #2 on pen and paper? Well, calculating the Fibonacci sequence, ok. The sum of prime divisors of X+1, I guess... though it gets slightly harder for me after dividing by 2, 3 and 5. But how do you know for sure that X is prime? Based on bd's link, I'll just assume that you have super powers. (or I'm approaching the problem the wrong way) edit: I was starting to think about what to write for…

You have less than 30 Fibbonacci numbers to compute.

That 317811 is divisible by 3 is obvious upon adding its digits together.

Once you've verified that 514229 isn't divisible by a handful of small primes, you don't try to prove primality. Instead factor 514230 and stick it in. After dividing by 2, 3, and 5, you've got 17141. It doesn't take that long to run through 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 and 61. At which point you have an answer you can try plugging in to discover it is correct. Which is a sequence cperciva pretty definitely has memorized. (I do.) Or alternately cperciva may have better factorization techniques memorized.

If you already have a routine around for factoring (I do), then this takes longer than coding it. But I could do it with paper and pencil pretty easily.

Re: Can you solve it? The Greplin programming challenge

#122

Post by ynniv »

cperciva wrote: post #32

Do I get bonus marks for solving this without writing any code?

I'm disappointed that it is possible to solve by hand, as that undercuts the reward. This is one of the great aspects of ITA's programming problems: none of them are even solvable by brute force.

Re: Can you solve it? The Greplin programming challenge

#123

Post by dantle »

staunch wrote: post #100
cosgroveb wrote: post #50

Earlier quoted context omitted.

I immediately went to Wikipedia, found out what type of CS problem the first challenge was, then followed the external links at the bottom of the page to find the Perl module I needed and installed it from CPAN. I quit because this seemed like cheating but now I'm thinking... Maybe it was the point? To see if I would try to find something off-the-shelf to solve the problem quickly. Still not sure it was, because if s…

Easy job for a regex: while ($string =~ /((\w+)\w?(??{reverse $2}))/g) { print "$1\n"; }

fuckin nice. now I feel like a doofus for using ruby, when I thought it was straightforward.

Re: Can you solve it? The Greplin programming challenge

#124

Post by Timothee »

btilly wrote: post #121
Timothee wrote: post #92

Earlier quoted context omitted.

How do you go about solving #2 on pen and paper? Well, calculating the Fibonacci sequence, ok. The sum of prime divisors of X+1, I guess... though it gets slightly harder for me after dividing by 2, 3 and 5. But how do you know for sure that X is prime? Based on bd's link, I'll just assume that you have super powers. (or I'm approaching the problem the wrong way) edit: I was starting to think about what to write for…

You have less than 30 Fibbonacci numbers to compute. That 317811 is divisible by 3 is obvious upon adding its digits together. Once you've verified that 514229 isn't divisible by a handful of small primes, you don't try to prove primality. Instead factor 514230 and stick it in. After dividing by 2, 3, and 5, you've got 17141. It doesn't take that long to run through 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,…

Fair enough. Though I'd argue on "entirely solvable by pencil and paper", since the answer is an educated guess in that case and the proof that it's correct resides in checking with the webpage. ;-)

To be honest, in the same amount of time, one could also estimate the range where the answer should be and plug it one by one in the form until it validates. (which we'll call a less educated guess :))

Re: Can you solve it? The Greplin programming challenge

#125

Post by [deleted] »

dschoon wrote: post #26
bd wrote: post #25

"Even if you're not looking for a job, we'd love to hear what you thought about the challenge." I would be curious how many people did you lose because of phonecall requirement (before you changed it). Also CSV for just a list of 22 numbers wasn't really necessary. If you do web puzzle, the best is to keep everything self-contained, no downloads, no using external channels, just copy and paste. FYI another Python che…

I don't think trivializing the combinations with Python's builtins, looking up the fib primes with OEIS, or computing factors with Alpha is cheating. I hope, in fact, it's the whole point of the exercise: choose the right tools for the job. If you're writing code to test primeness or generate Fibonacci numbers, I sure as hell don't want to hire you.

[deleted]

Re: Can you solve it? The Greplin programming challenge

#126

Post by dasil003 »

leif wrote: post #118
dasil003 wrote: post #87

Here's better-than-brute-force solution to Q1 http://gist.github.com/617715 Is there a better algorithm? Dynamic programming of some sort? I guess we'd need a longer string to tell the difference.

I can't read ruby, but here's something a little smarter than brute force in C (on its way to DP, but I couldn't be arsed to work out the recurrence so I just iterated until it stabilized): http://gist.github.com/617854

It looks similar to mine, but you got lucky (or unlucky depending on how you look at it) that the longest palindrome had an odd character count.

The confusing bits in the Ruby are actually just the definition of an even and odd palindrome finder, which are the same except for two seed values for where the first comparison is conducted and it's length.

Re: Can you solve it? The Greplin programming challenge

#127

Post by Natsu »

1amzave wrote: post #23

So what languages did everyone use? I decided to try a different one on each level, so I used Python, bash (letting GNU coreutils 'factor' do the hard work), and Haskell, respectively.

Perl. From the look of this thread, I guess everyone else has moved on?

Re: Can you solve it? The Greplin programming challenge

#128

Post by Natsu »

leif wrote: post #119
Tichy wrote: post #105

Earlier quoted context omitted.

brute force seems to be sufficient

you also probably don't want to memoize, you aren't going to re-use, so why waste the memory?

I wrote that right before leaving for work, so I hadn't spent any time thinking about the problem.

Coming back, I see that I really don't need to be very efficient for any of these problems, which I honestly find a little disappointing.

Re: Can you solve it? The Greplin programming challenge

#129

Post by mfukar »

cperciva wrote: post #32

Do I get bonus marks for solving this without writing any code?

Writing code for 2 & 3 would probably take more than solving it with pen&paper, for me at least. I wrote code for #1 because it was practically 3 lines..

If it was really meant as a programming challenge, it should feature problems which are worth writing code for.

Re: Can you solve it? The Greplin programming challenge

#130

Post by Natsu »

rwalker wrote: post #22
triangleman83 wrote: post #21

Wow the G. Address was horribly mutilated. Four score and seven years ago our faathers brought forth on this containent a new nation conceived inz Liberty and dedicated to the proposition that all men are created equal Now we are engaged in a greaht civil war testing whether that naption or any nartion so conceived and so dedicated can long endure We are qmet on a great battlefiemld of tzhat war

This was intentional - we had to tie break the longest palindrome and we didn't want a quick diff to be able to see what we changed.

Why not ask for the rightmost palindrome, then? Just to make it a tiny bit more complex (not that it's very hard to iterate backwards)?
Post reply on HN