QIR (Quantum Intermediate Representation)

Nah, just kidding - I used Rust. The only tricky part seemed to be finding time on a Sunday to get it coded!

Part 1 I swept down with a bool array for beams and part 2 I swept up with a score array and summed when it split (joined).

 rust

    
struct Teleporter(String);

impl Teleporter {
    fn new(s: String) -> Self {
        Self(s)
    }

    fn start_pos(line: &str) -> Result<usize> {
        line.find('S').ok_or_eyre("Start not found")
    }

    fn splits(&self) -> Result<usize> {
        let mut input = self.0.lines();
        let start_line = input.next().ok_or_eyre("No start line")?;
        let start = Self::start_pos(start_line)?;

        let mut beams = vec![false; start_line.len()];
        beams[start] = true;

        let mut splits = 0;
        for line in input {
            for (i, ch) in line.bytes().enumerate() {
                if beams[i] && ch == b'^' {
                    splits += 1;
                    beams[i] = false;
                    beams[i - 1] = true;
                    beams[i + 1] = true;
                }
            }
        }
        Ok(splits)
    }

    fn timelines(&self) -> Result<usize> {
        let mut input = self.0.lines();
        let start_line = input.next().ok_or_eyre("No start line")?;
        let start = Self::start_pos(start_line)?;

        let mut num_paths = vec![1; start_line.len()];
        for line in input.rev() {
            for (i, c) in line.bytes().enumerate() {
                if c == b'^' || c == b'S' {
                    num_paths[i] = num_paths[i - 1] + num_paths[i + 1];
                }
            }
        }
        Ok(num_paths[start])
    }
}

Why not use .iter().sum() and .iter().product()?

nushell

I was afk when the puzzle went up so I had another go at doing it on my phone in Turmux with my shell's scripting language. It's quite nice how your shell is also a REPL so you can build up the answer in pieces, although I wrote a file for the second part.

nu

    
open input.txt | str replace --all --regex ' +' ' ' |
        lines | each { $in | str trim } | to text |
        from csv --noheaders --separator ' ' |
        reverse | transpose --ignore-titles |
        each {
                |list| transpose | skip 1 | if $list.column0 == '+' { math sum } else { math product }
        } |
        math sum

Part 2

nu

    
let input = open input.txt | lines | each { $in | split chars }
let last_row = ($input | length) - 1
let last_col = ($input | first | length) - 1

mut op = ' '
mut numbers = []
mut grand_tot = 0
for x in $last_col..0 {
  if $op == '=' {
    $op = ' '
    continue
  }
  let n = 0..($last_row - 1) | each { |y| $input | get $y | get $x } | str join | into int
  $numbers = ($numbers | append $n)

  $op = $input | get $last_row | get $x
  if $op != ' ' {
    $grand_tot += $numbers | if $op == '+' { math sum } else { math product }
    $numbers = []
    $op = '='
  }
}
$grand_tot

Our local wizard who casts these spells is @mykl@lemmy.world

Rust

I didn't look at the input at first so tried a naive version with sets, but it was too slow even for part one. I got smarter and wrote a version with less code that runs in under half a millisecond.

 rust

    
type Id = usize;

struct Ingredients {
    fresh: Vec<RangeInclusive<Id>>,
    available: HashSet<Id>,
}

impl Ingredients {
    fn is_fresh(&self, id: Id) -> bool {
        self.fresh.iter().any(|range| range.contains(&id))
    }

    fn num_fresh_available(&self) -> usize {
        self.available
            .iter()
            .filter(|&&id| self.is_fresh(id))
            .count()
    }

    fn num_fresh_all(&self) -> usize {
        self.fresh
            .iter()
            .map(|range| 1 + range.end() - range.start())
            .sum()
    }
}

fn merge_ranges(mut ranges: Vec<RangeInclusive<Id>>) -> Vec<RangeInclusive<Id>> {
    if ranges.is_empty() {
        return ranges;
    }
    ranges.sort_by_key(|range| *range.start());

    let mut merged = Vec::new();
    let mut start = ranges[0].start();
    let mut end = ranges[0].end();
    for range in ranges.iter().skip(1) {
        if range.start() > end {
            merged.push(RangeInclusive::new(*start, *end));
            start = range.start();
            end = range.end();
        }
        if range.end() > end {
            end = range.end();
        }
    }
    merged.push(RangeInclusive::new(*start, *end));

    merged
}

impl FromStr for Ingredients {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let Some((fresh_str, avail_str)) = s.split_once("\n\n") else {
            bail!("missing divider");
        };

