Making 2d grids in ruby and solving the puzzle

I am very interested in learning to code in Ruby simply because I would
like to get into web developing but I also have a small side project
that I actually calculated on the paper manually.

I was making a square and simply counting ways that you can go from the
top left point towards the bottom right point while only going right and
down.

Now in 1x1 grid there are only 2 solutions. When you make a 2x2 grid you
are actually making 4 squares (or one big 1x1 grid size of 2 but you
then split it in half on both sides)

The answer on this puzzle is 6.

And so I was going for 3x3, 4x4 etc. and calculating manually. Why I did
all that you might ask? Well I was actually looking for a sequence of
numbers that I would input into the integer sequence database (oeis.org)
and was trying to find the mathematical formula for this puzzle. It was
a success however I wanted to go further by simply changing the rules
for example you can’t move more then twice towards the right, or down…
or maybe you could move left only once and so on.

Then I realized that calculating all the possibilities manually would be
very difficult so I decided to try and make a code that would bruteforce
it.

I understand that Ruby might not be the best language for this (maybe
c++?) but I am really interested in Ruby and would like to solve this
problem using this language.

The problem is I have no idea where to start :frowning:

The easiest, but perhaps not the fastest, way to go about this would be
recursion. Write a function that performs one step at a time, and calls
itself again and again until the goal is reached. For each step, you can
check whether the step is allowed or prohibited by some custom
restrictions.

Here’s some exemplary code to get you started. Use it from the command
line like this:

$ ruby grid.rb 1 1
=> {:POS_X=>1, :POS_Y=>1, :GOAL_X=>1, :GOAL_Y=>1, :STEPS=>0, :PATH=>[]}
=> found 1 solution(s)

(we’re at the goal already)

$ ruby grid.rb 3 3
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:right, :right, :down, :down]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:right, :down, :right, :down]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:right, :down, :down, :right]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:down, :right, :right, :down]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:down, :right, :down, :right]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:down, :down, :right, :right]}
=> found 6 solution(s)

Here’s the actual code, the entire state (current position, goal, number
of steps, step taken etc.) are stored in the hash array “state”. I think
you should find it easy to add custom restrictions. Just change the
functions can_step_down? and can_step_right?; and add more entries to
the state hash if necessary.

Get the dimensions of the grid from the command line.

DIM_X = ARGV.shift.to_i
DIM_Y = ARGV.shift.to_i

###Main function###

Check whether we’re at the goal, otherwise take one step to

the right and left.

Calls itself recursively until the goal is reached.

def take_one_step(state=initialize_state,solutions=[],&block)
if solution?(state)
yield state
else
if can_step_right?(state)
step_right(state)
take_one_step(state,solutions,&block)
undo_step_right(state)
end
if can_step_down?(state)
step_down(state)
take_one_step(state,solutions,&block)
undo_step_down(state)
end
end
solutions
end

###Helper functions###

We start out at the top-left corner.

def initialize_state
{
:POS_X => 1,
:POS_Y => 1,
:GOAL_X => DIM_X,
:GOAL_Y => DIM_Y,
:STEPS => 0,
:PATH => []
}
end

Take a step to the right, updating the state accordingly.

def step_right(state)
state[:POS_X] += 1
state[:STEPS] += 1
state[:PATH] << :right
end

Undo the step to the right, ie. reset the state hash.

def undo_step_right(state)
state[:POS_X] -= 1
state[:STEPS] -= 1
state[:PATH].pop
end

Take a step down, updating the state accordingly.

def step_down(state)
state[:POS_Y] += 1
state[:STEPS] += 1
state[:PATH] << :down
end

Undo the step down, ie. reset the state hash.

def undo_step_down(state)
state[:POS_Y] -= 1
state[:STEPS] -= 1
state[:PATH].pop
end

# Are we allowed to step right? You can add custom restrictions here.

def can_step_right?(state)
state[:POS_X] < state[:GOAL_X]
end

Are we allowed to step down? You can add custom restrictions here.

def can_step_down?(state)
state[:POS_Y] < state[:GOAL_Y]
end

Is this state a solution, ie. are we at the goal?

