Advent of Code 2023 Day 3, Part 2 in Python

Question

Part 2

I'm not sure if my solution covers all edge cases. The puzzle goes as follows: Given some input like this:

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

We're looking for * symbols ("gears") that are adjacent to precisely two integers, and compute the sum of the product of adjacent integers. In the above example this would be 467 * 35 + 755 * 598 = 16345 + 451490 = 467835.

import re

PATTERN = r"\d+"


def go_forwards(line, start=0):
    part_number = ""
    for c in line[start:]:
        if c.isdigit():
            part_number = part_number + c
        else:
            break
    return part_number


def go_backwards(line, end=0):
    part_number = ""
    for c in reversed(line[:end]):
        if c.isdigit():
            part_number = part_number + c
        else:
            break
    return part_number[::-1]


with open("input.txt") as f:
    lines = f.readlines()

    sum = 0

    for line_index, curr_line in enumerate(lines):
        curr_line = "".join(curr_line.strip())

        if line_index == 0:
            prev_line = curr_line
        if line_index >= len(lines) - 1:
            next_line = curr_line
        else:
            next_line = lines[line_index + 1]

        for pos, c in enumerate(curr_line):
            if c == "*":
                adjacents = 0

                # check number of adjacents before doing anything
                if curr_line[pos - 1].isdigit():
                    adjacents += 1
                if curr_line[pos + 1].isdigit():
                    adjacents += 1
                adjacents += len(re.findall(PATTERN, prev_line[pos - 1:pos + 2]))
                adjacents += len(re.findall(PATTERN, next_line[pos - 1:pos + 2]))

                if adjacents != 2:
                    continue

                part_numbers = list()

                # part numbers next to *
                if curr_line[pos - 1].isdigit():
                    part_numbers.append(go_backwards(curr_line, end=pos))
                if curr_line[pos + 1].isdigit():
                    part_numbers.append(go_forwards(curr_line, start=pos + 1))

                # part number in prev line at * position
                if prev_line[pos].isdigit():
                    part_numbers.append(
                        go_backwards(prev_line, end=pos + 1)
                        + go_forwards(prev_line, start=pos + 1)
                    )
                # part number in prev line at position -1 or +1 of *
                else:
                    if prev_line[pos - 1].isdigit():
                        part_numbers.append(go_backwards(prev_line, end=pos))
                    if prev_line[pos + 1].isdigit():
                        part_numbers.append(go_forwards(prev_line, start=pos + 1))

                # part number in next line at * position
                if next_line[pos].isdigit():
                    part_numbers.append(
                        go_backwards(next_line, end=pos + 1)
                        + go_forwards(next_line, start=pos + 1)
                    )
                # part number in next line at position -1 or +1 of *
                else:
                    if next_line[pos - 1].isdigit():
                        part_numbers.append(go_backwards(next_line, end=pos))
                    if next_line[pos + 1].isdigit():
                        part_numbers.append(go_forwards(next_line, start=pos + 1))

                sum += int(part_numbers[0]) * int(part_numbers[1])

        prev_line = curr_line

print(sum)

Review request

The idea was to run through each character in an input line and search for the symbol *. If it is found, the number of adjacent digits is checked. If there are not exactly two, the program simply moves on to the next character. Otherwise, the program scrolls either forwards or backwards depending on the position of the digit found. If a digit is found exactly at the position of the * symbol in the previous or next line, the program moves both forwards and backwards. The corresponding functions go_backwards and go_forwards return a character string with the adjacent digits.

This code works for both the example input and my real input. However, I'm not sure if my code covers all edge cases.

• Do you see any weaknesses here that you would replace?
• Does your input contain edge cases that break my code?
• What would you do differently?

Answer 1

representation

What would you do differently?

You used many immutable strings to represent the schematic diagram. Given that this spatially-oriented problem is asking us to examine Moore neighborhoods, I feel an array of (x, y) grid locations would be the most natural representation.

And, to facilitate bookkeeping, I would find it convenient to have a mutable array (or ndarray) so we can mark part numbers as "done" on the diagram. This emulates a human pen-and-paper approach to solving this puzzle, where we scan for gears and use a pen to cross out adjacent part numbers we have found.

