Python
Made a single cleaned-up solver for all 3 parts after solving them separately. Intersection logic can be optimized, but the inputs are small enough to not need it.
click to view code
# simple type to represent an arc
Arc = tuple[int, int]
# single solver for all 3 parts
class Solver:
def __init__(self, forward_skips_visited = False, forbid_crossings = False):
# a forward jump landing on a visited point slides right to the first free point (part 2)
self.forward_skips_visited = forward_skips_visited
# arcs may not cross, and a jump with no valid landing is skipped entirely (part 3)
self.forbid_crossings = forbid_crossings
# current position on the line
self.pos = 0
# set of visited points on the line
self.visited = {0}
# which side the arc will be drawn on next (down = 0, up = 1)
self.side = 0
# arc segments on each side of the line
self.arcs: dict[int, list[Arc]] = { 0: [], 1: [] }
# get the first arc / segment that crosses the given range
def _get_crossing(self, start: int, end: int) -> Arc | None:
low, high = min(start, end), max(start, end)
for a, b in self.arcs[self.side]:
if a < low < b < high or low < a < high < b:
return a, b
return None
# try moving backwards by the given length, return None if not possible
def _move_backward(self, length: int) -> int | None:
next_pos = self.pos - length
if next_pos < 0 or next_pos in self.visited:
return None
if self.forbid_crossings and self._get_crossing(next_pos, self.pos) is not None:
return None
return next_pos
# try moving forwards by the given length, return None if not possible
def _move_forward(self, length: int) -> int | None:
next_pos = self.pos + length
while True:
# keep moving forward until an unvisited point is found
if self.forward_skips_visited and next_pos in self.visited:
next_pos += 1
continue
if not self.forbid_crossings:
return next_pos
crossing = self._get_crossing(self.pos, next_pos)
if crossing is None:
return next_pos
# if the crossing arc ends before the next position, it becomes impossible to jump without crossing it
_, end = crossing
if end < next_pos:
return None
# clear the arc
next_pos = end + 1
# perform a jump of the given length according to the active rules
def jump(self, length: int):
next_pos = self._move_backward(length)
if next_pos is None:
next_pos = self._move_forward(length)
if next_pos is None:
return
# update solver state
self.arcs[self.side].append((min(self.pos, next_pos), max(self.pos, next_pos)))
self.visited.add(next_pos)
self.side = 1 - self.side
self.pos = next_pos
def sum_final_positions(data: str, forward_skips_visited = False, forbid_crossings = False):
total = 0
for line in data.splitlines():
solver = Solver(forward_skips_visited, forbid_crossings)
for length in map(int, line.split(',')):
solver.jump(length)
total += solver.pos
return total
def part1(data: str):
"""
Rules:
- For each jump, first try to move backwards by its specified length.
- If the destination is negative or has been visited before, move forwards by the same distance.
"""
return sum_final_positions(data)
def part2(data: str):
"""
Additional rules:
- Whenever a forward jump would land on a previously visited point,
increase the destination by one until you reach the first unvisited point
"""
return sum_final_positions(data, forward_skips_visited=True)
def part3(data: str):
"""
Additional rules:
- If a backward jump would cause a crossing, try moving forwards instead
- If a forward jump would cause a crossing, keep increasing its length by one until there is no crossing
- If no valid forward jump exists, skip that jump entirely and continue with the next jump length in the sequence
"""
return sum_final_positions(data, forward_skips_visited=True, forbid_crossings=True)
