ACR 2016 snake case code challenge

snake_case.rb

# Take the smallest case possible, a one wide grid
#
# .
#
# The number of ways of navigating this is 1 (do nothing)
#
# 1
#
# Extending this to a 2x2 grid still has the 0 case
#
# 1-.
# | |
# .-.
#
# Looking at the upper right corner,
#
#   |
#   v
# 1-.
# | |
# .-.
#
# there is one way to navigate to the upper right
#
# 1-1
# | |
# .-.
#
# and the same is true for the lower left
#
# 1-1
# | |
# 1-.
#
# and now for the lower right we see that this is the
# sum of the nodes it can navigate to via a single link.
#
# 1-1
# | |
# 1-2
#
# Lets extend this to a 3x3 grid
#
# 1-1-.
# | | |
# 1-2-.
# | | |
# .-.-.
#
# The upper right stil only has one way to get to the
# end point, via it's link to the left
#
# 1-1-1
# | | |
# 1-2-.
# | | |
# .-.-.
#
# Now lets look at this location
#
# 1-1-1
# | | |
# 1-2-. <-
# | | |
# .-.-.
#
# There are three ways for it to go, adding up the
# ways via going north, and the way going west.
#
# 1-1-1
# | | |
# 1-2-3
# | | |
# .-.-.
#
# Now lets look at the bottom row. The lower
# left corner still only provides one way to
# navigate.
#
# 1-1-1
# | | |
# 1-2-3
# | | |
# 1-.-.
#   ^
#   |
#
# This location has three ways to navigate, two via
# going north and one going west.
#
# 1-1-1
# | | |
# 1-2-3
# | | |
# 1-3-. <-
#
# Now looking at the last location we see that it has
# a total of six ways to go, three by going north and
# three by going west.
#
# 1-1-1
# | | |
# 1-2-3
# | | |
# 1-3-6
#
# Now lets extend this to a 4x4 grid
#
# 1-1-1-.
# | | | |
# 1-2-3-.
# | | | |
# 1-3-6-.
# | | | |
# .-.-.-.
#
# Lets fill this out using the same process we did for
# 3x3.
#
# 1--1--1--1
# |  |  |  |
# 1--2--3--4
# |  |  |  |
# 1--3--6--10
# |  |  |  |
# 1--4-10--20
#
# So in general we can say that the number of paths for
# any cell is the number of paths for the cell to the west
# plus the number of cells to the north if there are such
# cells present.
#
# If we consider this a zero based grid we can consider
# the number of paths from a cell(x,y) is cell(x-1,y) (west)
# plus cell(x,y-1) (north)
#
# And we handle the case along the edges where x, or y
# are 0 to return a count of 1

def snake_case(x,y)
  (x == 0 || y == 0) ? 1 : snake_case(x-1, y) + snake_case(x, y-1)
end

# Print the snake_case for the entire grid if you like
#
# 0.upto(10) do |x|
#   0.upto(10) do |y|
#     print "#{snake_case(x,y).to_s.ljust(5, " ")} "
#   end
#   puts
# end

puts snake_case(10,10)

👍