How do I interpret this pseudocode in Ruby?

Question

I don't quite understand how to "initialize a multidimensional array to equal 1" as the initial for loops seem to suggest here. I haven't learned to properly read pseudocode, and I don't fully understand how this program works.

function countRoutes(m,n)
  grid ← array[m + 1][n + 1]

  for i = 0 to m do 
    grid[i][0] ← 1
  end for

  for j = 0 to n do 
    grid[0][j] ← 1
  end for

  for i = 1 to m do
    for j = 1 to n do
      grid[i][j] ← grid[i − 1][j] + grid[i][j − 1] 
    end for
  end for

  return grid[m][n] 
end function

Thanks for your help!

Answer 1

This isn't hard to translate.. Ruby uses = instead of left arrow for assignment, and def instead of function to define a subroutine (which it calls a method instead of a function), but that's about it. Let's go through it.

function countRoutes(m,n)

That's beginning a function definition. In Ruby we use a method instead, and the keyword to define such a thing is def. It's also convention in Ruby to use snake_case for multiword names instead of camelCase:

def count_routes(m, n)

Now to create the grid:

grid ← array[m + 1][n + 1]

Ruby arrays are dynamic, so you don't normally need to specify the size at creation time. But that also means you don't get initialization or two-dimensionality for free. So what we have to do here is create an array of m+1 arrays, each of which can be empty (we don't need to specify that the sub-arrays need to hold n+1 items). Ruby's Array constructor has a way to do just that:

  grid = Array.new(m+1) do [] end

Now the initialization. Ruby technically has for loops, but nobody uses them. Instead, we use iterator methods. For counting loops, there's a method on integers called times. But the pseudocode counts from 0 through m inclusive; times also starts at 0, but only counts up to one less than the invocant (so that way when you call 3.times, the loop really does execute "three times", not four). In this case, that means to get the behavior of the pseudocode, we need to call times on m+1 instead of m:

  (m+1).times do |i|
    grid[i][0] = 1
  end

As an aside, we could also have done that part of the initialization inside the original array creation:

  grid = Array.new(m+1) do [1] end

Anyway, the second loop, which would be more awkward to incorporate into the original creation, works the same as the first. Ruby will happily extend an array to assign to not-yet-existent elements, so the fact that we didn't initialize the subarrays is not a problem:

  (n+1).times do |j|
    grid[0][j] = 1
  end

For the nested loops, the pseudocode is no longer counting from 0, but from 1. Counting from 1 through m is the same number of loop iterations as counting from 0 through m-1, so the simplest approach is to let times use its natural values, but adjust the indexes in the assignment statement inside the loop. That is, where the pseudocode starts counting i from 1 and references i-1 and i, the Ruby code starts counting i from 0 and references i and i+1 instead.

  m.times do |i|
    n.times do |j| 
      grid[i+1][j+1] = grid[i][j+1] + grid[i+1][j] 
    end
  end

And the return statement works the same, although in Ruby you can leave it off:

  return grid[m][n]
end

Putting it all together, you get this:

def count_routes(m, n)
  grid = Array.new(m+1) do [1] end

  (n+1).times do |j|
    grid[0][j] = 1
  end

  m.times do |i|
    n.times do |j| 
      grid[i+1][j+1] = grid[i][j+1] + grid[i+1][j] 
    end
  end

  return grid[m][n]
end

Answer 2

The notation grid[i][j] ← something means assigning something to the element of grid taking place on i-th line in j-th position. So the first two loops here suggest setting all values of the first column and the first row of the grid (correspondingly, the first and the second loops) to 1.