        let fresh = fresh_str
            .lines()
            .map(|l| -> Result<RangeInclusive<_>, Self::Err> {
                let (start, end) = l.split_once('-').ok_or_eyre("bad range")?;
                let start: Id = start.parse()?;
                let end: Id = end.parse()?;
                Ok(start..=end)
            })
            .collect::<Result<_, _>>()?;

        let available = avail_str
            .lines()
            .map(|l| l.parse())
            .collect::<Result<_, _>>()?;

        Ok(Ingredients {
            fresh: merge_ranges(fresh),
            available,
        })
    }
}

::: spoiler Full code

 rust

    
use std::{collections::HashSet, fs, ops::RangeInclusive, str::FromStr};

use color_eyre::eyre::{OptionExt, Report, Result, bail};

#[derive(Debug, PartialEq, Eq)]
struct Ingredients {
    fresh: Vec<RangeInclusive<Id>>,
    available: HashSet<Id>,
}

type Id = usize;

impl Ingredients {
    fn is_fresh(&self, id: Id) -> bool {
        self.fresh.iter().any(|range| range.contains(&id))
    }

    fn num_fresh_available(&self) -> usize {
        self.available
            .iter()
            .filter(|&&id| self.is_fresh(id))
            .count()
    }

    fn num_fresh_all(&self) -> usize {
        self.fresh
            .iter()
            .map(|range| 1 + range.end() - range.start())
            .sum()
    }
}

fn merge_ranges(mut ranges: Vec<RangeInclusive<Id>>) -> Vec<RangeInclusive<Id>> {
    if ranges.is_empty() {
        return ranges;
    }
    ranges.sort_by_key(|range| *range.start());

    let mut merged = Vec::new();
    let mut start = ranges[0].start();
    let mut end = ranges[0].end();
    for range in ranges.iter().skip(1) {
        if range.start() > end {
            merged.push(RangeInclusive::new(*start, *end));
            start = range.start();
            end = range.end();
        }
        if range.end() > end {
            end = range.end();
        }
    }
    merged.push(RangeInclusive::new(*start, *end));

    merged
}

impl FromStr for Ingredients {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let Some((fresh_str, avail_str)) = s.split_once("\n\n") else {
            bail!("missing divider");
        };

        let fresh = fresh_str
            .lines()
            .map(|l| -> Result<RangeInclusive<_>, Self::Err> {
                let (start, end) = l.split_once('-').ok_or_eyre("bad range")?;
                let start: Id = start.parse()?;
                let end: Id = end.parse()?;
                Ok(start..=end)
            })
            .collect::<Result<_, _>>()?;

        let available = avail_str
            .lines()
            .map(|l| l.parse())
            .collect::<Result<_, _>>()?;

        Ok(Ingredients {
            fresh: merge_ranges(fresh),
            available,
        })
    }
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let ingrd = Ingredients::from_str(&input).unwrap();
    Ok(ingrd.num_fresh_available())
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let ingrd = Ingredients::from_str(&input).unwrap();
    Ok(ingrd.num_fresh_all())
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("d05/input.txt")?);
    println!("Part 2: {}", part2("d05/input.txt")?);
    Ok(())
}

Ha, I've got that article half-read in a tab somewhere. Same problem here though - they're not in the standard library for anything I plan to use for AoC.

Now you're just showing off!

Edit: ooh, this makes it obvious that my puzzle input takes more cycles to reach the done state.

Rust

I pulled out some code from last year to make representing 2D grids as a vector easier, so this was quite straightforward. 2.5ms runtime (including reading/parsing the input twice cos of TDD).

 rust

    
impl Grid {
    fn neighbour(&self, i: usize, dir: Direction) -> Option<bool> {
        let width = self.width;
        let length = self.grid.len();

        use Direction::*;
        match dir {
            N if i >= width => Some(i - width),
            NE if i >= width && i % width != width - 1 => Some(i - width + 1),
            E if i % width != width - 1 => Some(i + 1),
            SE if i + width + 1 < length && i % width != width - 1 => Some(i + width + 1),
            S if i + width < length => Some(i + width),
            SW if i + width - 1 < length && !i.is_multiple_of(width) => Some(i + width - 1),
            W if !i.is_multiple_of(width) => Some(i - 1),
            NW if i >= width && !i.is_multiple_of(width) => Some(i - width - 1),
            _ => None,
        };
        .map(|i| self.grid[i])
    }

    #[rustfmt::skip]
    fn cell_accessible(&self, i: usize) -> bool {
        Direction::ALL
            .iter()
            .filter(|&&dir| self.neighbour(i, dir).unwrap_or(false))
            .count() < 4
    }

