/
day09.py
106 lines (82 loc) · 2.63 KB
/
day09.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
from timeit import default_timer as timer
from dataclasses import dataclass
class CircularList:
@dataclass
class Node:
value: int
left: object
right: object
def __init__(self):
self.currNode = None
def currValue(self):
if self.currNode is None:
return None
else:
return self.currNode.value
def seek(self, amount):
if self.currNode is None:
return self
for _ in range(abs(amount)):
if amount < 0:
self.currNode = self.currNode.left
else:
self.currNode = self.currNode.right
return self
def pop(self):
if self.currNode is None:
return None
elif self.currNode.left is self.currNode.right:
val = self.currNode.value
self.currNode = None
return val
else:
self.currNode.left.right = self.currNode.right
self.currNode.right.left = self.currNode.left
val = self.currNode.value
self.currNode = self.currNode.right
return val
def insert(self, value):
if self.currNode is None:
self.currNode = self.Node(value, None, None)
self.currNode.left = self.currNode
self.currNode.right = self.currNode
else:
newNode = self.Node(
value, self.currNode, self.currNode.right)
self.currNode.right.left = newNode
self.currNode.right = newNode
self.currNode = newNode
def tolist(self):
if self.currNode is None:
return []
else:
res = []
nextNode = self.currNode
while True:
res.append(nextNode.value)
nextNode = nextNode.right
if nextNode == self.currNode:
return res
def __str__(self):
return str(self.tolist())
def playgames(numberOfElves, biggestMarble):
marbleCircle = CircularList()
marbleCircle.insert(0)
elves = [0] * numberOfElves
elveIdx = 0
for marbleValue in range(1, biggestMarble+1):
if marbleValue % 23 == 0:
elves[elveIdx] += marbleValue
elves[elveIdx] += marbleCircle.seek(-7).pop()
else:
marbleCircle.seek(1).insert(marbleValue)
elveIdx = (elveIdx + 1) % numberOfElves
return elves
start = timer()
print("Solution 1", max(playgames(468, 71010)))
end = timer()
print(" Time: ", end - start)
start = timer()
print("Solution 2", max(playgames(468, 71010*100)))
end = timer()
print(" Time: ", end - start)