def solution?(state)
state[:POS_X] == state[:GOAL_X] && state[:POS_Y] == state[:GOAL_Y]
end

###MAIN###

Call the recursive function and print the result.

i = 0
take_one_step do |sol|
p sol
i += 1
end
puts “found #{i} solution(s)”

For a grid of size 14x14 I’m getting (after removing the print statement
for every solution) 10_400_600 solutions in 30 seconds on my machine.

Filip Krama wrote in post #1173360:

I was making a square and simply counting ways that you can go from the
top left point towards the bottom right point while only going right and
down.

Here a short version

====
require “benchmark”

def duplicate(w) w.clone.map {|a| a.clone} end
def show_world(w)
w.each {|r| r.each {|a| print a ? ‘x’:’ '} ; puts}
puts ; puts
end

$dir=[1,0],[-1,0],[0,1],[0,-1]

def step(world,point,&b)
return b.call(world) if point==[world.size-1,world[0].size-1]
$dir.each do |(dx,dy)|
nextp=[point[0]+dx,point[1]+dy]
next unless (0…world.size).include?(nextp[0])
next unless (0…world[0].size).include?(nextp[1])
if !world[nextp[0]][nextp[1]]
nw=duplicate(world).tap {|w| w[nextp[0]][nextp[1]]=true }
step(nw,nextp,&b)
end
end
end

nbc,nbr=ARGV[0].to_i,ARGV[1].to_i

world= (0…nbc).map {|x| (0…nbr).to_a.map {|a| false}}
world[0][0]=true

puts “Duration: #{Benchmark.realtime {
i=0
step(world,[0,0]) {|w| i+=1 }
puts “Count: #{i}”
}}”

I made it a bit longer with descriptive variable names and a main
function with several helper functions in the hopes that it would be
easier to understand. Note that this isn’t supposed to be fast, but
instructive. You can gain a speedup by a factor of 2-4 already if you
don’t need
the path, but only the number of different solutions.

  • The function “take_one_step” begins with a check whether we have
    arrived at the goal already (“solution?”). If so, it yields the solution
    and
    stops calling itself again; otherwise, another step is taken.

  • We store the current step in one variable (hash) shared by all calls
    to the function. For example, when taking a step to the right, after
    state[:POS_X] has been increased by one, the function calls itsekf
    again. After trying a step to the right, we need to try going down as
    well – but we need to undo the step to right by decreasing
    state[:POS_X] again by one.

  • Try printing the state hash (p state) at the beginning of each
    function call and it should become obvious.

Thank you for doing this for me. Also the comments are really nice. The
big problem is that I just started learning Ruby (and I am a beginner in
programming in general) so I am having hard time understanding the code.
I will continue studying Ruby in hope that I can understand this code
one day. Thank you so much for this :slight_smile:

Edit: I have looked over the code once more and I am starting to
understand it more and more. However there are couple of things I don’t
quite understand.

How does the code not repeat itself twice? Like Right right down down
(found the solution). What happens next?

Also I don’t quite understand the take a step back state.

Dansei Yuuki wrote in post #1173437:

I made it a bit longer with descriptive variable names and a main
function with several helper functions in the hopes that it would be
easier to understand. Note that this isn’t supposed to be fast, but
instructive. You can gain a speedup by a factor of 2-4 already if you
don’t need
the path, but only the number of different solutions.

  • The function “take_one_step” begins with a check whether we have
    arrived at the goal already (“solution?”). If so, it yields the solution
    and
    stops calling itself again; otherwise, another step is taken.

  • We store the current step in one variable (hash) shared by all calls
    to the function. For example, when taking a step to the right, after
    state[:POS_X] has been increased by one, the function calls itsekf
    again. After trying a step to the right, we need to try going down as
    well – but we need to undo the step to right by decreasing
    state[:POS_X] again by one.

  • Try printing the state hash (p state) at the beginning of each
    function call and it should become obvious.

Yeah, it seems easier to understand now. Also the code you wrote is
somewhat easier to understand to a beginner like myself. The code that
raubarede wrote looks very complex and I am not able to understand
anything.

I guess I will have to keep learning. :slight_smile:

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs