Day 1: Report Repair
Rust solution to AoC|2020|1.
Find numbers that sum up to 2020 from a list
Input
Just a plain list of numbers
1
2
3
4
5
6
7
8
9
10
11
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<usize>);
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self(s.lines().map(str::parse).collect::<Result<_, _>>().unwrap())
}
}
}
Star 1
The flat_map function comes in handy
1
2
3
4
5
6
7
pub fn star_1(PuzzleData(list): &PuzzleData) -> SolType1 {
(0..list.len() - 1)
.flat_map(|k_1| (k_1 + 1..list.len()).map(move |k_2| (list[k_1], list[k_2])))
.find(|(a, b)| a + b == 2020)
.map(|(a, b)| a * b)
.unwrap()
}
Star 2
The three number case is a simple extension. There is obviously room for optimizations: if the first two numbers exceed 2020, there is no point scanning through the 3rd, but … who cares
1
2
3
4
5
6
7
8
9
10
11
pub fn star_2(PuzzleData(list): &PuzzleData) -> SolType2 {
(0..list.len() - 2)
.flat_map(|k_1| {
(k_1 + 1..list.len() - 1).flat_map(move |k_2| {
(k_2 + 1..list.len()).map(move |k_3| (list[k_1], list[k_2], list[k_3]))
})
})
.find(|(a, b, c)| a + b + c == 2020)
.map(|(a, b, c)| a * b * c)
.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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"1721
979
366
299
675
1456
"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(514_579, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(241_861_950, star_2(&data));
}
}
Day 2: Password Philosophy
Rust solution to AoC|2020|2.
Check password validity
Input
This is the most difficult part for today.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
pub mod input {
#[derive(Debug)]
pub struct PuzzleData<'a>(pub Vec<((usize, usize), u8, &'a [u8])>);
impl<'a> From<&'a str> for PuzzleData<'a> {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self(
s.lines()
.map(|l| l.split_once(": ").unwrap())
.map(|(r, p)| {
(
r[..r.len() - 2]
.split_once('-')
.map(|(a, b)| (a.parse().unwrap(), b.parse().unwrap()))
.unwrap(),
r.as_bytes()[r.len() - 1],
p.as_bytes(),
)
})
.collect(),
)
}
}
}
Star 1
Count occurrence of given letter and check it is in range
1
2
3
4
5
6
pub fn star_1(PuzzleData(passwords): &PuzzleData) -> SolType1 {
passwords
.iter()
.filter(|&&((mn, mx), r, p)| (mn..=mx).contains(&p.iter().filter(|&&b| b == r).count()))
.count()
}
Star 2
Exactly one of two is done with XOR
1
2
3
4
5
6
pub fn star_2(PuzzleData(passwords): &PuzzleData) -> SolType2 {
passwords
.iter()
.filter(|&&((a, b), r, p)| (p[a - 1] == r) ^ (p[b - 1] == r))
.count()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc
"#;
#[test]
pub fn test_from() {
let PuzzleData(passwords) = PuzzleData::from(CONTENT);
assert_eq!(
vec![
((1, 3), b'a', b"abcde" as &[u8]),
((1, 3), b'b', b"cdefg"),
((2, 9), b'c', b"ccccccccc")
],
passwords
);
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(2, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(1, star_2(&data));
}
}
Day 3: Toboggan Trajectory
Rust solution to AoC|2020|3.
Avoid (or rather count) trees on toboggan trajectories
Input
Standard grid of bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub mod input {
#[derive(Debug)]
pub struct PuzzleData {
pub grid: Vec<u8>,
pub w: usize,
}
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
let w = s.find('\n').unwrap();
let grid = s.bytes().filter(|&b| b != b'\n').collect();
Self { grid, w }
}
}
}
Star 1
Solution is refactored into a function check_slope which takes the slope as an argument to be re-usable for part 2.
1
2
3
4
5
6
7
8
9
10
pub fn check_slope(PuzzleData { grid, w }: &PuzzleData, (d_x, d_y): (usize, usize)) -> SolType {
(d_y..grid.len() / w)
.step_by(d_y)
.filter(|&y| grid[(d_x * y / d_y) % w + w * y] == b'#')
.count()
}
pub fn star_1(data: &PuzzleData) -> SolType {
check_slope(data, (3, 1))
}
Star 2
Not really anything added compared to part 1.
1
2
3
4
5
6
pub fn star_2(data: &PuzzleData) -> SolType {
[(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)]
.iter()
.map(|&d| check_slope(data, d))
.product()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#
"#;
#[test]
pub fn test_from() {
let data = PuzzleData::from(CONTENT);
assert_eq!(11, data.w);
assert_eq!(121, data.grid.len());
}
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(7, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(336, star_2(&data));
}
}
Day 4: Passport Processing
Rust solution to AoC|2020|4.
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
pub mod input {
use crate::Passport;
#[derive(Debug)]
pub struct PuzzleData<'a>(pub Vec<Passport<'a>>);
impl<'a> From<&'a str> for PuzzleData<'a> {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self(s.split("\n\n").map(Passport::from).collect())
}
}
impl<'a> From<&'a str> for Passport<'a> {
fn from(s: &'a str) -> Self {
let mut passport = Self::default();
for (key, value) in s
.split_ascii_whitespace()
.map(|p| p.split_once(':').unwrap())
{
match key {
"byr" => passport.byr = Some(value),
"iyr" => passport.iyr = Some(value),
"eyr" => passport.eyr = Some(value),
"hgt" => passport.hgt = Some(value),
"hcl" => passport.hcl = Some(value),
"ecl" => passport.ecl = Some(value),
"pid" => passport.pid = Some(value),
"cid" => passport.cid = Some(value),
_ => panic!(),
}
}
passport
}
}
}
Star 1
Simply check whether all fields are set, ignoring 'cid'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn star_1(PuzzleData(passports): &PuzzleData) -> SolType1 {
passports
.iter()
.filter(|passport| {
passport.byr.is_some()
&& passport.iyr.is_some()
&& passport.eyr.is_some()
&& passport.hgt.is_some()
&& passport.hcl.is_some()
&& passport.ecl.is_some()
&& passport.pid.is_some()
})
.count()
}
Star 2
Implementation of validity check gets a bit tedious but still simple
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
pub fn is_valid(passport: &&Passport) -> bool {
// byr (Birth Year) - four digits; at least 1920 and at most 2002.
// iyr (Issue Year) - four digits; at least 2010 and at most 2020.
// eyr (Expiration Year) - four digits; at least 2020 and at most 2030.
if !passport
.byr
.map(|v| v.len() == 4 && ("1920"..="2002").contains(&v))
.unwrap_or(false)
{
return false;
}
if !passport
.iyr
.map(|v| v.len() == 4 && ("2010"..="2020").contains(&v))
.unwrap_or(false)
{
return false;
}
if !passport
.eyr
.map(|v| v.len() == 4 && ("2020"..="2030").contains(&v))
.unwrap_or(false)
{
return false;
}
// hgt (Height) - a number followed by either cm or in:
// If cm, the number must be at least 150 and at most 193.
// If in, the number must be at least 59 and at most 76.
let valid_hgt = passport
.hgt
.map(|hgt| {
if hgt.len() < 3 {
return false;
}
let mut v = 0;
for b in &hgt.as_bytes()[0..hgt.len() - 2] {
match b {
b'0'..=b'9' => v = v * 10 + (b - b'0') as usize,
_ => return false,
}
}
match &hgt.as_bytes()[hgt.len() - 2..] {
b"cm" => (150..=193).contains(&v),
b"in" => (59..=76).contains(&v),
_ => false,
}
})
.unwrap_or(false);
if !valid_hgt {
return false;
}
// hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f.
let valid_hcl = passport
.hcl
.map(|hcl| {
let hcl = hcl.as_bytes();
hcl[0] == b'#'
&& hcl[1..]
.iter()
.all(|b| b.is_ascii_digit() || (b'a'..=b'f').contains(b))
})
.unwrap_or(false);
if !valid_hcl {
return false;
}
// ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.
if !passport
.ecl
.map(|ecl| ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"].contains(&ecl))
.unwrap_or(false)
{
return false;
}
// pid (Passport ID) - a nine-digit number, including leading zeroes.
if !passport
.pid
.map(|pid| pid.len() == 9 && pid.bytes().all(|b| b.is_ascii_digit()))
.unwrap_or(false)
{
return false;
}
// cid (Country ID) - ignored, missing or not.
true
}
pub fn star_2(PuzzleData(passports): &PuzzleData) -> SolType2 {
passports.iter().filter(is_valid).count()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cm
iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
hcl:#cfa07d byr:1929
hcl:#ae17e1 iyr:2013
eyr:2024
ecl:brn pid:760753108 byr:1931
hgt:179cm
hcl:#cfa07d eyr:2025 pid:166559648
iyr:2011 ecl:brn hgt:59in
"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(2, star_1(&data));
}
}
Day 5: Binary Boarding
Rust solution to AoC|2020|5.
Manipulate bits in boarding passes
Input
Just interpret 'L' / 'F' as 'LOW', i.e., 0 bits, and 'R' / 'B' as 'HIGH', i.e., 1 bits.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<u16>);
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self(
s.lines()
.map(|pass| {
pass.bytes().fold(0, |pass, b| match b {
b'F' | b'L' => pass << 1,
b'B' | b'R' => (pass << 1) | 1,
_ => panic!(),
})
})
.collect(),
)
}
}
}
Star 1
Just return the biggest value
1
2
3
pub fn star_1(PuzzleData(seats): &PuzzleData) -> SolType {
*seats.iter().max().unwrap()
}
Star 2
Sort the list and find the number that fits in between two existing
1
2
3
4
5
6
7
8
9
10
pub fn star_2(PuzzleData(seats): &PuzzleData) -> SolType {
let mut seats = seats.to_owned();
seats.sort_unstable();
let (a, _) = seats
.iter()
.zip(seats.iter().skip(1))
.find(|&(a, b)| b - a == 2)
.unwrap();
a + 1
}
Day 6: Custom Customs
Rust solution to AoC|2020|6.
Input
I parse the input into the bits of u64 numbers
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<Vec<u64>>);
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self(
s.split("\n\n")
.map(|group| {
group
.lines()
.map(|line| line.bytes().fold(0, |g, b| g | 1 << (b - b'a')))
.collect()
})
.collect(),
)
}
}
}
Star 1
Accumulation uses bitwise of.
1
2
3
4
5
6
pub fn star_1(PuzzleData(groups): &PuzzleData) -> SolType {
groups
.iter()
.map(|group| group.iter().fold(0, |g, v| g | v).count_ones())
.sum()
}
Star 2
Change accumulation to use bitwise and (and start from all bits set)
1
2
3
4
5
6
pub fn star_2(PuzzleData(groups): &PuzzleData) -> SolType {
groups
.iter()
.map(|group| group.iter().fold(u64::MAX, |g, v| g & v).count_ones())
.sum()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"abc
a
b
c
ab
ac
a
a
a
a
b
"#;
#[test]
pub fn test_from() {
let PuzzleData(groups) = PuzzleData::from(CONTENT);
assert_eq!(
vec![
vec![0b111],
vec![0b1, 0b10, 0b100],
vec![0b11, 0b101],
vec![0b1, 0b1, 0b1, 0b1],
vec![0b10]
],
groups
);
}
#[test]
pub fn test_star_1() {
assert_eq!(11, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(6, star_2(&data));
}
}
Day 7: Handy Haversacks
Rust solution to AoC|2020|7.
Understand how bags need to be wrapped in each other
Input
Input parsing is a bit tedious because it is quite textual. In the end, I have a map with outer bag names as keys and a list of pairs of counts and inner bag names 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
pub mod input {
use std::collections::HashMap;
#[derive(Debug)]
pub struct Rules<'a>(pub HashMap<&'a str, Vec<(usize, &'a str)>>);
impl<'a> From<&'a str> for Rules<'a> {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self(
s.lines()
.map(|line| line.split_once(" bags contain ").unwrap())
.map(|(name, contained)| match contained {
"no other bags." => (name, vec![]),
_ => (
name,
contained
.trim_end_matches('.')
.split(", ")
.map(|part| part.split_once(' ').unwrap())
.map(|(v, n)| {
(
v.parse::<usize>().unwrap(),
n.trim_end_matches('s').strip_suffix(" bag").unwrap(),
)
})
.collect(),
),
})
.collect(),
)
}
}
}
Star 1
I construct an inverse map (from inner to outer bag) and then do a depth first search to find the number of bags that may eventually contain a shiny gold bag.
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 fn star_1(Rules(rules): &Rules) -> SolType1 {
let mut inv_rules = HashMap::new();
for (&outer, list) in rules {
for &(_, inner) in list {
inv_rules
.entry(inner)
.or_insert_with(Vec::new)
.push(outer)
}
}
let target = "shiny gold";
let mut seen = HashSet::from([target]);
let mut queue = Vec::from([target]);
let mut cnt = 0;
while let Some(name) = queue.pop() {
if let Some(list) = inv_rules.get(name) {
for &outer in list {
if seen.insert(outer) {
cnt += 1;
queue.push(outer);
}
}
}
}
cnt
}
Star 2
Count the number of total bags using a recursive count_bags function. In the end, the outermost bag needs to be subtracted
1
2
3
4
5
6
7
8
9
10
11
pub fn count_bags(rules: &HashMap<&str, Vec<(usize, &str)>>, name: &str) -> usize {
1 + rules
.get(name)
.unwrap_or(&vec![])
.iter()
.fold(0, |acc, &(cnt, inner)| acc + cnt * count_bags(rules, inner))
}
pub fn star_2(Rules(rules): &Rules) -> SolType2 {
count_bags(rules, "shiny gold") - 1
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashMap;
const CONTENT: &str = r#"light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.
"#;
#[test]
pub fn test_from() {
let Rules(rules) = CONTENT.into();
assert_eq!(
HashMap::from([
("light red", vec![(1, "bright white"), (2, "muted yellow")]),
(
"dark orange",
vec![(3, "bright white"), (4, "muted yellow")]
),
("bright white", vec![(1, "shiny gold")]),
("muted yellow", vec![(2, "shiny gold"), (9, "faded blue")]),
("shiny gold", vec![(1, "dark olive"), (2, "vibrant plum")]),
("dark olive", vec![(3, "faded blue"), (4, "dotted black")]),
("vibrant plum", vec![(5, "faded blue"), (6, "dotted black")]),
("faded blue", vec![]),
("dotted black", vec![]),
]),
rules
);
}
#[test]
pub fn test_star_1() {
let data = Rules::from(CONTENT);
assert_eq!(4, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = Rules::from(CONTENT);
assert_eq!(32, star_2(&data));
}
}
Day 8: Handheld Halting
Rust solution to AoC|2020|8.
Fix infinite loop in handheld device
Input
Parse instructions in list of Instruction 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
28
29
30
31
32
33
34
35
36
37
pub mod input {
use crate::Instruction;
#[derive(Debug)]
pub struct Program(pub Vec<Instruction>);
impl From<&str> for Program {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self(s.lines().map(Instruction::from).collect())
}
}
impl From<&str> for Instruction {
fn from(value: &str) -> Self {
let v_0: isize = value[5..].parse().unwrap();
let v = match &value[4..5] {
"+" => v_0,
"-" => -v_0,
_ => panic!(),
};
match &value[0..3] {
"acc" => Self::Acc(v),
"nop" => Self::NOp(v),
"jmp" => Self::Jmp(v),
_ => panic!(),
}
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Instruction {
Acc(isize),
NOp(isize),
Jmp(isize),
}
Star 1
Just loop through the instructions until one is seen for a second time
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn loop_or_terminate(instructions: &[Instruction]) -> (usize, isize) {
let mut seen = vec![false; instructions.len()];
let mut p = 0;
let mut acc = 0;
loop {
seen[p] = true;
(p, acc) = match instructions[p] {
Instruction::Acc(v) => (p + 1, acc + v),
Instruction::NOp(_) => (p + 1, acc),
Instruction::Jmp(v) => (p.wrapping_add_signed(v), acc),
};
if p == instructions.len() || seen[p] {
break;
}
}
(p, acc)
}
pub fn star_1(Program(instructions): &Program) -> SolType {
loop_or_terminate(instructions).1
}
Star 2
Use the the solution from part one and run it on the modified program variants, until a modification is found, that terminates correctly
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(Program(instructions): &Program) -> SolType {
let mut instructions = instructions.to_owned();
for k in 0..instructions.len() {
let (old, new) = match instructions[k] {
Instruction::NOp(v) => (Instruction::NOp(v), Instruction::Jmp(v)),
Instruction::Jmp(v) => (Instruction::Jmp(v), Instruction::NOp(v)),
_ => continue,
};
instructions[k] = new;
let (p, acc) = loop_or_terminate(&instructions);
if p == instructions.len() {
return acc;
}
instructions[k] = old;
}
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
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: &str = r#"nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
"#;
#[test]
pub fn test_from() {
use Instruction::{Acc, Jmp, NOp};
let Program(data) = Program::from(CONTENT);
assert_eq!(
vec![
NOp(0),
Acc(1),
Jmp(4),
Acc(3),
Jmp(-3),
Acc(-99),
Acc(1),
Jmp(-4),
Acc(6)
],
data
);
}
#[test]
pub fn test_star_1() {
let data = Program::from(CONTENT);
assert_eq!(5, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = Program::from(CONTENT);
assert_eq!(8, star_2(&data));
}
}
Day 9: Encoding Error
Rust solution to AoC|2020|9.
Hack eXchange-Masking Addition System (XMAS)
Input
Just read a list of numbers
1
2
3
4
5
6
7
8
9
10
11
pub mod input {
#[derive(Debug)]
pub struct Data(pub Vec<usize>);
impl From<&str> for Data {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self(s.lines().map(str::parse).collect::<Result<_, _>>().unwrap())
}
}
}
Star 1
Iterate through the list and find the first element that is not the sum of two distinct numbers in the N previous elements, where N ist the length of the preamble
1
2
3
4
5
6
7
8
9
10
11
pub fn solve_1(data: &[usize], preamble: usize) -> SolType1 {
(preamble..)
.filter(|&k| {
!(k - preamble..k)
.flat_map(|i| (i + 1..k).map(move |j| (i, j)))
.any(|(i, j)| data[i] != data[j] && data[i] + data[j] == data[k])
})
.map(|k| data[k])
.next()
.unwrap()
}
Star 2
Find a contiguous set summing up to the number from part 1 by scanning through the list and alternating between adding more elements until the number is reached or surpassed and removing elements until the number is reached or falls below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub fn solve_2(data: &[usize], preamble: usize) -> SolType1 {
let n = solve_1(data, preamble);
let mut k_0 = 0;
let mut k_1 = 1;
let mut sum = data[0];
while sum != n {
while sum < n {
sum += data[k_1];
k_1 += 1;
}
while sum > n {
sum -= data[k_0];
k_0 += 1;
}
}
let (mn, mx) = (k_0..k_1).fold((usize::MAX, usize::MIN), |(mn, mx), k| {
(mn.min(data[k]), mx.max(data[k]))
});
mn + mx
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576
"#;
#[test]
pub fn test_solve_1() {
assert_eq!(127, solve_1(&Data::from(CONTENT).0, 5));
}
#[test]
pub fn test_solve_2() {
assert_eq!(62, solve_2(&Data::from(CONTENT).0, 5));
}
}
Day 10: Adapter Array
Rust solution to AoC|2020|10.
Figure out which adapters to use to charge your devices…
Input
As part of input processing, I add the 0 jolts outlet and the +3 jolts device and sort the adapters by rating.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub mod input {
#[derive(Debug)]
pub struct List(pub Vec<usize>);
impl From<&str> for List {
/// parse the puzzle input
fn from(s: &str) -> Self {
let mut list: Vec<usize> = s.lines().map(|l| l.parse().unwrap()).collect();
list.push(0);
list.sort_unstable();
list.push(list.last().unwrap() + 3);
Self(list)
}
}
}
Star 1
Determine deltas using iter.zip and count…
1
2
3
4
5
6
7
8
9
10
11
12
pub fn star_1(List(list): &List) -> SolType1 {
let (ones, threes) =
list.iter()
.zip(list[1..].iter())
.fold((0, 0), |(ones, threes), (a, b)| match b - a {
1 => (ones + 1, threes),
3 => (ones, threes + 1),
_ => (ones, threes),
});
ones * threes
}
Star 2
Use the fact that all distances are either 1 or 3.
So there are groups where all ratings are at distance 1 which are separated by distance 3. Each of these groups, which consists of at least 3 members, contributes a factor to the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn star_2(List(list): &List) -> SolType2 {
let (groups, cnt) =
list.iter()
.zip(list[1..].iter())
.fold(([0; 3], 1), |(mut groups, cnt), (a, b)| {
if b - a == 1 {
(groups, cnt + 1)
} else {
assert_eq!(3, b - a, "unexpected distance from {} to {}", a, b);
if cnt > 2 {
groups[cnt - 3] += 1;
}
(groups, 1)
}
});
debug_assert_eq!(1, cnt, "last delta is 3");
const COMBINATIONS: [usize; 3] = [2, 4, 7];
(0..3).map(|k| COMBINATIONS[k].pow(groups[k])).product()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"16
10
15
5
1
11
7
19
6
12
4
"#;
#[test]
pub fn test_from() {
let data = List::from(CONTENT);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
assert_eq!(35, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(8, star_2(&CONTENT.into()));
}
}
Day 11: Seating System
Rust solution to AoC|2020|11.
Seating simulation
Input
The seat layout is parsed into a grid of bytes (removing newlines)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub mod input {
#[derive(Debug)]
pub struct Grid {
pub data: Vec<u8>,
pub w: usize,
}
impl From<&str> for Grid {
/// parse the puzzle input
fn from(s: &str) -> Self {
let data = s.bytes().filter(|&b| b != b'\n').collect();
let w = s.find('\n').unwrap();
Self { data, w }
}
}
}
Star 1
The final solution is generic for both parts.
The specific part for star 1 is the function to count occupied adjacent seats and and the limit indicating how when an occupied seat gets free (4 for part 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
52
53
54
55
56
pub fn solve<F: Fn(usize, usize, &[u8], usize) -> usize>(
Grid { data, w }: &Grid,
lim: usize,
f: F,
) -> SolType {
let mut data = data.to_owned();
let mut upd = vec![b'.'; data.len()];
while data != upd {
for p in 0..data.len() {
let (x, y) = (p % w, p / w);
if data[x + w * y] == b'.' {
continue;
}
let occupied = f(x, y, &data, *w);
upd[x + w * y] = if occupied == 0 {
b'#'
} else if occupied >= lim {
b'L'
} else {
data[x + w * y]
}
}
(data, upd) = (upd, data)
}
data.iter().filter(|&&b| b == b'#').count()
}
const DELTA: [(isize, isize); 8] = [
(1, 0),
(1, -1),
(0, -1),
(-1, -1),
(-1, 0),
(-1, 1),
(0, 1),
(1, 1),
];
pub fn star_1(grid: &Grid) -> SolType {
solve(grid, 4, |x, y, data, w| {
DELTA
.iter()
.map(|&(d_x, d_y)| {
(
x.wrapping_add_signed(d_x),
(w * y).wrapping_add_signed(w as isize * d_y),
)
})
.filter(|&(x, y_scaled)| x < w && y_scaled < data.len() && data[x + y_scaled] == b'#')
.count()
})
}
Star 2
The function to count occupied adjacents is a bit more complicated for part 2. The limit changed to 5. Everything else is unchanged.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
pub fn star_2(grid: &Grid) -> SolType {
solve(grid, 5, |x, y, data, w| {
let mut occupied = 0;
for (d_x, d_y) in DELTA {
for k in 1.. {
let (x, y_scaled) = (
x.wrapping_add_signed(k * d_x),
(w * y).wrapping_add_signed(w as isize * k * d_y),
);
if x >= w || y_scaled >= data.len() {
break;
}
match data[x + y_scaled] {
b'L' => break,
b'#' => {
occupied += 1;
break;
}
_ => (),
}
}
}
occupied
})
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL
"#;
#[test]
pub fn test_from() {
let data = Grid::from(CONTENT);
assert_eq!(10, data.w);
println!("{data:?}");
}
#[test]
pub fn test_star_1() {
let data = Grid::from(CONTENT);
assert_eq!(37, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = Grid::from(CONTENT);
assert_eq!(26, star_2(&data));
}
}
Day 12: Rain Risk
Rust solution to AoC|2020|12.
Input
Parse instructions in a list of pairs of instruction identifier bytes and values
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub mod input {
#[derive(Debug)]
pub struct Instructions(pub Vec<(u8, isize)>);
impl From<&str> for Instructions {
/// parse the puzzle input
fn from(value: &str) -> Self {
Self(
value
.lines()
.map(|line| (line.as_bytes()[0], line[1..].parse().unwrap()))
.collect(),
)
}
}
}
Star 1
A simple iter, fold.
I had a bit of fun encoding the "move forward in direction of ship" part.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn star_1(Instructions(instructions): &Instructions) -> SolType1 {
let (x, y, _) = instructions
.iter()
.fold((0, 0, 0), |(e, n, h), (b, v)| match b {
b'E' => (e + v, n, h),
b'N' => (e, n + v, h),
b'W' => (e - v, n, h),
b'S' => (e, n - v, h),
b'L' => (e, n, (h + v / 90) & 3),
b'R' => (e, n, (h + 3 * v / 90) & 3),
b'F' => (
e + (!h & 1) * (1 - (h & 2)) * v,
n + (h & 1) * (1 - (h & 2)) * v,
h,
),
_ => panic!(),
});
x.abs() + y.abs()
}
Star 2
Another iter, fold
The rotation part uses a nested iterator. An alternative could be to model the four different rotations explicitly.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub fn star_2(Instructions(instructions): &Instructions) -> SolType2 {
let ((x, y), _) = instructions.iter().fold(
((0, 0), (10, 1)),
|((s_e, s_n), (w_e, w_n)), (b, v)| match b {
b'E' => ((s_e, s_n), (w_e + v, w_n)),
b'N' => ((s_e, s_n), (w_e, w_n + v)),
b'W' => ((s_e, s_n), (w_e - v, w_n)),
b'S' => ((s_e, s_n), (w_e, w_n - v)),
b'L' => (
(s_e, s_n),
(0..(*v / 90) & 3).fold((w_e, w_n), |(w_e, w_n), _| (-w_n, w_e)),
),
b'R' => (
(s_e, s_n),
(0..(*v / 90) & 3).fold((w_e, w_n), |(w_e, w_n), _| (w_n, -w_e)),
),
b'F' => ((s_e + v * w_e, s_n + v * w_n), (w_e, w_n)),
_ => panic!(),
},
);
x.abs() + y.abs()
}
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#"F10
N3
F7
R90
F11
"#;
#[test]
pub fn test_from() {
let Instructions(instructions) = CONTENT.into();
assert_eq!(
vec![(b'F', 10), (b'N', 3), (b'F', 7), (b'R', 90), (b'F', 11)],
instructions
);
}
#[test]
pub fn test_star_1() {
assert_eq!(25, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(286, star_2(&CONTENT.into()));
}
}
Day 13: Shuttle Search
Rust solution to AoC|2020|13.
Solution
Part 1 is straight forward:
1
2
3
4
5
6
7
/// Find earliest departure after timestamp `earliest`
pub fn find_earliest_departure(earliest: i64, ids: &[Option<i64>]) -> (i64, i64) {
ids.iter()
.filter_map(|id| id.map(|id| (id, ((earliest + id - 1) / id) * id)))
.min_by(|(_, a), (_, b)| a.cmp(b))
.expect("No min found")
}
Part 2 is more tricky.
I solved it using the Extended Euclidean Algorithm to compute the multiplicative inverse of an integer modulo another integer.
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
/// Find time which satisfied `(t + pos[i]) % id[i] == 0` for all ship ids
///
/// # Algorithm
///
/// The algorithm updates the time `t` for every position `pos[i]` where
/// `id[i] = id[pos[i]] != "x"`, solving equations of the form `(a k + b) % m = 0` for `k` as
/// follows.
///
/// ## Initial Step
///
/// 1. `t[0] = 0`
/// 2. `a[0] = 1`
///
/// ## Loop (`i >= 0`)
///
/// 1. solve `(t[i - 1] + k * a[i - 1] + pos[i]) % id[i] == 0` for `k`
/// 2. `t[i] = t[i - 1] + k * a[i - 1]`
/// 3. `a[i] = id[i - 1] * a[i - 1]`
///
/// ## Solving linear equations with modulo
///
/// The solution of `(a k + b) % m = 0` for `k` generally requires `a` and `m` to be co-prime and
/// is done with a multiplicative inverse `a` modulo `m`. See [`mul_inverse_mod`]
///
/// # Panics
/// if any of the ids are not co-prime
///
pub fn find_time(ids: &[Option<i64>]) -> i64 {
let (t, ..) = ids
.iter()
.enumerate()
.filter_map(|(pos, v)| v.map(|v| (pos as i64, v)))
.fold((0, 1), |(t, a), (pos, id)| {
let k = (-mul_inverse_mod(a, id) * (t + pos)).modulo(id);
(t + k * a, a * id)
});
t
}
I find it quite amazing that the solution only takes a couple of microseconds.
After comparing with other solutions, I realized that the key for performance is to go bus by bus and not so much how to solve the linear equations with a module.
Searching for those solutions iteratively is merely slower. I implemented a variant (idea taken from James Hockenberry):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/// Solution idea of James Hockenberry re-implemented in rust
///
/// Instead of calculating the multiplicative inverse, solves equations
/// `(k a + c) % m = 0` for `k` by linear search.
pub fn find_time_iteratively(ids: &[Option<i64>]) -> i64 {
let (t, ..) = ids
.iter()
.enumerate()
.filter_map(|(pos, v)| v.map(|v| (pos as i64, v)))
.fold((0, 1), |(t, a), (pos, id)| {
let mut k = 0;
while (t + k * a + pos) % id != 0 {
k += 1;
}
(t + k * a, a * id)
});
t
}
I have to admit it took me quite a while to get the algorithm right. In addition to test driven development, properly writing down your algorithm before you try to encode it in an iterator adaptor definitely helps.
Day 14: Docking Data
Rust solution to AoC|2020|14.
Solution
Today’s challenge gave me quite some headaches, especially part two. Can’t really explain why. In the end it was not very complicated.
The bit-mask is modeled as struct, and a single instruction is modeled as an enum with one variant for bit masks and another one for write operations.
1
2
3
4
5
6
7
8
9
/// A bitmask
///
/// Bits are stored in two integers, `ones` for all one bits, `zeros` for all zero bits. The unset
/// bits can be obtained as `nones = BitMask::ALL & !ones & !zeros`.
#[derive(Debug, PartialEq, Copy, Clone)]
pub struct BitMask {
ones: u64,
zeros: u64,
}
1
2
3
4
5
6
7
/// An instruction, with variants `BitMask` for [`BitMask`] values and `Write` for
/// tuple `(u64, u64)` values representing address and value
#[derive(Debug, PartialEq)]
pub enum Instruction {
BitMask(BitMask),
Write((u64, u64)),
}
Part 1
For part 1, the bit mask struct has a simple function apply which applies the bit mask to a value. With this, the solution for part 1 is
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/// Solve part 1
pub fn run_v1(Instructions(instructions): &Instructions) -> HashMap<u64, u64> {
// memory map: address -> value
let mut memory = HashMap::new();
// current mask
let mut mask = BitMask {
ones: BitMask::ALL,
zeros: 0,
};
for instruction in instructions {
// update mask or insert value with current mask applied
match instruction {
Instruction::BitMask(new_mask) => mask = *new_mask,
Instruction::Write((address, value)) => _ = memory.insert(*address, mask.apply(*value)),
}
}
// return memory
memory
}
Part 2
To iterate over all combinations of addresses, I implemented an iterator with the struct
1
2
3
4
5
6
7
/// An Iterator over all possible states the none bits of a [`BitMask`] may take
pub struct BitMaskNones {
current: u64,
max: u64,
mask: u64,
nones: Vec<u64>,
}
which is initialized from a BitMask as follows:
1
2
3
4
5
6
7
8
9
10
/// Construct instance from `[BitMask]`
fn from(mask: &BitMask) -> BitMaskNones {
let nones = mask.nones();
BitMaskNones {
current: 0,
max: 1 << nones.len(),
mask: !mask.zeros & !mask.ones & BitMask::ALL,
nones,
}
}
The only function to implement is the next function.
(The size_hint function is optional, it may help to optimize 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
impl Iterator for BitMaskNones {
type Item = (u64, u64);
fn next(&mut self) -> Option<(u64, u64)> {
if self.current >= self.max {
// all values consumed
return None;
}
// combine all nones for which the corresponding bit is set in `current` with bitwise or
let nones = self
.nones
.iter()
.enumerate()
.filter(|(pos, _)| (self.current >> pos) & 1 == 1)
.fold(0, |nones, (_, none)| nones | none);
// update counter
self.current += 1;
// return mask and none
Some((self.mask, nones))
}
fn size_hint(&self) -> (usize, Option<usize>) {
let remaining = self.max - self.current;
if remaining > usize::MAX as u64 {
(usize::MAX, None)
} else {
(remaining as usize, Some(remaining as usize))
}
}
}
With this, the solution for part 2 is
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/// Solve part 2
///
/// Iterating over all combinations of floating bits is done with my first own Iterator in Rust.
/// See [`BitMaskNones`].
pub fn run_v2(Instructions(instructions): &Instructions) -> HashMap<u64, u64> {
// memory map: address -> value
let mut memory = HashMap::new();
// current mask
let mut mask = BitMask {
ones: BitMask::ALL,
zeros: 0,
};
for instruction in instructions {
match instruction {
// update mask or insert value at all relevant addresses
Instruction::BitMask(new_mask) => mask = *new_mask,
Instruction::Write((address, value)) => {
// apply ones to address
let address = *address | mask.ones;
// iterate over all combinations of floating bits and add value to memory addresses
for (mask, none) in BitMaskNones::from(&mask) {
memory.insert((address & !mask) | none, *value);
}
}
}
}
// return memory
memory
}
Day 15: Rambunctious Recitation
Rust solution to AoC|2020|15.
Solution
The solution idea is to store for every value the last round when it occurred in a map.
The map is initialized with
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
/// Initialize map for memory game
///
/// The input is expected to be a comma separated list of integers
/// The function returns a map where the values in the input list are the keys and their position's
/// in the input list are their values. The last value is not in the map but returned in addition to
/// the map. The third return value is the number of the round to start playing on this map.
///
/// # Panics
///
/// This function panics if the input list is not a comma separated list of distinct integer values
pub fn init(line: &str) -> (Vec<usize>, usize, usize) {
let mut last = 0;
let mut map = Vec::new();
for (pos, v) in line
.trim()
.split(',')
.map(|v| v.parse::<usize>().unwrap())
.enumerate()
{
if map.len() <= v {
map.resize(v + 1, usize::MAX);
}
map[v] = pos;
last = v;
}
let start = map[last] + 1;
map[last] = usize::MAX;
(map, last, start)
}
Then rounds are played with
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
/// Play memory game rounds
///
/// Arguments:
///
/// `map` map as created by [`init`]
/// `last` last value spoken
/// `start` start round (inclusive, initially length of the input)
/// `end` end round (exclusive)
///
/// Returns: the value spoken in the round end - 1
///
/// # Examples
///
/// ```
/// let (mut map, last, start) = mr_kaffee_2020_15::init("0,3,6");
/// let last = mr_kaffee_2020_15::play(&mut map, last, start, 7);
/// assert_eq!(last, 1);
/// let last = mr_kaffee_2020_15::play(&mut map, last, 7, 10);
/// assert_eq!(last, 0);
/// ```
pub fn play(map: &mut Vec<usize>, last: usize, start: usize, end: usize) -> usize {
(start - 1..end - 1).fold(last, |last, turn| {
if map.len() <= last {
map.resize(last + 1, usize::MAX);
}
let prev = map[last];
map[last] = turn;
if prev == usize::MAX {
0
} else {
turn - prev
}
})
}
I used the same method to solve both parts 1 and 2. I wonder whether there are more elegant solutions for part 2. With compiler optimizations on, brute force solves part 2 in a about a second…
Day 16: Ticket Translation
Rust solution to AoC|2020|16.
Solution
The most difficult part for the first star was to parse the input correctly:
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
impl<'a> From<&'a str> for PuzzleData<'a> {
fn from(content: &'a str) -> Self {
let mut mode = 0;
let mut rules = Vec::new();
let mut my_pass = Vec::new();
let mut passes = Vec::new();
let mut invalids = 0;
for line in content.lines() {
match line {
YOUR_TICKET => {
mode = 1;
continue;
}
NEARBY_TICKETS => {
mode = 2;
continue;
}
_ if line.is_empty() => continue,
_ => (),
};
match mode {
0 => {
let (name, ranges) = line.split_once(": ").unwrap();
let mut ranges = ranges.split(" or ").map(|range| {
range
.split_once('-')
.map(|(a, b)| (a.parse().unwrap(), b.parse().unwrap()))
.unwrap()
});
rules.push(Rule {
name,
range_1: ranges.next().unwrap(),
range_2: ranges.next().unwrap(),
});
}
1 => {
my_pass.extend(line.split(',').map(|v| v.parse::<i32>().unwrap()));
assert_eq!(rules.len(), my_pass.len());
}
2 => {
let pass: Vec<_> =
line.split(',').map(|v| v.parse::<i32>().unwrap()).collect();
assert_eq!(rules.len(), pass.len());
match pass
.iter()
.filter(|&v| !rules.iter().any(|rule| rule.matches(*v)))
.fold(None, |invalid, v| invalid.or(Some(0)).map(|w| w + v))
{
Some(invalid) => invalids += invalid,
None => passes.push(pass),
}
}
_ => unreachable!(),
}
}
Self {
rules,
my_pass,
passes,
invalids,
}
}
}
In the second part of the puzzle, I struggled a bit with the fact that in my puzzle input, there seemed to be a field for which no rule matches, consistently for all passes.
My assumption was, that this is a bug in my solution, which I was trying to figure out for a while, before I realized that all the "departure" fields were already uniquely identified, … and my answer was accepted.
Looking at the problem a second time, I realized my mistake (obviously, it was my mistake). In the first part of the puzzle, I discarded all passes for which the sum of the invalid fields was greater than zero. This kept the pass with an invalid field equal to zero in my list for the second part of the puzzle, for which later on no rule matched.
TIL: Sum over elements equal to zero does not imply count of elements equal to zero.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub fn find_fields(rules: &[Rule], passes: &[Vec<i32>], prefix: &str) -> Vec<(usize, usize)> {
let n = rules.len();
// i = r + f * n -> r = i % n, f = i / n
let mut candidates = (0..n * n)
.map(|i| passes.iter().all(|pass| rules[i % n].matches(pass[i / n])))
.collect::<Vec<_>>();
let settled = reduce(&mut candidates, n);
assert_eq!(
settled.len(),
n,
"Could not settle all rules: {} of {} settled.",
settled.len(),
n
);
(0..n)
.filter(|&r| rules[r].name.starts_with(prefix))
.map(|r| (r, *settled.get(&r).unwrap()))
.collect()
}
Once the matrix of candidates is constructed, it is reduced as follows:
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
/// Reduce square `n x n` matrix with a column for each rule a and a row for
/// each field
///
/// If there is a rule, which is a candidate for exactly one field, this field
/// is removed as a candidate for all other rules
fn reduce(candidates: &mut [bool], n: usize) -> BTreeMap<usize, usize> {
// count number of candidates per rule
let mut counts = (0..n)
.map(|rule| (0..n).filter(|field| candidates[rule + n * field]).count())
.collect::<Vec<usize>>();
// map for results rule -> field
// (BTreeSet is faster than HashSet here, probably because it is small)
let mut rules = BTreeMap::new();
// while there is a rule with one candidate not yet settled
while let Some(rule) = (0..n).find(|rule| !rules.contains_key(rule) && counts[*rule] == 1) {
// find unique field
let field = (0..n).find(|field| candidates[rule + n * field]).unwrap();
// update result
rules.insert(rule, field);
// update candidates and counts
for other_rule in (0..n).filter(|&other_rule| other_rule != rule) {
if candidates[other_rule + n * field] {
candidates[other_rule + n * field] = false;
counts[other_rule] -= 1;
}
}
}
// return rules
rules
}
Day 17: Conway Cubes
Rust solution to AoC|2020|17.
Update infinite 3D or 4D grid
Solution
My challenge in this puzzle was to find a way how to implement the solution in a generic way, that works for both, parts 1 and 2.
I did this with a quite simple Coord trait which is implemented by [isize; 3] and [isize; 4]. The Index and IndexMut trait bounds are key.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub trait Coord:
Eq + Hash + Copy + Default + Index<usize, Output = isize> + IndexMut<usize>
{
const DIM: usize;
fn map<F: FnMut(isize) -> isize>(self, f: F) -> Self;
}
impl Coord for [isize; 3] {
const DIM: usize = 3;
fn map<F: FnMut(isize) -> isize>(self, f: F) -> Self {
<[isize; 3]>::map(self, f)
}
}
impl Coord for [isize; 4] {
const DIM: usize = 4;
fn map<F: FnMut(isize) -> isize>(self, f: F) -> Self {
<[isize; 4]>::map(self, f)
}
}
Here is how the solving functions look like:
1
2
3
4
5
6
7
8
9
10
11
12
13
pub fn star_1(input: &&str) -> SolType {
solve(input, [0, 0, 0], 6)
}
pub fn star_2(input: &&str) -> SolType {
solve(input, [0, 0, 0, 0], 6)
}
pub fn solve<T: Coord>(input: &str, x_0: T, steps: isize) -> SolType {
let (map, bbox) = parse(input, x_0);
let (map, _) = update_steps(&map, &bbox, steps);
map.len()
}
Whether a 3D or a 4D solution is calculated is fully determined by the value (or actually type) of the x_0 parameter, which I find quite elegant.
Parsing
The generic parse function looks as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub fn parse<T: Coord>(content: &str, x_0: T) -> (HashSet<T>, BBox<T>) {
let mut map: HashSet<T> = HashSet::new();
let mut bbox: BBox<T> = BBox::default();
content.lines().enumerate().for_each(|(v_1, line)| {
line.chars().enumerate().for_each(|(v_0, c)| {
if c == '#' {
let mut x = x_0;
(x[0], x[1]) = (v_0 as _, v_1 as _);
bbox.update(&x);
map.insert(x);
}
});
});
(map, bbox)
}
Grid updates
Here is the update functions:
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
pub fn update_steps<T: Coord>(
map: &HashSet<T>,
bbox: &BBox<T>,
steps: isize,
) -> (HashSet<T>, BBox<T>) {
assert!(steps > 0, "steps > 0 required");
let (mut map, mut bbox) = update(map, bbox);
for _ in 1..steps {
(map, bbox) = update(&map, &bbox);
}
(map, bbox)
}
pub fn update<T: Coord>(map: &HashSet<T>, BBox(min, max): &BBox<T>) -> (HashSet<T>, BBox<T>) {
let mut map_upd = HashSet::new();
let mut bbox_upd = BBox::default();
let (mut x, mut d_x) = (min.map(|x| x - 1), 0);
while d_x < T::DIM {
let (mut cnt, mut a, mut d_a) = (0, x.map(|x| x - 1), 0);
while d_a < T::DIM {
if a != x && map.contains(&a) {
cnt += 1;
if cnt > 3 {
break;
}
}
// update a with overflow
d_a = 0;
while d_a < T::DIM {
if a[d_a] == x[d_a] + 1 {
a[d_a] = x[d_a] - 1;
d_a += 1;
} else {
a[d_a] += 1;
break;
}
}
}
if cnt == 3 || cnt == 2 && map.contains(&x) {
bbox_upd.update(&x);
map_upd.insert(x);
}
// update x with overflow
d_x = 0;
while d_x < T::DIM {
if x[d_x] == max[d_x] {
x[d_x] = min[d_x] - 1;
d_x += 1;
} else {
x[d_x] += 1;
break;
}
}
}
(map_upd, bbox_upd)
}
In order to be generic without too much overhead, I update coordinates with overflow, i.e., increment the lowest coordinate, if it would overflow, increment the next, … and stop the loop if the last coordinate overflows.
Day 18: Operation Order
Rust solution to AoC|2020|18.
Solution
Today was much more difficult for me than it should have been :(. My first solution for part 1 was not useable at all to solve part 2…
I first parse the input into tokens:
1
2
3
4
5
6
7
8
#[derive(PartialEq, Debug, Clone, Copy)]
pub enum Token {
Open,
Close,
Plus,
Times,
Value(isize),
}
Next I convert the tokens in an expression tree implemented as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#[derive(Debug)]
pub enum Expression {
Leaf(isize),
Sum(Box<Expression>, Box<Expression>),
Prod(Box<Expression>, Box<Expression>),
Nil,
}
impl Expression {
pub fn evaluate(&self) -> isize {
match self {
Expression::Leaf(v) => *v,
Expression::Sum(a, b) => a.evaluate() + b.evaluate(),
Expression::Prod(a, b) => a.evaluate() * b.evaluate(),
_ => panic!("Cannot evaluate Nil"),
}
}
}
The conversion is done as.
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
fn to_expression(tokens: &[Token], greedy: bool, precedence: bool) -> (Expression, usize) {
let mut upd = (Expression::Nil, 0);
while upd.1 < tokens.len() {
upd = match tokens[upd.1] {
Token::Value(v) => (Expression::Leaf(v), upd.1 + 1),
Token::Times => {
let (rhs, k_int) = to_expression(&tokens[upd.1 + 1..], precedence, precedence);
(
Expression::Prod(Box::new(upd.0), Box::new(rhs)),
upd.1 + k_int + 1,
)
}
Token::Plus => {
let (rhs, k_int) = to_expression(&tokens[upd.1 + 1..], false, precedence);
(
Expression::Sum(Box::new(upd.0), Box::new(rhs)),
upd.1 + k_int + 1,
)
}
Token::Open => {
let mut idx = None;
let mut level = 1;
for (l, token) in tokens.iter().enumerate().skip(upd.1 + 1) {
level = match token {
Token::Open => level + 1,
Token::Close if level > 1 => level - 1,
Token::Close => {
idx = Some(l);
break;
}
_ => {
continue;
}
};
}
let idx = idx.expect("No matching bracket");
let (rhs, k_int) = to_expression(&tokens[upd.1 + 1..idx], true, precedence);
(rhs, upd.1 + k_int + 2)
}
Token::Close => panic!("What should I do here?"),
};
if !greedy {
break;
}
}
upd
}
The function to_expression calls itself recursively.
The parameter greedy controls whether it should parse only the next value or until the end.
This is how I differentiate between parts 1 and 2. In part 1, I parse only the next value (greedy = false) after Plus and Times.
In part 2, I parse all tokens after Times (greedy = true).
Day 19: Monster Messages
Rust solution to AoC|2020|19.
Solution
Again one that caused some headaches. I had a solution working from the text to match backwards to rule zero, which worked on the small examples but caused my program to exit with out-of-memory-errors on the real input. I tried to simplify the set of rules by eliminating all rules without pipes by substituting them into the rules with pipes. Did not really help.
Then I started to look at the solution manually from rule zero to the value to match. This helped to find my way… (But I was still not thinking about regular expressions)
Here is my solution, which actually works for both, part 1 and part 2.
First, I parse the rules into an enum type Rule with three variants for the different rules that exist in the Puzzle.
1
2
3
4
5
6
#[derive(Debug, PartialEq, Clone)]
pub enum Rule {
Sequence(Vec<usize>),
Alternative(Vec<usize>, Vec<usize>),
Leaf(char),
}
The actual solution expands the first symbol of a search pattern repeatedly by applying the corresponding rule (possibly resulting in multiple branches) until the first symbol of the pattern is a leaf (later I learned that this would be called a terminal symbol in a formal grammar). Then there are two cases:
-
The leaf’s value matches the first character of the text to match. In this case the character is settled, and the algorithm moves on to the next symbol/character of both pattern and text to match. If there are no more symbols, the value is confirmed to match.
-
The leaf’s value does not match the first character of the text to match. In this case the algorithm rejects the pattern and discards this branch of the search.
No changes of the algorithm were required for part 2. Just replaced the rules.
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
fn matches_int(rules: &HashMap<usize, Rule>, pattern: &[usize], text: &[char]) -> bool {
// pointer to pattern element and character in text
let mut k = 0;
while let Some(Rule::Leaf(c)) = rules.get(&pattern[k]) {
// heads do not match, return false
if *c != text[k] {
return false;
}
k += 1;
// if all matches (content and candidate are exhausted at the same time) return true
if k == text.len() && k == pattern.len() {
return true;
}
// if not all matches and content or candidate exhausted, return false
if k >= text.len() || k >= pattern.len() {
return false;
}
}
match rules.get(&pattern[k]) {
Some(Rule::Sequence(a)) => {
matches_int(rules, &[a, &pattern[k + 1..]].concat(), &text[k..])
}
Some(Rule::Alternative(a, b)) => {
matches_int(rules, &[a, &pattern[k + 1..]].concat(), &text[k..])
|| matches_int(rules, &[b, &pattern[k + 1..]].concat(), &text[k..])
}
_ => panic!("Unexpected leaf node or rule not found"),
}
}
Day 20: Jurassic Jigsaw
Rust solution to AoC|2020|20.
Solution
A day to forget. Just got lost in transformations…
It’s a lot about transformations.
There are eight in total to represent all possible rotations and flips (see comments in code below).
Those transformations are applied to a flat index idx = x + n * y, where n is the width of a square tile.
The functions below are used to get and set data at a given coordinate after transformation:
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
fn transform(&self, idx: usize, t: usize) -> usize {
// idx = x + n * y
// x = idx % n
// y = idx / n
//
// 0 identity: (x, y) -> ( x, y), idx => x + n * ( y)
// 1 rot_90: (x, y) -> (n-1 - y, x), idx => n-1 - y + n * ( x)
// 2 rot_180: (x, y) -> (n-1 - x, n-1 - y), idx => n-1 - x + n * (n - 1 - y)
// 3 rot_270: (x, y) -> ( y, n-1 - x), idx => y + n * (n - 1 - x)
// 4 flip (x, y) -> (n-1 - x, y), idx => n-1 - x + n * ( y)
// 5 flip_rot_90 (x, y) -> (n-1 - y, n-1 - x), idx => n-1 - y + n * (n - 1 - x)
// 6 flip_rot_180 (x, y) -> ( x, n-1 - y), idx => x + n * (n - 1 - y)
// 7 flip_rot_270 (x, y) -> ( y, x), idx => y + n * ( x)
match t {
0 => idx,
1 => self.n - 1 - idx / self.n + self.n * (idx % self.n),
2 => self.n - 1 - idx % self.n + self.n * (self.n - 1 - idx / self.n),
3 => idx / self.n + self.n * (self.n - 1 - idx % self.n),
4 => self.n - 1 - idx % self.n + self.n * (idx / self.n),
5 => self.n - 1 - idx / self.n + self.n * (self.n - 1 - idx % self.n),
6 => idx % self.n + self.n * (self.n - 1 - idx / self.n),
7 => idx / self.n + self.n * (idx % self.n),
_ => panic!("Illegal transformation"),
}
}
fn get(&self, idx: usize, t: usize) -> char {
self.data[self.transform(idx, t)]
}
fn set(&mut self, idx: usize, t: usize, c: char) {
let idx = self.transform(idx, t);
self.data[idx] = c;
}
This is used, e.g., to check whether two tiles match on a given side (0: top, 1: right, 2: bottom, 3: left).
The transformation of the tile on which the function is called is given as an argument (t), the matching transformation of the tile provided as an argument, if any, is returned by the function.
If there is none, the function returns None.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pub fn matches(&self, tile: &Self, t: usize, side: usize) -> Option<usize> {
if self.n != tile.n {
return None;
}
let (f1, f2) = match side {
0 => ((0, 1), (self.n * (self.n - 1), 1)),
1 => ((self.n - 1, self.n), (0, self.n)),
2 => ((self.n * (self.n - 1), 1), (0, 1)),
3 => ((0, self.n), (self.n - 1, self.n)),
_ => panic!("Illegal side"),
};
(0..8).find(|t_other| {
(0..self.n).all(|k| self.get(f1.0 + f1.1 * k, t) == tile.get(f2.0 + f2.1 * k, *t_other))
})
}
The biggest part for me was to arrange the tiles. My first version started from an arbitrary tile and worked for the example but not for the real data.
Since I could not figure out my problem (see below), I first created a solution for part 1 by finding all corner tiles, i.e., all tiles which do not match to any other tile on two sides.
Once I had that, I just kept the part to find one corner tile and created the solution below which constructs the solution from a corner tail.
The function find_corner below finds a corner tile as described above and provides a transformation (rotation), that ensures the two boundaries not matching to any other tile are in the top and left directions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
pub fn find_corner(tiles: &[Tile]) -> (usize, usize) {
let (pos, neighbors) = tiles
.iter()
.enumerate()
.map(|(pos1, tile1)| {
(
pos1,
(0..4)
.map(|side| {
let found = tiles
.iter()
.enumerate()
.filter(|(pos2, _)| *pos2 != pos1)
.any(|(_, tile2)| tile1.matches(tile2, 0, side).is_some());
(found as usize) << side
})
.sum::<usize>(),
)
})
.find(|(_, dirs)| dirs.count_ones() == 2)
.unwrap();
let t = match neighbors {
0b0011 => 3,
0b0110 => 0,
0b1100 => 1,
0b1001 => 2,
_ => panic!("Illegal unmatched boundary combination"),
};
(pos, t)
}
From this, the solution is constructed row by row as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#[cfg(feature = "variant2")]
pub fn solve(Tiles(tiles): &Tiles) -> (usize, Vec<(Tile, usize)>) {
let mut tiles: Vec<_> = tiles.to_vec();
// determine puzzle dimension
let width = (0..tiles.len())
.find(|width| width * width == tiles.len())
.expect("No valid puzzle dimensions");
let mut solution: Vec<(Tile, usize)> = Vec::with_capacity(width * width);
// top left corner
let (top_left, t) = find_corner(&tiles);
solution.push((tiles.remove(top_left), t));
// top row
for k in 1..width {
// move on to the right => side = 1
let (tile1, t) = &solution[k - 1];
let (pos, t) = tiles
.iter()
.enumerate()
.map(|(pos, tile2)| (pos, tile1.matches(tile2, *t, 1)))
.filter_map(|(pos, t)| t.map(|t| (pos, t)))
.next()
.unwrap();
solution.push((tiles.remove(pos), t));
}
for y in 1..width {
// first element in row, move down from previous row => side = 2
let (tile1, t) = &solution[width * (y - 1)];
let (pos, t) = tiles
.iter()
.enumerate()
.map(|(pos, tile2)| (pos, tile1.matches(tile2, *t, 2)))
.filter_map(|(pos, t)| t.map(|t| (pos, t)))
.next()
.unwrap();
solution.push((tiles.remove(pos), t));
for x in 1..width {
// find tiles which match to the left and to the top
let idx = x + width * y;
let (tile_up, t_up) = &solution[idx - width];
let (tile_left, t_left) = &solution[idx - 1];
let (pos, t) = tiles
.iter()
.enumerate()
.map(|(pos, tile2)| {
(
pos,
tile_up.matches(tile2, *t_up, 2),
tile_left.matches(tile2, *t_left, 1),
)
})
.filter(|(_, t_up, t_left)| t_up == t_left)
.filter_map(|(pos, t, _)| t.map(|t| (pos, t)))
.next()
.unwrap();
solution.push((tiles.remove(pos), t))
}
}
(width, solution)
}
For the second part, the picture is constructed as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
pub fn get_picture(width: usize, solution: &[(Tile, usize)]) -> Tile {
let n = solution[1].0.n;
let w = width * (n - 2);
let mut picture = Vec::with_capacity(w * w);
for _ in 0..w * w {
picture.push('.')
}
for row in 0..width {
for col in 0..width {
let (tile, t) = &solution[col + width * row];
for y_tile in 1..n - 1 {
let y = row * (n - 2) + y_tile - 1;
for x_tile in 1..n - 1 {
picture[col * (n - 2) + x_tile - 1 + w * y] = tile.get(x_tile + n * y_tile, *t);
}
}
}
}
Tile {
id: 0,
n: w,
data: picture,
}
}
And the monster is searched in the picture using
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 find_pattern(
&self,
t: usize,
pattern: &[char],
width: usize,
idx0: usize,
) -> Option<usize> {
let w_pat = width;
let h_pat = pattern.len() / w_pat;
let n_tile = self.n;
let mut idx_tile_start = idx0;
loop {
if idx_tile_start / n_tile + h_pat > n_tile {
// pattern height does not fit, give up
break;
}
if idx_tile_start % n_tile + w_pat > n_tile {
// pattern width does not fit, go to next row
idx_tile_start = n_tile * (idx_tile_start / n_tile + 1);
continue;
}
let mut found = true;
for (idx_pat, _) in pattern.iter().enumerate().filter(|(_, &pat)| pat != ' ') {
// determine idx in tile
let x_pat = idx_pat % w_pat;
let y_pat = idx_pat / w_pat;
let idx_tile = idx_tile_start + x_pat + y_pat * n_tile;
// apply transformation
if self.get(idx_tile, t) != '#' {
// no '#' => not found
found = false;
break;
}
}
// still found after all checks => match
if found {
return Some(idx_tile_start);
}
// search in next position
idx_tile_start += 1;
}
// nothing found
None
}
}
I was happy that the monsters do not overlap (at least in my case). That made calculating the roughness very easy:
1
2
3
4
5
pub fn get_roughness(picture: &Tile, monsters: usize) -> usize {
let a = MONSTER.chars().filter(|c| *c != ' ').count();
let b = picture.data.iter().filter(|c| **c == '#').count();
b - monsters * a
}
Solution Revisited
I still wanted to get my solution idea implemented, where I just start from an arbitrary tile and expand in both directions. So I implemented this as a solution variant. Don’t know what I got wrong in the first place. Works now, a bit faster than my original solution as expected ;)
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
/// Appends tiles to solution until no more tile is found
///
/// Works in two directions, depending on argument `fwd`
///
/// If solution length is larger than `w`, next tiles are checked against neighbor in row above
/// if `fwd` is `true` or row below if `fwd` is false.
///
/// If neighbor from other row matches and direct neighbor does not match, new row is assumed. The
/// function does not check that each row actually has `width` elements, which should be the case
/// for a well formed problem.
#[cfg(not(feature = "variant2"))]
fn append(
solution: &mut std::collections::VecDeque<(Tile, usize)>,
tiles: &mut Vec<Tile>,
w: usize,
fwd: bool,
) {
// determine search directions
let (s_n, s_o) = if fwd { (1, 2) } else { (3, 0) };
while !tiles.is_empty() {
// neighbor and other row elements
let ((tile_n, t_n), other) = if fwd {
(solution.back().unwrap(), solution.get(solution.len() - w))
} else {
(solution.front().unwrap(), solution.get(w - 1))
};
// find matching tile with transformation
// there are three cases when an element matches
// a) neighbor matches, there is no other -> add in first row
// b) neighbor and other match with same transformation -> add in same row
// c) neighbor does not match, other matches -> add in next row
match tiles
.iter()
.enumerate()
.filter_map(|(pos, tile)| {
match (
tile_n.matches(tile, *t_n, s_n),
other.and_then(|(tile_o, t_o)| tile_o.matches(tile, *t_o, s_o)),
) {
(Some(ta), None) if other.is_none() => Some((pos, ta)),
(Some(ta), Some(tb)) if ta == tb => Some((pos, ta)),
(None, Some(tb)) => Some((pos, tb)),
_ => None,
}
})
.next()
.map(|(pos, t)| (tiles.remove(pos), t))
{
Some(value) if fwd => solution.push_back(value),
Some(value) => solution.push_front(value),
_ => break,
}
}
}
#[cfg(not(feature = "variant2"))]
pub fn solve(Tiles(tiles): &Tiles) -> (usize, Vec<(Tile, usize)>) {
let mut tiles: Vec<_> = tiles.to_vec();
// determine puzzle dimension
let width = (0..tiles.len())
.find(|width| width * width == tiles.len())
.expect("No valid puzzle dimensions");
// start solution from an arbitrary tile and extend backward and forward
let mut solution = std::collections::VecDeque::with_capacity(width * width);
solution.push_front((tiles.pop().unwrap(), 0));
append(&mut solution, &mut tiles, width, false);
append(&mut solution, &mut tiles, width, true);
// may need to iterate because row wrap may not work in the first round
append(&mut solution, &mut tiles, width, false);
// all tiles shall be consumed here
assert_eq!(tiles.len(), 0);
// convert from VecDeque<_> to Vec<_>
let solution = solution.into_iter().collect();
(width, solution)
}
Art work
Day 21: Allergen Assessment
Rust solution to AoC|2020|21.
Input
Parse the input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
pub mod input {
use std::collections::HashSet;
#[derive(Debug)]
pub struct PuzzleData<'a> {
pub foods: Vec<(HashSet<&'a str>, HashSet<&'a str>)>,
}
impl<'a> From<&'a str> for PuzzleData<'a> {
/// parse the puzzle input
fn from(s: &'a str) -> Self {
Self {
foods: s
.lines()
.map(|line| {
let mut parts = line.split(" (contains ");
let ingredients: HashSet<_> =
parts.next().expect("No ingredients").split(' ').collect();
let allergens: HashSet<_> = parts
.next()
.map(|part| part[..part.len() - 1].split(", ").collect())
.unwrap_or_default();
(ingredients, allergens)
})
.collect(),
}
}
}
}
Star 1
First, build a map with allergens as keys and lists of candidate ingredients as values by checking for every allergen which ingredients are contained in all foods that contain the allergen:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// Constructs a map with all allergens as keys and sets of candidate ingredients as values
pub fn build_allergen_map<'a>(data: &PuzzleData<'a>) -> HashMap<&'a str, HashSet<&'a str>> {
let mut allergen_map: HashMap<&str, HashSet<&str>> = HashMap::new();
for (ingredients, allergens) in &data.foods {
for &allergen in allergens {
match allergen_map.entry(allergen) {
Entry::Occupied(mut o) => o.get_mut().retain(|c| ingredients.contains(c)),
Entry::Vacant(v) => {
v.insert(ingredients.clone());
}
}
}
}
allergen_map
}
The union of all the candidate ingredients is the set of ingredients which contain allergens, everything not contained in this union is safe.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// Count ingredients without allergens
pub fn count_without_allergens(
foods: &[(HashSet<&str>, HashSet<&str>)],
allergen_map: &HashMap<&str, HashSet<&str>>,
) -> usize {
let with_allergens: HashSet<&str> = HashSet::from_iter(
allergen_map
.values()
.flat_map(|ingredients| ingredients.iter().map(Deref::deref)),
);
foods
.iter()
.flat_map(|(ingredients, _)| ingredients.iter())
.filter(|&ingredient| !with_allergens.contains(ingredient))
.count()
}
1
2
3
pub fn star_1(data: &PuzzleData) -> SolType1 {
count_without_allergens(&data.foods, &build_allergen_map(data))
}
Star 2
In the next step, the allergen map is reduced to map each allergen to exactly one ingredient iteratively. In each iteration, the ingredients mapped to settled allergens are removed from the candidate lists, and the allergens with candidate lists of length 1 are settled.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/// Reduce the map allergen -> ingredient candidates to a map allergen -> ingredient
pub fn reduce_allergen_map<'a>(
mut map: HashMap<&'a str, HashSet<&'a str>>,
) -> HashMap<&'a str, &'a str> {
let mut reduced: HashMap<&str, &str> = HashMap::new();
let mut changed = true;
while changed {
changed = false;
for (allergen, ingredients) in &mut map {
for ingredient in reduced.values() {
ingredients.remove(ingredient);
}
debug_assert!(
!ingredients.is_empty(),
"No remaining ingredients for {}",
allergen
);
if ingredients.len() == 1 {
reduced.insert(allergen, ingredients.iter().next().unwrap());
changed = true;
}
}
map.retain(|allergen, _| !reduced.contains_key(allergen));
}
debug_assert_eq!(map.len(), 0, "everything from map should be consumed");
reduced
}
Finally, the canonical dangerous ingredients list is assembled
1
2
3
4
5
6
7
8
9
10
pub fn star_2(data: &PuzzleData) -> SolType2 {
let mut list = reduce_allergen_map(build_allergen_map(data))
.into_iter()
.collect::<Vec<_>>();
list.sort_unstable();
list.iter()
.map(|(_, ingredient)| *ingredient)
.collect::<Vec<_>>()
.join(",")
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)
sqjhc fvjkl (contains soy)
sqjhc mxmxvkd sbzzf (contains fish)
"#;
#[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!(5, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!("mxmxvkd,sqjhc,fvjkl", star_2(&data));
}
}
Day 22: Crab Combat
Rust solution to AoC|2020|22.
Solution
I was very happy to find a reference to AoC|2019|22, one of my all-time favorites.
The solution for today was however not really related to the solution of last year’s Slam Shuffle.
Part 1 - the warm-up
Non-recursive Combat
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
/// Play Combat
///
/// Returns a tuple of a flag indicating the winning player (true for player 1, false for player
/// two) and the winning player's score
pub fn play(mut decks: (VecDeque<usize>, VecDeque<usize>)) -> (bool, usize) {
while !decks.0.is_empty() && !decks.1.is_empty() {
let a = decks.0.pop_front().unwrap();
let b = decks.1.pop_front().unwrap();
if a > b {
decks.0.push_back(a);
decks.0.push_back(b);
} else {
decks.1.push_back(b);
decks.1.push_back(a);
}
}
(
!decks.0.is_empty(),
calc_score(if decks.0.is_empty() {
&decks.1
} else {
&decks.0
}),
)
}
Part 2 - slightly more tricky
Recursive Combat
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
/// Play Recursive Combat
///
/// Returns a tuple of a flag indicating the winning player (true for player 1, false for player
/// two) and the winning player's score
pub fn play_recursive(mut decks: (VecDeque<usize>, VecDeque<usize>)) -> (bool, usize) {
// holds games played before
let mut seen = HashSet::new();
while !decks.0.is_empty() && !decks.1.is_empty() {
// make sure game does not repeat
if seen.contains(&decks) {
return (true, calc_score(&decks.0));
}
seen.insert(decks.clone());
// deal first card
let a = decks.0.pop_front().unwrap();
let b = decks.1.pop_front().unwrap();
let mut a_wins = a > b;
if a <= decks.0.len() && b <= decks.1.len() {
// recurse
a_wins = play_recursive((
decks.0.iter().take(a).cloned().collect(),
decks.1.iter().take(b).cloned().collect(),
))
.0;
}
// winner takes cards
if a_wins {
decks.0.push_back(a);
decks.0.push_back(b);
} else {
decks.1.push_back(b);
decks.1.push_back(a);
}
}
(
!decks.0.is_empty(),
calc_score(if decks.0.is_empty() {
&decks.1
} else {
&decks.0
}),
)
}
Day 23: Crab Cups
Rust solution to AoC|2020|23.
Solution
Linked Lists does not seem to be a concept Rustacians like a lot. Googling for linked lists in Rust, you find a lot of explanations why you should not use them…
My solution models the ring of cups using an array indexed by cup labels whose values are successor’s cup labels.
The ring is initialized as follows:
1
2
3
4
5
6
7
8
9
10
fn init_ring(ring: &mut [usize], labels: &[usize]) -> usize {
let len = ring.len();
let f = || labels.iter().cloned().chain(labels.len()..len);
for (current, next) in f().zip(f().cycle().skip(1)) {
ring[current] = next;
}
f().next().unwrap()
}
The function play_round simulates a single round.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fn play_round(ring: &mut [usize], current: usize) -> usize {
let cup1 = ring[current];
let cup2 = ring[cup1];
let cup3 = ring[cup2];
let mut dest = (current + ring.len() - 1) % ring.len();
while dest == cup1 || dest == cup2 || dest == cup3 {
dest = (dest + ring.len() - 1) % ring.len();
}
// current - cup1 - cup2 - cup3 - after-cup3 ... dest - after-dest
// current - after-cup3 ... dest - cup1 - cup2 - cup3 - after-dest
ring[current] = ring[cup3];
ring[cup3] = ring[dest];
ring[dest] = cup1;
ring[current]
}
Star 1 / 2
Essentially initialize ring and play rounds. For star 2, the data does not fit to the stack; we use to have a vec instead of an array.
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(data: &PuzzleData) -> usize {
let mut ring = [0; 9];
let mut current = init_ring(&mut ring, data.labels());
for _ in 0..100 {
current = play_round(&mut ring, current);
}
successors(Some(ring[0]), |&c| match ring[c] {
0 => None,
n => Some(n),
})
.fold(0, |r, c| 10 * r + c + 1)
}
pub fn star_2(data: &PuzzleData) -> usize {
let mut ring = vec![0; 1_000_000];
let mut current = init_ring(&mut ring, data.labels());
for _ in 0..10_000_000 {
current = play_round(&mut ring, current);
}
(ring[0] + 1) * (ring[ring[0]] + 1)
}
Tests
As usual …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"389125467"#;
#[test]
pub fn test_star_1() {
let data = PuzzleData::from(CONTENT);
assert_eq!(67_384_529, star_1(&data));
}
#[test]
pub fn test_star_2() {
let data = PuzzleData::from(CONTENT);
assert_eq!(149_245_887_792, star_2(&data));
}
#[test]
pub fn test_parse() {
let data = PuzzleData::from(CONTENT);
assert_eq!([2, 7, 8, 0, 1, 4, 3, 5, 6], data.labels());
}
#[test]
pub fn test_init_ring() {
let mut ring = [0; 9];
init_ring(&mut ring, &[2, 7, 8, 0, 1, 4, 3, 5, 6]);
assert_eq!([1, 4, 7, 5, 3, 6, 2, 8, 0], ring);
}
#[test]
pub fn test_play_round() {
let mut ring = [0; 9];
let mut exp = [0; 9];
let mut current = init_ring(&mut ring, PuzzleData::from(CONTENT).labels());
let exps = vec![
("328915467", 1),
("325467891", 4),
("725891346", 7),
("325846791", 3),
("925841367", 0),
("725841936", 8),
("836741925", 1),
("741583926", 5),
("574183926", 4),
("583741926", 7),
];
for (exp_cups, exp_current) in exps {
init_ring(&mut exp, PuzzleData::from(exp_cups).labels());
current = play_round(&mut ring, current);
assert_eq!(exp, ring);
assert_eq!(exp_current, current);
}
}
}
Day 24: Lobby Layout
Rust solution to AoC|2020|24.
Solution
I use (x, y) coordinates where adjacent columns (east/west) have a distance of two and adjacent rows have a distance of 1 in y direction and all tiles have an offset of +/- 1 in x direction.
The first step is to read the input and map every line to the coordinates the path leads to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn get_coords(content: &str) -> Vec<(i32, i32)> {
let re = Regex::new(r"(e)|(se)|(sw)|(w)|(nw)|(ne)").expect("Illegal regex");
content
.lines()
.map(|line| {
re.find_iter(line)
.fold((0, 0), |(x, y), m| match m.as_str() {
"e" => (x + 2, y),
"se" => (x + 1, y + 1),
"sw" => (x - 1, y + 1),
"w" => (x - 2, y),
"nw" => (x - 1, y - 1),
"ne" => (x + 1, y - 1),
_ => panic!("Illegal direction: {:?}", m),
})
})
.collect()
}
For part one, I add all the coordinates to a set. If a coordinate is seen for the second time, it is removed again.
1
2
3
4
5
6
7
8
9
pub fn flip_tiles(coords: &[(i32, i32)]) -> HashSet<(i32, i32)> {
let mut blacks = HashSet::new();
coords.iter().for_each(|value| {
if !blacks.remove(value) {
blacks.insert(*value);
}
});
blacks
}
For part two, I apply update steps repeatedly.
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
pub fn update_step(blacks: &HashSet<(i32, i32)>) -> HashSet<(i32, i32)> {
// determine bounds
let (min_x, max_x, min_y, max_y) = blacks.iter().fold(
(i32::MAX, i32::MIN, i32::MAX, i32::MIN),
|(min_x, max_x, min_y, max_y), (x, y)| {
(
min(min_x, *x),
max(max_x, *x + 1),
min(min_y, *y),
max(max_y, *y + 1),
)
},
);
// closure to check whether tile at coordinate is black, pre-check range
let is_black = |(x, y)| {
(min_x..max_x).contains(&x) && (min_y..max_y).contains(&y) && blacks.contains(&(x, y))
};
// even row: lowest even x >= min_x - 1; odd row: lowest odd x >= min_x - 1
let off_min_x = if min_x & 1 == 0 { [0, 1] } else { [1, 0] };
let mut blacks_upd = HashSet::new();
for y in min_y - 1..max_y + 1 {
for x in (min_x - off_min_x[(y & 1) as usize]..max_x + 1).step_by(2) {
// is currently black
let black = is_black((x, y));
// count black adjacents; if 3 found stop counting
let cnt = DELTAS
.iter()
.filter(|&(dx, dy)| is_black((x + dx, y + dy)))
.take(3)
.count();
// apply update rules
if (black && cnt == 1) || cnt == 2 {
blacks_upd.insert((x, y));
}
}
}
blacks_upd
}
Day 25: Combo Breaker
Rust solution to AoC|2020|25.
Solution
50 Stars collected! Vacation on that nice tropical island ready to start!
-
Read two public keys from a file
-
Determine the loop size for the second public key with linear search (function
find_loop_size) -
Transform the first public key with that loop size (function
transform)
The last two steps are combined in function get_encryption_key
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
/// transform: `subject -> (subject^loop_size) % `[`MOD`]
///
/// Just because it is possible, I implemented a recursive O(log(n)) solution.
pub fn transform(subject: usize, loop_size: usize) -> usize {
if loop_size == 0 {
return 1;
}
let mut result = transform(subject, loop_size >> 1);
result = (result * result) % MOD;
if loop_size & 1 > 0 {
result = (result * subject) % MOD;
}
result
}
/// find the loop size which transforms the given `subject` to the given `result`
///
/// See [Discrete Logarithm](https://en.wikipedia.org/wiki/Discrete_logarithm) on Wikipedia
pub fn find_loop_size(subject: usize, result: usize) -> usize {
let mut cnt = 1;
let mut val = subject;
while val != result {
val = (val * subject) % MOD;
cnt += 1;
}
cnt
}
/// recover encryption key from two public keys
pub fn get_encryption_key(&PuzzleData(key_1, key_2): &PuzzleData) -> SolType1 {
transform(key_1, find_loop_size(SUBJECT, key_2))
}