Day 3, Year 2021: Binary Diagnostic
First read the problem description.
def count(f):
= {}
sums = 0
lines for l in f:
for p, ch in enumerate(l.rstrip()):
= sums.get(p, 0) + int(ch)
sums[p] += 1
lines
return sums, lines
def rates(f):
= count(f)
sums, lines = len(sums)
digits = 0
gamma = 0
epsilon for p, s in sums.items():
if s > lines/2:
|= 1<<(digits-p-1)
gamma else:
|= 1<<(digits-p-1)
epsilon
return gamma, epsilon
import import_ipynb
import helper
= helper.open_file('2021_3.txt')
f
= rates(f)
gamma, epsilon
print(gamma*epsilon)
4147524
class Node:
def __init__(self):
self.children = [None, None]
def insert(node, bitstring):
for bit in bitstring:
= int(bit)
bit if node.children[bit] is None:
= Node()
node.children[bit] = node.children[bit]
node
def count_leafs(node):
if node is None:
return 0
= 0
c
= True
leaf for n in node.children:
if n:
+= count_leafs(n)
c = False
leaf
if leaf:
+= 1
c
return c
import import_ipynb
import helper
= helper.open_file('2021_3.txt')
f
= Node()
root
for l in f:
insert(root, l.rstrip())
def rating(node, bit_criteria):
= 0
r while node:
= count_leafs(node.children[0])
c0 = count_leafs(node.children[1])
c1
if c0 == 0 and c1 == 0:
break
<<= 1
r if not (c0 == 0 and c1 == 1) and \
or (c0 == 1 and c1 == 0)):
(bit_criteria(c0, c1)
= node.children[0]
node else:
= node.children[1]
node |= 1
r
return r
import operator
= rating(root, operator.gt)
oxygen_generator_rate = rating(root, operator.le)
c02_scrubber_rate
* c02_scrubber_rate oxygen_generator_rate
3570354
Source code of the solution(s):