Advent Of Code 2023 - Day Four Solution

Murtuzaali Surti
Murtuzaali Surti

• 3 min read

It felt easier than the previous one to be honest, especially the first part. The puzzle is quite simple. For a given number of scratchcards, there are two lists of numbers printed on it separated by a pipe | sign.

The first list contains of all the winning numbers and the second list contains the numbers given to you. You have to figure out which of the given numbers match the winning numbers. You get one point for the first match then double it for every match after the first.

Part One #

So, for example, if you have,

Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1

then, the matching numbers will be 1 and 21 and the points will be 1 after the first match and 1 * 2 = 2 points after the next. You need to sum up all the points for a pile of cards.

import { readFileByLine } from "../lib/shared.mjs";

const lines = await readFileByLine("day-4/input.txt");

const cardsWithTheirPoints = Array.from({ length: lines.length })
const cardsWithTheirWinningCopies = Array.from({ length: lines.length }).map((_, i) => ({
    card: i + 1,
    copies: {
        count: 1
    }
}))

function getNumbers(str, index) {
    return str.split("|")[index].trim().split(" ").map(i => i.trim()).filter(j => parseInt(j)).map(k => parseInt(k))
}

function PartOne() {
    for (const [i, line] of lines.entries()) {
        const cardNumbers = line.split(":")[1].trim()

        const winningNumbers = getNumbers(cardNumbers, 0);
        const numbersIhave = getNumbers(cardNumbers, 1);

        let points = 0;
        let firstMatch = true;
        const matchingNumbers = []

        for (const win of winningNumbers) {
            if (numbersIhave.includes(win)) {
                matchingNumbers.push(win)

                if (!firstMatch) {
                    points = points * 2
                } else {
                    points++;
                }

                firstMatch = false;
            }
        }

        cardsWithTheirPoints[i] = {
            matchingNumbers,
            points,
            card: i + 1
        }
    }

    return cardsWithTheirPoints.reduce((acc, curr) => acc + curr.points, 0);
}

const totalPointsOfPileOfCards = PartOne();

Part Two #

The second part is quite interesting. The concept of points is now removed. For each matching win number you win the next card. So, for example, if you have a card,

Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1

then, it has two matching numbers, 1 and 21 and therefore you also win cards 4 and 5. This way, multiple copies of cards are generated. If a card has no matching numbers, you win nothing. What you have to do is calculate all of the instances of each card (original + copies) and then sum them up to get the total number of scratchcards.

function PartTwo() {
    for (const [index, line] of lines.entries()) {
        function calc(index, line) {
            const card = index + 1;
            const cardNumbers = line.split(":")[1].trim();

            const winningNumbers = getNumbers(cardNumbers, 0);
            const numbersIhave = getNumbers(cardNumbers, 1);
            const matchingNumbers = [];

            for (const win of winningNumbers) {
                if (numbersIhave.includes(win)) {
                    matchingNumbers.push(win)
                }
            }

            if (matchingNumbers.length > 0) {
                const nextcards = Array.from({ length: ((matchingNumbers.length + card) - card) / 1 + 1 }, (_, t) => card + t * 1).slice(1);

                for (const winningCopyNumber of nextcards) {
                    cardsWithTheirWinningCopies[winningCopyNumber - 1].copies.count++;
                }
            }
        }

        for (let copy = 0; copy < cardsWithTheirWinningCopies[index].copies.count; copy++) {
            calc(index, line);
        }
    }

    return cardsWithTheirWinningCopies.reduce((acc, curr) => curr.copies.count + acc, 0);
}

For each winning number, I am incrementing the copies of the successor cards and then looping over the copies. I initiated the copies for every card with 1 depicting the original copy. If the card has no matching numbers, the copy count will be 1 as it generated no more winning cards.

The execution time for the second part in javascript is not up to the mark, and thus there's an opportunity to optimize, which I leave it to you.

exec Part 1: 3.171 ms
exec Part 2: 58.305 s

You can find the entire code in my repository as well as the code for the previous puzzles.


Web Components & Custom Elements

Previous

rssed — An RSS Feed Reader And Blogroll - Built Using Astro

Next