58 lines
1.9 KiB
Python
58 lines
1.9 KiB
Python
|
import bisect
|
||
|
|
input = open("input", 'r')
|
||
|
|
|
||
|
|
splitters = None
|
||
|
|
start = None
|
||
|
|
for row, line in enumerate(input):
|
||
|
|
if splitters == None:
|
||
|
|
splitters = [[] for _ in range(len(line))]
|
||
|
|
for col, char in enumerate(line):
|
||
|
|
if char == "S":
|
||
|
|
start = (row, col)
|
||
|
|
elif char == "^":
|
||
|
|
splitters[col].append(row)
|
||
|
|
|
||
|
|
def beam_to_splitter(splitters, beam):
|
||
|
|
beam_row, beam_col = beam
|
||
|
|
splitters_in_col = splitters[beam_col]
|
||
|
|
next_splitter = bisect.bisect_right(splitters_in_col, beam_row)
|
||
|
|
if next_splitter == len(splitters_in_col):
|
||
|
|
return None
|
||
|
|
return (splitters_in_col[next_splitter], beam_col)
|
||
|
|
|
||
|
|
def part1(splitters, start):
|
||
|
|
used_splitters = set()
|
||
|
|
unresolved_splitters = [beam_to_splitter(splitters,start)]
|
||
|
|
while unresolved_splitters:
|
||
|
|
splitter = unresolved_splitters.pop()
|
||
|
|
used_splitters.add(splitter)
|
||
|
|
|
||
|
|
splitter_row, splitter_col = splitter
|
||
|
|
for offset in [-1, 1]:
|
||
|
|
new_beam = (splitter_row, splitter_col+offset)
|
||
|
|
next_splitter = beam_to_splitter(splitters, new_beam)
|
||
|
|
if not next_splitter or next_splitter in used_splitters:
|
||
|
|
continue
|
||
|
|
unresolved_splitters.append(next_splitter)
|
||
|
|
|
||
|
|
return len(used_splitters)
|
||
|
|
|
||
|
|
def part2(splitters, start):
|
||
|
|
splitter_multiverses = {}
|
||
|
|
def multiverse_count(splitters, splitter):
|
||
|
|
if splitter == None:
|
||
|
|
return 1
|
||
|
|
if splitter not in splitter_multiverses:
|
||
|
|
splitter_multiverses[splitter] = 0
|
||
|
|
splitter_row, splitter_col = splitter
|
||
|
|
for offset in [-1, 1]:
|
||
|
|
new_beam = (splitter_row, splitter_col+offset)
|
||
|
|
next_splitter = beam_to_splitter(splitters, new_beam)
|
||
|
|
splitter_multiverses[splitter] += multiverse_count(splitters, next_splitter)
|
||
|
|
return splitter_multiverses[splitter]
|
||
|
|
|
||
|
|
return multiverse_count(splitters, start)
|
||
|
|
|
||
|
|
print(part1(splitters, start))
|
||
|
|
print(part2(splitters, start))
|