|
1 | 1 |
|
2 | | -# for is_part1 in [True, False]: |
3 | | -for is_part1 in [True, False]: |
4 | | - # n = [int(i) for i in "476138259"] |
5 | | - n = [int(i) for i in "389125467"] |
| 2 | +class Node: |
| 3 | + def __init__(self, n, pred, succ): |
| 4 | + self.n = n |
| 5 | + self.pred = pred |
| 6 | + self.succ = succ |
6 | 7 |
|
7 | | - if not is_part1: |
8 | | - n += list(range(10, 1_000_001)) |
| 8 | +def to_linked_list(l): |
| 9 | + prev = Node(l[0], None, None) |
| 10 | + f = prev |
| 11 | + for e in l[1:]: |
| 12 | + n = Node(e, prev, None) |
| 13 | + prev.succ = n |
| 14 | + prev = n |
| 15 | + n.succ = f |
| 16 | + f.pred = n |
| 17 | + return f |
| 18 | + |
| 19 | +def to_dict(curr): |
| 20 | + d = {} |
| 21 | + n = curr.n |
| 22 | + d[n] = curr |
| 23 | + while True: |
| 24 | + curr = curr.succ |
| 25 | + if curr.n == n: break |
| 26 | + d[curr.n] = curr |
| 27 | + return d |
| 28 | + |
| 29 | +def to_list(curr): |
| 30 | + first = curr.n |
| 31 | + res = [first] |
| 32 | + while True: |
| 33 | + curr = curr.succ |
| 34 | + if curr.n == first: break |
| 35 | + res.append(curr.n) |
| 36 | + return res |
| 37 | + |
| 38 | +def make_move(curr, d, l): |
| 39 | + act = curr |
| 40 | + f1 = curr.succ |
| 41 | + f2 = f1.succ |
| 42 | + f3 = f2.succ |
| 43 | + |
| 44 | + curr.succ = f3.succ |
| 45 | + f3.pred = curr |
| 46 | + |
| 47 | + n = curr.n |
| 48 | + while True: |
| 49 | + n -= 1 |
| 50 | + if n == 0: |
| 51 | + n = l |
| 52 | + if n not in [f1.n, f2.n, f3.n]: |
| 53 | + break |
| 54 | + |
| 55 | + curr = d[n] |
9 | 56 |
|
10 | | - if is_part1: |
| 57 | + k = curr.succ |
| 58 | + curr.succ = f1 |
| 59 | + f1.pred = curr |
| 60 | + f3.succ = k |
| 61 | + k.pred = f3 |
| 62 | + return act.succ |
| 63 | + |
| 64 | +for is_part1 in [True, False]: |
| 65 | + n = [int(i) for i in "476138259"] |
| 66 | + |
| 67 | + if is_part1: |
11 | 68 | n_moves = 100 |
12 | 69 | else: |
| 70 | + n += list(range(10, 1_000_001)) |
13 | 71 | n_moves = 10_000_000 |
14 | 72 |
|
15 | 73 | l = len(n) |
16 | | - idx = 0 |
| 74 | + n = to_linked_list(n) |
| 75 | + d = to_dict(n) |
| 76 | + |
17 | 77 | for move in range(n_moves): |
18 | | - if move % 100 == 0: |
19 | | - print(move, end=" ", flush=True) |
20 | | - |
21 | | - curr = n[idx] |
22 | | - i = (idx + 1) % l |
23 | | - sel = [] |
24 | | - for _ in range(3): |
25 | | - sel.append(n[i]) |
26 | | - i = (i + 1) % l |
27 | | - |
28 | | - for e in sel: |
29 | | - n.remove(e) |
30 | | - |
31 | | - dest = curr |
32 | | - while True: |
33 | | - dest -= 1 |
34 | | - if dest == 0: |
35 | | - dest = l |
36 | | - if dest not in sel: |
37 | | - break |
38 | | - |
39 | | - pos = n.index(dest) + 1 |
40 | | - n = n[:pos] + sel + n[pos:] |
41 | | - idx = (n.index(curr) + 1) % l |
42 | | - |
43 | | - print() |
44 | | - oneidx = n.index(1) |
| 78 | + n = make_move(n, d, l) |
| 79 | + |
| 80 | + k = to_list(d[1]) |
45 | 81 | if is_part1: |
46 | | - print("".join([str(c) for c in n[oneidx+1:]+n[:oneidx]])) |
| 82 | + print("".join(str(c) for c in k[1:])) |
47 | 83 | else: |
48 | | - print(n[oneidx+1]*n[oneidx+2]) |
| 84 | + print(k[1]*k[2]) |
0 commit comments