recursive method and references

[Sci000 Lem.]

Hello @ all,

I just wanted to realize a small heuristic search algorithm, but it
doesn’t work as I expected it to be. Here is the problem:

The test function f works properly:
def f(a, i=0)
(puts "---"; return) if i==10
(0..3).each do |x|
b=a.dup
next if x>=1
b[0]=i+x
f(b.dup, i+1)
print b, "\n"
end
end

a=[1,2,3]
a.push(4)
print "#", a, "\n"
f(a.dup)
print "#", a, "\n"


The output is:
#1234
---
9234
8234
7234
6234
5234
4234
3234
2234
1234
0234
#1234


Exactly what I want!

But the real one doesn’t:
def tyra(arr, pos2, tmp2, resul, res=0, i=0)
(puts "#####"; resul.push(res); return) if i>=13
(0..3).each do |y|
pos=pos2.dup; tmp=tmp2.dup
#~ tmp[0]=(tmp[0]+1)%7 if y==0
#~ tmp[0]=(tmp[0]-1)%7 if y==1
#~ tmp[1]=(tmp[1]+1)%8 if y==2
#~ tmp[1]=(tmp[1]-1)%8 if y==3
next if pos[tmp[0]][tmp[1]]==1
pos[tmp[0]][tmp[1]]=1
tyra(arr, pos.dup, tmp.dup, resul, res+arr[tmp[0]][tmp[1]], i+1)
print "*", pos2, "\n", "_", pos, "\n"
end
end

arr, pos, tmp, resul = [], [], [], []
arr.push([32,80,19,98,01,90,14,85])
arr.push([66,22,73,52,72,57,83,31])
arr.push([30,84,41,73,16,74,45,92])
arr.push([77,06,70,24,00,28,67,11])
arr.push([32,99,44,81,27,75,42,98])
arr.push([68,21,72,56,59,42,75,17])
arr.push([34,87,19,92,05,99,27,88])

arr[0].length.times{tmp.push(0)}
arr.length.times{pos.push(tmp.dup)}
tmp2=[3,4]

print "#", pos, "\n"
tyra(arr, pos.dup, tmp2.dup, resul)
print "#", pos, "\n"


The output is:
#00000000000000000000000000000000000000000000000000000000
*00000000000000000000000000001000000000000000000000000000
_00000000000000000000000000001000000000000000000000000000
#00000000000000000000000000001000000000000000000000000000


The lines marked with a "#" does not equal each other as with the test
function…
What goes wrong, where’s the bug?

Thanks to all your answers in advance.

 

[Chris Hulan]

Sci000 Lem. wrote:
...

def tyra(arr, pos2, tmp2, resul, res=0, i=0)
(puts "#####"; resul.push(res); return) if i>=13
(0..3).each do |y|
pos=pos2.dup; tmp=tmp2.dup ...
next if pos[tmp[0]][tmp[1]]==1
pos[tmp[0]][tmp[1]]=1
tyra(arr, pos.dup, tmp.dup, resul, res+arr[tmp[0]][tmp[1]], i+1)
print "*", pos2, "\n", "_", pos, "\n"
end
end

arr, pos, tmp, resul = [], [], [], []
arr.push([32,80,19,98,01,90,14,85])
arr.push([66,22,73,52,72,57,83,31])
arr.push([30,84,41,73,16,74,45,92])
arr.push([77,06,70,24,00,28,67,11])
arr.push([32,99,44,81,27,75,42,98])
arr.push([68,21,72,56,59,42,75,17])
arr.push([34,87,19,92,05,99,27,88])

arr[0].length.times{tmp.push(0)}
arr.length.times{pos.push(tmp.dup)}
tmp2=[3,4]

print "#", pos, "\n"
tyra(arr, pos.dup, tmp2.dup, resul)
print "#", pos, "\n"


The output is:
#00000000000000000000000000000000000000000000000000000000
*00000000000000000000000000001000000000000000000000000000
_00000000000000000000000000001000000000000000000000000000
#00000000000000000000000000001000000000000000000000000000


The lines marked with a "#" does not equal each other as with the test
function…
What goes wrong, where’s the bug?

Your pos array contains references to other arrays,
and pos.dup is a shallow copy, thus pos2 contains refs
to the same sub-arrays as pos. Any changes made via
access to pos2 affects the same sub-arrays as viewed
from pos.

Clear as mud? 9^)

Cheers
Chris

 

[Sci000 Lem.]

Your pos array contains references to other arrays,

and pos.dup is a shallow copy, thus pos2 contains refs
to the same sub-arrays as pos. Any changes made via
access to pos2 affects the same sub-arrays as viewed
from pos.

Clear as mud? 9^)

Cheers
Chris

Thank you for the answer, I didn’t know that the subarrays in Ruby are
just referenced to the whole array, so I was wondering why it don’t work
(normally I solve this kind of problems in Mercury, and that’s
completely different)
I rewrote the lines which built pos as following:
arr.length.times{arr[0].length.times{pos.push(0)}}
and everything works properly!