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.
Gobbel2000
joined 1 year ago
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
Dijkstra's algorithm can fairly simply be modified to work for part 2. In the relaxation step you just need to also handle the case that the distances of two joining paths are equal.
Rust
Dijkstra's algorithm. While the actual shortest path was not needed in part 1, only the distance, in part 2 the path is saved in the parent hashmap, and crucially, if we encounter two paths with the same distance, both parent nodes are saved. This ensures we end up with all shortest paths in the end.
Solution
use std::cmp::{Ordering, Reverse};
use euclid::{default::*, vec2};
use priority_queue::PriorityQueue;
use rustc_hash::{FxHashMap, FxHashSet};
const DIRS: [Vector2D<i32>; 4] = [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)];
type Node = (Point2D<i32>, u8);
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, l) in input.lines().enumerate() {
let mut row = Vec::new();
for (x, b) in l.bytes().enumerate() {
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());
}
row.push(b == b'#');
}
field.push(row);
}
(field, start.unwrap(), end.unwrap())
}
fn adj(field: &[Vec<bool>], (v, dir): Node) -> Vec<(Node, u32)> {
let mut adj = Vec::with_capacity(3);
let next = v + DIRS[dir as usize];
if !field[next.y as usize][next.x as usize] {
adj.push(((next, dir), 1));
}
adj.push(((v, (dir + 1) % 4), 1000));
adj.push(((v, (dir + 3) % 4), 1000));
adj
}
fn shortest_path_length(field: &[Vec<bool>], start: Node, end: Point2D<i32>) -> u32 {
let mut dist: FxHashMap<Node, u32> = FxHashMap::default();
dist.insert(start, 0);
let mut pq: PriorityQueue<Node, Reverse<u32>> = PriorityQueue::new();
pq.push(start, Reverse(0));
while let Some((v, _)) = pq.pop() {
for (w, weight) in adj(field, v) {
let dist_w = dist.get(&w).copied().unwrap_or(u32::MAX);
let new_dist = dist[&v] + weight;
if dist_w > new_dist {
dist.insert(w, new_dist);
pq.push_increase(w, Reverse(new_dist));
}
}
}
// Shortest distance to end, regardless of final direction
(0..4).map(|dir| dist[&(end, dir)]).min().unwrap()
}
fn part1(input: String) {
let (field, start, end) = parse(&input);
let distance = shortest_path_length(&field, (start, 0), end);
println!("{distance}");
}
fn shortest_path_tiles(field: &[Vec<bool>], start: Node, end: Point2D<i32>) -> u32 {
let mut parents: FxHashMap<Node, Vec<Node>> = FxHashMap::default();
let mut dist: FxHashMap<Node, u32> = FxHashMap::default();
dist.insert(start, 0);
let mut pq: PriorityQueue<Node, Reverse<u32>> = PriorityQueue::new();
pq.push(start, Reverse(0));
while let Some((v, _)) = pq.pop() {
for (w, weight) in adj(field, v) {
let dist_w = dist.get(&w).copied().unwrap_or(u32::MAX);
let new_dist = dist[&v] + weight;
match dist_w.cmp(&new_dist) {
Ordering::Greater => {
parents.insert(w, vec![v]);
dist.insert(w, new_dist);
pq.push_increase(w, Reverse(new_dist));
}
// Remember both parents if distance is equal
Ordering::Equal => parents.get_mut(&w).unwrap().push(v),
Ordering::Less => {}
}
}
}
let mut path_tiles: FxHashSet<Point2D<i32>> = FxHashSet::default();
path_tiles.insert(end);
// Shortest distance to end, regardless of final direction
let shortest_dist = (0..4).map(|dir| dist[&(end, dir)]).min().unwrap();
for dir in 0..4 {
if dist[&(end, dir)] == shortest_dist {
collect_tiles(&parents, &mut path_tiles, (end, dir));
}
}
path_tiles.len() as u32
}
fn collect_tiles(
parents: &FxHashMap<Node, Vec<Node>>,
tiles: &mut FxHashSet<Point2D<i32>>,
cur: Node,
) {
if let Some(pars) = parents.get(&cur) {
for p in pars {
tiles.insert(p.0);
collect_tiles(parents, tiles, *p);
}
}
}
fn part2(input: String) {
let (field, start, end) = parse(&input);
let tiles = shortest_path_tiles(&field, (start, 0), end);
println!("{tiles}");
}
util::aoc_main!();
Also on github
Rust
Part 2 was a bit tricky. Moving into a box horizontally works mostly the same as for part 1, for the vertical case I used two recursive functions. The first recurses from the left and right side for each box just to find out if the entire tree can be moved. The second function actually does the moving in a similar recursive structure, but now with the knowledge that all subtrees can actually be moved.
Lots of moving parts, but at least it could very nicely be debugged by printing out the map from the two minimal examples after each round.
Solution
use euclid::{default::*, vec2};
// Common type for both parts. In part 1 all boxes are BoxL.
#[derive(Clone, Copy)]
enum Spot {
Empty,
BoxL,
BoxR,
Wall,
}
impl From<u8> for Spot {
fn from(value: u8) -> Self {
match value {
b'.' | b'@' => Spot::Empty,
b'O' => Spot::BoxL,
b'#' => Spot::Wall,
other => panic!("Invalid spot: {other}"),
}
}
}
fn parse(input: &str) -> (Vec<Vec<Spot>>, Point2D<i32>, Vec<Vector2D<i32>>) {
let (field_s, moves_s) = input.split_once("\n\n").unwrap();
let mut field = Vec::new();
let mut robot = None;
for (y, l) in field_s.lines().enumerate() {
let mut row = Vec::new();
for (x, b) in l.bytes().enumerate() {
row.push(Spot::from(b));
if b == b'@' {
robot = Some(Point2D::new(x, y).to_i32())
}
}
field.push(row);
}
let moves = moves_s
.bytes()
.filter(|b| *b != b'\n')
.map(|b| match b {
b'^' => vec2(0, -1),
b'>' => vec2(1, 0),
b'v' => vec2(0, 1),
b'<' => vec2(-1, 0),
other => panic!("Invalid move: {other}"),
})
.collect();
(field, robot.unwrap(), moves)
}
fn gps(field: &[Vec<Spot>]) -> u32 {
let mut sum = 0;
for (y, row) in field.iter().enumerate() {
for (x, s) in row.iter().enumerate() {
if let Spot::BoxL = s {
sum += x + 100 * y;
}
}
}
sum as u32
}
fn part1(input: String) {
let (mut field, mut robot, moves) = parse(&input);
for m in moves {
let next = robot + m;
match field[next.y as usize][next.x as usize] {
Spot::Empty => robot = next, // Move into space
Spot::BoxL => {
let mut search = next + m;
let can_move = loop {
match field[search.y as usize][search.x as usize] {
Spot::BoxL => {}
Spot::Wall => break false,
Spot::Empty => break true,
Spot::BoxR => unreachable!(),
}
search += m;
};
if can_move {
robot = next;
field[next.y as usize][next.x as usize] = Spot::Empty;
field[search.y as usize][search.x as usize] = Spot::BoxL;
}
}
Spot::Wall => {} // Cannot move
Spot::BoxR => unreachable!(),
}
}
println!("{}", gps(&field));
}
// Transform part 1 field to wider part 2 field
fn widen(field: &[Vec<Spot>]) -> Vec<Vec<Spot>> {
field
.iter()
.map(|row| {
row.iter()
.flat_map(|s| match s {
Spot::Empty => [Spot::Empty; 2],
Spot::Wall => [Spot::Wall; 2],
Spot::BoxL => [Spot::BoxL, Spot::BoxR],
Spot::BoxR => unreachable!(),
})
.collect()
})
.collect()
}
// Recursively find out whether or not the robot can move in direction `dir` from `start`.
fn can_move_rec(field: &[Vec<Spot>], start: Point2D<i32>, dir: Vector2D<i32>) -> bool {
let next = start + dir;
match field[next.y as usize][next.x as usize] {
Spot::Empty => true,
Spot::BoxL => can_move_rec(field, next, dir) && can_move_rec(field, next + vec2(1, 0), dir),
Spot::BoxR => can_move_rec(field, next - vec2(1, 0), dir) && can_move_rec(field, next, dir),
Spot::Wall => false,
}
}
// Recursively execute a move for vertical directions into boxes.
fn do_move(field: &mut [Vec<Spot>], start: Point2D<i32>, dir: Vector2D<i32>) {
let next = start + dir;
match field[next.y as usize][next.x as usize] {
Spot::Empty | Spot::Wall => {}
Spot::BoxL => {
do_move(field, next, dir);
do_move(field, next + vec2(1, 0), dir);
let move_to = next + dir;
field[next.y as usize][next.x as usize] = Spot::Empty;
field[next.y as usize][next.x as usize + 1] = Spot::Empty;
field[move_to.y as usize][move_to.x as usize] = Spot::BoxL;
field[move_to.y as usize][move_to.x as usize + 1] = Spot::BoxR;
}
Spot::BoxR => {
do_move(field, next - vec2(1, 0), dir);
do_move(field, next, dir);
let move_to = next + dir;
field[next.y as usize][next.x as usize - 1] = Spot::Empty;
field[next.y as usize][next.x as usize] = Spot::Empty;
field[move_to.y as usize][move_to.x as usize - 1] = Spot::BoxL;
field[move_to.y as usize][move_to.x as usize] = Spot::BoxR;
}
}
}
fn part2(input: String) {
let (field1, robot1, moves) = parse(&input);
let mut field = widen(&field1);
let mut robot = Point2D::new(robot1.x * 2, robot1.y);
for m in moves {
let next = robot + m;
match field[next.y as usize][next.x as usize] {
Spot::Empty => robot = next, // Move into space
Spot::BoxL | Spot::BoxR if m.y == 0 => {
let mut search = next + m;
let can_move = loop {
match field[search.y as usize][search.x as usize] {
Spot::BoxL | Spot::BoxR => {}
Spot::Wall => break false,
Spot::Empty => break true,
}
search += m;
};
if can_move {
robot = next;
// Shift boxes by array remove/insert
field[next.y as usize].remove(search.x as usize);
field[next.y as usize].insert(next.x as usize, Spot::Empty);
}
}
Spot::BoxL | Spot::BoxR => {
if can_move_rec(&field, robot, m) {
do_move(&mut field, robot, m);
robot = next;
}
}
Spot::Wall => {} // Cannot move
}
}
println!("{}", gps(&field));
}
util::aoc_main!();
Also on github
Very cool, taking a statistical approach to discern random noise from picture.
Rust
Part 2 was very surprising in that it had a very vague requirement: "Find christmas tree!". But my idea of finding the first round where no robots overlap turned out to just work when printing the map, so that was nice. I'm glad I did not instead start looking for symmetric patterns, because the christmas tree map is not symmetric at all.
Solution
use euclid::default::*;
use regex::Regex;
fn parse(input: &str) -> Vec<(Point2D<i32>, Vector2D<i32>)> {
let re = Regex::new(r"p=(\d+),(\d+) v=(-?\d+),(-?\d+)").unwrap();
re.captures_iter(input)
.map(|cap| {
let (_, [p0, p1, v0, v1]) = cap.extract();
(
Point2D::new(p0.parse().unwrap(), p1.parse().unwrap()),
Vector2D::new(v0.parse().unwrap(), v1.parse().unwrap()),
)
})
.collect()
}
const ROOM: Size2D<i32> = Size2D::new(101, 103);
const TIME: i32 = 100;
fn part1(input: String) {
let robots = parse(&input);
let new_pos: Vec<Point2D<i32>> = robots.iter()
.map(|&(p, v)| (p + v * TIME).rem_euclid(&ROOM))
.collect();
assert_eq!(ROOM.width % 2, 1);
assert_eq!(ROOM.height % 2, 1);
let mid_x = ROOM.width / 2;
let mid_y = ROOM.height / 2;
let mut q = [0u32; 4];
for p in new_pos {
use std::cmp::Ordering::*;
match (p.x.cmp(&mid_x), p.y.cmp(&mid_y)) {
(Less, Less) => q[0] += 1,
(Greater, Less) => q[1] += 1,
(Less, Greater) => q[2] += 1,
(Greater, Greater) => q[3] += 1,
_ => {}
};
}
let prod = q[0] * q[1] * q[2] * q[3];
println!("{prod}");
}
fn print_map(map: &[Vec<bool>]) {
for row in map {
for p in row {
if *p { print!("#") } else { print!(".") }
}
println!();
}
println!();
}
fn part2(input: String) {
let mut robots = parse(&input);
let mut map = vec![vec![false; ROOM.width as usize]; ROOM.height as usize];
for i in 1.. {
let mut overlap = false;
for (p, v) in &mut robots {
*p = (*p + *v).rem_euclid(&ROOM);
if map[p.y as usize][p.x as usize] {
// Found two robots on the same spot,
// which is used as a heuristic for detecting the easter egg.
overlap = true;
} else {
map[p.y as usize][p.x as usize] = true;
}
}
if !overlap {
print_map(&map);
println!("Round: {i}");
break;
}
for row in &mut map {
row.fill(false);
}
}
}
util::aoc_main!();
Also on github
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
Also on github