如何实现 2048 的合并功能
How can I implement the merge functionality for 2048
我正在尝试使用 JavaScript 实现 the game 2048。我正在使用二维数组来表示电路板。对于每一行，它都使用整数数组表示。
这里我主要关注实现左合并功能，即用户在键盘上点击左键后发生的合并。
这是我想出的一组测试用例
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]
注释部分是merge left发生后的预期结果。
这是我的尝试
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)));
所以这里的想法是我合并数组，然后将非零项向左移动。
对于这种特殊情况，我当前的解决方案存在错误 - 当数组为 [2, 2, 2, 2] 时，输出为 [4,2,2,0] 而预期输出为 [4,4,0,0]
我知道我的实现也不优雅。所以我很想看看如何以（好得多）更好的方式实现它。
顺便说一下，我在代码审查堆栈交换中发现有一个 python 实现似乎可以正常工作。但是，我真的不知道 Python 也不知道函数式编程范例。如果有人可以 take a look at it 看看如何将其翻译成 JavaScript
，我将不胜感激
你可以试试这个。
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)));
我认为这里的递归版本是最简单的：
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))}`)
)
我们的基本 shift 用 zeroFill 包装，它向数组添加尾随零，使其长度为四。
主要功能是shift，它会左移一行，但如果我要构建一个完整的 2048，我会在所有班次中使用它，只需将方向转换为索引必需的。它是这样工作的：
- 如果我们的数组是空的，我们return一个空数组
- 如果第一个值为零，我们忽略它并继续数组的其余部分
- 如果第二个值为零，我们将其删除并与余数（包括第一个值）一起递归
- 如果前两个值相等，我们将它们合并为第一个点并在余数上重复
- 否则，我们保留第一个值，然后对其他所有值（包括第二个值）进行递归
尽管我们可以删除包装器，将零填充合并到主函数中，例如在第二种情况下，我们将 returning shift([n1, ...ns]) 而不是 returning shift([n1, ...ns]) =] zeroFill(shift([n1, ...ns]))。但这意味着无缘无故多次调用零填充。
更新
一条评论要求澄清我将如何使用它来向各个方向移动板。这是我的第一个想法：
// 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}
我们从反转数组副本的函数开始，并在主对角线上（西北到东南）转置网格。我们将这两者结合起来，以创建顺时针和逆时针旋转网格的函数。然后我们包含上面讨论的函数，稍微重命名，并内联零填充助手。
使用这些我们现在可以很容易地编写我们的方向转换函数。 shiftLeft 只是将 shiftRow 映射到行上。 shiftRight 首先反转行，调用 shiftLeft 然后再次反转它们。 shiftUp和shiftDown逆时针旋转棋盘分别调用shiftLeft和shiftRight，然后顺时针旋转棋盘。
请注意，这些主要函数中的 none 会改变您的数据。每个 return 都是一个新板。这是函数式编程最重要的原则之一：将数据视为不可变的。
这不是完整的 2048 系统。它不会随机添加新的 2s 或 4s 到看板，也没有任何用户界面的概念。但我认为对于游戏的功能版本来说，它可能是一个相当坚实的核心..
这是一个在一个循环中执行合并和移位的函数：
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));
解释
for 循环将 endIndex 从 1 增加到 3。该索引表示需要移位的潜在值and/or合并。
如果该索引引用一个空槽（值为 0），则不需要对其进行任何处理，因此我们 continue 进行下一次循环迭代。
所以现在我们处于 endIndex 指的是非零值的情况。有两种情况需要使用该值发生某些事情：
startIndex 处的值为零：在这种情况下，endIndex 处的值必须移至 startIndex
startIndex 的值等于 endIndex 的值：在这种情况下 endIndex 的值也必须移动到 startIndex，但添加到它已经存在的东西。
这些案例非常相似。在第一种情况下，我们甚至可以说 endIndex 处的值是 添加 到 startIndex 处的值，因为后者为零。所以这两种情况在一个 if 块中处理。
如果我们不属于这两种情况中的任何一种，那么我们就知道 startIndex 处的值非零并且不同于 endIndex 处的值。在那种情况下，我们应该保持 startIndex 的值不变，继续前进。但是，我们应该在下一次迭代中再次重新考虑同一个 endIndex 的值，因为它可能需要继续移动。所以这就是为什么我们这样做 endIndex-- 来中和循环的 endIndex++ ，它会在一瞬间后发生。
有一种情况我们想去下一个endIndex：那就是当startIndex等于endIndex：在这个算法中绝对不允许这样做。
最后，startIndex 在其最初具有非零值时递增。但是，如果在本次迭代开始时为零，则应在循环的下一次迭代中重新考虑。所以我们不给它加1。 startIndex += !!target 只是另一种方式：
if (target > 0) startIndex++;
我正在尝试使用 JavaScript 实现 the game 2048。我正在使用二维数组来表示电路板。对于每一行，它都使用整数数组表示。
这里我主要关注实现左合并功能，即用户在键盘上点击左键后发生的合并。
这是我想出的一组测试用例
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]
注释部分是merge left发生后的预期结果。
这是我的尝试
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)));
所以这里的想法是我合并数组，然后将非零项向左移动。
对于这种特殊情况，我当前的解决方案存在错误 - 当数组为 [2, 2, 2, 2] 时，输出为 [4,2,2,0] 而预期输出为 [4,4,0,0]
我知道我的实现也不优雅。所以我很想看看如何以（好得多）更好的方式实现它。
顺便说一下，我在代码审查堆栈交换中发现有一个 python 实现似乎可以正常工作。但是，我真的不知道 Python 也不知道函数式编程范例。如果有人可以 take a look at it 看看如何将其翻译成 JavaScript
，我将不胜感激你可以试试这个。
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)));
我认为这里的递归版本是最简单的：
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))}`)
)
我们的基本 shift 用 zeroFill 包装，它向数组添加尾随零，使其长度为四。
主要功能是shift，它会左移一行，但如果我要构建一个完整的 2048，我会在所有班次中使用它，只需将方向转换为索引必需的。它是这样工作的：
- 如果我们的数组是空的，我们return一个空数组
- 如果第一个值为零，我们忽略它并继续数组的其余部分
- 如果第二个值为零，我们将其删除并与余数（包括第一个值）一起递归
- 如果前两个值相等，我们将它们合并为第一个点并在余数上重复
- 否则，我们保留第一个值，然后对其他所有值（包括第二个值）进行递归
尽管我们可以删除包装器，将零填充合并到主函数中，例如在第二种情况下，我们将 returning shift([n1, ...ns]) 而不是 returning shift([n1, ...ns]) =] zeroFill(shift([n1, ...ns]))。但这意味着无缘无故多次调用零填充。
更新
一条评论要求澄清我将如何使用它来向各个方向移动板。这是我的第一个想法：
// 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}
我们从反转数组副本的函数开始，并在主对角线上（西北到东南）转置网格。我们将这两者结合起来，以创建顺时针和逆时针旋转网格的函数。然后我们包含上面讨论的函数，稍微重命名，并内联零填充助手。
使用这些我们现在可以很容易地编写我们的方向转换函数。 shiftLeft 只是将 shiftRow 映射到行上。 shiftRight 首先反转行，调用 shiftLeft 然后再次反转它们。 shiftUp和shiftDown逆时针旋转棋盘分别调用shiftLeft和shiftRight，然后顺时针旋转棋盘。
请注意，这些主要函数中的 none 会改变您的数据。每个 return 都是一个新板。这是函数式编程最重要的原则之一：将数据视为不可变的。
这不是完整的 2048 系统。它不会随机添加新的 2s 或 4s 到看板，也没有任何用户界面的概念。但我认为对于游戏的功能版本来说，它可能是一个相当坚实的核心..
这是一个在一个循环中执行合并和移位的函数：
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));
解释
for 循环将 endIndex 从 1 增加到 3。该索引表示需要移位的潜在值and/or合并。
如果该索引引用一个空槽（值为 0），则不需要对其进行任何处理，因此我们 continue 进行下一次循环迭代。
所以现在我们处于 endIndex 指的是非零值的情况。有两种情况需要使用该值发生某些事情：
startIndex处的值为零：在这种情况下，endIndex处的值必须移至startIndexstartIndex的值等于endIndex的值：在这种情况下endIndex的值也必须移动到startIndex，但添加到它已经存在的东西。
这些案例非常相似。在第一种情况下，我们甚至可以说 endIndex 处的值是 添加 到 startIndex 处的值，因为后者为零。所以这两种情况在一个 if 块中处理。
如果我们不属于这两种情况中的任何一种，那么我们就知道 startIndex 处的值非零并且不同于 endIndex 处的值。在那种情况下，我们应该保持 startIndex 的值不变，继续前进。但是，我们应该在下一次迭代中再次重新考虑同一个 endIndex 的值，因为它可能需要继续移动。所以这就是为什么我们这样做 endIndex-- 来中和循环的 endIndex++ ，它会在一瞬间后发生。
有一种情况我们想去下一个endIndex：那就是当startIndex等于endIndex：在这个算法中绝对不允许这样做。
最后，startIndex 在其最初具有非零值时递增。但是，如果在本次迭代开始时为零，则应在循环的下一次迭代中重新考虑。所以我们不给它加1。 startIndex += !!target 只是另一种方式：
if (target > 0) startIndex++;