APL

I’m using this years’ AoC to learn (Dyalog) APL, so this is probably terrible code. I’m happy to receive pointers for improvement, particularly if there is a way to write the same logic with tacit functions or inner/outer products that I missed.

input←⊃⎕NGET'inputs/day4.txt'1
num_matches←'Card [ \d]+: ([ 0-9]+) \| ([ 0-9]+)'⎕S{≢↑∩/0~⍨¨{,⎕CSV⍠'Separator' ' '⊢⍵'S'3}¨⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} input
⎕←+/2*1-⍨0~⍨num_matches ⍝ part 1
⎕←+/{⍺←0 ⋄ ⍺=≢⍵:⍵ ⋄ (⍺+1)∇⍵ + (≢⍵)↑∊((⍺+1)⍴0)(num_matches[⍺]⍴⍵[⍺])((≢⍵)⍴0)}(≢num_matches)⍴1 ⍝ part 2

Crystal

late because I had to skip two days of aoc. Fairly easy

input =  File.read("input.txt").lines

sum = 0
winnings = Array.new(input.size) {[1, 0]}
input.each_with_index do |line, i|
	card, values = line.split(":")
	nums = values.split("|").map(&.split.map(&.to_i))

	points = 0
	nums[1].each do |num|
		if nums[0].includes?(num)
			points = points == 0 ? 1 : points * 2
			winnings[i][1] += 1
	end    end
	sum += points
end
puts sum

winnings.each_with_index do |card, i|
	next if card[1] == 0
	(1..card[1]).each do |n|
		winnings[i+n][0] += card[0]
end    end
puts winnings.sum(&.[0])

Late as always (actually a day late by UK time).

My solution to this one runs slow, but it gets the job done. I didn’t actually need the CardInfo struct by the time I was done, but couldn’t be bothered to remove it. Previously, it held more than just count.

Day 04 in Rust 🦀

View formatted on GitLab

use std::{
    collections::BTreeMap,
    env, fs,
    io::{self, BufRead, BufReader, Read},
};

fn main() -> io::Result<()> {
    let args: Vec = env::args().collect();
    let filename = &args[1];
    let file1 = fs::File::open(filename)?;
    let file2 = fs::File::open(filename)?;
    let reader1 = BufReader::new(file1);
    let reader2 = BufReader::new(file2);

    println!("Part one: {}", process_part_one(reader1));
    println!("Part two: {}", process_part_two(reader2));
    Ok(())
}

fn process_part_one(reader: BufReader) -> u32 {
    let mut sum = 0;
    for line in reader.lines().flatten() {
        let card_data: Vec<_> = line.split(": ").collect();
        let all_numbers = card_data[1];
        let number_parts: Vec> = all_numbers
            .split('|')
            .map(|x| {
                x.replace("  ", " ")
                    .split_whitespace()
                    .map(|val| val.to_string())
                    .collect()
            })
            .collect();
        let (winning_nums, owned_nums) = (&number_parts[0], &number_parts[1]);
        let matches = owned_nums
            .iter()
            .filter(|num| winning_nums.contains(num))
            .count();
        if matches > 0 {
            sum += 2_u32.pow((matches - 1) as u32);
        }
    }
    sum
}

#[derive(Debug)]
struct CardInfo {
    count: u32,
}

fn process_part_two(reader: BufReader) -> u32 {
    let mut cards: BTreeMap = BTreeMap::new();
    for line in reader.lines().flatten() {
        let card_data: Vec<_> = line.split(": ").collect();
        let card_id: u32 = card_data[0]
            .replace("Card", "")
            .trim()
            .parse()
            .expect("is digit");
        let all_numbers = card_data[1];
        let number_parts: Vec> = all_numbers
            .split('|')
            .map(|x| {
                x.replace("  ", " ")
                    .split_whitespace()
                    .map(|val| val.to_string())
                    .collect()
            })
            .collect();
        let (winning_nums, owned_nums) = (&number_parts[0], &number_parts[1]);
        let matches = owned_nums
            .iter()
            .filter(|num| winning_nums.contains(num))
            .count();
        let card_details = CardInfo { count: 1 };
        if let Some(old_card_info) = cards.insert(card_id, card_details) {
            let card_entry = cards.get_mut(&card_id);
            card_entry.expect("card exists").count += old_card_info.count;
        };
        let current_card = cards.get(&card_id).expect("card exists");
        if matches > 0 {
            for _ in 0..current_card.count {
                for i in (card_id + 1)..=(matches as u32) + card_id {
                    let new_card_info = CardInfo { count: 1 };
                    if let Some(old_card_info) = cards.insert(i, new_card_info) {
                        let card_entry = cards.get_mut(&i).expect("card exists");
                        card_entry.count += old_card_info.count;
                    }
                }
            }
        }
    }
    let sum = cards.iter().fold(0, |acc, c| acc + c.1.count);
    sum
}

