Intro

First things first, I stopped using Go and started using Python. You can find my new solutions repo here. I decided to stop using Go because I am also working through SICP in addition to Advent of Code and a stealthmode side project I’m working on. That’s all in addition to my fulltime job, so something had to give and I’m dropping Go for now. What I saw was interesting though, and I hope to work with it again soon.

Now, for the solution!

Solution

My first approach to this problem was way more complicated than it needed to be. I was first calculating the required dimensions of the board by calculating the max width/height requirements of the cord pair. This was way too slow in Python (it’s also just a bad approach - don’t want to blame the language for my poor algorithm choice).

My next approach was to track the grid state as a dictionary where keys are strings of the form “x,y” and values are the IDs of the cord that passes through that square.

This is the main driver that process all the cord segments:

cord_id = 0
for cord in cords:
    x = 0
    y = 0
    steps = 0
    for segment in cord:
        if segment.direction == "L":
            process_left(cord_id, board, x, y, segment.distance, steps)
            x -= segment.distance
        elif segment.direction == "U":
            process_up(cord_id, board, x, y, segment.distance, steps)
            y -= segment.distance
        elif segment.direction == "R":
            process_right(cord_id, board, x, y, segment.distance, steps)
            x += segment.distance
        elif segment.direction == "D":
            process_down(cord_id, board, x, y, segment.distance, steps)
            y += segment.distance
        steps += segment.distance
    cord_id += 1

And this is a directional processing function:

def process_left(cord_id, board, x, y, distance, steps):
    while distance > 0:
        square = str(x) + "," + str(y)
        update_board(cord_id, board, square, steps)
        x -= 1
        distance -= 1
        steps += 1

There are four different processing functions, one for each direction. You could create a single process function that updates the right coordinate with a switch statement, because the rest of the code is the same between the functions. In fact, I think that’s a better way to do things, but I’m too far behind on the puzzles to tackle refactoring a working solution right now.

The update_board function simply adds the cord id (and steps to the square, for part 2) to the dictionary if the square isn’t there yet. It appends the new cord if it hasn’t been there before.

def update_board(cord_id, board, key, steps):
    if (key in board) and (cord_id not in board[key]):
        board[key][cord_id] = steps
    else:
        board[key] = {cord_id: steps}

The main solving loop is straightforward enough. It iterates though the grid and tests squares with more than one cord to see if they are less than the running minimums. If they are, the minimums get updated. Easy peasy.

for key, value in board.items():
    if len(value) > 1:
        manhattan_distance = calc_manhattan_dist(key)
        if manhattan_distance < min_distance and manhattan_distance != 0:
            min_distance = manhattan_distance

        # value here has the form {0: 120230, 1: 21387}
        current_steps = 0
        for cord_id, steps in value.items():
            current_steps += steps
        
        if current_steps < min_steps and manhattan_distance != 0:
            min_steps = current_steps

Again, the full repo is here!