Ruby solution luke_bkk 21st October, 2008 13:43 (UTC)
Here is my solution.. tick is you gotta think about it backwards. http://gist.github.com/18289
Ruby solution Kirit Sælensminde 21st October, 2008 17:11 (UTC)
luke_bkk said

Here is my solution.. tick is you gotta think about it backwards. http://gist.github.com/18289

That looks like a really cool solution. I don't understand what it's doing yet — I'm looking forwards to hearing the explanation.

I take it you did check with the almighty Google that the answer was Right™ :) I realise now that mine will print out the answer off by one, but I think I can probably work that last bit out for myself.

Ruby solution luke_bkk 21st October, 2008 18:52 (UTC)

Best explained with a small 3 x 3 grid. Numbers are how many ways to get to X.

6 3 1

3 2 1

1 1 X

Down the right and along bottom there is only one way to get to X. Otherwise at any point you have the option of going one of two ways, so the number possible ways at that point is the sum of your choices. The code starts at the bottom right then works back to top left.

- Luke

Ruby solution luke_bkk 21st October, 2008 18:53 (UTC)

I would love to see a pure maths solution. Someone can do it I'm sure.

- Luke