151–160 of 167 posts
Nice and short Haskell solution to #3: http://gist.github.com/617675 Ruby solutions to #1 and #2: http://gist.github.com/617676 http://gist.github.com/617678
(not . null) instead of (\x -> length x > 1) is shorter, and works on infinite lists also.
Edit: well, in case you would test for x>0.
Earlier quoted context omitted.
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.
I am not sure if this step of allowing the "shortcuts" was part of the game or not. All that would had to be done is to give 128 elements of the array to exclude at least the most blatant brute-forcing.
Earlier quoted context omitted.
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.
# memoized fibonacci function
fibtable = {1:1, 0:1}
def fib (n):
global fibtable
if n in fibtable.keys():
return fibtable [n]
val = fib (n-1) + fib (n-2)
fibtable [n] = val
return valEarlier quoted context omitted.
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.
Here (where you have to search through Fibonacci numbers) I suspect memoization is rather the way to go: # memoized fibonacci function fibtable = {1:1, 0:1} def fib (n): global fibtable if n in fibtable.keys(): return fibtable [n] val = fib (n-1) + fib (n-2) fibtable [n] = val return val
last_fib = 0
fib = 1
while fib 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.
Earlier quoted context omitted.
I would think that pencil and paper would be slower than writing the programs. But you're right that they are ridiculously easy.
For the third problem, yes. But after solving the first two problems without writing code, I didn't feel like starting on the last problem.
Hmm... now that I think about it, did you do something like starting at the end of the list, then subtracting numbers as you went until you either found a set that added up to your top number, or found it impossible for that number to be in the set?
It seems like it would take a lot of paper to do that, but it's more efficient than the simple brute force technique I did.
I'm just curious, because I bet there are better ways to do that one and I think the challenge is probably over by now.
Earlier quoted context omitted.
For the third problem, yes. But after solving the first two problems without writing code, I didn't feel like starting on the last problem.
I seem to recall that there were 2^22 sets in the power set of that list of numbers, so you obviously had to use some kind of technique to cull the vast majority of the sets. Hmm... now that I think about it, did you do something like starting at the end of the list, then subtracting numbers as you went until you either found a set that added up to your top number, or found it impossible for that number to be in the…
I'm pretty sure that cperciva used a similar trick, but in each row you're potentially adding another element of the set, and not potentially adding 1.
This gives you a mapping telling you how many ways there are to get 0, 1, 2, 3, etc as the sum of some subset of the set. Just sum this over the set, and subtract the size of the set. (Every element in the set is the sum of itself, but you don't want to count those.) And there is your answer.
Earlier quoted context omitted.
Congratulations are in order, he sacrificed 400ms CPU time to save at least a few minutes of coding time.
I wasn't being entirely sarcastic. It never occurred to me that you could use a non-polynomial-time algorithm.
Earlier quoted context omitted.
fuckin nice. now I feel like a doofus for using ruby, when I thought it was straightforward.
I've done it ruby this way: text.scan(/(.)(.)(.)(.)(\3)(\2)(\1)/)
Oddly enough, it didn't even occur to me to try a regex and I like using them quite a bit.