About recursion from learn to program book

Rafa_F · February 18, 2016, 12:46am

M=‘land’
o=‘water’

world = [
[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,o,M,M,o,o,o,o],
[o,o,o,o,M,M,M,M,o,o,o],
[o,o,o,M,M,M,M,M,M,M,o],
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o]
]

def continent_size world, x, y
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)

end

puts continent_size(world, 5, 5)

So this would start with 5,5 as counted land and
size = size + continent_size(world, x-1, y-1), which would be
4,4 3,3 2,2 1,1 0,0 then move on to
size = size + continent_size(world, x , y-1), which would be
5,4 5,3 5,2 5,1 5,0
next
6,4 7,3 8,2 9,1 10,0
next
4,5 3,5 2,5 1,5 0,5
next
6,5 7,5 8,5 9,5 10,5
next
4,6 3,7 2,8 1,9 0,10
next
5,6 5,7 5,8 5,9 5,10
lastly
6,6 7,7 8,8 9,9 10,10

if this is correct, point 6,3 which is land would be miss by those
recursion.

What am I missing??

Hong_kim_T · February 18, 2016, 5:30pm

Works for me when I run the code. It outputs 23, which is how many I
count manually.

world.each{|x|puts x.map{|y|y[0]}*’’}

prints

wwwwwwwwwww
wwwwllwwwww
wwwwwwwwllw
wwwcwwwwwlw
wwwcwccwwww
wwwwccccwww
wwwcccccccw
wwwccwcccww
wwwwwwccwww
wlwwwcwwwww
wwwwwwwwwww

As far as I can see, it counts all the tiles in the neighbourhood?

Hong_kim_T · February 18, 2016, 9:17pm

Dansei Yuuki wrote in post #1181488:

Works for me when I run the code. It outputs 23, which is how many I
count manually.

world.each{|x|puts x.map{|y|y[0]}*’’}

prints

wwwwwwwwwww
wwwwllwwwww
wwwwwwwwllw
wwwcwwwwwlw
wwwcwccwwww
wwwwccccwww
wwwcccccccw
wwwccwcccww
wwwwwwccwww
wlwwwcwwwww
wwwwwwwwwww

As far as I can see, it counts all the tiles in the neighbourhood?

size = size + continent_size(world, x-1, y-1), which would be
4,4 3,3 2,2 1,1 0,0 then move on to
size = size + continent_size(world, x , y-1), which would be
5,4 5,3 5,2 5,1 5,0
next
6,4 7,3 8,2 9,1 10,0
next
4,5 3,5 2,5 1,5 0,5
next
6,5 7,5 8,5 9,5 10,5
next
4,6 3,7 2,8 1,9 0,10
next
5,6 5,7 5,8 5,9 5,10
lastly
6,6 7,7 8,8 9,9 10,10

code works fine, it does output 23, I just don’t understand how they
count land 6,3

Hong_kim_T · February 19, 2016, 1:11pm

(x,y)=(6,3) is a water tile, (3,6) is a land tile.

Just print what the algorithm does at each step. It seems you’re missing
(3,6) after (4,5) (x-1,y+1). Without water tiles, the algorithm visits
the the land tiles in this order:

(x,y)
(5, 5)
(5, 4)
(6, 4)
(6, 5)
(7, 5)
(6, 6)
(5, 6)
(4, 5)
(3, 4)
(3, 3)
(3, 6)
(4, 6)
(3, 7)
(4, 7)
(6, 7)
(7, 6)
(8, 6)
(9, 6)
(8, 7)
(7, 7)
(6, 8)
(7, 8)
(5, 9)

If you need more details, print them:

M=?#
o=?\

world = [
[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,o,M,M,o,o,o,o],
[o,o,o,o,M,M,M,M,o,o,o],
[o,o,o,M,M,M,M,M,M,M,o],
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o]
]

def show_map(world)
world.each{|x|puts x*’’}
end

def continent_size world, x, y
size = 1
puts “”
puts “----------------------------”
puts “---------DO–#{x}–#{y}-----------”
puts “----------------------------”
if world[y][x] != M
puts “is-water”
return 0
end
world[y][x] = ?x
show_map(world)
world[y][x] = ?c

 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)

end

puts continent_size(world, 5, 5)

Hong_kim_T · February 20, 2016, 9:10pm

Dansei Yuuki wrote in post #1181512:

(x,y)=(6,3) is a water tile, (3,6) is a land tile.

Just print what the algorithm does at each step. It seems you’re missing
(3,6) after (4,5) (x-1,y+1). Without water tiles, the algorithm visits
the the land tiles in this order:

