Cookie monster problem: minimum moves to reduce all array elements to 0

You could use an A* algorithm with an "admissible" heurstic function.

When we have a list of distinct values, we can at best hope to take a pile, such that the other piles from which that amount is subtracted, now all match with another pile from which no subtraction took place. That means that at most we can reduce the number of piles with the selected pile and half of the others, so becomes (-1)/2

So we will need at least 1+floor(log₂) moves to reach the goal. We can see an instance of this minimum in [1,2,3,4,5,6,7]. The optimal solution for this particular input always takes the middle value, so that we halve the list with each move:

• take 4, result => [1,2,3,1,2,3] => [1,2,3]
• take 2, result => [1, 1] => [1]
• take 1, done.

Here is an implementation of a A* algorithm with that heuristic, and with marking configurations as "visited", to avoid solving the same pile-configuration twice:

from heapq import heappush, heappop

def food(piles):
    if not piles:
        return 0
    node = frozenset(piles)
    heap = [(len(node).bit_length(), 0, node, [])]
    visited = set()

    while heap:
        heuristic, cost, node, moves = heappop(heap)
        if len(node) == 1:
            return moves + [min(node)]
        if len(node) == 2:
            return moves + [min(node), max(node) - min(node)]
        cost += 1
        for amount in node:
            neighbor = frozenset(pile - amount if pile > amount else pile
                                 for pile in node if pile != amount)
            if neighbor not in visited:
                visited.add(neighbor)
                heappush(heap, (cost + len(neighbor).bit_length(), cost, neighbor, 
                                moves + [amount]))

This code returns the list of moves to perform. If it is only needed to return the minimal number of moves, then the above can be simplified to:

def food(piles):
    if not piles:
        return 0
    node = frozenset(piles)
    heap = [(len(node).bit_length(), 0, node)]
    visited = set()

    while heap:
        heuristic, cost, node = heappop(heap)
        if len(node) <= 2:
            return heuristic
        cost += 1
        for amount in node:
            neighbor = frozenset(pile - amount if pile > amount else pile
                                 for pile in node if pile != amount)
            if neighbor not in visited:
                visited.add(neighbor)
                heappush(heap, (cost + len(neighbor).bit_length(), cost, neighbor))

The proposal below does a brute force search, using as possible moves the size of each cookie pile (I'm not sure this ensures that this ensures optimality, as in principle a number not in the pile could be optimal). Also, since a brute force is done, in the worst case a factorial number of cases will be tried, so for inputs larger than 10 or 11 the execution time (and memory) may become unmanageable (but I'll show how to improve on that later).

The recursion depth is the length of the input - 2, so quite shallow. The algorithm is pretty simple: at any step, for all possible moves, it selects a move and then solve the sub-problem after that move is made. Since every movie eats at least one pile, the number of piles is always smaller at every step. It selects the shortest solution out of all possible ones. We could have done a slight optimisation here in that, since we know the smallest possible size of a solution, if we found a solution with this size we stop searching for more, since we cannot do better than the current one anyway.

An additional optimisation that was not done is that the question requests the length of the smallest solution, and the code below produces a sequence of moves that is (hopefully) minimal.

def solve_cookie_monster_problem(piles):
    if len(piles) <= 2:  # This is the end of recursion condition. 2 jars always need two moves
        return list(piles)

    # Try each element in piles as a move, and return the solution with the least moves
    best_try = range(len(piles) + 1)  # This is longer than any try
    for move in piles:
        next_piles = {(el - move) if el > move else el
                      for el in piles if el != move}
        current_try = solve_cookie_monster_problem(next_piles)
        current_try.append(move)
        if len(current_try) < len(best_try):
            best_try = current_try
    # best_try contains the shortest solution
    return best_try

The result is quite slow on my machine (all tests cases below run in about 5 s). There is a simple way to improve significantly this algorithm, if we note that each recursion step might visit problems that were already solved before: we can memoise the function, i.e. record previous results and simply return then, if we see a call with the same configuration of cookies. This is extremely simple to implement with python dictionaries. This simple improvement reduced the execution time from 5s to about 0.25s in the test cases below.

def solve_cookie_monster_memoised(initial_piles):
    """Memoised version of solve_cookie_monster.
    Essentially the same algorithm, but checking if that particular sub-problem hasn't been solved before."""

    memory = {}  # Will record subproblems already solved
    def get(value): return list(memory[value])  # Always create a copy when accessing the memoised
    initial_piles = frozenset(initial_piles)

    def algorithm(piles):
        if piles in memory:
            return get(piles)

        if len(piles) <= 2:  # This is the end of recursion condition. 2 jars always need two moves
            memory[piles] = list(piles)
            return get(piles)

        # Try each element in piles as a move, and return the solution with the least moves
        best_try = range(len(piles) + 1)  # This is longer than any try
        for move in piles:
            next_piles = frozenset({(el - move) if el > move else el
                                    for el in piles if el != move})
            current_try = algorithm(next_piles)
            current_try.append(move)
            if len(current_try) < len(best_try):
                best_try = current_try
        memory[piles] = best_try
        return get(piles)
    return algorithm(initial_piles)

Here are some test cases:

if __name__ == '__main__':
    import time
    piles1 = [2, 3, 5, 8, 13, 21, 34, 55, 89]
    piles2 = [11, 26, 37, 44, 49, 52, 68, 75, 87, 102]
    piles3 = [7, 4, 3, 1]
    piles4 = [20, 19, 14, 7, 4]
    piles5 = [18, 16, 9, 8]
    piles6 = [11, 26, 37, 44, 49, 52, 68, 75, 87, 89, 102]

    tstart = time.perf_counter()
    print(solve_cookie_monster_problem(piles1))  # [2, 3, 8, 21, 55]
    print(solve_cookie_monster_problem(piles2))  # [3, 4, 7, 15, 34, 68]
    print(solve_cookie_monster_problem(piles3))  # [1, 4, 3]
    print(solve_cookie_monster_problem(piles4))  # [1, 2, 4, 14]
    print(solve_cookie_monster_problem(piles5))  # [1, 2, 8, 16]
    print(solve_cookie_monster_problem(piles6))  # [1, 3, 7, 16, 37, 49]
    tend = time.perf_counter()
    print(f'Time: {tend-tstart:.2f}')  # About 5s on my machine

    print('\nMemoised version')
    tstart = time.perf_counter()
    print(solve_cookie_monster_memoised(piles1))  # [2, 3, 8, 21, 55]
    print(solve_cookie_monster_memoised(piles2))  # [3, 4, 7, 15, 34, 68]
    print(solve_cookie_monster_memoised(piles3))  # [1, 4, 3]
    print(solve_cookie_monster_memoised(piles4))  # [1, 2, 4, 14]
    print(solve_cookie_monster_memoised(piles5))  # [1, 2, 8, 16]
    print(solve_cookie_monster_memoised(piles6))  # [1, 3, 7, 16, 37, 49]
    tend = time.perf_counter()
    print(f'Time: {tend-tstart:.2f}')  # About 0.25s on my machine

A modification of this code to return only the length is trivial, and will improve a bit the performance (about 10% in the non-memoised version).