....
.TH.
....


# Python imports
from __future__ import annotations  # aids with typing classes

import numpy as np

from pathlib import Path


test = Path("data/day09_test.txt")  # test data
test2 = Path("data/day09_test2.txt")  # more test data
data = Path("data/day09_data.txt")  # puzzle data


def parse_input(fpath: Path) -> list[tuple[str]]:
    """Parse puzzle input into
    
    :param fpath: path to puzzle input
    """
    with fpath.open() as ifh:
        data = [_.strip().split() for _ in ifh.readlines()]  # list of instruction characters
        return [(_[0], int(_[1])) for _ in data]  # cast number to int
    
class Knot:
    
    """Represents a single knot on the rope
    
    It has a location and potentially follows another knot
    """
    
    def __init__(self, xpos: int=0, ypos:int=0):
        """Initialise knot with start position and empty followers
        
        :param xpos:  start x-coordinate
        :param ypos:  start y-coordinate
        """
        self.xpos = xpos
        self.ypos = ypos
        self.next = []  # holds knots that will follow directly from this knot
        
    def add_follower(self, knot: Knot) -> None:
        """Add a Knot to follow the location of this knot"""
        self.next.append(knot)
        
    def update(self, xpos: int, ypos: int) -> None:
        """Move this knot to the new position (not following another knot)
        
        :param xpos:  new x-coordinate
        :param ypos:  new y-coordinate        
        """
        self.xpos = xpos
        self.ypos = ypos
        
        # Update locations of any following knots
        for knot in self.next:
            knot.follow(self.xpos, self.ypos)
            
    def follow(self, xpos: int, ypos: int) -> None:
        """Update knot location to follow that of another linked knot
        
        :param xpos:  knot x-coordinate (being followed)
        :param ypos:  knot y-coordinate (being followed)
        """
        # account for diagonal movement first
        if abs(xpos - self.xpos) > 1 and abs(ypos - self.ypos) > 1:  # diagonal
            if xpos - self.xpos > 1 and ypos - self.ypos > 1:  # move up/right
                self.xpos += 1
                self.ypos += 1
            if xpos - self.xpos > 1 and ypos - self.ypos < 1:  # move down/right
                self.xpos += 1
                self.ypos -= 1
            if xpos - self.xpos < 1 and ypos - self.ypos > 1:  # move up/left
                self.xpos -= 1
                self.ypos += 1
            if xpos - self.xpos < 1 and ypos - self.ypos < 1:  # move down/left
                self.xpos -= 1
                self.ypos -= 1
        else:  # U/D/L/R movement
            if xpos - self.xpos > 1:  # move right
                self.xpos += 1
                self.ypos = ypos
            elif self.xpos - xpos > 1:  # move left
                self.xpos -= 1
                self.ypos = ypos
            elif ypos - self.ypos > 1:  # move up
                self.ypos += 1
                self.xpos = xpos
            elif self.ypos - ypos > 1:  # move down
                self.ypos -= 1
                self.xpos = xpos

        # Update locations of any following knots
        for knot in self.next:
            knot.follow(self.xpos, self.ypos)
            
    @property
    def position(self) -> tuple[int, int]:
        """Return current knot position"""
        return (self.xpos, self.ypos)
        

class Rope:
    
    """Represents a rope, comprising a finite number of knots"""
    
    def __init__(self, knots: int=2):
        """Instantiate a rope with a stated number of knots
        
        :param knots:  the number of knots in the rope
        """
        self.knots = []  # holds all knots in rope
        self.knots.append(Knot())  # add a head knot
        
        # append any following knots to head knot
        for _ in range(knots - 1):  
            knot = Knot()  # new knot
            self.knots[-1].add_follower(knot)  # knot follows last current knot in rope
            self.knots.append(knot)  # add knot to current list
                    
        # tail visited locations
        self.tvis = set()
        self.tvis.add(self.tail.position)
            
        
    def update_head(self, drn: str, val: int) -> None:
        """Update the position of the head knot in the rope
        
        :param drn:  movement direction
        :param val:  number of steps of movement
        
        Each step updates the head position and cascades down the rope.
        Because each step may also update the tail position, we update our
        record of this on each step.
        """
        if drn == "R":  # move head right
            for _ in range(val):
                xpos, ypos = self.head.position
                self.head.update(xpos + 1, ypos)
                self.tvis.add(self.tail.position)
        elif drn == "L":  # move head left
            for _ in range(val):
                xpos, ypos = self.head.position
                self.head.update(xpos - 1, ypos)
                self.tvis.add(self.tail.position)
        elif drn == "U":  # move head up
            for _ in range(val):
                xpos, ypos = self.head.position
                self.head.update(xpos, ypos + 1)
                self.tvis.add(self.tail.position)
        else:  #  "D" - move head down
            for _ in range(val):
                xpos, ypos = self.head.position
                self.head.update(xpos, ypos - 1)
                self.tvis.add(self.tail.position)

    @property
    def head(self) -> Knot:
        """Return head knot in rope"""
        return self.knots[0]

    @property
    def tail(self) -> Knot:
        """Return tail knot in rope"""
        return self.knots[-1]
    
    def __str__(self) -> str:
        """Return string visualising current rope position"""
        # get bounds on positions
        xmin, xmax, ymin, ymax = 0, 0, 0, 0
        for xpos, ypos in [_.position for _ in self.knots]:
            if xpos < xmin:
                xmin = xpos
            elif xpos > xmax:
                xmax = xpos
            if ypos < ymin:
                ymin = ypos
            elif ypos > ymax:
                ymax = ypos
                
        # create square numpy array bounded as above
        arrsize = max(ymax - ymin + 1, xmax - xmin + 1)
        arrshape = (arrsize, arrsize)
        arr = np.zeros(arrshape, dtype=str)
        
        # populate array with rope locations
        for idx in range(len(self.knots)-1, -1, -1):
            xpos, ypos = self.knots[idx].position
            arr[ypos, xpos] = idx
            
        # make string representation that matches puzzle
        # (clunky, but hey...)
        outstr = []
        for row in arr[::-1]:
            rstr = ""
            for elem in row:
                if elem == "":
                    rstr += "."
                elif elem == "0":
                    rstr += "H"
                else:
                    rstr += elem
            outstr.append(rstr)
                
        return '\n'.join(outstr) + "\n"
            
    
