Chris Pine Ruby ch 10, recursion

Question

I have been trying to learn ruby using the book 'learn to program' by Chris Pine. I was actually getting excited when going through the book until I got to chapter 10 and the examples used. Now this chapter alone and its examples have completely deflated all of my excitement to continue with this book. In this example I have completely no idea how its trying to count the tiles, or why he uses world [y],[x] when the method was defined with the attribute of continent_size world, x,y? Im not sure how the recursion in this example works. Can someone shed some more light onto this example as to what the author was actually trying to do?

M = 'land'
o = 'water'

world = [
  [o,o,o,o,o,M,o,o,o,o,o],
  [o,o,o,o,M,M,o,o,o,o,o],
  [o,o,o,o,o,M,o,o,M,M,o],
  [o,o,o,M,o,M,o,o,o,M,o],
  [o,o,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,M,M,M,M,o,o,o],
  [M,M,M,M,M,M,M,M,M,M,M],
  [o,o,o,M,M,o,M,M,M,o,o],
  [o,o,o,o,o,o,M,M,o,o,o],
  [o,M,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,o,M,o,o,o,o,o]]

def continent_size world, x ,y

  if x < 0 or x > 10 or y < 0 or y > 10
    return 0
  end

  if world[y][x] != 'land'
    return 0
  end

  size = 1
  world [y][x] = 'counted land'

  size = size + continent_size(world, x-1, y-1)
  size = size + continent_size(world, x , y-1)
  size = size + continent_size(world, x+1, y-1)
  size = size + continent_size(world, x-1, y )
  size = size + continent_size(world, x+1, y )
  size = size + continent_size(world, x-1, y+1)
  size = size + continent_size(world, x , y+1)
  size = size + continent_size(world, x+1, y+1)
  size

end

puts continent_size(world, 5, 5)

Answer 1

I been also working through the book and found myself with this and thanks to some of your insights posted here I finally solve it!

Just like user MDJ stated, x and y are just for conventional alphanumeric order, the expression world[y][x] is telling Ruby to access the y element from world, and from y the x value; both variables are used in coordinates represented in a 2D space. So if world[x][y] is world[5][5] as the the books states at the method call, the returning value M aka 'land' is evaluated accordingly.

Now here is how I solve the the extended version:

# Changed to `tile` and `row` arguments over x and y for better clarity
def continent_size(world, tile, row)
  # This value adds up for every recursive call if world[y][x] equals 'M'
  size = 1 # Moved up here

Because of the eight recursive calls, we might end up with four possible combinations:

• A valid row and tile value
• Both are invalid
• Row is valid and tile is not,
• and vice versa

The first is covered with elsif and else statements.

We assert if row is a valid index value, anything lower than 0 or higher than 10 will return nil, which covers second and fourth case returning 0.

Since a row value could be valid but the tile not, we verify it by using the valid row then whichever value tile represents. Then again, if it is lower than 0 or higher than 10 it will return nil, hence covering the third case.

    if world[row].nil? || world[row][tile].nil?
      0
    # Water tile or already counted
    elsif world[row][tile] != 'land'
      0
    else
      world[row][tile] = 'counted land' # Tracker

      # The eight directions surrounding every position
      size += continent_size(world, tile - 1, row - 1)
      size += continent_size(world, tile, row - 1)
      size += continent_size(world, tile + 1, row - 1)
      size += continent_size(world, tile - 1, row)
      size += continent_size(world, tile + 1, row)
      size += continent_size(world, tile - 1, row + 1)
      size += continent_size(world, tile, row + 1)
      size += continent_size(world, tile + 1, row + 1)

      # Total land space
      size
    end
end

You can evaluate row and tile with > or <, however only works with this specific grid size. On the other hand nil? evaluates to true if the index (represented by row or tile) does not correspond to any value.

Hope this helps!

Answer 2

It also took me some time to get the head around this example. I tried to solve the task like this, at first:

  if ( world[y] > world[y].length  || world[x] > world[x].length ) || ( world[y] < world[y].length || world[x] < world[x].length )
    return 0 
  end

But I kept getting errors of the "undefined method ">" for an array"

I then realised that the solution could be in conditioning "x" and "y", if they are more than an array (10) or lower than (0):

if x > 10 || x < 0 || y > 10 || y < 0
  return 0
end

The problem here is that it works on this particular size of arrays...if the world is bigger than 10 - the program would count every "land" it encounters as 0.

So I guess it's half-solution only...

Answer 3

I also noticed the transposition of x and y in Pine's code.
I think the reasoning might be that he arranged the "world" array so that there is one sub-array on each line. The first number in square brackets following "world" (world[0]) refers to the index of the element (sub-array) within world. Since these are stacked vertically it is your y-axis. The second bracketed number (world[0][5]) refers to the element within the sub-array. These run horizontally so the second number refers to your x-axis. Writing the method to take parameter x then parameter y allows you to enter the staring location in the conventional (x,y) format while within the method the variables are transposed to accomplish the task. I think. I'm completely new to this though.

Also, if anyone has a clean solution to extended version of this exercise where where the continent "borders the edge of the world" I would love to see it

Answer 4

It looks like the rescue approach still crashes when the top edge of the world is all 'o's. A simple approach to solving this is to write a conditional that checks if either coordinate (x,y) is outside of the boundary (i.e. outside of 0 or world.length-1) and return 0 if that condition is met.

Answer 5

I feel pretty dirty about the way I solved it, and am here looking for a better answer. I created a new variable, E = 'edge', and changed any character that touched the edge of the map to E. Then I added this code to the top of the continent_size method:

if world[y][x] == 'edge'
        return 1
    end

It works. :/

Answer 6

Taking a few steps back from the other answers, the recursion here is in that continent_size is called eight times from within continent_size.

So the method is being called eight times inside itself.

But ... each of those eight inner methods call continent_size a further eight times.

And so on, and so on.

It's bonkers to get your head around it, but when you do, it feels like you can see The Matrix. Albeit very briefly.

I stumbled across this question looking for some help with the extension bit of the task (how to avoid the error if one of your 'explorers' falls off the edge of the world).

I ended up solving this with a rescue:

# If it's off the edge of the world, it's as good as water
square = world[y][x] rescue 'o'

if square != 'Land'
  return 0
end

I don't know if this is the best way to do it, but it seems quite elegant to me.

Answer 7

For what it's worth I when I worked through this problem in the book I also noticed the transposition of x & y when world is called. I looked on the Pragmatic Programmer's website to see if this was listed in the errata, but it is not.

I thought it was typo and flipped them to x, y. The code works either way.

It doesn't really matter, since the starting point of 5,5 is arbitrary and the code will check all eight tiles around x,y (or y,x) regardless until it hits the "edge" of the array/world.

Answer 8

This is called a flood fill. What it's doing is counting the size of all the pieces of 'land' that are connected to the initial starting point. Note that it doesn't count all of the 'land' symbols, just the ones on that it can't get to because of water.

Flood fill is a form of something called depth first search which is a way to traverse a graph (here, a discrete 'map'). It can be summarized like so:

1. Visit the current position/graph node, count it and mark it as visited
2. Check all connected nodes (here, anything up, down, left or right), if they are not visited and they are land, recursively visit them

He might be doing y, x for the following reason: the logical format of a 2D array is organized first by row, then by column. The row could be thought of as the y axis and the column as the x.