So here we go for the 10th anniversary of advent of code…
Day 1: Historian Hysteria
Rust solution to AoC|2024|1.
Abstract: Compare two lists.
Input
We have two lists side by side. I parse the numbers in a flat list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<usize>);
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(
s.as_ref()
.split_ascii_whitespace()
.map(str::parse)
.collect::<Result<_, _>>()
.unwrap(),
)
}
}
}
Star 1
Extract the first and the second list, sort them and sum the differences.
1
2
3
4
5
6
7
8
9
10
pub fn star_1(PuzzleData(data): &PuzzleData) -> usize {
let mut d1 = data.iter().step_by(2).copied().collect::<Vec<_>>();
let mut d2 = data.iter().skip(1).step_by(2).copied().collect::<Vec<_>>();
d1.sort_unstable();
d2.sort_unstable();
d1.into_iter()
.zip(d2)
.map(|(a, b)| b.max(a) - b.min(a))
.sum()
}
Star 2
Count number of occurrences in the second list into a hash map and iterate over the first list to calculate and sum similarity scores.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn star_2(PuzzleData(data): &PuzzleData) -> usize {
let occurrences = data
.iter()
.skip(1)
.step_by(2)
.fold(HashMap::new(), |mut occurrences, b| {
*occurrences.entry(b).or_insert(0) += 1;
occurrences
});
data.iter()
.step_by(2)
.map(|a| a * occurrences.get(a).unwrap_or(&0))
.sum()
}
Day 2: Red-Nosed Reports
Rust solution to AoC|2024|2.
Abstract: Verify monotonicity and limited step size of sequences of numbers ('reports'), allow one outlier in part two.
Input
Parse input into a vec of reports, each represented by a vec.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<Vec<usize>>);
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(
s.as_ref()
.lines()
.map(|line| {
line.split_ascii_whitespace()
.map(str::parse)
.collect::<Result<_, _>>()
})
.collect::<Result<_, _>>()
.unwrap(),
)
}
}
}
Star 1
Count the number of safe reports using the is_safe function.
To make the code re-usable, pass the report as any type that can be converted into an iterator over references to integers.
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 is_safe<'a, T: IntoIterator<Item = &'a usize>>(report: T) -> bool {
let mut it = report.into_iter();
let mut inc = None;
let Some(mut previous) = it.next().copied() else {
return false;
};
for ¤t in it {
let nok = if *inc.get_or_insert(current > previous) {
previous >= current || current > previous + 3
} else {
current >= previous || previous > current + 3
};
if nok {
return false;
}
previous = current;
}
true
}
pub fn star_1(PuzzleData(data): &PuzzleData) -> usize {
data.iter().filter(|&report| is_safe(report)).count()
}
Star 2
I first tried to find some clever solution that does not require to actually remove elements from the report and check the remaining report for safety. - I failed.
At least, because the is_safe function only requires a type that can be converted into an iterator, there is no need for intermediate allocations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
fn is_safe_with_damper(report: &[usize]) -> bool {
(0..report.len()).any(|k| {
is_safe(
report
.iter()
.enumerate()
.filter(|(i, _)| *i != k)
.map(|(_, v)| v),
)
})
}
pub fn star_2(PuzzleData(data): &PuzzleData) -> usize {
data.iter()
.filter(|report| is_safe_with_damper(report))
.count()
}
Day 3: Mull It Over
Rust solution to AoC|2024|3.
Abstract: Find patterns representing multiplications in a string, exclude some regions in part 2.
The puzzle descriptions shouts regular expression at me. But since there is no regular expressions in Rust’s standard library, I’ll do it manually.
Star 1
Find the valid multiplications and add the products to 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
const OPEN: &str = "mul(";
const COMMA: char = ',';
const CLOSE: char = ')';
pub fn star_1(data: &&str) -> usize {
let mut data = *data;
let mut sum = 0;
while let Some(start) = data.find(OPEN) {
let mut a = 0;
let mut b = 0;
let mut current = &mut a;
let mut first = true;
let mut len = OPEN.len();
for c in data[start + OPEN.len()..].chars() {
if c.is_ascii_digit() {
*current = *current * 10 + ((c as u8) - b'0') as usize;
} else if c == COMMA && first {
current = &mut b;
first = false;
} else {
if c == CLOSE && !first {
sum += a * b;
}
data = &data[start + len..];
break;
}
len += 1;
}
}
sum
}
Star 2
Call the star_1 functions for the regions that are not excluded by don’t() instructions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const ACTIVATE: &str = "do()";
const DEACTIVATE: &str = "don't()";
pub fn star_2(data: &&str) -> usize {
let mut data = *data;
let mut pattern = DEACTIVATE;
let mut sum = 0;
while !data.is_empty() {
let start = data.find(pattern).unwrap_or(data.len());
if pattern == DEACTIVATE {
sum += star_1(&&data[..start]);
pattern = ACTIVATE;
} else {
pattern = DEACTIVATE;
}
data = &data[start..];
}
sum
}
Day 4: Ceres Search
Rust solution to AoC|2024|4.
Abstract: Word search in a grid.
Input
I use my Grid utility to parse the input. Adding a boundary avoids boundary checks later.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub mod input {
use crate::*;
use mr_kaffee_utils::grids::MakeGrid;
#[derive(Debug)]
pub struct PuzzleData(pub Grid);
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(s.as_ref().make_grid(Some(0)))
}
}
}
Star 1
Search all occurrences of X in the grid. Then search from these locations for MAS in all directions.
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
const DIRS: [(isize, isize); 8] = [
(1, 0),
(1, 1),
(0, 1),
(-1, 1),
(-1, 0),
(-1, -1),
(0, -1),
(1, -1),
];
pub fn star_1(PuzzleData(grid): &PuzzleData) -> usize {
grid.data()
.iter()
.positions(|c| **c == b'X')
.map(|idx| grid.to_col_row(idx))
.map(|(col, row)| {
DIRS.into_iter()
.filter(|&(dx, dy)| {
(1..4)
.map(|step| {
grid[(
col.wrapping_add_signed(step * dx),
row.wrapping_add_signed(step * dy),
)]
})
.zip([b'M', b'A', b'S'])
.all(|(a, b)| a == b)
})
.count()
})
.sum()
}
Star 2
Search all occurrences of A in the grid. Then verify that these locations are the center of two MAS in the shape of an X.
1
2
3
4
5
6
7
8
9
10
11
12
13
pub fn star_2(PuzzleData(grid): &PuzzleData) -> usize {
grid.data()
.iter()
.positions(|c| **c == b'A')
.map(|idx| grid.to_col_row(idx))
.filter(|(col, row)| {
(grid[(col - 1, row - 1)] == b'M' && grid[(col + 1, row + 1)] == b'S'
|| grid[(col - 1, row - 1)] == b'S' && grid[(col + 1, row + 1)] == b'M')
&& (grid[(col - 1, row + 1)] == b'M' && grid[(col + 1, row - 1)] == b'S'
|| grid[(col - 1, row + 1)] == b'S' && grid[(col + 1, row - 1)] == b'M')
})
.count()
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
"#;
#[test]
pub fn test_star_1() {
assert_eq!(18, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(9, star_2(&CONTENT.into()));
}
}
Day 5: Print Queue
Rust solution to AoC|2024|5.
Abstract: Check consistency of sequences of numbers (part 1) or partially sort the sequences (part 2) given rules that define a partial ordering of the numbers.
Input
The input is parsed in a rules part (a hashmap mapping numbers that shall appear first to a set of numbers that shall appear later) and an updates part (a list of lists).
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 {
use crate::*;
#[derive(Debug)]
pub struct PuzzleData {
pub rules: RulesT,
pub updates: Vec<Vec<usize>>,
}
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
let (rules, updates) = s.as_ref().split_once("\n\n").unwrap();
let rules = rules
.lines()
.map(|l| l.split_once("|").unwrap())
.map(|(a, b)| (a.parse().unwrap(), b.parse().unwrap()))
.fold(RulesT::new(), |mut rules, (a, b)| {
rules.entry(a).or_default().insert(b);
rules
});
let updates = updates
.lines()
.map(|l| l.split(',').map(str::parse).collect::<Result<_, _>>())
.collect::<Result<_, _>>()
.unwrap();
Self { rules, updates }
}
}
}
Star 1
The function is_consistent verifies consistency of a single update by iterating over the numbers of the update and verifying that the numbers that shall appear after the current number did not appear earlier in the update.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
fn is_consistent(rules: &RulesT, update: &[usize]) -> bool {
update
.iter()
.enumerate()
.all(|(k, value)| match rules.get(value) {
Some(rule) => !update[..k].iter().any(|v| rule.contains(v)),
_ => true,
})
}
pub fn star_1(data: &PuzzleData) -> usize {
data.updates
.iter()
.filter(|update| is_consistent(&data.rules, update))
.map(|update| update[update.len() >> 1])
.sum()
}
Star 2
The function is_consistent from part 1 is used to find the inconsistent updates.
The function find_mid partially sorts these inconsistent updates. It uses the fact that the left most element is the only one that does not appear in the rules of any other element. Once the left-most element is settled, the left-most element of the remaining list can be determined and so on until the middle element is settled.
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 find_mid(rules: &RulesT, update: &[usize]) -> usize {
let mut update = update.to_vec();
for k in 0..=update.len() >> 1 {
let idx = update[k..]
.iter()
.position(|&a| {
update[k..].iter().all(|&b| {
a == b
|| !rules
.get(&b)
.map(|rule| rule.contains(&a))
.unwrap_or_default()
})
})
.unwrap();
update.swap(k, k + idx);
}
update[update.len() >> 1]
}
pub fn star_2(data: &PuzzleData) -> usize {
data.updates
.iter()
.filter(|update| !is_consistent(&data.rules, update))
.map(|update| find_mid(&data.rules, update))
.sum()
}
Day 6: Guard Gallivant
Rust solution to AoC|2024|6.
Abstract: predict (part 1) and manipulate (part 2) a guard’s motion on a 2D grid.
Input
The input is a grid, so once again, I use my Grid utility.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub mod input {
use mr_kaffee_utils::grids::MakeGrid;
use crate::*;
#[derive(Debug, Clone)]
pub struct PuzzleData {
pub grid: Grid,
}
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self {
grid: s.as_ref().make_grid(None),
}
}
}
}
Star 1
The function path_iter returns an iterator over the path of the guard using successors, until the path leaves the grid.
The solution for star 1 collects the positions represented by the elements returned by the iterator into a set and returns the length of the set.
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
const DELTAS: &[(isize, isize)] = &[(0, -1), (1, 0), (0, 1), (-1, 0)];
impl PuzzleData {
fn start(&self) -> (usize, usize, usize) {
let (col, row) = self
.grid
.to_col_row(self.grid.iter().position(|c| *c == b'^').unwrap());
(col, row, 0)
}
fn path_iter_from_start(
&self,
(col, row, dir): (usize, usize, usize),
) -> impl Iterator<Item = (usize, usize, usize)> + '_ {
successors(Some((col, row, dir)), |&(col, row, direction)| {
let (d_col, d_row) = DELTAS[direction];
let (col_upd, row_upd) = (
col.wrapping_add_signed(d_col),
row.wrapping_add_signed(d_row),
);
if col_upd >= self.grid.width() || row_upd >= self.grid.height() {
None
} else if self.grid[(col_upd, row_upd)] == b'#' {
Some((col, row, (direction + 1) % 4))
} else {
Some((col_upd, row_upd, direction))
}
})
}
fn path_iter(&self) -> impl Iterator<Item = (usize, usize, usize)> + '_ {
self.path_iter_from_start(self.start())
}
}
pub fn star_1(data: &PuzzleData) -> usize {
data.path_iter()
.map(|(col, row, _)| (col, row))
.collect::<HashSet<_>>()
.len()
}
Star 2
Walk the original path, simulate adding blocks on the way and check for each added block if the path repeats, i.e., the guard is trapped in a 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
pub fn star_2(data: &PuzzleData) -> usize {
let mut data_mut = data.clone(); // mutable copy to add new obstacles
let mut visited = vec![0u8; data.grid.len()]; // visited points
let mut blocks = vec![false; data.grid.len()]; // blocks added
let mut result = 0; // count of blocks added
let mut it = data.path_iter().peekable();
while let Some((col, row, dir)) = it.next() {
visited[col + row * data.grid.width()] |= 1 << dir; // mark visited
// peek next point
let Some(&(col_nxt, row_nxt, dir_nxt)) = it.peek() else {
continue;
};
// if direction did not change and next point is not blocked nor visited, check if path repeats by adding block
let pos_nxt = col_nxt + row_nxt * data.grid.width();
if dir == dir_nxt && !blocks[pos_nxt] && visited[pos_nxt] == 0 {
data_mut.grid[pos_nxt] = b'#';
if data_mut
.path_iter_from_start((col, row, (dir + 1) % 4))
.scan(visited.clone(), |visited, (col, row, dir)| {
if visited[col + row * data.grid.width()] & 1 << dir != 0 {
Some(true) // point seen before
} else {
visited[col + row * data.grid.width()] |= 1 << dir;
Some(false) // point not seen before
}
})
.any(bool::from)
{
blocks[pos_nxt] = true;
result += 1;
}
data_mut.grid[pos_nxt] = b'.';
}
}
result
}
Day 7: Bridge Repair
Rust solution to AoC|2024|7.
Abstract: Find operators (multiplication, addition and - in part 2 - digit concatenation) to reproduce test values from lists of operands.
Input
Read into a list of tuples of test values and list of operand values.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<(usize, Vec<usize>)>);
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(
s.as_ref()
.lines()
.map(|s| {
let mut it = s
.split(&[' ', ':'])
.filter(|v| !v.is_empty())
.map(|s| s.parse().unwrap());
(it.next().unwrap(), it.collect())
})
.collect(),
)
}
}
}
Star 1
Nothing but brute force here.
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
fn update_values_add_mul(a: usize, b: usize) -> [usize; 2] {
[a + b, a * b]
}
fn find_ops<T, F>(test: usize, current: usize, values: &[usize], f: &F) -> bool
where
T: IntoIterator<Item = usize>,
F: Fn(usize, usize) -> T,
{
if values.is_empty() {
return test == current;
} else if current > test {
return false;
}
f(current, values[0])
.into_iter()
.any(|update| find_ops(test, update, &values[1..], f))
}
pub fn solve<T, F>(PuzzleData(data): &PuzzleData, f: F) -> usize
where
T: IntoIterator<Item = usize>,
F: Fn(usize, usize) -> T,
{
data.iter()
.filter(|(test, values)| find_ops(*test, values[0], &values[1..], &f))
.map(|(test, _)| test)
.sum()
}
pub fn star_1(data: &PuzzleData) -> usize {
solve(data, update_values_add_mul)
}
Star 2
A bit more brute force and concatenation of decimal digits.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn concatenate(mut a: usize, b: usize) -> usize {
let mut x = b;
while x > 0 {
x /= 10;
a *= 10;
}
a + b
}
fn update_values_add_mul_con(a: usize, b: usize) -> [usize; 3] {
[a + b, a * b, concatenate(a, b)]
}
pub fn star_2(data: &PuzzleData) -> usize {
solve(data, update_values_add_mul_con)
}
Day 8: Resonant Collinearity
Rust solution to AoC|2024|8.
Abstract: Find grid positions that are in line with pairs of antennas of the same type.
Input
Input processing is used to determine grid dimensions only.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub mod input {
#[derive(Debug)]
pub struct PuzzleData<'a> {
pub data: &'a str,
pub w: usize,
pub h: usize,
}
impl<'a, T> From<&'a T> for PuzzleData<'a>
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
let data = s.as_ref();
let w = data.bytes().position(|b| b == b'\n').unwrap_or(data.len());
let h = data.as_bytes().len() / (w + 1);
Self { data, w, h }
}
}
}
Star 1
First construct a map of antenna types to list of antenna positions.
Then determine the resonant locations for any pair of antennas of the same type and add it to a counter. The helper function resonants_1 is used for this purpose. Given two antenna locations, it returns an iterator over resonant locations that are contained in the grid.
Finally, return the number of resonant locations.
There is two counter implementations: one using a Vec (the default), and one using a HashSet (feature hash_set). Vector based counting is significantly faster.
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
impl PuzzleData<'_> {
/// Converts a 1D index into the data to 2D coordinates (col, row).
pub fn to_col_row(&self, pos: usize) -> (usize, usize) {
(pos % (self.w + 1), pos / (self.w + 1))
}
/// Returns the next location in direction (d_col, d_row) from (col, row)
/// if it is within the bounds of the data.
pub fn next_pos(
&self,
(col, row): &(usize, usize),
(d_col, d_row): (isize, isize),
) -> Option<(usize, usize)> {
Some((
col.wrapping_add_signed(d_col),
row.wrapping_add_signed(d_row),
))
.filter(|&(col, row)| col < self.w && row < self.h)
}
}
impl PuzzleData<'_> {
#[cfg(feature = "hash_set")]
fn init_counter<V>(&self) -> HashSet<V> {
HashSet::new()
}
#[cfg(not(feature = "hash_set"))]
fn init_counter(&self) -> (usize, Vec<bool>, impl Fn((usize, usize)) -> usize + '_) {
(0, vec![false; self.w * self.h], |(c, r)| c + r * self.w)
}
}
trait ResonantCounter<V> {
fn count(self) -> usize;
fn update<T: IntoIterator<Item = V>>(self, positions: T) -> Self;
}
impl<V: Hash + Eq> ResonantCounter<V> for HashSet<V> {
fn count(self) -> usize {
self.len()
}
fn update<T: IntoIterator<Item = V>>(mut self, positions: T) -> Self {
self.extend(positions);
self
}
}
impl<V, F: Fn(V) -> usize> ResonantCounter<V> for (usize, Vec<bool>, F) {
fn count(self) -> usize {
self.0
}
fn update<T: IntoIterator<Item = V>>(mut self, positions: T) -> Self {
for idx in positions.into_iter().map(&self.2) {
let s = &mut self.1[idx];
if !*s {
self.0 += 1;
*s = true;
}
}
self
}
}
fn resonants_1(
data: &PuzzleData,
(col_a, row_a): (usize, usize),
(col_b, row_b): (usize, usize),
) -> impl Iterator<Item = (usize, usize)> {
let (d_col, d_row) = (
col_b as isize - col_a as isize,
row_b as isize - row_a as isize,
);
data.next_pos(&(col_b, row_b), (d_col, d_row))
.into_iter()
.chain(data.next_pos(&(col_a, row_a), (-d_col, -d_row)))
}
/// Returns the number of resonants in the data.
///
/// The function f determines the resonant locations given the positions of two antennas.
pub fn star<
'a,
T: Iterator<Item = (usize, usize)> + 'a,
F: Fn(&'a PuzzleData, (usize, usize), (usize, usize)) -> T,
>(
data: &'a PuzzleData,
f: F,
) -> usize {
data.data
.bytes()
.enumerate()
.filter(|&(_, b)| b != b'.' && b != b'\n')
.fold(HashMap::<_, Vec<_>>::new(), |mut map, (pos, value)| {
map.entry(value).or_default().push(data.to_col_row(pos));
map
})
.into_iter()
.fold(data.init_counter(), |counter, (_, positions)| {
positions
.iter()
.enumerate()
.flat_map(|(k, &a)| positions[k + 1..].iter().map(move |&b| (a, b)))
.map(|(a, b)| f(data, a, b))
.fold(counter, |counter, positions| counter.update(positions))
})
.count()
}
Star 2
The only change to star 1 is how the resonant locations are determined.
For this second star, I used my greatest common divisor utility function to determine the distance between two neighboring resonant locations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn resonants_2<'a>(
data: &'a PuzzleData,
(col_a, row_a): (usize, usize),
(col_b, row_b): (usize, usize),
) -> impl Iterator<Item = (usize, usize)> + 'a {
let (d_col, d_row) = (
col_b as isize - col_a as isize,
row_b as isize - row_a as isize,
);
let g = gcd(d_col.abs(), d_row.abs());
let (d_col, d_row) = (d_col / g, d_row / g);
successors(Some((col_a, row_a)), move |pos| {
data.next_pos(pos, (d_col, d_row))
})
.chain(successors(
data.next_pos(&(col_a, row_a), (-d_col, -d_row)),
move |pos| data.next_pos(pos, (-d_col, -d_row)),
))
}
Day 9: Disk Fragmenter
Rust solution to AoC|2024|9.
Abstract: Disk defragmentation. Make as much contiguous free space at the end as possible. Part 2 adds the constraint of avoiding fragmentation of blocks.
Star 1
Have two iterators over the used blocks. One starting from the left, one starting from the right.
Process the blocks from the left and fill the gaps with the blocks from the right.
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
fn sum_positions(pos: usize, len: usize) -> usize {
((pos + len).wrapping_add_signed(-1) * (pos + len) - (pos.wrapping_add_signed(-1)) * pos) / 2
}
pub fn star_1(data: &&str) -> usize {
let mut it_fwd = data
.bytes()
.scan(0, |pos, len| {
let v = (*pos, (len - b'0') as usize);
*pos += v.1;
Some(v)
})
.step_by(2)
.enumerate()
.peekable();
let mut it_rev = (0..(data.len() + 1) >> 1)
.rev()
.map(|pos| (pos, (data.as_bytes()[pos << 1] - b'0') as usize));
let mut result = 0;
let (mut id_rev, mut len_rev) = it_rev.next().unwrap();
while let Some((id_fwd, (mut pos_fwd, mut len_fwd))) = it_fwd.next() {
match id_fwd.cmp(&id_rev) {
Ordering::Greater => break,
Ordering::Equal => len_fwd = len_rev,
Ordering::Less => (),
}
// add the sum of the current block
result += id_fwd * sum_positions(pos_fwd, len_fwd);
// fill the free block with blocks taken from the end
pos_fwd += len_fwd;
let &(_, (pos_fwd_next, _)) = it_fwd.peek().unwrap();
let mut len = len_rev.min(pos_fwd_next - pos_fwd);
while len > 0 && id_rev > id_fwd {
result += id_rev * sum_positions(pos_fwd, len);
pos_fwd += len;
len_rev -= len;
if len_rev == 0 {
(id_rev, len_rev) = it_rev.next().unwrap();
}
len = len_rev.min(pos_fwd_next - pos_fwd);
}
}
result
}
Star 2
Iterate over used blocks from the right. Find the first free block that fits (if any).
The sentence 'Attempt to move each file exactly once in order of decreasing file ID number starting with the file with the highest file ID number' is important. It allows to discard larger contiguous free space that is created at the right when moving used blocks into free blocks to the left.
Storing the max_len and skipping the search for free blocks that are too large saves a significant bit of run time.
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
pub fn star_2(data: &&str) -> usize {
let (used, mut free, _) = data.bytes().enumerate().fold(
(
Vec::with_capacity((data.len() + 1) >> 1),
Vec::with_capacity(data.len() >> 1),
0,
),
|(mut used, mut free, pos), (k, b)| {
let v = (b - b'0') as usize;
if k & 1 == 0 {
used.push((k >> 1, pos, v));
} else {
free.push((k >> 1, pos, v));
}
(used, free, pos + v)
},
);
let mut max_len = usize::MAX;
used.into_iter()
.rev()
.map(|(id, pos, len)| {
let pos = if len >= max_len {
pos
} else if let Some((free_idx, &(_, free_pos, _))) = free
.iter()
.enumerate()
.take_while(|&(_, &(_, free_pos, _))| free_pos < pos)
.find(|&(_, &(_, _, free_len))| free_len >= len)
{
free[free_idx].1 += len;
free[free_idx].2 -= len;
free_pos
} else {
max_len = max_len.min(len);
pos
};
id * sum_positions(pos, len)
})
.sum()
}
Day 10: Hoof It
Rust solution to AoC|2024|10.
Abstract: Find trails, i.e., paths from 0 to 9 in a grid.
The first graph traversal solution this year.
Input
Another day for a Grid with boundary.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pub mod input {
use mr_kaffee_utils::grids::MakeGrid;
use super::*;
#[derive(Debug)]
pub struct PuzzleData(pub Grid);
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(s.as_ref().make_grid(Some(0)))
}
}
}
Star 1
How many tails can be reached from a head: simple breadth-first search starting from all trail heads (0 values), counting the number of trail tails (9 values) reached.
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
pub trait SeenChecker {
fn for_grid(grid: &Grid) -> Self;
fn check_and_update(&mut self, pos: (usize, usize), grid: &Grid) -> bool;
fn reset(&mut self);
}
impl SeenChecker for Vec<bool> {
fn for_grid(grid: &Grid) -> Self {
vec![false; grid.width() * grid.height()]
}
fn check_and_update(&mut self, (col, row): (usize, usize), grid: &Grid) -> bool {
let s = &mut self[col + grid.width() * row];
if !*s {
*s = true;
false
} else {
true
}
}
fn reset(&mut self) {
self.fill(false);
}
}
pub fn star<T: SeenChecker>(PuzzleData(grid): &PuzzleData) -> usize {
let mut seen = T::for_grid(grid);
grid.iter()
.positions(|&&value| value == b'0')
.map(|idx| grid.to_col_row(idx))
.map(|pos| {
seen.reset();
seen.check_and_update(pos, grid);
let mut queue = VecDeque::from([pos]);
let mut tails = 0;
while let Some((c, r)) = queue.pop_front() {
let value = grid[(c, r)];
if value == b'9' {
tails += 1;
continue;
}
for pos in [(c + 1, r), (c, r - 1), (c - 1, r), (c, r + 1)]
.into_iter()
.filter(|&pos| grid[pos] == value + 1)
{
if !seen.check_and_update(pos, grid) {
queue.push_back(pos);
}
}
}
tails
})
.sum()
}
Star 2
How many different ways exist to reach any tail from a head: just remove the seen check from the solution of part 1. I did this by defining a SeenChecker trait and implementing it for the unit type () to always yield false.
1
2
3
4
5
6
7
8
9
impl SeenChecker for () {
fn for_grid(_: &Grid) -> Self {}
fn check_and_update(&mut self, _: (usize, usize), _: &Grid) -> bool {
false
}
fn reset(&mut self) {}
}
Day 11: Plutonian Pebbles
Rust solution to AoC|2024|11.
Abstract: Simulate repeated update steps on a sequence of numbers ('stones').
The key to this puzzle was to realize that the positions of the stones do not matter. So I only count the number of stones with a given value. In part two, after 75 iterations, there are less than 4000 distinct values on almost 250 trillion stones.
Star 1
The input is first parsed into a map with numbers seen on stones as keys and frequencies of occurrence as values.
The step function applies the rules to update the stones. As an optimization, I use two hash maps alternatingly as current map and updated map, to reduce the number of allocations.
All that is left to do is call the step function 25 times and sum the frequencies of occurrence for each distinct number seen on any stone.
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
fn step(
(cur, mut upd): (HashMap<usize, usize>, HashMap<usize, usize>),
) -> (HashMap<usize, usize>, HashMap<usize, usize>) {
upd.clear();
upd = cur.iter().fold(upd, |mut upd, (&v, &n)| {
if v == 0 {
*upd.entry(1).or_default() += n;
} else {
let n_digits = successors(Some(v), |v| Some(v / 10))
.take_while(|&v| v > 0)
.count();
if n_digits & 1 == 0 {
let fac = usize::pow(10, (n_digits >> 1) as u32);
*upd.entry(v / fac).or_default() += n;
*upd.entry(v % fac).or_default() += n;
} else {
*upd.entry(v * 2024).or_default() += n;
}
}
upd
});
(upd, cur)
}
pub fn star(data: &&str, iterations: usize) -> usize {
let map = data
.split_ascii_whitespace()
.map(str::parse)
.fold(HashMap::new(), |mut map, v| {
*map.entry(v.unwrap()).or_default() += 1;
map
});
(0..iterations)
.fold((map, HashMap::new()), |maps, _| step(maps))
.0
.values()
.sum()
}
Star 2
Just repeat the process 75 times.
Day 12: Garden Groups
Rust solution to AoC|2024|12.
Abstract: Find area and perimeter (part 1) or sides (part 2) of contiguous groups in a grid.
Input
Again, parse the input into a Grid with boundary.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub mod input {
use mr_kaffee_utils::grids::{Grid, MakeGrid};
#[derive(Debug)]
pub struct PuzzleData(pub Grid);
impl<'a, T> From<&'a T> for PuzzleData
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(s.as_ref().make_grid(Some(0)))
}
}
}
Star 1
Explore the garden using depth-first searches (breadth-first would work just as well) to find the contiguous groups of plants. Whenever a different plant type is found, the perimeter of the group is increased. The lefts parameter in the check function is ignored in part 1, the check function returns true unconditionally.
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 fn star<F: Fn(((usize, usize), (usize, usize)), &Grid, u8) -> bool>(
PuzzleData(grid): &PuzzleData,
check: F,
) -> usize {
let mut cost = 0;
let mut seen = vec![false; grid.len()];
let mut queue = Vec::new();
let mut start = 0;
while let Some(offset) = grid.data()[start..]
.iter()
.zip(&seen[start..])
.position(|(&value, &s)| value != 0 && !s)
{
start += offset;
let (value, mut area, mut sides) = (grid[start], 0, 0);
seen[start] = true;
queue.push(grid.to_col_row(start));
while let Some((col, row)) = queue.pop() {
area += 1;
for ((col_nxt, row_nxt), lefts) in [
// check additional tiles on the left in the direction of moving (move from X to 0, check A and B)
// B0 AB XA 0X
// AX X0 0B BA
((col, row + 1), ((col - 1, row), (col - 1, row + 1))),
((col + 1, row), ((col, row + 1), (col + 1, row + 1))),
((col, row - 1), ((col + 1, row), (col + 1, row - 1))),
((col - 1, row), ((col, row - 1), (col - 1, row - 1))),
] {
if grid[(col_nxt, row_nxt)] != value {
if check(lefts, grid, value) {
sides += 1;
}
} else {
let s = &mut seen[grid.to_idx((col_nxt, row_nxt))];
if !*s {
*s = true;
queue.push((col_nxt, row_nxt));
}
}
}
}
cost += area * sides;
}
cost
}
pub fn star_1(data: &PuzzleData) -> usize {
star(data, |_, _, _| true)
}
Star 2
Almost the same as star 1, but the check function now uses the lefts parameter to only count the left-most element of a side, i.e., to only count unique sides.
1
2
3
4
5
pub fn star_2(data: &PuzzleData) -> usize {
star(data, |(a, b), grid, value| {
grid[a] != value || grid[b] == value
})
}
Day 13: Claw Contraption
Rust solution to AoC|2024|13.
Abstract: Solve a set of two linear equations.
I was a bit confused by the 'minimum' requirement in the problem statement. We have two linear equations with two unknowns. As long as the two equations are not redundant (they aren’t in my input), these equations have exactly one solution in the real numbers. The price can be reached if and only if the solution happens to be in the non-negative integers.
Solving the linear equations directly works for both parts.
Input
The PuzzleData struct is a simple wrapper for the input data, that allows to implement a function that returns an iterator over the games.
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
pub mod input {
pub type CoordT = [isize; 2];
pub type GameT = [CoordT; 3];
#[derive(Debug)]
pub struct PuzzleData<'a>(&'a str);
impl<'a, T> From<&'a T> for PuzzleData<'a>
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(s.as_ref())
}
}
impl<'a> PuzzleData<'a> {
const PREFIXES: [&'static str; 3] = ["Button A: ", "Button B: ", "Prize: "];
const NOISE: [char; 5] = ['X', 'Y', '+', '=', ' '];
pub fn iter(&self) -> impl Iterator<Item = GameT> + 'a {
self.0.split("\n\n").map(|game| {
game.lines()
.zip(Self::PREFIXES)
.map(|(line, prefix)| {
line.strip_prefix(prefix)
.unwrap()
.split(',')
.map(|s| s.trim_matches(Self::NOISE).parse().unwrap())
.fold((CoordT::default(), 0), |(mut coord, idx), value| {
coord[idx] = value;
(coord, idx + 1)
})
.0
})
.fold((GameT::default(), 0), |(mut game, idx), coord| {
game[idx] = coord;
(game, idx + 1)
})
.0
})
}
}
}
Star 1
Solve the equations…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub fn cost_for_prize([[a_x, a_y], [b_x, b_y], [p_x, p_y]]: GameT) -> usize {
// Equations:
// a_x * a + b_x * b = p_x
// a_y * a + b_y * b = p_y
// Solution:
// a = (b_x * p_y - b_y * p_x) / (b_x * a_y - b_y * a_x)
// b = (a_y * p_x - a_x * p_y) / (b_x * a_y - b_y * a_x)
let den = b_x * a_y - b_y * a_x;
assert!(den != 0, "Redundant equations");
let (nom_a, nom_b) = (b_x * p_y - b_y * p_x, a_y * p_x - a_x * p_y);
let (a, b) = (nom_a / den, nom_b / den);
if a >= 0 && b >= 0 && a * den == nom_a && b * den == nom_b {
(3 * a + b) as usize
} else {
0
}
}
pub fn star_1(data: &PuzzleData) -> usize {
data.iter().map(cost_for_prize).sum()
}
Star 2
The same with an offset.
1
2
3
4
5
6
7
8
const OFFSET: isize = 10_000_000_000_000;
pub fn star_2(data: &PuzzleData) -> usize {
data.iter()
.map(|[a, b, [p_x, p_y]]| [a, b, [p_x + OFFSET, p_y + OFFSET]])
.map(cost_for_prize)
.sum()
}
Day 14: Restroom Redoubt
Rust solution to AoC|2024|14.
Abstract: Simulate uniform motion of robots in 2D, wrapping around the edges
Input
A wrapper that allows to iterate over robots.
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 mod input {
type SizedT = isize;
type SizedCoordT = [SizedT; 2];
type SizedRobotT = [SizedCoordT; 2];
pub type UnsizedT = usize;
pub type UnsizedCoordT = (UnsizedT, UnsizedT);
pub type UnsizedRobotT = (UnsizedCoordT, UnsizedCoordT);
#[derive(Debug)]
pub struct PuzzleData<'a>(pub &'a str);
impl<'a, T> From<&'a T> for PuzzleData<'a>
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(s.as_ref())
}
}
impl<'a> PuzzleData<'a> {
pub fn iter(&self, (w, h): UnsizedCoordT) -> impl Iterator<Item = UnsizedRobotT> + 'a {
self.0
.lines()
.map(|line| {
line.split_ascii_whitespace()
.map(|part| {
part.trim_matches(['p', 'v', '='])
.split(',')
.map(str::parse)
.fold((SizedCoordT::default(), 0), |(mut coord, idx), value| {
coord[idx] = value.unwrap();
(coord, idx + 1)
})
.0
})
.fold((SizedRobotT::default(), 0), |(mut robot, idx), coord| {
robot[idx] = coord;
(robot, idx + 1)
})
.0
})
.map(move |[[x, y], [v_x, v_y]]| {
(
(x as UnsizedT, y as UnsizedT),
(
w.wrapping_add_signed(v_x) % w,
h.wrapping_add_signed(v_y) % h,
),
)
})
}
}
}
Star 1
The first part is straight forward: calculate the position of every robot after steps and then count the robots in every quadrant.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn solve_1(data: &PuzzleData, (w, h): UnsizedCoordT, steps: UnsizedT) -> UnsizedT {
data.iter((w, h))
.map(|((x, y), (v_x, v_y))| ((x + steps * v_x) % w, (y + steps * v_y) % h))
.filter_map(|(x, y)| match (x.cmp(&(w >> 1)), y.cmp(&(h >> 1))) {
(std::cmp::Ordering::Equal, _) | (_, std::cmp::Ordering::Equal) => None,
(std::cmp::Ordering::Greater, std::cmp::Ordering::Less) => Some(0),
(std::cmp::Ordering::Less, std::cmp::Ordering::Less) => Some(1),
(std::cmp::Ordering::Less, std::cmp::Ordering::Greater) => Some(2),
(std::cmp::Ordering::Greater, std::cmp::Ordering::Greater) => Some(3),
})
.fold([0; 4], |mut counts, quadrant| {
counts[quadrant] += 1;
counts
})
.into_iter()
.product()
}
pub fn star_1(data: &PuzzleData) -> UnsizedT {
solve_1(data, (101, 103), 100)
}
Star 2
The challenge of the second part is that it seems under-specified. Most of the robots shall end up in a formation that represents a Christmas tree at some time. We don’t know which robots are part of the formation, we don’t know how the Christmas tree looks like and we don’t know when and where exactly it will appear.
The solution idea is to consider movement in x and y direction independently. Movement in x and y direction repeat every width or height steps respectively. Since width and height are co-prime, any constellation of the x coordinates eventually coincides with every constellation of the y coordinates.
For each of the coordinates, we independently search for a time when the coordinates are 'closely together'. Initially, I did that by counting robots in sliding intervals. A much simpler solution is to calculate the variance of the coordinate values (an idea taken from u/i_have_no_buiscuits).
The Christmas tree appears when the variances in x and y coordinates are simultaneously minimized.
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
pub fn star_2(data: &PuzzleData) -> UnsizedT {
let (w, h): UnsizedCoordT = (101, 103);
let robots = data.iter((w, h)).collect::<Vec<_>>();
// find time when where the robot coordinates have the lowest variance for x- and y-direction independently
let (t_x, t_y) = (0..w.max(h))
.map(|t| {
let (_, (_, var_x), (_, var_y)): (f64, (f64, f64), (f64, f64)) = robots
.iter()
.map(|&((x, y), (p, q))| (((x + t * p) % w) as f64, ((y + t * q) % h) as f64))
.fold(
Default::default(),
|(mut n, (mut mx, mut m2x), (mut my, mut m2y)), (x, y)| {
// Welford's algorithm for variance
n += 1.0;
let (dx, dy) = (x - mx, y - my);
(mx, my) = (mx + dx / n, my + dy / n);
(m2x, m2y) = (m2x + dx * (x - mx), m2y + dy * (y - my));
(n, (mx, m2x), (my, m2y))
},
);
(t, var_x, var_y)
})
.fold(None, |mn, (t, var_x, var_y)| match mn {
None => Some(((var_x, t), (var_y, t))),
Some((mn_x, mn_y)) => Some((
if (var_x, t) < mn_x { (var_x, t) } else { mn_x },
if (var_y, t) < mn_y { (var_y, t) } else { mn_y },
)),
})
.map(|((_, t_x), (_, t_y))| (t_x, t_y))
.unwrap_or_default();
// find first time t that is t = t_x + k_x * w and t = t_y + k_y * h for some non-negative integer k_x and k_y
// (t_x + k_x * w + (h - t_y)) = 0 (mod h)
let k_x = ((mul_inverse_mod(w as _, h as _) as UnsizedT) * (t_y + h - t_x)) % h;
#[cfg(feature = "plot")]
println!(
"{}",
to_string(robots.iter().copied(), (w, h), t_x + k_x * w)
);
t_x + k_x * w
}
And here’s the picture and an animation that shows the last couple of steps before the Christmas tree appears, including moments when the variance is minimized in 'y'-direction, in 'x'-direction, and in both directions simultaneously:
Day 15: Warehouse Woes
Rust solution to AoC|2024|15.
Abstract: Simulate movement of 'boxes' on a grid as a robot moves and pushes the boxes.
Input
Split the input in a grid and a list of 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
pub mod input {
#[derive(Debug)]
pub struct PuzzleData<'a>(&'a str);
impl<'a, T> From<&'a T> for PuzzleData<'a>
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(s.as_ref())
}
}
impl<'a> PuzzleData<'a> {
pub fn get(&self) -> (&'a [u8], impl Iterator<Item = (isize, isize)> + 'a) {
self.0
.split_once("\n\n")
.map(|(grid, moves)| {
(
grid.as_bytes(),
moves.bytes().filter_map(|c| match c {
b'<' => Some((-1, 0)),
b'>' => Some((1, 0)),
b'^' => Some((0, -1)),
b'v' => Some((0, 1)),
_ => None,
}),
)
})
.unwrap()
}
}
}
Star 1
For every move, search in the direction of the move for some free space. Stop the search if a wall is hit. Then update the grid in reverse order.
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
fn find_robot(grid: &Grid) -> (usize, usize) {
grid.iter()
.position(|&c| c == b'@')
.map(|pos| grid.to_col_row(pos))
.unwrap()
}
fn gps_score(grid: &Grid, symbol: u8, (fac_col, fac_row): (usize, usize)) -> usize {
grid.iter()
.enumerate()
.filter(|&(_, &b)| b == symbol)
.map(|(idx, _)| grid.to_col_row(idx))
.map(|(c, r)| c * fac_col + r * fac_row)
.sum()
}
pub fn star_1(data: &PuzzleData) -> usize {
let (grid, moves) = data.get();
let mut grid = grid.make_grid(None);
let (mut col, mut row) = find_robot(&grid);
for (d_col, d_row) in moves {
let Some((mut c, mut r)) = successors(
Some((
col.wrapping_add_signed(d_col),
row.wrapping_add_signed(d_row),
)),
|&(c, r)| Some((c.wrapping_add_signed(d_col), r.wrapping_add_signed(d_row))),
)
.take_while(|&pos| grid[pos] != b'#')
.find(|&pos| grid[pos] == b'.') else {
continue;
};
while grid[(c, r)] != b'@' {
let (c_, r_) = (c.wrapping_add_signed(-d_col), r.wrapping_add_signed(-d_row));
grid[(c, r)] = grid[(c_, r_)];
(c, r) = (c_, r_);
}
grid[(c, r)] = b'.';
(col, row) = (c.wrapping_add_signed(d_col), r.wrapping_add_signed(d_row));
}
gps_score(&grid, b'O', (1, 100))
}
Star 2
Since blocks may be moved that are not in line with the position of the robot, use breadth-first search to find all blocks that may be moved. Stop if a wall is hit. If every candidate block has some free space ahead, move the blocks in reverse order.
This time we need to actually swap the grid contents. The breadth first traversal makes sure that we process moves row by 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
72
73
74
75
76
77
78
fn extend_grid(grid: &[u8]) -> Grid {
let w = grid.iter().position(|&b| b == b'\n').unwrap_or(grid.len());
let data = grid.iter().filter(|&&b| b != b'\n').fold(
Vec::with_capacity(2 * grid.len()),
|mut data, &b| {
let (b1, b2) = match b {
b'@' => (b'@', b'.'),
b'O' => (b'[', b']'),
b => (b, b),
};
data.push(b1);
data.push(b2);
data
},
);
(data, 2 * w).into()
}
pub fn star_2(data: &PuzzleData) -> usize {
let (grid, moves) = data.get();
let mut grid = extend_grid(grid);
let (mut col, mut row) = find_robot(&grid);
// reuse vec of positions and queue
let mut positions = Vec::new();
let mut queue = VecDeque::new();
for (d_col, d_row) in moves {
// breadth first search ensures that positions are stored row by row in the positions vec
// push current position to queue
queue.push_back((col, row));
while let Some((c, r)) = queue.pop_front() {
if d_row == 0 || !positions.contains(&(c, r)) {
// add candidate position for moves
positions.push((c, r));
}
let (c_next, r_next) = (c.wrapping_add_signed(d_col), r.wrapping_add_signed(d_row));
match grid[(c_next, r_next)] {
b'#' => {
// hit a wall, clear positions and queue
positions.clear();
queue.clear();
}
b'[' if d_row != 0 => {
// pushing a box vertically in the left position
queue.push_back((c_next, r_next));
queue.push_back((c_next + 1, r_next));
}
b']' if d_row != 0 => {
// pushing a box vertically in the right position
queue.push_back((c_next, r_next));
queue.push_back((c_next - 1, r_next));
}
b'[' | b']' => {
// pushing a box horizontally
queue.push_back((c_next, r_next));
}
b'.' => (),
b => unreachable!("unexpected byte: {}", b as char),
}
}
if !positions.is_empty() {
// move boxes, if move possible
// process positions in reverse order
while let Some((c, r)) = positions.pop() {
let (c_, r_) = (c.wrapping_add_signed(d_col), r.wrapping_add_signed(d_row));
(grid[(c_, r_)], grid[(c, r)]) = (grid[(c, r)], grid[(c_, r_)]);
}
// update robot location
(col, row) = (
col.wrapping_add_signed(d_col),
row.wrapping_add_signed(d_row),
);
}
}
gps_score(&grid, b'[', (1, 100))
}
Day 16: Reindeer Maze
Rust solution to AoC|2024|16.
Abstract: Find the shortest path / all elements on any shortest path through a maze with a penalty on turns.
Star 1
The solution uses Dijkstra’s algorithm. The main algorithm is implemented in the search function, which takes the following arguments:
-
the grid
-
a slice of starting positions with starting costs
-
a function that is used to decide what to do with a state popped from the queue (can be process, skip or return)
-
a function that is used to get an iterator over adjacents from a current state
Adjacents are obtained by an optional turn and a step. Note that a double turn, i.e., going back were we came from, is not a viable option. The only time when a double turn could make sense is at the start, which is handled by adding a second start node.
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
const COST_FWD: usize = 1;
const COST_TURN: usize = 1000;
const EAST: u8 = 0;
const NORTH: u8 = 1;
const WEST: u8 = 2;
const SOUTH: u8 = 3;
type StateT = ((usize, usize), u8); // (col, row), heading
fn adjacents_fwd(
cost: usize,
((col, row), heading): StateT,
) -> impl Iterator<Item = (usize, StateT)> {
[0, 1, 3].into_iter().map(move |turn| {
let heading_nxt = (heading + turn) & 3;
let pos_nxt = match heading_nxt {
EAST => (col + 1, row),
NORTH => (col, row - 1),
WEST => (col - 1, row),
SOUTH => (col, row + 1),
_ => unreachable!(),
};
let cost_nxt = cost + COST_FWD + COST_TURN * (turn & 1) as usize;
(cost_nxt, (pos_nxt, heading_nxt))
})
}
enum What {
Process,
Skip,
Return,
}
fn search<
W: FnMut(usize, StateT) -> What,
It: Iterator<Item = (usize, StateT)>,
A: Fn(usize, StateT) -> It,
>(
grid: &Grid,
starts: &[(StateT, usize)],
mut what: W,
adjacents: A,
) -> (Option<usize>, Grid<[usize; 4]>, Grid<u8>) {
let mut costs: Grid<_> = starts.iter().fold(
([usize::MAX >> 1; 4], grid.width(), grid.height()).into(),
|mut costs, &((pos, heading), cost)| {
costs[pos][heading as usize] = cost;
costs
},
);
let mut queue = BinaryHeap::from_iter(starts.iter().map(|&(state, cost)| (!cost, state)));
let mut settled: Grid = (0, grid.width(), grid.height()).into();
while let Some((cost, (pos, heading))) = queue.pop().map(|(c_inv, s)| (!c_inv, s)) {
let s = &mut settled[pos];
if *s & 1 << heading == 0 {
*s |= 1 << heading;
} else {
continue;
}
match what(cost, (pos, heading)) {
What::Skip => continue,
What::Return => return (Some(cost), costs, settled),
_ => (),
}
for (cost_nxt, (pos_nxt, heading_nxt)) in adjacents(cost, (pos, heading))
.filter(|&(_, (pos, h))| grid[pos] != b'#' && settled[pos] & (1 << h) == 0)
{
let cost_cur = &mut costs[pos_nxt][heading_nxt as usize];
if *cost_cur > cost_nxt {
*cost_cur = cost_nxt;
queue.push((!cost_nxt, (pos_nxt, heading_nxt)));
}
}
}
(None, costs, settled)
}
fn get_data(data: &str) -> (Grid, (usize, usize), (usize, usize)) {
let grid = data.make_grid(None);
let pos_s = grid
.iter()
.position(|&c| c == b'S')
.map(|idx| grid.to_col_row(idx))
.unwrap();
let pos_e = grid
.iter()
.position(|&c| c == b'E')
.map(|idx| grid.to_col_row(idx))
.unwrap();
(grid, pos_s, pos_e)
}
pub fn star_1(data: &&str) -> usize {
let (grid, pos_s, pos_e) = get_data(data);
search(
&grid,
&[((pos_s, EAST), 0)],
|_, (pos, _)| {
if pos == pos_e {
What::Return
} else {
What::Process
}
},
adjacents_fwd,
)
.0
.unwrap()
}
Star 2
The solution idea is to use Dijkstra’s algorithm as before, and then, in a second pass, use again Dijkstra’s algorithm from the target to the starting position. In this second pass, we only expand states where the sum of the forward cost from the start to the current state and the backward cost from the target to the current state equals the optimal cost (this can be interpreted as an A* with the cost forward cost as an heuristic). This way, the backward pass will visit exactly all nodes that are on any optimal path.
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
fn adjacents_rev(
cost: usize,
((col, row), heading): StateT,
) -> impl Iterator<Item = (usize, StateT)> {
let pos_prv = match heading {
EAST => (col - 1, row),
NORTH => (col, row + 1),
WEST => (col + 1, row),
SOUTH => (col, row - 1),
_ => unreachable!(),
};
[0, 1, 3].into_iter().map(move |turn| {
let heading_prv = (heading + turn) & 3;
let cost_prv = cost + COST_FWD + COST_TURN * (turn & 1) as usize;
(cost_prv, (pos_prv, heading_prv))
})
}
#[cfg(feature = "plot")]
pub fn plot(mut grid: Grid, cost: Grid<[usize; 4]>, settled: Grid<u8>) {
for (g, (_, s)) in grid
.iter_mut()
.zip(
cost.data()
.iter()
.map(|c| c.iter().any(|&c| c < usize::MAX >> 1))
.zip(settled.iter().map(|&s| s > 0)),
)
.filter(|&(&mut g, (c, _))| g != b'X' && c)
{
*g = if s { b'x' } else { b'+' };
}
println!("{}", grid);
}
pub fn star_2(data: &&str) -> usize {
let (grid, pos_s, pos_e) = get_data(data);
// minimum cost
let mut min_cost = usize::MAX;
// search forward, save costs to reach any position, stop if cost is larger then optimal cost
let (_, costs_fwd, _settled_fwd) = search(
&grid,
&[((pos_s, EAST), 0), ((pos_s, WEST), 2 * COST_TURN)],
|cost_fwd, (pos, _)| {
if pos == pos_e {
min_cost = cost_fwd;
}
if cost_fwd > min_cost {
What::Return
} else {
What::Process
}
},
adjacents_fwd,
);
// unique places to sit
let mut g = grid.clone();
let mut places = 0;
// search backwards, only expand nodes if forward cost to node + reverse cost to node equals the optimal cost
search(
&grid,
&[
((pos_e, EAST), 0),
((pos_e, NORTH), 0),
((pos_e, WEST), 0),
((pos_e, SOUTH), 0),
],
|cost_rev, (pos, heading)| {
if costs_fwd[pos][heading as usize] + cost_rev == min_cost {
let place = &mut g[pos];
if *place != b'X' {
*place = b'X';
places += 1;
}
What::Process
} else {
What::Skip
}
},
adjacents_rev,
);
#[cfg(feature = "plot")]
plot(g, costs_fwd, _settled_fwd);
places
}
There isn’t actually many distinct shortest paths, as you can see in the picture below:
Day 17: Chronospatial Computer
Rust solution to AoC|2024|17.
Abstract: Simulate a simple 'computer' and reverse engineer it’s program.
Star 1
Just tedious implementation of input parsing and the computer’s operations.
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
#[derive(Debug, Clone, PartialEq, Eq)]
struct Computer {
pub registers: [usize; 3],
pub program: Vec<u8>,
pub ip: usize,
pub outputs: Vec<usize>,
}
impl From<&str> for Computer {
fn from(value: &str) -> Self {
value
.split_once("\n\nProgram: ")
.map(|(r, p)| {
(
r.lines().map(|line| line[12..].parse()).enumerate().fold(
[0; 3],
|mut registers, (k, v)| {
registers[k] = v.unwrap();
registers
},
),
p.trim()
.split(',')
.map(str::parse)
.collect::<Result<_, _>>()
.unwrap(),
)
})
.map(|(registers, program)| Self {
registers,
program,
ip: 0,
outputs: Default::default(),
})
.unwrap()
}
}
impl Computer {
pub fn combo(&self, operand: u8) -> usize {
match operand {
0..4 => operand as _,
4..7 => self.registers[(operand - 4) as usize],
7 => panic!("Invalid operand"),
_ => unreachable!(),
}
}
pub fn op(&mut self) {
let instruction = self.program[self.ip];
let operand = self.program[self.ip + 1];
match instruction {
0 => {
self.registers[0] >>= self.combo(operand);
self.ip += 2;
} // adv
1 => {
self.registers[1] ^= operand as usize;
self.ip += 2;
} // bxl
2 => {
self.registers[1] = self.combo(operand) & 0b111;
self.ip += 2;
} // bst
3 => {
if self.registers[0] != 0 {
self.ip = operand as _;
} else {
self.ip += 2;
}
} // jnz
4 => {
self.registers[1] ^= self.registers[2];
self.ip += 2;
} // bxc
5 => {
self.outputs.push(self.combo(operand) & 0b111);
self.ip += 2;
} // out,
6 => {
self.registers[1] = self.registers[0] >> self.combo(operand);
self.ip += 2;
} // bdv,
7 => {
self.registers[2] = self.registers[0] >> self.combo(operand);
self.ip += 2;
} // cdv,
_ => unreachable!(),
}
}
pub fn run(&mut self) {
while self.ip < self.program.len() {
self.op();
}
}
pub fn output_string(&self) -> String {
let mut output = String::new();
let mut it = self.outputs.iter().peekable();
while let Some(v) = it.next() {
output.push_str(&v.to_string());
if it.peek().is_some() {
output.push(',');
}
}
output
}
}
pub fn star_1(&data: &&str) -> String {
let mut computer = Computer::from(data);
computer.run();
computer.output_string()
}
Star 2
Not a day for brute force.
A bit of reverse engineering reveals that:
-
There are iterations, each produces one output
-
In each iteration, the program only depends on the value of the register
Aat the start of the iteration -
At the end of each iteration,
Ais shifted right by 3 bits, i.e., the highest non-zero bit ofAdetermines the number of iterations / outputs. -
If there are
noutputs, thek`th output (zero based) is fully determined by the bits `3 * k..3 * nofA. The last output depends on the three bits3 * (n - 1)..3 * nofA, the last but one on the six bits3 * (n - 2)..3 * n, etc. -
We can thus determine the three highest bits of
Ausing the last output, then the three next highest bits using the last but one output, etc. -
Because there is sometimes more than one bit triplet producing the desired output, we need to put candidates in a queue and return the first full match. Because a LIFO queue is used (i.e., depth first search), we need to push candidate values for
Ain decreasing order to find the smallest possibleA.
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
impl Computer {
pub fn run_to_output(&mut self) -> Option<usize> {
while self.ip < self.program.len() {
let instruction = self.program[self.ip];
self.op();
if instruction == 5 {
return self.outputs.last().copied();
}
}
None
}
}
pub fn star_2(&data: &&str) -> usize {
let mut computer = Computer::from(data);
let mut queue = Vec::from([(computer.program.len() - 1, 0)]);
while let Some((k, a)) = queue.pop() {
if k == usize::MAX {
return a;
}
let v = Some(computer.program[k] as usize);
let k_nxt = k.wrapping_add_signed(-1);
queue.extend(
(0..8)
.rev()
.map(|d| (a << 3) | d)
.filter(|&a_nxt| {
computer.ip = 0;
computer.registers[0] = a_nxt;
computer.run_to_output() == v
})
.map(|a| (k_nxt, a)),
);
}
panic!("No solution found!");
}
Day 18: RAM Run
Rust solution to AoC|2024|18.
Abstract: Find paths through a space that changes over time and determine conditions when there is no more path.
Input
My input has a method that constructs a Grid where the grid elements are the times when a byte falls into the grid position.
I was expecting to see a shortest path in a dynamically changing grid in part 2. It did not come.
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 {
use mr_kaffee_utils::grids::Grid;
#[derive(Debug)]
pub struct PuzzleData<'a>(&'a str);
impl<'a, T> From<&'a T> for PuzzleData<'a>
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
Self(s.as_ref())
}
}
impl PuzzleData<'_> {
pub fn grid(&self, width: usize, height: usize) -> (Grid<usize>, usize) {
self.0
.lines()
.map(|line| line.split(',').map(str::parse).map(Result::unwrap))
.map(|mut it| (it.next().unwrap(), it.next().unwrap()))
.enumerate()
.fold(
((usize::MAX, width, height).into(), 0),
|(mut grid, _), (t, pos)| {
let g = &mut grid[pos];
*g = (t + 1).min(*g);
(grid, t + 1)
},
)
}
}
}
Star 1
Simple shortest path in grid using BFS.
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 solve_1(grid: &Grid<usize>, t_snapshot: usize) -> Option<usize> {
let start = (0, 0);
let target = (grid.width() - 1, grid.height() - 1);
let mut visited: Grid<_> = (false, grid.width(), grid.height()).into();
visited[start] = true;
let mut queue = VecDeque::from([(0, start)]);
while let Some((t, (col, row))) = queue.pop_front() {
if (col, row) == target {
return Some(t);
}
for pos_nxt in [(1, 0), (0, -1), (-1, 0), (0, 1)]
.into_iter()
.map(|(d_col, d_row)| {
(
col.wrapping_add_signed(d_col),
row.wrapping_add_signed(d_row),
)
})
.filter(|&(col, row)| {
col < grid.width() && row < grid.height() && grid[(col, row)] > t_snapshot
})
{
let v = &mut visited[pos_nxt];
if !*v {
*v = true;
queue.push_back((t + 1, pos_nxt));
}
}
}
None
}
pub fn star_1(data: &PuzzleData) -> usize {
solve_1(&data.grid(71, 71).0, 1024).unwrap()
}
Star 2
Find the earliest time when the path is blocked using binary search. Then return the coordinates of the byte that was added at that time.
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 solve_2(grid: &Grid<usize>, t_max: usize) -> String {
// binary search
successors(Some((0, t_max)), |&(t_left, t_right)| {
let t_mid = (t_left + t_right) >> 1;
match solve_1(grid, t_mid) {
Some(_) => Some((t_mid, t_right)),
None => Some((t_left, t_mid)),
}
})
.find(|&(t_left, t_right)| t_right - t_left == 1)
.and_then(|(_, t_block)| {
grid.iter()
.position(|&t| t == t_block)
.map(|idx| grid.to_col_row(idx))
.map(|(col, row)| format!("{},{}", col, row))
})
.unwrap()
}
pub fn star_2(data: &PuzzleData) -> String {
let (grid, t_max) = data.grid(71, 71);
solve_2(&grid, t_max)
}
Day 19: Linen Layout
Rust solution to AoC|2024|19.
Abstract: Check whether (in how many ways) a pattern can be re-constructed by concatenating sub-patterns.
Input
Parse input into a list of towels (sub-patterns) and a string representing the list of patterns.
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 mod input {
#[derive(Debug)]
pub struct PuzzleData<'a> {
pub towels: Vec<&'a [u8]>,
pub patterns: &'a str,
}
impl<'a, T> From<&'a T> for PuzzleData<'a>
where
T: AsRef<str> + 'a + ?Sized,
{
fn from(s: &'a T) -> Self {
let (towels, patterns) = s
.as_ref()
.split_once("\n\n")
.map(|(towels, patterns)| {
(
towels.trim().split(", ").map(str::as_bytes).collect(),
patterns,
)
})
.unwrap();
Self { towels, patterns }
}
}
impl<'a> PuzzleData<'a> {
pub fn patterns(&self) -> impl Iterator<Item = &'a [u8]> {
self.patterns.trim().lines().map(str::as_bytes)
}
}
}
Star 1
Simple dynamic programming.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub fn is_possible<'a>(
pattern: &'a [u8],
towels: &'a [&'a [u8]],
cache: &mut HashMap<&'a [u8], bool>,
) -> bool {
if pattern.is_empty() {
return true;
} else if let Some(&possible) = cache.get(pattern) {
return possible;
}
let possible = towels.iter().any(|towel| {
pattern.starts_with(towel) && is_possible(&pattern[towel.len()..], towels, cache)
});
cache.insert(pattern, possible);
possible
}
pub fn star_1(data: &PuzzleData) -> usize {
let mut cache = HashMap::new();
data.patterns()
.filter(|pattern| is_possible(pattern, &data.towels, &mut cache))
.count()
}
Star 2
Extending the solution from part 1 to count options instead of checking existence of an option is straight forward. The structure of the solution is identical.
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
pub fn count_possible<'a>(
pattern: &'a [u8],
towels: &'a [&'a [u8]],
cache: &mut HashMap<&'a [u8], usize>,
) -> usize {
if pattern.is_empty() {
return 1;
} else if let Some(&count) = cache.get(pattern) {
return count;
}
let count = towels
.iter()
.filter(|towel| pattern.starts_with(towel))
.map(|towel| count_possible(&pattern[towel.len()..], towels, cache))
.sum();
cache.insert(pattern, count);
count
}
pub fn star_2(data: &PuzzleData) -> usize {
let mut cache = HashMap::new();
data.patterns()
.map(|pattern| count_possible(pattern, &data.towels, &mut cache))
.sum()
}
Day 20: Race Condition
Rust solution to AoC|2024|20.
Abstract: Determine how many cheats (shortcuts ignoring walls) of a given step size save a given number of steps or more on a way through a maze.
My main challenge today was to correctly parse all the details of the input.
Star 1
After I solved part 2, I removed my initial solution for part 1, which was essentially a special case.
The basic ingredient for the solution is to determine the cost from the start node to any reachable node in the grid. This is enough to compute cheat savings because there is only one unique path from the start to the end and the end position is the last position reachable from the start.
The solve function iterates over all positions and calls count_cheats to get the number of cheats for that position.
The count_cheats function iterates over all positions reachable from the start position within the given time and counts how many of them would lead to a saving of threshold or more.
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 fn get_costs(grid: &Grid) -> Grid<usize> {
successors(
grid.iter()
.position(|&c| c == b'S')
.map(|idx| ((usize::MAX, usize::MAX), grid.to_col_row(idx))),
|&(pos_prv, (c, r))| {
[(c + 1, r), (c, r - 1), (c - 1, r), (c, r + 1)]
.into_iter()
.find(|&pos_nxt| grid[pos_nxt] != b'#' && pos_nxt != pos_prv)
.map(|pos_nxt| ((c, r), pos_nxt))
},
)
.map(|(_, pos)| pos)
.enumerate()
.fold(
(usize::MAX, grid.width(), grid.height()).into(),
|mut costs, (cost, pos)| {
costs[pos] = cost;
costs
},
)
}
pub fn count_cheats(
costs: &Grid<usize>,
(col, row): (usize, usize),
cheat_time: usize,
threshold: usize,
) -> usize {
match costs[(col, row)] {
usize::MAX => 0,
cost_0 => {
let time = cheat_time as isize;
(-time..=time)
.map(|d_col| (d_col.abs(), col.wrapping_add_signed(d_col)))
.filter(|&(_, col)| col < costs.width())
.map(|(d_col, col)| {
(d_col - time..=time - d_col)
.map(|d_row| (d_row.abs(), row.wrapping_add_signed(d_row)))
.filter(|&(_, row)| row < costs.height())
.map(move |(d_row, row)| ((d_col + d_row) as usize, costs[(col, row)]))
.filter(|&(d, cost)| cost != usize::MAX && cost >= cost_0 + d + threshold)
.count()
})
.sum()
}
}
}
pub fn solve(grid: Grid, cheat_time: usize, threshold: usize) -> usize {
let costs = get_costs(&grid);
(0..costs.len())
.map(|idx| count_cheats(&costs, costs.to_col_row(idx), cheat_time, threshold))
.sum()
}
pub fn star_1(data: &&str) -> usize {
solve(data.make_grid(None), 2, 100)
}
Star 2
Same as part 1 with longer cheat time.
1
2
3
pub fn star_2(data: &&str) -> usize {
solve(data.make_grid(None), 20, 100)
}
Day 21: Keypad Conundrum
Rust solution to AoC|2024|21.
Abstract: Recursive operation of robots with keypads.
Star 1
The solution is a variation of the dynamic programming theme.
Essentially, on every level of directional keypads, the problem repeats itself. We repeatedly have to enter sequences of moves and always terminate on A. Hence, we also start every sequence on A.
As I do the calculations, I cache the results for those sequences. And then I just try all the feasible sequences and choose the shortest one (measured in button presses on the manually operated keypad).
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
const DIR_SYMBOLS: [u8; 5] = [b'>', b'^', b'<', b'v', b'A'];
const DIR_COORDS: [(isize, isize); 5] = [(2, 0), (1, 1), (0, 0), (1, 0), (2, 1)];
const DIR_FORBIDDEN: (isize, isize) = (0, 1);
const NUM_FORBIDDEN: (isize, isize) = (0, 0);
/// Convert number symbol to keypad coordinates
fn num_to_coord(num: u8) -> (isize, isize) {
match num {
b'A' => (2, 0),
b'0' => (1, 0),
b => {
let n = (b - b'0' - 1) as isize;
(n % 3, n / 3 + 1)
}
}
}
/// Calculate the minimum cost for a pattern, do not cache the result
///
/// This function can be called without constraints on the life time of pattern
/// If the life time of pattern is satisfies `'a`, prefer `cost_for_pattern`.
fn cost_for_pattern_no_cache<'a>(
pattern: &str,
level: usize,
paths: &'a [Vec<String>],
cache: &mut HashMap<(&'a str, usize), usize>,
) -> Result<usize, usize> {
if level == 0 {
Err(pattern.len())
} else if let Some(&v) = cache.get(&(pattern, level)) {
Err(v)
} else {
let idx = |b| DIR_SYMBOLS.iter().position(|&s| s == b).unwrap();
Ok(once(b'A')
.chain(pattern.bytes())
.map(idx)
.zip(pattern.bytes().map(idx))
.map(|(from, to)| cost_for_move(from, to, level, paths, cache))
.sum())
}
}
/// Calculate the minimum cost for a pattern.
///
/// Calls cost_for_move and cost_for_pattern recursively and caches results.
fn cost_for_pattern<'a>(
pattern: &'a str,
level: usize,
paths: &'a [Vec<String>],
cache: &mut HashMap<(&'a str, usize), usize>,
) -> usize {
cost_for_pattern_no_cache(pattern, level, paths, cache)
.map(|v| *cache.entry((pattern, level)).or_insert(v))
.unwrap_or_else(Into::into)
}
/// Calculate the minimum cost for a move.
///
/// Calls cost_for_pattern and cost_for_move recursively and caches results.
fn cost_for_move<'a>(
from_idx: usize,
to_idx: usize,
level: usize,
paths: &'a [Vec<String>],
cache: &mut HashMap<(&'a str, usize), usize>,
) -> usize {
match level {
0 => 1,
_ => paths[DIR_COORDS.len() * from_idx + to_idx]
.iter()
.map(|pattern| cost_for_pattern(pattern, level - 1, paths, cache))
.min()
.unwrap(),
}
}
/// An iterator that yields all possible paths between two positions (avoiding a forbidden direction)
/// on the directional keypad as `String`s.
pub struct PathVariants {
end: (isize, isize),
delta: (isize, isize),
forbidden: (isize, isize),
queue: Vec<(String, (isize, isize))>,
btn_horizontal: u8,
btn_vertical: u8,
}
impl PathVariants {
pub fn from(
(col_s, row_s): (isize, isize),
(col_e, row_e): (isize, isize),
forbidden: (isize, isize),
) -> Self {
let (d_col, d_row) = (col_e - col_s, row_e - row_s);
let btn_horizontal = match d_col > 0 {
true => b'>',
false => b'<',
};
let btn_vertical = match d_row > 0 {
true => b'^',
false => b'v',
};
let queue = Vec::from([(String::new(), (col_s, row_s))]);
Self {
end: (col_e, row_e),
delta: (d_col.signum(), d_row.signum()),
forbidden,
queue,
btn_horizontal,
btn_vertical,
}
}
}
impl Iterator for PathVariants {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
// loop until an item is found or the queue is exhausted
while let Some((mut p, (col, row))) = self.queue.pop() {
if (col, row) == self.end {
p.push('A');
return Some(p);
}
let horizontal = (col != self.end.0)
.then(|| (self.btn_horizontal, (col + self.delta.0, row)))
.filter(|&(_, pos)| pos != self.forbidden);
let vertical = (row != self.end.1)
.then(|| (self.btn_vertical, (col, row + self.delta.1)))
.filter(|&(_, pos)| pos != self.forbidden);
match (horizontal, vertical) {
(None, Some((b, (col, row)))) | (Some((b, (col, row))), None) => {
p.push(b as _);
self.queue.push((p, (col, row)));
}
(Some((b_h, (col_h, row_h))), Some((b_v, (col_v, row_v)))) => {
let mut p_h = p.clone();
p_h.push(b_h as _);
self.queue.push((p_h, (col_h, row_h)));
p.push(b_v as _);
self.queue.push((p, (col_v, row_v)));
}
_ => (),
}
}
None
}
}
/// Get all possible paths between any two positions on the directional keypad
fn get_paths() -> Vec<Vec<String>> {
DIR_COORDS.iter().copied().fold(Vec::new(), |paths, from| {
DIR_COORDS.iter().copied().fold(paths, |mut paths, to| {
paths.push(PathVariants::from(from, to, DIR_FORBIDDEN).collect());
paths
})
})
}
/// Calculate the length of the shortest sequence of button presses on the manually operated directional keypad.
///
/// Operates `levels` intermediate directional keypads and finally the numeric keypad.
///
/// Uses pre-calculated paths between all positions on the directional keypad (see `get_paths`) and a cache for
/// intermediate results.
fn shortest_code_length<'a>(
code: &'a str,
levels: usize,
paths: &'a [Vec<String>],
cache: &mut HashMap<(&'a str, usize), usize>,
) -> usize {
(once(b'A').chain(code.bytes()).map(num_to_coord))
.zip(code.bytes().map(num_to_coord))
.map(|(from, to)| {
PathVariants::from(from, to, NUM_FORBIDDEN)
.map(|p| {
cost_for_pattern_no_cache(&p, levels, paths, cache).unwrap_or_else(Into::into)
})
.min()
.unwrap()
})
.sum()
}
/// Solve the puzzle with the given number of intermediate directional keypads.
pub fn solve(data: &str, levels: usize) -> usize {
let paths = get_paths();
let mut cache = HashMap::new();
data.trim()
.lines()
.map(|code| {
shortest_code_length(code, levels, &paths, &mut cache)
* code
.bytes()
.take_while(u8::is_ascii_digit)
.fold(0, |value, b| 10 * value + (b - b'0') as usize)
})
.sum()
}
pub fn star_1(data: &&str) -> usize {
solve(data, 2)
}
Star 2
My solution for part 1 worked for part 2 immediately today. Just increase the number of keypads (levels). While part 1 is tractable without caching results, part 2 is not.
1
2
3
pub fn star_2(data: &&str) -> usize {
solve(data, 25)
}
Day 22: Monkey Market
Rust solution to AoC|2024|22.
Abstract: Simulate 'pseudo random numbers' and do not try to invert the random number generator.
A nice one today with a nice story of monkeys, a market and bananas.
Star 1
The first one is essentially to make sure the simulation is correct. I am pretty sure, there is no way to avoid 'brute force' simulation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pub fn update(mut secret: usize) -> usize {
secret = secret ^ (secret << 6) & 0xFFFFFF;
secret = secret ^ (secret >> 5);
secret ^ (secret << 11) & 0xFFFFFF
}
pub fn sequence(secret: usize) -> impl Iterator<Item = usize> {
successors(Some(secret), |&secret| Some(update(secret)))
}
pub fn star_1(data: &&str) -> usize {
data.trim()
.lines()
.map(str::parse)
.map(Result::unwrap)
.map(|secret| sequence(secret).nth(2000).unwrap())
.sum()
}
Star 2
The key to my solution of the second part is to store the bananas for every change sequence into a map during the simulation.
The change sequence is encoded in single integer, which allows cheap updates in every simulation step. To make sure, we used the first time a sequence occurs, we need to keep track of the seen sequences for every monkey.
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
const CHG_MAX: usize = 19;
const CHG_OFF: usize = CHG_MAX >> 1;
const CHS_MAX: usize = CHG_MAX.pow(4);
pub fn star_2(data: &&str) -> usize {
data.trim()
.lines()
.map(str::parse)
.map(Result::unwrap)
.fold(
(0, vec![0; CHS_MAX], vec![false; CHS_MAX]),
|(best, map, mut seen), secret| {
seen.fill(false);
sequence(secret)
.map(|secret| secret % 10)
.scan((0, 0), |(chg_id, prv), bananas| {
*chg_id = (*chg_id * CHG_MAX + bananas + CHG_OFF - *prv) % CHS_MAX;
*prv = bananas;
Some((*chg_id, *prv))
})
.take(2001)
.skip(4)
.fold(
(best, map, seen),
|(mut best, mut map, mut seen), (id, bananas)| {
let id_seen = &mut seen[id];
if !*id_seen {
*id_seen = true;
let sum_bananas = &mut map[id];
*sum_bananas += bananas;
best = best.max(*sum_bananas);
}
(best, map, seen)
},
)
},
)
.0
}
Day 23: LAN Party
Rust solution to AoC|2024|23.
Abstract: Find (maximal) cliques in a graph.
Learned a new algorithm: the Bron-Kerbosch algorithm
Star 1
I first got this wrong and tried to find groups of three, that are a connected sub-group of the overall map.
When I realized that it was about to find cliques of three (i.e., groups, where all group members have a link to both of the other two), it wasn’t all that complicated.
The only catch is to count groups correctly in which more than one member’s name starts with a 't'. This is done by incrementing the counter by 6 (the least common multiple of 1, 2 and 3) divided by the number of names starting with a 't', and in the end dividing the sum by 6 (single 't' contributes 1, double 't' contributes 1/2, and triple 't' contributes 1/3).
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 build_adjacent_lists(data: &str) -> HashMap<&str, Vec<&str>> {
data.trim()
.lines()
.filter_map(|line| line.split_once("-"))
.fold(HashMap::new(), |mut map, (a, b)| {
map.entry(a).or_default().push(b);
map.entry(b).or_default().push(a);
map
})
}
pub fn star_1(data: &&str) -> usize {
let adjacents = build_adjacent_lists(data);
adjacents
.iter()
.filter(|(a, _)| a.starts_with('t'))
.flat_map(|(_, adj_a)| {
adj_a[..adj_a.len() - 1]
.iter()
.enumerate()
.map(|(k, b)| (k, 1 + b.starts_with('t') as usize, &adjacents[b]))
.flat_map(|(k, v, adj_b)| {
adj_a[k + 1..]
.iter()
.filter(|c| adj_b.contains(c))
.map(move |&c| v + c.starts_with('t') as usize)
})
})
.fold(0, |cnt, v| cnt + 6 / v)
/ 6
}
Star 2
For the second star, my initial solution was wrong and I was lucky that it produced the right solution.
The correct solution is an implementation of the Bron-Kerbosch algorithm to find all maximal cliques in a graph and return the largest one.
The Bron-Kerbosch implementation is realized in a struct that implements the Iterator trait. The iterator yields all maximal cliques in the graph of size larger than two. The sets R, P, X are represented as Vec`s. The sets `P and X are stored in a single Vec with X at the front and P at the back.
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
type StackElT<K> = (Vec<K>, (usize, Vec<K>));
struct BronKerbosch<K> {
adjacents: HashMap<K, HashSet<K>>,
stack: Vec<StackElT<K>>,
}
impl<K: Eq + Hash + Copy, It: IntoIterator<Item = (K, K)>> From<It> for BronKerbosch<K> {
fn from(links: It) -> Self {
let adjacents =
links
.into_iter()
.fold(HashMap::<_, HashSet<_>>::new(), |mut map, (a, b)| {
map.entry(a).or_default().insert(b);
map.entry(b).or_default().insert(a);
map
});
let mut nodes = adjacents.keys().copied().collect::<Vec<_>>();
nodes.sort_unstable_by_key(|n| adjacents[n].len());
let stack = Vec::from([(Vec::new(), (0, nodes))]);
Self { adjacents, stack }
}
}
impl<K: Eq + Hash + Copy> Iterator for BronKerbosch<K> {
type Item = Vec<K>;
fn next(&mut self) -> Option<Self::Item> {
while let Some((r, (mut k, mut nodes))) = self.stack.pop() {
if nodes.is_empty() && r.len() > 2 {
// P and X are empty and relevant clique found
return Some(r);
} else if k == nodes.len() {
// P is empty
continue;
}
let pivot = nodes[nodes.len() - 1];
let pivot_adj = &self.adjacents[&pivot];
// iterate over all elements in P that are not adjacents of the pivot
let mut off = 0;
while let Some((idx, &node)) = nodes[k + off..]
.iter()
.enumerate()
.find(|&(_, node)| !pivot_adj.contains(node))
{
// get adjacents of the current element
let adj = &self.adjacents[&node];
// filter nodes to contain only adjacents of the current element
// update k to the number of filtered elements that had an index less than k
let (k_nxt, nodes_nxt) = nodes
.iter()
.enumerate()
.filter(|&(_, c)| adj.contains(c))
.fold((0, Vec::new()), |(k_nxt, mut computers), (idx, &c)| {
computers.push(c);
(if idx < k { k_nxt + 1 } else { k_nxt }, computers)
});
if r.len() + 1 + nodes_nxt.len() - k_nxt > 2 {
// add element to r and push to stack
let mut r = r.clone();
r.push(node);
self.stack.push((r, (k_nxt, nodes_nxt)));
}
// remove element from P and add to X
off += idx;
nodes[k..k + off + 1].rotate_right(1);
k += 1;
}
}
None
}
}
pub fn star_2(data: &&str) -> String {
let mut result = BronKerbosch::from(data.lines().filter_map(|line| line.split_once('-')))
.max_by_key(Vec::len)
.unwrap_or_default();
result.sort_unstable();
result.join(",")
}
Day 24: Crossed Wires
Rust solution to AoC|2024|24.
Abstract: Simulate and fix bit level manipulations that realize addition.
Input
Mainly uninteresting input parsing.
I decided to represent the operations in a map with wires as key and operations as values.
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
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Op {
And((Bit, Bit)),
Or((Bit, Bit)),
Xor((Bit, Bit)),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Bit {
X(u32),
Y(u32),
Z(u32),
Other([u8; 3]),
}
type MapT = HashMap<Bit, Op>;
type IMapT = HashMap<Op, Bit>;
impl Display for Bit {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Bit::X(v) => write!(f, "x{:02}", v),
Bit::Y(v) => write!(f, "y{:02}", v),
Bit::Z(v) => write!(f, "z{:02}", v),
Bit::Other([a, b, c]) => write!(f, "{}{}{}", *a as char, *b as char, *c as char),
}
}
}
impl From<&str> for Bit {
fn from(value: &str) -> Self {
match *value.as_bytes() {
[b'x', a, b] => Self::X((10 * (a - b'0') + b - b'0') as _),
[b'y', a, b] => Self::Y((10 * (a - b'0') + b - b'0') as _),
[b'z', a, b] => Self::Z((10 * (a - b'0') + b - b'0') as _),
[a, b, c] => Self::Other([a, b, c]),
_ => panic!("Unknown key: {}", value),
}
}
}
fn sort((a, b): (Bit, Bit)) -> (Bit, Bit) {
(a.min(b), a.max(b))
}
pub fn parse_data(data: &str) -> (MapT, HashMap<Bit, bool>) {
let (init, ops) = data.split_once("\n\n").unwrap();
(
ops.lines()
.map(|line| {
let mut words = line.split(' ').filter(|&w| w != "->");
(
words.next().unwrap().into(),
words.next().unwrap(),
words.next().unwrap().into(),
words.next().unwrap().into(),
)
})
.map(|(a, op, b, res)| match op {
"AND" => (res, Op::And(sort((a, b)))),
"OR" => (res, Op::Or(sort((a, b)))),
"XOR" => (res, Op::Xor(sort((a, b)))),
_ => panic!("Unknown op: {op}"),
})
.collect(),
init.lines()
.filter_map(|l| l.split_once(": ").map(|(k, v)| (k.into(), v == "1")))
.collect(),
)
}
Star 1
Straightforward implementation of the operations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
fn get_value(key: &Bit, values: &mut HashMap<Bit, bool>, ops: &MapT) -> bool {
if let Some(&value) = values.get(key) {
return value;
}
let value = match ops.get(key) {
Some(Op::And((a, b))) => get_value(a, values, ops) && get_value(b, values, ops),
Some(Op::Or((a, b))) => get_value(a, values, ops) || get_value(b, values, ops),
Some(Op::Xor((a, b))) => get_value(a, values, ops) ^ get_value(b, values, ops),
_ => panic!("Unknown key: {:?}", key),
};
values.insert(*key, value);
value
}
pub fn star_1(data: &&str) -> usize {
let (ops, mut values) = parse_data(data);
(0..)
.take_while(|&bit| ops.contains_key(&Bit::Z(bit)))
.map(|k| (k, get_value(&Bit::Z(k), &mut values, &ops) as usize))
.fold(0, |result, (k, bit)| result | bit << k)
}
Star 2
Since we know, what the network is supposed to do, we can explicitly search for places were it deviates to fix it.
For every bit (where bits with indices out of range are set to constant 0):
carry[k] = (x[k-1] & y[k-1]) | ((x[k-1] ^ y[k-1]) & carry[k-1]) z[k] = (x[k] ^ y[k]) ^ carry[k]
With this, the (quite generic) solution is:
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
fn swap_keys(map: &mut MapT, inv_map: &mut IMapT, k: (Bit, Bit)) -> bool {
fn swap<K: Eq + Hash, V: Copy>(map: &mut HashMap<K, V>, (a, b): (K, K)) -> Option<(V, V)> {
map.remove(&a)
.and_then(|v| map.insert(b, v).map(|w| (v, w)))
.and_then(|(v, w)| map.insert(a, w).map_or(Some((v, w)), |_| None))
}
swap(map, k).and_then(|v| swap(inv_map, v)) == Some(k)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Value {
Bit(Bit),
And(Box<Value>, Box<Value>),
Or(Box<Value>, Box<Value>),
Xor(Box<Value>, Box<Value>),
}
impl From<Bit> for Value {
fn from(bit: Bit) -> Self {
Self::Bit(bit)
}
}
impl Value {
fn and<A: Into<Value>, B: Into<Value>>(a: A, b: B) -> Self {
Self::And(a.into().into(), b.into().into())
}
fn or<A: Into<Value>, B: Into<Value>>(a: A, b: B) -> Self {
Self::Or(a.into().into(), b.into().into())
}
fn xor<A: Into<Value>, B: Into<Value>>(a: A, b: B) -> Self {
Self::Xor(a.into().into(), b.into().into())
}
fn to_bit(&self, map: &IMapT) -> Option<Bit> {
match self {
Self::Bit(bit) => Some(bit),
Self::And(a, b) => map.get(&Op::And(sort((a.to_bit(map)?, b.to_bit(map)?)))),
Self::Or(a, b) => map.get(&Op::Or(sort((a.to_bit(map)?, b.to_bit(map)?)))),
Self::Xor(a, b) => map.get(&Op::Xor(sort((a.to_bit(map)?, b.to_bit(map)?)))),
}
.copied()
}
}
pub fn find_err(bit: Bit, val: &Value, ops: &MapT, inv_ops: &IMapT) -> Option<(Bit, Option<Bit>)> {
let (t, v, w) = match val {
&Value::Bit(exp) => return (bit != exp).then_some((bit, Some(exp))),
Value::And(v, w) => (0, v, w),
Value::Or(v, w) => (1, v, w),
Value::Xor(v, w) => (2, v, w),
};
let (a, b) = match ops.get(&bit).copied() {
Some(Op::And((a, b))) if t == 0 => (a, b),
Some(Op::Or((a, b))) if t == 1 => (a, b),
Some(Op::Xor((a, b))) if t == 2 => (a, b),
_ => return Some((bit, val.to_bit(inv_ops))),
};
match match (find_err(a, v, ops, inv_ops), find_err(b, w, ops, inv_ops)) {
(Some(_), Some(_)) => (find_err(a, w, ops, inv_ops), find_err(b, v, ops, inv_ops)),
x => x,
} {
(err, None) | (None, err) => err,
_ => Some((bit, val.to_bit(inv_ops))),
}
}
pub fn star_2(data: &&str) -> String {
let (mut ops, values) = parse_data(data);
let mut inv_ops = ops.iter().map(|(&k, &v)| (v, k)).collect::<HashMap<_, _>>();
let n = (values.len() >> 1) as _;
let mut swaps = Vec::new();
let mut carry = None;
for b in 0..=n {
// (x[0] ^ y[0])
// (x[1] ^ y[1]) ^ ((x[0] & y[0])
// (x[k] ^ y[k]) ^ ((x[k-1] & y[k-1]) | ((x[k-1] ^ y[k-1]) & carry[k-1]))
let carry_upd = match carry {
None if b == 0 => None,
None => Some(Value::and(Bit::X(b - 1), Bit::Y(b - 1))), // X[0] & Y[0]
Some(carry) => Some(Value::or(
Value::and(Bit::X(b - 1), Bit::Y(b - 1)),
Value::and(Value::xor(Bit::X(b - 1), Bit::Y(b - 1)), carry),
)), // (X[k-1] & Y[k-1]) | ((X[k-1] ^ Y[k-1]) & carry)
};
let value = match &carry_upd {
None => Value::xor(Bit::X(b), Bit::Y(b)),
Some(carry_upd) if b == n => carry_upd.clone(),
Some(carry_upd) => Value::xor(Value::xor(Bit::X(b), Bit::Y(b)), carry_upd.clone()),
};
if let Some((a, b)) = find_err(Bit::Z(b), &value, &ops, &inv_ops) {
swap_keys(&mut ops, &mut inv_ops, (a, b.unwrap()));
swaps.push(a.to_string());
swaps.push(b.unwrap().to_string());
}
carry = carry_upd.and_then(|carry_upd| carry_upd.to_bit(&inv_ops));
}
swaps.sort_unstable();
swaps.join(",")
}
Day 25: Code Chronicle
Rust solution to AoC|2024|25.
Abstract: Check compatibility of key patterns with lock patterns.
Star 1
A simple one to finish…
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) -> usize {
data.split("\n\n")
.map(|schematic| schematic.as_bytes())
.map(|schematic| {
(
&schematic[0..5] == "#####".as_bytes(),
schematic[6..36]
.iter()
.filter(|&&c| c != b'\n')
.enumerate()
.filter(|&(_, &b)| b == b'#')
.fold([0u8; 5], |mut heights, (k, _)| {
heights[k % 5] += 1;
heights
}),
)
})
.fold(
(0, Vec::new(), Vec::new()),
|(count, mut locks, mut keys), (lock, heights)| {
let (this, other) = match lock {
true => (&mut locks, &keys),
false => (&mut keys, &locks),
};
this.push(heights);
(
count
+ other
.iter()
.filter(|item| item.iter().zip(heights.iter()).all(|(a, b)| a + b <= 5))
.count(),
locks,
keys,
)
},
)
.0
}
References to previous years
| 2024 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | 2021 | 2022 | 2023 |
|---|---|---|---|---|---|---|---|---|---|