def simulate(knots: int, instructions: list[tuple[str, int]]) -> Rope:
    """Return rope after simulation
    
    :param knots:  number of knots in the rope
    :param instructions:  instructions for moving the head of the rope
    """
    # initialise start position for the rope, and empty set of
    # positions visited by the tail
    rope = Rope(knots)
    
    # move the head with each instruction
    for drn, val in instructions:
        rope.update_head(drn, val)
        
    return rope

   
    
def part1(fpath: Path):
    """Solve the puzzle
    
    :param fpath:  path to puzzle input
    """
    instructions = parse_input(fpath)
    rope = simulate(2, instructions)
    return len(rope.tvis)


part1(test)

13


part1(data)

6026

== Initial State ==

......
......
......
......
H.....  (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s)

== R 4 ==

......
......
......
......
1H....  (1 covers 2, 3, 4, 5, 6, 7, 8, 9, s)

......
......
......
......
21H...  (2 covers 3, 4, 5, 6, 7, 8, 9, s)

......
......
......
......
321H..  (3 covers 4, 5, 6, 7, 8, 9, s)

......
......
......
......
4321H.  (4 covers 5, 6, 7, 8, 9, s)

== U 4 ==

......
......
......
....H.
4321..  (4 covers 5, 6, 7, 8, 9, s)

......
......
....H.
.4321.
5.....  (5 covers 6, 7, 8, 9, s)

......
....H.
....1.
.432..
5.....  (5 covers 6, 7, 8, 9, s)

....H.
....1.
..432.
.5....
6.....  (6 covers 7, 8, 9, s)

== L 3 ==

...H..
....1.
..432.
.5....
6.....  (6 covers 7, 8, 9, s)

..H1..
...2..
..43..
.5....
6.....  (6 covers 7, 8, 9, s)

.H1...
...2..
..43..
.5....
6.....  (6 covers 7, 8, 9, s)

== D 1 ==

..1...
.H.2..
..43..
.5....
6.....  (6 covers 7, 8, 9, s)

== R 4 ==

..1...
..H2..
..43..
.5....
6.....  (6 covers 7, 8, 9, s)

..1...
...H..  (H covers 2)
..43..
.5....
6.....  (6 covers 7, 8, 9, s)

......
...1H.  (1 covers 2)
..43..
.5....
6.....  (6 covers 7, 8, 9, s)

......
...21H
..43..
.5....
6.....  (6 covers 7, 8, 9, s)

== D 1 ==

......
...21.
..43.H
.5....
6.....  (6 covers 7, 8, 9, s)

== L 5 ==

......
...21.
..43H.
.5....
6.....  (6 covers 7, 8, 9, s)

......
...21.
..4H..  (H covers 3)
.5....
6.....  (6 covers 7, 8, 9, s)

......
...2..
..H1..  (H covers 4; 1 covers 3)
.5....
6.....  (6 covers 7, 8, 9, s)

......
...2..
.H13..  (1 covers 4)
.5....
6.....  (6 covers 7, 8, 9, s)

......
......
H123..  (2 covers 4)
.5....
6.....  (6 covers 7, 8, 9, s)

== R 2 ==

......
......
.H23..  (H covers 1; 2 covers 4)
.5....
6.....  (6 covers 7, 8, 9, s)

......
......
.1H3..  (H covers 2, 4)
.5....
6.....  (6 covers 7, 8, 9, s)


def part2(fpath: Path) -> int:
    """Solve the puzzle
    
    :param fpath:  path to puzzle input
    """
    instructions = parse_input(fpath)
    rope = simulate(10, instructions)
    return len(rope.tvis)


part2(test)

1


part2(test2)

36


part2(data)

2273

Day 9: Rope Bridge¶

Part 1¶

Part 2¶