Day 1: Secret Entrance
Rust solution to AoC|2025|1.
Warm-up puzzle for AoC 2025.
Star 1
Iterate over lines, update current position with wrapping, count how many times we end up at zero.
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
const INITIAL_POS: isize = 50;
const MAX_POS: isize = 100;
fn line_iter(data: &str) -> impl Iterator<Item = (isize, isize)> + '_ {
data.lines()
.map(|line| line.trim().as_bytes())
.filter(|line| !line.is_empty())
.map(|line| {
(
match line[0] {
b'R' => 1,
b'L' => -1,
_ => panic!("Unexpected direction"),
},
line[1..]
.iter()
.fold(0, |acc, b| acc * 10 + (b - b'0') as isize),
)
})
}
pub fn star_1(data: &&str) -> usize {
line_iter(data)
.scan(INITIAL_POS, |pos, (d, v)| {
*pos = (*pos + d * v).rem_euclid(MAX_POS);
Some(*pos)
})
.filter(|&pos| pos == 0)
.count()
}
Star 2
Same basic iteration, but do not only count how often we end up at zero, but also how often we pass it. This cannot be done with an iterator that just iterates over positions after each move.
Of course, this approach works for star 1 as well.
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 star<F>(data: &str, f: F) -> usize
where
F: Fn(isize, isize, isize, isize) -> usize,
{
line_iter(data)
.scan(INITIAL_POS, |pos, (d, v)| {
let prev_pos = *pos;
*pos = (prev_pos + d * v).rem_euclid(MAX_POS);
Some(f(prev_pos, *pos, d, v))
})
.sum()
}
pub fn star_1_alternative(data: &&str) -> usize {
star(data, |_, pos, _, _| if pos == 0 { 1 } else { 0 })
}
pub fn star_2(data: &&str) -> usize {
star(data, |prev_pos, pos, d, v| {
if prev_pos != 0 && (pos == 0 || ((pos - prev_pos) * d < 0)) {
(v / MAX_POS) as usize + 1
} else {
(v / MAX_POS) as _
}
})
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"L68
L30
R48
L5
R60
L55
L1
L99
R14
L82
"#;
const EXPECTED_STAR_1: usize = 3;
const EXPECTED_STAR_2: usize = 6;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
#[test]
pub fn test_star_1_alternative() {
assert_eq!(EXPECTED_STAR_1, star_1_alternative(&CONTENT.into()));
}
}
Day 2: Gift Shop
Rust solution to AoC|2025|2.
Identify numbers with repeating digit patterns.
There is surely smart ways to not check every number in the range. That might be for later…
Star 1
Only consider numbers that consist of a sequence of digits repeated once
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
pub fn test_value<G, I>(v: usize, group_sizes: G) -> bool
where
G: Fn(usize) -> I,
I: Iterator<Item = usize>,
{
group_sizes(
successors(Some(v), |v| Some(v / 10))
.take_while(|&v| v > 0)
.count(),
)
.any(|n| {
let m = usize::pow(10, n as _);
successors(Some(v / m), |w| Some(w / m))
.take_while(|&w| w > 0)
.all(|w| (v - w) % m == 0)
})
}
pub fn star<G, I>(data: &str, group_sizes: G) -> usize
where
G: Fn(usize) -> I,
I: Iterator<Item = usize>,
{
data.trim()
.split(',')
.filter_map(|range| {
range
.split_once('-')
.and_then(|(a, b)| Some(a.parse::<usize>().ok()?..=b.parse::<usize>().ok()?))
})
.map(|range| {
range
.filter(|&v| test_value(v, &group_sizes))
.sum::<usize>()
})
.sum::<usize>()
}
pub fn star_1(data: &&str) -> usize {
star(&data, |n| (n & 1 == 0).then_some(n >> 1).into_iter())
}
Star 2
Consider numbers that consist of digit patterns of any length repeated multiple times
1
2
3
4
5
pub fn star_2(data: &&str) -> usize {
star(data, |n_total| {
(1..=n_total >> 1).filter(move |n_group| n_total % n_group == 0)
})
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124
"#;
const EXPECTED_STAR_1: usize = 11 + 22 + 99 + 1010 + 1188511885 + 222222 + 446446 + 38593859;
const EXPECTED_STAR_2: usize = 11
+ 22
+ 99
+ 111
+ 999
+ 1010
+ 1188511885
+ 222222
+ 446446
+ 38593859
+ 565656
+ 824824824
+ 2121212121;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 3: Lobby
Rust solution to AoC|2025|3.
Make the biggest possible number out of given digits keeping their original order.
Star 1
Choose two digits. The solution is refactored to be generic in the number of digits.
Pitfall: the max function from the rust standard library yields the last element if there is more than one biggest element.
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 star(data: &str, n: usize) -> usize {
data.trim()
.lines()
.map(|line| line.as_bytes())
.map(|line| {
(0..n).rev().fold((0, line), |(value, line), rem| {
line[..line.len() - rem]
.iter()
.enumerate()
.fold(None, |mx, (pos, &b)| match mx {
None => Some((pos, b)),
Some((_, b_mx)) if b > b_mx => Some((pos, b)), // take first if multiple max
Some(m) => Some(m),
})
.map(|(pos, b)| (value * 10 + (b - b'0') as usize, &line[pos + 1..]))
.unwrap()
})
})
.map(|(v, _)| v)
.sum()
}
pub fn star_1(data: &&str) -> usize {
star(data, 2) as usize
}
Star 2
1
2
3
pub fn star_2(data: &&str) -> usize {
star(data, 12)
}
Tests
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#"987654321111111
811111111111119
234234234234278
818181911112111
"#;
const EXPECTED_STAR_1: usize = 98 + 89 + 78 + 92;
const EXPECTED_STAR_2: usize = 3_121_910_778_619;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 4: Printing Department
Rust solution to AoC|2025|4.
Input
Parse input into a grid of bytes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub mod input {
#[derive(Debug, Clone)]
pub struct PuzzleData(pub Vec<u8>, pub usize);
impl<T> From<&T> for PuzzleData
where
T: AsRef<str> + ?Sized,
{
fn from(s: &T) -> Self {
let data = s.as_ref().as_bytes();
let w = data.iter().position(|&b| b == b'\n').unwrap_or(data.len());
let grid = data.iter().copied().filter(|&b| b != b'\n').collect();
Self(grid, w)
}
}
}
Star 1
Count number of paper rolls with less than 4 adjacent rolls.
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 count_adjacent(grid: &[u8], w: usize, h: usize, pos: usize) -> usize {
let (col, row) = (pos % w, pos / w);
[
(1, 0),
(1, -1),
(0, -1),
(-1, -1),
(-1, 0),
(-1, 1),
(0, 1),
(1, 1),
]
.into_iter()
.map(|(dc, dr)| (col.wrapping_add_signed(dc), row.wrapping_add_signed(dr)))
.filter(|&(col, row)| col < w && row < h && grid[col + w * row] == b'@')
.count()
}
pub fn star_1(PuzzleData(grid, w): &PuzzleData) -> SolT1 {
let h = grid.len() / w;
grid.iter()
.enumerate()
.filter(|&(pos, &b)| b == b'@' && count_adjacent(grid, *w, h, pos) < 4)
.count()
}
Star 2
Repeatedly remove rolls with less than 4 adjacent rolls and count how many are removed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn star_2(data: &PuzzleData) -> SolT2 {
let PuzzleData(mut grid, w) = data.clone();
let h = grid.len() / w;
let mut count = 0;
while let Some((pos, _)) = grid
.iter()
.enumerate()
.find(|&(pos, &b)| b == b'@' && count_adjacent(&grid, w, h, pos) < 4)
{
grid[pos] = b'.';
count += 1;
}
count
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.
"#;
const EXPECTED_STAR_1: SolT1 = 13;
const EXPECTED_STAR_2: SolT2 = 43;
#[test]
pub fn test_from() {
let PuzzleData(grid, w) = PuzzleData::from(CONTENT);
assert_eq!(10, w);
assert_eq!(100, grid.len());
println!("{grid:?}");
}
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 5: Cafeteria
Rust solution to AoC|2025|5.
Check IDs in ranges
Input
Collect ranges in a vector, keep numbers as a &str.
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 mod input {
use std::ops::RangeInclusive;
#[derive(Debug, Clone)]
pub struct PuzzleData<'a>(pub Vec<RangeInclusive<usize>>, pub &'a str);
impl<'a, T> From<&'a T> for PuzzleData<'a>
where
T: AsRef<str> + ?Sized + 'a,
{
fn from(s: &'a T) -> Self {
let (ranges, ids) = s.as_ref().trim().split_once("\n\n").unwrap();
PuzzleData(
ranges
.lines()
.filter_map(|line| {
line.split_once('-')
.and_then(|(start, end)| Some(start.parse().ok()?..=end.parse().ok()?))
})
.collect(),
ids,
)
}
}
}
Star 1
Check for every ID if it is contained in any of the ranges.
1
2
3
4
5
6
7
pub fn star_1(PuzzleData(ranges, ids): &PuzzleData) -> usize {
ids.lines()
.map(str::parse)
.filter_map(Result::ok)
.filter(|id| ranges.iter().any(|range| range.contains(id)))
.count()
}
Star 2
Sort ranges to count total number of unique IDs in any of them in a single pass.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn star_2(PuzzleData(ranges, _): &PuzzleData) -> usize {
let mut ranges = ranges.clone();
ranges.sort_unstable_by_key(|range| (*range.start(), *range.end()));
ranges
.iter()
.fold((0, 0), |(n, end), r| {
if end <= *r.end() {
(n + r.end() - end.max(*r.start()) + 1, r.end() + 1)
} else {
(n, end)
}
})
.0
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"3-5
10-14
16-20
12-18
1
5
8
11
17
32
"#;
const EXPECTED_STAR_1: usize = 3;
const EXPECTED_STAR_2: usize = 14;
#[test]
pub fn test_from() {
let PuzzleData(ranges, numbers) = PuzzleData::from(CONTENT);
assert_eq!(ranges, vec![3..=5, 10..=14, 16..=20, 12..=18]);
assert!(numbers.starts_with("1\n"));
assert!(numbers.ends_with("\n32"));
}
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 6: Trash Compactor
Rust solution to AoC|2025|6.
Read numbers for a 2D grid horizontally and vertically
Star 1
The refactored solution can read numbers horizontally and vertically just by swapping the step sizes for numbers and digits respectively.
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
pub fn star(data: &str, vertical: bool) -> usize {
let data = data.trim_matches('\n').as_bytes();
let width = data.iter().position(|&b| b == b'\n').unwrap_or(data.len());
let ops_pos = ((data.len() + width) / (width + 1) - 1) * (width + 1);
let (n_step, d_step) = if vertical {
(1, width + 1)
} else {
(width + 1, 1)
};
data[ops_pos..]
.iter()
.copied()
.enumerate()
.filter(|&(_, b)| b == b'+' || b == b'*')
.map(|(pos, operation)| {
(pos..ops_pos)
.step_by(n_step)
.map(|pos| {
(pos..ops_pos)
.step_by(d_step)
.map(|pos| data[pos])
.skip_while(|&b| b == b' ')
.take_while(|b| b.is_ascii_digit())
.fold(None, |number, b| match number {
Some(number) => Some(10 * number + (b - b'0') as usize),
None => Some((b - b'0') as usize),
})
})
.take_while(Option::is_some)
.map(Option::unwrap)
.fold(
match operation {
b'+' => 0,
_ => 1,
},
|acc, n| match operation {
b'+' => acc + n,
_ => acc * n,
},
)
})
.sum()
}
pub fn star_1(data: &&str) -> usize {
star(data, false)
}
Star 2
Uses solution from star 1.
1
2
3
pub fn star_2(data: &&str) -> usize {
star(data, true)
}
Tests
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#"123 328 51 64
45 64 387 23
6 98 215 314
* + * +
"#;
const EXPECTED_STAR_1: usize = 33210 + 490 + 4243455 + 401;
const EXPECTED_STAR_2: usize = 1058 + 3253600 + 625 + 8544;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 7: Laboratories
Rust solution to AoC|2025|7.
Analyze how beam splits.
Star 1
Process 'manifold' line by line. Count how often beams hit splitter.
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: &&str) -> usize {
let data = data.as_bytes();
let width = data.iter().position(|&b| b == b'\n').unwrap_or(data.len());
data.iter()
.filter(|&&b| b != b'\n')
.enumerate()
.map(|(pos, &b)| (pos % width, b))
.fold(
(0, vec![false; width]),
|(mut count, mut current), (col, b)| {
if b == b'S' {
current[col] = true;
} else if b == b'^' && current[col] {
current[col] = false;
current[col - 1] = true;
current[col + 1] = true;
count += 1;
}
(count, current)
},
)
.0
}
Star 2
Dynamic programming approach: calculate timeline count recursively with cache.
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 fn star_2(data: &&str) -> usize {
fn count_timelines(
(data, width): (&[u8], usize),
pos: usize,
cache: &mut HashMap<usize, usize>,
) -> usize {
if pos >= data.len() {
return 1;
} else if let Some(&timelines) = cache.get(&pos) {
return timelines;
}
let timelines = if let Some(split_pos) = (pos + width + 1..data.len())
.step_by(width + 1)
.find(|&split_pos| data[split_pos] == b'^')
{
count_timelines((data, width), split_pos - 1, cache)
+ count_timelines((data, width), split_pos + 1, cache)
} else {
1
};
cache.insert(pos, timelines);
timelines
}
let data = data.as_bytes();
let width = data.iter().position(|&b| b == b'\n').unwrap_or(data.len());
count_timelines(
(data, width),
data.iter().position(|&b| b == b'S').unwrap(),
&mut HashMap::new(),
)
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#".......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
"#;
const EXPECTED_STAR_1: usize = 21;
const EXPECTED_STAR_2: usize = 40;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 8: Playground
Rust solution to AoC|2025|8.
Connect junction boxes to a huge circuit so that the required wire length increases for every connection made.
Input
Transform input to a vector of junction box 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
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<[usize; 3]>);
impl<T> From<&T> for PuzzleData
where
T: AsRef<str> + ?Sized,
{
fn from(s: &T) -> Self {
Self(
s.as_ref()
.lines()
.map(|line| {
line.split(',')
.map(str::parse)
.map(Result::unwrap)
.enumerate()
.take(3)
.fold([0; 3], |mut point, (pos, coord)| {
point[pos] = coord;
point
})
})
.collect(),
)
}
}
}
Star 1 & 2
The key ingredient is the make_circuits function which calculates all the pairwise distance squares into a sorted vector and then process them one by one to compile the circuits.
The circuits are calculated using folding an iterator over the distances. The fold ends (is shortcutted) once all junction boxes are in a single circuit using my short-cuttable fold utility.
It returns a list of the connected circuits (for star 1) and the last pair processed (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
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
pub fn make_circuits(points: &[[usize; 3]], n: usize) -> (Vec<Vec<usize>>, (usize, usize)) {
// calculate all pair-wise distance squares into a sorted vector
let mut distances = points
.iter()
.enumerate()
.flat_map(|(id_a, point_a)| {
points[id_a + 1..]
.iter()
.enumerate()
.map(move |(k, point_b)| (id_a + 1 + k, point_b))
.map(move |(id_b, point_b)| {
(
point_a
.iter()
.zip(point_b)
.map(|(a, b)| (a.max(b) - a.min(b)).pow(2))
.sum::<usize>(),
id_a,
id_b,
)
})
})
.collect::<Vec<_>>();
distances.sort_unstable();
// process all distances to compile circuits
let (_, mut circuit_members, last_pair) = distances[0..n.min(distances.len())]
.iter()
.fold_short_cuttable(
(vec![None; points.len()], Vec::new(), None),
|(mut circuits, mut circuit_members, _), &(_, id_a, id_b)| {
let len = match (circuits[id_a], circuits[id_b], id_a, id_b) {
(None, None, _, _) => {
// new circuit
circuits[id_a] = Some(circuit_members.len());
circuits[id_b] = Some(circuit_members.len());
circuit_members.push(vec![id_a, id_b]);
2
}
(Some(circuit), None, _, id) | (None, Some(circuit), id, _) => {
// add one to circuit of other
circuits[id] = Some(circuit);
circuit_members[circuit].push(id);
circuit_members[circuit].len()
}
(Some(circuit_a), Some(circuit_b), _, _) if circuit_a != circuit_b => {
// merge circuits
let (circuit_1, circuit_2) =
(circuit_a.min(circuit_b), circuit_a.max(circuit_b));
let (members_1, members_2) = circuit_members.split_at_mut(circuit_2);
let (members_1, members_2) = (&mut members_1[circuit_1], &mut members_2[0]);
for id in members_2.drain(0..) {
circuits[id] = Some(circuit_1);
members_1.push(id);
}
members_1.len()
}
(Some(circuit), _, _, _) => circuit_members[circuit].len(), // already in same circuit
};
// short-cut fold if circuit contains all junction boxes
ok_if(
(circuits, circuit_members, Some((id_a, id_b))),
len < points.len(),
)
},
);
// sort circuit members by size descending, truncate to non-empty circuits
circuit_members.sort_unstable_by_key(|members| Reverse(members.len()));
let first_empty = circuit_members
.iter()
.position(Vec::is_empty)
.unwrap_or(circuit_members.len());
circuit_members.truncate(first_empty);
// return circuit members and last pair added
(circuit_members, last_pair.unwrap_or_default())
}
pub fn star_1(PuzzleData(points): &PuzzleData, n: usize) -> usize {
// product of three largest circuit sizes after adding n links
make_circuits(points, n)
.0
.iter()
.take(3)
.map(|members| members.len())
.product()
}
pub fn star_2(PuzzleData(points): &PuzzleData) -> usize {
// multiply x-coordinates of last pair added
let (_, (id_a, id_b)) = make_circuits(points, usize::MAX);
points[id_a][0] * points[id_b][0]
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
"#;
const EXPECTED_POINTS_LEN: usize = 20;
const TEST_POINT_ID: usize = 17;
const EXPECTED_TEST_POINT: [usize; 3] = [862, 61, 35];
#[test]
pub fn test_from() {
let PuzzleData(points) = PuzzleData::from(CONTENT);
assert_eq!(EXPECTED_POINTS_LEN, points.len());
assert_eq!(EXPECTED_TEST_POINT, points[TEST_POINT_ID]);
println!("{points:?}");
}
const TEST_PARAM_N: usize = 10;
const EXPECTED_STAR_1: usize = 40;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into(), TEST_PARAM_N));
}
const EXPECTED_STAR_2: usize = 25_272;
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 9: Movie Theater
Rust solution to AoC|2025|9.
Fit rectangle into a polygon.
Input
Parse points to vector of 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
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<[usize; 2]>);
impl<T> From<&T> for PuzzleData
where
T: AsRef<str> + ?Sized,
{
fn from(s: &T) -> Self {
Self(
s.as_ref()
.lines()
.map(|line| {
line.split(',')
.map(str::parse)
.map(Result::unwrap)
.take(2)
.enumerate()
.fold([0, 0], |mut point, (pos, coord)| {
point[pos] = coord;
point
})
})
.collect(),
)
}
}
}
Star 1
Star 1 reminded me a lot of yesterday’s puzzle.
1
2
3
4
5
6
7
8
9
10
11
pub fn star_1(PuzzleData(data): &PuzzleData) -> usize {
data.iter()
.enumerate()
.flat_map(|(pos, a)| {
data[pos + 1..].iter().map(|b| {
(a[0].max(b[0]) - a[0].min(b[0]) + 1) * (a[1].max(b[1]) - a[1].min(b[1]) + 1)
})
})
.max()
.unwrap_or_default()
}
Star 2
I quickly came up with the idea to use the Ray casting algorithm to calculate the points inside the polygon and find the largest rectangle that fits completely inside.
It took a while to figure out how to calculate the crossings correctly.
To achieve acceptable computation time, I compressed coordinates by mapping them to indices of sorted, unique x and y values respectively.
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
pub fn star_2(PuzzleData(data): &PuzzleData) -> usize {
// determine bounding box
let (x_min, y_min, x_max, y_max) = data.iter().fold(
(usize::MAX, usize::MAX, 0, 0),
|(x_min, y_min, x_max, y_max), point| {
(
x_min.min(point[0]),
y_min.min(point[1]),
x_max.max(point[0]),
y_max.max(point[1]),
)
},
);
// determine unique x and y coordinates for a compressed grid
let mut unique_xs = data.iter().map(|p| p[0]).collect::<Vec<_>>();
unique_xs.sort_unstable();
unique_xs.dedup();
let mut unique_ys = data.iter().map(|p| p[1]).collect::<Vec<_>>();
unique_ys.sort_unstable();
unique_ys.dedup();
let (w, h) = (unique_xs.len(), unique_ys.len());
// map original coordinates to compressed grid coordinates
let (x_ids, _) = (x_min..=x_max).fold(
(Vec::with_capacity(x_max - x_min + 1), 0),
|(mut ids, mut current), x| {
current += unique_xs[current..]
.iter()
.position(|&unique_x| unique_x >= x)
.unwrap();
ids.push(current);
(ids, current)
},
);
let (y_ids, _) = (y_min..=y_max).fold(
(Vec::with_capacity(y_max - y_min + 1), 0),
|(mut ids, mut current), y| {
current += unique_ys[current..]
.iter()
.position(|&unique_y| unique_y >= y)
.unwrap();
ids.push(current);
(ids, current)
},
);
// calculate compressed grid
// first initialize grid to 1 on the boundary
// then set interior of polygon to 2 with nested fold
let grid = (0..h).fold(
data.iter()
.zip(data.iter().cycle().skip(1))
.map(|(&[x1, y1], &[x2, y2])| (x1.min(x2), x1.max(x2), y1.min(y2), y1.max(y2)))
.fold(vec![0u8; w * h], |grid, (x_a, x_b, y_a, y_b)| {
(x_ids[x_a - x_min] + y_ids[y_a - y_min] * w
..=x_ids[x_b - x_min] + y_ids[y_b - y_min] * w)
.step_by(if x_a == x_b { w } else { 1 })
.fold(grid, |mut grid, pos| {
grid[pos] = 1;
grid
})
}),
|grid, y| {
(0..w)
.fold((grid, 0, 0), |(mut grid, current, mut crossings), x| {
if grid[x + y * w] > 0 {
(grid, current + 1, crossings)
} else {
if current == 1
|| current > 1
&& y > 0
&& y < h - 1
&& (grid[x - current + (y - 1) * w] != grid[x - 1 + (y - 1) * w]
|| grid[x - current + (y + 1) * w] != grid[x - 1 + (y + 1) * w])
{
// we crossed a polygon edge
// if current > 1 we are on an horizontal edge and need to check above or below the edge
crossings += 1;
}
if crossings % 2 == 1 {
// we are inside the polygon
grid[x + y * w] = 2;
}
(grid, 0, crossings)
}
})
.0
},
);
// calculate areas and sort descending
let mut areas = data
.iter()
.enumerate()
.flat_map(|(pos, &[x1, y1])| {
data[pos + 1..]
.iter()
.map(move |&[x2, y2]| (x1.min(x2), x1.max(x2), y1.min(y2), y1.max(y2)))
})
.map(|(x_a, x_b, y_a, y_b)| ((x_b - x_a + 1) * (y_b - y_a + 1), (x_a, x_b, y_a, y_b)))
.collect::<Vec<_>>();
areas.sort_unstable_by_key(|(area, _)| Reverse(*area));
// find the largest area that is completely inside the polygon
areas
.into_iter()
.find(|(_, (x_a, x_b, y_a, y_b))| {
(x_ids[x_a - x_min]..=x_ids[x_b - x_min])
.all(|x| (y_ids[y_a - y_min]..=y_ids[y_b - y_min]).all(|y| grid[x + y * w] > 0))
})
.map(|(area, _)| area)
.unwrap_or_default()
}
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#"7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3
"#;
const EXPECTED_LEN: usize = 8;
const TEST_POINT_IDX: usize = 5;
const EXPECTED_TEST_POINT: [usize; 2] = [2, 5];
#[test]
pub fn test_from() {
let PuzzleData(data) = PuzzleData::from(CONTENT);
assert_eq!(EXPECTED_LEN, data.len());
assert_eq!(EXPECTED_TEST_POINT, data[TEST_POINT_IDX]);
println!("{data:?}");
}
const EXPECTED_STAR_1: usize = 50;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
const EXPECTED_STAR_2: usize = 24;
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT.into()));
}
}
Day 10: Factory
Rust solution to AoC|2025|10.
Input
Parse each machine to leds, mask and buttons all represented as bits of usize integers and list of joltages.
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
pub mod input {
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Machine {
pub leds: usize,
pub mask: usize,
pub buttons: Vec<usize>,
pub joltages: Vec<usize>,
}
#[derive(Debug)]
pub struct PuzzleData(pub Vec<Machine>);
impl From<&str> for Machine {
fn from(s: &str) -> Self {
let mut it = s.split_ascii_whitespace();
let (leds, mask) = it
.next()
.unwrap()
.trim_matches(['[', ']'])
.bytes()
.enumerate()
.fold((0, 0), |(leds, mask), (pos, b)| {
(
leds | if b == b'#' { 1 << pos } else { 0 },
mask | (1 << pos),
)
});
let (buttons, joltages) =
it.fold((vec![], Vec::default()), |(mut buttons, joltages), part| {
if part.starts_with('(') {
buttons.push(
part.trim_matches(['(', ')'])
.split(',')
.map(str::parse)
.map(Result::unwrap)
.fold(0usize, |buttons, button: i32| buttons | (1 << button)),
);
(buttons, joltages)
} else if part.starts_with('{') {
(
buttons,
part.trim_matches(['{', '}'])
.split(',')
.map(str::parse)
.map(Result::unwrap)
.collect(),
)
} else {
panic!("Unexpected part: {}", part);
}
});
Self {
leds,
mask,
buttons,
joltages,
}
}
}
impl<T> From<&T> for PuzzleData
where
T: AsRef<str> + ?Sized,
{
fn from(s: &T) -> Self {
Self(s.as_ref().lines().map(Machine::from).collect())
}
}
}
Star 1
Straight-forward shortest path using breadth first search.
With the bit-representation the state is a simple usize integer and adjacents are calculated using XOR (^).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn shortest_button_path(machine: &Machine) -> usize {
let mut seen = vec![false; machine.mask + 1];
let mut queue = VecDeque::from([(0, 0)]);
seen[0] = true;
while let Some((steps, leds)) = queue.pop_front() {
if leds == machine.leds {
return steps;
}
for leds in machine.buttons.iter().map(|&button| leds ^ button) {
if !seen[leds] {
seen[leds] = true;
queue.push_back((steps + 1, leds));
}
}
}
unreachable!("No solution found")
}
pub fn star_1(PuzzleData(machines): &PuzzleData) -> usize {
machines.iter().map(shortest_button_path).sum()
}
Star 2
I am very unhappy with my solution. I was attempting dynamic programming and graph traversal approaches that all worked for the example but never finished for the real data. I guess there is ways to prune solution space enough to make these approaches work.
My current solution directly solves the set of linear equations using Gaussian elimination. It did not make the code robust to deal with problems that are not well formed (do not have a non-negative integer solution or no solution at all). If there are free variables, I scan all possible solutions and return the minimum cost that produces a non-negative integer 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
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
fn buttons_iter(buttons: usize) -> impl Iterator<Item = usize> {
successors(Some(buttons), |button| Some(button >> 1)).map(|b| b & 1)
}
const TOLERANCE: f64 = 1e-9;
pub fn solve_joltages(machine: &Machine) -> usize {
let num_vars = machine.buttons.len();
let width = num_vars + 1;
let height = machine.joltages.len();
// compile extended matrix for system of linear equations
let mut mat = vec![0.0; width * height];
// ... coefficients
for (col, &button) in machine.buttons.iter().enumerate() {
for (row, b) in buttons_iter(button)
.take(machine.joltages.len())
.enumerate()
{
mat[col + row * width] = b as f64;
}
}
// ... constants
for (row, &joltage) in machine.joltages.iter().enumerate() {
mat[num_vars + row * width] = joltage as f64;
}
// Gaussian elimination to row echelon form (see https://en.wikipedia.org/wiki/Gaussian_elimination)
let mut pivot_row = 0;
let mut pivot_col = 0;
while pivot_row < height && pivot_col < width {
let (max_row, max_val) = (pivot_row..height)
.map(|row| (row, mat[pivot_col + row * width].abs()))
.max_by(|(r1, v1), (r2, v2)| {
v1.partial_cmp(v2)
.unwrap_or(Ordering::Equal)
.then(r1.cmp(r2))
})
.unwrap();
if max_val == 0.0 {
pivot_col += 1;
continue;
}
if max_row != pivot_row {
for col in pivot_col..width {
mat.swap(col + pivot_row * width, col + max_row * width);
}
}
let pivot_val = mat[pivot_col + pivot_row * width];
for col in pivot_col..width {
mat[col + pivot_row * width] /= pivot_val;
}
for row in pivot_row + 1..height {
let fac = mat[pivot_col + row * width];
for col in pivot_col..width {
mat[col + row * width] -= fac * mat[col + pivot_row * width];
}
}
pivot_row += 1;
pivot_col += 1;
}
// continue to reduced row echelon form
for row_outer in (0..height).rev() {
if let Some(pivot_col) = mat[row_outer * width..(row_outer + 1) * width - 1]
.iter()
.position(|&v| (v - 1.0).abs() < TOLERANCE)
{
for row_inner in (0..row_outer).rev() {
let fac = mat[pivot_col + row_inner * width];
for col in pivot_col..width {
mat[col + row_inner * width] -= fac * mat[col + row_outer * width];
}
}
}
}
// determine pivot variables and free variables
let pivot_vars = (0..height * width)
.map(|idx| (idx % width, idx / width))
.filter(|&(col, _)| col < num_vars)
.filter(|&(col, row)| (mat[col + row * width] - 1.0).abs() < TOLERANCE)
.filter(|&(col, row)| {
(0..height)
.filter(|&row_other| row_other != row)
.all(|row_other| mat[col + row_other * width].abs() < TOLERANCE)
})
.collect::<Vec<_>>();
let free_vars = (0..num_vars)
.filter(|col| pivot_vars.iter().all(|(c, _)| c != col))
.collect::<Vec<_>>();
// determine max steps for all free variables
let max_steps = free_vars
.iter()
.map(|&col| {
buttons_iter(machine.buttons[col])
.zip(machine.joltages.iter())
.filter(|&(button, _)| button > 0)
.map(|(_, &joltage)| joltage)
.min()
.unwrap_or(0)
+ 1
})
.collect::<Vec<_>>();
// iterator over free variables from index
let f_free_vars = |free_vars_idx| {
max_steps.iter().scan(free_vars_idx, |idx, &steps| {
let val = *idx % steps;
*idx /= steps;
Some(val)
})
};
// steps for pivot variable in given row with free variables from index
let f_steps = |free_vars_idx, row| {
mat[num_vars + row * width]
- free_vars
.iter()
.zip(f_free_vars(free_vars_idx))
.map(|(&col, val)| mat[col + row * width] * val as f64)
.sum::<f64>()
};
// calculate minimum cost over all valid choices of free variables
// a choice is valid if it leads to a non-negative integer solution
(0..max_steps.iter().product::<usize>())
.filter_map(|idx| {
pivot_vars
.iter()
.map(|&(_, row)| f_steps(idx, row))
.map(|steps| {
((steps - steps.round()).abs() < TOLERANCE && steps > -TOLERANCE)
.then_some(steps.round() as usize)
})
.fold_short_cuttable(Some(f_free_vars(idx).sum()), |cost, steps| {
ok_if(
cost.and_then(|cost| steps.map(|v| cost + v)),
steps.is_some(),
)
})
})
.min()
.unwrap()
}
pub fn star_2(PuzzleData(machines): &PuzzleData) -> usize {
machines.iter().map(solve_joltages).sum()
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
"#;
const EXPECTED_MACHINES_LEN: usize = 3;
const TEST_MACHINE_IDX: usize = 1;
fn expected_test_machine() -> Machine {
Machine {
leds: 0b01000,
mask: 0b11111,
buttons: vec![0b11101, 0b01100, 0b10001, 0b00111, 0b11110],
joltages: vec![7, 5, 12, 7, 2],
}
}
#[test]
pub fn test_from() {
let PuzzleData(machines) = PuzzleData::from(CONTENT);
assert_eq!(EXPECTED_MACHINES_LEN, machines.len());
assert_eq!(&expected_test_machine(), &machines[TEST_MACHINE_IDX]);
println!("{machines:?}");
}
const EXPECTED_SHORTEST_BUTTON_PATHS: [usize; 3] = [2, 3, 2];
#[test]
pub fn test_shortest_button_path() {
let PuzzleData(machines) = PuzzleData::from(CONTENT);
for (expected_shortest_path, machine) in
EXPECTED_SHORTEST_BUTTON_PATHS.into_iter().zip(machines)
{
println!("Testing machine: {:?}", machine);
assert_eq!(expected_shortest_path, shortest_button_path(&machine));
}
}
#[test]
pub fn test_star_1() {
assert_eq!(
EXPECTED_SHORTEST_BUTTON_PATHS.into_iter().sum::<usize>(),
star_1(&CONTENT.into())
);
}
#[test]
pub fn test_buttons_iter() {
let buttons: usize = 0b10110;
let expected: Vec<usize> = vec![0, 1, 1, 0, 1];
let result: Vec<usize> = buttons_iter(buttons).take(5).collect();
assert_eq!(expected, result);
}
const EXPECTED_JOLTAGE_SOLUTIONS: [usize; 3] = [10, 12, 11];
#[test]
pub fn test_solve_joltages() {
let PuzzleData(machines) = PuzzleData::from(CONTENT);
for (expected_solution, machine) in EXPECTED_JOLTAGE_SOLUTIONS.into_iter().zip(machines) {
println!("Testing machine: {:?}", machine);
assert_eq!(expected_solution, solve_joltages(&machine));
}
}
#[test]
pub fn test_star_2() {
assert_eq!(
EXPECTED_JOLTAGE_SOLUTIONS.into_iter().sum::<usize>(),
star_2(&CONTENT.into())
);
}
}
Day 11: Reactor
Rust solution to AoC|2025|11.
Count paths from sources to targets
Input
Compile an adjacency map.
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 mod input {
use std::collections::HashMap;
#[derive(Debug)]
pub struct PuzzleData<'a>(pub HashMap<&'a str, Vec<&'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()
.trim()
.lines()
.map(|line| {
line.split_once(": ")
.map(|(key, values)| (key, values.split_ascii_whitespace().collect()))
})
.map(Option::unwrap)
.collect(),
)
}
}
}
Star 1
Dynamic programming (DFS with cache) approach recursively finds all paths.
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 star_1(PuzzleData(map): &PuzzleData) -> SolT1 {
const SOURCE: &str = "you";
const TARGET: &str = "out";
fn count_paths<'a>(
map: &'a HashMap<&'a str, Vec<&'a str>>,
source: &'a str,
cache: &mut HashMap<&'a str, usize>,
) -> usize {
if source == TARGET {
return 1;
} else if let Some(&paths) = cache.get(source) {
return paths;
}
let paths = map
.get(source)
.map(|successors| {
successors
.iter()
.map(|&successor| count_paths(map, successor, cache))
.sum()
})
.unwrap_or(0);
cache.insert(source, paths);
paths
}
count_paths(&map, SOURCE, &mut HashMap::new())
}
Star 2
That was a surprisingly simple extension of part 1: just add the information whether the fft and dac nodes have been seen to the source node in my recursive function.
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_2(PuzzleData(map): &PuzzleData) -> SolT2 {
const SOURCE: &str = "svr";
const TARGET: &str = "out";
const FFT: &str = "fft";
const DAC: &str = "dac";
const FFT_BIT: u8 = 1;
const DAC_BIT: u8 = 2;
fn count_paths<'a>(
map: &HashMap<&'a str, Vec<&'a str>>,
source: (&'a str, u8),
cache: &mut HashMap<(&'a str, u8), usize>,
) -> usize {
if source == (TARGET, FFT_BIT | DAC_BIT) {
return 1;
} else if let Some(&paths) = cache.get(&source) {
return paths;
}
let paths = map
.get(source.0)
.map(|successors| {
successors
.iter()
.map(|&successor| match successor {
FFT => (successor, source.1 | FFT_BIT),
DAC => (successor, source.1 | DAC_BIT),
_ => (successor, source.1),
})
.map(|successor| count_paths(map, successor, cache))
.sum()
})
.unwrap_or(0);
cache.insert(source, paths);
paths
}
count_paths(&map, (SOURCE, 0), &mut HashMap::new())
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT_1: &str = r#"aaa: you hhh
you: bbb ccc
bbb: ddd eee
ccc: ddd eee fff
ddd: ggg
eee: out
fff: out
ggg: out
hhh: ccc fff iii
iii: out
"#;
#[test]
pub fn test_from() {
let PuzzleData(map) = PuzzleData::from(CONTENT_1);
assert_eq!(Some(&vec!["bbb", "ccc"]), map.get("you"));
println!("{map:?}");
}
const EXPECTED_STAR_1: usize = 5;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT_1.into()));
}
const CONTENT_2: &str = r#"svr: aaa bbb
aaa: fft
fft: ccc
bbb: tty
tty: ccc
ccc: ddd eee
ddd: hub
hub: fff
eee: dac
dac: fff
fff: ggg hhh
ggg: out
hhh: out
"#;
const EXPECTED_STAR_2: usize = 2;
#[test]
pub fn test_star_2() {
assert_eq!(EXPECTED_STAR_2, star_2(&CONTENT_2.into()));
}
}
Day 12: TODO
Rust solution to AoC|2025|12.
Hmm. I don’t know if I like today’s problem.
It asks whether jigsaw puzzles are solvable. It turns out that in the real data, the puzzles are solvable if and only if the area of the pieces is less than or equal to the available area.
Maybe the challenge was exactly to realize that it is intractable to invalidate feasibility of a puzzle by trying all positions of the pieces. At least my code was able to solve all the puzzles that were actually solvable…
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
60
61
62
63
64
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub pieces: Vec<(usize, Vec<u8>)>,
pub regions: Vec<((usize, usize), Vec<usize>)>,
}
impl<T> From<&T> for PuzzleData
where
T: AsRef<str> + ?Sized,
{
fn from(s: &T) -> Self {
let parts = s.as_ref().split("\n\n").collect::<Vec<_>>();
let shapes = parts
.iter()
.take(parts.len() - 1)
.map(|shape| {
let first_break = shape
.bytes()
.position(|b| b == b'\n')
.unwrap_or(shape.as_bytes().len());
let width = shape
.bytes()
.skip(first_break + 1)
.position(|b| b == b'\n')
.unwrap_or(shape.len() - first_break - 1);
(
width,
shape
.bytes()
.skip(first_break + 1)
.filter(|&b| b != b'\n')
.collect::<Vec<u8>>(),
)
})
.inspect(|(width, shape)| assert_eq!(width * width, shape.len()))
.collect();
let regions = parts[parts.len() - 1]
.lines()
.map(|region| {
region
.split_once(": ")
.and_then(|(dimensions, indices)| {
Some((
dimensions
.split_once('x')
.and_then(|(w, h)| Some((w.parse().ok()?, h.parse().ok()?)))?,
indices
.split_ascii_whitespace()
.map(str::parse)
.collect::<Result<_, _>>()
.ok()?,
))
})
.unwrap()
})
.collect();
Self {
pieces: shapes,
regions,
}
}
}
}
Star 1
In the end, just compare sizes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#[cfg(not(feature = "solve"))]
pub fn star_1(
PuzzleData {
pieces: shapes,
regions,
}: &PuzzleData,
) -> usize {
let sizes = shapes
.iter()
.map(|(_, data)| data.iter().filter(|&&b| b == b'#').count())
.collect::<Vec<_>>();
regions
.iter()
.filter(|&((width, height), counts)| {
counts
.iter()
.zip(sizes.iter())
.map(|(&c, &s)| c * s)
.sum::<usize>()
<= width * height
})
.count()
}
Puzzle Solver
The puzzle solver is still there for reference. Don’t try to use it to figure out that a puzzle is not feasible…
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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
#[cfg(feature = "solve")]
pub fn star_1(data: &PuzzleData) -> usize {
solver::star_1(data)
}
#[cfg(feature = "solve")]
pub mod solver {
use std::{
collections::HashMap,
iter::once,
ops::{Index, IndexMut},
};
use crate::input::PuzzleData;
#[derive(PartialEq, Eq, Debug)]
pub struct Trafo(u8);
impl From<u8> for Trafo {
fn from(value: u8) -> Self {
Self(value & 0b111)
}
}
impl Trafo {
pub fn is_even(&self) -> bool {
self.0 & 0b001 == 0
}
pub fn contains_flip(&self) -> bool {
self.0 & 0b100 == 0b100
}
pub fn invert(&self) -> Self {
if self.contains_flip() {
Self(self.0)
} else {
Self((0b100 - self.0) & 0b11)
}
}
pub fn transform(&self, (w, h): (usize, usize), (c, r): (usize, usize)) -> (usize, usize) {
match self.0 {
0 => (c, r),
1 => (h - 1 - r, c),
2 => (w - 1 - c, h - 1 - r),
3 => (r, w - 1 - c),
4 => (w - 1 - c, r),
5 => (r, c),
6 => (c, h - 1 - r),
7 => (h - 1 - r, w - 1 - c),
_ => unreachable!(),
}
}
}
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Clone)]
pub struct Grid<T> {
pub width: usize,
pub data: Vec<T>,
}
impl<T> From<(usize, Vec<T>)> for Grid<T> {
fn from((width, data): (usize, Vec<T>)) -> Self {
assert_eq!(0, data.len() % width, "Incomplete last row");
Self { width, data }
}
}
impl<T> Index<(usize, usize)> for Grid<T> {
type Output = T;
fn index(&self, (col, row): (usize, usize)) -> &Self::Output {
&self.data[col + row * self.width]
}
}
impl<T> IndexMut<(usize, usize)> for Grid<T> {
fn index_mut(&mut self, (col, row): (usize, usize)) -> &mut Self::Output {
&mut self.data[col + row * self.width]
}
}
impl<T> Grid<T> {
pub fn is_square(&self) -> bool {
self.width * self.width == self.data.len()
}
}
impl<T: Copy> Grid<T> {
pub fn transform(&self, t: Trafo) -> Self {
let (w, h) = (self.width, self.data.len() / self.width);
let (w_t, h_t) = if t.is_even() { (w, h) } else { (h, w) };
let t_inv = t.invert();
Self {
width: w_t,
data: (0..h_t)
.flat_map(|r_t| (0..w_t).map(move |c_t| (c_t, r_t)))
.map(|idx| self[t_inv.transform((w_t, h_t), idx)])
.collect(),
}
}
}
pub fn solve_rec(
unique_trafos_pieces: &[Vec<Grid<u8>>],
solution: Grid<bool>,
required: &[usize],
cache: &mut HashMap<Grid<bool>, bool>,
) -> bool {
if required.len() == 0 {
return true;
} else if let Some(&value) = cache.get(&solution) {
return value;
}
let (width, height) = (solution.width, solution.data.len() / solution.width);
let pieces = &unique_trafos_pieces[required[0]];
let w = pieces[0].width;
let candidates = (0..height + 1 - w)
.flat_map(|row| (0..width + 1 - w).map(move |col| (col, row)))
.flat_map(|(col, row)| pieces.iter().map(move |piece| (col, row, piece)))
.filter(|&(col, row, piece)| {
(0..w)
.flat_map(|r| (0..w).map(move |c| (c, r)))
.all(|(c, r)| piece[(c, r)] == b'.' || !solution[(col + c, row + r)])
})
.map(|(col, row, piece)| {
let solution = (0..piece.width)
.flat_map(|r| (0..piece.width).map(move |c| (c, r)))
.zip(&piece.data)
.filter(|&(_, b)| *b == b'#')
.fold(solution.clone(), |mut solution, ((c, r), _)| {
solution[(col + c, row + r)] = true;
solution
});
let (c_mn, c_mx, r_mn, r_mx) = solution
.data
.iter()
.enumerate()
.filter_map(|(idx, v)| {
v.then_some((idx % solution.width, idx / solution.width))
})
.fold((0, 0, 0, 0), |(c_mn, c_mx, r_mn, r_mx), (c, r)| {
(c_mn.min(c), c_mx.max(c + 1), r_mn.min(r), r_mx.max(r + 1))
});
let area = (c_mx - c_mn) * (r_mx - r_mn);
(area, solution)
})
.collect::<Vec<_>>();
let area_mn = candidates
.iter()
.map(|(area, _)| *area)
.min()
.unwrap_or_default();
let value = candidates
.into_iter()
.filter(|(area, _)| *area == area_mn) // this might be too restrictive
.any(|(_, solution)| solve_rec(unique_trafos_pieces, solution, &required[1..], cache));
cache.insert(solution, value);
value
}
pub fn solve(
unique_trafos_pieces: &[Vec<Grid<u8>>],
(w, h): (usize, usize),
counts: &[usize],
) -> bool {
solve_rec(
unique_trafos_pieces,
(w, vec![false; w * h]).into(),
&counts
.iter()
.enumerate()
.flat_map(|(idx, &c)| once(idx).cycle().take(c))
.collect::<Vec<_>>(),
&mut HashMap::new(),
)
}
pub fn star_1(PuzzleData { pieces, regions }: &PuzzleData) -> usize {
let unique_trafos_pieces = pieces
.iter()
.cloned()
.map(Grid::from)
.map(|grid| {
(1..8)
.map(Trafo::from)
.fold(vec![grid], |mut unique_trafos, t| {
let g = unique_trafos[0].transform(t);
if !unique_trafos.contains(&g) {
unique_trafos.push(g);
}
unique_trafos
})
})
.collect::<Vec<_>>();
let sizes = unique_trafos_pieces
.iter()
.map(|pieces| pieces[0].data.iter().filter(|&&b| b == b'#').count())
.collect::<Vec<_>>();
regions
.into_iter()
.enumerate()
.filter(|(_, ((w, h), counts))| {
sizes.iter().zip(counts).map(|(s, c)| s * c).sum::<usize>() <= w * h
})
.inspect(|(pos, _)| println!("Solving puzzle {} / {} ...", pos + 1, regions.len()))
.filter(|(_, (dim, counts))| solve(&unique_trafos_pieces, *dim, counts))
.count()
}
#[cfg(test)]
pub mod tests {
use super::*;
#[test]
pub fn test_trafo_invert() {
let pt = (1, 3);
let (w, h) = (4, 5);
for t in (0..8).map(Trafo::from) {
let t_inv = t.invert();
let (w_t, h_t) = if t.is_even() { (w, h) } else { (h, w) };
assert_eq!(
t,
t_inv.invert(),
"Inverting the inverse {:?} does not reproduce {:?}",
t_inv,
t
);
assert_eq!(
pt,
t_inv.transform((w_t, h_t), t.transform((w, h), pt)),
"Transforming {:?} with {:?} after {:?} does not reproduce point",
pt,
t_inv,
t
);
}
}
#[test]
pub fn test_trafo_transform() {
let pt = (1, 3);
let (w, h) = (4, 5);
for (t, exp) in [
(1, 3),
(1, 1),
(2, 1),
(3, 2),
(2, 3),
(3, 1),
(1, 1),
(1, 2),
]
.into_iter()
.enumerate()
{
let t = Trafo::from(t as u8);
assert_eq!(
exp,
t.transform((w, h), pt),
"Unexpected result for {:?}",
t
);
}
}
#[test]
pub fn test_grid_transform() {
let grid = Grid::from((3, vec![1, 2, 3, 0, 0, 0]));
for (t, exp) in [
vec![1, 2, 3, 0, 0, 0],
vec![0, 1, 0, 2, 0, 3],
vec![0, 0, 0, 3, 2, 1],
vec![3, 0, 2, 0, 1, 0],
vec![3, 2, 1, 0, 0, 0],
vec![1, 0, 2, 0, 3, 0],
vec![0, 0, 0, 1, 2, 3],
vec![0, 3, 0, 2, 0, 1],
]
.into_iter()
.enumerate()
{
let exp = Grid::from((3 - (t & 1), exp));
let t = Trafo::from(t as u8);
assert_eq!(exp, grid.transform(t));
}
}
const CONTENT: &str = r#"0:
###
##.
##.
1:
###
##.
.##
2:
.##
###
##.
3:
##.
###
##.
4:
###
#..
###
5:
###
.#.
###
4x4: 0 0 0 0 2 0
12x5: 1 0 1 0 2 2
12x5: 1 0 1 0 3 2
"#;
const EXPECTED_STAR_1: usize = 2;
#[test]
pub fn test_star_1() {
assert_eq!(EXPECTED_STAR_1, star_1(&CONTENT.into()));
}
}
}