Day 1: Chronal Calibration
Rust solution to AoC|2018|1.
Input
Parse input into list of numbers.
I was not sure whether the '+' character is accepted by the parse function - it is!
1
2
3
4
5
6
7
8
9
10
11
pub mod input {
#[derive(Debug)]
pub struct Deltas(pub Vec<isize>);
impl From<&str> for Deltas {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self(s.lines().map(str::parse).collect::<Result<_, _>>().unwrap())
}
}
}
Star 1
Simple sum over all numbers
1
2
3
pub fn star_1(Deltas(deltas): &Deltas) -> SolType {
deltas.iter().sum()
}
Star 2
Find the first partial sum that repeats, cycling through the input list indefinitely.
The indefinite cycling through the input list is achieved with Iterator::cycle, partial sums are calculated using Iterator::scan, repetition is checked using a HashSet.
1
2
3
4
5
6
7
8
9
10
11
12
pub fn star_2(Deltas(deltas): &Deltas) -> SolType {
let mut frequencies = HashSet::new();
deltas
.iter()
.cycle()
.scan(0, |f, d| {
*f += *d;
Some(*f)
})
.find(|&frequency| !frequencies.insert(frequency))
.unwrap()
}
Day 2: Inventory Management System
Rust solution to AoC|2018|2.
Star 1
Count occurrence of letters into HashSet, then check whether there are letters that occur twice or three times and sum twos and threes. Finally, take the product of the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn star_1(PuzzleData(ids): &PuzzleData) -> SolType1 {
let (sum_twos, sum_threes) = ids
.iter()
.map(|id| {
id.iter()
.fold(HashMap::new(), |mut map, &b| {
*map.entry(b).or_insert(0) += 1;
map
})
.values()
.fold((0, 0), |(twos, threes), &cnt| match cnt {
2 => (1, threes),
3 => (twos, 1),
_ => (twos, threes),
})
})
.fold((0, 0), |(sum_twos, sum_threes), (twos, threes)| {
(sum_twos + twos, sum_threes + threes)
});
sum_twos * sum_threes
}
Star 2
For each pair, iterate over pairs of letters and find first difference. If there is no second difference, the result is found.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub fn star_2(PuzzleData(ids): &PuzzleData) -> SolType2 {
for k_1 in 0..ids.len() - 1 {
for k_2 in k_1 + 1..ids.len() {
let mut it = ids[k_1]
.iter()
.zip(ids[k_2].iter())
.enumerate()
.filter(|(_, (a, b))| a != b);
let (k, _) = it.next().unwrap();
if it.next().is_none() {
return String::from_utf8([&ids[k_1][..k], &ids[k_1][k + 1..]].concat()).unwrap();
}
}
}
panic!("No solution!");
}
Day 3: No Matter How You Slice It
Rust solution to AoC|2018|3.
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
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<Claim>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(s.lines().map(Claim::from).collect())
}
}
#[derive(Debug)]
pub struct Claim {
pub id: usize,
pub p: (usize, usize),
pub w: (usize, usize),
}
impl From<&str> for Claim {
fn from(s: &str) -> Self {
let mut words = s.split_ascii_whitespace();
let id = words.next().unwrap()[1..].parse().unwrap();
words.next(); // @
let p = words
.next()
.unwrap()
.trim_end_matches(':')
.split_once(',')
.map(|(a, b)| (a.parse().unwrap(), b.parse().unwrap()))
.unwrap();
let w = words
.next()
.unwrap()
.split_once('x')
.map(|(a, b)| (a.parse().unwrap(), b.parse().unwrap()))
.unwrap();
Self { id, p, w }
}
}
}
Star 1
Add all overlaps to a set and return set size
1
2
3
4
5
6
7
8
9
10
11
12
13
pub fn star_1(PuzzleData(claims): &PuzzleData) -> SolType1 {
(0..claims.len() - 1)
.flat_map(|k_1| (k_1 + 1..claims.len()).map(move |k_2| (&claims[k_1], &claims[k_2])))
.fold(HashSet::new(), |mut set, (c_1, c_2)| {
for x in c_1.p.0.max(c_2.p.0)..(c_1.p.0 + c_1.w.0).min(c_2.p.0 + c_2.w.0) {
for y in c_1.p.1.max(c_2.p.1)..(c_1.p.1 + c_1.w.1).min(c_2.p.1 + c_2.w.1) {
set.insert((x, y));
}
}
set
})
.len()
}
Star 2
Scan for each claim whether it overlaps with any other claim. Return the ID for the claim that does not overlap with any other.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub fn star_2(PuzzleData(claims): &PuzzleData) -> SolType2 {
claims
.iter()
.find(|c_1| {
claims.iter().all(|c_2| {
c_1.id == c_2.id
|| c_1.p.0 + c_1.w.0 <= c_2.p.0
|| c_1.p.0 >= c_2.p.0 + c_2.w.0
|| c_1.p.1 + c_1.w.1 <= c_2.p.1
|| c_1.p.1 >= c_2.p.1 + c_2.w.1
})
})
.unwrap()
.id
}
Day 4: Repose Record
Rust solution to AoC|2018|4.
Input
I first parse the input in a Vec of events which I sort by date time.
Then I build a map with guard IDs as keys and sleep phases 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
pub mod input {
use std::{collections::HashMap, ops::Range};
#[derive(Debug)]
pub struct PuzzleData(pub HashMap<usize, Vec<Range<usize>>>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let mut events = s
.lines()
.map(|line| {
(
(
line[1..5].parse::<usize>().unwrap(),
line[6..8].parse::<usize>().unwrap(),
line[9..11].parse::<usize>().unwrap(),
line[12..14].parse::<usize>().unwrap(),
line[15..17].parse::<usize>().unwrap(),
),
&line[19..],
)
})
.collect::<Vec<_>>();
events.sort_unstable_by_key(|(date_time, _)| *date_time);
let mut map = HashMap::new();
let mut id = 0;
let mut asleep_minute = 0;
for (date_time, event) in events {
match event {
"falls asleep" => {
assert_eq!(0, date_time.3);
asleep_minute = date_time.4;
}
"wakes up" => {
assert_eq!(0, date_time.3);
map.entry(id)
.or_insert(Vec::new())
.push(asleep_minute..date_time.4);
}
v => {
id = v
.strip_prefix("Guard #")
.and_then(|v| v.strip_suffix(" begins shift"))
.unwrap()
.parse()
.unwrap();
}
}
}
Self(map)
}
}
}
Star 1
First find the guard with the highest number of minutes asleep.
Then determine for this guard which minute he is asleep most often.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn star_1(PuzzleData(map): &PuzzleData) -> SolType {
let (id, sleep_phases) = map
.iter()
.max_by_key(|(_, sleep_phases)| {
sleep_phases
.iter()
.map(|sleep_phase| sleep_phase.len())
.sum::<usize>()
})
.unwrap();
let mut minutes = HashMap::new();
for sleep_phase in sleep_phases {
for minute in sleep_phase.clone() {
*minutes.entry(minute).or_insert(0) += 1;
}
}
id * minutes.iter().max_by_key(|(_, &count)| count).unwrap().0
}
Star 2
Determine for each guard which minute he is asleep most often. Then find the maximum over all guards.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub fn star_2(PuzzleData(map): &PuzzleData) -> SolType {
map.iter()
.map(|(id, sleep_phases)| {
let mut minutes = HashMap::new();
for sleep_phase in sleep_phases {
for minute in sleep_phase.clone() {
*minutes.entry(minute).or_insert(0) += 1;
}
}
let (minute, count) = minutes.iter().max_by_key(|(_, &count)| count).unwrap();
(id, *minute, *count)
})
.max_by_key(|(_, _, count)| *count)
.map(|(id, minute, _)| id * minute)
.unwrap()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"[1518-11-01 00:00] Guard #10 begins shift
[1518-11-01 00:05] falls asleep
[1518-11-01 00:25] wakes up
[1518-11-01 00:30] falls asleep
[1518-11-01 00:55] wakes up
[1518-11-01 23:58] Guard #99 begins shift
[1518-11-02 00:40] falls asleep
[1518-11-02 00:50] wakes up
[1518-11-03 00:05] Guard #10 begins shift
[1518-11-03 00:24] falls asleep
[1518-11-03 00:29] wakes up
[1518-11-04 00:02] Guard #99 begins shift
[1518-11-04 00:36] falls asleep
[1518-11-04 00:46] wakes up
[1518-11-05 00:03] Guard #99 begins shift
[1518-11-05 00:45] falls asleep
[1518-11-05 00:55] wakes up
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(240, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(4_455, star_2(&data));
}
}
Day 5: Alchemical Reduction
Rust solution to AoC|2018|5.
See how a polymer reduces in size as reactions go on
Star 1
Just process unit by unit and either append it to the result or remove the last unit from the result if a reaction takes place.
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
const POLARITY_OFF: u8 = b'a' - b'A';
pub trait ReducedLen {
fn reduced_len(self) -> usize;
}
impl<T> ReducedLen for T
where
T: Iterator<Item = u8>,
{
fn reduced_len(self) -> usize {
self.fold(Vec::new(), |mut result, unit| {
match result.last() {
Some(&last) if last + POLARITY_OFF == unit || unit + POLARITY_OFF == last => {
result.pop();
}
_ => result.push(unit),
}
result
})
.len()
}
}
pub fn star_1(polymer: &&str) -> SolType1 {
polymer.trim().bytes().reduced_len()
}
Star 2
Repeat the process from part 1 filtering out units of single types one by one and find the minimum length.
I used this one to implement a trait which allows to directly call reduced_len on an iterator over bytes.
1
2
3
4
5
6
7
8
9
10
11
12
pub fn star_2(polymer: &&str) -> SolType2 {
(b'A'..=b'Z')
.map(|bad_unit| {
polymer
.trim()
.bytes()
.filter(|&unit| unit != bad_unit && unit != bad_unit + POLARITY_OFF)
.reduced_len()
})
.min()
.unwrap()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"dabAcCaCBAcCcaDA
"#;
#[test]
pub fn test_star_1() {
assert_eq!(10, star_1(&CONTENT));
}
#[test]
pub fn test_star_2() {
assert_eq!(4, star_2(&CONTENT));
}
}
Day 6: Chronal Coordinates
Rust solution to AoC|2018|6.
Input
Parse input in list of 2D coordinates and determine bounding box
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<(isize, isize)>, pub (isize, isize, isize, isize));
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
s.lines()
.map(|l| {
l.split_once(", ")
.map(|(a, b)| (a.parse().unwrap(), b.parse().unwrap()))
.unwrap()
})
.fold(
Self(Vec::new(), (isize::MAX, isize::MAX, isize::MIN, isize::MIN)),
|Self(mut list, (x_mn, y_mn, x_mx, y_mx)), (x, y)| {
list.push((x, y));
Self(list, (x_mn.min(x), y_mn.min(y), x_mx.max(x), y_mx.max(y)))
},
)
}
}
}
Star 1
The solution is calculated in three steps:
-
Determine which coordinates have a finite area of points that are closes to this coordinate. An area is finite if it is bound from all directions (east, north, west, south) by other coordinates; special treatment is required if neighboring points are exactly on the diagonal (north-east, north-west, south-west, south-east), in which case the locus of equidistant points is on a diagonal line (it turned out that - for my puzzle input - those corner cases are not relevant)
-
For each coordinate, count the number of points within the bounding box that are closest to this point. If more than one coordinate is at the same minimum distance of a point, it is not counted for any of them
-
Find the largest count among all coordinates with finite area
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 fn star_1(PuzzleData(coords, (x_mn, y_mn, x_mx, y_mx)): &PuzzleData) -> SolType {
// determine which coordinates have finite areas
let mut finite = vec![false; coords.len()];
for k in 0..coords.len() {
let (x_1, y_1) = coords[k];
let (mut e, mut ne, mut n, mut nw, mut w, mut sw, mut s, mut se) =
(false, false, false, false, false, false, false, false);
for &(x_2, y_2) in coords {
e = e || x_2 > x_1 && (y_2 - y_1).abs() < x_2 - x_1;
ne = ne || x_2 > x_1 && y_1 - y_2 == x_2 - x_1;
n = n || y_2 < y_1 && (x_2 - x_1).abs() < y_1 - y_2;
nw = nw || x_2 < x_1 && y_1 - y_2 == x_1 - x_2;
w = w || x_2 < x_1 && (y_2 - y_1).abs() < x_1 - x_2;
sw = sw || x_2 < x_1 && y_2 - y_1 == x_1 - x_2;
s = s || y_2 > y_1 && (x_2 - x_1).abs() < y_2 - y_1;
se = se || x_2 > x_1 && y_2 - y_1 == x_2 - x_1;
finite[k] = (e || ne || n && se)
&& (n || nw || w && ne)
&& (w || sw || s && nw)
&& (s || se || e && sw);
if finite[k] {
break;
}
}
}
// count closest points for each coordinate
let mut counts = vec![0; coords.len()];
for x in *x_mn..=*x_mx {
for y in *y_mn..=*y_mx {
let mut d_min = isize::MAX;
let mut minimizers = Vec::new();
for (k, d) in coords
.iter()
.enumerate()
.map(|(k, coord)| (k, (coord.0 - x).abs() + (coord.1 - y).abs()))
{
match d.cmp(&d_min) {
Ordering::Less => {
d_min = d;
minimizers.truncate(0);
minimizers.push(k);
}
Ordering::Equal => {
minimizers.push(k);
}
_ => {}
}
}
if minimizers.len() == 1 {
counts[minimizers[0]] += 1;
}
}
}
// find largest finite area
(0..counts.len())
.filter(|&k| finite[k])
.map(|k| counts[k])
.max()
.unwrap()
}
Star 2
Just calculate the sum for all points within the bounding box.
For points on the edge of the bounding box, moving away from the edge by one unit increases the sum by the number of coordinates
For points on the corner of the bounding box, there are n points at Manhattan distance n - 1 of the corner.
Again, it turns out, that this is not needed. For my puzzle input, none of the points on the edges or corners are in range and neither are any points outside of the bounding box.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
pub fn region_size(PuzzleData(coords, (x_mn, y_mn, x_mx, y_mx)): &PuzzleData, d: usize) -> SolType {
(*x_mn..=*x_mx)
.flat_map(|x| (*y_mn..=*y_mx).map(move |y| (x, y)))
.map(|(x, y)| {
(
x == *x_mn || x == *x_mx,
y == *y_mn || y == *y_mx,
coords
.iter()
.map(|&c| ((c.0 - x).abs() + (c.1 - y).abs()) as usize)
.sum::<usize>(),
)
})
.filter(|(_, _, s)| *s < d)
.map(|(edge_x, edge_y, s)| {
if edge_x && edge_y {
// corner
let k = (d - s).div_ceil(coords.len());
(k + 1) * k / 2
} else if edge_x || edge_y {
// edge w/o corner
(d - s).div_ceil(coords.len())
} else {
// inner
1
}
})
.sum()
}
pub fn star_2(data: &PuzzleData) -> SolType {
region_size(data, 10_000)
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"1, 1
1, 6
8, 3
3, 4
5, 5
8, 9
"#;
#[test]
pub fn test_from() {
let PuzzleData(coords, bbox) = PuzzleData::from(CONTENT);
assert_eq!(6, coords.len());
assert_eq!((1, 1, 8, 9), bbox);
}
#[test]
pub fn test_star_1() {
assert_eq!(17, star_1(&CONTENT.into()));
}
#[test]
pub fn test_region_size() {
assert_eq!(16, region_size(&CONTENT.into(), 32));
}
}
Day 7: The Sum of Its Parts
Rust solution to AoC|2018|7.
Input
Parse the input in a sorted map (BTreeMap) with steps as keys and prerequisite steps encoded in bits of u32 integers as values.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub mod input {
use std::collections::BTreeMap;
#[derive(Debug)]
pub struct PuzzleData(pub BTreeMap<u8, u32>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(s.lines().map(|l| (l.as_bytes()[5], l.as_bytes()[36])).fold(
BTreeMap::new(),
|mut map, (pre, post)| {
map.entry(pre).or_insert(0);
*map.entry(post).or_insert(0) |= 1 << (pre - b'A');
map
},
))
}
}
}
Star 1
Iterate until all steps are done. In each iteration, take the first step for which all prerequisites are met.
1
2
3
4
5
6
7
8
9
10
11
12
13
pub fn star_1(PuzzleData(prerequisites): &PuzzleData) -> SolType1 {
let mut completed = 0;
let mut result = String::with_capacity(prerequisites.len());
while result.len() < prerequisites.len() {
let (&k, _) = prerequisites
.iter()
.find(|(&k, &pre)| pre & completed == pre && (completed >> (k - b'A')) & 1 == 0)
.unwrap();
result.push(k as char);
completed |= 1 << (k - b'A');
}
result
}
Star 2
While not all steps are done, 'wait' until next worker(s) are available, for each available worker, assign it the next available step; if there are workers that cannot be assigned a task, re-assess after the next step to be completed.
Steps in process are pushed to a heap (BTreeMap) with completion time as value and a tuple of available workers and completed steps as value.
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
pub fn time_to_complete(
PuzzleData(prerequisites): &PuzzleData,
workers: usize,
time_0: usize,
) -> SolType2 {
let mut heap = BTreeMap::from([(0, (workers, 0))]);
let mut started: u32 = 0;
let mut completed: u32 = 0;
while let Some((t, (workers, steps))) = heap.pop_first() {
// update completed steps
completed |= steps;
if completed.count_ones() == prerequisites.len() as u32 {
return t;
}
// insert possible steps to heap
let mut len = 0;
let started_prev = started;
for possible in prerequisites
.iter()
.filter(|(&k, &pre)| pre & completed == pre && (started_prev >> (k - b'A')) & 1 == 0)
.map(|(&k, _)| k)
.take(workers)
{
len += 1;
started |= 1 << (possible - b'A');
heap.entry(t + time_0 + (possible - b'A' + 1) as usize)
.and_modify(|(workers, steps)| {
*workers += 1;
*steps |= 1 << (possible - b'A');
})
.or_insert((1, 1 << (possible - b'A')));
}
// add excess workers to head of heap
if len < workers {
let mut entry = heap.first_entry().unwrap();
let (prev_workers, _) = entry.get_mut();
*prev_workers += workers - len;
}
}
panic!("No solution!");
}
pub fn star_2(data: &PuzzleData) -> SolType2 {
time_to_complete(data, 5, 60)
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#[cfg(test)]
mod tests {
use std::collections::BTreeMap;
use super::*;
const CONTENT: &str = r#"Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.
"#;
#[test]
pub fn test_from() {
let PuzzleData(prerequisites) = PuzzleData::from(CONTENT);
assert_eq!(
BTreeMap::from([
(b'A', 0b000100),
(b'B', 0b000001),
(b'C', 0b000000),
(b'D', 0b000001),
(b'E', 0b101010),
(b'F', 0b000100)
]),
prerequisites
);
}
#[test]
pub fn test_star_1() {
assert_eq!("CABDFE".to_string(), star_1(&CONTENT.into()));
}
#[test]
pub fn test_time_to_complete() {
assert_eq!(15, time_to_complete(&CONTENT.into(), 2, 0));
}
}
Day 8: Memory Maneuver
Rust solution to AoC|2018|8.
Recursion on trees.
Star 1
Recursively sum metadata
1
2
3
4
5
6
7
8
9
10
11
12
pub fn sum_metadata<T: Iterator<Item = usize>>(data: &mut T) -> SolType {
let n_children = data.next().unwrap();
let n_metadata = data.next().unwrap();
(0..n_children).map(|_| sum_metadata(data)).sum::<SolType>()
+ (0..n_metadata)
.map(|_| data.next().unwrap())
.sum::<SolType>()
}
pub fn star_1(data: &&str) -> SolType {
sum_metadata(&mut data.split_ascii_whitespace().map(|v| v.parse().unwrap()))
}
Star 2
Recursively calculate node values. I do not have a solution without intermediate storage since the metadata (indices to child nodes) is only available after the child nodes are processed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn node_value<T: Iterator<Item = usize>>(data: &mut T) -> SolType {
let n_children = data.next().unwrap();
let n_metadata = data.next().unwrap();
if n_children == 0 {
(0..n_metadata).map(|_| data.next().unwrap()).sum()
} else {
let child_values = (0..n_children)
.map(|_| node_value(data))
.collect::<Vec<_>>();
(0..n_metadata)
.map(|_| data.next().unwrap())
.filter(|&k| k > 0 && k <= n_children)
.map(|k| child_values[k - 1])
.sum()
}
}
pub fn star_2(data: &&str) -> SolType {
node_value(&mut data.split_ascii_whitespace().map(|v| v.parse().unwrap()))
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2"#;
#[test]
pub fn test_star_1() {
assert_eq!(138, star_1(&CONTENT));
}
#[test]
pub fn test_star_2() {
assert_eq!(66, star_2(&CONTENT));
}
}
Day 9: Marble Mania
Rust solution to AoC|2018|9.
Linked lists representing marbles in a circle.
I represent the doubly linked list as two separate lists, one for the forward (clockwise) and one for the backward (anti-clockwise) direction. Each list’s entries are the successors / predecessors of the node labeled by the index into the list.
Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub mod input {
#[derive(Debug, PartialEq, Eq)]
pub struct PuzzleData(pub usize, pub usize);
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
let mut words = s.split_ascii_whitespace();
Self(
words.nth(0).unwrap().parse().unwrap(),
words.nth(5).unwrap().parse().unwrap(),
)
}
}
}
Star 1
Simulate turns until the last marble is played
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
pub fn star_1(PuzzleData(players, last): &PuzzleData) -> SolType {
let mut ring_fwd = vec![0; last + 1];
let mut ring_rev = vec![0; last + 1];
let mut current = 0;
let mut scores = vec![0; *players];
for k in 1..=*last {
if k % 23 == 0 {
// h g f e d c b a (current) => h (f) e d c b a current
let f = ring_rev[ring_rev[ring_rev[ring_rev[ring_rev[ring_rev[current]]]]]];
let g = ring_rev[f];
let h = ring_rev[g];
ring_fwd[h] = f;
ring_rev[f] = h;
current = f;
scores[k % *players] += g + k;
} else {
// (current) a b => current a (k) b
let a = ring_fwd[current];
let b = ring_fwd[a];
(ring_fwd[a], ring_fwd[k]) = (k, b);
(ring_rev[k], ring_rev[b]) = (a, k);
current = k;
}
}
scores.iter().cloned().max().unwrap()
}
Star 2
I had no better idea than re-using my code from part 1 and simulate the larger game.
1
2
3
pub fn star_2(PuzzleData(players, last): &PuzzleData) -> SolType {
star_1(&PuzzleData(*players, 100 * last))
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"10 players; last marble is worth 1618 points"#;
#[test]
pub fn test_from() {
assert_eq!(PuzzleData(10, 1_618), CONTENT.into());
}
#[test]
pub fn test_star_1() {
assert_eq!(8_317, star_1(&CONTENT.into()));
}
}
Day 10: The Stars Align
Rust solution to AoC|2018|10.
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
pub mod input {
use crate::Point;
#[derive(Debug)]
pub struct PuzzleData(pub Vec<(Point, Point)>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(
s.lines()
.map(|l| {
l.strip_prefix("position=<")
.and_then(|l| l.strip_suffix('>'))
.and_then(|l| l.split_once("> velocity=<"))
.unwrap()
})
.map(|(a, b)| {
(
a.split_once(',')
.map(|(a1, a2)| {
(a1.trim().parse().unwrap(), a2.trim().parse().unwrap())
})
.unwrap()
.into(),
b.split_once(',')
.map(|(b1, b2)| {
(b1.trim().parse().unwrap(), b2.trim().parse().unwrap())
})
.unwrap()
.into(),
)
})
.collect(),
)
}
}
}
Star 1 & 2
Figure out when the stars are closest together and decode the display they form 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
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
pub fn get_lights_at(lights: &[(Point, Point)], t: isize) -> (Vec<Point>, BoundingBox) {
lights.iter().fold(
(Vec::with_capacity(lights.len()), BoundingBox::empty()),
|(mut lights, bbox), (p, v)| {
let p = Point::from((p.x + t * v.x, p.y + t * v.y));
lights.push(p);
(lights, bbox.include(&p))
},
)
}
pub fn solve(PuzzleData(lights): &PuzzleData) -> (Vec<u8>, usize) {
// average position and velocity in x-direction
// sum_p(t) = sum_p + t * sum_v
let (sum_p, sum_v) = lights
.iter()
.fold((0, 0), |(sum_p, sum_v), (p, v)| (sum_p + p.x, sum_v + v.x));
// approximate time when individual x positions equal average x position,
// i.e., lights are as close to each other as possible
// n * p_i(t) = n * p_i + n * t v_i = sum_p + t * sum_v
// n * p_i - sum_p + t * (n * v_i - sum_v) = 0
// t = (sum_p - n * p_i) / (n * v_i - sum_v)
let sum_t = lights.iter().fold(0, |sum_t, (p, v)| {
sum_t + (sum_p - lights.len() as isize * p.x) / (lights.len() as isize * v.x - sum_v)
});
let mut t = sum_t / lights.len() as isize;
// candidate lights and bbox
let (mut lights_0, mut bbox_0) = get_lights_at(lights, t);
loop {
// while bbox gets smaller, update
let (lights_1, bbox_1) = get_lights_at(lights, t + 1);
if bbox_1.p_max.x - bbox_1.p_min.x < bbox_0.p_max.x - bbox_0.p_min.x {
(lights_0, bbox_0) = (lights_1, bbox_1);
t += 1;
} else {
break;
}
}
let w = (bbox_0.p_max.x - bbox_0.p_min.x + 1) as usize;
let h = (bbox_0.p_max.y - bbox_0.p_min.y + 1) as usize;
let mut display = vec![DARK as u8; w * h];
for &p in &lights_0 {
display[(p.x - bbox_0.p_min.x) as usize + (p.y - bbox_0.p_min.y) as usize * w] = LIT as u8;
}
(display, t as _)
}
pub fn star_1_2(data: &PuzzleData) -> SolType {
let (display, t) = solve(data);
(display.decode_big(0).unwrap(), t).into()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"position=< 9, 1> velocity=< 0, 2>
position=< 7, 0> velocity=<-1, 0>
position=< 3, -2> velocity=<-1, 1>
position=< 6, 10> velocity=<-2, -1>
position=< 2, -4> velocity=< 2, 2>
position=<-6, 10> velocity=< 2, -2>
position=< 1, 8> velocity=< 1, -1>
position=< 1, 7> velocity=< 1, 0>
position=<-3, 11> velocity=< 1, -2>
position=< 7, 6> velocity=<-1, -1>
position=<-2, 3> velocity=< 1, 0>
position=<-4, 3> velocity=< 2, 0>
position=<10, -3> velocity=<-1, 1>
position=< 5, 11> velocity=< 1, -2>
position=< 4, 7> velocity=< 0, -1>
position=< 8, -2> velocity=< 0, 1>
position=<15, 0> velocity=<-2, 0>
position=< 1, 6> velocity=< 1, 0>
position=< 8, 9> velocity=< 0, -1>
position=< 3, 3> velocity=<-1, 1>
position=< 0, 5> velocity=< 0, -1>
position=<-2, 2> velocity=< 2, 0>
position=< 5, -2> velocity=< 1, 2>
position=< 1, 4> velocity=< 2, 1>
position=<-2, 7> velocity=< 2, -2>
position=< 3, 6> velocity=<-1, -1>
position=< 5, 0> velocity=< 1, 0>
position=<-6, 0> velocity=< 2, 0>
position=< 5, 9> velocity=< 1, -2>
position=<14, 7> velocity=<-2, 0>
position=<-3, 6> velocity=< 2, -1>
"#;
pub type CoordT = (isize, isize);
pub const EXPECTED_LIGHTS: &[(CoordT, CoordT)] = &[
((9, 1), (0, 2)),
((7, 0), (-1, 0)),
((3, -2), (-1, 1)),
((6, 10), (-2, -1)),
((2, -4), (2, 2)),
((-6, 10), (2, -2)),
((1, 8), (1, -1)),
((1, 7), (1, 0)),
((-3, 11), (1, -2)),
((7, 6), (-1, -1)),
((-2, 3), (1, 0)),
((-4, 3), (2, 0)),
((10, -3), (-1, 1)),
((5, 11), (1, -2)),
((4, 7), (0, -1)),
((8, -2), (0, 1)),
((15, 0), (-2, 0)),
((1, 6), (1, 0)),
((8, 9), (0, -1)),
((3, 3), (-1, 1)),
((0, 5), (0, -1)),
((-2, 2), (2, 0)),
((5, -2), (1, 2)),
((1, 4), (2, 1)),
((-2, 7), (2, -2)),
((3, 6), (-1, -1)),
((5, 0), (1, 0)),
((-6, 0), (2, 0)),
((5, 9), (1, -2)),
((14, 7), (-2, 0)),
((-3, 6), (2, -1)),
];
#[test]
pub fn test_from() {
let PuzzleData(lights) = PuzzleData::from(CONTENT);
assert_eq!(
EXPECTED_LIGHTS
.iter()
.map(|&(p, v)| (Point::from(p), Point::from(v)))
.collect::<Vec<_>>(),
lights
);
}
pub const EXPECTED_DISPLAY: &[u8] =
"#...#..####...#...#.#...#...#.#####...#.#...#...#.#...#...#.#...#...#.#...#..###"
.as_bytes();
#[test]
pub fn test_solve() {
assert_eq!((Vec::from(EXPECTED_DISPLAY), 3), solve(&CONTENT.into()));
}
}
Day 11: Chronal Charge
Rust solution to AoC|2018|11.
The solution is based on Summed-area tables.
Input
The summed area table is calculated as part of the input processing.
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 {
use crate::W;
#[derive(Debug)]
pub struct PuzzleData(pub Vec<i64>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let serial = s.trim().parse::<i64>().unwrap();
let mut grid = vec![0; W * W];
for x in 1..W {
let rack_id = x as i64 + 10;
for y in 1..W {
grid[x + W * y] = (((rack_id * y as i64 + serial) * rack_id) / 100) % 10 - 5
+ grid[(x - 1) + W * y]
+ grid[x + W * (y - 1)]
- grid[x - 1 + W * (y - 1)];
}
}
PuzzleData(grid)
}
}
}
Star 1
Part 1 is solved by an iteration over all possible pairs of x and y coordinates.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub fn star_1(PuzzleData(grid): &PuzzleData) -> SolType {
(0..W - 3)
.flat_map(|x| (0..W - 3).map(move |y| (x, y)))
.map(|(x, y)| {
(
x,
y,
grid[(x + 3) + W * (y + 3)] + grid[x + W * y]
- grid[x + W * (y + 3)]
- grid[x + 3 + W * y],
)
})
.max_by_key(|(_, _, s)| *s)
.map(|(x, y, _)| format!("{},{}", x + 1, y + 1))
.unwrap()
}
Star 2
Part 2 adds the width of the square as a third dimension of iteration.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pub fn star_2(PuzzleData(grid): &PuzzleData) -> SolType {
(0..W - 1)
.flat_map(|x| (0..W - 1).map(move |y| (x, y)))
.flat_map(|(x, y)| (1..usize::min(W - x, W - y)).map(move |w| (x, y, w)))
.map(|(x, y, w)| {
(
x,
y,
w,
grid[(x + w) + W * (y + w)] + grid[x + W * y]
- grid[x + W * (y + w)]
- grid[x + w + W * y],
)
})
.max_by_key(|(_, _, _, s)| *s)
.map(|(x, y, w, _)| format!("{},{},{}", x + 1, y + 1, w))
.unwrap()
}
Day 12: Subterranean Sustainability
Rust solution to AoC|2018|12.
Simulate plant growth.
Solution idea: interpret pots as bits, a plant in a pot corresponds to a set bit, an empty pot is an unset bit.
Five consecutive bits are used as the address to an update lookup array.
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
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub initial: Vec<bool>,
pub rules: [bool; 1 << 5],
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let mut lines = s.lines();
Self {
initial: lines
.next()
.and_then(|p| p.strip_prefix("initial state: "))
.map(|p| p.bytes().map(|b| b == b'#').collect())
.unwrap(),
rules: lines.skip(1).fold([false; 1 << 5], |mut v, l| {
v[l[..5].bytes().fold(0, |v, b| v << 1 | (b == b'#') as usize)] =
&l[9..] == "#";
v
}),
}
}
}
}
Star 1
Simulate 20 generations
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 generation(rules: &[bool], state: &[bool], update: &mut Vec<bool>, mut off: isize) -> isize {
update.truncate(0);
let mut p = 0;
for k in 0..state.len() + 4 {
// remove highest value 'bit' and shift left
p = (p & 0b1111) << 1;
if k < state.len() {
// add 'bit' to the right
p |= state[k] as u8;
};
// skip leading zeros
if !update.is_empty() || rules[p as usize] {
if update.is_empty() {
// first one -> new offset
off = off + k as isize - 2;
}
update.push(rules[p as usize]);
}
}
// trim trailing zeros
let mut len = update.len();
while len > 0 && !update[len - 1] {
len -= 1;
}
update.truncate(len);
off
}
pub fn star_1(PuzzleData { initial, rules }: &PuzzleData) -> SolType {
let mut state = initial.to_owned();
let mut update = Vec::with_capacity(state.len());
let mut off = 0;
for _ in 0..20 {
off = generation(rules, &state, &mut update, off);
(state, update) = (update, state);
}
(0..state.len())
.filter(|&k| state[k])
.map(|k| k as isize + off)
.sum()
}
Star 2
Simulate until the pattern does not change. After that, only the offset (possibly) changes by constant steps and the rest of the simulation is a simple fast forward to calculate the ultimate offset.
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 star_2(PuzzleData { initial, rules }: &PuzzleData) -> SolType {
let mut state = initial.to_owned();
let mut update = Vec::with_capacity(state.len());
let mut off = 0;
// loop until pattern is static,
// in subsequent generations, pattern is shifted by delta
let mut generations = 0; // count generations
let mut delta = 0; // delta in offset
while state != update {
generations += 1;
delta = generation(rules, &state, &mut update, off) - off;
off += delta;
(state, update) = (update, state);
}
let n = 50_000_000_000;
off += (n - generations) * delta;
(0..state.len())
.filter(|&k| state[k])
.map(|k| k as isize + off)
.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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"initial state: #..#.#..##......###...###
...## => #
..#.. => #
.#... => #
.#.#. => #
.#.## => #
.##.. => #
.#### => #
#.#.# => #
#.### => #
##.#. => #
##.## => #
###.. => #
###.# => #
####. => #
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
assert_eq!(325, star_1(&CONTENT.into()));
}
}
Day 13: Mine Cart Madness
Rust solution to AoC|2018|13.
Find collisions of carts on tracks. Don’t forget to not only check collisions with carts that had already moved in a current tick but also those that have not yet moved.
I implemented enums for Orientation and Turn to have the updates explicit. This is certainly a bit of an overhead for this quite simple problem.
Input
Parse tracks. Replace carts by tracks below them and collect carts in a separate Vec (with position, orientation and next turn choice).
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 mod input {
use crate::{Orientation, Turn};
#[derive(Debug)]
pub struct PuzzleData {
pub tracks: Vec<u8>,
pub width: usize,
pub carts: Vec<((usize, usize), (Orientation, Turn))>,
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let width = s.find('\n').unwrap();
let mut tracks = s.bytes().filter(|&b| b != b'\n').collect::<Vec<_>>();
let mut carts = Vec::new();
for (k, b) in tracks
.iter_mut()
.enumerate()
.filter(|(_, b)| [b'<', b'>', b'^', b'v'].contains(b))
{
let (x, y) = (k % width, k / width);
carts.push(((y, x), (Orientation::from(*b as char), Turn::Left)));
*b = match *b {
b'>' | b'<' => b'-',
b'^' | b'v' => b'|',
_ => panic!(),
};
}
assert!((tracks.len() / width) * width == tracks.len());
Self {
tracks,
width,
carts,
}
}
}
}
Star 1
Simulate ticks until a collision occurs.
Because carts with lowest y move first, the position is stored as (y, x) to allow sorting using the natural order of the carts representation.
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_1(
PuzzleData {
width,
tracks,
carts,
}: &PuzzleData,
) -> SolType {
let mut carts = carts.to_owned();
loop {
carts.sort_unstable();
for k in 0..carts.len() {
let ((y, x), (o, c)) = carts[k];
let dir = update(o, c, tracks[x + width * y]);
let pos = dir.0.step((y, x));
carts[k] = (pos, dir);
if carts
.iter()
.enumerate()
.any(|(i, &(p, _))| i != k && p == pos)
{
return format!("{},{}", pos.1, pos.0);
}
}
}
}
Star 2
Simple extension to simulate ticks until only one cart is left. Crashed carts are 'parked' at (y, x) = (usize::MAX; usize::MAX) and removed from the list after re-sorting.
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
pub const CRASHED: (usize, usize) = (usize::MAX, usize::MAX);
pub fn star_2(
PuzzleData {
width,
tracks,
carts,
}: &PuzzleData,
) -> SolType {
let mut carts = carts.to_owned();
loop {
carts.sort_unstable();
// remove crashed
let mut len = carts.len();
while len > 0 && carts[len - 1].0 == CRASHED {
len -= 1;
}
carts.truncate(len);
// return if only one cart left
if len == 1 {
let (y, x) = carts[0].0;
return format!("{},{}", x, y);
}
for k in 0..carts.len() {
let ((y, x), (o, c)) = carts[k];
if (y, x) == CRASHED {
// skip crashed
continue;
}
let dir = update(o, c, tracks[x + width * y]);
let pos = dir.0.step((y, x));
carts[k] = (pos, dir);
if let Some((j, _)) = carts
.iter()
.enumerate()
.find(|(i, &(p, _))| *i != k && p == pos)
{
// mark as crashed
carts[j].0 = CRASHED;
carts[k].0 = CRASHED;
}
}
}
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT_0: &str = r#"|
v
|
|
|
^
|
"#;
const CONTENT_1: &str = r#"/->-\
| | /----\
| /-+--+-\ |
| | | | v |
\-+-/ \-+--/
\------/
"#;
const CONTENT_2: &str = r#"/>-<\
| |
| /<+-\
| | | v
\>+</ |
| ^
\<->/
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT_1);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
assert_eq!("0,3", star_1(&CONTENT_0.into()));
assert_eq!("7,3", star_1(&CONTENT_1.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!("6,4", star_2(&CONTENT_2.into()));
}
}
Day 14: Chocolate Charts
Rust solution to AoC|2018|14.
Lots of hot chocolate recipes…
Input
1
2
3
4
5
6
7
8
9
10
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub usize);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(s.trim().parse().unwrap())
}
}
}
Star 1
Create recipes until the list is long enough
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn star_1(&PuzzleData(n): &PuzzleData) -> SolType1 {
let mut recipes: Vec<u8> = Vec::from([3, 7]);
let (mut k1, mut k2) = (0, 1);
while recipes.len() < n + 10 {
let c = recipes[k1] + recipes[k2];
if c >= 10 {
recipes.push(c / 10);
}
recipes.push(c % 10);
(k1, k2) = (
(k1 + 1 + recipes[k1] as usize) % recipes.len(),
(k2 + 1 + recipes[k2] as usize) % recipes.len(),
);
}
recipes[n..n + 10]
.iter()
.fold(0, |v, &d| 10 * v + d as usize)
}
Star 2
Create recipes until the tail matches the required pattern
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
pub fn star_2(&PuzzleData(pat): &PuzzleData) -> SolType2 {
let (mut m, mut pat_len) = (1, 0);
while m <= pat {
(m, pat_len) = (m * 10, pat_len + 1);
}
let mut tail = 0;
let mut recipes: Vec<u8> = Vec::from([3, 7]);
let (mut k1, mut k2) = (0, 1);
loop {
let c = recipes[k1] + recipes[k2];
if c >= 10 {
let r = c / 10;
recipes.push(r);
tail = (10 * tail + r as usize) % m;
if tail == pat {
return recipes.len() - pat_len;
}
}
let r = c % 10;
recipes.push(r);
tail = (10 * tail + r as usize) % m;
if tail == pat {
return recipes.len() - pat_len;
}
(k1, k2) = (
(k1 + 1 + recipes[k1] as usize) % recipes.len(),
(k2 + 1 + recipes[k2] as usize) % recipes.len(),
);
}
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#[cfg(test)]
mod tests {
use super::*;
#[test]
pub fn test_star_1() {
assert_eq!(5_941_429_882, star_1(&PuzzleData(2_018)));
}
#[test]
pub fn test_star_2() {
assert_eq!(2_018, star_2(&PuzzleData(59_414)));
}
}
Day 15: Beverage Bandits
Rust solution to AoC|2018|15.
Simulate goblin vs. elves combats.
Input
Parse the input in a flat grid of Element enums.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
pub mod input {
use crate::Elem;
#[derive(Debug, Clone)]
pub struct PuzzleData {
pub width: usize,
pub grid: Vec<Elem>,
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self {
width: s.find('\n').unwrap(),
grid: s
.bytes()
.filter(|&b| b != b'\n')
.map(|b| match b {
b'.' => Elem::Empty,
b'E' => Elem::Unit(true, 200),
b'G' => Elem::Unit(false, 200),
_ => Elem::Wall,
})
.collect(),
}
}
}
}
Star 1
Play rounds until there are only elves or only goblins left.
In each round store the positions of the units in reading order. Then, for every unit in turn, do a breadth first search to find a potential attack target, move one step towards the target if applicable and attack an opponent if in range after moving.
The play method’s arguments elf_attack_power and short_cut are for the second part. In the first part, they are set to 3 and false 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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Elem {
Wall,
Empty,
/// the first value is true for elves and false for goblins
Unit(bool, u32),
}
/// deltas to adjacents in reading order
pub const D: [(isize, isize); 4] = [(0, -1), (-1, 0), (1, 0), (0, 1)];
pub fn adjacents(grid: &[Elem], width: usize, p: usize) -> impl Iterator<Item = usize> + '_ {
let (x, y) = (p % width, p / width);
D.iter()
.map(move |&(dx, dy)| (x.wrapping_add_signed(dx), y.wrapping_add_signed(dy)))
.filter(move |&(x, y)| x < width && y < grid.len() / width)
.map(move |(x, y)| x + width * y)
}
pub fn opponents(
grid: &[Elem],
width: usize,
p: usize,
elf: bool,
) -> impl Iterator<Item = usize> + '_ {
adjacents(grid, width, p).filter(move |&p| matches!(grid[p], Elem::Unit(t, _) if t != elf))
}
pub fn play(data: &PuzzleData, elf_attack_power: u32, short_cut: bool) -> Option<SolType> {
let PuzzleData { width, mut grid } = data.to_owned();
// sum hit points for elves and goblins
let mut hps = grid.iter().fold([0, 0], |hps, e| match e {
Elem::Unit(false, hp) => [hps[0] + hp, hps[1]],
Elem::Unit(true, hp) => [hps[0], hps[1] + hp],
_ => hps,
});
let attack_powers = [3, elf_attack_power];
for r in 0.. {
// get all units in reading order
let units = grid
.iter()
.cloned()
.enumerate()
.filter_map(|(p, e)| match e {
Elem::Unit(_, _) => Some(p),
_ => None,
})
.collect::<Vec<_>>();
for mut p0 in units {
// get current unit (if it is still alive)
let Elem::Unit(elf, _) = grid[p0] else {
continue;
};
if hps[(!elf) as usize] == 0 {
// no targets -> return
return Some(hps[elf as usize] as SolType * r);
}
// BFS to targets
let mut parents = HashMap::new();
let mut queue = VecDeque::from([(0, p0)]);
let mut t = usize::MAX; // target
let mut t_d = usize::MAX; // distance to target
while let Some((d, p)) = queue.pop_front() {
if d > t_d {
// distance is larger than distance to target found so far
break;
}
if opponents(&grid, width, p, elf).next().is_some() {
// potential target, choose if its position is less than
// position of target found so far
t = t.min(p);
t_d = d;
}
// add adjacents
for adjacent in adjacents(&grid, width, p).filter(|&p| grid[p] == Elem::Empty) {
if let Entry::Vacant(v) = parents.entry(adjacent) {
v.insert(p);
queue.push_back((d + 1, adjacent));
}
}
}
if t == usize::MAX {
// no targets found
continue;
}
if t != p0 {
// move
// (best path to target is automatically chosen by order in which
// adjacents are enqueued in BFS)
let mut parent = *parents.get(&t).unwrap();
while parent != p0 {
(t, parent) = (parent, *parents.get(&parent).unwrap());
}
grid[t] = grid[p0];
grid[p0] = Elem::Empty;
p0 = t;
}
// attack opponent if applicable
if let Some((p, hp)) = opponents(&grid, width, p0, elf)
.map(|p| {
let Elem::Unit(_, hp) = grid[p] else {
unreachable!()
};
(p, hp)
})
.min_by_key(|(_, hp)| *hp)
{
if hp <= attack_powers[elf as usize] {
if short_cut && !elf {
// an elf just died
return None;
}
grid[p] = Elem::Empty;
hps[(!elf) as usize] -= hp;
} else {
grid[p] = Elem::Unit(!elf, hp - attack_powers[elf as usize]);
hps[(!elf) as usize] -= attack_powers[elf as usize];
}
}
}
}
unreachable!()
}
pub fn star_1(data: &PuzzleData) -> SolType {
play(data, 3, false).unwrap()
}
Star 2
Repeat algorithm from first part with increasing elf attack power until the attack power is large enough so that no elf dies. Setting the short_cut parameter to true stops simulation as soon as an elf dies to speed-up simulation time.
1
2
3
4
5
6
pub fn star_2(data: &PuzzleData) -> SolType {
(4..)
.filter_map(|elf_attack_power| play(data, elf_attack_power, true))
.next()
.unwrap()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#[cfg(test)]
mod tests {
use super::*;
const CONTENT_1: &str = r#"#######
#.G...#
#...EG#
#.#.#G#
#..G#E#
#.....#
#######
"#;
const CONTENT_2: &str = r#"#######
#G..#E#
#E#E.E#
#G.##.#
#...#E#
#...E.#
#######
"#;
const CONTENT_3: &str = r#"#######
#E..EG#
#.#G.E#
#E.##E#
#G..#.#
#..E#.#
#######
"#;
const CONTENT_4: &str = r#"#######
#E.G#.#
#.#G..#
#G.#.G#
#G..#.#
#...E.#
#######
"#;
const CONTENT_5: &str = r#"#######
#.E...#
#.#..G#
#.###.#
#E#G#G#
#...#G#
#######
"#;
const CONTENT_6: &str = r#"#########
#G......#
#.E.#...#
#..##..G#
#...##..#
#...#...#
#.G...G.#
#.....G.#
#########
"#;
const CONTENT_EXP_STAR_1: &[(&str, usize)] = &[
(CONTENT_1, 27_730),
(CONTENT_2, 36_334),
(CONTENT_3, 39_514),
(CONTENT_4, 27_755),
(CONTENT_5, 28_944),
(CONTENT_6, 18_740),
];
const CONTENT_EXP_STAR_2: &[(&str, usize)] = &[
(CONTENT_1, 4_988),
(CONTENT_3, 31_284),
(CONTENT_4, 3_478),
(CONTENT_5, 6_474),
(CONTENT_6, 1_140),
];
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT_1);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
for &(content, exp) in CONTENT_EXP_STAR_1 {
assert_eq!(exp, star_1(&content.into()));
}
}
#[test]
pub fn test_star_2() {
for &(content, exp) in CONTENT_EXP_STAR_2 {
assert_eq!(exp, star_2(&content.into()));
}
}
}
Day 16: Chronal Classification
Rust solution to AoC|2018|16.
Figure out which code corresponds to which operation.
Input
My solution for input parsing is neither elegant nor concise… It works.
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
pub mod input {
#[derive(Debug, PartialEq, Eq)]
pub struct PuzzleData(
pub Vec<([usize; 4], [usize; 4], [usize; 4])>,
pub Vec<[usize; 4]>,
);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let (a, b) = s.split_once("\n\n\n\n").unwrap();
Self(
a.split("\n\n")
.map(|s| {
let mut lines = s.lines();
(
lines
.next()
.and_then(|l| l.strip_prefix("Before: ["))
.and_then(|l| l.strip_suffix(']'))
.unwrap()
.split(", ")
.map(|v| v.parse().unwrap())
.enumerate()
.fold([0; 4], |mut b, (k, v)| {
b[k] = v;
b
}),
lines
.next()
.unwrap()
.split(' ')
.map(|v| v.parse().unwrap())
.enumerate()
.fold([0; 4], |mut b, (k, v)| {
b[k] = v;
b
}),
lines
.next()
.and_then(|l| l.strip_prefix("After: ["))
.and_then(|l| l.strip_suffix(']'))
.unwrap()
.split(", ")
.map(|v| v.parse().unwrap())
.enumerate()
.fold([0; 4], |mut b, (k, v)| {
b[k] = v;
b
}),
)
})
.collect(),
b.lines()
.map(|l| {
l.split(' ').map(|v| v.parse().unwrap()).enumerate().fold(
[0; 4],
|mut b, (k, v)| {
b[k] = v;
b
},
)
})
.collect(),
)
}
}
}
Star 1
Straightforward. For each before - operation - after triplet, count the number of operations that possibly match. If it is at least three, count it for the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
pub enum OpCode {
Addr,
Addi,
Mulr,
Muli,
Banr,
Bani,
Borr,
Bori,
Setr,
Seti,
Gtir,
Gtri,
Gtrr,
Eqir,
Eqri,
Eqrr,
}
impl OpCode {
pub const OPCODES: [OpCode; 16] = [
Self::Addr,
Self::Addi,
Self::Mulr,
Self::Muli,
Self::Banr,
Self::Bani,
Self::Borr,
Self::Bori,
Self::Setr,
Self::Seti,
Self::Gtir,
Self::Gtri,
Self::Gtrr,
Self::Eqir,
Self::Eqri,
Self::Eqrr,
];
pub fn exec(&self, params: &[usize], mut registers: [usize; 4]) -> [usize; 4] {
registers[params[2]] = match self {
OpCode::Addr => registers[params[0]] + registers[params[1]],
OpCode::Addi => registers[params[0]] + params[1],
OpCode::Mulr => registers[params[0]] * registers[params[1]],
OpCode::Muli => registers[params[0]] * params[1],
OpCode::Banr => registers[params[0]] & registers[params[1]],
OpCode::Bani => registers[params[0]] & params[1],
OpCode::Borr => registers[params[0]] | registers[params[1]],
OpCode::Bori => registers[params[0]] | params[1],
OpCode::Setr => registers[params[0]],
OpCode::Seti => params[0],
OpCode::Gtir => (params[0] > registers[params[1]]) as _,
OpCode::Gtri => (registers[params[0]] > params[1]) as _,
OpCode::Gtrr => (registers[params[0]] > registers[params[1]]) as _,
OpCode::Eqir => (params[0] == registers[params[1]]) as _,
OpCode::Eqri => (registers[params[0]] == params[1]) as _,
OpCode::Eqrr => (registers[params[0]] == registers[params[1]]) as _,
};
registers
}
}
pub fn star_1(PuzzleData(ops, _): &PuzzleData) -> SolType {
ops.iter()
.filter(|&(before, op, after)| {
OpCode::OPCODES
.iter()
.filter(|oc| oc.exec(&op[1..], *before) == *after)
.count()
>= 3
})
.count()
}
Star 2
First build a map of operation codes to operations, then execute the code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
pub fn star_2(PuzzleData(ops, code): &PuzzleData) -> SolType {
let mut map = [true; OpCode::OPCODES.len() * OpCode::OPCODES.len()];
for (before, op, after) in ops {
let num = op[0];
for idx in 0..OpCode::OPCODES.len() {
map[num + OpCode::OPCODES.len() * idx] = map[num + OpCode::OPCODES.len() * idx]
&& OpCode::OPCODES[idx].exec(&op[1..], *before) == *after;
}
}
let mut settled = [usize::MAX; OpCode::OPCODES.len()];
while !settled.iter().all(|&s| s != usize::MAX) {
for num in 0..OpCode::OPCODES.len() {
if settled[num] < usize::MAX {
// already settled
continue;
}
let mut candidates =
(0..OpCode::OPCODES.len()).filter(|idx| map[num + OpCode::OPCODES.len() * idx]);
let idx = candidates.next().unwrap(); // first candidate should always exist
if candidates.next().is_some() {
// more than one match
continue;
}
settled[num] = idx;
for other_num in (0..OpCode::OPCODES.len()).filter(|&other_num| other_num != num) {
map[other_num + OpCode::OPCODES.len() * settled[num]] = false;
}
}
}
// execute code
code.iter().fold([0; 4], |registers, op| {
OpCode::OPCODES[settled[op[0]]].exec(&op[1..], registers)
})[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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Before: [3, 2, 1, 1]
9 2 1 2
After: [3, 2, 2, 1]
0 1 2 3
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
assert_eq!(
PuzzleData(
vec![([3, 2, 1, 1], [9, 2, 1, 2], [3, 2, 2, 1])],
vec![[0, 1, 2, 3]]
),
data
);
}
}
Day 17: Reservoir Research
Rust solution to AoC|2018|17.
Figure out how water flows through ground of sand with veins of clay.
Input
The input describes horizontal and vertical lines of clay tiles. Those are parsed into a HashMap with coordinates as key and type of ground as values (during input parsing, only clay: '#')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
pub mod input {
use std::collections::HashMap;
#[derive(Debug, Clone)]
pub struct Ground {
pub grid: HashMap<(isize, isize), u8>,
pub y_mn: isize,
pub y_mx: isize,
}
impl From<&str> for Ground {
/// parse the puzzle input
fn from(s: &str) -> Self {
s.lines()
.map(|l| l.split_once(", ").unwrap())
.map(|(a, bs)| {
bs[2..]
.split_once("..")
.map(|(b_1, b_2)| {
(
a.as_bytes()[0],
a[2..].parse().unwrap(),
b_1.parse().unwrap()..=b_2.parse().unwrap(),
)
})
.unwrap()
})
.flat_map(|(coord_a, a, bs)| {
bs.map(move |b| match coord_a {
b'x' => (a, b),
b'y' => (b, a),
_ => panic!(),
})
})
.fold(
Self {
grid: HashMap::new(),
y_mn: isize::MAX,
y_mx: isize::MIN,
},
|mut ground, (x, y)| {
ground.set((x, y), Self::CLAY);
ground.y_mn = ground.y_mn.min(y);
ground.y_mx = ground.y_mx.max(y + 1);
ground
},
)
}
}
}
Solution
The solution is realized with a recursive function fill_ground (recursion is indirect: fill_ground calls fill_horizontal which calls fill_ground again)
The fill_ground function first lets water flow down until either clay or water at rest is reached.
Then water expands to the right and to the left (implemented in fill_horizontal) until clay is reached or an overflow occurs; overflows are handled by recursive calls of fill_ground.
If clay is found to the left and to the right, water is at rest at that layer and the layer just above is processed next.
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
impl Ground {
const CLAY: u8 = b'#';
const SAND: u8 = b'.';
const WATER_FLOW: u8 = b'*';
const WATER_REST: u8 = b'~';
pub fn set(&mut self, p: (isize, isize), b: u8) {
self.grid.insert(p, b);
}
pub fn get(&self, p: &(isize, isize)) -> u8 {
*self.grid.get(p).unwrap_or(&Self::SAND)
}
pub fn get_or_insert(&mut self, p: (isize, isize), default: u8) -> u8 {
*self.grid.entry(p).or_insert(default)
}
pub fn count(&self) -> (usize, usize) {
self.grid
.iter()
.filter(|(&(_, y), &b)| {
y >= self.y_mn && y <= self.y_mx && b == Self::WATER_FLOW || b == Self::WATER_REST
})
.fold((0, 0), |(reached, rest), (_, &b)| match b {
Self::WATER_FLOW => (reached + 1, rest),
Self::WATER_REST => (reached + 1, rest + 1),
_ => unreachable!(),
})
}
}
fn fill_horizontal(ground: &mut Ground, (mut x, y): (isize, isize), d_x: isize) -> (isize, bool) {
let mut bound = false;
loop {
x += d_x;
let b = ground.get_or_insert((x, y), Ground::WATER_FLOW);
if b == Ground::WATER_REST {
break;
} else if b == Ground::CLAY {
bound = true;
break;
} else if y + 1 < ground.y_mx {
match ground.get(&(x, y + 1)) {
Ground::SAND => {
// overflow -> recurse
fill_ground(ground, (x, y));
break;
}
Ground::WATER_FLOW => break, // overflow already processed
Ground::WATER_REST | Ground::CLAY => (), // continue loop
_ => unreachable!(),
}
}
}
(x, bound)
}
pub fn fill_ground(ground: &mut Ground, (x, mut y): (isize, isize)) {
// sink until clay or water at rest is reached or out of range
loop {
if y + 1 >= ground.y_mx {
// out of range, return from function
return;
}
// mark position as water flowing if not yet seen
let b = ground.get_or_insert((x, y + 1), Ground::WATER_FLOW);
if b == Ground::CLAY || b == Ground::WATER_REST {
// clay or water at rest is reached
break;
}
y += 1;
}
// look left and right
while y >= ground.y_mn {
// mark position as water flowing
ground.set((x, y), Ground::WATER_FLOW);
let (x_r, bound_r) = fill_horizontal(ground, (x, y), 1);
let (x_l, bound_l) = fill_horizontal(ground, (x, y), -1);
if bound_l && bound_r {
// mark all as water at rest
for x in x_l + 1..x_r {
ground.set((x, y), Ground::WATER_REST);
}
// proceed to row above
y -= 1;
} else {
break;
}
}
}
pub fn star_1_2(ground: &Ground) -> SolType {
let mut ground = ground.clone();
ground.set((500, 0), Ground::WATER_FLOW);
fill_ground(&mut ground, (500, 0));
// count reached by water and water at rest
ground.count().into()
}
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
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashMap;
const CONTENT: &str = r#"x=495, y=2..7
y=7, x=495..501
x=501, y=3..7
x=498, y=2..4
x=506, y=1..2
x=498, y=10..13
x=504, y=10..13
y=13, x=498..504
"#;
#[test]
pub fn test_from() {
let data = Ground::from(CONTENT);
let mut exp = HashMap::new();
(2..=7).for_each(|y| {
exp.insert((495, y), Ground::CLAY);
});
(495..=501).for_each(|x| {
exp.insert((x, 7), Ground::CLAY);
});
(3..=7).for_each(|y| {
exp.insert((501, y), Ground::CLAY);
});
(2..=4).for_each(|y| {
exp.insert((498, y), Ground::CLAY);
});
(1..=2).for_each(|y| {
exp.insert((506, y), Ground::CLAY);
});
(10..=13).for_each(|y| {
exp.insert((498, y), Ground::CLAY);
});
(10..=13).for_each(|y| {
exp.insert((504, y), Ground::CLAY);
});
(498..=504).for_each(|x| {
exp.insert((x, 13), Ground::CLAY);
});
assert_eq!(exp, data.grid);
assert_eq!(1, data.y_mn);
assert_eq!(14, data.y_mx);
}
#[test]
pub fn test_star_1_2() {
let data = Ground::from(CONTENT);
assert_eq!(Solutions::from((57, 29)), star_1_2(&data));
}
}
Day 18: Settlers of The North Pole
Rust solution to AoC|2018|18.
Simulate lumber growth.
Input
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 grid: Vec<u8>,
pub width: usize,
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self {
grid: s.bytes().filter(|&b| b != b'\n').collect(),
width: s.find('\n').unwrap(),
}
}
}
}
Star 1
Simulate rounds straight forward…
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
const D: [(isize, isize); 8] = [
(1, 0),
(1, -1),
(0, -1),
(-1, -1),
(-1, 0),
(-1, 1),
(0, 1),
(1, 1),
];
pub fn adjacents(grid: &[u8], width: usize, x: usize, y: usize) -> impl Iterator<Item = u8> + '_ {
D.iter()
.map(move |&(dx, dy)| (x.wrapping_add_signed(dx), y.wrapping_add_signed(dy)))
.filter(move |&(x, y)| x < width && y < grid.len() / width)
.map(move |(x, y)| grid[x + width * y])
}
pub fn play_round(grid: &[u8], update: &mut Vec<u8>, width: usize) {
update.resize(grid.len(), 0);
for x in 0..width {
for y in 0..grid.len() / width {
update[x + width * y] = match grid[x + width * y] {
b'|' if adjacents(grid, width, x, y)
.filter(|&b| b == b'#')
.nth(2)
.is_some() =>
{
b'#'
}
b'.' if adjacents(grid, width, x, y)
.filter(|&b| b == b'|')
.nth(2)
.is_some() =>
{
b'|'
}
b'#' if adjacents(grid, width, x, y)
.fold([false; 2], |v, b| [v[0] || b == b'#', v[1] || b == b'|'])
.iter()
.any(|v| !v) =>
{
b'.'
}
v => v,
}
}
}
}
pub fn star_1(data: &PuzzleData) -> SolType {
let PuzzleData { width, mut grid } = data.to_owned();
let mut update = grid.clone();
// simulate 10 rounds
for _ in 0..10 {
play_round(&grid, &mut update, width);
(grid, update) = (update, grid);
}
// calculate resource value
grid.iter()
.fold([0, 0], |cnt, &b| {
[cnt[0] + (b == b'|') as usize, cnt[1] + (b == b'#') as usize]
})
.iter()
.product()
}
Star 2
Find a pattern which repeats to fast forward the simulation.
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: &PuzzleData) -> SolType {
let PuzzleData { width, mut grid } = data.to_owned();
let mut update = grid.clone();
const T: usize = 1_000_000_000;
// simulate rounds until pattern repeats
let mut seen = HashMap::from([(grid.clone(), 0)]);
let mut t = 0;
loop {
t += 1;
play_round(&grid, &mut update, width);
(grid, update) = (update, grid);
if let Some(t_prv) = seen.insert(grid.clone(), t) {
// fast forward
let dt = t - t_prv;
t += ((T - t) / dt) * dt;
break;
}
}
// simulate remaining rounds
for _ in t..T {
play_round(&grid, &mut update, width);
(grid, update) = (update, grid);
}
// calculate resource value
grid.iter()
.fold([0, 0], |cnt, &b| {
[cnt[0] + (b == b'|') as usize, cnt[1] + (b == b'#') as usize]
})
.iter()
.product()
}
Day 19: Go With The Flow
Rust solution to AoC|2018|19.
Reverse engineer op code programs
While the first part can be solved by just executing the op codes, the second part does not.
Reverse engineering the input, it turns out that the program first executes instructions to calculate a value in register 4 and then calculates the sum of all factors (including 1 and the value itself) that divide that value without remainder.
Hence, the solution is to run the program to calculate the value in register 4 and then calculate the sum of the factors without using the op code program.
The general structure of the op code program is as follows (this may vary in variations of the input, but my guess is that the variance is essentially in the values produced by the initialization and possibly the meaning of the registers):
| Instructions | Explanation |
|---|---|
|
Jump to initialization (instruction |
|
Main calculation loop |
|
Initialization of |
|
Skip to instruction |
|
More initialization of |
|
Reset |
The main calculation consists of two nested loops iterating over candidate factors dividing the value in r[4] without remainder.
The outer loop iterates over fac1 in 0..=r[4], initialized in instruction 1. The loop condition (fac1 <= r[4]) is checked in instructions 13..=15 which jump back to instruction 1 + 1 while looping.
The inner loop iterates over fac2 in 0..=r[4], initialized in instruction 2. The loop condition (fac2 <= r[4]) is checked in instructions 9..=11 which jump back to instruction 2 + 1 while looping.
Within the inner loop, fac1 is added to the result (r[0]) if fac1 * fac2 == d[4].
Once the outer loop terminates, instruction 16 moves the instruction pointer beyond the last instruction and thus ends the program
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
pub mod input {
use crate::OpCode;
#[derive(Debug, Clone)]
pub struct PuzzleData {
pub ip: usize,
pub ops: Vec<(OpCode, [usize; 3])>,
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let mut lines = s.lines();
Self {
ip: lines
.next()
.unwrap()
.strip_prefix("#ip ")
.unwrap()
.parse()
.unwrap(),
ops: lines
.map(|l| l.split(' '))
.map(|mut words| {
(
words.next().unwrap().into(),
[
words.next().unwrap().parse().unwrap(),
words.next().unwrap().parse().unwrap(),
words.next().unwrap().parse().unwrap(),
],
)
})
.collect(),
}
}
}
}
Star 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
pub fn solve(ip: usize, ops: &[(OpCode, [usize; 3])], v0: usize) -> SolType {
let mut registers = [0; 6];
registers[0] = v0;
// the op code initializes r[4] and then jumps to instruction 1
while registers[ip] != 1 {
let (code, params) = ops[registers[ip]];
registers = code.exec(¶ms, registers);
registers[ip] += 1;
}
// once instruction 1 is reached, the code calculates the sum of all factors of the
// value in r[4] including 1 and r[4] itself
let mut a = registers[4];
let mut b = 1;
let mut result = if a == b { a } else { a + b };
while a & 1 == 0 {
(a, b) = (a >> 1, b << 1);
result += if a == b { a } else { a + b };
}
let mut fac = 3;
while fac * fac < a {
while a % fac == 0 {
(a, b) = (a / fac, b * fac);
result += if a == b { a } else { a + b };
}
fac += 2;
}
result
}
#[cfg(feature = "simulate")]
pub fn run(ip: usize, ops: &[(OpCode, [usize; 3])]) -> [usize; 6] {
let mut registers = [0; 6];
while registers[ip] < ops.len() {
let (code, params) = ops[registers[ip]];
registers = code.exec(¶ms, registers);
registers[ip] += 1;
}
registers
}
#[cfg(feature = "simulate")]
pub fn star_1(PuzzleData { ip, ops }: &PuzzleData) -> SolType {
run(*ip, ops)[0]
}
#[cfg(not(feature = "simulate"))]
pub fn star_1(PuzzleData { ip, ops }: &PuzzleData) -> SolType {
solve(*ip, ops, 0)
}
Star 2
The solution for part 1 works for part 2 as well. The difference is the value put in register 4 in the first couple of instructions.
1
2
3
pub fn star_2(PuzzleData { ip, ops }: &PuzzleData) -> SolType {
solve(*ip, ops, 1)
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"#ip 0
seti 5 0 1
seti 6 0 2
addi 0 1 0
addr 1 2 3
setr 1 0 0
seti 8 0 4
seti 9 0 5
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
#[cfg(feature = "simulate")]
pub fn test_run() {
let PuzzleData { ip, ops } = PuzzleData::from(CONTENT);
assert_eq!([7, 5, 6, 0, 0, 9], run(ip, &ops));
}
}
Day 20: A Regular Map
Rust solution to AoC|2018|20.
Explore a map represented as all possible paths given as a regular expression.
Input
Process the regular expression recursively to obtain a HashSet with the location of all doors
I wonder whether it would be efficiently possible to obtain the result from the regular expression directly without mapping the grid. But since there is no guarantee that the paths described by the regular expression visit every door exactly once, that might get very complicated (any maybe it would not be easy even if every door was used exactly 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
pub mod input {
use std::collections::HashSet;
#[derive(Debug, PartialEq, Eq)]
pub struct Grid(pub HashSet<(isize, isize)>);
pub fn map_path(
path: &[u8],
(mut x, mut y): (isize, isize),
grid: &mut HashSet<(isize, isize)>,
) -> usize {
let mut pos = 0;
loop {
match path[pos] {
b'E' => {
grid.insert((x + 1, y));
x += 2
}
b'N' => {
grid.insert((x, y - 1));
y -= 2
}
b'W' => {
grid.insert((x - 1, y));
x -= 2
}
b'S' => {
grid.insert((x, y + 1));
y += 2
}
b'(' => loop {
pos += 1;
pos += map_path(&path[pos..], (x, y), grid);
if path[pos] == b')' {
break;
}
debug_assert_eq!(
b'|', path[pos],
"Unexpected delimiter {}",
path[pos] as char
);
},
b')' | b'$' | b'|' => return pos,
e => panic!("Unexpected character: {}", e as char),
}
pos += 1;
}
}
impl From<&str> for Grid {
fn from(path: &str) -> Self {
let mut grid = HashSet::new();
let len = map_path(&path.trim().as_bytes()[1..], (0, 0), &mut grid);
debug_assert_eq!(len, path.trim().len() - 2, "Input processing incomplete");
Self(grid)
}
}
}
Star 1
Breadth first traversal of the grid (any other traversal would be good here, since the complete grid is processed)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub const D: [(isize, isize); 4] = [(1, 0), (0, -1), (-1, 0), (0, 1)];
pub fn star_1(Grid(grid): &Grid) -> SolType {
let start = (0, 0);
let mut seen = HashSet::from([start]);
let mut queue = VecDeque::from([(0, start)]);
let mut d_max = 0;
while let Some((d, (x, y))) = queue.pop_front() {
d_max = d;
for (dx, dy) in D {
if grid.contains(&(x + dx, y + dy)) && seen.insert((x + 2 * dx, y + 2 * dy)) {
queue.push_back((d + 1, (x + 2 * dx, y + 2 * dy)));
}
}
}
d_max
}
Star 2
Breadth first traversal of the grid until limit is reached. Then subtract the number of doors used from the total number of doors. The number of doors used equals the number of rooms seen minus one, since the first room is not entered through any door.
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_2(Grid(grid): &Grid) -> SolType {
const D: [(isize, isize); 4] = [(1, 0), (0, -1), (-1, 0), (0, 1)];
let start = (0, 0);
let mut seen = HashSet::from([start]);
let mut queue = VecDeque::from([(0, start)]);
let threshold = 1000;
let mut room_count = 0;
while let Some((d, (x, y))) = queue.pop_front() {
if d >= threshold {
break;
}
room_count += 1;
for (dx, dy) in D {
if grid.contains(&(x + dx, y + dy)) && seen.insert((x + 2 * dx, y + 2 * dy)) {
queue.push_back((d + 1, (x + 2 * dx, y + 2 * dy)));
}
}
}
grid.len() - (room_count - 1) // the first room is not entered through any door
}
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
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashSet;
const CONTENT_1: &str = r#"^ENWWW(NEEE|SSE(EE|N))$"#;
const DOORS_1: [(isize, isize); 15] = [
(-3, 2),
(-1, 2),
(1, 2),
(-4, 1),
(-2, 1),
(1, 0),
(-4, -1),
(2, -1),
(-3, -2),
(-1, -2),
(1, -2),
(-4, -3),
(-3, -4),
(-1, -4),
(1, -4),
];
const CONTENT_2: &str = r#"^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$"#;
const DOORS_2: [(isize, isize); 24] = [
(1, 0),
(-4, -1),
(2, -1),
(4, -1),
(-3, -2),
(-1, -2),
(-4, -3),
(0, -3),
(2, -3),
(4, -3),
(-3, -4),
(1, -4),
(-4, 1),
(-2, 1),
(4, 1),
(-1, 2),
(1, 2),
(3, 2),
(-4, 3),
(0, 3),
(4, 3),
(-3, 4),
(-1, 4),
(3, 4),
];
#[test]
pub fn test_from() {
assert_eq!(Grid(HashSet::from(DOORS_1)), CONTENT_1.into());
assert_eq!(Grid(HashSet::from(DOORS_2)), CONTENT_2.into());
}
#[test]
pub fn test_star_1() {
assert_eq!(10, star_1(&CONTENT_1.into()));
assert_eq!(18, star_1(&CONTENT_2.into()));
}
}
Day 21: Chronal Conversion
Rust solution to AoC|2018|21.
Another bit of reverse engineering op codes.
One key observation is that the value in r[0] is only used in the last three instructions to compare against r[4] and move the instruction pointer beyond the last instruction if they are equal.
In the operations given in the input, integer division is performed by linear search over potential quotients until just before the product of the quotient and the divisor exceeds the dividend, which can obviously get prohibitively expensive. This is replaced in the reverse engineered code by simple division. The rest is essentially the operations from the input taken as they are.
Input
Copied from day 19.
Star 1
Setting r[0] to the first value that appears for r[4] is causes the program to terminate in the least number of steps.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
pub fn reverse_engineered(ops: &[(OpCode, [usize; 3])], stop_at_first: bool) -> SolType {
// constants
assert_eq!(
(
OpCode::Bori,
OpCode::Seti,
OpCode::Bani,
OpCode::Bani,
OpCode::Muli,
OpCode::Bani,
OpCode::Gtir,
OpCode::Muli,
),
(ops[6].0, ops[7].0, ops[8].0, ops[10].0, ops[11].0, ops[12].0, ops[13].0, ops[19].0)
);
let c6 = ops[6].1[1]; // bori
let c7 = ops[7].1[0]; // seti
let c8 = ops[8].1[1]; // bani
let c10 = ops[10].1[1]; // bani
let c11 = ops[11].1[1]; // muli
let c12 = ops[12].1[1]; // bani
let c13 = ops[13].1[0]; // gtir
let c19 = ops[19].1[1]; // muli
// init, 5
let mut d4 = 0;
let mut d5;
let mut d4s = HashSet::new();
let mut sol = usize::MAX;
loop {
// init, 6..=7
d5 = d4 | c6;
d4 = c7;
loop {
// update d4, 8..=12
d4 = (((d4 + (d5 & c8)) & c10) * c11) & c12;
// check, 13..=16
if c13 > d5 {
break;
}
// init d2 = 0, 17
// division, 18..=26
d5 /= c19;
// loop, 27
}
// check, 28..=30
// the program terminates if d4 == d0.
if d4s.insert(d4) {
// this is the first time this d4 is seen
sol = d4;
} else {
// the same d4 has been seen before,
// from here, no new solutions can appear
break;
}
if stop_at_first {
break;
}
}
sol
}
pub fn star_1(PuzzleData { ip, ops }: &PuzzleData) -> SolType {
assert_eq!(1, *ip);
reverse_engineered(ops, true)
}
Star 2
Setting r[0] to the last value that appears for r[4] before values start repeating causes the program to terminate in the highest number of steps.
1
2
3
4
pub fn star_2(PuzzleData { ip, ops }: &PuzzleData) -> SolType {
assert_eq!(1, *ip);
reverse_engineered(ops, false)
}
Day 22: Mode Maze
Rust solution to AoC|2018|22.
Cave rescue mission
Input
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, PartialEq, Eq)]
pub struct PuzzleData {
pub depth: usize,
pub target: (usize, usize),
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
s.trim()
.strip_prefix("depth: ")
.and_then(|s| s.split_once("\ntarget: "))
.map(|(depth, pos)| Self {
depth: depth.parse().unwrap(),
target: pos
.split_once(',')
.map(|(x, y)| (x.parse().unwrap(), y.parse().unwrap()))
.unwrap(),
})
.unwrap()
}
}
}
Star 1
Straight-forward calculation of erosion levels and then area types which equal risk 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Erosion {
w: usize,
h: usize,
data: Vec<usize>,
depth: usize,
target: (usize, usize),
}
impl Erosion {
pub const FAC_X: usize = 16_807;
pub const FAC_Y: usize = 48_271;
pub const M: usize = 20_183;
const INC: usize = 100;
pub fn new(depth: usize, target: (usize, usize)) -> Self {
let (w, h) = (target.0 + 1, target.1 + 1);
let data = vec![0; w * h];
let mut v = Self {
w,
h,
data,
depth,
target,
};
for y in 0..h {
for x in 0..w {
v.data[x + w * y] = v.calc(&v.data, w, (x, y));
}
}
v
}
fn calc(&self, data: &[usize], w: usize, (x, y): (usize, usize)) -> usize {
(self.depth
+ match (x, y) {
(x, 0) => Self::FAC_X * x,
(0, y) => Self::FAC_Y * y,
(x, y) if (x, y) != self.target => data[x - 1 + w * y] * data[x + w * (y - 1)],
_ => 0,
})
% Self::M
}
pub fn get(&mut self, (x, y): (usize, usize)) -> usize {
if x >= self.w || y >= self.h {
let w = if x >= self.w {
self.w.max(x + 1) + Self::INC
} else {
self.w
};
let h = if y >= self.h {
self.h.max(y + 1) + Self::INC
} else {
self.h
};
let mut data = vec![0; w * h];
for y in 0..self.h {
data[w * y..self.w + w * y]
.copy_from_slice(&self.data[self.w * y..self.w * (y + 1)]);
for x in self.w..w {
data[x + w * y] = self.calc(&data, w, (x, y));
}
}
for y in self.h..h {
for x in 0..w {
data[x + w * y] = self.calc(&data, w, (x, y));
}
}
self.w = w;
self.h = h;
self.data = data;
}
self.data[x + self.w * y]
}
}
pub fn star_1(&PuzzleData { depth, target }: &PuzzleData) -> SolType1 {
let mut e = Erosion::new(depth, target);
let (w, h) = (target.0 + 1, target.1 + 1);
(0..h)
.flat_map(|y| (0..w).map(move |x| (x, y)))
.map(|p| e.get(p) % 3)
.sum()
}
Star 2
The struct Erosion implements a grid which grows dynamically if elements out of bounds are read with the get function.
With this, a Dijkstra / A* like "shortest time first" traversal is implemented. No decrease key is required.
Adding the Manhattan distance to the target as a heuristic to the search (A* style), speeds up the algorithm by roughly a factor four.
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
const D: [(isize, isize); 4] = [(1, 0), (0, -1), (-1, 0), (0, 1)];
const EQUIP_NONE: u8 = 0;
const EQUIP_TORCH: u8 = 1;
const EQUIP_CLIMBING_GEAR: u8 = 2;
const TYPE_ROCKY: u8 = 0;
const TYPE_WET: u8 = 1;
const TYPE_NARROW: u8 = 2;
const TYPE_MAX: u8 = 3;
pub fn star_2(&PuzzleData { depth, target }: &PuzzleData) -> SolType1 {
let mut e = Erosion::new(depth, target);
let start = ((0, 0), EQUIP_TORCH);
let mut seen = HashMap::from([(start, (target.0 + target.1, 0))]);
let mut queue = BinaryHeap::from([(!(target.0 + target.1), !0, start)]);
while let Some((_, not_time, ((x, y), equip))) = queue.pop() {
if (x, y) == target {
if equip == EQUIP_TORCH {
return !not_time;
} else {
queue.push((not_time - 7, not_time - 7, ((x, y), EQUIP_TORCH)));
continue;
}
}
for (adj_x, adj_y) in D
.iter()
.map(|&(dx, dy)| (x.wrapping_add_signed(dx), y.wrapping_add_signed(dy)))
.filter(|&(x, y)| x < usize::MAX >> 1 && y < usize::MAX >> 1)
{
let adj_t = (e.get((adj_x, adj_y)) % TYPE_MAX as usize) as u8;
let (adj_time, adj_equip) = if (adj_t == TYPE_ROCKY && equip != EQUIP_NONE)
|| (adj_t == TYPE_WET && equip != EQUIP_TORCH)
|| (adj_t == TYPE_NARROW && equip != EQUIP_CLIMBING_GEAR)
{
// no need to change equipment to move to adjacent
(!not_time + 1, equip)
} else {
// change gear to the one that can be used in current and adjacent
let t = (e.get((x, y)) % TYPE_MAX as usize) as u8;
(
!not_time + 8,
match (t, adj_t) {
(TYPE_ROCKY, TYPE_WET) | (TYPE_WET, TYPE_ROCKY) => EQUIP_CLIMBING_GEAR,
(TYPE_WET, TYPE_NARROW) | (TYPE_NARROW, TYPE_WET) => EQUIP_NONE,
(TYPE_NARROW, TYPE_ROCKY) | (TYPE_ROCKY, TYPE_NARROW) => EQUIP_TORCH,
_ => unreachable!(),
},
)
};
let adj_weight = adj_time + target.0.max(adj_x) - target.0.min(adj_x)
+ target.1.max(adj_y)
- target.1.min(adj_y);
let prev_w_t = seen
.entry(((adj_x, adj_y), adj_equip))
.or_insert((usize::MAX, usize::MAX));
if (adj_weight, adj_time) < *prev_w_t {
*prev_w_t = (adj_weight, adj_time);
queue.push((!adj_weight, !adj_time, ((adj_x, adj_y), adj_equip)));
}
}
}
panic!("No solution!");
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"depth: 510
target: 10,10
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
assert_eq!(
PuzzleData {
depth: 510,
target: (10, 10)
},
data
);
}
#[test]
pub fn test_star_1() {
assert_eq!(114, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(45, star_2(&CONTENT.into()));
}
}
Day 23: Experimental Emergency Teleportation
Rust solution to AoC|2018|23.
One of the most difficult puzzles for me - not so much the coding part, but rather coming up with an idea…
Input
Parse the nanobots in Nanobot structs with their positions and radius'.
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
pub mod input {
/// Nanobot with 3D position and range
#[derive(PartialEq, Eq, Clone, Copy, Debug)]
pub struct Nanobot {
pub(crate) x: i64,
pub(crate) y: i64,
pub(crate) z: i64,
pub(crate) r: i64,
}
impl From<&str> for Nanobot {
/// Parse nanobot
///
/// # Examples
/// ```
/// # use mr_kaffee_2018_23::input::*;
/// let s = "pos=<10,20,30>, r=5";
/// let b = Nanobot::from(s);
/// println!("{:?}", b);
/// ```
fn from(s: &str) -> Self {
let mut parts = s.split(", ");
// parse position
let part_pos = parts.next().unwrap();
let mut pos = part_pos
.strip_prefix("pos=<")
.and_then(|pos| pos.strip_suffix('>'))
.map(|pos| pos.split(',').map(|c| c.parse().unwrap()))
.unwrap();
let x = pos.next().unwrap();
let y = pos.next().unwrap();
let z = pos.next().unwrap();
// parse radius
let r = parts
.next()
.and_then(|r| r.strip_prefix("r="))
.map(|r| r.parse().unwrap())
.unwrap();
Self { x, y, z, r }
}
}
#[derive(Debug, PartialEq, Eq)]
pub struct PuzzleData {
pub(crate) nanobots: Vec<Nanobot>,
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self {
nanobots: s.lines().map(Nanobot::from).collect(),
}
}
}
}
Star 1
Part 1 on straight forward.
1
2
3
4
5
6
7
8
9
10
pub fn star_1(data: &PuzzleData) -> usize {
// find bot with largest range
let bot = data.nanobots.iter().max_by_key(|bot| bot.r).unwrap();
// count bots in range of bot with largest range
data.nanobots
.iter()
.filter(|b| Node::leaf(b.x, b.y, b.z).is_seen_by(bot))
.count()
}
Star 2
The idea for part 2 is to search the space by cuboids. In each step, a cuboid is split in up to 8 smaller cuboids (two in each dimension), starting from one big cuboid containing all the nanobots' ranges. In each step, the cuboid which is seen by the largest number of nanobots is processed, if two cuboids are seen by the same number of nanobots, the one closer to origin is processed first.
Once a cuboid of size 1 is processed, we found the solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
/// Node -- a cuboid
#[derive(PartialEq, Eq, Clone, Copy, Debug, PartialOrd, Ord)]
pub struct Node {
x_mn: i64,
x_mx: i64,
y_mn: i64,
y_mx: i64,
z_mn: i64,
z_mx: i64,
}
impl Node {
/// create a leaf node (size = 1) at given position
pub fn leaf(x: i64, y: i64, z: i64) -> Self {
Self {
x_mn: x,
x_mx: x + 1,
y_mn: y,
y_mx: y + 1,
z_mn: z,
z_mx: z + 1,
}
}
/// create a node that contains the nanobot's range
pub fn bbox(bot: &Nanobot) -> Self {
Self::leaf(bot.x, bot.y, bot.z).extend_to_fit(bot)
}
/// extend this node to contain the nanobot's range and return the extended node
pub fn extend_to_fit(mut self, bot: &Nanobot) -> Self {
self.x_mn = std::cmp::min(self.x_mn, bot.x - bot.r);
self.x_mx = std::cmp::max(self.x_mx, bot.x + bot.r + 1);
self.y_mn = std::cmp::min(self.y_mn, bot.y - bot.r);
self.y_mx = std::cmp::max(self.y_mx, bot.y + bot.r + 1);
self.z_mn = std::cmp::min(self.z_mn, bot.z - bot.r);
self.z_mx = std::cmp::max(self.z_mx, bot.z + bot.r + 1);
self
}
/// check whether this node is seen by the given nanobot
pub fn is_seen_by(&self, bot: &Nanobot) -> bool {
if self.x_mx == self.x_mn || self.y_mx == self.y_mn || self.z_mx == self.z_mn {
return false;
}
let mut r = bot.r;
// x-coordinate
if bot.x - r >= self.x_mx || bot.x + r < self.x_mn {
return false;
} else if bot.x < self.x_mn || bot.x >= self.x_mx {
r -= std::cmp::min((self.x_mn - bot.x).abs(), (self.x_mx - 1 - bot.x).abs());
}
// y-coordinate
if bot.y - r >= self.y_mx || bot.y + r < self.y_mn {
return false;
} else if bot.x < self.x_mn || bot.x >= self.x_mx {
r -= std::cmp::min((self.y_mn - bot.y).abs(), (self.y_mx - 1 - bot.y).abs());
};
// z-coordinate
bot.z - r < self.z_mx && bot.z + r >= self.z_mn
}
/// get the distance to the origin (0, 0, 0) of this node
pub fn dist_to_origin(&self) -> u64 {
(if self.x_mn >= 0 {
self.x_mn
} else if self.x_mx < 0 {
1 - self.x_mx
} else {
0
} + if self.y_mn >= 0 {
self.y_mn
} else if self.y_mx < 0 {
1 - self.y_mx
} else {
0
} + if self.z_mn >= 0 {
self.z_mn
} else if self.z_mx < 0 {
1 - self.z_mx
} else {
0
}) as u64
}
/// check whether this node is a leaf node (size = 1)
pub fn is_leaf(&self) -> bool {
self.x_mx - self.x_mn == 1 && self.y_mx - self.y_mn == 1 && self.z_mx - self.z_mn == 1
}
/// split this node in (up to) 8 smaller nodes, two in every dimension (x, y, and z)
pub fn split(&self) -> Vec<Self> {
let mut splits = Vec::with_capacity(8);
let xs = [self.x_mn, (self.x_mn + self.x_mx) / 2, self.x_mx];
let ys = [self.y_mn, (self.y_mn + self.y_mx) / 2, self.y_mx];
let zs = [self.z_mn, (self.z_mn + self.z_mx) / 2, self.z_mx];
for (&x_mn, &x_mx) in xs.iter().zip(xs.iter().skip(1)).filter(|(mn, mx)| mx > mn) {
for (&y_mn, &y_mx) in ys.iter().zip(ys.iter().skip(1)).filter(|(mn, mx)| mx > mn) {
for (&z_mn, &z_mx) in zs.iter().zip(zs.iter().skip(1)).filter(|(mn, mx)| mx > mn) {
splits.push(Self {
x_mn,
x_mx,
y_mn,
y_mx,
z_mn,
z_mx,
});
}
}
}
splits
}
}
pub fn star_2(data: &PuzzleData) -> u64 {
// start from bounding box
let root = data
.nanobots
.iter()
.fold(None as Option<Node>, |n, b| {
Some(n.map_or_else(|| Node::bbox(b), |n| n.extend_to_fit(b)))
})
.unwrap();
// init heap
let mut heap = BinaryHeap::new();
// nodes on the heap are triples of
// - number of bots that see the node (largest first)
// - distance to origin (inverted -> smallest first)
// - the actual node (cuboid)
// if a node of size 1 is found, no later node can be better, since
// it will either be seen by less bots or by the same number of bots
// in which case it will be farther away from origin
heap.push((data.nanobots.len(), !root.dist_to_origin(), root));
while let Some((_, d, node)) = heap.pop() {
if node.is_leaf() {
// first leaf found is position seen by the largest possible number of nanobots
// (with ties broken by closest distance to the origin)
return !d;
}
for split in node.split() {
let n = data.nanobots.iter().filter(|b| split.is_seen_by(b)).count();
heap.push((n, !split.dist_to_origin(), split));
}
}
unreachable!("No solution found");
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = "pos=<10,12,12>, r=2\n\
pos=<12,14,12>, r=2\n\
pos=<16,12,12>, r=4\n\
pos=<14,14,14>, r=6\n\
pos=<50,50,50>, r=200\n\
pos=<10,10,10>, r=5";
const NANOBOTS: &[Nanobot] = &[
Nanobot {
x: 10,
y: 12,
z: 12,
r: 2,
},
Nanobot {
x: 12,
y: 14,
z: 12,
r: 2,
},
Nanobot {
x: 16,
y: 12,
z: 12,
r: 4,
},
Nanobot {
x: 14,
y: 14,
z: 14,
r: 6,
},
Nanobot {
x: 50,
y: 50,
z: 50,
r: 200,
},
Nanobot {
x: 10,
y: 10,
z: 10,
r: 5,
},
];
fn exp_data() -> PuzzleData {
PuzzleData {
nanobots: NANOBOTS.into(),
}
}
#[test]
fn test_puzzle_data_from_str() {
let data = PuzzleData::from(CONTENT);
assert_eq!(exp_data(), data);
}
#[test]
fn test_node_is_seen_by() {
let node = Node::leaf(12, 12, 12);
assert!(!node.is_seen_by(&NANOBOTS[5]));
assert_eq!(
5,
NANOBOTS.iter().filter(|bot| node.is_seen_by(bot)).count()
);
}
#[test]
fn test_node_split() {
let node = Node {
x_mn: 0,
x_mx: 10,
y_mn: 0,
y_mx: 1,
z_mn: 0,
z_mx: 1,
};
assert_eq!(
vec![
Node {
x_mn: 0,
x_mx: 5,
..node
},
Node {
x_mn: 5,
x_mx: 10,
..node
}
],
node.split()
);
}
#[test]
fn test_star_2() {
assert_eq!(36, star_2(&exp_data()));
}
}
Day 24: Immune System Simulator 20XX
Rust solution to AoC|2018|24.
Simulate combats in a reindeer’s immune system.
Input
Tedious input parsing
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
pub mod input {
use std::collections::HashSet;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Group<'a> {
pub n: u64,
pub hp: u64,
pub weak: HashSet<&'a str>,
pub immune: HashSet<&'a str>,
pub damage: u64,
pub damage_type: &'a str,
pub initiative: u64,
}
impl<'a> From<&'a str> for Group<'a> {
fn from(s: &'a str) -> Self {
let mut words = s
.split(&[' ', '(', ')', ',', ';'])
.filter(|w| !w.is_empty());
let n = words.next().unwrap().parse().unwrap(); // <n>
let hp = words.nth(3).unwrap().parse().unwrap(); // units each with <hp>
words.nth(1); // hit points
let mut weak = HashSet::new();
let mut immune = HashSet::new();
let mut set = &mut weak;
loop {
match words.next().unwrap() {
"weak" => {
words.next(); // to
set = &mut weak;
}
"immune" => {
words.next(); // to
set = &mut immune;
}
"with" => break,
w => _ = set.insert(w),
};
}
let damage = words.nth(4).unwrap().parse().unwrap(); // an attack that does <damage>
let damage_type = words.next().unwrap(); // <damage_type>
let initiative = words.nth(3).unwrap().parse().unwrap(); // damage at initiative <initiative>
Self {
n,
hp,
weak,
immune,
damage,
damage_type,
initiative,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Armies<'a>(pub [Vec<Group<'a>>; 2]);
impl Armies<'_> {
pub const DEFENSE: usize = 0;
pub const INFECT: usize = 1;
}
impl<'a> From<&'a str> for Armies<'a> {
fn from(s: &'a str) -> Self {
let (immune_system, infection) = s.split_once("\n\n").unwrap();
let immune_system = immune_system.strip_prefix("Immune System:\n").unwrap();
let infection = infection.strip_prefix("Infection:\n").unwrap();
Self([
immune_system.lines().map(Group::from).collect(),
infection.lines().map(Group::from).collect(),
])
}
}
}
Star 1
Simulate combat and make sure you get the orderings correctly for target selections and attack.
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
/// returns an `Ok` variant with the number of units left in each army
/// if the combat ends with a winner and an `Err` variant with the current status
/// of the armies if the combat ends in an endless loop
pub fn solve(mut armies: [Vec<Group>; 2], boost: u64) -> Result<[u64; 2], [Vec<Group>; 2]> {
// apply boost
if boost > 0 {
for g in &mut armies[Armies::DEFENSE] {
g.damage += boost;
}
}
while !armies[Armies::DEFENSE].is_empty() && !armies[Armies::INFECT].is_empty() {
let mut groups = (0..2)
.flat_map(|a| (0..armies[a].len()).map(move |g| (a, g)))
.collect::<Vec<_>>();
// order for target selection
groups.sort_unstable_by_key(|&(a, g)| {
let grp = &armies[a][g];
(!(grp.n * grp.damage), !grp.initiative)
});
// select targets
let mut targets = [
vec![None; armies[Armies::DEFENSE].len()],
vec![None; armies[Armies::INFECT].len()],
];
let mut selected = [
vec![false; armies[Armies::DEFENSE].len()],
vec![false; armies[Armies::INFECT].len()],
];
for &(a, g) in &groups {
let grp = &armies[a][g];
let a_tar = (a + 1) & 1;
if let Some(g_tar) = (0..armies[a_tar].len())
.filter(|&g_tar| !selected[a_tar][g_tar])
.filter(|&g_tar| !armies[a_tar][g_tar].immune.contains(grp.damage_type))
.max_by_key(|&g_tar| {
let tar = &armies[a_tar][g_tar];
(
tar.weak.contains(grp.damage_type),
tar.n * tar.damage,
tar.initiative,
)
})
{
targets[a][g] = Some(g_tar);
selected[a_tar][g_tar] = true;
}
}
// order for attack
groups.sort_unstable_by_key(|&(a, g)| !armies[a][g].initiative);
// attack
let mut total_kills = 0;
for (a, g) in groups {
let grp = &armies[a][g];
if grp.n == 0 {
continue;
}
let (damage, damage_type) = (grp.damage * grp.n, grp.damage_type);
let a_tar = (a + 1) & 1;
if let Some(g_tar) = targets[a][g] {
let tar = &mut armies[a_tar][g_tar];
let damage = damage * (tar.weak.contains(damage_type) as u64 + 1);
let kills = tar.n.min(damage / tar.hp);
tar.n -= kills;
total_kills += kills;
}
}
if total_kills == 0 {
// life-lock
return Err(armies);
}
// remove groups that have no units left
for army in &mut armies {
for k_g in (0..army.len()).rev() {
if army[k_g].n == 0 {
army.swap_remove(k_g);
}
}
}
}
Ok(armies.map(|army| army.iter().map(|group| group.n).sum()))
}
pub fn star_1(Armies(armies): &Armies) -> SolType {
solve(armies.to_owned(), 0).unwrap().iter().sum()
}
Star 2
Do a binary search to find the lowest boost that allows the immune system to win the combat.
This requires to add a test for combats that end in endless loops, i.e., fights within a combat that do not cause any units to be killed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn star_2(Armies(armies): &Armies) -> SolType {
let (mut boost_l, mut boost_h) = (0, 32);
// double boost until defense wins
let mut res = solve(armies.to_owned(), boost_h).map(|r| r[0]).unwrap_or(0);
while res == 0 {
(boost_l, boost_h) = (boost_h, boost_h << 1);
res = solve(armies.to_owned(), boost_h).map(|r| r[0]).unwrap_or(0);
}
// half interval until smallest possible boost is found
while boost_h - boost_l > 1 {
let boost_m = (boost_h + boost_l) / 2;
match solve(armies.to_owned(), boost_m).map(|r| r[0]).unwrap_or(0) {
0 => boost_l = boost_m,
res_ => (boost_h, res) = (boost_m, res_),
}
}
res
}
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
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashSet;
const CONTENT: &str = r#"Immune System:
17 units each with 5390 hit points (weak to radiation, bludgeoning) with an attack that does 4507 fire damage at initiative 2
989 units each with 1274 hit points (immune to fire; weak to bludgeoning, slashing) with an attack that does 25 slashing damage at initiative 3
Infection:
801 units each with 4706 hit points (weak to radiation) with an attack that does 116 bludgeoning damage at initiative 1
4485 units each with 2961 hit points (immune to radiation; weak to fire, cold) with an attack that does 12 slashing damage at initiative 4
"#;
#[test]
pub fn test_from() {
let data = Armies::from(CONTENT);
let exp = Armies([
vec![
Group {
n: 17,
hp: 5_390,
weak: HashSet::from(["radiation", "bludgeoning"]),
immune: HashSet::new(),
damage: 4_507,
damage_type: "fire",
initiative: 2,
},
Group {
n: 989,
hp: 1_274,
weak: HashSet::from(["bludgeoning", "slashing"]),
immune: HashSet::from(["fire"]),
damage: 25,
damage_type: "slashing",
initiative: 3,
},
],
vec![
Group {
n: 801,
hp: 4_706,
weak: HashSet::from(["radiation"]),
immune: HashSet::from([]),
damage: 116,
damage_type: "bludgeoning",
initiative: 1,
},
Group {
n: 4_485,
hp: 2_961,
weak: HashSet::from(["fire", "cold"]),
immune: HashSet::from(["radiation"]),
damage: 12,
damage_type: "slashing",
initiative: 4,
},
],
]);
assert_eq!(exp, data);
}
#[test]
pub fn test_star_1() {
assert_eq!(5_216, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(51, star_2(&CONTENT.into()));
}
}
Day 25: Four-Dimensional Adventure
Rust solution to AoC|2018|25.
Group 4D points in constellations
Input
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(pub Vec<[i64; 4]>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(
s.trim()
.lines()
.map(|l| {
l.split(',').enumerate().fold([0; 4], |mut p, (k, v)| {
p[k] = v.parse().unwrap();
p
})
})
.collect(),
)
}
}
}
Star 1
Iterate through points.
For each point, find the constellations the point belongs to.
If there are no constellations, the point starts a new constellation.
If a point belongs to exactly one constellation, the point is added to that constellation.
If the point belongs to more than one constellation, all constellations the point belongs to are merged into one bigger constellation. This is realized by removing all but one constellations and add the points to the remaining constellation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
pub fn star_1(PuzzleData(points): &PuzzleData) -> SolType {
points
.iter()
.fold::<Vec<Vec<[i64; 4]>>, _>(vec![], |mut cs, &pt| {
// determine which constellations point is a member of
let member = cs
.iter()
.enumerate()
.filter(|(_, c)| {
c.iter().any(|c_pt| {
pt.iter()
.zip(c_pt.iter())
.map(|(a, b)| (a - b).abs())
.sum::<i64>()
<= 3
})
})
.map(|(k, _)| k)
.collect::<Vec<_>>();
if member.is_empty() {
// new constellation
cs.push(vec![pt]);
} else {
for &k in member[1..].iter().rev() {
// more then one constellation
// => merge all constellations into one
let c = cs.swap_remove(k);
cs[member[0]].extend(c);
}
// add point to existing constellation
cs[member[0]].push(pt);
}
cs
})
.len()
}
Test
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"-1,2,2,0
0,0,2,-2
0,0,0,-2
-1,2,0,0
-2,-2,-2,2
3,0,2,-1
-1,3,2,2
-1,0,-1,0
0,2,1,-2
3,0,0,0
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
assert_eq!(4, star_1(&CONTENT.into()));
}
}