8
\$\begingroup\$

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 }
                });
        }
    };
};

The repository including tests can be found here.

\$\endgroup\$

3 Answers 3

Reset to default
4
\$\begingroup\$

One way to do this, is to have a Cell class. This way you make your board a vector<vector<Cell*>> You can have one collection that is organized by rows and one that is organized by columns. The overhead is minimal because they're stored as pointers.

Now one function can do all the moves just by passing the reference to the collection and an indication to use either the forward or reverse iterator of that collection.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for taking the time to answer. I think I understand your idea, and it sounds good. I am having difficulty imagining an implementation. Would you expand your answer with some code? \$\endgroup\$ Commented Sep 4, 2018 at 4:37
3
\$\begingroup\$

The best and most idiomatic way to articulate this is, in my opinion, a combination of iterators and algorithms: iterators to represent row / column traversal, and an algorithm to compute the next state for each row / column.

Iterators

As you know, iterators are used in C++ to represent a position in a range. They can be dereferenced, like a pointer, to access the element at the position they point to. If your board is implemented as an array or a vector, and that you provide two kinds of iterators, one horizontal and one vertical (the vertical one is increased by the number of cells in a row to get to the next position), you can then use a single algorithm to make the tiles fold as in the game.

Oh, and I forgot to tell you that once you have an iterator going one direction, there's a std::reverse_iterator to make it go the other way around.

Writing iterators isn't as trivial as one could think, if you want them perfect at least, but you can simplify the task by using Boost::Iterator_facade. There are also guides available; see for instance this SO question.

Algorithm

Once you have this done, a single algorithm will suffice. I've written a stub to give you a rough idea of how it could be done:

template <typename Iterator>
auto move_2048(Iterator first, Iterator last) {
    auto consider = std::stable_partition(first, last, [](const Cell& cell) {
        return is_empty(cell);
        });
    auto garbage = consider;
    // [first, garbage) are empty cells or trash
    // [consider, last) are candidates to folding
    while (true) {
        auto merge = std::adjacent_find(consider, last);
        if (merge == last) break;
        *std::next(merge) *= 2;
        std::rotate(garbage++, merge, std::next(merge));
        consider = std::next(merge, 2);
    }
    std::fill(first, garbage, empty_cell());
    return garbage;
}

I haven't tested it extensively but it seems ok. This algorithm is, IMO, correctly balanced between efficiency and readability. It returns the first non-empty cell after the move, so that you can compute the number of empty cells in that line/row: this by-product is a useful indication to compute the place where you'll insert the new tile.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your answer. I think it is well articulated and demonstrates the algorithm library well. However doesn't std::partition lose relative order? Would, for instance, the range {2, 2, 4, 0} possibly be partitioned to {0, 2, 4, 2} and thus miss the combination of 2 and 2? \$\endgroup\$ Commented Sep 6, 2018 at 3:38
  • \$\begingroup\$ @pls Yes, you're perfectly right, I should have used std::stable_partition. Let me edit my answer... \$\endgroup\$ Commented Sep 6, 2018 at 8:28
1
\$\begingroup\$

Drawing inspiration from tinstaafl I've implemented a single method (GameBoard::moveAlong) that incorporates the tile movement logic common to each direction in an effort to remove duplication.

#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()
{
    moveAlong(&GameBoard::toTheRight);
}

void GameBoard::moveLeft()
{
    moveAlong(&GameBoard::toTheLeft);
}

void GameBoard::moveDown()
{
    moveAlong(&GameBoard::downwards);
}

void GameBoard::moveUp()
{
    moveAlong(&GameBoard::upwards);
}

void GameBoard::moveAlong(double &(GameBoard::*direction)(size_t slice, size_t element))
{
    for (size_t slice = 0; slice < N; ++slice) {
        std::vector<bool> hasBeenCombined(N, false);
        for (size_t adjacentElement = N - 1; adjacentElement > 0; --adjacentElement)
        {
            const auto element = adjacentElement - 1;
            const auto value = (this->*direction)(slice, element);
            auto nextNonzeroOrLastElement = element;
            while (nextNonzeroOrLastElement < N - 1 && (this->*direction)(slice, ++nextNonzeroOrLastElement) == 0)
                ;
            if ((this->*direction)(slice, nextNonzeroOrLastElement) == 0)
                (this->*direction)(slice, N - 1) = value;
            else if (
                (this->*direction)(slice, nextNonzeroOrLastElement) == value &&
                !hasBeenCombined[nextNonzeroOrLastElement])
            {
                (this->*direction)(slice, nextNonzeroOrLastElement) += value;
                hasBeenCombined[nextNonzeroOrLastElement] = true;
            }
            else if (nextNonzeroOrLastElement != adjacentElement)
                (this->*direction)(slice, nextNonzeroOrLastElement - 1) = value;
            else
                continue;
            (this->*direction)(slice, element) = 0;
        }
    }
}

double & GameBoard::toTheRight(size_t slice, size_t element)
{
    return board[slice][element];
}

double & GameBoard::toTheLeft(size_t slice, size_t element)
{
    return board[slice][N - 1 - element];
}

double & GameBoard::upwards(size_t slice, size_t element)
{
    return board[N - 1 - element][slice];
}

double & GameBoard::downwards(size_t slice, size_t element)
{
    return board[element][slice];
}

This achieves my original intent of removing the duplication (at least some) between the "move" methods. However the passing of a non-static member function seems strange, but I found it useful in accessing the board. And I think the code would benefit from some of the standard algorithm library functions as demonstrated in papagaga's answer, but I am not well versed in these yet.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.