Algorithm for solving this distributing beads puzzle?

Question

Lets say you have a circle (like below) with N spots, and you have N beads distributed in the slots.

Here's an example:

Each bead can be moved clockwise for X slots, which costs X^2 dollars. Your goal is to end up with one bead in each slot. What is the minimum amount of money you have to spend to achieve this task?

More interesting variation of this problem: Algorithm for distributing beads puzzle (2)?

Answer 1

In this answer I assume beads can only be moved once. Otherwise it would be evident that beads should only move one square at a time, which makes this problem much less interesting: the sum of squares would downgrade to a simple sum of moves.

The problem can be solved in O(n) time, and at point 4 I give a JavaScript implementation. If you want to skip the reasoning that lead to the algorithm, just scroll to that section.

Edit: I added a section B, where a variant of the problem is analysed.

But here are the observations that lead to the suggested algorithm for the question at hand:

1. No overtaking

It should be observed that in an optimal solution the beads will never be moved such that one bead "overtakes" another. The alternative solution where these two beads would swap their target slots would always give a lower sum of squares.

To formalise this a bit, let's say one bead moves from slot number a to b, and another from c to d. It is required that they cannot move counter-clockwise. Let's now assume the first overtakes the other, then we have all of these truths:

1. a < b
2. c < d
3. a < c
4. b > d

Then the squares of the moves of the overtaking version, and the squares of moves of the alternative version (where beads swap targets), compare like this:

(b-a)² + (d-c)² > (d-a)² + (b-c)²

Proof is that the above inequality breaks down to:

b²-2ab+a² + d²-2cd+c² > d²-2ad+a² + b²-2bc+c²
-2ab + -2cd > -2ad + -2bc
ab + cd < ad + bc
a(b-d) < c(b-d)
a < c
true

As a consequence, the beads that share the same slot at the start will always end up in neighbouring slots in the optimal solution.

More generally:

2. Only look at solutions where beads stay in same order

So -- if we give an (arbitrary) order to the beads that start in the same slot -- we can say that an optimal solution can be found where the order of beads is the same as in the original input (since overtaking is excluded).

This also means that we can quite easily find a candidate solution where we pick up the beads by order number and put them in the slot with that same order number. This might not be the optimal solution, but it could be. It might even be invalid if it contains a counter-clockwise move. But it is still useful to start with.

3. Cycle solution to optimal one

Any other potential solution that keeps the same order is found by just moving all beads to the next slot, until a valid and best solution is found. I will call such a move a cycle.

If the first candidate solution is invalid because of a counter-clockwise move, it is straightforward to find the best solution: take the largest counter-clockwise move, and add the opposite of this move to all the moves, including that one. This will make all offending moves non-counter-clockwise (at least one will be a zero-move). Cycling further will evidently make the sum of squares larger. So this is the optimal solution.

If on the other hand the candidate solution is valid, but none of the beads stays in position, the solution can be improved by cycling the other way round, i.e. by making the moves smaller, until at least one bead stays in position.

4. Algorithm

With all of the above information, I present here the algorithm implemented in JavaScript, which can be tested in this live snippet:

function optimalSpread(beadCounts) {
    // Initialisation
    var n = beadCounts.length;
    var solution = {
        // Keep track of sum of squares of moves
        // A move is a number of slots and only be positive (clockwise).
        sumSquares: 0,
        // Keep track of sum of moves.
        sumMoves: 0,
        // Per slot, keep an array with one element per bead, but
        // we start with empty arrays
        movesPerSlotPerBead: [],
    };
    // Build a first a non-optimised solution. 
    // Assign beads in FIFO order to consecutive slots.
    // *move*, when added to the current slot number, identifies the first slot where
    // a bead needs to end up in this solution. Note that this initial solution
    // may do counter-clockwise moves. This will be corrected later.
    // =O(n)
    var move = 0,
        totalBeadCount = 0,
        minMove = 0;
    beadCounts.forEach(function(beadCount, slotId) {
        // check sum
        totalBeadCount += beadCount;
        // See where the next bead would be moved (relative to slot)
        move += beadCount - 1;
        // and keep the minimum value. Can be negative, meaning a 
        // counter clockwise move.
        if (move < minMove) minMove = move;
    });
    // abort if number of beads is not equal to number of slots
    if (totalBeadCount !== n) return {error: "invalid input"}; 
    // Improve solution by making sure there are no counter-clockwise
    // moves, and at least one bead stays unmoved (0).
    // Apply correction we got from previous loop to ensure this.
    // =O(n)
    move = -minMove;
    beadCounts.forEach(function(beadCount, slotId) {
        solution.movesPerSlotPerBead[slotId] = [];
        // Move each bead into next available slot
        for (; beadCount > 0; beadCount--, move++) {
            // Store the move for this bead
            solution.movesPerSlotPerBead[slotId].push(move);
            solution.sumMoves += move;
            solution.sumSquares += move*move;
        }
        // Compensate the increment of slotId
        move--;
    });
    // The solution is now optimal:
    // Cycling counter-clockwise would make at least one bead go that way;
    // Cycling clockwise would increase the sum of squares (as all moves are
    //    non-negative values)
    return solution;
}

