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

111–120 of 167 posts

Re: Can you solve it? The Greplin programming challenge

#111

Post by btilly »

shiven wrote: post #109
zmitri wrote: post #29

Earlier quoted context omitted.

Code to generate fibs is literally one line. Remember eigenvalues :)?

Sorry, couldn't help myself!! That approach is just so damn elegant. int((1/math.sqrt(5))*(math.pow(((1+math.sqrt(5))/2),fibonacci)-math.pow(((1-math.sqrt(5))/2),fibonacci))) Reference here: http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...

Elegant, but inefficient if you want to get exact values for large n. You're much better off using doubling operations. If you forget those, you can remember them from the matrix version. If fib(0) = 0. fib(1) = 1. etc. Then

       n
  [0 1]  = [fib(n)   fib(n+1)]
  [1 1]    [fib(n+1) fib(n+2)]
With repeated squarings, you can efficiently generate any Fibonacci number you want.

Re: Can you solve it? The Greplin programming challenge

#113

Post by baddox »

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 can use the Sieve of Eratosthenes to generate primes with pen and paper very easily. Or, you could find a roll of paper and evaluate any computable function (assuming unbounded paper). ;)

Re: Can you solve it? The Greplin programming challenge

#114

Post by Timothee »

baddox wrote: post #113
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 can use the Sieve of Eratosthenes to generate primes with pen and paper very easily. Or, you could find a roll of paper and evaluate any computable function (assuming unbounded paper). ;)

It doesn't seem to make it especially easy: you still have the same problem of having to eliminate the multiples of 61, 79, 89, etc. which are not obvious. Yes, you can count, but it looks very time-consuming.

The problem still stands that one needs to go in the 500,000s for that problem (thus 700s for the square root). That's still a long way to go…

I'm really curious about how cperciva did it. You're supposed to find the first Fibonacci prime over 227,000. The first Fibonacci number over that is obviously not prime (multiple of 3), but the one after that is not obvious even if you have the list of primes obtained with that method.

Re: Can you solve it? The Greplin programming challenge

#115

Post by l0nwlf »

preek wrote: post #77
l0nwlf wrote: post #19

Earlier quoted context omitted.

Brute works here because of bad test case. Author could have generated a smart test case and then optimal algorithm could be using suffix array which takes O(n), brute would take O(n!). However a bit smart brute gave the answer in approx 3-4 minutes ( computation + coding time). And yes, Python FTW.

3-4min? Since it was only like 5 lines of code I did it in brute force. Python and Mac Mini here - the answer came almost instantaneously.

By 3-4 minutes I mean both computation as well as coding time. Solution of mine came in < 1s.

Re: Can you solve it? The Greplin programming challenge

#116

Post by dsc »

cperciva wrote: post #55
grogers wrote: post #47

That was fun, good waste of time while my code was compiling. I just used C++ and hacked up a prime seive for #2 and for #3 used a combination generator I had previously used before - http://photon.poly.edu/~hbr/boost/combinations.html

for #3 used a combination generator Congratulations, you just used an exponential-time algorithm for a polynomial-time problem.

Not always is "exponential" a bad thing. For small sets, the expo algorithm is actually faster than the polynomial one. Although yeah, generally speaking, it's a bad idea.

Re: Can you solve it? The Greplin programming challenge

#118

Post by leif »

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

Re: Can you solve it? The Greplin programming challenge

#119

Post by leif »

Tichy wrote: post #105
Natsu wrote: post #28

Damn, I have to go in to work early today or I could continue this. The first one only took a minute or two of coding to solve in Perl. The search string was several times longer than my code, even with use warnings & use strict in there. I'd write a bit of code to memoize the function before I'd do the Fibonacci numbers, though, and I just don't have time to continue right now, even though it's pretty easy. Are the…

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?

Re: Can you solve it? The Greplin programming challenge

#120

Post by staktrace »

cosgroveb wrote: post #50
cperciva wrote: post #32

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

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…

I solved all three problems in under a half-hour by writing quick-and-dirty Java programs to do it. The standard libraries provide almost everything I needed; the only thing I used other than that was Maple to factor the number. I'm pretty sure mucking around with CPAN libs such would have taken me longer. Granted, my solutions were brute-force and not very elegant, but for simple problems like these with small inputs I can write code to solve it faster than finding the answer elsewhere.
Post reply on HN