Glad to be able to help. This one really was a doozy.
Gobbel2000
joined 10 months ago
Rust
Nice breather today (still traumatized from the robots). At some point I thought you had to do some magic for predicting special properties of the pseudorandom function, but no, just collect all values, have a big table for all sequences and in the end take the maximum value in that table. Part 1 takes 6.7ms, part 2 19.2ms.
Solution
fn step(n: u32) -> u32 {
let a = (n ^ (n << 6)) % (1 << 24);
let b = a ^ (a >> 5);
(b ^ (b << 11)) % (1 << 24)
}
fn part1(input: String) {
let sum = input
.lines()
.map(|l| {
let n = l.parse().unwrap();
(0..2000).fold(n, |acc, _| step(acc)) as u64
})
// More than 2ยนโฐ 24-bit numbers requires 35 bits
.sum::<u64>();
println!("{sum}");
}
const N_SEQUENCES: usize = 19usize.pow(4);
fn sequence_key(sequence: &[i8]) -> usize {
sequence
.iter()
.enumerate()
.map(|(i, x)| (x + 9) as usize * 19usize.pow(i as u32))
.sum()
}
fn part2(input: String) {
// Table for collecting the amount of bananas for every possible sequence
let mut table = vec![0; N_SEQUENCES];
// Mark the sequences we encountered in a round to ensure that only the first occurence is used
let mut seen = vec![false; N_SEQUENCES];
for l in input.lines() {
let n = l.parse().unwrap();
let (diffs, prices): (Vec<i8>, Vec<u8>) = (0..2000)
.scan(n, |acc, _| {
let next = step(*acc);
let diff = (next % 10) as i8 - (*acc % 10) as i8;
*acc = next;
Some((diff, (next % 10) as u8))
})
.unzip();
for (window, price) in diffs.windows(4).zip(prices.iter().skip(3)) {
let key = sequence_key(window);
if !seen[key] {
seen[key] = true;
table[key] += *price as u32;
}
}
// Reset seen sequences for next round
seen.fill(false);
}
let bananas = table.iter().max().unwrap();
println!("{bananas}");
}
util::aoc_main!();
Also on github
Rust
For me this was the hardest puzzle so far this year. First I did a bunch of things that turned out not to work properly. For example I tried to solve it with a greedy algorithm that always moved horizontally first then vertically, but that ignores the gaps that need to be avoided (what a sneaky requirement) and also somehow doesn't guarantee the shortest sequence.
After reaching part 2 it became clear that a recursive function (with memoization) is needed again, and of course in the end it turned out a lot simpler than what I had cooked up before (you don't want to see that). Now even part 2 takes just 1.6ms.
Solution
use euclid::{default::*, point2, vec2};
use rustc_hash::FxHashMap;
use std::iter;
type Move = Option<Vector2D<i32>>;
const KEYPAD_GAP: Point2D<i32> = point2(0, 3);
const DPAD_GAP: Point2D<i32> = point2(0, 0);
fn keypad_pos(n: u8) -> Point2D<i32> {
match n {
b'7' => point2(0, 0),
b'8' => point2(1, 0),
b'9' => point2(2, 0),
b'4' => point2(0, 1),
b'5' => point2(1, 1),
b'6' => point2(2, 1),
b'1' => point2(0, 2),
b'2' => point2(1, 2),
b'3' => point2(2, 2),
b'0' => point2(1, 3),
b'A' => point2(2, 3),
other => panic!("Invalid keypad symbol {other}"),
}
}
// `None` is used for A
fn dpad_pos(d: Move) -> Point2D<i32> {
match d {
Some(Vector2D { x: 0, y: -1, .. }) => point2(1, 0),
None => point2(2, 0),
Some(Vector2D { x: -1, y: 0, .. }) => point2(0, 1),
Some(Vector2D { x: 0, y: 1, .. }) => point2(1, 1),
Some(Vector2D { x: 1, y: 0, .. }) => point2(2, 1),
other => panic!("Invalid dpad symbol {other:?}"),
}
}
fn moves_for_diff(diff: Vector2D<i32>, pos: Point2D<i32>, gap: Point2D<i32>) -> Vec<Vec<Move>> {
let horizontal = iter::repeat_n(
Some(vec2(diff.x.signum(), 0)),
diff.x.unsigned_abs() as usize,
);
let vertical = iter::repeat_n(
Some(vec2(0, diff.y.signum())),
diff.y.unsigned_abs() as usize,
);
if pos + vec2(diff.x, 0) == gap {
// Must not move horizontal first, or we hit the gap
vec![vertical.chain(horizontal).chain(iter::once(None)).collect()]
} else if pos + vec2(0, diff.y) == gap {
vec![horizontal.chain(vertical).chain(iter::once(None)).collect()]
} else {
// Try both horizontal first and vertical first
vec![
horizontal
.clone()
.chain(vertical.clone())
.chain(iter::once(None))
.collect(),
vertical.chain(horizontal).chain(iter::once(None)).collect(),
]
}
}
fn dpad_sequence_len(
start: Move,
end: Move,
rounds: u32,
cache: &mut FxHashMap<(Move, Move, u32), u64>,
) -> u64 {
if rounds == 0 {
return 1;
}
if let Some(len) = cache.get(&(start, end, rounds)) {
return *len;
}
let start_pos = dpad_pos(start);
let end_pos = dpad_pos(end);
let diff = end_pos - start_pos;
let possible_paths = moves_for_diff(diff, start_pos, DPAD_GAP);
let shortest_sequence = possible_paths
.iter()
.map(|moves| {
moves
.iter()
.fold((0, None), |(cost, prev), &m| {
(cost + dpad_sequence_len(prev, m, rounds - 1, cache), m)
})
.0
})
.min()
.unwrap();
cache.insert((start, end, rounds), shortest_sequence);
shortest_sequence
}
fn keypad_sequence_len(start: u8, end: u8, rounds: u32) -> u64 {
let start_pos = keypad_pos(start);
let end_pos = keypad_pos(end);
let diff = end_pos - start_pos;
let possible_paths = moves_for_diff(diff, start_pos, KEYPAD_GAP);
let mut cache = FxHashMap::default();
possible_paths
.iter()
.map(|moves| {
moves
.iter()
.fold((0, None), |(cost, prev), &m| {
(cost + dpad_sequence_len(prev, m, rounds, &mut cache), m)
})
.0
})
.min()
.unwrap()
}
fn solve(input: &str, rounds: u32) -> u64 {
let mut sum: u64 = 0;
for l in input.lines() {
let mut prev = b'A';
let mut len = 0;
for b in l.bytes() {
len += keypad_sequence_len(prev, b, rounds);
prev = b;
}
let code_n: u64 = l.strip_suffix('A').unwrap().parse().unwrap();
sum += code_n * len;
}
sum
}
fn part1(input: String) {
println!("{}", solve(&input, 2));
}
fn part2(input: String) {
println!("{}", solve(&input, 25));
}
util::aoc_main!();
Also on github
There is exactly one path without cheating, so yes, the distance to one end is always the total distance minus the distance to the other end.
Rust
The important part here is to build two maps first that hold for every point on the path the distance to the start and the distance to the end respectively. Then calculating the path length for a cheat vector is a simple lookup. For part 2 I first generated all vectors with manhattan distance <= 20, or more specifically, exactly half of those vectors to avoid checking the same vector in both directions.
Part 2 takes 15ms. The code looks a bit unwieldy at parts and uses the pyramid of doom paradigm but works pretty well.
Solution
use euclid::{default::*, vec2};
const DIRS: [Vector2D<i32>; 4] = [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)];
const MIN_SAVE: u32 = 100;
const MAX_DIST: i32 = 20;
fn parse(input: &str) -> (Vec<Vec<bool>>, Point2D<i32>, Point2D<i32>) {
let mut start = None;
let mut end = None;
let mut field = Vec::new();
for (y, line) in input.lines().enumerate() {
let mut row = Vec::new();
for (x, b) in line.bytes().enumerate() {
row.push(b == b'#');
if b == b'S' {
start = Some(Point2D::new(x, y).to_i32());
} else if b == b'E' {
end = Some(Point2D::new(x, y).to_i32());
}
}
field.push(row);
}
(field, start.unwrap(), end.unwrap())
}
fn distances(
field: &[Vec<bool>],
start: Point2D<i32>,
end: Point2D<i32>,
) -> (Vec<Vec<u32>>, Vec<Vec<u32>>) {
let width = field[0].len();
let height = field.len();
let mut dist_to_start = vec![vec![u32::MAX; width]; height];
let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height)).to_i32();
let mut cur = start;
let mut dist = 0;
dist_to_start[cur.y as usize][cur.x as usize] = dist;
while cur != end {
for dir in DIRS {
let next = cur + dir;
if bounds.contains(next)
&& !field[next.y as usize][next.x as usize]
&& dist_to_start[next.y as usize][next.x as usize] == u32::MAX
{
cur = next;
break;
}
}
dist += 1;
dist_to_start[cur.y as usize][cur.x as usize] = dist;
}
let total_dist = dist_to_start[end.y as usize][end.x as usize];
let dist_to_end = dist_to_start
.iter()
.map(|row| {
row.iter()
.map(|&d| {
if d == u32::MAX {
u32::MAX
} else {
total_dist - d
}
})
.collect()
})
.collect();
(dist_to_start, dist_to_end)
}
fn cheats(
field: &[Vec<bool>],
dist_to_start: &[Vec<u32>],
dist_to_end: &[Vec<u32>],
total_dist: u32,
) -> u32 {
let width = field[0].len();
let height = field.len();
let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height)).to_i32();
let mut count = 0;
for (y, row) in field.iter().enumerate() {
for (x, _w) in row.iter().enumerate().filter(|&(_i, w)| *w) {
let pos = Point2D::new(x, y).to_i32();
for (d0, &dir0) in DIRS.iter().enumerate().skip(1) {
for &dir1 in DIRS.iter().take(d0) {
let p0 = pos + dir0;
let p1 = pos + dir1;
if bounds.contains(p0) && bounds.contains(p1) {
let p0 = p0.to_usize();
let p1 = p1.to_usize();
if !field[p0.y][p0.x] && !field[p1.y][p1.x] {
let dist = dist_to_start[p0.y][p0.x].min(dist_to_start[p1.y][p1.x])
+ dist_to_end[p1.y][p1.x].min(dist_to_end[p0.y][p0.x])
+ 2; // Add 2 for cutting across the wall
if total_dist - dist >= MIN_SAVE {
count += 1;
}
}
}
}
}
}
}
count
}
fn part1(input: String) {
let (field, start, end) = parse(&input);
let (dist_to_start, dist_to_end) = distances(&field, start, end);
let total_dist = dist_to_start[end.y as usize][end.x as usize];
println!(
"{}",
cheats(&field, &dist_to_start, &dist_to_end, total_dist)
);
}
// Half of all vectors with manhattan distance <= MAX_DIST.
// Only vectors with positive x or going straight down are considered to avoid using the same
// vector twice in both directions.
fn cheat_vectors() -> Vec<Vector2D<i32>> {
let mut vectors = Vec::new();
for y in -MAX_DIST..=MAX_DIST {
let start = if y > 0 { 0 } else { 1 };
for x in start..=(MAX_DIST - y.abs()) {
assert!(x + y <= MAX_DIST);
vectors.push(vec2(x, y));
}
}
vectors
}
fn cheats20(
field: &[Vec<bool>],
dist_to_start: &[Vec<u32>],
dist_to_end: &[Vec<u32>],
total_dist: u32,
) -> u32 {
let vectors = cheat_vectors();
let width = field[0].len();
let height = field.len();
let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height)).to_i32();
let mut count = 0;
for (y, row) in field.iter().enumerate() {
for (x, _w) in row.iter().enumerate().filter(|&(_i, w)| !*w) {
let p0 = Point2D::new(x, y);
for &v in &vectors {
let pi1 = p0.to_i32() + v;
if bounds.contains(pi1) {
let p1 = pi1.to_usize();
if !field[p1.y][p1.x] {
let dist = dist_to_start[p0.y][p0.x].min(dist_to_start[p1.y][p1.x])
+ dist_to_end[p1.y][p1.x].min(dist_to_end[p0.y][p0.x])
+ v.x.unsigned_abs() // Manhattan distance of vector
+ v.y.unsigned_abs();
if total_dist - dist >= MIN_SAVE {
count += 1;
}
}
}
}
}
}
count
}
fn part2(input: String) {
let (field, start, end) = parse(&input);
let (dist_to_start, dist_to_end) = distances(&field, start, end);
let total_dist = dist_to_start[end.y as usize][end.x as usize];
println!(
"{}",
cheats20(&field, &dist_to_start, &dist_to_end, total_dist)
);
}
util::aoc_main!();
Also on github
Writing the same number a different way does not make it rational. There are no two natural numbers p and q so that p/q = 1 base pi.
The 3ms are for part 1 only, part 2 takes around 27ms. But I see that our approaches there are very similar. One difference that might make an impact is that you copy the substrings for inserting into the hashmap into Strings.
About 3ms. A manual implementation might be a bit faster, but not by much. The regex crate is quite optimized for pretty much these problems.
Rust
First part is solved by making a regex of the available towels, like ^(r|wr|bg|bwu|rb|gb|br)*$ for the example. If a design matches it, then it can be made. This didn't work for the second part, which is done using recursion and memoization instead. Again, it was quite surprising to see such a high solution number. 32 bits were not enough (thanks, debug mode overflow detection).
Solution
use regex::Regex;
use rustc_hash::FxHashMap;
fn parse(input: &str) -> (Vec<&str>, Vec<&str>) {
let (towels, designs) = input.split_once("\n\n").unwrap();
(towels.split(", ").collect(), designs.lines().collect())
}
fn part1(input: String) {
let (towels, designs) = parse(&input);
let pat = format!("^({})*$", towels.join("|"));
let re = Regex::new(&pat).unwrap();
let count = designs.iter().filter(|d| re.is_match(d)).count();
println!("{count}");
}
fn n_arrangements<'a>(
design: &'a str,
towels: &[&str],
cache: &mut FxHashMap<&'a str, u64>,
) -> u64 {
if design.is_empty() {
return 1;
}
if let Some(n) = cache.get(design) {
return *n;
}
let n = towels
.iter()
.filter(|t| design.starts_with(*t))
.map(|t| n_arrangements(&design[t.len()..], towels, cache))
.sum();
cache.insert(design, n);
n
}
fn part2(input: String) {
let (towels, designs) = parse(&input);
let sum: u64 = designs
.iter()
.map(|d| n_arrangements(d, &towels, &mut FxHashMap::default()))
.sum();
println!("{sum}");
}
util::aoc_main!();
Also on github
Rust
Naive approach running BFS after every dropped byte after 1024. Still runs in 50ms. This could be much optimized by using binary search to find the first blocked round and using A* instead of BFS, but I didn't feel like doing more today.
Solution
use std::collections::VecDeque;
use euclid::{default::*, vec2};
fn parse(input: &str) -> Vec<Point2D<i32>> {
input
.lines()
.map(|l| {
let (x, y) = l.split_once(',').unwrap();
Point2D::new(x.parse().unwrap(), y.parse().unwrap())
})
.collect()
}
const BOUNDS: Rect<i32> = Rect::new(Point2D::new(0, 0), Size2D::new(71, 71));
const START: Point2D<i32> = Point2D::new(0, 0);
const TARGET: Point2D<i32> = Point2D::new(70, 70);
const N_BYTES: usize = 1024;
const DIRS: [Vector2D<i32>; 4] = [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)];
fn adj(
field: &[[bool; BOUNDS.size.width as usize]],
v: Point2D<i32>,
) -> impl Iterator<Item = Point2D<i32>> + use<'_> {
DIRS.iter()
.map(move |&d| v + d)
.filter(|&next| BOUNDS.contains(next) && !field[next.y as usize][next.x as usize])
}
fn find_path(field: &[[bool; BOUNDS.size.width as usize]]) -> Option<u32> {
let mut seen = [[false; BOUNDS.size.width as usize]; BOUNDS.size.height as usize];
let mut q = VecDeque::from([(START, 0)]);
seen[START.y as usize][START.x as usize] = true;
while let Some((v, dist)) = q.pop_front() {
for w in adj(field, v) {
if w == TARGET {
return Some(dist + 1);
}
if !seen[w.y as usize][w.x as usize] {
seen[w.y as usize][w.x as usize] = true;
q.push_back((w, dist + 1));
}
}
}
None
}
fn part1(input: String) {
let bytes = parse(&input);
let mut field = [[false; BOUNDS.size.width as usize]; BOUNDS.size.height as usize];
for b in &bytes[..N_BYTES] {
field[b.y as usize][b.x as usize] = true;
}
println!("{}", find_path(&field).unwrap());
}
fn part2(input: String) {
let bytes = parse(&input);
let mut field = [[false; BOUNDS.size.width as usize]; BOUNDS.size.height as usize];
for (i, b) in bytes.iter().enumerate() {
field[b.y as usize][b.x as usize] = true;
// We already know from part 1 that below N_BYTES there is a path
if i > N_BYTES && find_path(&field).is_none() {
println!("{},{}", b.x, b.y);
break;
}
}
}
util::aoc_main!();
Also on github
Rust
First part was straightforward (the divisions are actually just right shifts), second part not so much. I made some assumptions about the input program, namely that in the end register 8 is divided by 8, then an output is made, then everything starts from the beginning again (if a isn't 0). I found that the output always depends on at most 10 bits of a, so I ran through all 10-bit numbers and grouped them by the first generated output. At that point it's just a matter of chaining these 10-bit numbers from the correct groups so that they overlap on 7 bits. The other 3 bits are consumed each round.
Solution
use rustc_hash::FxHashMap;
fn parse(input: &str) -> Option<Program> {
let mut lines = input.lines();
let a = lines.next()?.split_once(": ")?.1.parse().ok()?;
let b = lines.next()?.split_once(": ")?.1.parse().ok()?;
let c = lines.next()?.split_once(": ")?.1.parse().ok()?;
lines.next()?;
let program = lines
.next()?
.split_once(": ")?
.1
.split(',')
.map(|s| s.parse())
.collect::<Result<Vec<u8>, _>>()
.ok()?;
Some(Program {
a,
b,
c,
out: vec![],
program,
ip: 0,
})
}
#[derive(Debug, Clone, Default)]
struct Program {
a: u64,
b: u64,
c: u64,
out: Vec<u8>,
program: Vec<u8>,
ip: usize,
}
impl Program {
fn run(&mut self) {
while self.step() {}
}
// Returns true if a step was taken, false if it halted
fn step(&mut self) -> bool {
let Some(&[opcode, operand]) = &self.program.get(self.ip..self.ip + 2) else {
return false;
};
self.ip += 2;
match opcode {
0 => self.adv(self.combo(operand)),
1 => self.bxl(operand),
2 => self.bst(self.combo(operand)),
3 => self.jnz(operand),
4 => self.bxc(),
5 => self.out(self.combo(operand)),
6 => self.bdv(self.combo(operand)),
7 => self.cdv(self.combo(operand)),
_ => panic!(),
}
true
}
fn combo(&self, operand: u8) -> u64 {
match operand {
0..=3 => operand as u64,
4 => self.a,
5 => self.b,
6 => self.c,
_ => unreachable!(),
}
}
fn adv(&mut self, x: u64) {
self.a >>= x
}
fn bxl(&mut self, x: u8) {
self.b ^= x as u64
}
fn bst(&mut self, x: u64) {
self.b = x % 8
}
fn jnz(&mut self, x: u8) {
if self.a != 0 {
self.ip = x as usize
}
}
fn bxc(&mut self) {
self.b ^= self.c
}
fn out(&mut self, x: u64) {
self.out.push((x % 8) as u8)
}
fn bdv(&mut self, x: u64) {
self.b = self.a >> x
}
fn cdv(&mut self, x: u64) {
self.c = self.a >> x
}
}
fn part1(input: String) {
let mut program = parse(&input).unwrap();
program.run();
if let Some(e) = program.out.first() {
print!("{e}")
}
for e in program.out.iter().skip(1) {
print!(",{e}")
}
println!()
}
// Some assumptions on the input:
// * There is exactly one jump instruction at the end of the program, jumping to 0
// * Right before that, an output is generated
// * Right before that, register a is shifted right by 3: adv(3)
//
// Each output depends on at most 10 bits of a (it is used with a shift of at most 7).
// Therefore we look at all 10-bit a's and group them by the first number that is output.
// Then we just need to combine these generators into a chain that fits together.
fn number_generators(mut program: Program) -> [Vec<u16>; 8] {
let mut out = [const { vec![] }; 8];
for a in 1..(1 << 10) {
program.a = a as u64;
program.out.clear();
program.ip = 0;
program.run();
let &output = program.out.first().unwrap();
out[output as usize].push(a);
}
out
}
fn part2(input: String) {
let mut program = parse(&input).unwrap();
let generators = number_generators(program.clone());
let output = program.program.clone();
// a_candidates maps from 7-bit required prefixes to the lower bits of a that
// generate the required numbers so far.
let mut a_candidates: FxHashMap<u8, u64> = generators[output[0] as usize]
.iter()
.rev() // Collects the values for each prefix
.map(|&a| ((a >> 3) as u8, a as u64 % 8))
.collect();
let len = output.len();
for (i, x) in output.iter().enumerate().skip(1) {
let mut next_candidates = FxHashMap::default();
for (prefix, val) in generators[*x as usize]
.iter()
.filter(|&a| {
// Take only short candidates in the end to ensure that not too many numbers are generated
let max_bits = (len - i) * 3;
(*a as u64) < (1u64 << max_bits)
})
// Only use generators that match any required prefix
.filter(|&a| a_candidates.contains_key(&((a % (1 << 7)) as u8)))
.map(|&a| {
let prefix = (a >> 3) as u8;
let val = a as u64 % 8;
let prev = a_candidates[&((a % (1 << 7)) as u8)];
(prefix, (val << (i * 3)) | prev)
})
{
// Only insert first (smallest) encountered value
next_candidates.entry(prefix).or_insert(val);
}
a_candidates = next_candidates;
}
println!("{}", a_candidates[&0]);
// Verify result
program.a = a_candidates[&0];
program.run();
assert_eq!(program.out, program.program);
}
util::aoc_main!();
Also on github
Rust
Finding cliques in a graph, which is actually NP-comlete. For part two I did look up how to do it and implemented the Bron-Kerbosch algorithm. Adding the pivoting optimization improved the runtime from 134ms to 7.4ms, so that is definitely worth it (in some sense, of course I already had the correct answer without pivoting).
Solution
Also on github