Algorithm to find a moving target in as few steps as possible

Question

I have the following problem I'm trying to solve:

There are 6 cups (Say numbered 1 through 6) in a row. Under one of the cups is a ball (I don't know which one). I can lift up a cup, and see if the ball is there. If it is, I win. If it is not, the ball gets moved from its current position to a cup to its immediate left or right (So from cup 4 to either cup 3 or 5. From cup 6 it can only move to cup 5). The ball must move, it cannot stay in place.

The question is: If you use the optimal strategy, after what number of "cup lifts" will you know the location of the ball.

Currently, I have puzzled out a strategy with a worst case of 6 lifts. Note that the final lift, "proving" where the ball is, does not need to be done. My questions are: Is there an algorithm with a better "worst case"? And if not, how do I prove this is the best algorithm?

My current strategy. We assume the ball is under an even cup at the start (so 2, 4 or 6). The step by step of my worst case is as follows.

Lift 1: Lift cup number 2. The ball is not there. By our assumption, the ball will move to an odd cup, but it cannot have moved to cup 1 (Because it would have to originate in cup 2, and it wasn't there)

Lift 2: Lift cup number 3. The ball is not there. I couldn't have been under 1 (see above), it's not under 3, and by assumption it's under an odd cup. This means it is now under cup 5, and must thus move to cup 4 or 6.

Lift 3: Lift cup number 4, ball is not there. This means it must have moved to cup number 6, so on the next move it must move to cup number 5

Lift 4: Lift cup number 5, ball is not there. This was the only possibility left, so we guessed incorrectly that it started under an even cup. As a result, it is now under some even cup, and will move to an odd cup on the next move. We now work the same process, but the other way around.

Lift 5: Lift cup number 5 (again). Ball is not there. By the new assumption, the ball will now move to cup 2 or 4 (Again, it cannot move to cup 6, because it wasn't under 5).

Lift 6: Lift cup number 4. It is not there, so it must be under cup number 2 (it is under an even cup, and it is not under 6 or 4). We thus know where the cup is (even though we don't perform the final lift of cup number 2).

Answer 1

If you want to solve the problem with a program, construct a graph where the vertices are the sets of possible places the ball can be, and the edges are cup lifts which turn out not to reveal a ball. Then a solution is a shortest path from whatever starting state you want to any state with 2 possible cup lifts. (The terminating condition of ending at a is a bit messy because of the rule that it's allowed to "know" where the ball is before it moves).

This code is pretty rough, but uses DFS to find a shortest path and then pretty prints the solution. It confirms that 6 cup lifts are required to find the ball in the worst case, and in fact finds the exact same solution as you did.

The output is:

$ python cups.py
the ball can be under cups: 1,2,3,4,5,6
lift cup 2
the ball can be under cups: 2,3,4,5,6
lift cup 3
the ball can be under cups: 1,3,4,5,6
lift cup 4
the ball can be under cups: 2,4,5,6
lift cup 5
the ball can be under cups: 1,3,5
lift cup 5
the ball can be under cups: 2,4
lift cup 2

The code is:

import collections

N = 6
MASK = (1<<N)-1

def bitcount(n):
    if n == 0: return 0
    return 1 + bitcount(n & (n-1))

def shifts(c):
    return ((c << 1) | (c >> 1)) & MASK

def adjacent(c):
    if bitcount(c) == 2:
        yield min(i for i in xrange(N) if (c>>i)&1), 0
        return
    for i in xrange(N):
        if (c>>i)&1:
            yield i, shifts(c & ~(1<<i))

def bfs(edges, start):
    prev = {start: None}
    q = collections.deque([start])
    while q:
        x = q.popleft()
        for y in edges[x]:
            if y in prev: continue
            prev[y] = x
            q.append(y)
    return prev

def path(x, prev):
    if x is None: return []
    return path(prev[x], prev) + [x]

edges = dict((v, [n for _, n in adjacent(v)]) for v in xrange(2**N))
best_path = path(0, bfs(edges, MASK))

for pi, p in enumerate(best_path[:-1]):
    print 'the ball can be under cups: %s' % ','.join(str(i+1) for i in xrange(N) if (p>>i)&1)
    print 'lift cup %d' % list(c+1 for c, n in adjacent(best_path[pi]) if n == best_path[pi+1])[0]

Answer 2

I think this riddle is close to the problem you proposed. However, it contains 5 boxes instead of 6. Anyways, you can still check the solution they proposed and compare their strategy to yours.

Hope it helps.

Answer 3

Your algorithm has a flaw. If the ball starts in an odd position, it will end up in an odd position after an even number of moves. Your algorithm assumes that it's in an even position after six moves. That will never work. Further, your sequence of lifts doesn't positively identify where the ball is.

For example, imagine that the ball starts under cup #1. Following your sequence of lifts, the following is possible.

1. Lift cup 2. Ball moves to cup 2.
2. Lift cup 3. Ball moves to cup 1.
3. Lift cup 4. Ball moves to cup 2.
4. Lift cup 5. Ball moves to cup 1.
5. Lift cup 5 (again). Ball moves to cup 2.
6. Lift cup 4. Ball moves to cup 1.

After step 6, the ball can move from cup 2 to cup 1 or cup 3. So you don't know where it is.