#[cfg(test)]
mod tests {
    use super::*;

    const INPUT: &str = "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";

    #[test]
    fn test_process_part_one() {
        let input_bytes = INPUT.as_bytes();
        assert_eq!(13, process_part_one(BufReader::new(input_bytes)));
    }

    #[test]
    fn test_process_part_two() {
        let input_bytes = INPUT.as_bytes();
        assert_eq!(30, process_part_two(BufReader::new(input_bytes)));
    }
}

[Language: Lean4]

I’ll only post the actual parsing and solution. I have written some helpers which are in other files, as is the main function. For the full code, please see my github repo.

I’m pretty sure that implementing part 2 in a naive way would cause Lean to demand a proof of termination, what might not be that easy to supply in this case… Luckily there’s a way more elegant and way faster solution than the naive one, that can use structural recursion and therefore doesn’t need an extra proof of termination.

structure Card where
  id : Nat
  winningNumbers : List Nat
  haveNumbers : List Nat
  deriving Repr

private def Card.matches (c : Card) : Nat :=
  flip c.haveNumbers.foldl 0 λo n ↦
    if c.winningNumbers.contains n then o + 1 else o

private def Card.score : Card → Nat :=
  (· / 2) ∘ (2^·) ∘ Card.matches

abbrev Deck := List Card

private def Deck.score : Deck → Nat :=
  List.foldl (· + ·.score) 0

def parse (input : String) : Option Deck := do
  let mut cards : Deck := []
  for line in input.splitOn "\n" do
    if line.isEmpty then
      continue
    let cs := line.splitOn ":"
    if p : cs.length = 2 then
      let f := String.trim $ cs[0]'(by simp[p])
      let g := String.trim $ cs[1]'(by simp[p])
      if not $ f.startsWith "Card " then
        failure
      let f := f.drop 5 |> String.trim
      let f ← f.toNat?
      let g := g.splitOn "|"
      if q : g.length = 2 then
        let winners := String.trim $ g[0]'(by simp[q])
        let draws := String.trim $ g[1]'(by simp[q])
        let toNumbers := λ(s : String) ↦
          s.split (·.isWhitespace)
          |> List.filter (not ∘ String.isEmpty)
          |> List.mapM String.toNat?
        let winners ← toNumbers winners
        let draws ← toNumbers draws
        cards := {id := f, winningNumbers := winners, haveNumbers := draws : Card} :: cards
      else
        failure
    else
      failure
  return cards -- cards is **reversed**, that's intentional. It doesn't affect part 1, but makes part 2 easier.

def part1 : Deck → Nat := Deck.score

def part2 (input : Deck) : Nat :=
  -- Okay, doing this brute-force is dumb.
  -- Instead let's compute how many cards each original card is worth, and sum that up.
  -- This relies on parse outputting the cards in **reverse** order.
  let multipliers := input.map Card.matches
  let sumNextN : Nat → List Nat → Nat := λn l ↦ (l.take n).foldl (· + ·) 0
  let rec helper : List Nat → List Nat → List Nat := λ input output ↦ match input with
    | [] => output
    | a :: as => helper as $ (1 + (sumNextN a output)) :: output
  let worths := helper multipliers []
  worths.foldl (· + ·) 0

PHP

Today was the easiest day so far IMHO. Today, I coded in PHP, a horrible language that produces even worse code. (Ok, full confession, I fed my family for about half a decade on PHP. I seemed to have gotten stuck with it, and so I earned a PhD to escape it.)

Anyway, the only trouble I had was I forgot about the explode function’s capacity to return empty strings. Once I filtered those I had the correct answer on the first one, and then 10 minutes later I had the second part. I wrote my code true to raw php’s awful idioms, though I didn’t make it web based. I read from stdin.

My code is linked on github:

• https://github.com/pngwen/advent-2023/blob/main/day-4a.php
• https://github.com/pngwen/advent-2023/blob/main/day-4b.php