Minimum number of moves to have brick towers in descending order

Question

I have a problem where I have n number of towers with i bricks. I need to rearrange them in descending order. I can only move on brick at a time to an adjacent tower. For example, for this problem:

4 3 0 1 1

The answer is 1 move as I can move one brick from the second tower to the third tower and have: 4 2 1 1 1.

For a problem like:

7 0 0 0 1

The answer is 3 moves to get: 7 1 0 0 0 or 6 1 1 0 0.

I currently have this function:

def compute_min_moves(towers, moves = 0):
    # Si 0 o 1 torre, no se hace nada
    if len(towers) < 2:
        return moves

    for i in range(len(towers)-1, 0 ,-1):
        if towers[i - 1] < towers[i]:
            diff = 0
            while towers[i - 1] < towers[i]:
                diff += 1
                towers[i - 1] += diff
                towers[i] -= diff
                moves += diff   
           
            sub_array = towers[i-1:]
            if not all(earlier >= later for earlier, later in zip(sub_array, sub_array[1:])):
                moves = compute_min_moves(towers, moves)

    return moves

I don't see how we could get the optimal solution.

Answer 1

Your initial solution only ever moved bricks between towers right to left, so the solution you proposed to 4 3 0 1 1, which is an optimal one, couldn't ever be found (since it moves pieces from left to right).

You made some adjustments to the algorithm that narrow the problem, but still only moves bricks left to right, and it loses track of what has been done before.

Another issue with the algorithm you came up with is that it keeps moving bricks from a tower until it has been equalised with the one next to it, which isn't necessarily the fastest way to a solution.

Here's an approach that works more generally: since you require the smallest number of moves, a breadth-first search is the best way to go. By exploring all possible moves from the starting position, and then all possible moves from those n=1 positions, and so on, you can guarantee that the first time you reach a solution, you will have done so in the fewest number of moves (although it won't find all such solutions - it terminates after finding a first).

What further complicates the problem, is that moves in both directions are allowed, you need to ensure you don't create cycles in the search.

A good mechanism for a breadth-first search is to create a queue of positions explored so far, adding newly reachable positions to the end of the queue (if they don't outright solve the problem) and continuing to do so while reading from the start of the queue.

Also note that it's clear that a solution can always be reached and that an algorithm like this will terminate if it succeeds in avoiding cycles. Eventually, all possible positions would be reached, and at least one of those will be sorted from high to low, left to right (many will, but we only need to believe it will always reach at least one).

Here's an example implementation of that approach.

def solved(towers):
    # True if towers is sorted from high to low, left to right
    return all(t1 >= t2 for t1, t2 in zip(towers, towers[1:]))


def solve(towers: list[int]) -> (int, list[int]):
    if solved(towers):
        return 0, towers
    # keep track of visited states, to avoid cycles
    visited = {tuple(towers)}
    # queue of states to expand on, preceded by the number of moves to reach them
    queue = [(0, towers)]
    # range of left indices to move between them and the next (right)
    r = range(len(towers) - 1)
    # it's safe to loop while True, since the algorithm is guaranteed to terminate
    # (although it may run for a very long time for large problems)
    while True:
        n, prev_pos = queue.pop(0)
        for i in r:
            # to avoid repeating the same code twice (once for each direction)
            # we iterate over a tuple of (direction and offset)
            for d, o in ((1, 1), (-1, 0)):
                # the tower we're moving from must contain at least one brick
                if prev_pos[i+o] > 0:
                    # copy the previous position and make a single move
                    new_pos = prev_pos.copy()
                    new_pos[i] += d
                    new_pos[i+1] -= d
                    # convert the new position in a (hashable) tuple to check visited
                    if (new_post_tuple := tuple(new_pos)) not in visited:
                        # if not visited before, check if it solves the problem
                        if solved(new_pos):
                            # as soon as a solution is found, break and return
                            return n+1, new_pos
                        # otherwise, avoid visiting it again
                        visited.add(new_post_tuple)
                        # add it to the queue to expand from later
                        queue.append((n+1, new_pos))


print(solve([4, 3, 0, 1, 1]))
print(solve([7, 0, 0, 0, 1]))

Output:

(1, [4, 2, 1, 1, 1])
(3, [6, 1, 1, 0, 0])

I did not see a straightforward way from the solution you had so far to one that always finds the optimal solution, so I opted to share a solution that I came up with. Please do investigate your own solution more closely based on the feedback above, and don't simply accept 'the answer' - I assume this is part of an assignment that's supposed to teach you something, so it won't help if you submit my work as your own. Perhaps only look at it and then try to implement your own based on what you learned.

A nice addition to explore the process:

class LoudList(list):
    def append(self, elem):
        print(f"Appending {elem}")
        super().append(elem)

And define queue as:

    queue = LoudList([(0, towers)])

Output:

Appending (1, [5, 2, 0, 1, 1])
Appending (1, [3, 4, 0, 1, 1])
(1, [4, 2, 1, 1, 1])
Appending (1, [6, 1, 0, 0, 1])
Appending (1, [7, 0, 0, 1, 0])
Appending (2, [5, 2, 0, 0, 1])
Appending (2, [6, 0, 1, 0, 1])
Appending (2, [6, 1, 0, 1, 0])
Appending (2, [7, 0, 1, 0, 0])
Appending (3, [4, 3, 0, 0, 1])
Appending (3, [5, 1, 1, 0, 1])
Appending (3, [5, 2, 0, 1, 0])
Appending (3, [6, 0, 0, 1, 1])
Appending  (3, [6, 0, 1, 1, 0])
(3, [6, 1, 1, 0, 0])

Answer 2

Maybe this solution is easier to understand

#function_to_find whether the list is in descending order
def descending(lst):
    for i in range(1, len(lst)):
        if lst[i] > lst[i-1]:
            return 0
    return 1

'''function_to_find the best list among all the possible
output based on the number of repeatation is minimum
'''
def better_lst(lst):
    l = []
    for x in lst:
        c = 0
        for y in x:

            #count the numbers of repeatation
            c = c + x.count(y)
        
        l.append(c)
    idx = l.index(min(l))
    return lst[idx]
    
def compute_min_moves(towers):
    lst = []
    
    #iterate thru lst
    for i,x in enumerate(towers):
    
        #create a list other than x say l
        l = towers[:i] + towers[i+1:]
        
        #iterate thru l
        for j, y in enumerate(l):
            y_idx = towers.index(y)
            l_2 = towers.copy()
            l_2[i] = x - 1
            l_2[y_idx] = y + 1
            if descending(l_2):
                lst.append(l_2)
    return better_lst(lst)

r = compute_min_moves([4, 3, 0, 1, 1])
print(r) # output : [4, 3, 1, 1, 0]

r = compute_min_moves([7, 0, 0, 0, 1])
print(r) # Output : [7, 1, 0, 0, 0]