Ask vague questions, get oddly specific answers, I guess.

https://www.youtube.com/watch?v=laZpTO7IFtA is worth the 15 minutes, but the TL;DW is that the kids are just using it as an in-joke marker (i.e. the phrase is a shibboleth), but its origin is in lyrics* by the rapper Skrilla referring to police codes for a dead body.

* are rapped words lyrics?

nushell

I'm still travelling, so another phone attempt. Jet lag says sleep, so just part 1 for now:

nu

    
def part1 [filename: string] {
  mut input = open $filename | lines |
    each { parse '{index}: {children}' | update children { split row " " } | first } |
    insert paths { null }
  print $"Data loaded, ($input | length) devices"

  $input = explore-path $input you
  $input | where index == you | get 0.paths
}

def explore-path [devices, start: string] {
  print $"Exploring ($start)"
  let dev = $devices | where index == $start | first
  if ($dev | get paths) != null {
    print "Already explored"
    return $devices
  }

  # Shadow with mutable version
  mut devices = $devices
  mut paths = 0
  let is_out = $dev | get children | where ($it == out) | is-not-empty
  if $is_out {
    print $"Found an out device: ($start)"
    $paths = 1
  } else {
    for child in ($dev | get children ) {
      $devices = explore-path $devices $child
      $paths += $devices | where index == $child | get 0.paths
    }
  }

  # Shadow with immutable... wtf
  let paths = $paths
  print $"Setting paths for ($start) to ($paths)"
  $devices = $devices | update paths { |row| if $row.index == $start {  
$paths } else {} }
   $devices
}

Firefox does seem to be clearing out their old bugs (another example is MKV support) but perhaps it's buses arriving together and not due to some policy.

I can't code today because of travel, just as the one that might run slow enough to geek out on benchmarking the various options. Does seem like it's a bit of a jump in difficulty from previous days.

We’re still preparing the notes for this release, and will post them here when they are ready. Please check back later.

Oh come on guys

edit: they're up now

That is surprising about Firefox - you'd have thought something that literally just runs JavaScript would be able to beat Firefox with all the UI, sandboxing, etc. 30% is a huge margin.

For part one and likely part 2 you don't need to do all 499500 comparisons, you could split the grid into boxes and only search adjacent ones. E.g. z / 10 = which decile and look at z, z-1, z+1 (and the same for x and y). Less work for the processor, more work for you, and of course, sqrt (which you can also probably skip) is so efficient on modern chips that the overhead of this eats a chunk of the benefits (depending on how low-level your language is).

Rust

Part 1 took a decent while, partly life getting in the way, partly as I was struggling with some Rust things like floats not being sortable without mucking around, plus some weird bugs trying to get collect to do everything that I eventually just rewrote to avoid.

I found the noisy_float crate which let me wrap f64 as a "real" r64 which meant no NaN which meant Ord which meant sort_by_cached_key() and the rest worked.

I'd planned how to partition the closest neighbour search, but the whole thing runs in 24ms so I didn't bother.

other types

 rust

    
type Id = usize;
type Connection = (Id, Id);
type Circuit = HashSet<Id>;

#[derive(PartialEq)]
struct Point {
    x: usize,
    y: usize,
    z: usize,
}

impl FromStr for Point {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self> {
        let mut parts = s.split(',');
        Ok(Point {
            x: parts.next().ok_or_eyre("missing x")?.parse()?,
            y: parts.next().ok_or_eyre("missing y")?.parse()?,
            z: parts.next().ok_or_eyre("missing z")?.parse()?,
        })
    }
}

impl Point {
    fn distance(&self, other: &Point) -> R64 {
        let dist = ((
            self.x.abs_diff(other.x).pow(2) +
            self.y.abs_diff(other.y).pow(2) +
            self.z.abs_diff(other.z).pow(2)) as f64)
            .sqrt();
        r64(dist)
    }
}

 rust

    
struct Boxes(Vec<Point>);

impl Boxes {
    fn closest(&self) -> Vec<Connection> {
        let mut closest = (0..self.0.len())
            .flat_map(|a| ((a + 1)..self.0.len()).map(move |b| (a, b)))
            .collect::<Vec<_>>();

        closest.sort_by_cached_key(|&(a, b)| self.0[a].distance(&self.0[b]));
        closest
    }

    fn connect_all(&self, p1_threshold: usize) -> Result<(usize, usize)> {
        let mut circuits: Vec<Circuit> = (0..self.0.len())
            .map(|id| HashSet::from_iter(iter::once(id)))
            .collect();

        let mut closest = self.closest().into_iter();
        let mut p1 = 0;
        let mut n = 0;
        loop {
            n += 1;
            let (a, b) = closest.next().ok_or_eyre("All connected already")?;
            let a_circ = circuits.iter().position(|c| c.contains(&a));
            let b_circ = circuits.iter().position(|c| c.contains(&b));
            match (a_circ, b_circ) {
                (None, None) => {
                    circuits.push(vec![a, b].into_iter().collect());
                }
                (None, Some(idx)) => {
                    circuits[idx].insert(a);
                }
                (Some(idx), None) => {
                    circuits[idx].insert(b);
                }
                (Some(a_idx), Some(b_idx)) if a_idx != b_idx => {
                    let keep_idx = a_idx.min(b_idx);
                    let rem_idx = a_idx.max(b_idx);

                    let drained = circuits.swap_remove(rem_idx);
                    // this position is still valid since we removed the later set
                    circuits[keep_idx].extend(drained);
                }
                _ => { /* already connected to same circuit */ }
            };

            if n == p1_threshold {
                circuits.sort_by_key(|set| set.len());
                circuits.reverse();
                p1 = circuits.iter().take(3).map(|set| set.len()).product();
            }
            if circuits.len() == 1 {
                let p2 = self.0[a].x * self.0[b].x;
                return Ok((p1, p2));
            }
        }
    }
}

I normally use the "most appropriate" size, but this year I'm just using usize everywhere and it's a lot more fun. So far I haven't found any problem where it ran too slow and the problem was in my implementation and not my algorithm choice.

Ah, it took me looking at your updated Codeberg version to understand this - you looked at part two in the opposite way than I did but it comes out the same in the end (and yours is much more efficient).

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.

Deebster

@ Deebster @programming.dev

Posts

58
Comments

1028
Joined

3 yr. ago

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

Deebster

What don't you need?

JD Vance is sick of 67: ‘Ban these numbers forever’

🧦 - 2025 DAY 11 SOLUTIONS - 🧦

nushell

Firefox 147 Promises Support for the XDG Base Directory Specification, Beta Out Now

Firefox 147 Promises Support for the XDG Base Directory Specification, Beta Out Now

[2025 Day 9] When you wake up and see lots of grey stars

Firefox 146.0 Release Notes

🎁 - 2025 DAY 9 SOLUTIONS - 🎁

[2025 Day 8] Fan go brrrrr

🤶 - 2025 DAY 8 SOLUTIONS - 🤶

Rust

[2025 Day 7] As long as the result is positive, it can't have overflown, right?

👪 - 2025 DAY 7 SOLUTIONS - 👪

👪 - 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 - 🎄