In [1]:
1
2
3
4
5
6
7
8
9
import sys
sys.path.append("/home/swyoo/algorithm/")
from sys import stdin
from utils.generator import random2D, array2DtoStr
from utils.verbose import logging_time
from collections import deque
from typing import Tuple, List
from copy import deepcopy
import numpy as np
2048 Game
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
Idea
- STEP1: 주어진 조건에 맞게 블록을 이동하는 코드를 구현(deque 사용하면 쉽게 가능)
- STEP2: DFS를 사용하여 가능한 경우를 call해보고
ans를 찾는다.
In [2]:
1
2
3
4
5
6
plot = lambda x: print(np.array(x))
stdin = open('data/2048.txt')
input = stdin.readline
n = int(input())
grid = [list(map(int, input().strip().split(' '))) for _ in range(n)]
plot(grid)
1
2
3
4
5
[[4 8 8 2]
[4 0 2 0]
[0 0 0 0]
[0 0 0 0]]
STEP1: move를 구현하라
STEP1-1: 1D move 구현
In [3]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)
m, n = len(grid), len(grid[0])
def start(i, j, dx, dy) -> Tuple[int, int]:
""" determine a start point by given axis and direction.
Note that this function ignores i or j by the given direction.
:param:
:(i, j): selected axis.
:(dx, dy): selected direction
:returns (0, j) if direction in [up, down] else (i, 0) """
if (dx, dy) == up:
return 0, j
elif (dx, dy) == down:
return m - 1, j
elif (dx, dy) == left:
return i, 0
elif (dx, dy) == right:
return i, n - 1
def move1D(grid, x, y, dx, dy):
""" move 1 dimention by (dx, dy).
:param:
:x, y: start points. """
Q = deque()
i, j = x, y
while 0 <= i < m and 0 <= j < n:
if grid[i][j]:
Q.append(grid[i][j])
grid[i][j] = 0
i, j = i - dx, j - dy
while Q:
e = Q.popleft()
if not grid[x][y]:
grid[x][y] = e
elif grid[x][y] == e:
grid[x][y] *= 2
x, y = x - dx, y - dy
else:
x, y = x - dx, y - dy
grid[x][y] = e
return grid
In [4]:
1
2
3
4
n = 5
grid = random2D(shape=(n, n), sampling=[0, 2, 4, 8, 16], weights=[0.6, 0.1, 0.1, 0.1, 0.1])
m, n = len(grid), len(grid[0])
plot(grid)
1
2
3
4
5
6
[[ 0 0 0 8 8]
[ 0 4 0 2 0]
[ 4 0 0 16 4]
[16 0 0 0 8]
[ 0 0 0 0 0]]
In [5]:
1
2
3
4
5
# go: select row or column
# select column 2 and up.
go, direction = (0, 2), up
grid = move1D(grid, *start(*go, *direction), *direction)
plot(grid)
1
2
3
4
5
6
[[ 0 0 0 8 8]
[ 0 4 0 2 0]
[ 4 0 0 16 4]
[16 0 0 0 8]
[ 0 0 0 0 0]]
In [6]:
1
2
3
4
# select row 0 and right.
go, direction = (0, 0), right
grid = move1D(grid, *start(*go, *direction), *direction)
plot(grid)
1
2
3
4
5
6
[[ 0 0 0 0 16]
[ 0 4 0 2 0]
[ 4 0 0 16 4]
[16 0 0 0 8]
[ 0 0 0 0 0]]
In [7]:
1
2
3
4
# select row 1 and right.
go, direction = (1, 0), right
grid = move1D(grid, *start(*go, *direction), *direction)
plot(grid)
1
2
3
4
5
6
[[ 0 0 0 0 16]
[ 0 0 0 4 2]
[ 4 0 0 16 4]
[16 0 0 0 8]
[ 0 0 0 0 0]]
STEP1-2: 2D move 구현
단순히 주어진 조건에 맞게 2D에서 동작하도록 한다.
In [8]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)
m, n = len(grid), len(grid[0])
def move(grid: List[List[int]], direction: Tuple[int, int]) -> List[List[int]]:
""" Given a grid, move the elements in the grid by direction.
:returns changed grid. """
grid = deepcopy(grid)
def start(i, j, dx, dy) -> Tuple[int, int]:
if (dx, dy) == up:
return 0, j
elif (dx, dy) == down:
return m - 1, j
elif (dx, dy) == left:
return i, 0
elif (dx, dy) == right:
return i, n - 1
def move1D(x, y, dx, dy):
""" move 1 dimention by (dx, dy).
:param:
:x, y: start points. """
Q = deque()
i, j = x, y
while 0 <= i < m and 0 <= j < n:
if grid[i][j]:
Q.append(grid[i][j])
grid[i][j] = 0
i, j = i - dx, j - dy
while Q:
e = Q.popleft()
if not grid[x][y]:
grid[x][y] = e
elif grid[x][y] == e:
grid[x][y] *= 2
x, y = x - dx, y - dy
else:
x, y = x - dx, y - dy
grid[x][y] = e
k = m if direction in [up, down] else n
for i in range(k):
go = (0, i) if direction in [up, down] else (i, 0)
move1D(*start(*go, *direction), *direction)
return grid
In [9]:
1
2
3
4
5
n = 5
grid = random2D(shape=(n, n), sampling=[0, 2, 4, 8, 16], weights=[0.6, 0.1, 0.1, 0.1, 0.1])
m, n = len(grid), len(grid[0])
plot(grid)
move(grid, left)
1
2
3
4
5
6
[[ 0 16 8 4 0]
[ 8 0 0 0 0]
[ 0 0 8 8 0]
[ 2 0 0 8 0]
[16 0 0 0 0]]
1
2
3
4
5
[[16, 8, 4, 0, 0],
[8, 0, 0, 0, 0],
[16, 0, 0, 0, 0],
[2, 8, 0, 0, 0],
[16, 0, 0, 0, 0]]
STEP2: DFS
In [10]:
1
2
3
4
5
6
7
8
9
10
11
12
@logging_time
def solution(grid):
ans = 0
def dfs(grid, cnt=0):
nonlocal ans
if cnt > 5: return
ans = max(ans, max(list(map(max, grid))))
for direction in [up, down, left, right]:
dfs(move(grid, direction), cnt + 1)
dfs(grid)
return ans
In [11]:
1
2
3
4
5
n = 9
grid = random2D(shape=(n, n), sampling=[0, 2, 4, 8, 16], weights=[0.6, 0.1, 0.1, 0.1, 0.1])
m, n = len(grid), len(grid[0])
plot(grid)
print(solution(grid, verbose=True))
1
2
3
4
5
6
7
8
9
10
11
12
[[ 0 4 0 0 0 16 0 8 0]
[ 0 0 0 16 0 0 0 0 0]
[ 4 16 4 16 16 0 0 4 2]
[ 0 0 2 16 0 16 2 0 0]
[ 0 0 8 0 0 2 0 0 0]
[ 0 0 0 16 0 0 0 0 0]
[ 0 0 4 0 0 8 2 16 0]
[ 8 2 0 0 0 0 8 2 4]
[ 8 0 8 2 0 4 4 0 4]]
WorkingTime[solution]: 377.78997 ms
64
Time Complexity
시간 복잡도는 다음과 같다.
이동할 수 있는 최대 수를 $k$, 주어진 grid의 shape 를 $m, n$ 이라 하자.
- move: $O(n^2)$
- directions: $4$가지
따라서, $O(mn 4^k)$, where $k<=5$
Summited Code
In [12]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import sys
from sys import stdin
from collections import deque
from typing import Tuple, List
from copy import deepcopy
# import numpy as np
# plot = lambda x: print(np.array(x))
stdin = open('data/2048.txt') # 제출 시 주석 제거
input = stdin.readline
n = int(input())
grid = [list(map(int, input().strip().split(' '))) for _ in range(n)]
# plot(grid)
up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)
m, n = len(grid), len(grid[0])
def move(grid: List[List[int]], direction: Tuple[int, int]) -> List[List[int]]:
""" Given a grid, move the elements in the grid by direction.
:returns changed grid. """
grid = deepcopy(grid)
def start(i, j, dx, dy) -> Tuple[int, int]:
if (dx, dy) == up:
return 0, j
elif (dx, dy) == down:
return m - 1, j
elif (dx, dy) == left:
return i, 0
elif (dx, dy) == right:
return i, n - 1
def move1D(x, y, dx, dy):
""" move 1 dimention by (dx, dy).
:param:
:x, y: start points. """
Q = deque()
i, j = x, y
while 0 <= i < m and 0 <= j < n:
if grid[i][j]:
Q.append(grid[i][j])
grid[i][j] = 0
i, j = i - dx, j - dy
while Q:
e = Q.popleft()
if not grid[x][y]:
grid[x][y] = e
elif grid[x][y] == e:
grid[x][y] *= 2
x, y = x - dx, y - dy
else:
x, y = x - dx, y - dy
grid[x][y] = e
k = m if direction in [up, down] else n
for i in range(k):
go = (0, i) if direction in [up, down] else (i, 0)
move1D(*start(*go, *direction), *direction)
return grid
def solution(grid):
ans = 0
def dfs(grid, cnt=0):
nonlocal ans
if cnt > 5: return
ans = max(ans, max(list(map(max, grid))))
for direction in [up, down, left, right]:
dfs(move(grid, direction), cnt + 1)
dfs(grid)
return ans
print(solution(grid))
1
2
16
Reference
[1] Problem 2048 baekjoon
[2] Refered code
Report
기울이는 문제는 모두 지운다음, 있어야할 위치부터 차례대로 채워넣는 방식이
그나마 구현하기 쉬운 것 같다.
주요내용을 정리하면 다음과 같다.
- move를 deque를 사용하여 구현하는게 복잡하였다.
- DFS구현은 간단하였다.
Leave a comment