# 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)