bitsnake.rb

# bitsnake.rb
# A solution to the Ancient City Ruby 2016 programming challenge: 
#   http://www.ancientcityruby.com/snake_case/
#
# Dustin King ( cathodion@gmail.com / @cathodion )
#
# Counts the number of paths through an 10x10 grid of city blocks
# moving only East and South.

EAST_BLOCKS = 10
SOUTH_BLOCKS = 10

# We model the path as a positive integer of N+M bits, 
# where East is 1 and South is 0.
total_int_bits = EAST_BLOCKS + SOUTH_BLOCKS

# A correct path is one that doesn't run you off the edge
# of the grid.
# The number of '1' bits in a correct path is conveniently 
# the number of East blocks in the grid.
total_ones = EAST_BLOCKS

# count the number of '1' bits in a non-negative integer
def bitsum(i)
  ones = 0
  while i != 0
    ones += i & 1 # A one that is not 1 is scarcely a one at all.
    i >>= 1
  end
  ones
end

# Add up the correct paths.
paths = 0
(1..(2**total_int_bits)).each do |i|
  paths += 1 if bitsum(i) == total_ones
end

puts paths