-
Notifications
You must be signed in to change notification settings - Fork 0
/
day08.py
127 lines (98 loc) · 4.02 KB
/
day08.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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
from utils import ProblemSolver
class Node(object):
def __init__(self, name, numChildren, numMetaDatas, parent):
self.id = name
self.numMetaDatas = numMetaDatas
self.metaData = []
self.numChildren = numChildren
self.children = []
self.parent = parent
def getValue(self, nodes):
if not self.numChildren:
print('node ', self.id, 'has no children, returning metadata value', sum(self.metaData))
return sum(self.metaData)
else:
total = 0
print(self.metaData, self.children)
for childIndex in self.metaData:
if childIndex <= len(self.children):
childIndex -= 1
value = nodes[self.children[childIndex]].getValue(nodes)
print('child index, ', childIndex, 'childID', self.children[childIndex], 'value ', value)
total += value
else:
print('childIndex', childIndex, 'is out of bounds of our children')
return total
def needsMetadata(self):
return len(self.metaData) < self.numMetaDatas
def childrenDiscovered(self):
return len(self.children) == self.numChildren
def __repr__(self):
return 'Node({}, {}, {}, {})>{}'.format(self.id, self.numChildren, self.numMetaDatas, self.parent, self.metaData)
class Day08Solver(ProblemSolver):
def __init__(self):
super(Day08Solver, self).__init__(8)
self.testDataPartOne = {'2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2': 138}
self.testDataPartTwo = {'2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2': 66}
def ProcessInput(self, data=None):
"""
Parses the input tree string to determine each node's
children and metadata, ultimately building a flat list
:param data:
:return:
"""
if not data:
data = self.rawData
nodes = {}
isNewID = True
isMetaData = False
currentNode = 0
pointer = 0
ints = [int(j) for j in data.split()]
while pointer < len(ints):
if isNewID:
# current node is up one from the
parent = currentNode
currentNode = len(nodes.keys()) + 1 # our new node is now one-up from the length of the list, since it's just an identifier
numChildren = ints[pointer]
numMetaDatas = ints[pointer + 1]
nodes[currentNode] = Node(currentNode, numChildren, numMetaDatas, parent)
if parent:
nodes[parent].children.append(currentNode)
# move the pointer up two spots
pointer += 2
# if we've disocvered all our children, the current pointer index is probably metadata
if nodes[currentNode].childrenDiscovered():
isMetaData = True
isNewID = False
# if we haven't discovered all the children for the current node, the next pointer is going to be a new ID
else:
isNewID = True
isMetaData = False
# get all the metadata in one go
if isMetaData:
while nodes[currentNode].needsMetadata():
nodes[currentNode].metaData.append(ints[pointer])
pointer += 1
isMetaData = False
currentNode = nodes[currentNode].parent
return nodes
def SolvePartOne(self, data=None):
"""
Loop over all our nodes and return the sum of all the metadata
:param data:
:return:
"""
if not data:
data = self.processed
flattenedList = sum([data[n].metaData for n in data], [])
return sum(flattenedList)
def SolvePartTwo(self, data=None):
if not data:
data = self.processed
# for i in data:
# print(i, data[i].children)
return data[1].getValue(data)
if __name__ == '__main__':
day08 = Day08Solver()
day08.Run()