Advent of Code 2020 day 23 . Ooh I liked this one because it taught me something new: linked lists!
I took the “obvious” approach for part one, but almost nothing of that version is shown below as I first re-factored it, then stuck part_two_answer
on top of it.
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
77
78
79
80
import unittest
class Game ():
def __init__ ( self , starting_circle , part = 1 ):
starting_circle = [ int ( char ) for char in starting_circle ]
self . max_cup = max ( starting_circle )
self . min_cup = min ( starting_circle )
if part == 2 :
starting_circle += [ i for i in range ( self . max_cup + 1 , 1 _000_000 + 1 )]
self . max_cup = 1 _000_000
self . circle = {
cup : starting_circle [( i + 1 ) % len ( starting_circle )]
for i , cup in enumerate ( starting_circle )
}
self . length = len ( self . circle )
self . current_cup = starting_circle [ 0 ]
def move ( self ):
crab = [
self . circle [ self . current_cup ],
self . circle [ self . circle [ self . current_cup ]],
self . circle [ self . circle [ self . circle [ self . current_cup ]]]
]
destination = self . current_cup - 1
if destination < self . min_cup :
destination = self . max_cup
while destination in crab :
destination -= 1
if destination < self . min_cup :
destination = self . max_cup
destination_original_link = self . circle [ destination ]
chain_end_original_link = self . circle [ crab [ - 1 ]]
self . circle [ destination ] = crab [ 0 ]
self . circle [ crab [ - 1 ]] = destination_original_link
self . circle [ self . current_cup ] = chain_end_original_link
self . current_cup = chain_end_original_link
def part_one_answer ( self ):
cup = 1
result = ""
for i in range ( self . length - 1 ):
result += str ( self . circle [ cup ])
cup = self . circle [ cup ]
return result
def part_two_answer ( self ):
return self . circle [ 1 ] * self . circle [ self . circle [ 1 ]]
def part_one ( input ):
game = Game ( input )
for _ in range ( 100 ):
game . move ()
return game . part_one_answer ()
def part_two ( input ):
game = Game ( input , 2 )
for _ in range ( 10 _000_000 ):
game . move ()
return game . part_two_answer ()
class TestPartOne ( unittest . TestCase ):
def test_part_one_example ( self ):
self . assertEqual ( part_one ( "389125467" ), '67384529' )
class TestPartTwo ( unittest . TestCase ):
def test_part_two_example ( self ):
self . assertEqual ( part_two ( "389125467" ), 149245887792 )
if __name__ == '__main__' :
print ( f "Part one: {part_one(INPUT)}" )
print ( f "Part two: {part_two(INPUT)}" )