How can I implement the merge functionality for 2048

Question

I am trying to implement the game 2048 using JavaScript. I am using a two-dimensional array to represent the board. For each row, it is represented using an array of integers.

Here I am focused on implementing the merge left functionality i.e. the merge that happens after the user hits left on their keyboard.

Here are a set of test cases that I came up with

const array1 = [2, 2, 2, 0] //  [4,2,0,0]
const array2 = [2, 2, 2, 2] // [4,4,0,0]
const array3 = [2, 0, 0, 2] // [4,0,0,0]
const array4 = [2, 2, 4, 16] // [4,4,16,0]

The commented part is the expected results after merge left happened.

Here is my attempt

const arrays = [
  [2, 2, 2, 0], //  [4,2,0,0]
  [2, 2, 2, 2], // [4,4,0,0]
  [2, 0, 0, 2], // [4,0,0,0]
  [2, 2, 4, 16] // [4,4,16,0]
];

function mergeLeft(array) {
  let startIndex = 0
  let endIndex = 1
  while (endIndex < array.length) {
    if (array[startIndex] === array[endIndex]) {
      array[startIndex] = array[startIndex] + array[endIndex]
      array[endIndex] = 0
      startIndex++
    }
    endIndex++
  }
  return shift(array, 'left')
}

function shift(array, dir) {
  if (dir === 'left') {
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] === 0) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]]
      }
    }
  }
  // omitting when dir === 'right', 'up', 'down' etc.
  return array
}

arrays.forEach(a => console.log(mergeLeft(a)));

So the idea here is that I merged the array and then shift the non-zero items to the left.

My current solution is buggy for this particular case - when the array is [2, 2, 2, 2], the output is [4,2,2,0] when the expected output is [4,4,0,0]

I know that my implementation is not elegant either. So I would love to see how this can be implemented in a (much) better way.

By the way I found on code review stack exchange there is a python implementation that seems to be working. However, I don't really know Python nor functional programming paradigm. I would appreciate it if someone can take a look at it and see if how this can be translated into JavaScript

Answer 1

I think a recursive version is simplest here:

const zeroFill = xs => 
  xs .concat ([0, 0, 0, 0]) .slice (0, 4)

const shift = ([n0, n1, ...ns]) =>
  n0 == undefined
    ? []
  : n0 == 0
    ? shift ([n1, ...ns])
  : n1 == 0
    ? shift ([n0, ...ns])
  : n0 == n1
    ? [n0 + n1, ... shift (ns)]
  : [n0, ...shift ([n1, ... ns])]

const shiftLeft = (ns) => 
  zeroFill (shift (ns))

const arrays = [[2, 2, 2, 0], [2, 2, 2, 2], [2, 0, 0, 2], [2, 2, 4, 16], [0, 8, 2, 2], [0, 0, 0, 0]];

arrays .forEach (
  a => console.log(`${JSON .stringify (a)}: ${JSON .stringify (shiftLeft (a))}`)
)

Our basic shift is wrapped with zeroFill, which adds trailing zeros to the the array, to make it four long.

The main function is shift, which does a shift-left of a row, but if I were to build a complete 2048, I would used this for all shifts, simply translating the directions to the indices required. It works like this:

• If our array is empty, we return an empty array
• If the first value is zero, we ignore it and continue with the rest of the array
• If the second value is zero, we remove it and recur with the remainder (including the first value)
• If the first two values are equal, we combine them for the first spot and recur on the remainder
• Otherwise, we keep the first value, and then recur on everything else (including the second value)

Although we could remove the wrapper, merging the zero-filling into the main function, so that, for instance in the second case, instead of returning shift([n1, ...ns]) we would return zeroFill(shift([n1, ...ns])). But that would mean calling the zero-fill several times for no good reason.

Update

A comment asked for clarification on how I would use this for shifting boards in all directions. Here is my first thought:

// utility functions
const reverse = (xs) => 
  [...xs] .reverse();

const transpose = (xs) => 
  xs [0] .map ((_, i) => xs .map (r => r[i]))

const rotateClockwise = (xs) =>
  transpose (reverse (xs))

const rotateCounter = (xs) => 
  reverse (transpose (xs))

// helper functions
const shift = ([n0, n1, ...ns]) =>
  n0 == undefined
    ? []
  : n0 == 0
    ? shift ([n1, ...ns])
  : n1 == 0
    ? shift ([n0, ...ns])
  : n0 == n1
    ? [n0 + n1, ... shift (ns)]
  : [n0, ... shift ([n1, ... ns])]

const shiftRow = (ns) => 
  shift (ns) .concat ([0, 0, 0, 0]) .slice (0, 4)

// main functions
const shiftLeft = (xs) => 
  xs .map (shiftRow)

const shiftRight = (xs) => 
  xs .map (x => reverse (shiftRow (reverse (x))))