function randomInput(n) {
    // Start with slots having all zero beads:
    beadCounts = Array.from({length: n}, x => 0);
    // Randomly assign beads to slots, keeping a count per slot
    for (var i = 0; i < n; i++) {
        beadCounts[Math.floor(Math.random() * n)]++;
    }
    return beadCounts;
}

// Link with I/O
var input = document.getElementById('input');
var randomize = document.getElementById('randomize');
var calculate = document.getElementById('calculate');
var output = document.getElementById('output');

// Capture events
randomize.onclick = function() {
    var n = 5 + Math.floor(Math.random() * 20);
    input.value = randomInput(n).join(',');
    calculate.onclick();
};

calculate.onclick = function() {
    var beadCounts = input.value.split(',').map(Number);
    var solution = optimalSpread(beadCounts);
    if (solution.error) {
        output.textContent = 'Error: ' + solution.error;
        return;
    }
    output.textContent = 
        '\nInput: ' + JSON.stringify(beadCounts) +
        '\nSum of squares of moves: ' + solution.sumSquares +
        '\nSum of moves: ' + solution.sumMoves +
        '\nMoves[slot][bead]: ' + JSON.stringify(solution.movesPerSlotPerBead);
};

Comma-separated list of number of beads per slot:<br/>
<input id="input" size="40" value="3,0,1,0,1,0,2,2,2,1,1,0,1,0">
<button id="randomize">Randomize</button><br/>
<button id="calculate">Find optimal spread</button></br>
<pre id="output"></pre>

This snippet takes an array where each index represents a slot, and the value represents the number of beads in that slot. It outputs the original array, the sum of squares of the optional solution, and the list of moves for the beads.

Output for the example problem in the question is:

Input: [3,0,1,0,1,0,2,2,2,1,1,0,1,0]
Sum of squares of moves: 60
Sum of moves: 26
Moves[slot][bead]: [[1,2,3],[],[2],[],[1],[],[0,1],[1,2],[2,3],[3],[3],[],[2],[]]

So the answer to the example configuration is: 60 dollars.

---

B. Addendum: Without Clockwise Requirement

What if the requirement for clockwise moves were removed, and moves could be in any direction? This was not asked, but I thought it was an interesting variant.

Here are the additional observations that apply for that case:

B.1. Sum of squares of one solution can be used for next

A cycle does not need to be actually performed in order to find the sum of squares of that new configuration:

Let's say we have three beads and three slots, and the beads have each been moved to their target slots by moving them x, y and z slots respectively. For instance, if they all were in slot 0, we could get x, y, z values of 0, 1, 2 (but also -1, 0, 1 or even 5, 6, 7 if we want to exaggerate).

The sum of squares is:

x²+y²+z²

If now we cycle this solution and thus add one slot more to each bead's move, the squares become:

(x+1)²+(y+1)²+(z+1)²

or:

x²+y²+z²   +3    +2(x+y+z)

In general, cycling a configuration with n beads like that increases the sum of squares with this term:

n + 2.sum(moves)

So, the algorithm can take advantage of that and quickly calculate the sum of squares of the solution resulting from a cycle. This can be repeated for subsequent cycles.

B.2. Only one local minimum for sum of squares

Finally, the sum of squares for each consecutive cycle (solution), will be a function with a parabolic shape, i.e. once a local minimum has been found, there is no need to look for another one; there isn't. We can see that from the above formula for increasing values for sum(moves). At the most we might have an equal sum of squares for two neighbouring cycles.

B.3. Algorithm

Here follows the algorithm implemented in JavaScript:

function optimalSpread(beadCounts) {
    // Initialisation
    var n = beadCounts.length;
    var solution = {
        // Keep track of sum of squares of moves
        // A move is a number of slots and can be negative or positive.
        sumSquares: 0,
        // Keep track of sum of moves.
        sumMoves: 0,
        // Per slot, keep an array with one element per bead, but
        // we start with empty arrays
        movesPerSlotPerBead: [],
    };
    // Build a first a non-optimised solution. 
    // Assign beads in FIFO order to consecutive slots.
    // *move*, when added to the current slot number, identifies the first slot where
    // a bead needs to end up in this solution.
    // =O(n)
    var move = 0,
        totalBeadCount = 0;
    beadCounts.forEach(function(beadCount, slotId) {
        solution.movesPerSlotPerBead[slotId] = [];
        // check sum
        totalBeadCount += beadCount;
        // Move each bead into next available slot
        for (; beadCount > 0; beadCount--, move++) {
            // Store the move for this bead
            solution.movesPerSlotPerBead[slotId].push(move);
            solution.sumMoves += move;
            solution.sumSquares += move*move;
        }
        // Compensate the increment of slotId
        move--;
    });
    // abort if number of beads is not equal to number of slots
    if (totalBeadCount !== n) return {error: "invalid input"}; 
    // See if solution can be improved by shifting all beads in one direction.
    // =O(n)
    bestMoveCorrection = 0;
    while (true) {
        // Improvement is only possible in the direction dictated by sumMoves 
        moveCorrection = (solution.sumMoves < 0 ? 1 : -1);
        // Calculate the delta this brings to sumSquares:
        // (a+1)²+(b+1)²+ ... +(x+1)² = a²+b²+...+x² +n  +2(a+b+...+x) 
        sumSquaresChange = n + moveCorrection * 2 * solution.sumMoves;
        // Stop if this brings no improvement anymore
        if (sumSquaresChange >= 0) break;
        // It is an improvement; keep it
        solution.sumMoves += moveCorrection * n;
        solution.sumSquares += sumSquaresChange;
        bestMoveCorrection += moveCorrection;
    }
    // Apply correction to solution, to make it optimal
    // =O(n)
    solution.movesPerSlotPerBead.forEach(function(moves) {
        moves.forEach(function(move, idx) {
            moves[idx] += bestMoveCorrection;
        });
    });
    return solution;
}

