3
\$\begingroup\$

Part 1:

The task involves determining the total points of a set of scratchcards. Each scratchcard contains two lists of numbers: the winning numbers and the numbers the player has. Points are awarded based on matches with the winning numbers, with the first match earning 1 point and each subsequent match doubling the point value. The goal is to calculate the total points for all scratchcards in a given input.

The Elf leads you over to the pile of colorful cards. There, you discover dozens of scratchcards, all with their opaque covering already scratched off. Picking one up, it looks like each card has two lists of numbers separated by a vertical bar (|): a list of winning numbers and then a list of numbers you have. You organize the information into a table (your puzzle input).

As far as the Elf has been able to figure out, you have to figure out which of the numbers you have appear in the list of winning numbers. The first match makes the card worth one point and each match after the first doubles the point value of that card.

For example:

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11

In the above example:

  1. Card 1 has four winning numbers (48, 83, 86, and 17), so it is worth 8 points (1 for the first match, then doubled three times for each of the three matches after the first).
  2. Card 2 has two winning numbers (32 and 61), so it is worth 2 points.
  3. Card 3 has two winning numbers (1 and 21), so it is worth 2 points.
  4. Card 4 has one winning number (84), so it is worth 1 point.
  5. Card 5 has no winning numbers, so it is worth no points.
  6. Card 6 has no winning numbers, so it is worth no points.

So, in this example, the Elf's pile of scratchcards is worth 13 points.

#!/usr/bin/env python3

import re
from pathlib import Path
from typing import Iterable

import typer


def calculate_points(old: list, new: list) -> int:
    count = 0

    for num in new:
        if num in old:
            count = 1 if count == 0 else count * 2

    return count


def card_points(line: str) -> int:
    # Card X: w1, w2, w3, .... | p1, p2, p3, ....
    pattern = r"((\d+\s+)+)|\s((\d+\s+)+)"
    groups = [x.group() for x in re.finditer(pattern, line)]
    winning, ours = [list(map(int, group.split())) for group in groups]
    return calculate_points(winning, ours)


def total_points(lines: Iterable[str]) -> int:
    return sum(map(card_points, lines))


def main(scratchcards_file: Path) -> None:
    with open(scratchcards_file, "r") as f:
        print(total_points(f))


if __name__ == "__main__":
    typer.run(main)

Part 2:

The second part involves scratchcards where matching numbers result in winning additional copies of subsequent cards, creating a chain of winnings. The goal is to determine the total number of scratchcards, including both the original set and all copies won.

This time, the above example goes differently:

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11
  1. Card 1 wins one copy each of the next four cards: cards 2, 3, 4, and 5.
  2. Original card 2 wins one copy each of cards 3 and 4.
  3. Copy of card 2 also wins one copy each of cards 3 and 4.
  4. Four instances of card 3 (one original and three copies) win four copies each of cards 4 and 5.
  5. Eight instances of card 4 (one original and seven copies) win eight copies of card 5.
  6. Fourteen instances of card 5 (one original and thirteen copies) have no matching numbers and win no more cards.
  7. One instance of card 6 (one original) has no matching numbers and wins no more cards.

The result is 1 instance of card 1, 2 instances of card 2, 4 instances of card 3, 8 instances of card 4, 14 instances of card 5, and 1 instance of card 6. The total number of scratchcards at the end of this process is 30.

#!/usr/bin/env python3

import re
from pathlib import Path
from typing import Iterable

import typer


def count_cards(line: str) -> int:
    # Card X: w1, w2, w3, .... | p1, p2, p3, ....
    pattern = r"((\d+\s+)+)|\s((\d+\s+)+)"
    groups = [x.group() for x in re.finditer(pattern, line)]
    winning, ours = [list(map(int, group.split())) for group in groups]
    return sum(1 for num in ours if num in winning)


def total_cards(scratchcards: Iterable[str]) -> int:
    card_counts = {}
    line_idx = 1
    total = 0

    for card in scratchcards:
        card_counts[line_idx] = card_counts.get(line_idx, 0) + 1
        matching = count_cards(card)

        for _ in range(card_counts[line_idx]):
            for i in range(line_idx + 1, line_idx + matching + 1):
                card_counts[i] = card_counts.get(i, 0) + 1

        total += card_counts[line_idx]
        line_idx += 1

    return total


