Jul
5
In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 15.
# Euler 15
# http://projecteuler.net/index.php?section=problems&id=15
# Starting in the top left corner of a 2x2 grid, there
# are 6 routes (without backtracking) to the bottom right
# corner. How many routes are their in a 20x20 grid?
timer_start = Time.now
# There's no factorial method in Ruby, I guess.
class Integer
# http://rosettacode.org/wiki/Factorial#Ruby
def factorial
(1..self).reduce(1, :*)
end
end
rows, cols = 20, 20
puts (rows+cols).factorial / (rows.factorial * cols.factorial)
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
This problem took a lot of time and paper to solve. After numerous route sketches, I was fortunate to see the beginnings of Pascal’s Triangle, the key to solving this problem, surface:
70 35 15 05 01
35 20 10 04 01
15 10 06 03 01
05 04 03 02 01
01 01 01 01 01
I then did research to find the equation needed to determine the number of path combinations for larger grids.
1×1 = (1+1)!/(1! * 1!) = 2
2×2 = (2+2)!/(2! * 2!) = 6
3×3 = (3+3)!/(3! * 3!) = 20
4×4 = (4+4)!/(4! * 4!) = 70
…
As always, any feedback is welcome.
With havin so much content do you ever run into any problems of plagorism or copyright infringement? My site has a lot of completely unique content I’ve either authored myself or outsourced but it looks like a lot of it is popping it up all over the internet without my authorization. Do you know any solutions to help reduce content from being ripped off? I’d genuinely appreciate it.
Nice post mate, I love your blog, thanks for sharing it
My husband and i got quite joyful that Albert could conclude his investigations via the ideas he acquired in your web pages. It’s not at all simplistic to simply continually be giving for free secrets and techniques that a number of people may have been trying to sell. And we also figure out we need the blog owner to give thanks to for this. The specific explanations you’ve made, the straightforward site navigation, the friendships your site make it possible to promote – it’s mostly superb, and it is making our son in addition to us understand the article is pleasurable, and that is seriously vital. Thank you for all the pieces!
I noticed some other people using the pascal’s triangle method, I think that is a much more elegant way to solve this problem, I simply calculated the permutations !(20+20)/(!20 * !20)