    fn num_accessible(&self) -> usize {
        self.grid
            .iter()
            .enumerate()
            .filter(|&(i, &is_occupied)| is_occupied && self.cell_accessible(i))
            .count()
    }

    fn remove_accessible(&mut self) -> Option<usize> {
        let removables = self
            .grid
            .iter()
            .enumerate()
            .filter_map(|(i, &is_occupied)| (is_occupied && self.cell_accessible(i)).then_some(i))
            .collect::<Vec<_>>();

        let count = removables.len();
        if count > 0 {
            for idx in removables {
                self.grid[idx] = false;
            }
            Some(count)
        } else {
            None
        }
    }

    fn remove_recursive(&mut self) -> usize {
        let mut total_removed = 0;
        while let Some(removed) = self.remove_accessible() {
            total_removed += removed;
        }
        total_removed
    }
}

::: spoiler Full code

 rust

    
use std::{fs, str::FromStr};

use color_eyre::eyre::{Report, Result};

#[derive(Debug, Copy, Clone)]
enum Direction {
    N, NE, E, SE, S, SW, W, NW,
}

impl Direction {
    const ALL: [Direction; 8] = [
        Direction::N,
        Direction::NE,
        Direction::E,
        Direction::SE,
        Direction::S,
        Direction::SW,
        Direction::W,
        Direction::NW,
    ];
}

#[derive(Debug, PartialEq, Eq, Clone)]
struct Grid {
    grid: Vec<bool>,
    width: usize,
    height: usize,
}

impl FromStr for Grid {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let grid: Vec<_> = s
            .chars()
            .filter_map(|ch| match ch {
                '.' => Some(false),
                '@' => Some(true),
                '\n' => None,
                _ => panic!("Invalid input"),
            })
            .collect();
        let width = s
            .chars()
            .position(|ch| ch == '\n')
            .ok_or_else(|| Report::msg("grid width cannot be zero, or one line"))?;
        let height = grid.len() / width;
        Ok(Self {
            grid,
            width,
            height,
        })
    }
}

impl Grid {
    fn neighbour(&self, i: usize, dir: Direction) -> Option<bool> {
        let width = self.width;
        let length = self.grid.len();

        use Direction::*;
        match dir {
            N if i >= width => Some(i - width),
            NE if i >= width && i % width != width - 1 => Some(i - width + 1),
            E if i % width != width - 1 => Some(i + 1),
            SE if i + width + 1 < length && i % width != width - 1 => Some(i + width + 1),
            S if i + width < length => Some(i + width),
            SW if i + width - 1 < length && !i.is_multiple_of(width) => Some(i + width - 1),
            W if !i.is_multiple_of(width) => Some(i - 1),
            NW if i >= width && !i.is_multiple_of(width) => Some(i - width - 1),
            _ => None,
        };
        .map(|i| self.grid[i])
    }

    #[rustfmt::skip]
    fn cell_accessible(&self, i: usize) -> bool {
        Direction::ALL
            .iter()
            .filter(|&&dir| self.neighbour(i, dir).unwrap_or(false))
            .count() < 4
    }

    fn num_accessible(&self) -> usize {
        self.grid
            .iter()
            .enumerate()
            .filter(|&(i, &is_occupied)| is_occupied && self.cell_accessible(i))
            .count()
    }

    fn remove_accessible(&mut self) -> Option<usize> {
        let removables = self
            .grid
            .iter()
            .enumerate()
            .filter_map(|(i, &is_occupied)| (is_occupied && self.cell_accessible(i)).then_some(i))
            .collect::<Vec<_>>();

        let count = removables.len();
        if count > 0 {
            for idx in removables {
                self.grid[idx] = false;
            }
            Some(count)
        } else {
            None
        }
    }

    fn remove_recursive(&mut self) -> usize {
        let mut total_removed = 0;
        while let Some(removed) = self.remove_accessible() {
            total_removed += removed;
        }
        total_removed
    }
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let grid = Grid::from_str(&input)?;
    Ok(grid.num_accessible())
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let mut grid = Grid::from_str(&input)?;
    Ok(grid.remove_recursive())
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("d04/input.txt")?);
    println!("Part 2: {}", part2("d04/input.txt")?);
    Ok(())
}

My version used strings as well, and I thought that as I was comparing small integers either way, it made sense to stay in ASCII as the strings were already easy to index, and it meant I could skip parsing input numbers, only needing to parse output numbers so they could be summed.

I did start with numbers so I could convert it back to compare, but it's so fast (the whole thing takes 1ms - and that's reading/parsing the input twice) that it's almost a micro benchmark.

Rust

My first version worked with numbers, but since I was still sick of yesterday's pow(10) calls, I changed it to use ascii for the second half - the nice thing is that means it can work with hex input with no modification!

