[Baekjoon] 2048 (Easy)

Problem

It’s the 2048 game we all know. But with added constraints:

A block that has already merged in one move can’t merge again
If 3 or more blocks could merge, merge starting from the ones closest to the direction of movement
- e.g., If moving upward, merge from the top first

Solution

The merging idea itself is easy to come up with. If empty, move the value; if values are equal, double them; otherwise, place it in the cell above.

The part that was hard to understand even after reading others’ explanations was how to prevent already-merged blocks from merging again. I expected some kind of flag, but instead the approach keeps incrementing the row or column index for the merge target.

The second challenge was handling the four directions. This requires a solid understanding of which to process first between rows and columns.

For example, when moving left or right, you iterate by column and move one row at a time. For up or down, you iterate by row and move one column at a time.

1
if direction == 0:
2
        # Look at all columns of arr, so iterate n times
3
        for j in range(n):
4
            idx = 0
5
            # Need to look at all rows except the 0th
6
            for i in range(1, n):
7
                # If the element is not 0 == not empty
8
                if arr[i][j]:
9
                    # Store what we're going to move
10
                    temp = arr[i][j]
11
                    # Clear the original position
12
                    arr[i][j] = 0
13
                    # If the destination is 0
14
                    if arr[idx][j] == 0:
15
                        # It's empty, so just move it
16
                        arr[idx][j] = temp
17
                    # If what we're moving equals the destination
18
                    elif arr[idx][j] == temp:
19
                        # Merge
20
                        arr[idx][j] = temp * 2
21
                        # Increment idx so it can't merge again
22
                        idx += 1
23
                    # If what we're moving differs from the destination
24
                    else:
25
                        idx += 1 # Block it
26
                        arr[idx][j] = temp # Restore

[0, 3] are mapped to up, down, left, right in order. direction = 0 means the code above moves blocks upward.

Moving up is straightforward. Left and right are trickier. Here’s left:

1
elif direction == 2:
2
        for i in range(n):
3
            idx = 0
4
            for j in range(1, n):
5
                if arr[i][j]:
6
                    # Store what we're going to move
7
                    temp = arr[i][j]
8
                    # Clear the original position
9
                    arr[i][j] = 0
10
                    # If the destination is 0
11
                    if arr[i][idx] == 0:
12
                        # It's empty, so just move it
13
                        arr[i][idx] = temp
14
                    # If what we're moving equals the destination
15
                    elif arr[i][idx] == temp:
16
                        # Merge
17
                        arr[i][idx] = temp * 2
18
                        # Increment idx so it can't merge again
19
                        idx += 1
20
                    # If what we're moving differs from the destination
21
                    else:
22
                        idx += 1 # Block it
23
                        arr[i][idx] = temp # Restore

I always use i for the row variable and j for the column variable. For the left-movement task, you need to iterate by column and move one row at a time. So the loop order must be swapped to iterate i, then j.

The rest follows the same pattern as moving upward.

For moving down, reverse the range for i; for moving right, reverse the range for j. That is, iterate from n-2 down to 1.

Code

https://github.com/naem1023/codingTest/blob/master/implementation/acmipic-12100.py