Day 1: Calorie Counting
Rust solution to AoC|2022|1.
Nothing very interesting today.
Input
Parse everything in a vec of sums (initially I used a vec of vecs; since individual elements are never needed sums are enough)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub mod input {
use std::num::ParseIntError;
#[derive(Debug)]
pub struct PuzzleData {
pub calories: Vec<usize>,
}
impl TryFrom<&'static str> for PuzzleData {
type Error = ParseIntError;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
s.split("\n\n")
.map(|elf| elf.lines().map(|l| l.parse::<usize>()).sum())
.collect::<Result<Vec<_>, _>>()
.map(|calories| Self { calories })
}
}
}
Star 1
Just find the biggest sum (I use fold instead of max to not handle the Option::None case)
1
2
3
pub fn star_1(data: &PuzzleData) -> usize {
data.calories.iter().fold(0, |mx, &cal| mx.max(cal))
}
Star 2
Sum the three biggest sums. First solution used Vec::sort. New solution does not use any sorting and should be O(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn star_2(data: &PuzzleData) -> usize {
data.calories
.iter()
.fold([0; 3], |mut mx, &cal| {
if cal > mx[0] {
mx[2] = mx[1];
mx[1] = mx[0];
mx[0] = cal;
} else if cal > mx[1] {
mx[2] = mx[1];
mx[1] = cal;
} else if cal > mx[2] {
mx[2] = cal;
}
mx
})
.iter()
.sum()
}
Tests
No tests today. It was too simple.
Today I learned
Not so much. My template works.
Iterating/refactoring the solution, I learned that std::iter::Sum has an implementation impl<T, U, E> Sum<Result<U, E>> for Result<T, E>.
Day 2: Rock Paper Scissors
Rust solution to AoC|2022|2.
Input
I have two enums to parse the first column (A, B, C to RockPaperScissors) and the second column (X, Y, Z to XYZ).
It would have been much simpler to parse both into 0, 1, 2 and than use some simple formulas later on (which I did as an alternative, see below), but my solution fails gracefully if something unexpected comes in the input ;)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
pub mod input {
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RockPaperScissors {
Rock,
Paper,
Scissors,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum XYZ {
X,
Y,
Z,
}
#[derive(Debug)]
pub struct PuzzleData {
pub strategy: Vec<(RockPaperScissors, XYZ)>,
}
impl TryFrom<&'static str> for PuzzleData {
type Error = String;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
s.lines()
.map(|l| {
l.split_once(' ')
.ok_or_else(|| format!("Could not parse line '{l}'"))
.and_then(|(a, b)| {
match a {
"A" => Ok(RockPaperScissors::Rock),
"B" => Ok(RockPaperScissors::Paper),
"C" => Ok(RockPaperScissors::Scissors),
_ => Err(format!("Expected one of A, B, C, found '{a}'")),
}
.and_then(|a| match b {
"X" => Ok((a, XYZ::X)),
"Y" => Ok((a, XYZ::Y)),
"Z" => Ok((a, XYZ::Z)),
_ => Err(format!("Expected one of X, Y, Z, found '{b}'")),
})
})
})
.collect::<Result<Vec<_>, _>>()
.map(|strategy| Self { strategy })
}
}
}
Star 1
For star 1 I directly convert `XYZ`s to `RockPaperScissors’ using
1
2
3
4
5
6
7
fn to_rock_paper_scissors(self) -> RockPaperScissors {
match self {
XYZ::X => RockPaperScissors::Rock,
XYZ::Y => RockPaperScissors::Paper,
XYZ::Z => RockPaperScissors::Scissors,
}
}
The scores are calculated with
1
2
3
4
5
6
7
8
9
10
11
12
13
fn result(&self, other: &Self) -> usize {
match (self, other) {
(RockPaperScissors::Rock, RockPaperScissors::Rock) => 1 + 3,
(RockPaperScissors::Rock, RockPaperScissors::Paper) => 1,
(RockPaperScissors::Rock, RockPaperScissors::Scissors) => 1 + 6,
(RockPaperScissors::Paper, RockPaperScissors::Rock) => 2 + 6,
(RockPaperScissors::Paper, RockPaperScissors::Paper) => 2 + 3,
(RockPaperScissors::Paper, RockPaperScissors::Scissors) => 2,
(RockPaperScissors::Scissors, RockPaperScissors::Rock) => 3,
(RockPaperScissors::Scissors, RockPaperScissors::Paper) => 3 + 6,
(RockPaperScissors::Scissors, RockPaperScissors::Scissors) => 3 + 3,
}
}
And the solution is
1
2
3
4
5
6
pub fn star_1(data: &PuzzleData) -> usize {
data.strategy
.iter()
.map(|(a, b)| b.to_rock_paper_scissors().result(a))
.sum()
}
Star 2
I was expecting an optimization for the second part of the kind, "Figure out what X, Y, Z need to be so you end up with the highest score possible" or "… so that you end up with the lowest score possible that with more than 50% wins". Maybe that would have been too much for day 2.
The scores are still calculated in the same way but the conversion is now done using
1
2
3
4
5
6
7
8
9
10
11
fn for_result(&self, opponent: &RockPaperScissors) -> RockPaperScissors {
match (&self, opponent) {
(XYZ::X, RockPaperScissors::Rock) => RockPaperScissors::Scissors,
(XYZ::X, RockPaperScissors::Paper) => RockPaperScissors::Rock,
(XYZ::X, RockPaperScissors::Scissors) => RockPaperScissors::Paper,
(XYZ::Y, _) => *opponent,
(XYZ::Z, RockPaperScissors::Rock) => RockPaperScissors::Paper,
(XYZ::Z, RockPaperScissors::Paper) => RockPaperScissors::Scissors,
(XYZ::Z, RockPaperScissors::Scissors) => RockPaperScissors::Rock,
}
}
The solution is
1
2
3
4
5
6
pub fn star_2(data: &PuzzleData) -> usize {
data.strategy
.iter()
.map(|(a, b)| b.for_result(a).result(a))
.sum()
}
Tests
I made a mistake in my scoring function in the first place. So I wrote tests this time to debug this…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"A Y
B X
C Z"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(15, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(12, star_2(&data));
}
}
Today I learned
I think it was the first time I used Result::and_then in a (maybe) meaningful way.
Alternative based on direct calculations
I could not stop myself from implementing an alternative solution using direct calculations. Run the alternative solution with cargo run --release --features modulo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pub fn star_1(data: &PuzzleData) -> usize {
// 0 rock
// 1 paper
// 2 scissor
// (rock - paper + 1) % 3 = 0
// (rock - rock + 1) % 3 = 1
// (rock - scissor + 1) % 3 = 2
data.strategy
.iter()
.map(|(a, b)| ((b + 4 - a) % 3) * 3 + (b + 1))
.sum()
}
pub fn star_2(data: &PuzzleData) -> usize {
// 0 rock, 1 paper, 2 scissor
// 0 loose, 1 draw, 2 win
// to loose, subtract 1 (% 3), to win add 1 (% 3)
// play (a + b - 1) % 3 -> add this in formula for first star
data.strategy
.iter()
.map(|(a, b)| b * 3 + (a + b + 2) % 3 + 1)
.sum()
}
I also implemented a parse function which does not check any inputs and will probably result in panics if something unexpected is in the input (to parse without error handling run cargo run --release --features unchecked_parse; this will automatically use the direct calculation variant)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
impl TryFrom<&'static str> for PuzzleData {
type Error = String;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
if cfg!(feature = "unchecked_parse") {
Ok(Self {
strategy: s
.lines()
.map(str::as_bytes)
.map(|bytes| ((bytes[0] - b'A') as usize, (bytes[2] - b'X') as usize))
.collect(),
})
} else {
s.lines()
.map(|l| {
l.split_once(' ')
.ok_or_else(|| format!("Could not parse line '{l}'"))
.and_then(|(a, b)| {
match a {
"A" => Ok(0),
"B" => Ok(1),
"C" => Ok(2),
_ => Err(format!("Expected one of A, B, C, found '{a}'")),
}
.and_then(|a| match b {
"X" => Ok((a, 0)),
"Y" => Ok((a, 1)),
"Z" => Ok((a, 2)),
_ => Err(format!("Expected one of X, Y, Z, found '{b}'")),
})
})
})
.collect::<Result<Vec<_>, _>>()
.map(|strategy| Self { strategy })
}
}
}
Interestingly, not doing any error handling in parsing the input does not lead to any measurable speed-up. Maybe this is because the overall solution time is so small, that the differences are not distinguishable from noise?
Day 3: Rucksack Reorganization
Rust solution to AoC|2022|3.
Input
I parse the input directly into a vec of vecs of bytes, each representing the priority of the items contained in the rucksacks.
I was tempted to think about using sets for quicker contains operations, but given the size of the problem, this is most likely not worth it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub rucksacks: Vec<Vec<u8>>,
}
impl TryFrom<&'static str> for PuzzleData {
type Error = &'static str;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
s.lines()
.map(|l| {
l.as_bytes()
.iter()
.map(|&b| match b {
b'a'..=b'z' => Ok(b - b'a' + 1),
b'A'..=b'Z' => Ok(b - b'A' + 27),
_ => Err("Unexpected bytes in input"),
})
.collect::<Result<Vec<_>, _>>()
})
.collect::<Result<Vec<_>, _>>()
.map(|rucksacks| Self { rucksacks })
}
}
}
Star 1
Star 1 is about finding the item in the first compartment (first half) of the rucksack, which is also contained in the secod half.
Some simplifications work because / if the input is correct.
-
I assume that a common item always exists and therefore do not limit the search to the first half (it will stop once an item is found, which will be in the first half)
-
The
findfunction returns anOption. If there were anyNonevalues, they would be simply discarded usingfilter_map(actually, for part 1, there can be noNonevalues, because search is not stopped in the first half, so the first element of the second half would be found, if there is no common element between first and second half. so a simpleunwrapwould work as well). -
The
chunks_exactfunction makes sure that every chunk has exactly three elements. If the overall number of rucksacks was not a multiple of three, the remaining rucksacks would simply be discarded.
I use a fold instead of sum to do type conversion on the fly (u8 would not be big enough to hold the sum).
1
2
3
4
5
6
7
8
9
10
pub fn star_1(data: &PuzzleData) -> usize {
data.rucksacks
.iter()
.filter_map(|rucksack| {
rucksack
.iter()
.find(|item| rucksack.as_slice()[rucksack.len() / 2..].contains(item))
})
.fold(0usize, |sum, item| sum + *item as usize)
}
Star 2
Star 2 is a simple modification, where we look for items that are common for groups of three consecutive rucksacks
1
2
3
4
5
6
7
8
9
10
pub fn star_2(data: &PuzzleData) -> usize {
data.rucksacks
.chunks_exact(3)
.filter_map(|group| {
group[0]
.iter()
.find(|item| group[1].contains(item) && group[2].contains(item))
})
.fold(0usize, |sum, item| sum + *item as usize)
}
Tests
Tests use the example given in the puzzle.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(157, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(70, star_2(&data));
}
}
Today I learned
... that sometimes it is as simple as it appears at first view.
Day 4: Camp Cleanup
Rust solution to AoC|2022|4.
Input
Today, input parsing was the biggest challenge. Mainly because I decided to not use unwrap but try some proper error handling and to avoid intermediate collect calls. Until I figured out that the code is much simplified if I create a separate function to parse a single line (because ? can be used in that function but not in a clojure within an iterator’s map function), I had to use a lot of and_then, map, map_error, …
So here is my parsing functions (admittedly not how it looked like when I submitted my results)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
pub mod input {
use crate::Pair;
use mr_kaffee_aoc::err::PuzzleError;
#[derive(Debug)]
pub struct PuzzleData {
pub range_pairs: Vec<Pair>,
}
fn parse_pair(line: &str) -> Result<Pair, PuzzleError> {
let mut iter = line.split(['-', ',']);
Ok((
(
iter.next()
.ok_or_else(|| format!("Missing start 1 '{line}'"))?
.parse()?,
iter.next()
.ok_or_else(|| format!("Missing end 1 in '{line}'"))?
.parse()?,
),
(
iter.next()
.ok_or_else(|| format!("Missing start 2 in '{line}'"))?
.parse()?,
iter.next()
.ok_or_else(|| format!("Missing end 2 in '{line}'"))?
.parse()?,
),
))
}
impl TryFrom<&'static str> for PuzzleData {
type Error = PuzzleError;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
s.lines()
.map(parse_pair)
.collect::<Result<Vec<_>, _>>()
.map(|range_pairs| Self { range_pairs })
}
}
}
Star 1
The actual solution is simple for part 1 …
1
2
3
4
5
6
7
8
9
pub fn star_1(data: &PuzzleData) -> usize {
// count how often one range is contained in the other
data.range_pairs
.iter()
.filter(|((start1, end1), (start2, end2))| {
(start1 <= start2 && end2 <= end1) || (start2 <= start1 && end1 <= end2)
})
.count()
}
Star 2
... as well as for part 2 (I was afraid to be asked to look for overlaps across pairs in part 2 …)
1
2
3
4
5
6
7
8
9
pub fn star_2(data: &PuzzleData) -> usize {
// count how often ranges overlap, i.e., start of one range is contained in the other range
data.range_pairs
.iter()
.filter(|((start1, end1), (start2, end2))| {
(start1 <= start2 && start2 <= end1) || (start2 <= start1 && start1 <= end2)
})
.count()
}
Tests
Today I even did test-driven development in the sense that I did not write any functional code before I had a failing test case ;)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#[cfg(test)]
mod tests {
use super::*;
use mr_kaffee_aoc::err::PuzzleError;
const CONTENT: &str = r#"2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8"#;
#[test]
pub fn test_star_1() -> Result<(), PuzzleError> {
let data = PuzzleData::try_from(CONTENT)?;
assert_eq!(2, star_1(&data));
Ok(())
}
#[test]
pub fn test_star_2() -> Result<(), PuzzleError> {
let data = PuzzleData::try_from(CONTENT)?;
assert_eq!(4, star_2(&data));
Ok(())
}
}
Today I learned
and_then - map - and_then - map - map_err … is all not needed if some parsing functionality for one line is moved to a separate function where the ? shortcut operator can be used for error propagation and conversion
Day 5: Supply Stacks
Rust solution to AoC|2022|5.
Today, there where two main challenges for me:
-
Parsing the input
-
Rust’s mutability & borrowing concept for part 2
In addition, it turns out quite complicated to handle possible errors (all kind of invalid moves, empty stacks at end of moves, …). All this effort for code that is never used, because the puzzle inputs are well-formed. I think I will stop this excercise and use plain unwrap again for subsequent days.
Input
Today, it was not just "process input line by line", but in the end almost …
First, I split the input in one part describing the stacks and a second part describing the moves. Parsing the moves in tuples (n, from, to) is easy. I make the from and to parts zero-based on the fly.
Parsing the stacks of crates is a bit more tricky. I did not (could not) use a simple iterator / collect scheme but allocated the stacks upfront and than process line by line starting at the last and pushing elements on the stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
pub mod input {
use mr_kaffee_aoc::err::PuzzleError;
#[derive(Debug, PartialEq, Eq)]
pub struct PuzzleData {
stacks: Vec<Vec<char>>,
moves: Vec<(usize, usize, usize)>,
}
fn parse_move(line: &str, len: usize) -> Result<(usize, usize, usize), PuzzleError> {
let mut parts = line.split(' ');
parts.next(); // skip "move"
let n = parts
.next()
.ok_or_else(|| format!("Missing number in move '{line}'"))?
.parse::<usize>()?;
parts.next(); // skip "from"
let from = parts
.next()
.ok_or_else(|| format!("Missing from in move '{line}'"))?
.parse::<usize>()?
- 1;
parts.next(); // skip "to"
let to = parts
.next()
.ok_or_else(|| format!("Missing to in move '{line}'"))?
.parse::<usize>()?
- 1;
if from >= len || to >= len {
Err(format!("Invalid move: '{line}', <from>, <to> <= {len} required.").into())
} else if from == to {
Err(format!("Invalid move: '{line}', <from> != <to> required.").into())
} else {
Ok((n, from, to))
}
}
fn parse_crate_layer(stacks: &mut Vec<Vec<char>>, line: &str) {
for (k, item) in line
.chars()
.skip(1)
.step_by(4)
.enumerate()
.filter(|(_, item)| *item != ' ')
{
while k >= stacks.len() {
stacks.push(Vec::new());
}
stacks[k].push(item);
}
}
impl TryFrom<&'static str> for PuzzleData {
type Error = PuzzleError;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
let (stacks_part, moves_part) = s
.split_once("\n\n")
.ok_or("Could not separate crates from moves")?;
let mut stacks: Vec<Vec<char>> = vec![];
for line in stacks_part.lines().rev().skip(1) {
parse_crate_layer(&mut stacks, line);
}
let moves = moves_part
.lines()
.map(|line| parse_move(line, stacks.len()))
.collect::<Result<Vec<_>, _>>()?;
Ok(PuzzleData { stacks, moves })
}
}
impl PuzzleData {
/// get moves
pub fn moves(&self) -> &[(usize, usize, usize)] {
&self.moves
}
/// get cloned crates
pub fn stacks(&self) -> Vec<Vec<char>> {
self.stacks.clone()
}
}
}
Star 1
This is straight forward. Just process move by move, and pop from one stack / push to the other stack the correct number of times.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
fn msg(stacks: &[Vec<char>]) -> Result<String, PuzzleError> {
stacks
.iter()
.map(|c| {
c.last().ok_or_else(|| {
PuzzleError::from(format!(
"Can't construct message. Empty stack in {stacks:?}"
))
})
})
.collect()
}
pub fn star_1(data: &PuzzleData) -> Result<String, PuzzleError> {
let mut stacks = data.stacks();
for (n, from, to) in data.moves() {
for _ in 0..*n {
let item = stacks[*from]
.pop()
.ok_or_else(|| format!("Tried to pop from empty stack {from}, stacks: {stacks:?}"))?;
stacks[*to].push(item);
}
}
msg(&stacks)
}
Star 2
This is slightly more tricky. Now we have to pop a complete pack of items and push that on top of another stack preserving the order.
The challenging part of it is that Rust does not allow mutable references to two items in a vec at the same time. My first solution used intermediate storage. My current solution uses slice::split_at_mut to circumvent this (speed-up by a factor 3 to 4 for part 2 compared to intermediate storage). The code gets a bit complicated though — I extracted the complicated part to a function mut_references.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
fn mut_references<T>(v: &mut [T], idx1: usize, idx2: usize) -> (&mut T, &mut T) {
if idx1 > idx2 {
let (left, right) = v.split_at_mut(idx1);
(&mut right[0], &mut left[idx2])
} else {
let (left, right) = v.split_at_mut(idx2);
(&mut left[idx1], &mut right[0])
}
}
pub fn star_2(data: &PuzzleData) -> Result<String, PuzzleError> {
let mut stacks = data.stacks();
for (n, from, to) in data.moves() {
// I need a mutable reference to the from and the to part at the same time
// to avoid creating intermediate storage
let (source, dest) = mut_references(&mut stacks, *from, *to);
let len = source.len();
if *n > len {
return Err(format!(
"Trying to pop {n} elements from stack {from} containing {len}, stacks: {stacks:?}"
)
.into());
}
for item in source.drain(len - n..) {
dest.push(item);
}
}
msg(&stacks)
}
Tests
And there are some tests.
Since parsing was not totally obvious, I did an additional test for this part …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#" [D]
[N] [C]
[Z] [M] [P]
1 2 3
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2"#;
#[test]
pub fn test_parse() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(
vec![vec!['Z', 'N'], vec!['M', 'C', 'D'], vec!['P']],
data.stacks()
);
assert_eq!(&[(1, 1, 0), (3, 0, 2), (2, 1, 0), (1, 0, 1)], data.moves());
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!("CMZ", star_1(&data).unwrap());
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!("MCD", star_2(&data).unwrap());
}
}
Today I learned
How to mutably access two elements of one vec in Rust.
Day 6: Tuning Trouble
Rust solution to AoC|2022|6.
Today I totally screwed up for the second star for no specific reason :(
Too little sleep probably.
Input
I parse the input directly into a slice of bytes. That should be very cheap…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub mod input {
use std::convert::Infallible;
#[derive(Debug)]
pub struct PuzzleData {
pub stream: &'static [u8],
}
impl TryFrom<&'static str> for PuzzleData {
type Error = Infallible;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
Ok(PuzzleData {
stream: s.trim().as_bytes(),
})
}
}
}
Star 1
Hand-crafted solution
1
2
3
4
5
6
7
8
9
10
11
12
13
pub fn star_1(data: &PuzzleData) -> usize {
let (k, _) = data
.stream
.windows(4)
.enumerate()
.find(|(_, s)| match s {
&[a, b, c, d] => a != b && a != c && a != d && b != c && b != d && c != d,
_ => unreachable!(),
})
.unwrap();
k + 4
}
Star 2
Solution with a bit of iterators.
It feels bad to search the same thing again and again. If a duplicate is found in a window, the search could skip everything until the character just after the first occurance of the duplicate. I implemented this as an alternative (see below)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn star_2(data: &PuzzleData) -> usize {
let (k, _) = data
.stream
.windows(14)
.enumerate()
.find(|(_, w)| {
w.iter()
.enumerate()
.skip(1)
.all(|(p, c1)| w.iter().take(p).all(|c2| c1 != c2))
})
.unwrap();
k + 14
}
Alternative
As an alternative, I implemented a generic solution which skips parts of the search already covered. Interestingly, this solution tends to be slightly slower (the difference is close to measurement noise in my not very professional time measurements)
1
2
3
4
5
6
7
8
9
10
11
pub fn find_distinct(stream: &[u8], n: usize) -> usize {
let mut k = 0;
while k < stream.len() - n {
match (k + 1..k + n).find(|p| stream[*p..k + n].contains(&stream[*p - 1])) {
Some(q) => k = q,
None => return k + n,
}
}
panic!("No solution.");
}
Tests
Tests for all variants
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"mjqjpqmgbljsphdztnvjfqwrcgsmlb"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(7, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(19, star_2(&data));
}
#[test]
pub fn test_find_distinct() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(7, find_distinct(data.stream, 4));
assert_eq!(19, find_distinct(data.stream, 14));
}
}
Today I learned
Take a second cup of coffee before solving the puzzle, don’t forget to wear glasses, and
-
it is cool to not allocate any intermediate storage but work directly on byte slices.
-
it is possible to destructure slices with
match
Day 7: No Space Left On Device
Rust solution to AoC|2022|7.
When reading the puzzle today, I thought it would get complicated. Finally, it was quite straight-forward.
Input
The description asks for recursion / recursive data structures, which I find a pain in Rust. My solution is to create a vec of Directory elements. Each directory contains references to children and the parent directory as index to this vec.
The directories are created by processing the input line by line. When an ls command yields a directory, a new Directory element is added, its index is added to the children to of the current directory and its parent is set to the current directorie’s index.
File sizes are directly summed up (initially, child files were stored in a vec, but once part 2 was unveiled, it was clear that the sum is the only thing needed)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
pub mod input {
use std::{collections::HashMap, convert::Infallible};
#[derive(Debug)]
pub struct Directory {
parent: Option<usize>,
children: HashMap<&'static str, usize>,
size: usize,
}
impl Directory {
fn new(parent: Option<usize>) -> Self {
Self {
parent,
children: HashMap::new(),
size: 0,
}
}
pub fn total_size(&self, dirs: &[Directory]) -> usize {
self.size
+ self
.children
.values()
.map(|idx| dirs[*idx].total_size(dirs))
.sum::<usize>()
}
}
#[derive(Debug)]
pub struct PuzzleData {
dirs: Vec<Directory>,
}
impl TryFrom<&'static str> for PuzzleData {
type Error = Infallible;
/// parse the puzzle input
fn try_from(s: &'static str) -> Result<Self, Self::Error> {
let mut dirs = vec![Directory::new(None)];
let mut current = 0;
for line in s.lines() {
match line {
"$ cd /" => current = 0,
"$ cd .." => current = dirs[current].parent.unwrap(),
"$ ls" => (),
_ if line.starts_with("$ cd ") => current = dirs[current].children[&line[5..]],
_ if line.starts_with("dir ") => {
let dir = dirs.len();
dirs.push(Directory::new(Some(current)));
dirs[current].children.insert(&line[4..], dir);
}
_ => {
dirs[current].size +=
line[..line.find(' ').unwrap()].parse::<usize>().unwrap();
}
}
}
Ok(Self { dirs })
}
}
impl PuzzleData {
/// immutable access to directories as slice
pub fn dirs(&self) -> &[Directory] {
&self.dirs
}
}
}
Star 1
Simple iter - filter - fold
1
2
3
4
5
6
7
pub fn star_1(data: &PuzzleData) -> usize {
data.dirs()
.iter()
.map(|d| d.total_size(data.dirs()))
.filter(|&s| s <= 100_000)
.sum()
}
Star 2
Another simple iter - filter - fold
1
2
3
4
5
6
7
8
9
pub fn star_2(data: &PuzzleData) -> usize {
let required = data.dirs()[0].total_size(data.dirs()) - 40_000_000;
data.dirs()
.iter()
.map(|d| d.total_size(data.dirs()))
.filter(|&s| s >= required)
.fold(usize::MAX, |mn, s| mn.min(s))
}
Tests
The standard tests.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(95_437, star_1(&data))
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::try_from(CONTENT).unwrap();
assert_eq!(24_933_642, star_2(&data))
}
}
Day 8: Treetop Tree House
Rust solution to AoC|2022|8.
I took a moment to put my brain in the condition to think in the 2D grid…
Input
I directly use the bytes from the input. I scan for the first occurrence of a line break. Its index is the width of the grid. The PuzzleData struct’s implementation has an additional field for the height of the grid.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub trees: &'static [u8],
pub w: usize,
pub h: usize,
}
impl From<&'static str> for PuzzleData {
/// parse the puzzle input
fn from(s: &'static str) -> Self {
let trees = s.as_bytes();
let w = s.find('\n').unwrap();
let h = trees.len() / (w + 1);
Self { trees, w, h }
}
}
}
Star 1
The function is_visible verifies in all four directions (left, right, top, bottom), that all trees up to the boundary are smaller. It stops after one such direction is found.
1
2
3
4
5
6
7
8
pub fn is_visible(&self, x: usize, y: usize) -> bool {
let h = self.trees[x + (self.w + 1) * y];
let fx = |x_: usize| self.trees[x_ + (self.w + 1) * y] < h;
let fy = |y_: usize| self.trees[x + (self.w + 1) * y_] < h;
(0..x).all(fx) || (x + 1..self.w).all(fx) || (0..y).all(fy) || (y + 1..self.h).all(fy)
}
Then I count in the star_1 function, how many trees are visible. For a tree on the boundary, is_visible always returns true, so no need to handle the boundary separately.
1
2
3
4
5
pub fn star_1(data: &PuzzleData) -> usize {
(0..data.w)
.map(|x| (0..data.h).filter(|&y| data.is_visible(x, y)).count())
.sum::<usize>()
}
Star 2
Similar to star 1. This time, I use the function scenic_score to calculate the scenic score of each tree and the function star_2 to find the maximum.
In the scenic score calculations, different to the visibility check, the traversal order matters. For left and top directions, the direction is reversed.
1
2
3
4
5
6
7
8
9
10
11
pub fn scenic_score(&self, x: usize, y: usize) -> usize {
let h = self.trees[x + (self.w + 1) * y];
let fx = |&x_: &usize| self.trees[x_ + (self.w + 1) * y] >= h;
let fy = |&y_: &usize| self.trees[x + (self.w + 1) * y_] >= h;
(x - (0..x).rev().find(fx).unwrap_or(0))
* ((x + 1..self.w).find(fx).unwrap_or(self.w - 1) - x)
* (y - (0..y).rev().find(fy).unwrap_or(0))
* ((y + 1..self.h).find(fy).unwrap_or(self.h - 1) - y)
}
1
2
3
4
5
6
pub fn star_2(data: &PuzzleData) -> usize {
(0..data.w)
.map(|x| (0..data.h).map(|y| data.scenic_score(x, y)).max().unwrap())
.max()
.unwrap()
}
Tests
Tests for star_1, scenic_score and star_2 functions based on example defined in puzzle description.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"30373
25512
65332
33549
35390
"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(21, star_1(&data));
}
#[test]
pub fn test_scenic_score() {
let data = PuzzleData::from(CONTENT);
assert_eq!(4, data.scenic_score(2, 1));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(8, star_2(&data));
}
}
Day 9: Rope Bridge
Rust solution to AoC|2022|9.
Knots are moving around, following each other. The difficulty is to figure out where you have your off by one errors or similar. In the end, I had a print function showing current configurations to debug my code (because it actually looks nice, you may want to have a look at the output with cargo test test_star_2 -- --nocapture):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/// Print knots for debugging purposes
///
/// Knots are printed by consecutive letters `a`, `b`, ... starting with the head at `a`
///
/// If a knot sits on a spot which is already seen, it is represented by a capital letter `A`, `B`, ...
///
/// The start is indicated by `$` if no knot is located at the start
///
/// Spots that have been seen and where currently no knot is located are shown as `#`
///
/// If several knots sit on top of each other, the first one in the chain is shown.
pub fn print(
rx: RangeInclusive<isize>,
ry: RangeInclusive<isize>,
knots: &[(isize, isize)],
((dx, dy), s): ((isize, isize), usize),
seen: &HashSet<(isize, isize)>,
) {
println!("\nAfter moving {s} times by ({dx}, {dy}):");
for y in ry {
for x in rx.clone() {
let seen = seen.contains(&(x, y));
match knots
.iter()
.enumerate()
.find(|(_, (xn, yn))| *xn == x && *yn == y)
{
Some((v, _)) if seen => print!("{}", (b'A' + v as u8) as char),
Some((v, _)) => print!("{}", (b'a' + v as u8) as char),
None if x == 0 && y == 0 => print!("$"),
_ if seen => print!("#"),
_ => print!("\u{00b7}"),
}
}
println!();
}
}
Input
I parse the input in a vec of tuples ((dx, dy), s) where dx and dy are the horizontal / vertical unit step changes and s is the number of steps.
Not allocating extra memory for today’s input parsing is not for me ;)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
moves: Vec<((isize, isize), usize)>,
}
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self {
moves: s
.lines()
.map(|l| match (l.as_bytes()[0], l[2..].parse().unwrap()) {
(b'U', s) => ((0, -1), s),
(b'D', s) => ((0, 1), s),
(b'L', s) => ((-1, 0), s),
(b'R', s) => ((1, 0), s),
_ => panic!("No valid move: {l}"),
})
.collect(),
}
}
}
impl PuzzleData {
pub fn moves(&self) -> &[((isize, isize), usize)] {
&self.moves
}
}
}
Solution
After a little bit of refactoring, one solution works for both parts today. The solve function is called with the total number of knots (including head) as a parameter.
In each step, it updates the head and then all subsequent knots ony by one.
The debug function parameter is a clojure that is called after each move for debugging purposes. In the actual solution, an empty function is used. In the test cases, the print function is called.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
pub fn solve<F>(data: &PuzzleData, n: usize, debug: F) -> usize
where
F: Fn(&[(isize, isize)], ((isize, isize), usize), &HashSet<(isize, isize)>),
{
let mut seen: HashSet<(isize, isize)> = HashSet::from([(0, 0)]);
let mut knots: Vec<(isize, isize)> = vec![(0, 0); n];
for ((dx, dy), s) in data.moves() {
for _ in 0..*s {
knots[0].0 += *dx;
knots[0].1 += *dy;
for k in 1..n {
let dx = knots[k].0 - knots[k - 1].0;
let dy = knots[k].1 - knots[k - 1].1;
knots[k].0 += (dx < -1 || (dx == -1 && dy.abs() > 1)) as isize
- (dx > 1 || (dx == 1 && dy.abs() > 1)) as isize;
knots[k].1 += (dy < -1 || (dy == -1 && dx.abs() > 1)) as isize
- (dy > 1 || (dy == 1 && dx.abs() > 1)) as isize;
}
seen.insert(knots[n - 1]);
}
debug(&knots, ((*dx, *dy), *s), &seen);
}
seen.len()
}
Tests
The usual tests:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2
"#;
const CONTENT_2: &str = r#"R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20
"#;
#[test]
pub fn test_try_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(
13,
solve(&data, 2, |knots, mv, seen| print(
0..=5,
-5..=0,
knots,
mv,
seen
))
);
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(1, solve(&data, 10, |_, _, _| ()));
let data = PuzzleData::from(CONTENT_2);
assert_eq!(
36,
solve(&data, 10, |knots, mv, seen| print(
-11..=14,
-15..=5,
knots,
mv,
seen
))
);
}
}
Today I learned
That sometimes it is helpful to write as _ to give the rust compiler a hint to perform type coercion. Although in the end, I did not use it in my solution.
And, today for the first time, I used my scripted solution to submit results. Not because it is faster (who cares about a few seconds) but because it is fun.
Day 10: Cathode-Ray Tube
Rust solution to AoC|2022|10.
Today is about a simple CPU which is used to control a simple display (a cathode-ray tube)
Input
Parsing the input is straight forward. Each line represents either an addx operation or a noop operation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
pub mod input {
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum Instr {
NoOp,
AddX(isize),
}
#[derive(Debug)]
pub struct PuzzleData {
instructions: Vec<Instr>,
}
impl From<&'static str> for PuzzleData {
/// parse the puzzle input
fn from(s: &'static str) -> Self {
Self {
instructions: s
.lines()
.map(|l| match l {
"noop" => Instr::NoOp,
_ => Instr::AddX(l[5..].parse().unwrap()),
})
.collect(),
}
}
}
impl PuzzleData {
pub fn instructions(&self) -> &[Instr] {
&self.instructions
}
}
}
Star 1
I created a small model of the CPU:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
pub struct Cpu {
instructions: Vec<Instr>,
pointer: usize,
cycle: usize,
timer: usize,
x: isize,
}
impl Cpu {
pub fn init(instructions: &[Instr]) -> Self {
let mut cpu = Self {
instructions: Vec::from(instructions),
pointer: 0,
cycle: 0,
timer: 0,
x: 1,
};
// set initial timer if required
if let Instr::AddX(_) = cpu.instructions[0] {
cpu.timer = 1;
}
cpu
}
pub fn step(&mut self) {
// should not be called if no more instructions
assert!(self.pointer < self.instructions.len(), "Cpu halted");
if self.timer > 0 {
// only decrement timer
self.timer -= 1;
} else {
// apply increment
if let Instr::AddX(inc) = self.instructions[self.pointer] {
self.x += inc;
}
// increment pointer
self.pointer += 1;
// set timer if required
if self.pointer < self.instructions.len() {
if let Instr::AddX(_) = self.instructions[self.pointer] {
self.timer = 1;
}
}
}
// increment cycle counter
self.cycle += 1;
}
}
The most difficult part was to read the puzzle description carefully. Specifically the part were it says to calculate the signal strength during and not after the 20th, 60th, … cycle.
The rest was just applying the instructions giving in the puzzle.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn star_1(data: &PuzzleData) -> isize {
let mut cpu = Cpu::init(data.instructions());
// we first look during 20th cycle, i.e., after 19th cycle
for _ in 0..19 {
cpu.step();
}
let mut v = (cpu.cycle as isize + 1) * cpu.x;
// 5 blocks of 40 cycles
for _ in 0..5 {
for _ in 0..40 {
cpu.step();
}
v += (cpu.cycle as isize + 1) * cpu.x;
}
v
}
Star 2
Again, reading carefully is important. I did not get the meaning of
In this system, there is no such thing as "vertical position"
After having that fixed, it was again straight forward. It somehow feels incorrect to manually read the "LCD" to produce the result to enter at the website, hence I created a little helper which recognizes the letters. Since there is nothing to recognize for the sample data, I put the recognition in a separate function to still be able to run my code on the examples.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
pub fn solve_2(data: &PuzzleData) -> [u8; 240] {
const W: usize = 40;
const H: usize = 6;
// initialize lcd with new lines, W + 1 to keep new lines at the and
let mut lcd = [b'.'; W * H];
let mut cpu = Cpu::init(data.instructions());
for row in 0..H {
for col in 0..W {
lcd[col + W * row] = if (cpu.x - 1..=cpu.x + 1).contains(&(col as _)) {
LIT as u8
} else {
DARK as u8
};
cpu.step();
}
}
lcd
}
pub fn star_2(data: &PuzzleData) -> String {
solve_2(data).decode(0).unwrap()
}
Tests
A bit of tests, as usual …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#[cfg(test)]
mod tests {
use super::*;
#[test]
pub fn test_try_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(13_140, star_1(&data));
}
#[test]
pub fn test_solve_2() {
let data = PuzzleData::from(CONTENT);
let b = solve_2(&data);
let mut s = String::with_capacity(41 * 6);
for row in 0..6 {
for col in 0..40 {
s.push(b[col + 40 * row] as _);
}
s.push('\n');
}
assert_eq!(EXP_2, s);
}
#[test]
pub fn test_simple() {
let data = PuzzleData::from(CONTENT_SIMPLE);
let mut cpu = Cpu::init(data.instructions());
let r = (0..5)
.map(|_| {
cpu.step();
cpu.x
})
.collect::<Vec<_>>();
let exp: &[isize] = &[1, 1, 4, 4, -1];
assert_eq!(exp, r);
}
const CONTENT_SIMPLE: &str = r#"noop
addx 3
addx -5"#;
const EXP_2: &str = r"##..##..##..##..##..##..##..##..##..##..
###...###...###...###...###...###...###.
####....####....####....####....####....
#####.....#####.....#####.....#####.....
######......######......######......####
#######.......#######.......#######.....
";
const CONTENT: &str = r#"addx 15
addx -11
addx 6
addx -3
addx 5
addx -1
addx -8
addx 13
addx 4
noop
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx -35
addx 1
addx 24
addx -19
addx 1
addx 16
addx -11
noop
noop
addx 21
addx -15
noop
noop
addx -3
addx 9
addx 1
addx -3
addx 8
addx 1
addx 5
noop
noop
noop
noop
noop
addx -36
noop
addx 1
addx 7
noop
noop
noop
addx 2
addx 6
noop
noop
noop
noop
noop
addx 1
noop
noop
addx 7
addx 1
noop
addx -13
addx 13
addx 7
noop
addx 1
addx -33
noop
noop
noop
addx 2
noop
noop
noop
addx 8
noop
addx -1
addx 2
addx 1
noop
addx 17
addx -9
addx 1
addx 1
addx -3
addx 11
noop
noop
addx 1
noop
addx 1
noop
noop
addx -13
addx -19
addx 1
addx 3
addx 26
addx -30
addx 12
addx -1
addx 3
addx 1
noop
noop
noop
addx -9
addx 18
addx 1
addx 2
noop
noop
addx 9
noop
noop
noop
addx -1
addx 2
addx -37
addx 1
addx 3
noop
addx 15
addx -21
addx 22
addx -6
addx 1
noop
addx 2
addx 1
noop
addx -10
noop
noop
addx 20
addx 1
addx 2
addx 2
addx -6
addx -11
noop
noop
noop
"#;
}
Day 11: Monkey in the Middle
Rust solution to AoC|2022|11.
It was quite tedious today for me to create the solution.
I liked the twist in part 2. Since each monkey does a modulo test before passing on the item, we can safely do a modulo with the product of all tests of all monkeys to keep the numbers small. Still took me a while to complete part two because I just replaced the / 3 from the first part with / mod in the second part which is obviously not the same as % mod. And I have to confess that my first attempt was to use 128bit numbers.
Input
Parsing was a painful, initially, to the point that I almost regretted my decision to not use external dependencies (and thus not use Regex) … In the end it looks quite clean, I guess.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
pub mod input {
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum Operation {
Plus(usize),
Times(usize),
Square,
Double,
}
impl Operation {
pub fn apply(&self, item: usize) -> usize {
match self {
Operation::Plus(v) => item + v,
Operation::Times(v) => item * v,
Operation::Square => item * item,
Operation::Double => item + item,
}
}
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Monkey {
pub worries: Vec<usize>,
pub upd: Operation,
pub test: usize,
pub if_true: usize,
pub if_false: usize,
}
impl From<&'static str> for Monkey {
fn from(monkey: &'static str) -> Self {
const PREFIXES: [&str; 5] = [
"Starting items: ",
"Operation: new = old ",
"Test: divisible by ",
"If true: throw to monkey ",
"If false: throw to monkey ",
];
let mut parts = (monkey.lines().skip(1).map(str::trim))
.zip(PREFIXES)
.map(|(v, prefix)| v.strip_prefix(prefix).unwrap());
Self {
worries: (parts.next().unwrap())
.split(", ")
.map(str::parse)
.collect::<Result<_, _>>()
.unwrap(),
upd: match parts.next().map(|p| (&p[0..1], &p[2..])).unwrap() {
("+", "old") => Operation::Double,
("*", "old") => Operation::Square,
("+", v) => Operation::Plus(v.parse().unwrap()),
("*", v) => Operation::Times(v.parse().unwrap()),
e => panic!("Unexpected content: {:?}", e),
},
test: parts.next().unwrap().parse().unwrap(),
if_true: parts.next().unwrap().parse().unwrap(),
if_false: parts.next().unwrap().parse().unwrap(),
}
}
}
#[derive(Debug)]
pub struct PuzzleData(pub Vec<Monkey>);
impl From<&'static str> for PuzzleData {
/// parse the puzzle input
fn from(s: &'static str) -> Self {
Self(s.split("\n\n").map(Monkey::from).collect())
}
}
}
Solution
Here is my solution for both parts. The solve function is called with div = 3 for the first part and div = 1 for the second.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
pub fn round(monkeys: &mut [Monkey], counts: &mut [usize], div: usize, m: usize) {
for id in 0..monkeys.len() {
counts[id] += monkeys[id].worries.len();
for k in 0..monkeys[id].worries.len() {
let worry = (monkeys[id].upd.apply(monkeys[id].worries[k]) / div) % m;
let target = if worry % monkeys[id].test == 0 {
monkeys[id].if_true
} else {
monkeys[id].if_false
};
monkeys[target].worries.push(worry);
}
monkeys[id].worries.clear();
}
}
pub fn solve(PuzzleData(monkeys): &PuzzleData, div: usize, rounds: usize) -> usize {
let mut monkeys = monkeys.to_owned();
let mut counts = vec![0; monkeys.len()];
let m = monkeys.iter().map(|monkey| monkey.test).product();
for _ in 0..rounds {
round(&mut monkeys, &mut counts, div, m);
}
counts.sort_unstable();
counts[counts.len() - 1] * counts[counts.len() - 2]
}
Tests
-
and the tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Monkey 0:
Starting items: 79, 98
Operation: new = old * 19
Test: divisible by 23
If true: throw to monkey 2
If false: throw to monkey 3
Monkey 1:
Starting items: 54, 65, 75, 74
Operation: new = old + 6
Test: divisible by 19
If true: throw to monkey 2
If false: throw to monkey 0
Monkey 2:
Starting items: 79, 60, 97
Operation: new = old * old
Test: divisible by 13
If true: throw to monkey 1
If false: throw to monkey 3
Monkey 3:
Starting items: 74
Operation: new = old + 3
Test: divisible by 17
If true: throw to monkey 0
If false: throw to monkey 1
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_round() {
let PuzzleData(mut monkeys) = PuzzleData::from(CONTENT);
let mut counts = vec![0; monkeys.len()];
round(&mut monkeys, &mut counts, 3, usize::MAX);
assert_eq!(vec![20, 23, 27, 26], monkeys[0].worries);
assert_eq!(vec![2080, 25, 167, 207, 401, 1046], monkeys[1].worries);
assert!(monkeys[2].worries.is_empty());
assert!(monkeys[3].worries.is_empty());
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(10605, solve(&data, 3, 20));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(4 * 6, solve(&data, 1, 1));
assert_eq!(99 * 103, solve(&data, 1, 20));
assert_eq!(2_713_310_158, solve(&data, 1, 10_000));
}
}
Day 12: Hill Climbing Algorithm
Rust solution to AoC|2022|12.
The first path finding challenge in 2022’s AoC edition ;)
Input
I parse the input into a grid of bytes stored in a vec and additionally determine the starting position, the target position and the width of the grid.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub grid: Vec<u8>,
pub width: usize,
pub start: usize,
pub target: usize,
}
impl<'a> From<&'a str> for PuzzleData {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
let width = s.find('\n').unwrap();
let mut grid: Vec<_> = s
.as_bytes()
.iter()
.cloned()
.filter(|b| *b != b'\n')
.collect();
let start = grid.iter().position(|&b| b == b'S').unwrap();
let target = grid.iter().position(|&b| b == b'E').unwrap();
grid[start] = b'a';
grid[target] = b'z';
Self {
grid,
width,
start,
target,
}
}
}
}
Star 1
The shortest path is found by a breadth first traversal.
The function shortest_path returns an option with a None value in case no path is found. My initial version just panicked in that case which turned out to not be good enough for part 2.
Today, I made the baddest mistake ever: I put the wrong number in my test (32 instead of 31) and was trying to figure out for quite some while where I inserted an off-by-one error in my code until I figured that my expected value was wrong.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
pub fn shortest_path(data: &PuzzleData, start: usize) -> Option<usize> {
let mut queue = VecDeque::new();
queue.push_back((0, start));
let mut seen = vec![false; data.grid.len()];
seen[start] = true;
let height = data.grid.len() / data.width;
while let Some((steps, pos)) = queue.pop_front() {
if pos == data.target {
return Some(steps);
}
let x = pos % data.width;
let y = pos / data.width;
for (chk, nxt) in [
(x > 0, pos as isize - 1),
(x < data.width - 1, pos as isize + 1),
(y > 0, pos as isize - data.width as isize),
(y < height - 1, pos as isize + data.width as isize),
] {
if chk && !seen[nxt as usize] && data.grid[nxt as usize] <= data.grid[pos] + 1 {
queue.push_back((steps + 1, nxt as _));
seen[nxt as usize] = true;
}
}
}
None
}
pub fn star_1(data: &PuzzleData) -> usize {
shortest_path(data, data.start).unwrap()
}
Star 2
Just perform shortest path calculation for all possible starting positions (that was my solution to submit the answer)
1
2
3
4
5
6
7
pub fn star_2_original(data: &PuzzleData) -> usize {
(0..data.grid.len())
.filter(|&k| data.grid[k] == b'a')
.filter_map(|start| shortest_path(data, start))
.min()
.unwrap()
}
Then I realized it is much simpler if I just reverse the search direction and look for the shortest path from the target to any 'a'. So I did that to have another sub 1ms solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
pub fn shortest_path_2<F, G>(
data: &PuzzleData,
starts: &[usize],
reached: F,
check: G,
) -> Option<usize>
where
F: Fn(usize) -> bool,
G: Fn(u8, u8) -> bool,
{
let mut queue = VecDeque::new();
let mut seen = vec![false; data.grid.len()];
for start in starts {
queue.push_back((0, *start));
seen[*start] = true;
}
let height = data.grid.len() / data.width;
while let Some((steps, pos)) = queue.pop_front() {
if reached(pos) {
return Some(steps);
}
let x = pos % data.width;
let y = pos / data.width;
for (chk, nxt) in [
(x > 0, pos as isize - 1),
(x < data.width - 1, pos as isize + 1),
(y > 0, pos as isize - data.width as isize),
(y < height - 1, pos as isize + data.width as isize),
] {
if chk && !seen[nxt as usize] && check(data.grid[pos], data.grid[nxt as usize]) {
queue.push_back((steps + 1, nxt as _));
seen[nxt as usize] = true;
}
}
}
None
}
pub fn star_2(data: &PuzzleData) -> usize {
shortest_path_2(
data,
&[data.target],
|pos| data.grid[pos] == b'a',
|f, t| f <= t + 1,
)
.unwrap()
}
The shortest_path_2 function is generic to also work for part 1, but I did not change it in my code. Here is how to call it:
shortest_path_2(data, data.start, |pos| pos == data.target, |f, t| t <= f + 1).unwrap()Tests
And the mandatory tests. But be careful, if a test of the type expected == actual fails, there are two possible reasons: actual can be wrong or expected can be wrong.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
assert_eq!(8, data.width);
assert_eq!(0, data.start);
assert_eq!(21, data.target);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(31, star_1(&data));
// use general method
assert_eq!(
31,
shortest_path_2(
&data,
&[data.start],
|pos| pos == data.target,
|f, t| t <= f + 1
).unwrap()
);
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
// search backwards
assert_eq!(29, star_2(&data));
// search forward from all starts one by one and take min
assert_eq!(29, star_2_original(&data));
// search forward from all a simultaneously (Thomas' idea)
assert_eq!(29, star_2_variant(&data));
}
}
Day 13: Distress Signal
Rust solution to AoC|2022|13.
My initial solution was based on "If the input looks like a tree structure, parse it into a tree structure!"
Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub mod input {
use super::node::Node;
pub struct PuzzleData {
pub nodes: Vec<Node>,
}
impl<'a> From<&'a str> for PuzzleData {
fn from(s: &'a str) -> Self {
Self {
nodes: s
.lines()
.filter(|l| !l.is_empty())
.map(Node::from)
.collect(),
}
}
}
}
Solution
The whole work for the solution is in the recursive Node enum modeling the trees represented by the puzzle input with its implementation. Namely recursive parsing in the parse function and comparison in the Ord trait implementation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
pub mod node {
//! Tree structure for recursive lists from puzzle
use std::cmp::Ordering;
#[derive(Debug, Eq, PartialEq, Clone)]
pub enum Node {
List(Box<[Node]>),
Value(usize),
}
impl std::fmt::Display for Node {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Node::List(list) => {
'['.fmt(f)?;
for n in list.iter().take(1) {
n.fmt(f)?;
}
for n in list.iter().skip(1) {
','.fmt(f)?;
n.fmt(f)?;
}
']'.fmt(f)?;
}
Node::Value(value) => value.fmt(f)?,
}
Ok(())
}
}
impl<T> From<T> for Node
where
T: AsRef<[u8]>,
{
fn from(s: T) -> Self {
Self::parse(s.as_ref(), 0).0
}
}
impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
match (self, other) {
(Node::List(lhs), Node::List(rhs)) => lhs.cmp(rhs),
(Node::Value(lhs), Node::Value(rhs)) => lhs.cmp(rhs),
(_, Node::Value(rhs)) => self.cmp(&Node::List(vec![Node::Value(*rhs)].into())),
(Node::Value(lhs), _) => Node::List(vec![Node::Value(*lhs)].into()).cmp(other),
}
}
}
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Node {
fn parse(s: &[u8], pos: usize) -> (Self, usize) {
if s[pos] == b'[' && s[pos + 1] == b']' {
// handle empty list separately
(Self::List(vec![].into()), 2)
} else if s[pos] == b'[' {
let mut v = Vec::new();
let mut len = 1;
loop {
let (n, l) = Self::parse(s, pos + len);
v.push(n);
len += l + 1;
if s[pos + len - 1] == b']' {
break;
}
}
(Self::List(v.into()), len)
} else {
let mut v = 0;
let mut len = 0;
while pos + len < s.len() && s[pos + len] >= b'0' && s[pos + len] <= b'9' {
v = v * 10 + (s[pos + len] - b'0') as usize;
len += 1;
}
(Self::Value(v), len)
}
}
}
}
Star 1
Do the pairwise comparisons.
1
2
3
4
5
6
7
8
9
pub fn star_1(data: &PuzzleData) -> usize {
data.nodes
.iter()
.step_by(2)
.zip(data.nodes.iter().skip(1).step_by(2))
.enumerate()
.filter(|(_, (a, b))| a.cmp(b) != Ordering::Greater)
.fold(0, |s, (k, _)| s + k + 1)
}
Star 2
Find the position of the divider packets after sorting.
1
2
3
4
5
6
7
8
9
10
11
pub fn star_2(data: &PuzzleData) -> usize {
let mut v = data.nodes.clone();
v.push(Node::from("[[2]]"));
v.push(Node::from("[[6]]"));
v.sort_unstable();
let a = v.iter().position(|n| n == &Node::from("[[2]]")).unwrap();
let b = v.iter().position(|n| n == &Node::from("[[6]]")).unwrap();
(a + 1) * (b + 1)
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#[cfg(test)]
mod tests {
use super::*;
use crate::tree::node::Node;
#[test]
pub fn test_parse() {
let s = "[1,[2,[3,[4,[5,6,7]]]],8,9]";
let n = Node::from(s);
println!("{n:?}");
assert_eq!(s, n.to_string());
}
#[test]
pub fn test_cmp() {
let nodes = PuzzleData::from(crate::tests::CONTENT).nodes;
let cmp = nodes
.iter()
.step_by(2)
.zip(nodes.iter().skip(1).step_by(2))
.map(|(a, b)| a.cmp(b))
.collect::<Vec<_>>();
println!("{cmp:?}");
assert_eq!(
vec![
Ordering::Less,
Ordering::Less,
Ordering::Greater,
Ordering::Less,
Ordering::Greater,
Ordering::Less,
Ordering::Greater,
Ordering::Greater
],
cmp
);
}
#[test]
pub fn test_star_1() {
assert_eq!(13, star_1(&PuzzleData::from(crate::tests::CONTENT)))
}
#[test]
pub fn test_star_2() {
assert_eq!(140, star_2(&PuzzleData::from(crate::tests::CONTENT)))
}
}
Alternative without using heap
Later on, I thought it should be possible to implement a solution that does not require any heap allocations by directly iterating on the input data. I added this in a variant of my solution in mod iter. You can run this variant using cargo run --release --features no-heap. Interestingly it is not really performing any better than the original solution. The advantage for the second part is probably mainly caused by avoiding to sort.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
pub mod iter {
use self::node::List;
use self::{input::PuzzleData, node::Node};
use mr_kaffee_aoc::{Puzzle, Star};
use std::cmp::Ordering;
/// the puzzle
pub fn puzzle() -> Puzzle<'static, PuzzleData<'static>, usize> {
Puzzle {
year: 2022,
day: 13,
input: include_str!("../../../input/2022/day13.txt"),
star1: Some(Star {
name: "Star 1",
f: &star_1,
exp: Some(5_675),
}),
star2: Some(Star {
name: "Star 2",
f: &star_2,
exp: Some(20_383),
}),
}
}
pub mod input {
pub struct PuzzleData<'a> {
pub input: &'a str,
}
impl<'a> From<&'a str> for PuzzleData<'a> {
fn from(input: &'a str) -> Self {
Self { input }
}
}
}
pub mod node {
use std::{cmp::Ordering, iter::once};
#[derive(Debug, Clone)]
pub struct List<'a> {
data: &'a [u8],
pos: usize,
}
#[derive(Debug, Clone)]
pub enum Node<'a> {
List(List<'a>),
Value(usize),
}
impl std::fmt::Display for Node<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Node::List(list) => list.fmt(f),
Node::Value(value) => value.fmt(f),
}
}
}
impl<'a> From<&'a str> for Node<'a> {
fn from(s: &'a str) -> Self {
if s.starts_with('[') {
Self::List(List::from(s))
} else {
Self::Value(s.parse().unwrap())
}
}
}
impl std::fmt::Display for List<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let mut level = 1;
'['.fmt(f)?;
for &b in &self.data[self.pos..] {
level = match b {
b'[' => level + 1,
b']' => level - 1,
_ => level,
};
(b as char).fmt(f)?;
if level == 0 {
break;
}
}
Ok(())
}
}
impl<'a> From<&'a [u8]> for List<'a> {
fn from(s: &'a [u8]) -> Self {
let data = s;
let pos = if data[0] == b'[' { 1 } else { 0 };
Self { data, pos }
}
}
impl<'a> From<&'a str> for List<'a> {
fn from(s: &'a str) -> Self {
Self::from(s.as_bytes())
}
}
impl<'a> Iterator for List<'a> {
type Item = Node<'a>;
fn next(&mut self) -> Option<Self::Item> {
if self.pos >= self.data.len() || self.data[self.pos] == b']' {
// exhausted
None
} else if self.data[self.pos] == b'[' {
// parse list
let nxt = Self::Item::List(List::from(&self.data[self.pos..]));
// advance pos to after list
self.pos += 2 + self.data[self.pos + 1..]
.iter()
.scan(1usize, |level, b| {
match b {
b'[' => *level += 1,
b']' => *level -= 1,
_ => (),
};
Some(*level)
})
.position(|level| level == 0)
.unwrap();
// skip ',' if applicable
if self.pos < self.data.len() && self.data[self.pos] == b',' {
self.pos += 1;
}
// return list
Some(nxt)
} else {
// parse value
let mut v = 0;
while self.data[self.pos].is_ascii_digit() {
// parse digit
v = 10 * v + (self.data[self.pos] - b'0') as usize;
self.pos += 1;
}
// skip ',' if applicable
if self.pos < self.data.len() && self.data[self.pos] == b',' {
self.pos += 1;
}
// return value
Some(Self::Item::Value(v))
}
}
}
impl Ord for Node<'_> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
match (self, other) {
(Node::Value(lhs), Node::Value(rhs)) => lhs.cmp(rhs),
(Node::List(lhs), Node::List(rhs)) => lhs.clone().cmp(rhs.clone()),
(Node::List(lhs), rhs) => lhs.clone().cmp(once(rhs.clone())),
(lhs, Node::List(rhs)) => once(lhs.clone()).cmp(rhs.clone()),
}
}
}
impl PartialOrd for Node<'_> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl PartialEq for Node<'_> {
fn eq(&self, other: &Self) -> bool {
self.cmp(other) == Ordering::Equal
}
}
impl Eq for Node<'_> {}
}
pub fn star_1(data: &PuzzleData) -> usize {
let mut lines = data.input.lines().filter(|l| !l.is_empty());
let mut idx = 0;
let mut result = 0;
while let (Some(a), Some(b)) = (lines.next(), lines.next()) {
idx += 1;
if Node::from(a).cmp(&Node::from(b)) != Ordering::Greater {
result += idx;
}
}
result
}
pub fn star_2(data: &PuzzleData) -> usize {
let n_1 = List::from("[[2]]");
let n_2 = List::from("[[6]]");
let (cnt_1, cnt_2) =
data.input
.lines()
.filter(|l| !l.is_empty())
.fold((1, 2), |(cnt_1, cnt_2), l| {
if n_1.clone().cmp(List::from(l)) == Ordering::Greater {
(cnt_1 + 1, cnt_2 + 1)
} else if n_2.clone().cmp(List::from(l)) == Ordering::Greater {
(cnt_1, cnt_2 + 1)
} else {
(cnt_1, cnt_2)
}
});
cnt_1 * cnt_2
}
#[cfg(test)]
mod tests {
use super::*;
use crate::iter::node::{List, Node};
#[test]
pub fn test_next() {
let mut list = List::from("[10,[[9,10,0],2]]");
assert_eq!(Some("10".into()), list.next().map(|n| n.to_string()));
assert_eq!(
Some("[[9,10,0],2]".into()),
list.next().map(|n| n.to_string())
);
assert!(list.next().is_none());
}
#[test]
pub fn test_cmp() {
let nodes = crate::tests::CONTENT
.lines()
.filter(|l| !l.is_empty())
.map(List::from)
.map(Node::List)
.collect::<Vec<_>>();
let cmp = nodes
.iter()
.step_by(2)
.zip(nodes.iter().skip(1).step_by(2))
.map(|(a, b)| a.cmp(b))
.collect::<Vec<_>>();
println!("{cmp:?}");
assert_eq!(
vec![
Ordering::Less,
Ordering::Less,
Ordering::Greater,
Ordering::Less,
Ordering::Greater,
Ordering::Less,
Ordering::Greater,
Ordering::Greater
],
cmp
);
}
#[test]
pub fn test_star_1() {
assert_eq!(13, star_1(&PuzzleData::from(crate::tests::CONTENT)))
}
#[test]
pub fn test_star_2() {
assert_eq!(140, star_2(&PuzzleData::from(crate::tests::CONTENT)))
}
}
}
Day 14: Regolith Reservoir
Rust solution to AoC|2022|14.
I was remembered of AoC|2018|17 even without the hint in the puzzle.
I don’t think my solution is very elegant, but at the moment, I do not have an idea how to create a nice one …
Input
I parse the input in a vec of paths, where each path is vec of points. The structure PuzzleData has methods to compute the bounding box for all points (bbox) and build a 2D grid using the paths specified (grid).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
paths: Vec<Vec<(isize, isize)>>,
}
impl<'a> From<&'a str> for PuzzleData {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self {
paths: s
.lines()
.map(|l| {
l.split(" -> ")
.map(|c| c.split_once(',').unwrap())
.map(|(x, y)| (x.parse().unwrap(), y.parse().unwrap()))
.collect()
})
.collect(),
}
}
}
impl PuzzleData {
pub fn bbox(&self) -> (isize, isize, isize, isize) {
self.paths.iter().fold((500, 0, 501, 1), |bbox, v| {
v.iter().fold(bbox, |(x_mn, y_mn, x_mx, y_mx), (x, y)| {
(x_mn.min(*x), y_mn.min(*y), x_mx.max(x + 1), y_mx.max(y + 1))
})
})
}
/// get a grid as flat list of chars, the width of the grid, and the point of sand inflow
pub fn grid(&self) -> (Vec<char>, usize, (usize, usize)) {
let (x_mn, y_mn, x_mx, y_mx) = self.bbox();
let width = (x_mx - x_mn) as usize;
let height = (y_mx - y_mn) as usize;
let mut grid = vec!['.'; width * height];
for path in &self.paths {
for k in 1..path.len() {
let (dx, dy, len) = if path[k].0 > path[k - 1].0 {
assert!(path[k].1 == path[k - 1].1);
(1, 0, path[k].0 - path[k - 1].0)
} else if path[k].0 < path[k - 1].0 {
assert!(path[k].1 == path[k - 1].1);
(-1, 0, path[k - 1].0 - path[k].0)
} else if path[k].1 > path[k - 1].1 {
assert!(path[k].0 == path[k - 1].0);
(0, 1, path[k].1 - path[k - 1].1)
} else if path[k].1 < path[k - 1].1 {
assert!(path[k].0 == path[k - 1].0);
(0, -1, path[k - 1].1 - path[k].1)
} else {
unreachable!()
};
let x0 = path[k - 1].0 - x_mn;
let y0 = path[k - 1].1 - y_mn;
for k in 0..len + 1 {
grid[(x0 + dx * k) as usize + (y0 + dy * k) as usize * width] = '#';
}
}
}
(grid, width, ((500 - x_mn) as _, (0 - y_mn) as _))
}
}
}
Star 1
Just let the sand flow in the grid until sand starts flowing off to the big void.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
pub fn star_1(data: &PuzzleData) -> usize {
let (mut grid, width, (x_0, y_0)) = data.grid();
let height = grid.len() / width;
let mut cnt = 0;
'inflow: loop {
// first candidate is spot directly on top of something solid
let mut x = x_0;
let mut y = match (y_0..height).find(|y| grid[x + y * width] != '.') {
Some(y) => y - 1,
None => unreachable!("Nothing solid found to start with"),
};
loop {
if y == height - 1 {
// go to void below
break 'inflow;
}
if grid[x + (y + 1) * width] == '.' {
// bubble down
y += 1;
} else if x > 0 && grid[x - 1 + (y + 1) * width] == '.' {
// bubble down-left
y += 1;
x -= 1;
} else if x < width - 1 && grid[x + 1 + (y + 1) * width] == '.' {
// bubble down-right
y += 1;
x += 1;
} else if x == 0 || x == width - 1 {
// go to void left/right
break 'inflow;
} else {
grid[x + y * width] = 'o';
cnt += 1;
break;
}
}
}
cnt
}
Star 2
Create a grid with an additional line added at the bottom and big enough to make sure nothing flows off to the void anymore. The only thing on top to do is to change the condition for exiting the loop.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
pub fn star_2(data: &PuzzleData) -> usize {
let (grid_0, width_0, (x_0_0, y_0)) = data.grid();
let height_0 = grid_0.len() / width_0;
// wrap the grid in a bigger grid (append height columns to the left and right and an additional row below)
let width = width_0 + 2 * height_0;
let height = height_0 + 1;
let mut grid = vec!['.'; width * height];
for y in 0..height_0 {
for x in 0..width_0 {
grid[x + height_0 + y * width] = grid_0[x + y * width_0];
}
}
let x_0 = x_0_0 + height_0;
let mut cnt = 0;
loop {
// first candidate is spot directly on top of something solid
let mut x = x_0;
let mut y = match (y_0..height).find(|y| grid[x + y * width] != '.') {
Some(y) => {
if y == y_0 {
// No more sand can enter
break;
}
y - 1
}
None => unreachable!("Nothing solid found to start with"),
};
loop {
if y == height - 1 {
// floor reached
grid[x + y * width] = 'o';
cnt += 1;
break;
}
if grid[x + (y + 1) * width] == '.' {
// bubble down
y += 1;
} else if x > 0 && grid[x - 1 + (y + 1) * width] == '.' {
// bubble down-left
y += 1;
x -= 1;
} else if x < width - 1 && grid[x + 1 + (y + 1) * width] == '.' {
// bubble down-right
y += 1;
x += 1;
} else if x == 0 || x == width - 1 {
// the grid should not be too small
unreachable!("Grid is too small!");
} else {
// cannot move any further
grid[x + y * width] = 'o';
cnt += 1;
break;
}
}
}
cnt
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
let bbox = data.bbox();
assert_eq!((494, 0, 504, 10), bbox);
let (grid, width, (x0, y0)) = data.grid();
assert_eq!((6, 0), (x0, y0));
assert_eq!(10, width);
let exp = "............................................#...##....#...#...###...#.........#.........#.#########.";
assert_eq!(exp.chars().collect::<Vec<_>>(), grid);
for row in 0..grid.len() / width {
for col in 0..width {
print!("{}", grid[col + row * width]);
}
println!();
}
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(24, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(93, star_2(&data));
}
}
Day 15: Beacon Exclusion Zone
Rust solution to AoC|2022|15.
This one was a challenge for me. Part one was initially solved with brute force. My current solution projects ranges on the row to scan.
For part 2, brute force was not a real option.
Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
pub mod input {
use crate::{SensorRaw, SensorWithR};
#[derive(Debug)]
pub struct PuzzleData {
sensors: Vec<SensorRaw>,
pub row: isize,
pub width: isize,
}
fn parse_line(l: &str) -> SensorRaw {
let words = l.split_ascii_whitespace();
let mut words = words.skip(2); // Sensor at
let x_s = words.next().unwrap();
let x_s = x_s.strip_prefix("x=").unwrap().strip_suffix(',').unwrap();
let x_s = x_s.parse().unwrap();
let y_s = words.next().unwrap();
let y_s = y_s.strip_prefix("y=").unwrap().strip_suffix(':').unwrap();
let y_s = y_s.parse().unwrap();
let mut words = words.skip(4); // closest beacon is at
let x_b = words.next().unwrap();
let x_b = x_b.strip_prefix("x=").unwrap().strip_suffix(',').unwrap();
let x_b = x_b.parse().unwrap();
let y_b = words.next().unwrap();
let y_b = y_b.strip_prefix("y=").unwrap();
let y_b = y_b.parse().unwrap();
((x_s, y_s), (x_b, y_b))
}
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self {
sensors: s.lines().map(parse_line).collect(),
row: 2_000_000,
width: 4_000_000,
}
}
}
impl PuzzleData {
pub fn sensors(&self) -> &[SensorRaw] {
&self.sensors
}
pub fn sensors_with_r(&self) -> Vec<SensorWithR> {
self.sensors
.iter()
.map(|((x, y), (x_b, y_b))| ((*x, *y), (x - x_b).abs() + (y - y_b).abs()))
.collect()
}
}
}
Star 1
Project ranges
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/// determine ranges covered by sensors on given row
pub fn ranges(sensors: &[SensorRaw], mn: isize, mx: isize, row: isize) -> Vec<(isize, isize)> {
sensors
.iter()
.map(|((x, y), (x_b, y_b))| (*x, (x - x_b).abs() + (y - y_b).abs() - (y - row).abs()))
.map(|(x, d)| ((x - d).max(mn), (x + d).min(mx)))
.filter(|(mn, mx)| mx >= mn)
.fold(Vec::new(), |mut ranges, range| {
ranges.push(range);
let mut k_2 = ranges.len() - 1;
for k_1 in (0..ranges.len() - 1).rev() {
if ranges[k_1].0 <= ranges[k_2].0 && ranges[k_1].1 >= ranges[k_2].1 {
// k_2 contained in k_1
ranges.swap_remove(k_2);
break;
} else if ranges[k_2].0 <= ranges[k_1].0 && ranges[k_2].1 >= ranges[k_1].1 {
// k_1 contained in k_2
ranges.swap_remove(k_1);
k_2 = if k_2 == ranges.len() { k_1 } else { k_2 };
} else if ranges[k_2].0 >= ranges[k_1].0 && ranges[k_2].0 <= ranges[k_1].1 + 1 {
// k_2's min in k_1 or immediately after
ranges[k_1].1 = ranges[k_2].1;
ranges.swap_remove(k_2);
k_2 = k_1;
} else if ranges[k_2].1 >= ranges[k_1].0 - 1 && ranges[k_2].1 <= ranges[k_1].1 {
// k_2's max in k_1 or immediately before
ranges[k_1].0 = ranges[k_2].0;
ranges.swap_remove(k_2);
k_2 = k_1;
}
}
ranges
})
}
pub fn star_1(data: &PuzzleData) -> usize {
let ranges: Vec<(isize, isize)> = ranges(data.sensors(), isize::MIN, isize::MAX, data.row);
let r = ranges
.iter()
.map(|(mn, mx)| (mx - mn + 1) as usize)
.sum::<usize>();
let s = data
.sensors()
.iter()
.filter(|(_, (_, y))| *y == data.row)
.map(|(_, b)| b)
.collect::<HashSet<_>>()
.len();
r - s
}
Star 2
The idea is that the position of the distress beacon must be just outside the range of at least two sensors. Hence, for all pairs of sensors, I find the points that are just outside of both sensor’s ranges as candidates. Out of these candidates, I search for a point that is also outside of all the other sensor’s ranges.
Well … it works. But coming up with the formulas for the points was a pain and very error prone for me. I am sure there is something more elegant and simple.
There is also a flaw in the candidates function. Normally, it should be symmetric, i.e., candidates(s1, s2) == candidates(s2, s1); it is not in all cases. I guess this is rounding issues … It seems the function returns rather too many candidates than too few, which would not be an issue.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
pub type SensorWithR = ((isize, isize), isize);
pub fn is_distress_beacon(sensors: &[SensorWithR], p: &(isize, isize), width: isize) -> bool {
(0..=width).contains(&p.0)
&& (0..=width).contains(&p.1)
&& sensors
.iter()
.all(|((x, y), r)| (x - p.0).abs() + (y - p.1).abs() > *r)
}
pub fn candidates(
(((x_1, y_1), r_1), ((x_2, y_2), r_2)): (&SensorWithR, &SensorWithR),
) -> HashSet<(isize, isize)> {
let dx = x_2 - x_1;
let dy = y_2 - y_1;
let dr = r_2 - r_1;
[
// TL - RT
// x1+(dx+dy-dr)/2,y1-r1-1+(dx+dy-dr)/2
(
x_1 + (dx + dy - dr + 1) / 2,
y_1 - r_1 - 1 + (dx + dy - dr) / 2,
),
(x_1 + (dx + dy - dr) / 2, y_1 - r_1 - 1 + (dx + dy - dr) / 2),
// LB - BR
// x1+(dx+dy+dr)/2,y1+r1+1+(dx+dy+dr)/2
(
x_1 + (dx + dy + dr - 1) / 2,
y_1 + r_1 + 1 + (dx + dy + dr) / 2,
),
(x_1 + (dx + dy + dr) / 2, y_1 + r_1 + 1 + (dx + dy + dr) / 2),
// RT - TL
// x1+(dx-dy+dr)/2,y1-r1-1-(dx-dy+dr)/2
(
x_1 + (dx - dy + dr - 1) / 2,
y_1 - r_1 - 1 - (dx - dy + dr) / 2,
),
(x_1 + (dx - dy + dr) / 2, y_1 - r_1 - 1 - (dx - dy + dr) / 2),
// BR - LB
// x1+(dx-dy-dr)/2,y1+r1+1-(dx-dy-dr)/2
(
x_1 + (dx - dy - dr + 1) / 2,
y_1 + r_1 + 1 - (dx - dy - dr) / 2,
),
(x_1 + (dx - dy - dr) / 2, y_1 + r_1 + 1 - (dx - dy - dr) / 2),
// LB - TL
// x1-r1-1+(dx+dy-dr)/2,y1+(dx+dy-dr)/2
(
x_1 - r_1 - 1 + (dx + dy - dr) / 2,
y_1 + (dx + dy - dr + 1) / 2,
),
(x_1 - r_1 - 1 + (dx + dy - dr) / 2, y_1 + (dx + dy - dr) / 2),
// BR - RT
// x1+r1+1+(dx-dy+dr)/2,y1-(dx-dy+dr)/2
(
x_1 + r_1 + 1 + (dx - dy + dr) / 2,
y_1 - (dx - dy + dr - 1) / 2,
),
(x_1 + r_1 + 1 + (dx - dy + dr) / 2, y_1 - (dx - dy + dr) / 2),
// TL - LB
// x1-r1-1+(dx-dy-dr)/2,y1-(dx-dy-dr)/2
(
x_1 - r_1 - 1 + (dx - dy - dr) / 2,
y_1 - (dx - dy - dr + 1) / 2,
),
(x_1 - r_1 - 1 + (dx - dy - dr) / 2, y_1 - (dx - dy - dr) / 2),
// RT - BR
// x2+r2+1+(dx+dy+dr)/2,y2+(dx+dy+dr)/2
(
x_1 + r_1 + 1 + (dx + dy + dr) / 2,
y_1 + (dx + dy + dr - 1) / 2,
),
(x_1 + r_1 + 1 + (dx + dy + dr) / 2, y_1 + (dx + dy + dr) / 2),
]
.into_iter()
.filter(|(x, y)| {
(1..=2).contains(&((x - x_1).abs() + (y - y_1).abs() - r_1))
&& (1..=2).contains(&((x - x_2).abs() + (y - y_2).abs() - r_2))
})
.collect()
}
#[cfg(not(feature="scan"))]
fn star_2_geometry(data: &PuzzleData) -> usize {
let sensors = data.sensors_with_r();
let (x, y) = sensors
.iter()
.zip(sensors.iter().skip(1))
.map(candidates)
.flat_map(HashSet::into_iter)
.find(|p| is_distress_beacon(&sensors, p, data.width))
.unwrap();
(x * 4_000_000 + y) as _
}
Star 2 — Scan Lines
A solution using the functionality from star 1 is as follows. Much simpler code but much longer run-time.
1
2
3
4
5
6
7
8
9
10
pub fn star_2_scan_lines(data: &PuzzleData) -> usize {
let (y, ranges) = (0..data.width)
.map(|row| (row, ranges(data.sensors(), 0, data.width, row)))
.find(|(_, r)| r.len() == 2)
.unwrap();
let x = ranges[0].0.max(ranges[1].0) - 1;
(x * 4_000_000 + y) as _
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3
"#;
#[test]
pub fn test_is_distress_beacon() {
let data = PuzzleData::from(CONTENT);
let sensors = data.sensors_with_r();
assert!(is_distress_beacon(&sensors, &(14, 11), 20));
}
#[test]
pub fn test_candidates() {
// 0...#..%...
// 1..#.#%.%..
// 2.#.A%#B.%.
// 3..#.#%.%..
// 4...#..%...
// 0123456789
let s1 = ((3, 2), 2);
let s2 = ((6, 2), 2);
let e = HashSet::from([(4, 0), (5, 0), (4, 4), (5, 4)]);
assert_eq!(
e,
candidates((&s1, &s2)).intersection(&e).cloned().collect()
);
assert_eq!(
e,
candidates((&s2, &s1)).intersection(&e).cloned().collect()
);
// 0...#...%..
// 1..#.#.%.%.
// 2.#.A.$.B.%
// 3..#.#.%.%.
// 4...#...%..
// 0123456789
//
// RT: [x1 + r1 + 1 - k1, y1 - k1];
// TL: [x2 - k2, y2 - r2 - 1 + k2];
// [x1+(dx+dy-dr)/2,y1-r1-1+(dx+dy-dr)/2];
// --- [x1+(dx-dy+dr)/2,y1-r1-1-(dx-dy+dr)/2];
//
// BR: [x1 + k1, y1 + r1 + 1 - k1];
// LB: [x2 - r2 - 1 + k2, y2 + k2];
// [x1+(dx-dy-dr)/2,y1+r1+1-(dx-dy-dr)/2];
// --- [x1+(dx+dy+dr)/2,y1+r1+1+(dx+dy+dr)/2];
let s1 = ((3, 2), 2);
let s2 = ((7, 2), 2);
let e = HashSet::from([(5, 1), (5, 3)]);
assert_eq!(
e,
candidates((&s1, &s2)).intersection(&e).cloned().collect()
);
assert_eq!(
e,
candidates((&s2, &s1)).intersection(&e).cloned().collect()
);
// 0...#....
// 1..#.#...
// 2.#.A%#..
// 3..#%#%..
// 4..%#..%.
// 5.%..B..%
// 6..%...%.
// 7...%.%..
// 8....%...
// 01234567
// LB: [x1 - r1 - 1 + k1, y1 + k1];
// TL: [x2 - k2, y2 - r2 - 1 + k2];
// [x1-r1-1+(dx+dy-dr)/2,y1+(dx+dy-dr)/2]
// --- [x1-r1-1+(dx-dy-dr)/2,y1-(dx-dy-dr)/2]
let s1 = ((3, 2), 2);
let s2 = ((4, 5), 3);
let e = HashSet::from([(1, 3), (1, 4), (6, 2), (6, 3)]);
assert_eq!(
e,
candidates((&s1, &s2)).intersection(&e).cloned().collect()
);
assert_eq!(
e,
candidates((&s2, &s1)).intersection(&e).cloned().collect()
);
// 0...#...
// 1..#.#..
// 2.#.A.#.
// 3..#.#..
// 4...$...
// 5.-%.%..
// 6.%.B.%.
// 7..%.%..
// 8...%...
// 0123456
let s1 = ((3, 2), 2);
let s2 = ((3, 6), 2);
let e = HashSet::from([(2, 4), (4, 4)]);
assert_eq!(
e,
candidates((&s1, &s2)).intersection(&e).cloned().collect()
);
assert_eq!(
e,
candidates((&s2, &s1)).intersection(&e).cloned().collect()
);
}
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let mut data = PuzzleData::from(CONTENT);
data.row = 10;
assert_eq!(26, star_1(&data));
}
#[test]
pub fn test_solve_2() {
let mut data = PuzzleData::from(CONTENT);
data.width = 20;
#[cfg(not(feature="scan"))]
assert_eq!(56_000_011, star_2_geometry(&data));
assert_eq!(56_000_011, star_2_scan_lines(&data));
assert_eq!(56_000_011, star_2_brute_force(&data));
}
}
Day 16: Proboscidea Volcanium
Rust solution to AoC|2022|16.
Today was a tough nut to crack for me.
My first attempt was to use a path finding algorithm that decides in every time step what to do next.
After some iterations, I implemented a path finding algorithm that uses pre-calculated shortest paths from one valve to another including the time to open the other valve. The path traversal is done in a highest potential first order (A* like), where the potential is the maximum pressure released if all valves are reached in the least possible time starting from the current position.
For part 1, the path traversal is straight forward. For part 2, in each step either the human or the elephant moves to the next valve and opens it. Quite a bit of time is saved by realizing that the two are actually interchangeable, which is realized by always storing positions of the two in a canonical (sorted) way.
The A* like traversal yields the following properties:
-
If a state is expanded, it is guaranteed that all adjacent states have at most the same potential. They will have equal potential if and only if all valves with positive flow are open. In all other cases, they will have lower potential.
-
If a state is popped from the queue, all states popped later on will have at most the same potential.
-
The potential of the first state popped from the queue with all valves open is the max. possible pressure.
Input
First, I parse the input into a vec of valves, where each valve has its tunnels stored as vec of indices to that list for cheap lookups. Then, as part of the input processing, I compute the shortest paths for all pairs of relevant valves (valves with zero flow which are not the starting valve can be ignored).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
pub mod input {
use crate::ValveMap;
use std::{
collections::{HashMap, HashSet, VecDeque},
iter::once,
};
fn parse_line(line: &str) -> (&str, Vec<&str>, usize) {
let mut words = line.split_ascii_whitespace().skip(1);
let name = words.next().unwrap();
let mut words = words.skip(2);
let flow = words.next().unwrap();
let flow = flow[5..flow.len() - 1].parse().unwrap();
let tunnels = words
.skip(4)
.map(|word| word.trim_end_matches(','))
.collect();
(name, tunnels, flow)
}
impl From<&str> for ValveMap {
/// parse the puzzle input
fn from(s: &str) -> Self {
let lines = s.lines().map(parse_line).collect::<Vec<_>>();
let valves_0: Vec<Valve> = lines
.iter()
.enumerate()
.map(|(idx, (name, tunnels, flow))| Valve {
name,
idx,
flow: *flow,
tunnels: tunnels
.iter()
.map(|&tunnel| {
lines
.iter()
.position(|&(name, _, _)| name == tunnel)
.unwrap()
})
.collect(),
})
.collect();
let root = lines.iter().position(|&(name, _, _)| name == "AA").unwrap();
debug_assert!(
valves_0.iter().all(|v| {
v.tunnels
.iter()
.all(|&adj| valves_0[adj].tunnels.contains(&v.idx))
}),
"Asymmetric valve system"
);
debug_assert!(
valves_0[root].flow == 0,
"Root has non-zero flow: {:?}",
valves_0[root]
);
// root and all valves with non-zero flow
let valves = once(&valves_0[root])
.chain(valves_0.iter().filter(|v| v.flow > 0))
.collect::<Vec<_>>();
let len = valves.len();
debug_assert!(
len <= usize::BITS as _,
"open valves cannot be encoded in usize: {} > {}",
len,
usize::BITS
);
let mut distances = vec![usize::MAX; len * len];
for p_1 in 0..len {
distances[p_1 + len * p_1] = 0;
let mut targets = (p_1 + 1..len)
.map(|p_2| (valves[p_2].idx, p_2))
.collect::<HashMap<_, _>>();
let mut queue = VecDeque::from([(valves[p_1].idx, 0)]);
let mut seen = HashSet::from([valves[p_1].idx]);
while let Some((idx, dist)) = queue.pop_front() {
if let Some(p_2) = targets.remove(&idx) {
// + 1 because one step is required to open the valve
distances[p_1 + len * p_2] = dist + 1;
distances[p_2 + len * p_1] = dist + 1;
}
if targets.is_empty() {
break;
}
for &adj in valves_0[idx].tunnels.iter() {
if seen.insert(adj) {
queue.push_back((adj, dist + 1));
}
}
}
}
Self {
len,
distances,
flows: valves.iter().map(|valve| valve.flow).collect(),
root: 0,
}
}
}
#[derive(Debug, PartialEq, Eq)]
struct Valve<'a> {
idx: usize,
name: &'a str,
flow: usize,
tunnels: Vec<usize>,
}
}
Star 1
Solution with a single agent (me).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
pub fn star_1(map: &ValveMap) -> usize {
let idx = map.root();
let t = 30;
let open: usize = 1 << map.root();
let rel = 0;
let potential = map.potential(&[idx], &[t], open, rel);
let mut queue = BinaryHeap::from([(potential, rel, t, idx, open)]);
let mut seen = HashMap::from([((idx, open), (potential, rel))]);
while let Some((pot_0, rel_0, t_0, idx_0, open_0)) = queue.pop() {
if pot_0 == rel_0 {
return rel_0;
}
for idx_1 in (0..map.len()).filter(|adj| ((open_0 >> adj) & 1) == 0) {
let d = map.distance(idx_0, idx_1);
if d < t_0 {
let t_1 = t_0 - d;
let rel_1 = rel_0 + (t_0 - d) * map.flow(idx_1);
let open_1 = open_0 | (1 << idx_1);
let pot_1 = map.potential(&[idx_1], &[t_1], open_1, rel_1);
let entry = seen.entry((idx_1, open_1)).or_insert((0, 0));
if (pot_1, rel_1).gt(entry) {
*entry = (pot_1, rel_1);
queue.push((pot_1, rel_1, t_1, idx_1, open_1));
}
}
}
}
unreachable!("No solution!")
}
Star 2
Same solution with two agents (me + elephant), not really anything new compared to star 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
pub fn star_2(map: &ValveMap) -> usize {
let idx = [map.root(); 2];
let t = [26; 2];
let open: usize = 1 << map.root();
let rel = 0;
let potential = map.potential(&idx, &t, open, rel);
let mut queue = BinaryHeap::from([(potential, rel, t, idx, open)]);
let mut seen = HashMap::from([((idx, open), (potential, rel))]);
while let Some((pot_0, rel_0, t_0, idx_0, open_0)) = queue.pop() {
if pot_0 == rel_0 {
return rel_0;
}
for adj in (0..map.len()).filter(|adj| ((open_0 >> adj) & 1) == 0) {
let d = [map.distance(idx_0[0], adj), map.distance(idx_0[1], adj)];
let open_1 = open_0 | (1 << adj);
if d[0] < t_0[0] {
let (idx_1, t_1) = if adj < idx_0[1] {
([adj, idx_0[1]], [t_0[0] - d[0], t_0[1]])
} else {
([idx_0[1], adj], [t_0[1], t_0[0] - d[0]])
};
let rel_1 = rel_0 + (t_0[0] - d[0]) * map.flow(adj);
let pot_1 = map.potential(&idx_1, &t_1, open_1, rel_1);
let entry = seen.entry((idx_1, open_1)).or_insert((0, 0));
if (pot_1, rel_1).gt(entry) {
*entry = (pot_1, rel_1);
queue.push((pot_1, rel_1, t_1, idx_1, open_1));
}
}
if d[1] < t_0[1] {
let (idx_1, t_1) = if adj < idx_0[0] {
([adj, idx_0[0]], [t_0[1] - d[1], t_0[0]])
} else {
([idx_0[0], adj], [t_0[0], t_0[1] - d[1]])
};
let rel_1 = rel_0 + (t_0[1] - d[1]) * map.flow(adj);
let pot_1 = map.potential(&idx_1, &t_1, open_1, rel_1);
let entry = seen.entry((idx_1, open_1)).or_insert((0, 0));
if (pot_1, rel_1).gt(entry) {
*entry = (pot_1, rel_1);
queue.push((pot_1, rel_1, t_1, idx_1, open_1));
}
}
}
}
unreachable!("No solution!")
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II
"#;
#[test]
pub fn test_valve_map_from() {
let distances = ValveMap::from(CONTENT);
println!("{:?}", distances);
}
#[test]
pub fn test_star_1() {
let map = ValveMap::from(CONTENT);
assert_eq!(1_651, star_1(&map));
}
#[test]
pub fn test_star_2() {
let map = ValveMap::from(CONTENT);
assert_eq!(1_707, star_2(&map));
}
}
Day 17: Pyroclastic Flow
Rust solution to AoC|2022|17.
So let’s play Tetris ;)
Because I made stupid bugs, I spent lots of time displaying the chamber and figuring out what I did wrong. My biggest mistake was to overwrite occupied space by empty space when a rock comes to rest and is not filling a full rectangle. Unfortunately, with this bug, I still get the correct result for the example data.
Part 2 is about finding a pattern that repeats itself. I do that by looking at the top 30 rows. The number 30 is kind of arbitrarily chosen.
Input
I just read the input in a byte array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub mod input {
#[derive(Debug)]
pub struct PuzzleData<'a> {
jets: &'a [u8],
}
impl<'a> From<&'a str> for PuzzleData<'a> {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self {
jets: s.trim().as_bytes(),
}
}
}
impl<'a> PuzzleData<'a> {
pub fn jets(&self) -> &'a [u8] {
self.jets
}
}
}
General solution
I have a struct Chamber with a method integrate_rock. This takes a rock and let’s it move in the chamber until it comes to rest.
My first version did not have the .filter(|&k| rock[k] == b'#') part in the update chamber loop at the end of the integrate_rock function. I typed these 29 characters with an average speed of about 12 character / hour.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
pub struct Chamber<'a> {
chamber: Vec<u8>,
jets: RingBuffer<'a, u8>,
rocks: RingBuffer<'static, (&'static str, usize)>,
}
impl<'a> From<&PuzzleData<'a>> for Chamber<'a> {
fn from(data: &PuzzleData<'a>) -> Self {
Self {
chamber: Vec::new(),
jets: data.jets().into(),
rocks: Self::ROCKS.into(),
}
}
}
impl Chamber<'_> {
const WIDTH: usize = 7;
const ROCKS: &'static [(&'static str, usize)] = &[
("####", 4),
(".#.###.#.", 3),
("###..#..#", 3),
("####", 1),
("####", 2),
];
const X0: usize = 2;
const DY0: usize = 3;
pub fn check(&self, rock: &[u8], x: usize, y: usize, w: usize) -> bool {
(0..rock.len())
.filter(|&k| rock[k] == b'#')
.filter(|k| y + k / w < self.height())
.all(|k| self.chamber[x + k % w + (y + k / w) * Self::WIDTH] == b'.')
}
pub fn height(&self) -> usize {
self.chamber.len() / Self::WIDTH
}
pub fn top(&self, rows: usize) -> (Vec<u8>, usize, usize) {
(
self.chamber[self.chamber.len() - rows * Self::WIDTH..].to_vec(),
self.rocks.pos(),
self.jets.pos(),
)
}
pub fn integrate_rock<F>(&mut self, f: F)
where
F: Fn(&[u8], &[u8], usize, usize, usize),
{
let &(rock, w) = self.rocks.successor();
let rock = rock.as_bytes();
let mut x = Self::X0;
let mut y = self.height() + Self::DY0;
let mut stop = false;
while !stop {
f(&self.chamber, rock, x, y, w);
let &jet = self.jets.successor();
x = if jet == b'<' && x > 0 && self.check(rock, x - 1, y, w) {
x - 1
} else if jet == b'>' && x + w < Chamber::WIDTH && self.check(rock, x + 1, y, w) {
x + 1
} else {
x
};
if y == 0 {
stop = true;
} else if y <= self.height() {
if self.check(rock, x, y - 1, w) {
y -= 1;
} else {
stop = true;
}
} else {
y -= 1;
}
if stop {
// add new lines to chamber
while self.height() < y + rock.len() / w {
self.chamber.extend([b'.'; Self::WIDTH])
}
// update chamber
for k in (0..rock.len()).filter(|&k| rock[k] == b'#') {
self.chamber[x + k % w + (y + k / w) * Self::WIDTH] = rock[k];
}
}
}
}
}
Star 1
Just integrate 2022 rocks.
1
2
3
4
5
6
7
8
9
pub fn star_1(data: &PuzzleData) -> usize {
let mut chamber = Chamber::from(data);
for _ in 0..2022 {
chamber.integrate_rock(|_, _, _, _, _| ());
}
chamber.height()
}
Star 2
Integrate rocks until a situation as defined by top rows of chamber, current jet position, current rock repeats. Calculate how much hight we gain by repeating this full cycle as often as it fits in the required number of rocks to integrate and simulate the remaining steps.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
pub fn star_2(data: &PuzzleData) -> usize {
let mut chamber = Chamber::from(data);
let mut seen = HashMap::new();
let rows = 30; // this is somehow arbitrary
let rounds: usize = 1_000_000_000_000;
let mut cnt = 0;
while chamber.height() < rows {
chamber.integrate_rock(|_, _, _, _, _| ());
cnt += 1;
}
for cur in cnt..rounds {
if let Some((prev, prev_height)) = seen.insert(chamber.top(rows), (cur, chamber.height())) {
let d_round = cur - prev;
let d_height = chamber.height() - prev_height;
let n = (rounds - cur) / d_round;
let h = n * d_height;
let rem = (rounds - cur) % d_round;
for _ in 0..rem {
chamber.integrate_rock(|_, _, _, _, _| ());
}
return chamber.height() + h;
}
chamber.integrate_rock(|_, _, _, _, _| ());
}
unreachable!()
}
Tests
Tests did not help a lot today.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#">>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(3_068, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(1_514_285_714_288, star_2(&data));
}
}
My testing approach was to print various configurations using very nice printing code. Obviously, I removed all the println! and if debug {} statements before I publish my code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
pub struct RockInChamber<'a, 'b> {
pub chamber: &'a [u8],
pub rock: &'b [u8],
pub x: usize,
pub y: usize,
pub w: usize,
pub rock_part: usize,
pub print_lim: usize,
}
impl Default for RockInChamber<'_, '_> {
fn default() -> Self {
Self {
chamber: &[],
rock: &[],
x: 0,
y: 0,
w: 1,
rock_part: 8,
print_lim: 17,
}
}
}
impl std::fmt::Display for RockInChamber<'_, '_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let h = self.chamber.len() / Chamber::WIDTH;
let y_mx = h + self.rock_part;
let y_mn = 0.max(h - self.print_lim.min(h));
for y_ in (y_mn..y_mx).rev() {
'|'.fmt(f)?;
for x_ in 0..Chamber::WIDTH {
if x_ >= self.x
&& x_ < self.x + self.w
&& y_ >= self.y
&& y_ < self.y + self.rock.len() / self.w
&& self.rock[x_ - self.x + (y_ - self.y) * self.w] == b'#'
{
'@'.fmt(f)?;
} else if y_ < h {
(self.chamber[x_ + y_ * Chamber::WIDTH] as char).fmt(f)?;
} else {
'.'.fmt(f)?;
}
}
"|\n".fmt(f)?;
}
if y_mn == 0 {
'+'.fmt(f)?;
for _ in 0..Chamber::WIDTH {
'-'.fmt(f)?;
}
"+".fmt(f)?;
} else {
"|~y=".fmt(f)?;
(y_mn - 1).fmt(f)?;
"~".fmt(f)?;
}
Ok(())
}
}
impl std::fmt::Display for Chamber<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
RockInChamber {
chamber: &self.chamber,
..RockInChamber::default()
}
.fmt(f)
}
}
Animation
Just for fun, I created an example with a little animation (simulates 2022 rocks using the example data). Run with cargo run --release --example animate — <ms> where <ms> is the amount of ms to sleep after each animation step, defaults to 40.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
fn main() {
// accept a single numeric argumnet
let arg = env::args().skip(1).next();
let wait = arg
.map(|arg| arg.parse().expect("a positive amount of ms to pause"))
.unwrap_or(40);
let mut chamber = Chamber::from(&CONTENT.into());
for k in 0..2022 {
chamber.integrate_rock(|chamber, rock, x, y, w| {
print!("\x1B[1;1H\x1B[J"); // clear console
println!(
"{}",
RockInChamber {
chamber,
rock,
x,
y,
w,
..RockInChamber::default()
}
);
println!("Rock {}", k + 1);
thread::sleep(Duration::from_millis(wait));
});
}
}
Day 18: Boiling Boulders
Rust solution to AoC|2022|18.
Input
Parse the input in a vec of 3D coordinates.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
cubes: Vec<(isize, isize, isize)>,
}
impl<'a> From<&'a str> for PuzzleData {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self {
cubes: s
.lines()
.map(|line| line.split(','))
.map(|mut split| {
(
split.next().unwrap().parse().unwrap(),
split.next().unwrap().parse().unwrap(),
split.next().unwrap().parse().unwrap(),
)
})
.collect(),
}
}
}
impl PuzzleData {
pub fn cubes(&self) -> &[(isize, isize, isize)] {
&self.cubes
}
}
}
Star 1
I use bits of bytes to store whether a side of a cube is touching a side of another cube. I start with all bits set to 1 and set them to zero by looking at all pairs of cubes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
pub fn star_1_pairwise_comp(data: &PuzzleData) -> usize {
let cubes = data.cubes();
let mut sides = vec![0b111111u8; cubes.len()];
for k1 in 0..cubes.len() - 1 {
let (x_1, y_1, z_1) = cubes[k1];
for k2 in k1 + 1..cubes.len() {
let (x_2, y_2, z_2) = cubes[k2];
if x_1 == x_2 + 1 && y_1 == y_2 && z_1 == z_2 {
sides[k1] &= !(1 << 0);
sides[k2] &= !(1 << 1);
} else if x_1 == x_2 - 1 && y_1 == y_2 && z_1 == z_2 {
sides[k1] &= !(1 << 1);
sides[k2] &= !(1 << 0);
} else if x_1 == x_2 && y_1 == y_2 + 1 && z_1 == z_2 {
sides[k1] &= !(1 << 2);
sides[k2] &= !(1 << 3);
} else if x_1 == x_2 && y_1 == y_2 - 1 && z_1 == z_2 {
sides[k1] &= !(1 << 3);
sides[k2] &= !(1 << 2);
} else if x_1 == x_2 && y_1 == y_2 && z_1 == z_2 + 1 {
sides[k1] &= !(1 << 4);
sides[k2] &= !(1 << 5);
} else if x_1 == x_2 && y_1 == y_2 && z_1 == z_2 - 1 {
sides[k1] &= !(1 << 5);
sides[k2] &= !(1 << 4);
}
}
}
sides.iter().map(|s| s.count_ones() as usize).sum()
}
Star 2
The approach for part 2 is totally different from the approach for part 1.
I calculate the bounding box containing all cubes of a droplet and do a breadth first traversal starting from all 8 corners of the bounding box (enlarged by one in each direction) at the same time. The traversal will not exit this enlarged bounding box.
Whenever the traversal hits a cube contained in the droplet, there is exactly on side facing outwards to be added to the count.
Interestingly, the solution for the second part is calculated faster than the solution for the first part in my case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
pub fn star_2(data: &PuzzleData) -> usize {
let ((x_mn, y_mn, z_mn), (x_mx, y_mx, z_mx)) = data.cubes().iter().fold(
(
(isize::MAX, isize::MAX, isize::MAX),
(isize::MIN, isize::MIN, isize::MIN),
),
|(mn, mx), c| {
(
(mn.0.min(c.0 - 1), mn.1.min(c.1 - 1), mn.2.min(c.2 - 1)),
(mx.0.max(c.0 + 1), mx.1.max(c.1 + 1), mx.2.max(c.2 + 1)),
)
},
);
let droplet: HashSet<(isize, isize, isize)> = HashSet::from_iter(data.cubes().iter().cloned());
let mut queue = VecDeque::new();
for x in [x_mn, x_mx] {
for y in [y_mn, y_mx] {
for z in [z_mn, z_mx] {
queue.push_back((x, y, z));
}
}
}
let mut seen: HashSet<(isize, isize, isize)> = HashSet::from_iter(queue.iter().cloned());
let mut sides = 0;
while let Some((x, y, z)) = queue.pop_front() {
for a in [
(x + 1, y, z),
(x - 1, y, z),
(x, y + 1, z),
(x, y - 1, z),
(x, y, z + 1),
(x, y, z - 1),
]
.into_iter()
.filter(|&(x, y, z)| {
x >= x_mn && y >= y_mn && z >= z_mn && x <= x_mx && y <= y_mx && z <= z_mx
}) {
if droplet.contains(&a) {
sides += 1;
} else if seen.insert(a) {
queue.push_back(a);
}
}
}
sides
}
Star 1 variant
After part 2 was done, I re-created a solution for part 1 based on the same idea.
This time, I do a breadth first traversal inside the droplet. Since the droplet is not necessarily connected, I need to wrap everything in an additional loop until all cubes are processed. To do so, I replace the seen set (which is initially empty) by a remain set, which initially contains all cubes, and from which I remove all cubes that are processed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
pub fn star_1_traversal(data: &PuzzleData) -> usize {
let droplet: HashSet<(isize, isize, isize)> = HashSet::from_iter(data.cubes().iter().cloned());
let mut sides = 0;
let mut queue = VecDeque::new();
let mut remain = droplet.clone();
while let Some(&start) = remain.iter().next() {
remain.remove(&start);
queue.push_back(start);
while let Some((x, y, z)) = queue.pop_front() {
for a in [
(x + 1, y, z),
(x - 1, y, z),
(x, y + 1, z),
(x, y - 1, z),
(x, y, z + 1),
(x, y, z - 1),
] {
if remain.remove(&a) {
// cube in droplet and not yet seen
queue.push_back(a);
} else if !droplet.contains(&a) {
// cube which is direct adjacent is not contained
sides += 1;
}
}
}
}
sides
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"2,2,2
1,2,2
3,2,2
2,1,2
2,3,2
2,2,1
2,2,3
2,2,4
2,2,6
1,2,5
3,2,5
2,1,5
2,3,5
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
assert_eq!(13, data.cubes().len());
assert_eq!((2, 1, 2), data.cubes()[3]);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(64, star_1_pairwise_comp(&data));
assert_eq!(64, star_1_traversal(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(58, star_2(&data));
}
}
Day 19: Not Enough Minerals
Rust solution to AoC|2022|19.
I was basically poking in the fog and brute forcing the solution.
After I had a working solution, I looked for help in the reddit solution megathread and re-worked my solution.
There are three main elements that lead to acceptable solution time:
-
Do not simulate every minute but rather decide which robot to build next and simulate as many minutes as required to build that robot at once
-
Understand that only one robot can be made per minute, which implies that there is no point in having more Ore, Clay or Obsidian collecting robots than the maximum Ore, Clay or Obsidian required to produce a single robot of any kind
-
Do a depth first search to have terminal states quickly and discard all branches for which an upper bound can be calculated which is below the current optimum (this is kind of an A* idea)
Input
I parse the blueprints into a vec containing the amount of Ore, Clay and Obsidian required to build any of the Ore collecting, Clay collecting, Obsidian collecting or Geode opening robots. This results in many 0’s but makes the implementation of the search algorithm much easier.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
pub mod input {
use crate::{SolT, CLAY, GEODE, OBSIDIAN, ORE};
#[derive(Debug)]
pub struct PuzzleData {
pub blueprints: Vec<[SolT; 12]>,
}
fn parse_blueprint(line: &str) -> [SolT; 12] {
let mut blueprint = [0; 12];
let mut words = line.split_ascii_whitespace().skip(6); // blueprint <id>: each ore robot costs
blueprint[ORE + 3 * ORE] = words.next().unwrap().parse().unwrap(); // XX: ore for ore robot
let mut words = words.skip(5); // ore. each clay robot costs
blueprint[ORE + 3 * CLAY] = words.next().unwrap().parse().unwrap(); // XX: ore for clay robot
let mut words = words.skip(5); // ore. each obsidian robot costs
blueprint[ORE + 3 * OBSIDIAN] = words.next().unwrap().parse().unwrap(); // XX: ore for obsidian robot
let mut words = words.skip(2); // ore and
blueprint[CLAY + 3 * OBSIDIAN] = words.next().unwrap().parse().unwrap(); // XX: clay for obsidian robot
let mut words = words.skip(5); // clay. each geode robot costs
blueprint[ORE + 3 * GEODE] = words.next().unwrap().parse().unwrap(); // XX: ore for geode robot
let mut words = words.skip(2); // ore and
blueprint[OBSIDIAN + 3 * GEODE] = words.next().unwrap().parse().unwrap(); // XX: obsidian for geode robot
assert_eq!(Some("obsidian."), words.next());
assert_eq!(None, words.next());
blueprint
}
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self {
blueprints: s.lines().map(parse_blueprint).collect(),
}
}
}
}
Star 1
My depth-first search implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
pub fn max_geodes(blueprint: &[SolT], steps: SolT) -> SolT {
// start with one ore robot, zero material and steps to go
let start = ([1, 0, 0, 0], [0; 4], steps);
// initialize queue
let mut queue = Vec::from([start]);
// maximum required amount of robots per type
let max_req = (ORE..=OBSIDIAN).fold([SolT::MAX; 4], |mut max_req, m| {
max_req[m] = (ORE..=GEODE).map(|r| blueprint[m + 3 * r]).max().unwrap();
max_req
});
// optimum
let mut opt: SolT = 0;
while let Some((robots, materials, steps)) = queue.pop() {
// update optimum, including geodes opened in remaining steps
opt = opt.max(materials[GEODE] + robots[GEODE] * steps);
// time elapsed
if steps == 0 {
continue;
}
// if geodes opened by making a geode robot in every subsequent step does not lead to
// an improvement, stop here
if (0..steps).fold(materials[GEODE], |bound, step| {
bound + (robots[GEODE] + step) * (steps - step)
}) < opt
{
continue;
}
for r in (ORE..=GEODE).rev().filter(|&r| robots[r] < max_req[r]) {
// calculate steps required to build robot
let Some(s) = (ORE..=OBSIDIAN)
.map(|m| {
if materials[m] >= blueprint[m + 3 * r] {
Some(0)
} else if robots[m] == 0 {
None
} else {
Some((blueprint[m + 3 * r] - materials[m]).div_ceil(robots[m]))
}
})
.try_fold(0, |s_max, s| s.map(|s| s_max.max(s)))
else {
// can't build robot
continue;
};
if s + 1 > steps {
// time elapsed
continue;
}
// update robots and materials
let mut materials = materials;
for m in ORE..=OBSIDIAN {
materials[m] += (s + 1) * robots[m];
materials[m] -= blueprint[m + 3 * r];
}
materials[GEODE] += (s + 1) * robots[GEODE];
let mut robots = robots;
robots[r] += 1;
// push to queue
queue.push((robots, materials, steps - s - 1));
}
}
opt
}
This is used for part 1 as
1
2
3
4
5
6
7
8
pub fn star_1(data: &PuzzleData) -> SolT {
data.blueprints
.iter()
.map(|blueprint| max_geodes(blueprint, 24))
.enumerate()
.map(|(k, opt)| (k as SolT + 1) * opt)
.sum()
}
Star 2
The same solution works for part 2:
1
2
3
4
5
6
7
pub fn star_2(data: &PuzzleData) -> SolT {
data.blueprints
.iter()
.take(3)
.map(|blueprint| max_geodes(blueprint, 32))
.product()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
assert_eq!(
[(9, 1), (12, 2)]
.into_iter()
.map(|(geodes, id)| geodes * id)
.sum::<SolT>(),
star_1(&CONTENT.into())
);
}
#[test]
pub fn test_star_2() {
assert_eq!(56 * 62, star_2(&CONTENT.into()));
}
}
Today I learned
Brute force sometimes works but it is no fun, and there is a lot to learn on how to solve these kind of problems …
Day 20: Grove Positioning System
Rust solution to AoC|2022|20.
Looked simple but was more tricky than expected.
The example data turned out to be too friendly for me.
Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub numbers: Vec<isize>,
}
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self {
numbers: s.trim().lines().map(|l| l.parse().unwrap()).collect(),
}
}
}
}
General Solution
I decided to store the data in a kind of doubly linked list. I implemented this by creating a list of indices to the predecessor and successor of each number. The numbers themselves are stored in a vec which is unchanged all the time (this is useful since we need to process along the initial order of the numbers)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn mix(numbers: &[isize], times: usize) -> isize {
let n = numbers.len();
let mut indices = (0..n)
.map(|k| ((k + n - 1) % n, (k + 1) % n))
.collect::<Vec<_>>();
let k0 = numbers.iter().position(|&v| v == 0).unwrap();
for _ in 0..times {
for k in 0..n {
mix_step(&mut indices, numbers, k);
}
}
let k1 = (0..1000).fold(k0, |k, _| indices[k].1);
let k2 = (0..1000).fold(k1, |k, _| indices[k].1);
let k3 = (0..1000).fold(k2, |k, _| indices[k].1);
numbers[k1] + numbers[k2] + numbers[k3]
}
The key is to perform a single mix step correctly. I failed to do so in all possible ways. To be able to test this properly, I put it into a separate function and created my own test cases for it (see below).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
pub fn mix_step(indices: &mut [(usize, usize)], numbers: &[isize], k: usize) {
let v = numbers[k];
let steps = v % (numbers.len() as isize - 1);
// move in direction of lower number of steps
let steps = if steps > (numbers.len() as isize - 1) / 2 {
steps - (numbers.len() as isize - 1)
} else if steps < -(numbers.len() as isize - 1) / 2 {
steps + (numbers.len() as isize - 1)
} else {
steps
};
if steps != 0 {
if steps > 0 {
// k_pre k k_post .. idx idx_post => k_pre k_post .. idx k idx_post
let idx = (0..steps).fold(k, |k, _| indices[k].1);
let (k_pre, k_post) = indices[k];
let (_, idx_post) = indices[idx];
indices[k_post].0 = k_pre;
indices[k_pre].1 = k_post;
indices[k] = (idx, idx_post);
indices[idx].1 = k;
indices[idx_post].0 = k;
} else {
// idx_pre idx .. k_pre k k_post => idx_pre k idx .. k_pre k_post
let idx = (steps..0).fold(k, |k, _| indices[k].0);
let (k_pre, k_post) = indices[k];
let (idx_pre, _) = indices[idx];
indices[k_post].0 = k_pre;
indices[k_pre].1 = k_post;
indices[k] = (idx_pre, idx);
indices[idx].0 = k;
indices[idx_pre].1 = k;
};
}
}
Star 1
Just call the mix function with times = 1.
Star 2
Call the mix function with numbers multiplied by the decryption key and times = 10:
1
2
3
4
5
6
7
8
9
10
pub fn star_2(data: &PuzzleData) -> isize {
mix(
&data
.numbers
.iter()
.map(|v| v * 811_589_153)
.collect::<Vec<_>>(),
10,
)
}
Tests
The most difficult part today: create test_mix_step and make it pass.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#[cfg(test)]
mod tests {
use std::collections::HashSet;
use super::*;
const CONTENT: &str = r#"1
2
-3
3
-2
0
4
"#;
#[test]
pub fn test_mix_step() {
let n = 21;
let numbers: &[isize] = &[
0,
-1,
-2,
1,
2,
n - 2,
n - 1,
n,
2 * n - 4,
2 * n - 3,
2 * n - 2,
2 * n - 1,
2 * n,
-n - 1,
-n,
-n + 1,
-2 * n - 3,
-2 * n - 2,
-2 * n - 1,
-2 * n,
-2 * n + 1,
];
println!(
"{:?}",
numbers
.iter()
.map(|v| (v, v % (n - 1), v.rem_euclid(n - 1)))
.collect::<Vec<_>>()
);
let exp = vec![
(-2 * n + 1, -1), // 0
(-2 * n + 1, 0), // -1
(-2 * n + 1, 0), // -2
(2, n - 2), // 1
(n - 1, n), // 2
(1, 2), // n - 2 = 19
(n - 2, n), // n - 1 = 20
(2 * n - 4, 2 * n - 3), // n = 21
(n - 2, n - 1), // 2 n - 4 = 38
(n, 2 * n - 4), // 2 n - 3 = 39
(2 * n - 3, 2 * n - 1), // 2 n - 2 = 40
(2 * n, -n - 1), // 2 n - 1 = 41
(-n, -n + 1), // 2 n = 42
(2 * n - 2, 2 * n - 1), // -n-1 = -22
(2 * n, -n - 1), // -n = -21
(-n, -2 * n - 3), // -n+1 = -20
];
let n = n as usize;
let to_vec = |indices: &Vec<(usize, usize)>| {
(0..n)
.scan(0, |k, _| {
let v = numbers[*k];
*k = indices[*k].1;
Some(v)
})
.collect::<Vec<isize>>()
};
let indices = (0..n)
.map(|k| ((k + n - 1) % n, (k + 1) % n))
.collect::<Vec<_>>();
assert_eq!(numbers, to_vec(&indices));
for k in 0..n {
let mut indices = (0..n)
.map(|k| ((k + n - 1) % n, (k + 1) % n))
.collect::<Vec<_>>();
mix_step(&mut indices, numbers, k);
println!("numbers[{k}] = {} => {:?}", numbers[k], to_vec(&indices));
if k < exp.len() {
assert_eq!(
exp[k],
(numbers[indices[k].0], numbers[indices[k].1]),
"at k = {k}"
);
}
let mut k_fwd = 0;
let mut k_rev = 0;
let mut fwds = HashSet::from([0]);
let mut revs = HashSet::from([0]);
for _ in 0..n {
k_fwd = indices[k_fwd].1;
k_rev = indices[k_rev].1;
fwds.insert(k_fwd);
revs.insert(k_rev);
}
// full cycle in both directions
assert_eq!(
0, k_fwd,
"incomplete forward cycle\nk: {k}\n numbers: {numbers:?}\n indices: {indices:?}"
);
assert_eq!(
0, k_rev,
"incomplete backwards cycle\nk: {k}\n numbers: {numbers:?}\n indices: {indices:?}"
);
assert_eq!(
n,
fwds.len(),
"items not in forward cycle\nk: {k}\n numbers: {numbers:?}\n indices: {indices:?}"
);
assert_eq!(
n,
revs.len(),
"items not in backwards cycle\nk: {k}\n numbers: {numbers:?}\n indices: {indices:?}"
);
}
}
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(3, mix(&data.numbers, 1));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(1_623_178_306, star_2(&data));
}
}
Day 21: Monkey Math
Rust solution to AoC|2022|21.
Primary school math today…
Input
I parse the input into a map with monkey names as keys and Yell enums as values. A Yell is either a Number or an Operation referencing other monkey by name. The Unknown variant is required for star 2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
pub mod input {
use std::collections::HashMap;
#[derive(Debug, Clone)]
pub enum Yell<'a> {
Operation(&'a str, &'a str, &'a str),
Number(isize),
Unknown, // required for part 2
}
pub fn parse_yell(line: &str) -> (&str, Yell<'_>) {
let mut words = line.split_ascii_whitespace();
let name = words.next().unwrap().trim_end_matches(':');
let word = words.next().unwrap();
let yell = if (word.as_bytes()[0] as char).is_ascii_digit() {
Yell::Number(word.parse().unwrap())
} else {
Yell::Operation(word, words.next().unwrap(), words.next().unwrap())
};
(name, yell)
}
#[derive(Debug)]
pub struct PuzzleData<'a> {
pub monkeys: HashMap<&'a str, Yell<'a>>,
}
impl<'a> From<&'a str> for PuzzleData<'a> {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self {
monkeys: s.lines().map(parse_yell).collect(),
}
}
}
}
Star 1
This is a trivial recursive get_result function.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn get_result(monkeys: &HashMap<&str, Yell<'_>>, monkey: &str) -> isize {
match monkeys.get(monkey) {
Some(Yell::Operation(lhs, op, rhs)) => {
let lhs = get_result(monkeys, lhs);
let rhs = get_result(monkeys, rhs);
match *op {
"+" => lhs + rhs,
"-" => lhs - rhs,
"*" => lhs * rhs,
"/" => lhs / rhs,
_ => panic!("Unknown operation: {op}"),
}
}
Some(Yell::Number(v)) => *v,
yell => panic!("Can't get result for monkey {monkey} => {yell:?}"),
}
}
pub fn star_1(data: &PuzzleData) -> isize {
get_result(&data.monkeys, "root")
}
Star 2
For the second part, I update the map so that the value for key "humn" is Unknown and the operation for key "root" is -, so that I can solve the root value for 0.
I put the yells in a recursive tree enum YellRec reducing branches of the tree that do not contain Unknown on the fly with a reduce function.
Then I solve for the Unknown inverting operations one by one. This works if the Unknown appears in exactly one of the right hand side or left hand side arguments, which is the case for my input (and I guess for every one else’s input as well) and for the example data.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#[derive(Debug)]
pub enum YellRec<'a> {
Operation(Box<(YellRec<'a>, &'a str, YellRec<'a>)>),
Number(isize),
Unknown,
}
pub fn reduce<'a>(monkeys: &HashMap<&str, Yell<'a>>, monkey: &str) -> YellRec<'a> {
match monkeys.get(monkey) {
Some(Yell::Operation(lhs, op, rhs)) => {
let lhs = reduce(monkeys, lhs);
let rhs = reduce(monkeys, rhs);
match (lhs, rhs) {
(YellRec::Number(lhs), YellRec::Number(rhs)) => match *op {
"+" => YellRec::Number(lhs + rhs),
"-" => YellRec::Number(lhs - rhs),
"*" => YellRec::Number(lhs * rhs),
"/" => YellRec::Number(lhs / rhs),
_ => panic!("Unknown operation: {op}"),
},
(lhs, rhs) => YellRec::Operation((lhs, *op, rhs).into()),
}
}
Some(Yell::Number(v)) => YellRec::Number(*v),
Some(Yell::Unknown) => YellRec::Unknown,
yell => panic!("Can't get result for monkey {monkey} => {yell:?}"),
}
}
pub fn solve(yell: &YellRec, tar: isize) -> isize {
match yell {
YellRec::Operation(b) => match b.as_ref() {
(lhs, op, YellRec::Number(rhs)) => match *op {
"+" => solve(lhs, tar - *rhs), // lhs + rhs = tar
"-" => solve(lhs, tar + *rhs), // lhs - rhs = tar
"*" => solve(lhs, tar / *rhs), // lhs * rhs = tar
"/" => solve(lhs, tar * *rhs), // lhs / rhs = tar
_ => panic!("Unknown operation: {op}"),
},
(YellRec::Number(lhs), op, rhs) => match *op {
"+" => solve(rhs, tar - *lhs), // lhs + rhs = tar
"-" => solve(rhs, *lhs - tar), // lhs - rhs = tar
"*" => solve(rhs, tar / *lhs), // lhs * rhs = tar
"/" => solve(rhs, *lhs / tar), // lhs / rhs = tar
_ => panic!("Unknown operation: {op}"),
},
_ => panic!("solve expects either rhs or lhs to be a number"),
},
YellRec::Unknown => tar,
YellRec::Number(_) => panic!("Can't solve a number"),
}
}
pub fn star_2(data: &PuzzleData) -> isize {
let mut monkeys = data.monkeys.clone();
let Some(Yell::Operation(lhs, _, rhs)) = monkeys.get("root") else {panic!()};
monkeys.insert("root", Yell::Operation(lhs, "-", rhs));
monkeys.insert("humn", Yell::Unknown);
solve(&reduce(&monkeys, "root"), 0)
}
Tests
I only created tests today, because my template contains them. I actually did not use them before submitting the result…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
ptdq: humn - dvpt
dvpt: 3
lfqf: 4
humn: 5
ljgn: 2
sjmn: drzm * dbpl
sllz: 4
pppw: cczh / lfqf
lgvd: ljgn * ptdq
drzm: hmdt - zczc
hmdt: 32
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(152, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(301, star_2(&data));
}
#[test]
pub fn test_solution_range() {
let data = PuzzleData::from(include_str!("../../../input/2022/day21.txt"));
let sol_a = star_2(&data);
let sol_b = star_2_bisection(&data);
let sol_rg = sol_a.min(sol_b)..=sol_a.max(sol_b);
println!("Solution range: {sol_rg:?}");
let mut monkeys = data.monkeys.clone();
let Some(Yell::Operation(lhs, _, rhs)) = monkeys.get("root") else {panic!()};
monkeys.insert("root", Yell::Operation(lhs, "-", rhs));
for sol in sol_rg {
monkeys.insert("humn", Yell::Number(sol));
assert_eq!(0, get_result(&monkeys, "root"));
}
}
}
Day 22: Monkey Map
Rust solution to AoC|2022|22.
Geometry! Cube layouts … what looked simple turned out to be very tedious
Input
Nothing special here today. I decided to make the lines of the grid equal length (padded with spaced) for easier processing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
pub mod input {
#[derive(Debug, PartialEq, Eq)]
pub enum Step {
Fwd(usize),
Left,
Right,
}
#[derive(Debug)]
pub struct PuzzleData {
pub grid: Vec<u8>,
pub width: usize,
pub steps: Vec<Step>,
}
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
let (grid_part, steps_part) = s.split_once("\n\n").unwrap();
// store the grid with rows of equal width
let lines = grid_part.lines().collect::<Vec<_>>();
let width = lines.iter().map(|line| line.len()).max().unwrap();
let mut grid = vec![b' '; width * lines.len()];
for row in 0..lines.len() {
for (col, b) in lines[row].as_bytes().iter().enumerate() {
grid[col + row * width] = *b;
}
}
let mut steps = Vec::new();
let mut fwd = 0;
for b in steps_part.trim().as_bytes() {
if b.is_ascii_digit() {
fwd = 10 * fwd + (b - b'0') as usize;
} else {
if fwd != 0 {
steps.push(Step::Fwd(fwd));
fwd = 0;
}
if *b == b'L' {
steps.push(Step::Left);
} else if *b == b'R' {
steps.push(Step::Right);
} else {
panic!("Unexpected {} in {steps_part}", *b as char);
}
}
}
if fwd != 0 {
steps.push(Step::Fwd(fwd));
}
Self { grid, width, steps }
}
}
}
Star 1
I used an iterator to move forward. Looks much nicer that for loops ;)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
pub fn star_1(data: &PuzzleData) -> usize {
let mut col = data.grid.iter().position(|&b| b == b'.').unwrap();
let mut row = 0;
let mut d: usize = 0;
let height = data.grid.len() / data.width;
for step in &data.steps {
match step {
Step::Fwd(fwd) => {
let (d_col, d_row, n) = match d {
0 => (1, 0, data.width),
1 => (0, 1, height),
2 => (data.width - 1, 0, data.width),
3 => (0, height - 1, height),
_ => unreachable!(),
};
(col, row) = (0..n)
.cycle()
.map(|s| ((col + s * d_col) % data.width, (row + s * d_row) % height))
.filter(|(col, row)| data.grid[col + data.width * row] != b' ')
.take(fwd + 1)
.take_while(|(col, row)| data.grid[col + row * data.width] != b'#')
.last()
.unwrap();
}
Step::Left => d = (d + 3) % 4,
Step::Right => d = (d + 1) % 4,
}
}
(row + 1) * 1000 + (col + 1) * 4 + d
}
Star 2
I did not see the cubes come when working on part 1.
This turned out to be much more complicated than what I first thought.
There is quite a bit of repetition in my code which multiplies the opportunities for mistakes. I used a lot of the opportunities and made a lot of them. And I had no efficient way for debugging. Which branch of the code is actually used, depends a lot on the cube layout. Since this is different for the example and the real data, the example was not good enough to fix all the issues.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
pub const EAST: usize = 0; // [1 0 0]
pub const NORTH: usize = 1; // [0 1 0]
pub const UP: usize = 2; // [0 0 1]
pub const WEST: usize = 3; // [-1 0 0]
pub const SOUTH: usize = 4; // [0 -1 0]
pub const DOWN: usize = 5; // [0 0 -1]
pub const HEAD_RIGHT: usize = 0;
pub const HEAD_DOWN: usize = 1;
pub const HEAD_LEFT: usize = 2;
pub const HEAD_UP: usize = 3;
pub fn star_2(data: &PuzzleData, face_width: usize) -> usize {
let layout_w = data.width / face_width;
let layout_h = (data.grid.len() / data.width) / face_width;
assert_eq!(
layout_w * face_width * layout_h * face_width,
data.grid.len(),
"Grid len does not match layout"
);
// get the cube layout (each face is represented by a '#')
let cube_layout = (0..data.grid.len() / (face_width * face_width))
.map(|p| (p % layout_w, p / layout_w))
.map(|(c, r)| {
if data.grid[c * face_width + r * face_width * data.width] == b' ' {
' '
} else {
'#'
}
})
.collect::<Vec<_>>();
// compile a map of cube faces with the normal direction as key and
// ((col, row), (n_dir, x_dir, y_dir)) as value where (col, row) is the
// position in the grid and (n_dir, x_dir, y_dir) is normal direction
// and direction of x- and y- respectively
let pos: usize = cube_layout.iter().position(|&face| face == '#').unwrap();
let start = ((pos % layout_w, pos / layout_w), (UP, EAST, SOUTH));
let mut faces = HashMap::from([(UP, start)]);
let mut queue = VecDeque::from([start]);
while let Some(((col, row), (n_dir, x_dir, y_dir))) = queue.pop_front() {
if col > 0 && cube_layout[col - 1 + row * layout_w] == '#' {
let value = ((col - 1, row), ((x_dir + 3) % 6, n_dir, y_dir));
if let Entry::Vacant(entry) = faces.entry(value.1 .0) {
entry.insert(value);
queue.push_back(value);
}
}
if col < layout_w - 1 && cube_layout[col + 1 + row * layout_w] == '#' {
let value = ((col + 1, row), (x_dir, (n_dir + 3) % 6, y_dir));
if let Entry::Vacant(entry) = faces.entry(value.1 .0) {
entry.insert(value);
queue.push_back(value);
}
}
if row > 0 && cube_layout[col + (row - 1) * layout_w] == '#' {
let value = ((col, row - 1), ((y_dir + 3) % 6, x_dir, n_dir));
if let Entry::Vacant(entry) = faces.entry(value.1 .0) {
entry.insert(value);
queue.push_back(value);
}
}
if row < layout_h - 1 && cube_layout[col + (row + 1) * layout_w] == '#' {
let value = ((col, row + 1), (y_dir, x_dir, (n_dir + 3) % 6));
if let Entry::Vacant(entry) = faces.entry(value.1 .0) {
entry.insert(value);
queue.push_back(value);
}
}
}
// current position is given by (x, y) within face and (col, row) of face
// in addition normal direction and x-/y-direction of current face and
// the current orientation `d`
let pos = data.grid.iter().position(|&b| b == b'.').unwrap();
let mut x = pos % face_width;
let mut y = 0;
let mut col = pos / face_width;
let mut row = 0;
let (_, (mut n_dir, mut x_dir, mut y_dir)) = faces.get(&UP).unwrap();
let mut d: usize = 0;
#[cfg(feature = "print-path")]
let mut path: HashMap<usize, usize> = HashMap::from([(pos, d)]);
for step in &data.steps {
match step {
Step::Fwd(fwd) => {
for _ in 0..*fwd {
// determine x and y updates (wrapping)
// and normal direction of next face (if wrapping)
let (x_upd, y_upd, n_dir_upd) = match d {
HEAD_RIGHT => (
(x + 1) % face_width,
y,
if x < face_width - 1 { n_dir } else { x_dir },
),
HEAD_DOWN => (
x,
(y + 1) % face_width,
if y < face_width - 1 { n_dir } else { y_dir },
),
HEAD_LEFT => (
(x + face_width - 1) % face_width,
y,
if x > 0 { n_dir } else { (x_dir + 3) % 6 },
),
HEAD_UP => (
x,
(y + face_width - 1) % face_width,
if y > 0 { n_dir } else { (y_dir + 3) % 6 },
),
_ => unreachable!(),
};
let (x_upd, y_upd, d_upd, col_upd, row_upd, x_dir_upd, y_dir_upd) = if n_dir_upd
!= n_dir
{
// calculate update on a new face
// get face
let ((col_upd, row_upd), (n_dir_upd, x_dir_upd, y_dir_upd)) =
*faces.get(&n_dir_upd).unwrap();
// do the transformation
let (x_upd, y_upd, d_upd) = if n_dir_upd == x_dir {
// move right
if y_dir_upd == y_dir && x_dir_upd == (n_dir + 3) % 6 {
(0, y, HEAD_RIGHT)
} else if y_dir_upd == (y_dir + 3) % 6 && x_dir_upd == n_dir {
(face_width - 1, face_width - 1 - y, HEAD_LEFT)
} else if x_dir_upd == y_dir && y_dir_upd == n_dir {
(y, face_width - 1, HEAD_UP)
} else if x_dir_upd == (y_dir + 3) % 6 && y_dir_upd == (n_dir + 3) % 6 {
(face_width - 1 - y, 0, HEAD_DOWN)
} else {
unreachable!(
"right: {}, _{}_, {} --> _{}_, {}, {}",
n_dir, x_dir, y_dir, n_dir_upd, x_dir_upd, y_dir_upd
)
}
} else if n_dir_upd == (x_dir + 3) % 6 {
// move left
if y_dir_upd == y_dir && x_dir_upd == n_dir {
(face_width - 1, y, HEAD_LEFT)
} else if y_dir_upd == (y_dir + 3) % 6 && x_dir_upd == (n_dir + 3) % 6 {
(0, face_width - 1 - y, HEAD_RIGHT)
} else if x_dir_upd == y_dir && y_dir_upd == (n_dir + 3) % 6 {
(y, 0, HEAD_DOWN)
} else if x_dir_upd == (y_dir + 3) % 6 && y_dir_upd == n_dir {
(face_width - 1 - y, face_width - 1, HEAD_UP)
} else {
unreachable!(
"left: {}, _{}_, {} --> _{}_, {}, {}",
n_dir, x_dir, y_dir, n_dir_upd, x_dir_upd, y_dir_upd
)
}
} else if n_dir_upd == y_dir {
// move down
if x_dir_upd == x_dir && y_dir_upd == (n_dir + 3) % 6 {
(x, 0, HEAD_DOWN)
} else if x_dir_upd == (x_dir + 3) % 6 && y_dir_upd == n_dir {
(face_width - 1 - x, face_width - 1, HEAD_UP)
} else if y_dir_upd == x_dir && x_dir_upd == n_dir {
(face_width - 1, x, HEAD_LEFT)
} else if y_dir_upd == (x_dir + 3) % 6 && x_dir_upd == (n_dir + 3) % 6 {
(0, face_width - 1 - x, HEAD_RIGHT)
} else {
unreachable!(
"down: {}, {}, _{}_ --> _{}_, {}, {}",
n_dir, x_dir, y_dir, n_dir_upd, x_dir_upd, y_dir_upd
)
}
} else if n_dir_upd == (y_dir + 3) % 6 {
// move up
if x_dir_upd == x_dir && y_dir_upd == n_dir {
(x, face_width - 1, HEAD_UP)
} else if x_dir_upd == (x_dir + 3) % 6 && y_dir_upd == (n_dir + 3) % 6 {
(face_width - 1 - x, 0, HEAD_DOWN)
} else if y_dir_upd == x_dir && x_dir_upd == (n_dir + 3) % 6 {
(0, x, HEAD_RIGHT)
} else if y_dir_upd == (x_dir + 3) % 6 && x_dir_upd == n_dir {
(face_width - 1, face_width - 1 - x, HEAD_LEFT)
} else {
unreachable!(
"up: {}, {}, _{}_ --> _{}_, {}, {}",
n_dir, x_dir, y_dir, n_dir_upd, x_dir_upd, y_dir_upd
)
}
} else {
unreachable!()
};
(x_upd, y_upd, d_upd, col_upd, row_upd, x_dir_upd, y_dir_upd)
} else {
// update within a face
(x_upd, y_upd, d, col, row, x_dir, y_dir)
};
if data.grid
[x_upd + col_upd * face_width + (y_upd + row_upd * face_width) * data.width]
== b'#'
{
// wall, can't move any further
break;
}
// update
x = x_upd;
y = y_upd;
d = d_upd;
col = col_upd;
row = row_upd;
n_dir = n_dir_upd;
x_dir = x_dir_upd;
y_dir = y_dir_upd;
#[cfg(feature = "print-path")]
path.insert(
x + col * face_width + (y + row * face_width) * data.width,
d,
);
}
}
Step::Left => d = (d + 3) % 4,
Step::Right => d = (d + 1) % 4,
}
#[cfg(feature = "print-path")]
path.insert(
x + col * face_width + (y + row * face_width) * data.width,
d,
);
}
#[cfg(feature = "print-path")]
for y in 0..data.grid.len() / data.width {
for x in 0..data.width {
let p = x + y * data.width;
match (path.get(&p), data.grid[p]) {
(Some(0), b'.') => print!(">"),
(Some(1), b'.') => print!("v"),
(Some(2), b'.') => print!("<"),
(Some(3), b'.') => print!("^"),
(None, b'#') => print!("#"),
(None, b'.') => print!("."),
(None, b' ') => print!(" "),
(a, b) => panic!("Unexpected {a:?}, {}", b as char),
}
}
println!();
}
(y + row * face_width + 1) * 1000 + (x + col * face_width + 1) * 4 + d
}
Tests
Tests were very necessary today to come up with a solution. I created several additional simple test cases.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#" ...#
.#..
#...
....
...#.......#
........#...
..#....#....
..........#.
...#....
.....#..
.#......
......#.
10R5L5R10L4R5L5
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(6_032, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(5_031, star_2(&data, 4));
let data = PuzzleData::from(include_str!("../tests_1.txt"));
assert_eq!(1_033, star_2(&data, 5));
let data = PuzzleData::from(include_str!("../tests_2.txt"));
assert_eq!(1_033, star_2(&data, 5));
let data = PuzzleData::from(include_str!("../tests_3.txt"));
assert_eq!(12_013, star_2(&data, 5));
let data = PuzzleData::from(include_str!("../tests_4.txt"));
assert_eq!(3_028, star_2(&data, 5));
}
}
Day 23: Unstable Diffusion
Rust solution to AoC|2022|23.
Elves extend in a space, open in all directions.
So the usual question: shall I use hash sets / hash maps or a more efficient grid based solution?
I decided to go with sets and maps first and I was not happy with that choice. It solved part 1 in about 20ms and part 2 in a bit more than 1s.
In a second attempt, I implemented a grid based solution which solves part 1 in less than 2ms and part 2 in about 70ms.
Input
The input is parsed into an Elves struct. It consists of a grid (to determine neighbors), a list of elves (to efficiently iterate over), a round counter, current limits for the elves' coordinates and a buffer for candidate moves.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#[derive(Debug, Default, Clone)]
pub struct Elves {
grid: Grid<(bool, u8)>,
elves: Vec<(usize, usize)>,
rounds: usize,
moves: Vec<(usize, (usize, usize))>,
limits: (usize, usize, usize, usize),
}
impl std::fmt::Display for Elves {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
for row in self.limits.1..self.limits.3 {
for v in (self.limits.0..self.limits.2).map(|col| self.grid[(col, row)].0) {
f.write_char(if v { '#' } else { '.' })?;
}
f.write_char('\n')?;
}
Ok(())
}
}
impl<T: AsRef<[u8]>> From<T> for Elves {
fn from(value: T) -> Self {
let value = value.as_ref().trim_ascii();
let w = value
.iter()
.position(|&b| b == b'\n')
.unwrap_or(value.len());
let h = (value.len() + 1) / (w + 1);
let (grid, elves, limits) = value
.iter()
.filter(|&&b| b != b'\n')
.enumerate()
.filter(|&(_, &b)| b == b'#')
.map(|(k, _)| (k % w, k / w))
.fold(
(Grid::from(((false, 0), w, h)), Vec::new(), (!0, !0, 0, 0)),
|(mut grid, mut elves, mut limits), pos| {
grid[pos].0 = true;
elves.push(pos);
update_limits(&mut limits, pos);
(grid, elves, limits)
},
);
Self {
grid,
elves,
limits,
..Default::default()
}
}
}
Star 1
The interesting part is in the Elves::round function. It uses the Grid::resize function to make sure the grid has enough space for all potential elf movements.
Then, in each round, I first iterate over all elves and identify potential moves which are stored in the Elves::moves vec. Then I iterate over the moves and move the elves if applicable.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
fn update_limits(
(col_mn, row_mn, col_mx, row_mx): &mut (usize, usize, usize, usize),
(col, row): (usize, usize),
) {
*col_mn = (*col_mn).min(col);
*row_mn = (*row_mn).min(row);
*col_mx = (*col_mx).max(col + 1);
*row_mx = (*row_mx).max(row + 1);
}
const DELTAS: [(isize, isize); 8] = [
(1, -1), // NE
(0, -1), // N
(-1, -1), // NW
(-1, 0), // W
(-1, 1), // SW
(0, 1), // S
(1, 1), // SE
(1, 0), // E
];
const DIRS: [usize; 4] = [1, 5, 3, 7]; // N, S, W, E
impl Elves {
const GAP_MIN: usize = 1;
const GAP_MAX: usize = 10;
pub fn round(&mut self) -> bool {
let (col_off, row_off) = if self.limits.0 < Self::GAP_MIN
|| self.limits.1 < Self::GAP_MIN
|| self.grid.width() - self.limits.2 < Self::GAP_MIN
|| self.grid.height() - self.limits.3 < Self::GAP_MIN
{
let (col_off, row_off) = (Self::GAP_MAX - self.limits.0, Self::GAP_MAX - self.limits.1);
self.grid.resize(
(
col_off as _,
row_off as _,
self.limits.2 - self.limits.0 + 2 * Self::GAP_MAX,
self.limits.3 - self.limits.1 + 2 * Self::GAP_MAX,
),
(false, 0),
);
(col_off, row_off)
} else {
(0, 0)
};
self.limits = (!0, !0, 0, 0);
for (k, (col, row)) in self.elves.iter_mut().enumerate() {
*col += col_off;
*row += row_off;
let (col, row) = (*col, *row);
let f_adj = |(d_col, d_row)| {
(
col.wrapping_add_signed(d_col),
row.wrapping_add_signed(d_row),
)
};
match DELTAS
.into_iter()
.map(&f_adj)
.find(|&pos| self.grid[pos].0)
.and_then(|_| {
(0..4)
.map(|k| DIRS[(k + self.rounds) & 3])
.filter(|&d| {
!self.grid[f_adj(DELTAS[(d + 7) & 7])].0
&& !self.grid[f_adj(DELTAS[(d + 1) & 7])].0
})
.map(|d| f_adj(DELTAS[d]))
.find(|&adj| !self.grid[adj].0)
})
.map(|adj| (adj, &mut self.grid[adj].1))
.and_then(|(adj, count)| {
*count += 1;
(*count == 1).then_some(adj)
}) {
Some(adj) => self.moves.push((k, adj)),
None => update_limits(&mut self.limits, (col, row)),
}
}
let mut change = false;
for (k, adj) in self.moves.drain(..) {
let g = &mut self.grid[adj];
let pos = if g.1 == 1 {
change = true;
*g = (true, 0);
let pos = &mut self.elves[k];
(self.grid[*pos].0, *pos) = (false, adj);
adj
} else {
g.1 = 0;
self.elves[k]
};
update_limits(&mut self.limits, pos);
}
self.rounds += 1;
change
}
pub fn rounds(&self) -> usize {
self.rounds
}
pub fn free_space_in_smallest_rect(&self) -> usize {
(self.limits.2 - self.limits.0) * (self.limits.3 - self.limits.1) - self.elves.len()
}
}
pub fn star_1(data: &&str) -> usize {
let mut elves = Elves::from(data);
while elves.rounds() < 10 && elves.round() {}
elves.free_space_in_smallest_rect()
}
Star 2
Just simulate rounds until nothing more happens.
1
2
3
4
5
pub fn star_2(data: &&str) -> usize {
let mut elves = Elves::from(data);
while elves.round() {}
elves.rounds()
}
Tests
Kind of visual tests today for the simple example. Just compared my output to the one on the website manually.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#[cfg(test)]
mod tests {
use super::*;
#[test]
pub fn test_star_1() {
assert_eq!(110, star_1(&CONTENT));
}
#[test]
pub fn test_star_2() {
assert_eq!(20, star_2(&CONTENT));
}
#[test]
pub fn test_elves_round() {
let mut elves = Elves::from(CONTENT_SMALL);
println!("{}", elves);
for _ in 0..3 {
elves.round();
println!("{}", elves);
}
}
const CONTENT: &str = r#"....#..
..###.#
#...#.#
.#...##
#.###..
##.#.##
.#..#..
"#;
const CONTENT_SMALL: &str = r#".....
..##.
..#..
.....
..##.
.....
"#;
}
Day 24: Blizzard Basin
Rust solution to AoC|2022|24.
Another day of path finding.
Input
I store blizzards separately by direction in a grid (stored as flat vec) which will never change over time. For each direction, there is an row / column offset (modulo width / hight) added depending on when we look at them later on.
The blizzards just contain the inner portion of the basin for easier wrapping around.
In addition, I store the position of the entry and the exit on the first and last row.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub blizzards_r: Vec<bool>,
pub blizzards_u: Vec<bool>,
pub blizzards_l: Vec<bool>,
pub blizzards_d: Vec<bool>,
pub width: usize,
pub height: usize,
pub entry: usize,
pub exit: usize,
}
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
let b = s.as_bytes();
let width = b.iter().position(|&b| b == b'\n').unwrap() - 2;
let entry = b.iter().position(|&b| b == b'.').unwrap() - 1;
let exit = width
- b.iter()
.rev()
.filter(|&&b| b != b'\n')
.position(|&b| b == b'.')
.unwrap();
let blizzards_r: Vec<bool> = b
.iter()
.skip(width + 3)
.take(b.len() - 2 * width - 6)
.filter(|&&b| b != b'\n' && b != b'#')
.map(|&b| b == b'>')
.collect();
let blizzards_l = b
.iter()
.skip(width + 3)
.take(b.len() - 2 * width - 6)
.filter(|&&b| b != b'\n' && b != b'#')
.map(|&b| b == b'<')
.collect();
let blizzards_u = b
.iter()
.skip(width + 3)
.take(b.len() - 2 * width - 6)
.filter(|&&b| b != b'\n' && b != b'#')
.map(|&b| b == b'^')
.collect();
let blizzards_d = b
.iter()
.skip(width + 3)
.take(b.len() - 2 * width - 6)
.filter(|&&b| b != b'\n' && b != b'#')
.map(|&b| b == b'v')
.collect();
let height = blizzards_r.len() / width;
Self {
blizzards_r,
blizzards_l,
blizzards_u,
blizzards_d,
width,
height,
entry,
exit,
}
}
}
}
Star 1
I implemented a function is_blizzard which checks whether there is a blizzard at a given position and a given time.
With this, I implement a A* style search (since the graph is unweighted, nodes are immediately settled once reached and no decrease key or similar is required)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
impl PuzzleData {
pub fn is_blizzard_r(&self, (col, row): (usize, usize), time: usize) -> bool {
self.blizzards_r[(col + self.width - time % self.width) % self.width + self.width * row]
}
pub fn is_blizzard_u(&self, (col, row): (usize, usize), time: usize) -> bool {
self.blizzards_u[col + self.width * ((row + time) % self.height)]
}
pub fn is_blizzard_l(&self, (col, row): (usize, usize), time: usize) -> bool {
self.blizzards_l[(col + time) % self.width + self.width * row]
}
pub fn is_blizzard_d(&self, (col, row): (usize, usize), time: usize) -> bool {
self.blizzards_d
[col + self.width * ((row + self.height - time % self.height) % self.height)]
}
pub fn is_blizzard(&self, pos: (usize, usize), time: usize) -> bool {
self.is_blizzard_r(pos, time)
|| self.is_blizzard_u(pos, time)
|| self.is_blizzard_l(pos, time)
|| self.is_blizzard_d(pos, time)
}
pub fn print(&self, col: usize, row: usize, time: usize) {
// first row
print!("#");
for col_ in 0..self.width {
if col_ != self.entry {
print!("#");
} else if col_ == col && row == 0 {
print!("E");
} else {
print!(".");
}
}
println!("#");
for row_ in 0..self.height {
print!("#");
for col_ in 0..self.width {
let r = self.is_blizzard_r((col_, row_), time) as u8;
let u = self.is_blizzard_u((col_, row_), time) as u8;
let l = self.is_blizzard_l((col_, row_), time) as u8;
let d = self.is_blizzard_d((col_, row_), time) as u8;
if (r + u + l + d) > 1 {
print!("{}", r + u + l + d);
} else if r > 0 {
print!(">");
} else if u > 0 {
print!("^");
} else if l > 0 {
print!("<");
} else if d > 0 {
print!("v");
} else if row_ + 1 == row && col_ == col {
print!("E");
} else {
print!(".");
}
}
println!("#");
}
// last row
print!("#");
for col_ in 0..self.width {
if col_ != self.exit {
print!("#");
} else if col_ == col && row == self.height + 1 {
print!("E");
} else {
print!(".");
}
}
println!("#");
}
pub fn shortest_path(
&self,
start: (usize, usize),
target: (usize, usize),
start_time: usize,
) -> usize {
let w = self.width;
let h = self.height;
let mut queue = BinaryHeap::new();
// items on the queue are
// - lower bound of time to target (Manhattan distance)
// - time used so far
// - current position (row, col)
queue.push((
!(self.entry.max(self.exit) - self.entry.min(self.exit) + h + 1),
!start_time,
start,
));
// do not visit nodes twice
let mut seen = HashSet::from([(start_time % (w * h), start)]);
while let Some((_n_bound, n_time, (col, row))) = queue.pop() {
let time = !n_time;
if (col, row) == target {
return time;
}
let time_upd = time + 1;
let mut enqueue = |(c, r), t| {
if (r == 0 || r == h + 1 || !self.is_blizzard((c, r - 1), t))
&& seen.insert((t % (w * h), (c, r)))
{
let bound =
target.0.max(c) - target.0.min(c) + target.1.max(r) - target.1.min(r) + t;
queue.push((!bound, !t, (c, r)))
}
};
// move to entry
if row == 1 && col == self.entry {
enqueue((self.entry, 0), time_upd);
}
// move to exit
if row == h && col == self.exit {
enqueue((self.exit, h + 1), time_upd);
}
// don't move at entry or exit or any position where there is no blizzard
enqueue((col, row), time_upd);
// move left (not in entry / exit rows)
if row != 0 && row != h + 1 && col > 0 {
enqueue((col - 1, row), time_upd);
}
// move up (not in entry row and row immediately below)
if row > 1 {
enqueue((col, row - 1), time_upd);
}
// move right (not in entry / exit rows)
if row != 0 && row != h + 1 && col < w - 1 {
enqueue((col + 1, row), time_upd);
}
// move down (not in exit row and row immediately above)
if row < h {
enqueue((col, row + 1), time_upd);
}
}
panic!(
"I've seen {} nodes but did not find a path from {start:?} at t = {start_time} to {target:?}",
seen.len()
);
}
}
pub fn star_1(data: &PuzzleData) -> usize {
data.shortest_path((data.entry, 0), (data.exit, data.height + 1), 0)
}
Star 2
My initial implementation was not quite generic (I never went back to the entry and actually stopped the search one step before the exit). Making it bi-directional was a simple extension.
1
2
3
4
5
6
7
pub fn star_2(data: &PuzzleData) -> usize {
let start = (data.entry, 0);
let target = (data.exit, data.height + 1);
let m1 = data.shortest_path(start, target, 0);
let m2 = data.shortest_path(target, start, m1);
data.shortest_path(start, target, m2)
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#
"#;
const CONTENT_SIMPLE: &str = r#"#.#####
#.....#
#>....#
#.....#
#...v.#
#.....#
#####.#
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
assert_eq!(24, data.blizzards_r.len());
assert_eq!(24, data.blizzards_u.len());
assert_eq!(24, data.blizzards_l.len());
assert_eq!(24, data.blizzards_d.len());
assert_eq!(6, data.width);
assert_eq!(0, data.entry);
assert_eq!(5, data.exit);
println!("{data:?}");
}
#[test]
pub fn test_blizzards_move() {
let data = PuzzleData::from(CONTENT_SIMPLE);
for time in 0..=12 {
println!("t = {time}");
data.print(data.entry, 0, time);
}
}
#[test]
pub fn test_blizzards_is_blizzard() {
let data = PuzzleData::from(CONTENT);
println!(
"entry: ({}, 0), exit: ({}, {})",
data.entry,
data.exit,
data.height + 1
);
let steps_col = [0, 0, 0, 0, 1, 1, 0, -1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0];
let steps_row = [1, 1, 0, -1, 0, 0, 1, 0, -1, 0, 0, 1, 1, 0, 0, 0, 1, 1];
let mut time = 0;
let mut col: usize = 0;
let mut row: usize = 0;
for k in 0..steps_col.len() {
col = col.wrapping_add_signed(steps_col[k]);
row = row.wrapping_add_signed(steps_row[k]);
time += 1;
println!("t = {time}: ({col}, {row})");
data.print(col, row, time);
assert!(row == data.height + 1 || !data.is_blizzard((col, row - 1), time));
}
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(18, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(54, star_2(&data));
}
}
Day 25: Full of Hot Air
Rust solution to AoC|2022|25.
A nice, simple last one for Christmas!
Star 1
There is not much to say. Here is the solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
pub fn star_1(data: &&str) -> String {
// convert SNAFU to decimal and sum
let mut sum: isize = data
.lines()
.map(|l| {
l.as_bytes().iter().fold(0, |value, &digit| {
5 * value
+ match digit {
b'2' => 2,
b'1' => 1,
b'0' => 0,
b'-' => -1,
b'=' => -2,
_ => unreachable!(),
}
})
})
.sum();
// convert decimal to SNAFU
let mut digits = Vec::new();
while sum != 0 {
let v = sum % 5;
sum /= 5;
if v > 2 {
sum += 1;
}
digits.push(match v {
3 => '=',
4 => '-',
0 => '0',
1 => '1',
2 => '2',
_ => unreachable!(),
});
}
digits.iter().rev().collect()
}
Tests
And the tests:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"1=-0-2
12111
2=0=
21
2=01
111
20012
112
1=-1=
1-12
12
1=
122
"#;
#[test]
pub fn test_star_1() {
assert_eq!("2=-1=0", star_1(&CONTENT));
}
}