โปรแกรมหาตำแหน่งบอร์ด 2048 ถัดไปหลังสไลด์ในทิศทางที่กำหนด Python

ปัญหา

กำหนดบอร์ดเกม 2048 (4x4 matrix) และทิศทางสไลด์ ("U", "D", "L", "R") ต้องการหาสถานะบอร์ดถัดไป กฎ: ตัวเลขเคลื่อนที่ไปจนสุดในทิศทางนั้น และตัวเลขติดกันที่เหมือนกันจะรวมกัน (บวก) เพียงครั้งเดียวต่อการสไลด์

ตัวอย่าง: สไลด์ "L" (ซ้าย)

Input: [[2,0,0,2], [2,2,2,2], [0,4,2,2], [2,2,2,0]]

Output: [[4,0,0,0], [4,4,0,0], [4,4,0,0], [4,2,0,0]]

อัลกอริทึม

1. หมุนบอร์ดให้ทิศทางสไลด์กลายเป็น "L" (ซ้าย) เสมอ:
   • "R": หมุน 180° (anti-clockwise 2 ครั้ง)
   • "U": หมุน 90° (anti-clockwise 1 ครั้ง)
   • "D": หมุน 270° (anti-clockwise 3 ครั้ง)
2. ประมวลผลแต่ละแถว (ตอนนี้ทุกแถวคือสไลด์ซ้าย):
   • เก็บเฉพาะค่าที่ไม่เป็น 0 → list row
   • วนเช็คค่าติดกัน: ถ้า row[j] == row[j+1] → คูณ 2, ลบตัวถัดไป
   • เติม 0 ท้าย list ให้ครบ 4 ค่า
3. หมุนบอร์ดกลับทิศทางเดิม (inverse rotation)
4. คืนค่าบอร์ดผลลัพธ์

การนำไปใช้ Python

class Solution:
    def solve(self, board, direction):
        # Rotate board so swipe direction becomes Left
        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)))
        
        # Process each row (swipe left)
        for i in range(4):
            row = [x for x in board[i] if x]  # non-zero only
            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.append(0)
            board[i] = row
        
        # Rotate back to original orientation
        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):
    """Rotate 4x4 matrix 90 degrees anti-clockwise"""
    x = [[x[i][j] for i in range(4)] for j in range(4)]
    return x[::-1]

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

ผลลัพธ์

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

จุดสำคัญ

• ลดปัญหา 4 ทิศทางเหลือแค่ 1 ทิศทาง (Left) ด้วยการหมุนเมทริกซ์
• การรวมตัวเลข (merge) เกิดขึ้นได้เพียงครั้งเดียวต่อคู่ต่อการสไลด์หนึ่งครั้ง
• ใช้ del row[j+1] ลบองค์ประกอบที่รวมแล้ว แล้ว pad 0 ท้าย