New account since lemmyrs.org went down, other @Deebsters are available.
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).
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.
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)
}
}
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).
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).
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()?
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.
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
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
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.
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,
})
}
}
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.
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).
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
}
}
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.
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.
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.
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:
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.
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.