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).
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.
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
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.
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
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).
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
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.