def main(scratchcards_file: Path) -> None:
    with open(scratchcards_file, "r") as f:
        print(total_cards(f))


if __name__ == "__main__":
    typer.run(main)

Review Request:

General coding comments, style, etc.

Today, I learned that the default mode for the open() function is read, and the second argument is optional. What is the convention regarding specifying the mode?

Is the regex robust?

What are some possible simplifications? What would you do differently?

\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

Docstrings

None of your functions are documented, while you have type annotations (which is great) they don't describe what the function is intended to do or how beyond the name. Docstrings can be added to functions simply by making the first line of the function a string:

def double(x: int) -> int:
    """Doubles the integer x"""
    return 2*x

and then can be read by calling help(double)

Internal comments can also be helpful to describe what a block of code is meant to be doing. But commenting is somewhat of a dark art and everyone has a different way of doing it and expectations. Nonetheless the total lack of comments besides a slightly misleading pattern (as already highlighted) is probably not sufficient.

REs

REs are somewhat costly and in this case, I would say use split as suggested by J_H. However, you have capturing groups where the capturing group is not used. If the group is not used later it can be best to mark it as non-capturing.

pattern = r"(?:re)"

This means it does not get added to the groups.

In your case, you use none of the captures and an unexpected alternation, which I believe you may have intended to be a literal |, in which case you need to escape it.

pattern = r"(?:\d+\s+)+\|\s+(?:\d+\s+)+"

In the case of parsing this, however, I would probably go for:

# Could make "game_id" `_` since it's unused, 
# but we may have wanted it in part 2 and this 
# makes the code more flexible.
game_id, numbers = line.split(":") 
ours, winning = numbers.split("|")
ours = [int(x) for x in ours.split()]
winning = [int(x) for x in winning.split()]

or if you wanted to have it in fewer lines:

ours, winning = ([int(x) for x in nums] for nums in numbers.split("|"))

or equivalently as a set

ours, winning = ({int(x) for x in nums} for nums in numbers.split("|"))

Enumerate

When you are looping over each game in part 2, you manually track the line_idx which is not really necessary. This is such a common operation Python has a built-in for it:

    card_counts = {}
    line_idx = 1
    total = 0

    for card in scratchcards:
        card_counts[line_idx] = card_counts.get(line_idx, 0) + 1
        matching = count_cards(card)

        for _ in range(card_counts[line_idx]):
            for i in range(line_idx + 1, line_idx + matching + 1):
                card_counts[i] = card_counts.get(i, 0) + 1

        total += card_counts[line_idx]
        line_idx += 1

becomes

    card_counts = {}
    total = 0

    for line_idx, card in enumerate(scratchcards, 1):
        card_counts[line_idx] = card_counts.get(line_idx, 0) + 1
        matching = count_cards(card)

        for _ in range(card_counts[line_idx]):
            for i in range(line_idx + 1, line_idx + matching + 1):
                card_counts[i] = card_counts.get(i, 0) + 1

        total += card_counts[line_idx]

where enumerate returns a tuple of (index, value) for an iterable. The 1 says start counting from 1 (default is 0).

Calculating points

Sometimes with these sorts of puzzles it's a good trick to think about what the maths is telling you rather than simply coding the naive solution (it becomes essential in many problems, in particular AoC is set up so that the part 1 can be easily brute-forced, while part 2 is impossible to solve in any real time without using some tricks).

In our case, the points are essentially floor(2**(count - 1)) e.g.

count pts reason
0 0 (2^-1 = 0.5 which floors to 0)
1 1 (2^0 = 1)
2 2 (2^1 = 2)
5 16 (2^4 = 16)

That means that all we need is the count.

If we were using lists as you are:

def calculate_points(old: list, new: list) -> int:
    count = sum(1 for num in new if num in old)

    return floor(2**(count - 1))
    # OR
    return 2**(count - 1) if count else 0

Or if we were using sets

def calculate_points(old: set, new: set) -> int:
    count = len(old & new)

    return floor(2**(count - 1))
    # OR
    return 2**(count - 1) if count else 0