Consider part 123 surrounded by three vertically stacked gears as both left- and right- bookends, plus one or two gears above and below. Any of those gears could also touch 456. Upon finding the first winning gear, I would want to scan left to locate 1. Then erase each digit as we scan rightward toward 3, for no "double counting". In the course of constructing our array it would be convenient to tack on {top, bottom, left, right} blank borders which definitely don't have gears. Then the Moore neighborhood check needn't worry about going out of bounds.

---

forward scan

def go_forwards(line, start=0):
    ...
    return part_number

This is beautifully clear, thank you.

I am skeptical that defaulting to zero is helpful. It seems to invite caller to accidentally misuse this helper -- we probably always want to specify an x-coordinate.

A type annotation which explains we return str (rather than e.g. an int part number) would be helpful, though we are saved by the brevity and simplicity of the function.

Similarly, a """docstring""" isn't necessary but it wouldn't hurt.

---

backward scan

def go_backwards(line, end=0):

I found this Public API a little surprising.

As mentioned, I initially envisioned the "find a part number!" task as scanning left followed by a rightward scan readout. It's something that works for any part number, no matter which side of it touches gear(s).

Here, we seem to be talking about more than just the part number, as the spatial relationship to (one of) its gears also matters.

I understand, from viewing the implementation, why you chose the identifier end. But to put that in the Public API is a bit jarring to the caller, who of course only has a start location in hand. This seems to be fallout from the decision to represent the diagram as many strings rather than as a grid of (x, y) locations.

---

use a function

with open("input.txt") as f:
    lines = f.readlines()

    sum = 0
    ...

This is nice enough. Thank you for using a with context handler to close f. Once we have lines it will stick around, even if we exdent the sum assignment four spaces to the left.

This (longish) block of code belongs within def main(): or similar function. And then we might break out small helper functions.

Avoid shadowing builtins like sum(). The conventional name would be sum_, or perhaps prefer total.

---

strip whitespace

        curr_line = "".join(curr_line.strip())

That's weird. I understand you wanted at least .rstrip() to trim the trailing newline. But the .join is quite odd, recommend you delete it.

---

prev / next

        if line_index == 0:
            prev_line = curr_line
        if line_index >= len(lines) - 1:
            next_line = curr_line
        else:
            next_line = lines[line_index + 1]
        ...
        prev_line = curr_line

We always have prev_line defined, good. But some automated code analyzers will tend to make a false report that a .findall on prev_line[pos - 1:pos + 2] may use an uninitialized variable. So don't be surprised when code like OP is edited by some future maintenance engineer to start with a "useless" initialization assignment of, say, empty string.

This is perhaps slightly tricky logic. It relies on an (easily proved) theorem from the problem domain: Pretending that gears in current line were also part of the previous line won't change the result. This is partly due to our neighborhood definition (currently the symmetric Moore neighborhood), and partly due to digit characters and gear characters forming disjoint sets. I continue to feel that random access to (x, y) locations would be a more natural fit to the business domain.

We strive to write functions (or "blocks" of main code) that can be visually taken in as a single screenfull, with no scrolling, to facilitate Local Analysis. That (buried) final assignment line illustrates why writing "short" functions is so important.

---

two techniques with same meaning

                # check number of adjacents before doing anything
                if curr_line[pos - 1].isdigit():
                    adjacents += 1
                if curr_line[pos + 1].isdigit():
                    adjacents += 1
                adjacents += len(re.findall(PATTERN, prev_line[pos - 1:pos + 2]))
                adjacents += len(re.findall(PATTERN, next_line[pos - 1:pos + 2]))

Thank you for the helpful comment, and for vertically setting this code apart. As usual, when you feel the need to write a comment, that often suggests the need to write a helper function. Here, we might name it def get_number_of_adjacents....

The name PATTERN is not very helpful. Better to mention that it matches digits.

I find it sad that we have two different approaches for accomplishing the same thing:

1. test character .is_digit()
2. regex digit pattern match

The current code could at least unify them by eschewing .is_digit in favor of a regex pattern match.

But better to eschew regexes entirely, and use .is_digit everywhere.

In the requirements we see:

any number adjacent to a symbol ... is a "part number"

                if adjacents != 2:
                    continue

