Python heapq heappush The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

Question

I'm running into a bug with the heapq library -- the heappush function in particular. The error code (below) gives me no help.

(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 and depth are int's and child_node_puzzle_state is a numpy array. Checkout out some of the debugging code...

(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 I just use h. And magically it works?

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 there is nothing funky going on, so I really doubt this is the problem. All the functions return integers (although they use numpy arrays)...

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 1

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.