Clippy was complaining about "needless_range_loops", but it's way more readable this way.

 rust

    
struct PowerSource(Vec<Bank>);

impl FromStr for PowerSource {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self> {
        let banks = s.lines().map(|l| Bank(l.to_owned())).collect();
        Ok(Self(banks))
    }
}

impl PowerSource {
    fn max_joltage(&self, num_digits: usize) -> usize {
        self.0.iter().map(|b| b.max_joltage(num_digits)).sum()
    }
}

struct Bank(String);

impl Bank {
    fn max_joltage(&self, num_digits: usize) -> usize {
        let batts = self.0.as_bytes();

        let mut digits = vec![b'0'; num_digits];
        let mut start = 0;
        for d in 0..num_digits {
            for i in start..=batts.len() - num_digits + d {
                if batts[i] > digits[d] {
                    digits[d] = batts[i];
                    start = i + 1;
                }
            }
        }

        usize::from_str(str::from_utf8(&digits).unwrap()).unwrap()
    }
}

Maybe? There's some deep wizardry shown in some people's macros so a regex feels fairly basic in comparison.

Every so often I look for a library that will compile the regex at compile time - iirc, there's some stuff needing to made const fn before that can happen.

Last time I used regex, lazy_static was the way to go; I assume that regex can go in OnceCell nowadays.

Another day where the dumb way would have so much quicker and easier, but I'm not competing for time.

I decided to solve it numerically without regex or using to_string(), which was more taxing for the ol' grey matter but is perhaps fairly optimal (if I bothered to pre-compute all those pow() calls, anyway).

Part 2 runs in 35ms (on my AMD Ryzen 7 9800X3D), whereas the to_string() version runs in 40ms. So... not really worth it, and it's less readable.

Rust

 rust

    
use std::fs;

use color_eyre::eyre::{Result, bail};

type InvalidChecker = fn(usize) -> bool;

fn sum_invalids(input: &str, checkfn: InvalidChecker) -> Result<usize> {
    let total = input
        .trim()
        .split(',')
        .map(|idrange| {
            if let Some((start, end)) = idrange.split_once('-') {
                let mut sum = 0;
                for n in start.parse::<usize>()?..=end.parse::<usize>()? {
                    if checkfn(n) {
                        sum += n;
                    }
                }
                Ok(sum)
            } else {
                bail!("Couldn't parse {idrange}")
            }
        })
        .sum::<Result<usize, _>>()?;
    Ok(total)
}

fn is_invalid_p1(n: usize) -> bool {
    let len = n.ilog10() + 1;
    // odd-length numbers can't repeat
    if len % 2 == 1 {
        return false;
    }

    let lhs = n / 10_usize.pow(len / 2);
    let rhs = n - (lhs * 10_usize.pow(len / 2));
    lhs == rhs
}

const SPANS: &[&[u32]] = &[
    &[],              // i = 0
    &[],              // i = 1
    &[1],             // i = 2
    &[1],             // i = 3
    &[1, 2],          // i = 4
    &[1],             // i = 5
    &[1, 2, 3],       // i = 6
    &[1],             // i = 7
    &[1, 2, 4],       // i = 8
    &[1, 3],          // i = 9
    &[1, 2, 5],       // i = 10
    &[1],             // i = 11
    &[1, 2, 3, 4, 6], // i = 12
];

fn is_invalid_p2(n: usize) -> bool {
    let len = n.ilog10() + 1;
    // 1-length numbers can't repeat
    if len == 1 {
        return false;
    }

    SPANS[len as usize].iter().any(|&span| {
        let lhs = n / 10_usize.pow(len - span);
        let mut remainder = n;
        let mut rhs = lhs;
        (2..=(len / span)).all(|i| {
            remainder -= rhs * 10_usize.pow(len - (i - 1) * span);
            rhs = remainder / 10_usize.pow(len - i * span);
            lhs == rhs
        })
    })
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let res = sum_invalids(&input, is_invalid_p1)?;
    Ok(res)
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let res = sum_invalids(&input, is_invalid_p2)?;
    Ok(res)
}

to_string version:

 rust

    
fn is_invalid_p2(n: usize) -> bool {
    let s = n.to_string();
    let len = s.len();
    // 1-length numbers can't repeat
    if len == 1 {
        return false;
    }

    SPANS[len].iter().any(|&span| {
        let span = span as usize;
        let lhs = &s[0..span].as_bytes();
        s.as_bytes().chunks(span).all(|rhs| *lhs == rhs)
    })
}

Brute forcing it like this was my first thought - like they say: if it's stupid and it works, it's not stupid.

