Recursive method and references

ruby-talk
1

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.

--
Posted via http://www.ruby-forum.com/.

2

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

···

--
Posted via http://www.ruby-forum.com/\.

3

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!

···

--
Posted via http://www.ruby-forum.com/\.