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
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:
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.
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 2
s or 4
s 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..