array shift and sum

Question

Help with solving this problem, or give me the name of the algorithm for this:

A one-dimensional array of length N is given randomly filled with numbers, all of which are powers of two. Two operations can be performed on the array: left and right shift. When left (right) shifted, two same numbers standing side by side are summarized; a new value is placed in the left (right) cell. The values in the array to the right (left) are shifted one position to the left (right). [1,4,16,8,8,2,1] > left > [1,4,16,16,2,1] > right > [1,4,32,2,1]. Find a sequence of shifts that will result in a minimum array length.

@Andreas I need at least the name of the algorithm, and then I myself will implement it. — cipoj90001, Dec 18 '19 at 17:49
I don't understand the description, what's the difference between left and right "shifting"? More specifically, what's "a new value is placed in the left (right) cell"? — ASDFGerte, Dec 18 '19 at 17:58
In your example, how would the result be different if you first do a right shift, and then a left shift? You speak of a "new value is placed...", but I don't see this in your example, and wonder what that value would be? — trincot, Dec 18 '19 at 18:14

score 0 · Accepted Answer · answered Dec 18 '19 at 20:03

The described shifts seem to be a generalisation of what is happening in the 2048 game, but in one dimension only, and without any zeroes. I don't think there is a name for the algorithm, but the transformation is often called "tile merging" in the context of the 2048 game.

First note that there is no difference in the effect of a left shift or a right shift. Both give the same outcome.

You can walk through the array with one index, and keep track of another, secondary index that will not increase whenever a "merge" of two values can take place. Instead that secondary index will move back after each merge, as long as merges can happen, and then it will increment again in tandem with the main index. When no merge takes place, the value at the primary index is merely copied to the secondary one.

Here is how that looks in code:

function collapse(arr) {
    let j = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] === arr[j]) {
            do {
                arr[j] *= 2;
                j--;
            } while (j >= 0 && arr[j] === arr[j+1]);
            j++;
        } else {
            j++;
            arr[j] = arr[i];
        }
    }
    // clip the array, throw away anything beyond index j:
    arr.length = j+1;
    return arr;
}

// Example
let arr = [1,4,16,8,8,2,1];
console.log(collapse(arr));

Here the function returns the resulting array, but if you only need the length of it, you can return j+1 instead.

array shift and sum

1 Answers1