function randomInput(n) {
    // Start with slots having all zero beads:
    beadCounts = Array.from({length: n}, x => 0);
    // Randomly assign beads to slots, keeping a count per slot
    for (var i = 0; i < n; i++) {
        beadCounts[Math.floor(Math.random() * n)]++;
    }
    return beadCounts;
}

// Link with I/O
var input = document.getElementById('input');
var randomize = document.getElementById('randomize');
var calculate = document.getElementById('calculate');
var output = document.getElementById('output');

// Capture events
randomize.onclick = function() {
    var n = 5 + Math.floor(Math.random() * 20);
    input.value = randomInput(n).join(',');
    calculate.onclick();
};

calculate.onclick = function() {
    var beadCounts = input.value.split(',').map(Number);
    var solution = optimalSpread(beadCounts);
    if (solution.error) {
        output.textContent = 'Error: ' + solution.error;
        return;
    }
    output.textContent = 
        '\nInput: ' + JSON.stringify(beadCounts) +
        '\nSum of squares of moves: ' + solution.sumSquares +
        '\nSum of moves: ' + solution.sumMoves +
        '\nMoves[slot][bead]: ' + JSON.stringify(solution.movesPerSlotPerBead);
};

Comma-separated list of number of beads per slot:<br/>
<input id="input" size="40" value="3,0,1,0,1,0,2,2,2,1,1,0,1,0">
<button id="randomize">Randomize</button><br/>
<button id="calculate">Find optimal spread</button></br>
<pre id="output"></pre>

This snippet takes an array where each index represents a slot, and the value represents the number of beads in that slot. It outputs the original array, the sum of squares of the optional solution, and the list of moves for the beads.

Output for the example problem in the question is:

Input: [3,0,1,0,1,0,2,2,2,1,1,0,1,0]  
Sum of squares of moves: 12  
Sum of moves: -2  
Moves[slot][bead]: [[-1,0,1],[],[0],[],[-1],[],[-2,-1],[-1,0],[0,1],[1],[1],[],[0],[]]

NB: This is not the answer to the question, because it allows counter-clockwise moves. For the answer, see first half of this response.

Answer 2

I implemented this in MATLAB. It relies on much the same logic as trincot's excellent answer. In this implementation, which also runs in O(n) time, the first step is to find a space to start where one bead should remain unmoved. I've yet to prove that this always works out to an optimal solution, but maybe I'll come back to it.

Oh, and this code also relies on the square pyramid formula https://en.wikipedia.org/wiki/Square_pyramidal_number

clear; 
%// inputBps (beads per space) will be our starting point.
%// inputBps=[2 0 3 0 0 0 4 0 1 0 1 0 1 2];
%// inputBps=[2 0 2 0 0 2];
%// inputBps=[1 1 1 1 1];
inputBps=[3 0 1 0 1 0 2 2 2 1 1 0 1 0];

%// This first block of code finds a good place to start.
%// We find a candidate for a bead that should not move.
okStart = 1;
stack = 0;
for i=1:length(inputBps)
    if inputBps(i)>1
        stack = stack + inputBps(i)-1;
    end
    if inputBps(i)==0 && stack<=0
        okStart = i+1;
    end
    if inputBps(i)==0 && stack>0
        stack=stack-1;
    end
end

%// This lets us start at the space we found above.
bps = [inputBps(okStart:end) inputBps(1:okStart-1)];

sum=0;
nextFree=1;
for k=1:length(bps)
    %// firstMoves are the moves that all the beads
    %// in a space have to take because they were "forced out."
    firstMoves = nextFree-k;

    %// Say firstMoves=3 and bps(k)=2. Then our our two beads
    %// moved three spaces and four spaces, like this:
    %// sum = sum + 3^2 + 4^2.  Rewriting:
    %// sum = sum + (1^2 + 2^2 + 3^2 + 4^2) - (1^2 + 2^2)
    sum = sum + squares( bps(k) + firstMoves - 1 ) - squares( firstMoves-1 );

    %// Now calculate the next space that can accept a bead.
    nextFree = nextFree+bps(k);
end

.

function [ y ] = squares( x )
%SQUARES Returns sqaure payramid of input
y = x*(x+1)*(2*x+1) / 6 ;
end

And the result for the problem in the question:

sum =

    60