forked from y-tetsu/math_puzzle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
q70.py
70 lines (51 loc) · 1.76 KB
/
q70.py
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
#!/usr/bin/env python
"""
Q70
"""
W, H = 6, 4
GOAL = [
0b000000000000111111111111,
0b111111111111000000000000,
0b000111000111000111000111,
0b111000111000111000111000,
]
MEMO = {}
def check(patterns, depth):
next_patterns = []
for ptn in patterns:
if ptn not in MEMO:
MEMO[ptn] = depth
# 横入替
for h in range(H):
for w in range(W - 1):
mask_bit1 = 0b1 << (h * W) + w
mask_bit2 = 0b1 << (h * W) + w + 1
mask_clear = ~(mask_bit1 | mask_bit2)
bit1_value = (ptn & mask_bit1) << 1
bit2_value = (ptn & mask_bit2) >> 1
next_ptn = (ptn & mask_clear) | bit1_value | bit2_value
if next_ptn not in MEMO:
next_patterns.append(next_ptn)
# 縦入替
for w in range(W):
for h in range(H - 1):
mask_bit1 = 0b1 << (h * W) + w
mask_bit2 = 0b1 << ((h + 1) * W) + w
mask_clear = ~(mask_bit1 | mask_bit2)
bit1_value = (ptn & mask_bit1) << W
bit2_value = (ptn & mask_bit2) >> W
next_ptn = (ptn & mask_clear) | bit1_value | bit2_value
if next_ptn not in MEMO:
next_patterns.append(next_ptn)
return next_patterns
if __name__ == '__main__':
next_patterns = GOAL
depth = 0
while True:
if next_patterns:
next_patterns = check(next_patterns, depth)
depth += 1
else:
break
print("ptn = ", sum([1 for value in MEMO.values() if value == depth - 1]))
print("max move =", depth - 1)