Measuring the little islands

I’m just cleaning up my PC at work and would like to share a few pieces of code with you guys. It can be very educational

The problem

What we are going to develop here is a program which is measuring the dimensions of an island in the middle of the ocean. Sounds funky isn’t it? Well actually we are talking about a two dimensional array here (it’s an array which has “small” arrays as elements inside).

M = 'land'
o = 'water'
 
world = [[0,0,0,0,M,0,0,0,0,0,0,0],
		 [0,0,0,0,M,0,0,0,0,0,0,0],
		 [0,0,0,0,M,M,0,0,0,0,0,0],
		 [0,0,0,0,M,M,M,0,0,0,0,0],
		 [0,0,0,M,M,M,M,0,0,0,0,0],
		 [M,M,M,M,M,M,M,M,0,0,0,0],
		 [0,0,0,0,M,M,M,M,0,0,0,0],
		 [0,0,0,0,M,M,0,0,0,0,0,0],
		 [0,0,0,0,M,M,M,0,0,0,0,0],
		 [0,0,0,0,0,M,M,0,0,0,0,0],
		 [0,0,0,0,0,0,0,0,0,0,0,0]]

So this will be our little map with lots of water o and land M on it. What we want to do is drop our little program on the island and it’s going to count for us how many fields one piece of land takes up.

def continent_size world, x, y
if world[y][x] != 'land'
return 0

if it’s not a land than our program shouts back 0

elsif world[y][x].nil?
return 0
end

If it falls off the map it does the same.

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

Otherwise it counts 1.
After giving out the order to our little program we send it out to all directions from the spot where we are standing:

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

And if you watch carefully you can see that we are using the

continent_size

method eventhough we are just in the middle of defining it. This is the recursive method. With this loop inside the loop we can actually run our program around the island and it will count for us every piece of land.

puts continent_size(world, 5, 5)

and at the end we just write it out and get the total number of land. We just call the method and define the coordinates where we parachute our little program in to the map.

Hope you enjoyed this little recursive excercise. If you have any comments or ideas please share it in the comments section.

Maybe next time I will talk about my new task and my meeting with PHP and PostgreSQL. It’s going to be fun!