Pythonで2048ゲームの指定方向スライド後の盤面を求める方法

問題の概要

2048ゲームの盤面(初期状態)と、スワイプ方向を表す文字列が与えられたとき、その方向に1回スライドした後の盤面の状態を求めるプログラムを作成します。

2048ゲームでは、4×4のマスに数字が配置されたボードを使用します(空きマスは0で表現されます)。プレイヤーは「U(上)」「D(下)」「L(左)」「R(右)」の4方向のいずれかへスワイプできます。スワイプを行うと、すべての数字はその方向へできるだけ遠くまで移動し、隣り合う同じ数値はちょうど1回だけ合算されます。

たとえば、次のような盤面が与えられたとします。

matrix = [
[2, 0, 0, 2],
[2, 2, 2, 2],
[0, 4, 2, 2],
[2, 2, 2, 0]]

direction = "L"(左スワイプ)の場合、出力は次のようになります。

[
[4, 0, 0, 0],
[4, 4, 0, 0],
[4, 4, 0, 0],
[4, 2, 0, 0]]

解法の考え方

この問題は、以下の手順で解くことができます。

• directionが「R」の場合
  → boardを反時計回りに2回回転する
• directionが「U」の場合
  → boardを反時計回りに1回回転する
• directionが「D」の場合
  → boardを反時計回りに3回回転する
• i を 0〜3 の範囲で繰り返し処理する
  • row := board[i] 内の非ゼロ要素のみを抽出したリストを作る
  • j を 0〜2 の範囲で繰り返し処理する
    • j + 1 < len(row) かつ row[j] == row[j + 1] の場合
      • row[j] := row[j] * 2(合算する)
      • row[j + 1] を削除する
  • len(row) < 4 の間、row の末尾に 0 を挿入する
  • board[i] := row とする
• directionが「R」の場合
  → boardを反時計回りに2回回転して元の向きへ戻す
• directionが「U」の場合
  → boardを反時計回りに3回回転して元の向きへ戻す
• directionが「D」の場合
  → boardを反時計回りに1回回転して元の向きへ戻す
• board を返す

このアプローチのポイントは、「左へのスライド」処理だけを実装すればよいという点です。他の方向については、あらかじめボードを回転させて左スライドの向きに揃えてから処理し、最後に元の向きへ戻すことで統一的に扱えます。

実装例

理解を深めるために、実際の実装を見てみましょう。

class Solution:
    def solve(self, board, direction):
        if direction == "R":
            board = rot_anti_clock_dir(rot_anti_clock_dir(board))
        elif direction == "U":
            board = rot_anti_clock_dir(board)
        elif direction == "D":
            board = rot_anti_clock_dir(rot_anti_clock_dir(rot_anti_clock_dir(board)))

        for i in range(4):
            row = [x for x in board[i] if x]
            for j in range(3):
                if j + 1 < len(row) and row[j] == row[j + 1]:
                    row[j] *= 2
                    del row[j + 1]
                while len(row) < 4:
                    row += [0]
            board[i] = row

        if direction == "R":
            board = rot_anti_clock_dir(rot_anti_clock_dir(board))
        elif direction == "U":
            board = rot_anti_clock_dir(rot_anti_clock_dir(rot_anti_clock_dir(board)))
        elif direction == "D":
            board = rot_anti_clock_dir(board)
        return board


def rot_anti_clock_dir(x):
    x = [[x[i][j] for i in range(4)] for j in range(4)]
    return x[::-1]

ob = Solution()
matrix = [
[2, 0, 0, 2],
[2, 2, 2, 2],
[0, 4, 2, 2],
[2, 2, 2, 0]]
print(ob.solve(matrix, "L"))

入力

matrix = [
[2, 0, 0, 2],
[2, 2, 2, 2],
[0, 4, 2, 2],
[2, 2, 2, 0]]

出力

[
[4, 0, 0, 0],
[4, 4, 0, 0],
[4, 4, 0, 0],
[4, 2, 0, 0]]

補足：回転関数の仕組み

ヘルパー関数 rot_anti_clock_dir() は、行列を転置したうえで行の順序を逆転させることで、反時計回り90度の回転を実現しています。このテクニックにより、上下左右どの方向のスワイプも「左スライド」のロジック1つに集約できるのが、この実装の大きな特徴です。各処理の計算量はボードサイズが固定(4×4)であるため、常に一定時間で完了します。