const shiftUp = (xs) =>
  rotateClockwise (shiftLeft (rotateCounter (board)))  

const shiftDown = (xs) =>
  rotateClockwise (shiftRight (rotateCounter (board)))  

// sample data
const board = [[4, 0, 2, 0], [8, 0, 8, 8], [2, 2, 4, 8], [0, 0, 4, 4]]

// demo
const display = (title, xss) => console .log (`----------------------\n${title}\n----------------------\n${xss .map (xs => xs .map (x => String(x).padStart (2, ' ')) .join(' ')).join('\n')}`)

display ('original', board)
display ('original shifted left', shiftLeft (board))
display ('original shifted right', shiftRight (board))
display ('original shifted up', shiftUp (board))
display ('original shifted down', shiftDown (board))

.as-console-wrapper {max-height: 100% !important; top: 0}

We start with function to reverse a copy of an array, and to transpose a grid over the main diagonal (northwest to southeast). We combine those two in order to create functions to rotate a grid clockwise and counter-clockwise. Then we include the function discussed above, slightly renamed, and with the zero-fill helper inlined.

Using these we can now write our directional shift function fairly easily. shiftLeft just maps shiftRow over the rows. shiftRight first reverses the rows, calls shiftLeft and then reverses them again. shiftUp and shiftDown rotate the board counter-clockwise call shiftLeft and shiftRight, respectively, and then rotates the board clockwise.

Note that none of these main functions mutate your data. Each returns a new board. That is one of the most important tenets of functional programming: treat data as immutable.

This is not a full 2048 system. It doesn't randomly add new 2s or 4s to the board, nor does it have any notion of a user interface. But I think it's probably a reasonably solid core for a functional version of the game..

Answer 2

You can try this.

const arrays = [
  [2, 2, 2, 0], //  [4,2,0,0]
  [2, 2, 2, 2], // [4,4,0,0]
  [2, 0, 0, 2], // [4,0,0,0]
  [2, 2, 4, 16] // [4,4,16,0]
];


function shiftLeft(array) {
    op = []
    while(array.length!=0){
        let v1 = array.shift();
        while(v1==0 && array.length>0){
            v1 = array.shift();
        }

        if(array.length==0){
            op.push(v1);
        }else{
            let v2 = array.shift();
            while(v2==0 && array.length>0){
                v2 = array.shift();
            }

            if(v1==v2){
                op.push(v1+v2);
            }else{
                op.push(v1);
                array.unshift(v2);
            }
        }
    }

    while(op.length!=4){
        op.push(0);
    }
  return op
}

arrays.forEach(a => console.log(shiftLeft(a)));

Answer 3

Here is a function that performs the merge and shift in one loop:

function mergeLeft(array) {
    let startIndex = 0;
    for (let endIndex = 1; endIndex < array.length; endIndex++) {
        if (!array[endIndex]) continue;
        let target = array[startIndex];
        if (!target || target === array[endIndex]) { // shift or merge
            array[startIndex] += array[endIndex];
            array[endIndex] = 0;
        } else if (startIndex + 1 < endIndex) {
            endIndex--; // undo the next for-loop increment
        }
        startIndex += !!target;
    }
    return array;
}

// Your tests:
const arrays = [
  [2, 2, 2, 0], // [4,2,0,0]
  [2, 2, 2, 2], // [4,4,0,0]
  [2, 0, 0, 2], // [4,0,0,0]
  [2, 2, 4, 16] // [4,4,16,0]
];

for (let array of arrays) console.log(...mergeLeft(array));

Explanations

The for loop increments the endIndex from 1 to 3 included. This index represents a potential value that needs to shift and/or merge.

If that index refers to an empty slot (value is 0), then nothing needs to happen with it, and so we continue with the next iteration of the loop.

So now we are in the case where endIndex refers to a non-zero value. There are two cases where something needs to happen with that value:

• The value at startIndex is zero: in that case the value at endIndex must move to startIndex

• The value at startIndex is equal to that at endIndex: in that case the value at endIndex must also move to startIndex, but adding to it what was already there.

These cases are very similar. In the first case we could even say that the value at endIndex is added to the one at startIndex since the latter is zero. So these two cases are handled in one if block.

If we are not in either of these two cases then we know that the value at startIndex is non-zero and different from the one at endIndex. In that case we should leave the value at startIndex unaltered and just move on. However, we should reconsider the value of this same endIndex again in the next iteration, as it might need to move still. So that is why we do endIndex-- so to neutralise the loop's endIndex++ that will happen one instant later.

There is one case where we do want to go to the next endIndex: that is when startIndex would become equal to endIndex: that should never be allowed in this algorithm.

Finally, startIndex is incremented when it originally had a non-zero value. However, if it was zero at the start of this iteration, it should be reconsidered in the next iteration of the loop. So then we do not add 1 to it. startIndex += !!target is just another way for doing:

if (target > 0) startIndex++;