I have no idea what that means. Are we seeking just multi-digit part numbers and ruling out 7 as a valid part? No. Maybe it is restricting us to the (smaller) Von Neumann neighborhood? I am at a loss to explain the motivation behind the magic number 2. You might have written a # comment to help me out.

This diagram should explain my confusion:

...378..
..*.....
........

3 is adjacent to a gear. I only come up with adjacents == 1 in this situation. Seems like a bug.

                part_numbers = list()

Standard idiom here is to assign ... = []. Larry Wall says there's more than one way to skin a cat. GvR says there should be one obvious way to do it.

---

delta coords

My goodness, what a lot of code to express the "is adjacent" concept!

                # part numbers next to *
                ...
                # part number in prev line at * position
                ...
                # part number in prev line at position -1 or +1 of *
                ...
                # part number in next line at * position
                ...
                # part number in next line at position -1 or +1 of *
                ...

Prefer these simpler (delta_x, delta_y) offsets:

    nbrhd = [
        (-1, -1),
        (0, -1),
        (1, -1),
        (-1, 0),
        (1, 0),
        (-1, 1),
        (0, 1),
        (1, 1),
    ]
    for dx, dy in nbrhd:
        examine x+dx, y+dy

Some folks prefer a pair of ranges, with the special case of ignoring the (0, 0) "self" cell.

---

This code appears to achieve its design goals.

I would not be willing to delegate or accept maintenance tasks on it.

Answer 2

Sometimes code gets too complicated. Your program processes the input text line-by-line and then character-by-character. Inside those nested for-loops, there is a big heap of algorithm: string indices are micromanaged; things like adjacents are tallied up; regular expressions are used, but on a super narrow scope; helper functions that further traverse the line character-by-character are invoked; and so forth. That's too much for a problem like this.

One source of complexity: doing everything at once. Even though you use two helper functions, the overall program is not decomposed into simpler parts, each handled by a narrowly tailored function. Instead, nearly everything is addressed in the guts of the nested for-loop structure. The solution here is to spend more planning time decomposing the problem into separate, and simpler, steps, each of which can be handled by a function.

Another source of complexity: operating on low level information. Your code accepts the data as given: lines of text that must be addressed character-by-character. That's too much tedium, too much mental overload for effective problem solving and readable code. Instead of reasoning over primitive data, spend more time considering how one might convert the given data into other information that makes the programming logic easier and more expressive.

Take advantage of those regular expressions. Your code uses re.findall(), but a more powerful approach for this problem is re.finditer(), which will give us re.Match objects that know their matched text and its position in the input string.

Initial steps: convert raw input into more useful data. Get the input file path from the user (don't hardcode it), read the lines (using a function), and convert each line into a list of our own Match objects holding the information we need.

import sys
import re
from dataclasses import dataclass

def main(args):
    path = args[0]
    lines = read_input(path)
    matches = [
        Match(m.group(), r, m.start(), m.end())
        for r, line in enumerate(lines)
        for m in re.finditer(r'\d+|\*', line)
    ]

def read_input(path):
    with open(path) as fh:
        return [line.strip() for line in fh]

@dataclass
class Match(frozen = True):
    text: str
    row: int
    start: int
    end: int

if __name__ == '__main__':
    main(sys.argv[1:])

What level are we at now? At this point, we are well beyond character-by-character analysis. Indeed, we've eliminated the grid itself (our data is a flat list).

Possible next steps. One idea is to separate the matches into two categories: multiplication symbols and numbers.

MULT = '*'

def main(args):
    ...
    mults = [m for m in matches if m.text == MULT]
    nums  = [m for m in matches if m.text != MULT]

Create a dict mapping each multiplication symbol to any numbers that it connects to. Finding those connections might involve the use of itertools and a simple helper function that takes two matches and returns true if they are connected (if the brute force of itertools is too slow, you could apply binary search to check only nums nearby a given mult). Once you have that dict, the multiplications occur wherever a symbol has multiple numbers.

from itertools product

def main(args):
    ...
    connections = {}
    for mult, num in product(mults, nums):
        if connected(mult, num):
            connections.setdefault(mult, []).append(num)

    for mult, nums in connections.items():
        if len(nums) > 1:
            # Boom.
            ...

def connected(mult, num):
    ...