Advent of Code Day 4 — Scratchcards

In today’s puzzle, we’re helping an elf figure out if any of the few hundred scratchcards he’s scratched off have won him anything.

Why? I have no idea. There was a meme in the subreddit today with the top picture of a guy looking like he was totally over it all with the caption, “When my boss asks me to solve a weird problem for money”, and the guy on the bottom looking all excited with the caption, “When an elf asks me to solve a weird problem for free”.

(Yes, I do recognize Robert Downey Jr and Chris Pratt. Don’t @ me.)

So yeah, elf wants our help with scratch cards, we’re helping the elf with the scratch cards.

In Part 1, we’re explaining to him how these things work. You see the winning numbers, and the numbers you scratched off, and you get points for the number of matches — 1, 2, 4, 8 etc points, and no points for no matches. Sum them up, and you have the answer to Part 1.

Java

This seemed like a problem for sets — collections that can’t contain any duplicate items. If the winning numbers were a set, and the card numbers were a set, then the intersection of those two sets would be the winning numbers. Then just run through them and sum up the points.

    private void part1() {
        var lines = readFile("2023/puzzle4.dat");

        var part1 = lines.stream().map(this::parse)
            .map(this::intersection)
            .filter(s -> !s.isEmpty())
            .mapToInt(s -> 1 << (s.size() - 1))
            .sum();

        System.out.println("Part 1: " + part1);
    }

Java has a problem with requiring extra stuff. But briefly, we read the data, go through each line and map the input into two sets — winning numbers and card numbers. We intersect them, discard losing cards, then figure out the point value and sum them up.

Haskell

getDuplicates :: String -> Int
getDuplicates str = length $ filter (\x -> length x > 1) (group (sort (drop 2 $ words str)))

The Haskell solution is a little different. I was trying not to be spoiled at work today by other people’s solutions, but someone mentioned that you could parse the line just by seeing how many duplicate tokens you had, didn’t have to split into sets or anything. So that’s what this does. Working from right to left, words str splits the input into tokens by splitting at spaces. drop 2 $ drops the first two words, which are “Game n:”. I was afraid the game number might match one of the other numbers and be a false match, though I guess since it would have a “:” appended, probably unnecessary. sort sorts them so that duplicates are lined up next to each other. group puts all the items in lists, and those duplicates will be in the same list. filter… filters out all the lists with only one element (non-winning numbers). We only care about the number of wins, so length just replaces the list itself with the length of it, and that’s the number of winning numbers.

main :: IO ()
main = do
    lines <- readLinesFromFile "puzzle4.dat"
    let duplicates = map getDuplicates lines
    putStrLn $ "Part 1: " ++ show (sum $ map (\x -> 2 ^ (x-1)) (filter (> 0) duplicates))

We read the input, and call getDuplicates on every line, making a list of winning numbers. The last line filters out losing cards, then assigns a score, sums them up, and prints them out.

-- function takes a list of numbers and returns the sum of the game
playGame :: [Int] -> Int
-- if the list is empty, return 0
playGame [] = 0
-- if head is 0, return 0
playGame (0:xs) = 0
-- otherwise (x:xs) call sum playGame called with the next x elements of xs and add x
playGame (x:xs) = x + sum (map (\z -> playGame $ drop z xs) [0..x-1])

In Part 2, we discover that you only win more scratch cards when you win, the number of cards being equal to the number of winning numbers, and the cards you win are copies of the n next cards. Of course, you get to scratch off those copies and do the same again… it’s recursive.

This was my chance to explore Haskell’s pattern matching. playGame take a list of integers — the number of winning numbers in each game — and returns an integer — the number of cards you got from scratching off the first card in the list.

playGame [] = 0 says what to do with the empty list — simply return 0.

playGame (0:xs) = 0 says what to do if the first element of the list is zero — a losing ticket. Just immediately return 0.

playGame (x:xs) = … is what to do if the list has at least one element. It takes the first element and binds it to x, and the rest of the list to xs. From 0 to the number of winning numbers – 1 (inclusive), skip the first z elements of rest of the list and call playGame on them, sum them up, add the number of winning numbers for this copy of the card, and return.

    let part2Sum = sum $ map (\x ->  1 + playGame (drop x duplicates)) [0..length duplicates - 1]
    putStrLn $ "Part 2: " ++ show part2Sum

The first line slices the list so that every card has a chance to be first, calls playGame on them, adds 1 for the original card we’re on to the sum of all the other cards this card won, sums all those up, and that’s Part 2.

It’s recursive, so not super fast — it takes a second or two to get through Part 2. Haskell is a compiled language, unlike Java (uses virtual machine) or Python (interpreted but can compile to C). I was wondering if Haskell’s functionality would make it faster. Let me try running it in Python.

Okay, I rewrote it in Python.

def part2(data):
    duplicates = [countDuplicates(line) for line in data]
    part2_sum = sum(1 + play_game(duplicates[x:]) for x in range(len(duplicates)))
    return part2_sum

It’s not much slower, to it’s credit. People on Reddit were saying it was taking them over two minutes. Dunno how.

Anyway. On to Day 5.