Kendall Weihe - 4 months ago 34

Python Question

I'm running into a bug with the

`heapq`

`heappush`

`(Pdb) heapq.heappush(priority_queue, (f, depth, child_node_puzzle_state))`

*** ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

Here's the snippet that is causing the problem...

`h = compute_heuristic(child_node_puzzle_state, solved_puzzle)`

depth = current_node[1] + 1

f = h + depth

heapq.heappush(priority_queue, [f, depth, child_node_puzzle_state])

I should note that

`h`

`depth`

`int`

`child_node_puzzle_state`

`(Pdb) child_node_puzzle_state`

array([[ 5., 4., 18., 15., 0., 0., 0., 0., 0., 0., 0.,

99.],

[ 99., 10., 6., 14., 12., 20., 0., 0., 0., 0., 99.,

99.],

[ 99., 99., 11., 19., 17., 16., 8., 0., 0., 99., 99.,

99.],

[ 99., 99., 99., 2., 3., 0., 0., 0., 99., 99., 99.,

99.],

[ 99., 99., 99., 99., 1., 21., 0., 99., 99., 99., 99.,

99.],

[ 99., 99., 99., 99., 99., 9., 13., 7., 0., 0., 0.,

0.]])

(Pdb) child_node_puzzle_state.dtype

dtype('float64')

(Pdb) p h

3

(Pdb) depth

2

(Pdb) f

5

(Pdb) priority_queue

[(5, 2, array([[ 9., 15., 0., 0., 0., 0., 0., 0., 0., 0., 0.,

99.],

[ 99., 10., 6., 14., 5., 4., 18., 0., 0., 0., 99.,

99.],

[ 99., 99., 11., 19., 17., 12., 20., 8., 0., 99., 99.,

99.],

[ 99., 99., 99., 16., 3., 0., 0., 0., 99., 99., 99.,

99.],

[ 99., 99., 99., 99., 2., 0., 0., 99., 99., 99., 99.,

99.],

[ 99., 99., 99., 99., 99., 1., 21., 13., 7., 0., 0.,

...

(Pdb) len(priority_queue)

9

Here's what I cannot figure out... if I change one little thing it works -- but it is semantically wrong. Here's is the change ...

`h = compute_heuristic(child_node_puzzle_state, solved_puzzle)`

depth = current_node[1] + 1

heapq.heappush(priority_queue, (h, depth, child_node_puzzle_state))

Did you catch the difference? Instead of computing

`f = h + depth`

`h`

This couldn't be the size, because as I showed in debugging...

`(Pdb) len(priority_queue)`

9

This really doesn't make sense to me, so I'm going to include more code. First, here is everything needed to compute

`h`

`def tubes_aligned(puzzle_state):`

current_index = 3 #test for index 3

blue_tube = puzzle_state[3,:]

len_of_top_tube = len(blue_tube[blue_tube < 99]) - 3

correct_index = 6 - len_of_top_tube

found = False

distance = 3

for i in range(3):

if i == correct_index:

distance = current_index - i

found = True

if not found:

for i in range(5,2,-1):

if i == correct_index:

distance = i - current_index

return distance

def balls_in_top_half(puzzle_state):

for i in range(6):

full_tube = puzzle_state[i,:]

num_balls = full_tube[full_tube < 99]

num_balls = len(num_balls[num_balls > 0])

if (6 - i - num_balls) != 0:

return 1

return 0

def balls_in_correct_place(puzzle_state, solved_puzzle):

if is_solved(puzzle_state, solved_puzzle):

return 0

else:

return 1

def compute_heuristic(puzzle_state, solved_puzzle):

# print "computing heuristic"

# heuristic (sum all three):

# 1. how many tubes is the puzzle state from tubes being aligned -- max is 3

# 2. is there balls in the top portion? 1 -- yes || 0 -- no

# 3. are there balls in the wrong place in the bottom half? 1 -- yes || 0 -- no

part_1 = tubes_aligned(puzzle_state)

part_2 = balls_in_top_half(puzzle_state)

part_3 = balls_in_correct_place(puzzle_state, solved_puzzle)

return part_1 + part_2 + part_3

Answer

`heapq.heappush`

will *compare* an array with other arrays in the heap, if the preceding elements in the tuple you push are otherwise equal.

Here is a pure Python implementation of `heappush()`

:

```
def heappush(heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
_siftdown(heap, 0, len(heap)-1)
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if newitem < parent:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
```

The actual implementation will be in C, which is why you get the error without a deeper traceback.

Note the `newitem < parent`

comparison; it is *that comparison* that is throwing the exception, as numpy `array`

objects would be compared element by element and produce a boolean array with true and false results. If there is a state in your heap where `f`

and `depth`

are equal, that comparison must compare the arrays:

```
>>> import numpy
>>> t1 = (5, 2, numpy.array([9., 15.]))
>>> t2 = (5, 2, numpy.array([10., 15.]))
>>> t1 < t2
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()
```

For you the problem 'disappeared' when you changed the value in the first position of the tuple, making the first two values unique again compared to what is already in your heap. But it doesn't actually solve the underlying problem.

You can avoid this issue by inserting a unique count (using `itertools.count()`

) before the array:

```
from itertools import count
# a global
tiebreaker = count()
# each time you push
heapq.heappush(priority_queue, (f, depth, next(tiebreaker), child_node_puzzle_state))
```

The counter ensures that the first three elements of your tuples are *always* unique. It also means that any later addition to the heap that matches an already-present state on the heuristic score *and* depth are sorted before older ones. You can use `count(step=-1)`

if you want to inverse that relationship.