(x,y)
(5, 5)
(5, 4)
(6, 4)
(6, 5)
(7, 5)
(6, 6)
(5, 6)
(4, 5)
(3, 4)
(3, 3)
(3, 6)
(4, 6)
(3, 7)
(4, 7)
(6, 7)
(7, 6)
(8, 6)
(9, 6)
(8, 7)
(7, 7)
(6, 8)
(7, 8)
(5, 9)

sorry I meant to say 3,6

5,5 which is starting land
next it will move on to x-1, y-1 which is 4,4 so it will return 0

x, y-1 5,4
x+1, y-1 6,4
x-1, y 4,5
x+1, y 6,5
x-1, y+1 4,6
x, y+1 5,6
x+1, y+1 6,6

I don’t understand how you got 7,5 after 6,5 ?

Hong_kim_T · February 23, 2016, 9:42pm

Dansei Yuuki wrote in post #1181602:

When it is at (6,5), the map looks like this:
[
[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,o,C,C,o,o,o,o],
[o,o,o,o,M,C,X,M,o,o,o],
[o,o,o,M,M,M,M,M,M,M,o],
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o]
]

X being the tile where we are currently, ie (6,5). Now it proceeds as
follows:

x-1, y-1 --> already counted
x , y-1 --> already counted
x+1, y-1 --> water
x-1, y --> already counted
x+1, y --> next tile that gets visited, which is (7,5)

First it is at (5,5). Then it proceeds to (5,4). Before it goes to
another tile it can reach from (5,5), it tries all tiles it can reach
from (5,4). The next tile is (6,4). Now it tries all tiles it can reach
from (6,4) first, then it proceeds with (5,4).

omg, all this time I thought this was the right execution order

[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,1,2,3,o,o,o,o],
[o,o,o,o,4,M,5,M,o,o,o],
[o,o,o,M,6,7,8,M,M,M,o],
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o]

I was wrong, this was the right one…

[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,2,3,4,o,o,o,o],
[o,o,o,o,9,1,5,6,o,o,o],
[o,o,o,M,M,8,7,M,M,M,o],
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o]

And also I realized once they find new land they will start over from
(world x-1, y-1) and continues until they find new land !

Dansei Yuuki I love you so much
I struggle over 4-5 days because of this simple problem, I really want
to thank you for
breaking down all the process for me. Thank you !!!

Hong_kim_T · February 23, 2016, 12:38pm

When it is at (6,5), the map looks like this:
[
[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,o,C,C,o,o,o,o],
[o,o,o,o,M,C,X,M,o,o,o],
[o,o,o,M,M,M,M,M,M,M,o],
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o]
]

X being the tile where we are currently, ie (6,5). Now it proceeds as
follows:

x-1, y-1 --> already counted
x , y-1 --> already counted
x+1, y-1 --> water
x-1, y --> already counted
x+1, y --> next tile that gets visited, which is (7,5)

First it is at (5,5). Then it proceeds to (5,4). Before it goes to
another tile it can reach from (5,5), it tries all tiles it can reach
from (5,4). The next tile is (6,4). Now it tries all tiles it can reach
from (6,4) first, then it proceeds with (5,4).

Hong_kim_T · February 24, 2016, 12:55am

You’re welcome.

Also, as I mentioned earlier, it helps to let the the program print what
it is doing. This way, you can compare it to what you think it should be
doing step by step.

The list of tiles from my first post was generated by adding a print
statement to the source code.

Hong_kim_T · March 17, 2016, 8:17am

http://www.lover-fashion.com/2016-New-Clubwear-Dresses-c563.html

Hong_kim_T · February 24, 2016, 1:28am

Dansei Yuuki wrote in post #1181618:

You’re welcome.

Also, as I mentioned earlier, it helps to let the the program print what
it is doing. This way, you can compare it to what you think it should be
doing step by step.

The list of tiles from my first post was generated by adding a print
statement to the source code.

I post wrong code srry

[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,1,2,3,o,o,o,o],
[o,o,o,o,4,M,5,M,o,o,o], <---- this is right order
[o,o,o,M,6,7,8,M,M,M,o],
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o],

[o,o,o,o,o,o,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,o,o,o,M,M,o],
[o,o,o,M,o,o,o,o,o,M,o],
[o,o,o,M,1,2,3,o,o,o,o],
[o,o,o,o,8,M,4,M,o,o,o], <---- this is the one I thought was correct
[o,o,o,M,7,6,5,M,M,M,o], no wonder everything was very awkward
[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,o,o,o,o,o],
[o,o,o,o,o,o,o,o,o,o,o],

I will use print command from now on to help me understand better.
Thank You again