Rust

 rust

    
use std::{cmp::Ordering, fs, str::FromStr};

use color_eyre::eyre::{Result, bail};

const DIAL_NUMBERS: isize = 100;

#[derive(Clone, Copy)]
struct Dial(usize);

impl Dial {
    fn new() -> Self {
        Self(50)
    }

    fn rotate(&mut self, rot: isize) -> usize {
        let pass_0s;

        let total = rot.wrapping_add_unsigned(self.0);
        match total.cmp(&0) {
            Ordering::Equal => {
                pass_0s = 1;
                self.0 = 0;
            }
            Ordering::Less => {
                // Starting on 0 means we don't cross it
                let started_0 = if self.0 == 0 { 1 } else { 0 };
                pass_0s = 1 + (-total / DIAL_NUMBERS) as usize - started_0;
                self.0 = (self.0 as isize + rot).rem_euclid(DIAL_NUMBERS) as usize;
            }
            Ordering::Greater => {
                let full_turns = total / DIAL_NUMBERS;
                pass_0s = full_turns as usize;
                self.0 = (total - DIAL_NUMBERS * full_turns) as usize;
            }
        };

        pass_0s
    }

    fn sequence(&mut self, s: &str) -> Result<(usize, usize)> {
        let mut end_0s = 0;
        let mut pass_0s = 0;

        for l in s.lines() {
            let num = isize::from_str(&l[1..]).unwrap();
            let dir = l.bytes().next().unwrap();
            pass_0s += match dir {
                b'L' => self.rotate(-num),
                b'R' => self.rotate(num),
                _ => bail!("b{dir} is an invalid rotation direction"),
            };
            if self.0 == 0 {
                end_0s += 1;
            }
        }

        Ok((end_0s, pass_0s))
    }
}

fn parts(filepath: &str) -> Result<(usize, usize)> {
    let input = fs::read_to_string(filepath)?;
    let mut dial = Dial::new();
    let res = dial.sequence(&input)?;
    Ok(res)
}

fn main() -> Result<()> {
    color_eyre::install()?;

    let (p1, p2) = parts("d01/input.txt")?;
    println!("Part 1: {p1}");
    println!("Part 2: {p2}");
    Ok(())
}

I lost a lot of time struggling with edge cases in part two since I thought it was wasteful to run rem_euclid() (i.e. modulus) when I'd already got the information to do it more efficiently. While I got there in the end my final code was a bit ugly. This prettier, "unoptimised" version runs in 1.6ms, so I was being an idiot.

The thing I couldn't comprehend was where 1000000000050 had come from.

I'm far from sure I understand what you're doing in part 2, but I think maybe you hit the same logic bug I did (I solved it with a shameful if statement that I will have to fix later).

    	// this is bollocks, delete it

That's almost certainly from a Brit.

    		// this looks like I'm being a fancy arsehole, but this is all because  
	// the window shows up white for some reason when first opened, and this  
	// disguises it.

Could be either.

chefkiss.png

Deebster

@ Deebster @programming.dev

Posts

53
Comments

877
Joined

2 yr. ago

New account since lemmyrs.org went down, other `@Deebster`s are available.

Deebster

👪 - 2025 DAY 7 SOLUTIONS - 👪

QIR (Quantum Intermediate Representation)

💃 - 2025 DAY 6 SOLUTIONS - 💃

💃 - 2025 DAY 6 SOLUTIONS - 💃

💃 - 2025 DAY 6 SOLUTIONS - 💃

nushell

line noise

🎄 - 2025 DAY 5 SOLUTIONS - 🎄

Rust

🎄 - 2025 DAY 4 SOLUTIONS - 🎄

🎄 - 2025 DAY 4 SOLUTIONS - 🎄

🎄 - 2025 DAY 4 SOLUTIONS - 🎄

Rust

💃 - 2025 DAY 3 SOLUTIONS - 💃

💃 - 2025 DAY 3 SOLUTIONS - 💃

Rust

🧑 - 2025 DAY 2 SOLUTIONS - 🧑

🧑 - 2025 DAY 2 SOLUTIONS - 🧑

🧑 - 2025 DAY 2 SOLUTIONS - 🧑

Rust

🔒 - 2025 DAY 1 SOLUTIONS -🔒

🔒 - 2025 DAY 1 SOLUTIONS -🔒

Rust

🔒 - 2025 DAY 1 SOLUTIONS -🔒

🔒 - 2025 DAY 1 SOLUTIONS -🔒

S&Box went open-source and the comments are very calm

Amyl and the Sniffers shout Melbourne live music venues $35k in free drinks after gig cancelled