Overall Structure

For reusability of functions, I would probably:

  • change calculate_points to just return the count which means we can use this again in part 2
  • rather than packing everything into card_points I would make card_points into parse_round and return winning & ours as a tuple from the function.

This means that rather than having to duplicate everything in part 2 we already have the tools we need. It also (to me) divides the code into more concrete stages:

  • parse file
  • get winners
  • score winners - Only different part between 1 & 2
  • compute total
\$\endgroup\$
2
\$\begingroup\$

Nice shebang! I like how it obeys $PATH, which is good for {venv, conda, poetry} environments. Also, typer FTW!

list types

def calculate_points(old: list, new: list) -> int:

Thank you for the optional type annotation. I would have appreciated being told that we're maybe receiving list[str], or, as it turns out, list[int]. The total_points annotation of Iterable[str], for example, is beautiful.

        if num in old:

The in operator is O(N) linear in length of list, so the nested loops have O(N²) quadratic cost, since the inputs are of similar lengths. N is "small", so it makes no practical difference here. But it's better to habitually prefer an appropriate data structure, such as set that offers O(1) constant lookup time.

If you convert both inputs to sets, then cPython offers a set intersection at the speed of C rather than waiting for an interpreted bytecode loop to complete.

It's unclear why old, new are sensible identifiers here. Leaving them as vanilla a, b would be fine.


comments lie

def card_points(line: str) -> int:
    # Card X: w1, w2, w3, .... | p1, p2, p3, ....
    pattern = r"((\d+\s+)+)|\s((\d+\s+)+)"

At first I thought you were helping me by offering that comment. But I read and re-read and just couldn't get the regex to work with that helpfully supplied input. Eventually I scrolled up to view the puzzle's example input and then all became clear.

Turning e.g. 83 into a symbolic w3 is fine. But the , commas are a big deal; they mislead me. Also, matching trailing whitespace of SPACE vs NEWLINE is kind of an interesting detail. Is it robust? Sure. But I feel it could be more readable.

We have three fields to parse, and you're ignoring the first one that contains X, fine. I would rather see a .split("|") followed by parsing two simple lists of space-delimited numbers.

You could have made the "optional whitespace" a little clearer. A regex of STUFF|\sSTUFF is harder to read than \s?STUFF.


    with open(scratchcards_file, "r") as f:

What is the convention regarding specifying the mode?

Omitting the "r" is customary.

However, I hear that some folks want to see , encoding="utf8" everywhere. The concern is that OS locale might alter the encoding default, and then hilarity ensues. I tend to only worry about deployment on MacOS + Linux, on systems running in North America, so typically I'll omit an explicit encoding.


defaultdict

    card_counts = {}

Consider using:

from collections import defaultdict
...
    card_counts = defaultdict(int)

It's handy for writing card_counts[i] += 1. What you did with .get defaulting is perfectly nice as-is.


This code achieves its design goals.

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

\$\endgroup\$
4
  • \$\begingroup\$ This is excellent. Thank you. Besides the inappropriate data structure, do you see any other potential bottlenecks contributing to the 11-12 second delay in processing a file with 193 lines? \$\endgroup\$
    – Harith
    Dec 13, 2023 at 8:20
  • \$\begingroup\$ I would add to this to say that better than a defaultdict for handling counting jobs like this collections.Counter is a better specifier of intent with useful functionality for jobs related to counting. Though in this case, I feel a list/array is a better structure since we're just indexing only by a monotonically increasing integer. Another thing possibly worth noting is that it is easy to turn a list-comprehension into a set-comprehension simply by changing the braces from [] to {}. \$\endgroup\$ Dec 13, 2023 at 13:32
  • \$\begingroup\$ @DeathIncarnate Can I use a list without having to iterate over the file/iterable twice? \$\endgroup\$
    – Harith
    Dec 14, 2023 at 14:09
  • \$\begingroup\$ Given these lists are small, you can easily store them all in memory, and just use the length of the list to determine the size. Otherwise you will need to run through the file twice, or append to the list as needed. \$\endgroup\$ Dec 14, 2023 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.