If interested theThe repository including tests can be found herehere.
2048 game: logic implementation
The following code implements the logic for moving tiles in the game 2048. The "move"(GameBoard::moveRight(), GameBoard::moveUp(), etc.) methods appear to be duplicating implementation. Any ideas for removing the duplication from the "move" methods? I would prefer that the time complexity for each "move" method be equivalent. I think an implementation that rotates the board to promote reusable movements would result in nonequivalent time complexities.
#include "GameBoard.h"
GameBoard::GameBoard(std::vector<std::vector<double>> _board) :
board(std::move(_board)),
N(board.size())
{
if (N == 0)
throw std::runtime_error("Empty board.");
for (const auto &row : board)
if (row.size() != N)
throw std::runtime_error("Invalid board dimensions.");
}
const std::vector<std::vector<double>> &GameBoard::getBoard()
{
return board;
}
void GameBoard::moveRight()
{
for (size_t row = 0; row < N; ++row)
{
std::vector<bool> hasBeenCombined(N, false);
for (size_t adjacentCol = N - 1; adjacentCol > 0; --adjacentCol)
{
const auto col = adjacentCol - 1;
const auto value = board[row][col];
const auto nextNonzeroOrLastColumn = getNextNonzeroOrLastColumn(row, col);
if (board[row][nextNonzeroOrLastColumn] == 0)
board[row].back() = value;
else if (
board[row][nextNonzeroOrLastColumn] == value &&
!hasBeenCombined[nextNonzeroOrLastColumn])
{
board[row][nextNonzeroOrLastColumn] += value;
hasBeenCombined[nextNonzeroOrLastColumn] = true;
}
else if (nextNonzeroOrLastColumn != adjacentCol)
board[row][nextNonzeroOrLastColumn - 1] = value;
else
continue;
board[row][col] = 0;
}
}
}
void GameBoard::moveLeft()
{
for (size_t row = 0; row < N; ++row)
{
std::vector<bool> hasBeenCombined(N, false);
for (size_t adjacentCol = 0; adjacentCol < N - 1; ++adjacentCol)
{
const auto col = adjacentCol + 1;
const auto value = board[row][col];
const auto previousNonzeroOrFirstColumn = getPreviousNonzeroOrFirstColumn(row, col);
if (board[row][previousNonzeroOrFirstColumn] == 0)
board[row].front() = value;
else if (
board[row][previousNonzeroOrFirstColumn] == value &&
!hasBeenCombined[previousNonzeroOrFirstColumn])
{
board[row][previousNonzeroOrFirstColumn] += value;
hasBeenCombined[previousNonzeroOrFirstColumn] = true;
}
else if (previousNonzeroOrFirstColumn != adjacentCol)
board[row][previousNonzeroOrFirstColumn + 1] = value;
else
continue;
board[row][col] = 0;
}
}
}
void GameBoard::moveDown()
{
for (size_t col = 0; col < N; ++col)
{
std::vector<bool> hasBeenCombined(N, false);
for (size_t adjacentRow = N - 1; adjacentRow > 0; --adjacentRow)
{
const auto row = adjacentRow - 1;
const auto value = board[row][col];
const auto nextNonzeroOrLastRow = getNextNonzeroOrLastRow(row, col);
if (board[nextNonzeroOrLastRow][col] == 0)
board.back()[col] = value;
else if (
board[nextNonzeroOrLastRow][col] == value &&
!hasBeenCombined[nextNonzeroOrLastRow])
{
board[nextNonzeroOrLastRow][col] += value;
hasBeenCombined[nextNonzeroOrLastRow] = true;
}
else if (nextNonzeroOrLastRow != adjacentRow)
board[nextNonzeroOrLastRow - 1][col] = value;
else
continue;
board[row][col] = 0;
}
}
}
void GameBoard::moveUp()
{
for (size_t col = 0; col < N; ++col)
{
std::vector<bool> hasBeenCombined(N, false);
for (size_t adjacentRow = 0; adjacentRow < N - 1; ++adjacentRow)
{
const auto row = adjacentRow + 1;
const auto value = board[row][col];
const auto previousNonzeroOrFirstRow = getPreviousNonzeroOrFirstRow(row, col);
if (board[previousNonzeroOrFirstRow][col] == 0)
board.front()[col] = value;
else if (
board[previousNonzeroOrFirstRow][col] == value &&
!hasBeenCombined[previousNonzeroOrFirstRow])
{
board[previousNonzeroOrFirstRow][col] += value;
hasBeenCombined[previousNonzeroOrFirstRow] = true;
}
else if (previousNonzeroOrFirstRow != adjacentRow)
board[previousNonzeroOrFirstRow + 1][col] = value;
else
continue;
board[row][col] = 0;
}
}
}
size_t GameBoard::getNextNonzeroOrLastColumn(size_t row, size_t col)
{
while (col < N - 1 && board[row][++col] == 0)
;
return col;
}
size_t GameBoard::getPreviousNonzeroOrFirstColumn(size_t row, size_t col)
{
while (col > 0 && board[row][--col] == 0)
;
return col;
}
size_t GameBoard::getNextNonzeroOrLastRow(size_t row, size_t col)
{
while (row < N - 1 && board[++row][col] == 0)
;
return row;
}
size_t GameBoard::getPreviousNonzeroOrFirstRow(size_t row, size_t col)
{
while (row > 0 && board[--row][col] == 0)
;
return row;
}
The corresponding header:
#pragma once
#include <vector>
#ifdef GAME_EXPORTS
#define GAME_API __declspec(dllexport)
#else
#define GAME_API __declspec(dllimport)
#endif
class GameBoard
{
// Order important for construction.
std::vector<std::vector<double>> board;
const size_t N;
public:
GAME_API GameBoard(std::vector<std::vector<double>> board);
GAME_API const std::vector<std::vector<double>> &getBoard();
GAME_API void moveRight();
GAME_API void moveLeft();
GAME_API void moveDown();
GAME_API void moveUp();
private:
size_t getNextNonzeroOrLastColumn(size_t row, size_t col);
size_t getPreviousNonzeroOrFirstColumn(size_t row, size_t col);
size_t getNextNonzeroOrLastRow(size_t row, size_t col);
size_t getPreviousNonzeroOrFirstRow(size_t row, size_t col);
};
The following tests demonstrate the intended usage:
#include "stdafx.h"
#include "CppUnitTest.h"
#include <GameBoard.h>
#include "assert_utility.h"
#include "test_board_utility.h"
namespace MSTest
{
TEST_CLASS(GameBoardTester)
{
public:
TEST_METHOD(testInvalidBoardThrows)
{
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
Assert::ExpectException<std::runtime_error>([]() { GameBoard({}); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ {}, {} }); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ { 0 }, {} }); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ {}, { 0 } }); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ { 0 }, { 0 } }); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ { 0, 0 }, {} }); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ {}, { 0, 0 } }); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ { 0, 0 }, { 0 } }); });
Assert::ExpectException<std::runtime_error>([]() { GameBoard({ { 0 }, { 0, 0 } }); });
GameBoard(
{
{ 0 }
}
);
GameBoard(
{
{ 0, 0 },
{ 0, 0 }
});
GameBoard(
{
{ 0, 0, 0 },
{ 0, 0, 0 },
{ 0, 0, 0 }
});
GameBoard(
{
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testAllZeros)
{
assertAllRotatedTransformTransitions(
{
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
private:
void assertAllRotatedTransformTransitions(
std::vector<std::vector<double>> initial,
std::string movement,
std::vector<std::vector<double>> final
)
{
for (int i = 0; i < 4; i++) {
assertBoardTransition(initial, movement, final);
initial = rotateClockwise(std::move(initial));
movement = clockwiseMovementTransform(std::move(movement));
final = rotateClockwise(std::move(final));
}
}
void assertBoardTransition(
const std::vector<std::vector<double>> &initial,
const std::string &movement,
const std::vector<std::vector<double>> &final
)
{
GameBoard board(initial);
for (const auto &c : movement)
switch (c)
{
case 'r':
case 'R':
board.moveRight();
break;
case 'd':
case 'D':
board.moveDown();
break;
case 'l':
case 'L':
board.moveLeft();
break;
case 'u':
case 'U':
board.moveUp();
break;
}
assertAreEqual(final, board.getBoard());
}
std::string clockwiseMovementTransform(std::string movement)
{
for (auto &c : movement)
switch (c)
{
case 'r':
case 'R':
c = 'd';
break;
case 'd':
case 'D':
c = 'l';
break;
case 'l':
case 'L':
c = 'u';
break;
case 'u':
case 'U':
c = 'r';
break;
}
return movement;
}
public:
TEST_METHOD(testOneTwo)
{
assertAllRotatedTransformTransitions(
{
{ 2, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 2, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 0, 2, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 0, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testTwoTwos)
{
assertAllRotatedTransformTransitions(
{
{ 2, 2, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 0, 2, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 0, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 2, 2, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 2, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 0, 2, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testThreeTwos)
{
assertAllRotatedTransformTransitions(
{
{ 2, 2, 2, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 2, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 0, 2, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 2, 2, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testFourTwos)
{
assertAllRotatedTransformTransitions(
{
{ 2, 2, 2, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 4, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testTwoUnequals)
{
assertAllRotatedTransformTransitions(
{
{ 2, 4, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 0, 4, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 0, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 2, 4, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 2, 0, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 2, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testThreeUnequals)
{
assertAllRotatedTransformTransitions(
{
{ 2, 4, 8, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 2, 4, 8 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 4, 0, 8 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 2, 4, 8 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 2, 0, 4, 8 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 2, 4, 8 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 2, 4, 8 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 2, 4, 8 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testFourUnequals)
{
assertAllRotatedTransformTransitions(
{
{ 2, 4, 8, 16 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 2, 4, 8, 16 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testCombinesOnlyOnce)
{
assertAllRotatedTransformTransitions(
{
{ 4, 2, 2, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 4, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 4, 2, 0, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 4, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 4, 0, 2, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 4, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
assertAllRotatedTransformTransitions(
{
{ 0, 4, 2, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"r",
{
{ 0, 0, 4, 4 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testTwiceAllZeros)
{
assertAllRotatedTransformTransitions(
{
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"rr",
{
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testThreeCombos)
{
assertAllRotatedTransformTransitions(
{
{ 8, 4, 2, 2 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
},
"rrr",
{
{ 0, 0, 0, 16 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
TEST_METHOD(testUnfortunateBoard)
{
assertAllRotatedTransformTransitions(
{
{ 2, 4, 2, 4 },
{ 4, 2, 4, 2 },
{ 2, 4, 2, 4 },
{ 4, 2, 4, 2 }
},
"rdlu",
{
{ 2, 4, 2, 4 },
{ 4, 2, 4, 2 },
{ 2, 4, 2, 4 },
{ 4, 2, 4, 2 }
});
}
TEST_METHOD(testVeryFortunateBoard)
{
assertAllRotatedTransformTransitions(
{
{ 2, 2, 2, 2 },
{ 2, 2, 2, 2 },
{ 2, 2, 2, 2 },
{ 2, 2, 2, 2 }
},
"rdlu",
{
{ 32, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
});
}
};
};
If interested the repository including tests can be found here
lang-cpp