Day 1: No Time for a Taxicab
Rust solution to AoC|2016|1.
Star 1
Essentially an iter-fold to find the final coordinate.
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_1(input: &&str) -> SolType {
let (_, (x, y)) = input
.trim()
.split(',')
.map(str::trim)
.map(|step| (step.as_bytes()[0], step[1..].parse::<SolType>().unwrap()))
.fold((1, (0, 0)), |(d, (x, y)), (t, n)| {
let d = match t {
b'L' => (d + 1) & 3,
b'R' => (d + 3) & 3,
_ => panic!("Bad direction {}", t as char),
};
match d {
0 => (0, (x + n, y)),
1 => (1, (x, y - n)),
2 => (2, (x - n, y)),
3 => (3, (x, y + n)),
_ => unreachable!(),
}
});
x.abs() + y.abs()
}
Star 2
To find the first coordinate that is visited twice, we need to consider all coordinates seen, not just the ones we finish at the end of an instruction.
The solution converts the relative turn directions in absolute directions in a first scan.
Then, the sequence is expanded to unit steps and in a second scan, the coordinates are calculated together with a unique flag, which is eventually used to find the first non-unique coordinate.
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 fn star_2(input: &&str) -> SolType {
let ((x, y), _) = input
.trim()
.split(',')
.map(str::trim)
.map(|step| (step.as_bytes()[0], step[1..].parse::<SolType>().unwrap()))
.scan(1, |d, (t, n)| {
*d = match t {
b'L' => (*d + 1) & 3,
b'R' => (*d + 3) & 3,
_ => panic!("Bad direction {}", t as char),
};
Some((*d, n))
})
.flat_map(|(d, n)| (0..n).map(move |_| d))
.scan(((0, 0), HashSet::from([(0, 0)])), |((x, y), seen), d| {
(*x, *y) = match d {
0 => (*x + 1, *y),
1 => (*x, *y - 1),
2 => (*x - 1, *y),
3 => (*x, *y + 1),
_ => unreachable!(),
};
Some(((*x, *y), seen.insert((*x, *y))))
})
.find(|(_, unique)| !unique)
.unwrap();
SolType::abs(x) + SolType::abs(y)
}
Day 2: Bathroom Security
Rust solution to AoC|2016|2.
I need to go to the bathroom. Now! Really!!
Input
1
2
3
4
5
6
7
8
9
10
pub mod input {
#[derive(Debug)]
pub struct PuzzleData<'a>(pub Vec<&'a [u8]>);
impl<'a> From<&'a str> for PuzzleData<'a> {
fn from(s: &'a str) -> Self {
Self(s.lines().map(str::as_bytes).collect())
}
}
}
Star 1
iter-scan-fold
The scan is to iterate over numbers, the fold is to iterate over steps to find the next number.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pub fn star_1(PuzzleData(digits): &PuzzleData) -> SolType1 {
digits
.iter()
.scan(4usize, |p, &steps| {
let (x, y) = steps
.iter()
.fold((*p % 3, *p / 3), |(x, y), &step| match step {
b'R' => ((x + 1).min(2), y),
b'U' => (x, y - 1.min(y)),
b'L' => (x - 1.min(x), y),
b'D' => (x, (y + 1).min(2)),
_ => panic!("Unexpected step {}", step as char),
});
*p = x + 3 * y;
Some(*p + 1)
})
.fold(0, |v, k| 10 * v + k)
}
Star 2
The layout of the keypad is stored in GRID. Illegal positions of the grid are marked with hashes (#). Making the grid larger than needed and filling it with hashes, we spare us from range checks.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const GRID: &[u8] = b"##########1#####234###56789###ABC#####D##########";
const W: usize = 7;
pub fn star_2(PuzzleData(digits): &PuzzleData) -> SolType2 {
let p = GRID.iter().position(|&b| b == b'5').unwrap();
digits
.iter()
.scan(p, |p, &steps| {
let (x, y) = steps
.iter()
.fold((*p % W, *p / W), |(x, y), &step| match step {
b'R' if GRID[x + 1 + W * y] != b'#' => (x + 1, y),
b'U' if GRID[x + W * (y - 1)] != b'#' => (x, y - 1),
b'L' if GRID[x - 1 + W * y] != b'#' => (x - 1, y),
b'D' if GRID[x + W * (y + 1)] != b'#' => (x, y + 1),
_ => (x, y),
});
*p = x + W * y;
Some(GRID[*p] as char)
})
.collect()
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"ULL
RRDDD
LURDL
UUUUD
"#;
#[test]
pub fn test_star_1() {
assert_eq!(1985, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!("5DB3", star_2(&CONTENT.into()));
}
}
Day 3: Squares With Three Sides
Rust solution to AoC|2016|3.
Find possible triangles in rows and columns.
Input
All numbers are read into a flat list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub mod input {
use crate::SolType1;
#[derive(Debug)]
pub struct PuzzleData(pub Vec<SolType1>, pub usize);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(
s.trim()
.split_ascii_whitespace()
.map(str::parse)
.collect::<Result<_, _>>()
.unwrap(),
3,
)
}
}
}
Star 1
Straight forward…
1
2
3
4
5
6
7
pub fn star_1(PuzzleData(list, _): &PuzzleData) -> SolType1 {
(0..list.len())
.step_by(3)
.map(|k| (list[k], list[k + 1], list[k + 2]))
.filter(|&(a, b, c)| a < b + c && b < c + a && c < a + b)
.count()
}
Star 2
Process numbers in columns in 3x3 blocks.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub fn star_2(PuzzleData(list, w): &PuzzleData) -> SolType2 {
(0..list.len() / w)
.step_by(3)
.flat_map(|y| {
(0..*w).map(move |x| {
(
list[x + w * y],
list[x + w * (y + 1)],
list[x + w * (y + 2)],
)
})
})
.filter(|&(a, b, c)| a < b + c && b < c + a && c < a + b)
.count()
}
Day 4: Security Through Obscurity
Rust solution to AoC|2016|4.
Decrypt room names
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
pub mod input {
use crate::SolType;
#[derive(Debug)]
pub struct PuzzleData<'a>(pub Vec<(&'a [u8], SolType, &'a [u8])>);
impl<'a> From<&'a str> for PuzzleData<'a> {
fn from(s: &'a str) -> Self {
Self(
s.lines()
.map(|l| {
let d = l.find(|c: char| c.is_ascii_digit()).unwrap();
let (a, b) = l[d..].split_once('[').unwrap();
(
l[0..d - 1].as_bytes(),
a.parse().unwrap(),
b.trim_end_matches(']').as_bytes(),
)
})
.collect(),
)
}
}
}
Star 1
Check validity by counting symbols and comparing the most common ones with the checksum.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub fn is_real(&(name, _, checksum): &(&[u8], SolType, &[u8])) -> bool {
let mut chars =
name.iter()
.copied()
.filter(|&b| b != b'-')
.fold(vec![(0u32, 0); 26], |mut v, b| {
v[(b - b'a') as usize] = (v[(b - b'a') as usize].0 + 1, b);
v
});
chars.sort_unstable_by_key(|&(cnt, b)| (!cnt, b));
checksum
.iter()
.zip(chars.iter())
.all(|(&a, &(_, b))| a == b)
}
pub fn star_1(PuzzleData(rooms): &PuzzleData) -> SolType {
rooms
.iter()
.copied()
.filter(is_real)
.map(|(_, id, _)| id)
.sum()
}
Star 2
Adding decryption is straight forward. It is not helpful that the problem statement asks for "north pole" written as two words while the decoded name contains "northpole" as a single word.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pub fn decrypt((name, id, _): (&[u8], SolType, &[u8])) -> String {
name.iter()
.map(|&b| match b {
b'-' => ' ',
_ => ((((b - b'a') as SolType + id) % 26) as u8 + b'a') as char,
})
.collect()
}
pub fn star_2(PuzzleData(rooms): &PuzzleData) -> SolType {
rooms
.iter()
.copied()
.filter(is_real)
.find(|&room| decrypt(room).contains("northpole"))
.map(|(_, id, _)| id)
.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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"aaaaa-bbb-z-y-x-123[abxyz]
a-b-c-d-e-f-g-h-987[abcde]
not-a-real-room-404[oarel]
totally-real-room-200[decoy]
"#;
#[test]
pub fn test_from() {
let PuzzleData(rooms) = PuzzleData::from(CONTENT);
assert_eq!(
vec![
("aaaaa-bbb-z-y-x".as_bytes(), 123, "abxyz".as_bytes()),
("a-b-c-d-e-f-g-h".as_bytes(), 987, "abcde".as_bytes()),
("not-a-real-room".as_bytes(), 404, "oarel".as_bytes()),
("totally-real-room".as_bytes(), 200, "decoy".as_bytes())
],
rooms
);
}
#[test]
pub fn test_star_1() {
assert_eq!(1_514, star_1(&CONTENT.into()));
}
#[test]
pub fn test_decrypt() {
assert_eq!(
"very encrypted name",
decrypt((b"qzmt-zixmtkozy-ivhz", 343, b""))
)
}
}
Day 5: How About a Nice Game of Chess?
Rust solution to AoC|2016|5.
MD5 hashes
Star 1
Create an iterator that only returns interesting hashes and take the first 8 values.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const HEX_CHARS: &[u8] = b"0123456789abcdef";
pub fn star_1(salt: &&str) -> SolType {
let salt = salt.trim().as_bytes();
let mut hasher = Md5::new();
let mut hash = [0; 16];
(0..)
.filter_map(|k| {
hasher.update(salt);
hasher.update(k.to_string().as_bytes());
hasher.finalize_into_reset((&mut hash).into());
match (hash[0], hash[1], hash[2] >> 4) {
(0, 0, 0) => Some(HEX_CHARS[(hash[2] & 15) as usize] as char),
_ => None,
}
})
.take(8)
.collect()
}
Star 2
Iterating gets a bit more complicated, but essentially, the idea is identical to 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
pub fn star_2(salt: &&str) -> SolType {
let salt = salt.trim().as_bytes();
let mut hasher = Md5::new();
let mut hash = [0; 16];
(0..)
.filter_map(|k| {
hasher.update(salt);
hasher.update(k.to_string().as_bytes());
hasher.finalize_into_reset((&mut hash).into());
match (hash[0], hash[1], hash[2] >> 4, hash[2] & 15) {
(0, 0, 0, v) if v < 8 => Some((v, HEX_CHARS[(hash[3] >> 4) as usize])),
_ => None,
}
})
.scan(0, |s, (p, b)| {
let nxt = Some((*s, p, b));
*s |= 1 << p;
nxt
})
.take_while(|&(s, _, _)| s < 255)
.filter(|&(s, p, _)| (s >> p) & 1 == 0)
.fold(vec!['_'; 8], |mut res, (_, p, b)| {
res[p as usize] = b as char;
res
})
.iter()
.collect()
}
Day 6: Signals and Noise
Rust solution to AoC|2016|6.
Star 1
Count for each position how often each letter appears and take the maximum.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fn solve<F: Fn(&[u32; 26], usize) -> u32>(data: &str, f: F) -> SolType {
let w = data.find('\n').unwrap();
data.lines()
.fold(vec![[0; 26]; w], |mut counts, l| {
for (k, b) in l.bytes().enumerate() {
counts[k][(b - b'a') as usize] += 1
}
counts
})
.iter()
.filter_map(|counts| {
(0..counts.len())
.max_by_key(|&p| f(counts, p))
.map(|p| (p as u8 + b'a') as char)
})
.collect::<String>()
}
pub fn star_1(data: &&str) -> SolType {
solve(data, |counts, p| counts[p])
}
Star 2
Count for each position how often each letter appears and take the minimum of those which appear at least once. This is achieved by taking the maximum over the inverse count (!count = u32::MAX - count) for positive counts and 0 otherwise.
The solution for parts 1 and 2 is made generic by passing the target function to maximize as an argument.
1
2
3
4
5
6
pub fn star_2(data: &&str) -> SolType {
solve(
data,
|counts, p| if counts[p] == 0 { 0 } else { !counts[p] },
)
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"eedadn
drvtee
eandsr
raavrd
atevrs
tsrnev
sdttsa
rasrtv
nssdts
ntnada
svetve
tesnvt
vntsnd
vrdear
dvrsen
enarar
"#;
#[test]
pub fn test_star_1() {
assert_eq!("easter", star_1(&CONTENT));
}
#[test]
pub fn test_star_2() {
assert_eq!("advent", star_2(&CONTENT));
}
}
Day 7: Internet Protocol Version 7
Rust solution to AoC|2016|7.
Check whether 'IP addresses' have patterns indicating they support 'TLS' / 'SSL'
Star 1
Fold into bits, n-th bit is set to 1 if 'ABBA' is found at nesting level n. The IP supports TLS if there is an 'ABBA' at nesting level 0 but not at any higher nesting levels.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn supports_tls(ip: &[u8]) -> bool {
(0..ip.len() - 3).fold((0, 0), |(b, s), k| match ip[k] {
b'[' => (b + 1, s),
b']' => (b - 1, s),
_ => (
b,
s | ((ip[k] == ip[k + 3] && ip[k + 1] == ip[k + 2] && ip[k] != ip[k + 1]) as u32) << b,
),
}) == (0, 1)
}
pub fn star_1(ips: &&str) -> SolType {
ips.lines().filter(|ip| supports_tls(ip.as_bytes())).count()
}
Star 2
Collect ABAs and BABs in sets. As soon as a match is found, return true.
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 supports_ssl(ip: &[u8]) -> bool {
let mut abas = HashSet::new();
let mut babs = HashSet::new();
let mut b = 0;
for k in 0..ip.len() - 2 {
match ip[k] {
b'[' => b += 1,
b']' => b -= 1,
v if v != ip[k + 1] && v == ip[k + 2] && ip[k + 1] != b'[' && ip[k + 1] != b']' => {
let (chk, ins, v) = match b {
0 => (&babs, &mut abas, &ip[k..k + 2]),
_ => (&abas, &mut babs, &ip[k + 1..k + 3]),
};
if chk.contains(&v) {
return true;
}
ins.insert(v);
}
_ => (),
}
}
false
}
pub fn star_2(ips: &&str) -> SolType {
ips.lines().filter(|ip| supports_ssl(ip.as_bytes())).count()
}
Day 8: Two-Factor Authentication
Rust solution to AoC|2016|8.
Implement a 'display driver' and decode letters on display.
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 {
use crate::Instr;
#[derive(Debug)]
pub struct PuzzleData(pub Vec<Instr>);
impl From<&str> for Instr {
fn from(s: &str) -> Self {
if let Some(s) = s.strip_prefix("rect ") {
s.split_once('x')
.map(|(a, b)| Self::Rect(a.parse().unwrap(), b.parse().unwrap()))
.unwrap()
} else if let Some(s) = s.strip_prefix("rotate row y=") {
s.split_once(" by ")
.map(|(a, b)| Self::Right(a.parse().unwrap(), b.parse().unwrap()))
.unwrap()
} else if let Some(s) = s.strip_prefix("rotate column x=") {
s.split_once(" by ")
.map(|(a, b)| Self::Down(a.parse().unwrap(), b.parse().unwrap()))
.unwrap()
} else {
panic!("Unexpected content: {}", s);
}
}
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(s.lines().map(Instr::from).collect())
}
}
}
#[derive(Debug, PartialEq, Eq)]
pub enum Instr {
Rect(usize, usize),
Down(usize, usize),
Right(usize, usize),
}
Star 1
Run the instructions and count lit pixels.
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 fn display(w: usize, h: usize, list: &[Instr]) -> Vec<u8> {
list.iter().fold(vec![b'.'; w * h], |mut d, e| {
match *e {
Instr::Rect(cols, rows) => {
for y in 0..rows {
d[w * y..w * y + cols].fill(b'#')
}
}
Instr::Down(x, n) => {
let temp = (0..n).map(|y| d[x + w * y]).collect::<Vec<_>>();
for y in (n..h).rev() {
d[x + w * ((y + n) % h)] = d[x + w * y];
}
for y in 0..n {
d[x + w * ((y + n) % h)] = temp[y];
}
}
Instr::Right(y, n) => d[y * w..(y + 1) * w].rotate_right(n),
}
d
})
}
pub fn star_1(PuzzleData(list): &PuzzleData) -> SolType1 {
display(50, 6, list)
.into_iter()
.filter(|&b| b == b'#')
.count()
}
Star 2
Run the instructions and decode letters using mr_kaffee_aoc::letters::decode.
1
2
3
pub fn star_2(PuzzleData(list): &PuzzleData) -> SolType2 {
display(50, 6, list).decode(0).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#"rect 3x2
rotate column x=1 by 1
rotate row y=0 by 4
rotate column x=1 by 1
"#;
#[test]
pub fn test_from() {
let PuzzleData(instructions) = PuzzleData::from(CONTENT);
assert_eq!(
vec![
Instr::Rect(3, 2),
Instr::Down(1, 1),
Instr::Right(0, 4),
Instr::Down(1, 1)
],
instructions
);
}
#[test]
pub fn test_display() {
let PuzzleData(instructions) = PuzzleData::from(CONTENT);
let d = display(7, 3, &instructions[0..1]);
assert_eq!("###....###...........".as_bytes(), d, "Step 1");
let d = display(7, 3, &instructions[0..2]);
assert_eq!("#.#....###.....#.....".as_bytes(), d, "Step 2");
let d = display(7, 3, &instructions[0..3]);
assert_eq!("....#.####.....#.....".as_bytes(), d, "Step 3");
let d = display(7, 3, &instructions[0..4]);
assert_eq!(".#..#.##.#.....#.....".as_bytes(), d, "Step 4");
}
}
Day 9: Explosives in Cyberspace
Rust solution to AoC|2016|9.
Calculate decompressed data length
Star 1
Find markers and calculate decompressed length.
The recurse argument to the solve function is used for part 2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
pub fn solve(s: &[u8], recurse: bool) -> SolType {
let mut len = 0;
let mut p = 0;
while p < s.len() {
if s[p] == b'(' {
p += 1; // skip '('
let (l, sub_len) = (p..)
.take_while(|&p| s[p] != b'x')
.fold((0, 0), |(l, v), p| {
(l + 1, 10 * v + (s[p] - b'0') as SolType)
});
p += l + 1;
let (l, sub_times) = (p..)
.take_while(|&p| s[p] != b')')
.fold((0, 0), |(l, v), p| {
(l + 1, 10 * v + (s[p] - b'0') as SolType)
});
p += l + 1;
if recurse {
len += sub_times * solve(&s[p..p + sub_len as usize], true)
} else {
len += sub_times * sub_len
}
p += sub_len as usize;
} else {
len += 1;
p += 1;
}
}
len
}
pub fn star_1(data: &&str) -> SolType {
solve(data.trim().as_bytes(), false)
}
Star 2
Modify the solution from part one to recursively calculate the length for data sections of markers.
1
2
3
pub fn star_2(data: &&str) -> SolType {
solve(data.trim().as_bytes(), true)
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#[cfg(test)]
mod tests {
use super::*;
#[test]
pub fn test_star_1() {
assert_eq!(11, star_1(&"A(2x2)BCD(2x2)EFG"));
assert_eq!(18, star_1(&"X(8x2)(3x3)ABCY"));
}
#[test]
pub fn test_star_2() {
assert_eq!(20, star_2(&"X(8x2)(3x3)ABCY"));
assert_eq!(
445,
star_2(&"(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN")
);
}
}
Day 10: Balance Bots
Rust solution to AoC|2016|10.
Observe bots distributing microchips…
Input
Parsing the inputs is a bit tedious.
The order of the rules seems arbitrary and does not seem to matter. The input is parsed into an inventory and a vector of rules. Both are indexed by bot IDs.
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 mod input {
use std::collections::BTreeSet;
use crate::SolType2;
#[derive(Debug)]
pub struct PuzzleData {
pub values: Vec<BTreeSet<SolType2>>,
pub rules: Vec<(bool, usize, bool, usize)>,
}
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let (values, rules) =
s.lines()
.fold((Vec::new(), Vec::new()), |(mut values, mut rules), l| {
let mut words = l.split_ascii_whitespace();
match words.next() {
Some("value") => {
let v = words.next().unwrap().parse().unwrap();
let bot = words.nth(3).unwrap().parse().unwrap();
if values.len() <= bot {
values.resize(bot + 1, BTreeSet::new());
}
values[bot].insert(v);
}
Some("bot") => {
let bot = words.next().unwrap().parse().unwrap();
let low_out = words.nth(3) == Some("output");
let low = words.next().unwrap().parse().unwrap();
let high_out = words.nth(3) == Some("output");
let high = words.next().unwrap().parse().unwrap();
if rules.len() <= bot {
rules.resize(bot + 1, (false, usize::MAX, false, usize::MAX));
}
rules[bot] = (low_out, low, high_out, high);
}
_ => panic!("Unexpected line: {}", l),
}
(values, rules)
});
Self { values, rules }
}
}
}
Star 1
Dispatch chips according to the rules until a bot is found that would dispatch chips numbered 17 and 61 (or 2 and 5 for the 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
pub fn solve_1(
PuzzleData { values, rules }: &PuzzleData,
(cmp_low, cmp_high): (SolType2, SolType2),
) -> SolType1 {
let mut values = values.to_owned();
while let Some(k) = values.iter().position(|v| v.len() == 2) {
let val_low = values[k].pop_first().unwrap();
let val_high = values[k].pop_last().unwrap();
if val_low == cmp_low && val_high == cmp_high {
return k;
}
let (out_low, low, out_high, high) = rules[k];
if !out_low {
values[low].insert(val_low);
}
if !out_high {
values[high].insert(val_high);
}
}
panic!("No solution");
}
pub fn star_1(data: &PuzzleData) -> SolType1 {
solve_1(data, (17, 61))
}
Star 2
Dispatch chips until there are no bots with two chips. Then multiply the values in the outputs.
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(PuzzleData { values, rules }: &PuzzleData) -> SolType2 {
let mut values = values.to_owned();
let mut outputs = [0; 3];
while let Some(k) = values.iter().position(|v| v.len() == 2) {
let val_low = values[k].pop_first().unwrap();
let val_high = values[k].pop_last().unwrap();
let (out_low, low, out_high, high) = rules[k];
if !out_low {
values[low].insert(val_low);
} else if low < 3 {
outputs[low] = val_low;
}
if !out_high {
values[high].insert(val_high);
} else if high < 3 {
outputs[high] = val_high;
}
}
outputs.iter().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
37
38
39
40
#[cfg(test)]
mod tests {
use std::collections::BTreeSet;
use super::*;
const CONTENT: &str = r#"value 5 goes to bot 2
bot 2 gives low to bot 1 and high to bot 0
value 3 goes to bot 1
bot 1 gives low to output 1 and high to bot 0
bot 0 gives low to output 2 and high to output 0
value 2 goes to bot 2
"#;
#[test]
pub fn test_from() {
let PuzzleData { values, rules } = PuzzleData::from(CONTENT);
assert_eq!(
vec![
BTreeSet::from([]),
BTreeSet::from([3]),
BTreeSet::from([5, 2])
],
values
);
assert_eq!(
vec![
(true, 2, true, 0),
(true, 1, false, 0),
(false, 1, false, 0)
],
rules
);
}
#[test]
pub fn test_solve_1() {
assert_eq!(2, solve_1(&CONTENT.into(), (2, 5)));
}
}
Day 11: Radioisotope Thermoelectric Generators
Rust solution to AoC|2020|1.
Bring objects to the upper floor safely. A variant of the Wolf, Goat, Cabbage riddle.
Solution
I spent a lot of time coming up with a building model
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
pub const CHIP: usize = 0;
pub const GENERATOR: usize = 1;
/// a pair of a chip and a generator
pub type ChipGenerator = [u8; 2];
pub type ElementIndex = [usize; 2];
/// a building's state
#[derive(PartialEq, Eq, Debug, Hash, Clone)]
pub struct Building {
chipgenerators: Vec<ChipGenerator>,
/// the elevator's floor
pub elevator: u8,
}
impl Building {
/// the number of floors (non-inclusive upper bound)
pub const FLOOR_MAX: u8 = 4;
/// check whether all floors are valid, i.e., [`Self::is_floor_valid`] returns `true` for all floors
pub fn is_valid(&self) -> bool {
(0..Self::FLOOR_MAX).all(|floor| self.is_floor_valid(floor))
}
/// check whether the given floor is valid
pub fn is_floor_valid(&self, floor: u8) -> bool {
let (solo_chips, generators) =
self.chipgenerators
.iter()
.fold(
(0, 0),
|(solo_chips, generators), chipgenerator| match chipgenerator
.map(|f| f == floor)
{
[true, false] => (solo_chips + 1, generators),
[_, true] => (solo_chips, generators + 1),
_ => (solo_chips, generators),
},
);
// a floor is valid if there are no solo chips or there are no generators and at
// most two (solo) chips. If more solo chips are on a floor, it is not possible to
// visit that floor with any generators in the future.
solo_chips == 0 || (generators == 0 && solo_chips <= 2)
}
fn increment(mut self, &[idx_cg, idx_t]: &ElementIndex) -> Option<Self> {
if self.chipgenerators[idx_cg][idx_t] < Building::FLOOR_MAX - 1 {
self.chipgenerators[idx_cg][idx_t] += 1;
Some(self)
} else {
None
}
}
fn decrement(mut self, &[idx_cg, idx_t]: &ElementIndex) -> Option<Self> {
if self.chipgenerators[idx_cg][idx_t] > 0 {
self.chipgenerators[idx_cg][idx_t] -= 1;
Some(self)
} else {
None
}
}
/// create and return canonical representation of this building's state
pub fn canonicalize(mut self) -> Self {
self.chipgenerators.sort_unstable();
self
}
/// call function `f` for each valid adjacent of this building's state
pub fn for_each_adjacent<F>(&self, mut f: F)
where
F: FnMut(Self),
{
// get list of all elements on floor where elevator is currently located
let element_indices = (0..self.chipgenerators.len())
.flat_map(|idx_cg| (0..2).map(move |idx_t| [idx_cg, idx_t]))
.filter(|&[idx_cg, idx_t]| self.chipgenerators[idx_cg][idx_t] == self.elevator)
.collect::<Vec<_>>();
for k1 in 0..element_indices.len() {
let element_idx_1 = &element_indices[k1];
// move single element up
if self.elevator < Self::FLOOR_MAX - 1 {
if let Some(mut b) = self
.clone()
.increment(element_idx_1)
.filter(Building::is_valid)
{
b.elevator += 1;
f(b.canonicalize());
}
}
// move single element down
if self.elevator > 0 {
if let Some(mut b) = self
.clone()
.decrement(&element_indices[k1])
.filter(Building::is_valid)
{
b.elevator -= 1;
f(b.canonicalize())
}
}
for element_idx_2 in &element_indices[k1 + 1..] {
// move two elements up
if self.elevator < Self::FLOOR_MAX - 1 {
if let Some(mut b) = self
.clone()
.increment(element_idx_1)
.and_then(|b| b.increment(element_idx_2))
.filter(Building::is_valid)
{
b.elevator += 1;
f(b.canonicalize())
}
}
// move two elements down
if self.elevator > 0 {
if let Some(mut b) = self
.clone()
.decrement(element_idx_1)
.and_then(|b| b.decrement(element_idx_2))
.filter(Building::is_valid)
{
b.elevator -= 1;
f(b.canonicalize())
}
}
}
}
}
/// Check whether building is in target state.
///
/// In target state, all elements incl. the elevator are at floor [`Building::FLOOR_MAX`] `- 1`.
pub fn is_target(&self) -> bool {
self.elevator == Self::FLOOR_MAX - 1
&& self
.chipgenerators
.iter()
.all(|chipgenerator| chipgenerator == &[Self::FLOOR_MAX - 1; 2])
}
/// get iterator over chip-generator pairs
pub fn chipgenerators(&self) -> impl Iterator<Item = &ChipGenerator> {
self.chipgenerators.iter()
}
/// insert additional chip-generator pair
pub fn insert(mut self, chipgenerator: ChipGenerator) -> Self {
self.chipgenerators.push(chipgenerator);
self.canonicalize()
}
}
and parsing the input into this model
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
pub mod input {
use crate::{Building, CHIP, GENERATOR};
use regex::Regex;
use std::collections::HashSet;
/// parser for a single floor from the puzzle input
///
/// this is essentially a container for the regular expressions used
pub struct FloorParser {
re_floor: Regex,
re_chip: Regex,
re_generator: Regex,
}
impl Default for FloorParser {
/**
* Create default parser instance.
*
* This is an alias for [`FloorParser::new`]
*/
fn default() -> Self {
Self::new()
}
}
impl FloorParser {
/// create parser instance
pub fn new() -> Self {
let re_floor = Regex::new(r"The (\w+) floor").unwrap();
let re_chip = Regex::new(r"(\w+)-compatible microchip").unwrap();
let re_generator = Regex::new(r"(\w+) generator").unwrap();
Self {
re_floor,
re_chip,
re_generator,
}
}
/// parse a single line from puzzle input
///
/// # Examples
/// ```
/// # use mr_kaffee_2016_11::input::*;
/// use std::collections::HashSet;
/// let line = "The third floor contains a promethium generator, a ruthenium generator, and a ruthenium-compatible microchip.";
/// let parser = FloorParser::new();
/// let (floor, chips, generators) = parser.parse(line);
/// assert_eq!(2, floor);
/// assert_eq!(HashSet::from(["ruthenium"]), chips);
/// assert_eq!(HashSet::from(["promethium", "ruthenium"]), generators);
/// ```
pub fn parse<'a>(&self, line: &'a str) -> (u8, HashSet<&'a str>, HashSet<&'a str>) {
let floor = match self
.re_floor
.captures(line)
.unwrap()
.get(1)
.unwrap()
.as_str()
{
"first" => 0,
"second" => 1,
"third" => 2,
"fourth" => 3,
floor => panic!("Unexpected floor: {}", floor),
};
let chips = self
.re_chip
.captures_iter(line)
.map(|c| c.get(1).map(|m| m.as_str()).unwrap())
.collect::<HashSet<_>>();
let generators = self
.re_generator
.captures_iter(line)
.map(|c| c.get(1).map(|m| m.as_str()).unwrap())
.collect::<HashSet<_>>();
(floor, chips, generators)
}
}
impl From<&str> for Building {
/// See [`FloorParser::parse`]
fn from(s: &str) -> Self {
let parser = FloorParser::new();
let floors = s.lines().map(|line| parser.parse(line)).collect::<Vec<_>>();
let types = floors
.iter()
.flat_map(|(_, chips, generators)| chips.iter().chain(generators.iter()))
.collect::<HashSet<_>>();
let mut chipgenerators = types
.iter()
.map(|&t| {
[
floors
.iter()
.find(|(_, chips, _)| chips.contains(t))
.unwrap()
.0,
floors
.iter()
.find(|(_, _, generators)| generators.contains(t))
.unwrap()
.0,
]
})
.collect::<Vec<_>>();
chipgenerators.sort();
Self {
chipgenerators,
elevator: 0,
}
}
}
impl std::fmt::Display for Building {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
for floor in (0..Self::FLOOR_MAX).rev() {
match self.elevator {
value if value == floor => write!(f, "E ")?,
_ => write!(f, ". ")?,
}
for (k, chipgenerator) in self.chipgenerators().enumerate() {
match chipgenerator[CHIP] {
value if value == floor => write!(f, "C{} ", k)?,
_ => write!(f, ".. ")?,
}
}
for (k, chipgenerator) in self.chipgenerators().enumerate() {
match chipgenerator[GENERATOR] {
value if value == floor => write!(f, "G{} ", k)?,
_ => write!(f, ".. ")?,
}
}
writeln!(f)?;
}
Ok(())
}
}
}
Star 1
The actual solution is a breadth first search.
A key ingredient is to realize that chip/generator pairs are essentially exchangeable and create a canonical representation of the model (function canonicalize), to reduce the search space.
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
/// find the shortest path to the target state, i.e., a building's state for which
/// [``Building::is_target``] returns `true`.
pub fn find_shortest_path(building: Building) -> Result<usize, PuzzleError> {
// check validity
if !building.is_valid() {
return Err("Cannot find shortest path for invalid building".into());
}
// keep track of path
let mut visited: HashSet<Rc<Building>> = HashSet::new();
// the queue for breadth first search
let mut queue = VecDeque::new();
// initialize
let building = Rc::new(building);
visited.insert(building.clone());
queue.push_front((building, 0));
while let Some((building, steps)) = queue.pop_back() {
if building.is_target() {
// target reached
return Ok(steps);
}
building.for_each_adjacent(|adj| {
let adj = Rc::new(adj);
if visited.insert(adj.clone()) {
queue.push_front((adj, steps + 1));
}
})
}
Err("Target not reached".into())
}
pub fn star_1(building: &Building) -> Result<usize, PuzzleError> {
find_shortest_path(building.to_owned())
}
Star 2
Solution for star 2 is essentially the same with more chip/generator pairs added
1
2
3
4
pub fn star_2(building: &Building) -> Result<usize, PuzzleError> {
// add two additional chip-generator pairs in floor 0
find_shortest_path(building.to_owned().insert([0, 0]).insert([0, 0]))
}
Day 12: Leonardo’s Monorail
Rust solution to AoC|2016|12.
Execute operations on registers …
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::{Op, Program, Val};
impl From<&str> for Val {
fn from(value: &str) -> Self {
let b = value.as_bytes()[0];
match b {
b'a'..=b'z' => Self::Reg((b - b'a') as _),
_ => Self::Val(value.parse().unwrap()),
}
}
}
impl From<&str> for Op {
fn from(s: &str) -> Self {
let mut words = s.split_ascii_whitespace();
match words.next() {
Some("cpy") => Self::Cpy(
words.next().unwrap().into(),
(words.next().unwrap().as_bytes()[0] - b'a') as _,
),
Some("inc") => Self::Inc((words.next().unwrap().as_bytes()[0] - b'a') as _),
Some("dec") => Self::Dec((words.next().unwrap().as_bytes()[0] - b'a') as _),
Some("jnz") => {
Self::Jnz(words.next().unwrap().into(), words.next().unwrap().into())
}
_ => panic!("Cannot parse {}", s),
}
}
}
impl From<&str> for Program {
fn from(s: &str) -> Self {
Self(s.lines().map(Op::from).collect())
}
}
}
Star 1
Use enum types Val and Op and a while loop to run the program.
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
impl Val {
pub fn get(&self, r: &[SolType]) -> SolType {
match self {
Val::Reg(idx) => r[*idx],
Val::Val(v) => *v,
}
}
}
impl Op {
pub fn execute(&self, r: &mut [SolType], p: &mut usize) {
match self {
Op::Cpy(v, idx) => (r[*idx], *p) = (v.get(r), *p + 1),
Op::Inc(idx) => (r[*idx], *p) = (r[*idx] + 1, *p + 1),
Op::Dec(idx) => (r[*idx], *p) = (r[*idx] - 1, *p + 1),
Op::Jnz(v1, v2) if v1.get(r) != 0 => *p = p.wrapping_add_signed(v2.get(r) as _),
Op::Jnz(_, _) => *p += 1,
}
}
}
pub fn solve(mut r: [SolType; 4], ops: &[Op]) -> SolType {
let mut p = 0;
while p < ops.len() {
ops[p].execute(&mut r, &mut p);
}
r[0]
}
pub fn star_1(Program(ops): &Program) -> SolType {
solve([0; 4], ops)
}
Star 2
Same solution with modified initial values.
1
2
3
pub fn star_2(Program(ops): &Program) -> SolType {
solve([0, 0, 1, 0], ops)
}
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#"cpy 41 a
inc a
inc a
dec a
jnz a 2
dec a
"#;
#[test]
pub fn test_from() {
let Program(ops) = Program::from(CONTENT);
assert_eq!(
vec![
Op::Cpy(Val::Val(41), 0),
Op::Inc(0),
Op::Inc(0),
Op::Dec(0),
Op::Jnz(Val::Reg(0), Val::Val(2)),
Op::Dec(0)
],
ops
)
}
#[test]
pub fn test_star_1() {
assert_eq!(42, star_1(&CONTENT.into()));
}
}
Day 13: A Maze of Twisty Little Cubicles
Rust solution to AoC|2016|13.
Another breadth first traversal.
Input
Parse the office designer’s favorite number.
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
Do the BFT to find the target.
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
const START: (usize, usize) = (1, 1);
const TARGET: (usize, usize) = (31, 39);
fn is_open((x, y): (usize, usize), off: usize) -> bool {
(x * (3 + x + 2 * y) + y * (1 + y) + off).count_ones() & 1 == 0
}
pub fn bft<P>(off: usize, done: P) -> (Option<SolType>, SolType)
where
P: Fn(SolType, (usize, usize)) -> bool,
{
let mut seen = HashSet::from([START]);
let mut queue = VecDeque::from([(0, START)]);
let mut cnt = 0;
while let Some((d, p)) = queue.pop_front() {
if done(d, p) {
return (Some(d), cnt);
}
cnt += 1;
for adj in [(1, 0), (0, -1), (-1, 0), (0, 1)]
.iter()
.map(|&(dx, dy)| (p.0.wrapping_add_signed(dx), p.1.wrapping_add_signed(dy)))
.filter(|&(x, y)| {
x != usize::MAX && y != usize::MAX && is_open((x, y), off) && seen.insert((x, y))
})
{
queue.push_back((d + 1, adj));
}
}
(None, cnt)
}
pub fn star_1(&PuzzleData(off): &PuzzleData) -> SolType {
bft(off, |_, p| p == TARGET).0.unwrap()
}
Star 2
Do the BFT to find all locations reachable in a given number of steps.
The solution for part 1 is quite simply made generic enough to also solve part 2.
1
2
3
4
5
const D_MAX: SolType = 50;
pub fn star_2(&PuzzleData(off): &PuzzleData) -> SolType {
bft(off, |d, _| d > D_MAX).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
#[cfg(test)]
mod tests {
use super::*;
const GRID_10: &str = r#".#.####.##
..#..#...#
#....##...
###.#.###.
.##..#..#.
..##....#.
#...##.###
"#;
#[test]
pub fn test_is_open() {
let grid = (0..10 * 7)
.map(|p| match is_open((p % 10, p / 10), 10) {
true => b'.',
_ => b'#',
})
.collect::<Vec<_>>();
let exp = GRID_10.bytes().filter(|&b| b != b'\n').collect::<Vec<_>>();
assert_eq!(exp, grid);
}
#[test]
pub fn test_bft() {
assert_eq!(Some(11), bft(10, |_, p| p == (7, 4)).0);
}
}
Day 14: One-Time Pad
Rust solution to AoC|2016|14.
Star 1
I created a little helper BufferedHashes; a ring buffer which calculates hashes for indices and stores the last 1,000.
The rest is the solve function which uses find_triple and has_quintuple functions.
To be able to mutably use the buffer in both the outer (finds triples) and the inner (finds quintuples) iterator, it is wrapped in a RefCell.
The optimization that often allows to step by 5 in has_quintuple had a surprisingly big effect for the performance of part 1 (roughly halves the run-time).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
const BUF_LEN: usize = 1000;
const N: usize = 1000;
const STRETCHES: usize = 2016;
pub struct BufferedHashes<'a> {
salt: &'a [u8],
stretches: usize,
hasher: CoreWrapper<Md5Core>,
buffer: [[u8; 16]; BUF_LEN],
off: usize,
avl: usize,
}
impl<'a> BufferedHashes<'a> {
const HEX_CHARS: &'static [u8] = b"0123456789abcdef";
pub fn new(salt: &'a str, stretches: usize) -> Self {
Self {
salt: salt.trim().as_bytes(),
stretches,
hasher: Md5::new(),
buffer: [[0; 16]; BUF_LEN],
off: 0,
avl: 0,
}
}
fn calc_hash(&mut self, index: usize) {
let hash = &mut self.buffer[index % BUF_LEN];
self.hasher.update(self.salt);
self.hasher.update(index.to_string().as_bytes());
self.hasher.finalize_into_reset(hash.into());
for _ in 0..self.stretches {
for &b in hash.iter() {
self.hasher.update([
Self::HEX_CHARS[(b >> 4) as usize],
Self::HEX_CHARS[(b & 15) as usize],
]);
}
self.hasher.finalize_into_reset(hash.into());
}
}
/// Get current offset.
pub fn off(&self) -> usize {
self.off
}
/// Get hash for index.
///
/// # Panics
///
/// if index is below current offset
pub fn get(&mut self, index: usize) -> &[u8] {
assert!(index >= self.off);
while self.off + self.avl <= index {
self.calc_hash(self.off + self.avl);
(self.off, self.avl) = match self.avl {
BUF_LEN => (self.off + 1, BUF_LEN),
_ => (self.off, self.avl + 1),
}
}
&self.buffer[index % BUF_LEN]
}
}
/// Find first symbol which repeats at least three times in a row, if any.
fn find_triple(hash: &[u8]) -> Option<u8> {
(0..2 * hash.len() - 2)
.map(|k| match k & 1 {
0 => (
hash[k >> 1] >> 4,
hash[k >> 1] & 15,
hash[(k >> 1) + 1] >> 4,
),
_ => (
hash[k >> 1] & 15,
hash[(k >> 1) + 1] >> 4,
hash[(k >> 1) + 1] & 15,
),
})
.filter_map(|(a, b, c)| if a == b && a == c { Some(a) } else { None })
.next()
}
/// Check whether given symbol `s` is contained in hash at least five times in a row.
fn has_quintuple(hash: &[u8], s: u8) -> bool {
let (mut k, mut len) = (0, 5);
while k <= 2 * hash.len() - len {
// start checking from behind, which often allows to jump by steps of 5
let Some(d) = (0..len).find(|d| match (k + len - d - 1) & 1 {
0 => hash[(k + len - d - 1) >> 1] >> 4 != s,
_ => hash[(k + len - d - 1) >> 1] & 15 != s,
}) else {
return true;
};
(k, len) = (k + len, 5 - d);
}
false
}
fn solve(buf: BufferedHashes) -> SolType {
let buf = RefCell::new(buf);
(0..)
.filter_map(|idx| find_triple(buf.borrow_mut().get(idx)).map(move |s| (idx, s)))
.filter(|&(idx, s)| {
(idx + 1..idx + 1 + N).any(|idx| has_quintuple(buf.borrow_mut().get(idx), s))
})
.nth(63)
.map(|(idx, _)| idx)
.unwrap()
}
pub fn star_1(salt: &&str) -> SolType {
solve(BufferedHashes::new(salt, 0))
}
Star 2
Modify the hash calculation to use stretches. I don’t know whether the run-time can be significantly reduced for the second part.
1
2
3
pub fn star_2(salt: &&str) -> SolType {
solve(BufferedHashes::new(salt, STRETCHES))
}
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::*;
#[test]
pub fn test_buffered_hashes() {
let mut buf0 = BufferedHashes::new("abc", 0);
let mut buf1 = BufferedHashes::new("abc", 0);
let mut triples = (0..).filter_map(|k| find_triple(buf0.get(k)).map(|s| (k, s)));
assert_eq!(Some((18, 8)), triples.next());
assert_eq!(
None,
(19..19 + N).find(|&idx| has_quintuple(buf1.get(idx), 8))
);
assert_eq!(Some((39, 14)), triples.next());
assert_eq!(
Some(816),
(40..40 + N).find(|&idx| has_quintuple(buf1.get(idx), 14))
);
assert_eq!(Some((92, 9)), triples.nth(6));
assert_eq!(
Some(200),
(93..93 + N).find(|&idx| has_quintuple(buf1.get(idx), 9))
);
}
#[test]
pub fn test_star_1() {
assert_eq!(22728, star_1(&"abc"));
}
#[test]
pub fn test_buffered_hashes_stretches() {
assert_eq!(
[(10, 1), (0, 7), (15, 15)].map(|(a, b)| a << 4 | b),
BufferedHashes::new("abc", STRETCHES).get(0)[0..3]
);
}
}
Day 15: Timing is Everything
Rust solution to AoC|2016|15.
Figure out when to release a capsule so that it passes through rotating discs.
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, i64)>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(
s.lines()
.map(str::split_ascii_whitespace)
.map(|mut words| {
(
words.nth(3).unwrap().parse().unwrap(),
words.last().unwrap().trim_end_matches('.').parse().unwrap(),
)
})
.collect(),
)
}
}
}
Star 1
The problem is solved using the extended euclidean algorithm in an iter-fold algorithm.
The fold is initialized with a virtual disc with only one position (i.e., the capsule passes no matter when it is released).
Each subsequent disc is merged with all previous discs to one bigger virtual disc as follows:
-
the virtual disc is represented by the size
m0(number of positions) and the earliest timet0a capsule can be released to pass through the disc -
hence the capsule will pass through the disc if it is released at
t = m0 * x + t0for any non-negative integerx -
the earliest time a capsule can be released to pass through the current disc (
0-based index:k1) of sizem1which starts at positionp1ist1 = -(k + 1 + p0) % m1 -
the capsule passes through all previous and the current disc if
xis such that(m0 x + t0 - t1) % m1 = 0 -
the new virtual disc is of size
m0 * m1(assumingm0andm1are co-prime) and the earliest time ism0 * x + t0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn solve(discs: &[(i64, i64)]) -> SolType {
let (_, t) = discs
.iter()
.enumerate()
.fold((1, 0), |(m0, t0), (k1, &(m1, p1))| {
// update t0 = m0 * x + t0
// (m0 * x + t0 - t1) % m1 = 0 with t1 = -(k1 + 1 + p1)
let t1 = -(k1 as i64 + 1 + p1);
let inv_n = mul_inverse_mod(m0, m1);
let x = (inv_n * (t1 - t0)).rem_euclid(m1);
(m0 * m1, x * m0 + t0)
});
t
}
pub fn star_1(PuzzleData(discs): &PuzzleData) -> SolType {
solve(discs)
}
Star 2
Solution from part 1 works without any change.
1
2
3
pub fn star_2(PuzzleData(discs): &PuzzleData) -> SolType {
solve(&[discs as &[_], &[(11, 0)]].concat())
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Disc #1 has 5 positions; at time=0, it is at position 4.
Disc #2 has 2 positions; at time=0, it is at position 1.
"#;
#[test]
pub fn test_from() {
let PuzzleData(discs) = PuzzleData::from(CONTENT);
assert_eq!(vec![(5, 4), (2, 1)], discs);
}
#[test]
pub fn test_star_1() {
assert_eq!(5, star_1(&CONTENT.into()));
}
}
Day 16: Dragon Checksum
Rust solution to AoC|2016|16.
Generate 'randomly looking' data of bits and checksums thereof
Input
1
2
3
4
5
6
7
8
9
10
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<bool>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
Self(s.trim().bytes().map(|b| b == b'1').collect())
}
}
}
Star 1
The implementation uses a Vec<bool> to store the data.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
pub fn generate(init: &[bool], len: usize) -> Vec<bool> {
let l = successors(Some(init.len()), |l| Some(l << 1 | 1))
.find(|&l| l >= len)
.unwrap();
let mut data = vec![false; l];
let mut l_0 = init.len();
data[0..l_0].copy_from_slice(init);
while l_0 < len {
let l_1 = l_0 << 1 | 1;
let (a, b) = data.split_at_mut(l_0);
a.iter()
.rev()
.zip(b[1..].iter_mut())
.for_each(|(&a, b)| *b = !a);
l_0 = l_1;
}
data.truncate(len);
data
}
pub fn checksum(mut data: Vec<bool>) -> Vec<bool> {
while data.len() & 1 == 0 {
let l = data.len() >> 1;
for k in 0..l {
data[k] = data[k << 1] == data[k << 1 | 1];
}
data.truncate(l);
}
data
}
pub fn solve(init: &[bool], len: usize) -> SolType {
checksum(generate(init, len))
.iter()
.map(|&b| if b { '1' } else { '0' })
.collect()
}
pub fn star_1(PuzzleData(init): &PuzzleData) -> SolType {
solve(init, 272)
}
Star 2
Do the same thing for much more data. Solution from part 1 works without changes in principle. The code avoids re-allocations to optimize performance.
1
2
3
pub fn star_2(PuzzleData(init): &PuzzleData) -> SolType {
solve(init, 35_651_584)
}
Tests
1
2
3
4
5
6
7
8
9
10
#[cfg(test)]
mod tests {
use super::*;
#[test]
pub fn test_solve_1() {
let PuzzleData(data) = "10000".into();
assert_eq!("01100", solve(&data, 20));
}
}
Day 17: Two Steps Forward
Rust solution to AoC|2016|17.
Calculate admissible paths based on MD5 hashes.
This puzzle deviates from my rule to not use any external dependencies. I use crate md5 to calculate the hashes.
Star 1
BFS for the target.
Admissible adjacents are chosen based on the lock status of the doors based on the current hash 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
pub fn star_1(password: &&str) -> SolType1 {
let password = password.trim().as_bytes();
let mut hasher = Md5::new();
let mut hash: [u8; 16] = [0; 16];
let mut queue: VecDeque<(Vec<u8>, (u32, u32))> = VecDeque::from([(Vec::new(), (0, 0))]);
while let Some((path, (x, y))) = queue.pop_front() {
if (x, y) == (3, 3) {
return String::from_utf8(path).unwrap();
}
hasher.update(password);
hasher.update(&path);
hasher.finalize_into_reset((&mut hash).into());
for (adj, c) in [
((0, -1), b'U', hash[0] >> 4),
((0, 1), b'D', hash[0] & 15),
((-1, 0), b'L', hash[1] >> 4),
((1, 0), b'R', hash[1] & 15),
]
.into_iter()
.filter(|(_, _, o)| *o > 10)
.map(|((dx, dy), c, _)| ((x.wrapping_add_signed(dx), y.wrapping_add_signed(dy)), c))
.filter(|((x, y), _)| 4.gt(x) && 4.gt(y))
{
let mut path = path.clone();
path.push(c);
queue.push_back((path, adj));
}
}
panic!("No solution");
}
Star 2
Exhaustive exploration of the grid.
This is almost the same as the solution for part 1. The only difference is that for part 2 we do not return once the target is reached for the first time but merely update the maximum path length found so far and continue exploration.
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(password: &&str) -> SolType2 {
let password = password.trim().as_bytes();
let mut hasher = Md5::new();
let mut hash: [u8; 16] = [0; 16];
let mut queue: VecDeque<(Vec<u8>, (u32, u32))> = VecDeque::from([(Vec::new(), (0, 0))]);
let mut max = 0;
while let Some((path, (x, y))) = queue.pop_front() {
if (x, y) == (3, 3) {
max = max.max(path.len());
continue;
}
hasher.update(password);
hasher.update(&path);
hasher.finalize_into_reset((&mut hash).into());
for (adj, c) in [
((0, -1), b'U', hash[0] >> 4),
((0, 1), b'D', hash[0] & 15),
((-1, 0), b'L', hash[1] >> 4),
((1, 0), b'R', hash[1] & 15),
]
.into_iter()
.filter(|(_, _, o)| *o > 10)
.map(|((dx, dy), c, _)| ((x.wrapping_add_signed(dx), y.wrapping_add_signed(dy)), c))
.filter(|((x, y), _)| 4.gt(x) && 4.gt(y))
{
let mut path = path.clone();
path.push(c);
queue.push_back((path, adj));
}
}
max
}
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#"ihgpwlah
"#;
#[test]
pub fn test_star_1() {
assert_eq!("DDRRRD", star_1(&CONTENT));
}
#[test]
pub fn test_star_2() {
assert_eq!(370, star_2(&CONTENT));
}
}
Day 18: Like a Rogue
Rust solution to AoC|2016|18.
Build rows with 'trap locations' based on 'trap locations' in previous row.
The way the problem is posed, seems to be made for a successors iterator.
The key observation is that the pattern to apply is essentially the left position XOR the right position of the previous row. This can be done very efficiently with bit operations.
Input
Parse the row in the bits of a u128 and also create a bit-mask.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub u128, pub u128);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let l = s.trim().len();
assert!(
l <= u128::BITS as _,
"Cannot process rows with more than {} elements. Found {}",
u128::BITS,
l,
);
Self(
s.trim()
.bytes()
.enumerate()
.filter(|(_, b)| b'^'.eq(b))
.fold(0, |v, (k, _)| v | 1 << k),
(1 << l) - 1,
)
}
}
}
Star 1
Since bit-shifts shift in zeros from the left or the right, the solution represents safe as 0 and trap as 1.
The number of safe tiles in a row is thus the number of zero bits of !mask | row.
1
2
3
4
5
6
7
8
9
10
pub fn solve(PuzzleData(row, mask): &PuzzleData, n: usize) -> SolType {
successors(Some(*row), |&row| Some((mask & row << 1) ^ (row >> 1)))
.take(n)
.map(|row| (!mask | row).count_zeros() as SolType)
.sum()
}
pub fn star_1(data: &PuzzleData) -> SolType {
solve(data, 40)
}
Star 2
The only change is the number of rows to consider.
(Ok, my first guess was to look for a repeating pattern. Finding an efficient implementation based on bitwise XOR was only my second attempt)
1
2
3
pub fn star_2(data: &PuzzleData) -> SolType {
solve(data, 400_000)
}
Tests
1
2
3
4
5
6
7
8
9
10
11
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#".^^.^.^^^^"#;
#[test]
pub fn test_solve() {
assert_eq!(38, solve(&CONTENT.into(), 10));
}
}
Day 19: An Elephant Named Joseph
Rust solution to AoC|2016|19.
Input
1
2
3
4
5
6
7
8
9
10
pub mod input {
#[derive(Debug)]
pub struct Elves(pub usize);
impl From<&str> for Elves {
fn from(s: &str) -> Self {
Self(s.trim().parse().unwrap())
}
}
}
Star 1
Play rounds until only one elf is left. In each round, half of the elves are eliminated. If the number of elves is odd, the number of eliminated elves is half of the number of elves rounded towards positive infinity. The number of remaining elves is half the number of elves rounded towards zero.
1
2
3
4
5
6
7
8
9
10
11
pub fn star_1(&Elves(n): &Elves) -> SolType {
let mut elves = (1..).take(n).collect::<Vec<_>>();
while elves.len() > 1 {
elves = ((elves.len() & 1) << 1..)
.step_by(2)
.take(elves.len() >> 1)
.map(|k| elves[k])
.collect();
}
elves[0]
}
Star 2
The solution is essentially the same as for part 1. Calculating the update is a bit more tricky.
It is best understood by taking examples:
If the number of elves is 10, the following happens:
-
Elf e[0] takes presents of elf e[5]
-
Elf e[1] takes presents of elf e[6]
-
Elf e[2] takes presents of elf e[8]
-
Elf e[3] takes presents of elf e[9]
-
Elf e[4] takes presents of elf e[1] = e[11 % 10]
The elves indexed 7 0 2 3 4 remain, 7 plays next. This can be expressed as
-
Iterate over
k in 0..elves.len() -
If
k % 3 == 2or number of skipped elves equals 5, add e[(l + k) % 10] to updated elves -
Otherwise, skip elf
Similarly, for odd numbers of elves, e.g. 11 elves:
-
Elf e[0] takes presents of elf e[5]
-
Elf e[1] takes presents of elf e[7]
-
Elf e[2] takes presents of elf e[8]
-
Elf e[3] takes presents of elf e[10]
-
Elf e[4] takes presents of elf e[0] = e[11 % 11]
-
Elf e[6] takes presents of elf e[2] = e[13 % 11]
The elves indexed 9 1 3 4 6 remain, 9 plays next. This can be expressed as
-
Iterate over
k in 0..elves.len() -
If
k % 3 == 1or number of skipped elves equals 6, add e[(l + k) % 11] to updated elves -
Otherwise, skip elf
The first index, 6, shall be added at the last position of the updated list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn star_2(&Elves(n): &Elves) -> SolType {
let mut elves = (1..).take(n).collect::<Vec<_>>();
while elves.len() > 1 {
let (m, l) = (elves.len() & 1, elves.len() >> 1);
(elves, _, _) = (0..elves.len()).fold(
(vec![0; l], (l - m) % l, 0),
|(mut upd, mut j, mut d), k| {
if k % 3 == 2 - m || d == l + m {
upd[j] = elves[(l + k) % elves.len()];
j = (j + 1) % l;
} else {
d += 1;
}
(upd, j, d)
},
);
}
elves[0]
}
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!(3, star_1(&Elves(5)));
}
#[test]
pub fn test_star_2() {
assert_eq!(2, star_2(&Elves(5)));
}
}
Day 20: Firewall Rules
Rust solution to AoC|2016|20.
Evaluate IP address black-lists
Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pub mod input {
use crate::SolType;
#[derive(Debug)]
pub struct BlackList(pub Vec<(SolType, SolType)>);
impl From<&str> for BlackList {
fn from(s: &str) -> Self {
Self(
s.lines()
.filter_map(|l| l.split_once('-'))
.map(|(l, h)| (l.parse().unwrap(), h.parse().unwrap()))
.collect(),
)
}
}
}
Star 1
The black-list is normalized to not contain any overlapping or immediately adjacent ranges and to be sorted by IP addresses. The .n_h.saturating_add(1) makes sure that ranges immediately adjacent to each other are also combined; saturating addition is necessary because the upper limit n_h may be the maximum value the type can represent (SolType::MAX).
Then the smallest admissible IP address is the first range’s max value plus one (unless the first range starts above zero, in which case it is 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 normalize(BlackList(ranges): &BlackList) -> Vec<(SolType, SolType)> {
let mut ranges = ranges.to_owned();
ranges.sort_unstable();
ranges.iter().fold(Vec::new(), |mut normalized, &(l, h)| {
match normalized
.last_mut()
.filter(|(n_l, n_h)| l >= *n_l && l <= n_h.saturating_add(1))
{
Some((_, n_h)) => *n_h = h.max(*n_h),
_ => normalized.push((l, h)),
}
normalized
})
}
pub fn star_1(list: &BlackList) -> SolType {
match normalize(list)[0] {
(0, h) => h + 1,
_ => 0,
}
}
Star 2
Again using the normalized list, we just need to sum the spaces between the forbidden ranges plus everything before the first range and everything behind the last range up to the maximum value. The maximum value is made an argument max for testability.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn solve_2(list: &BlackList, max: SolType) -> SolType {
let ranges = normalize(list);
ranges
.iter()
.zip(ranges[1..].iter())
.map(|((_, h1), (l2, _))| l2 - h1 - 1)
.sum::<SolType>()
+ ranges.first().map(|&(l, _)| l).unwrap()
+ ranges.last().map(|&(_, h)| max - h).unwrap()
}
pub fn star_2(list: &BlackList) -> SolType {
solve_2(list, SolType::MAX)
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"5-8
0-2
4-7
"#;
#[test]
pub fn test_from() {
let BlackList(ranges) = BlackList::from(CONTENT);
assert_eq!(vec![(5, 8), (0, 2), (4, 7)], ranges);
}
#[test]
pub fn test_normalize() {
let ranges = normalize(&CONTENT.into());
assert_eq!(vec![(0, 2), (4, 8)], ranges);
}
#[test]
pub fn test_star_1() {
assert_eq!(3, star_1(&CONTENT.into()));
}
#[test]
pub fn test_solve_2() {
assert_eq!(2, solve_2(&CONTENT.into(), 9));
}
}
Day 21: Scrambled Letters and Hash
Rust solution to AoC|2016|21.
Password scrambling
Input
Parse the input into an enum Op with variants for each type of scrambling operation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
pub mod input {
use crate::Op;
#[derive(Debug)]
pub struct PuzzleData(pub Vec<Op>);
impl From<&str> for PuzzleData {
/// parse the puzzle input
fn from(s: &str) -> Self {
Self(s.lines().map(Op::from).collect())
}
}
impl From<&str> for Op {
fn from(s: &str) -> Self {
if let Some(s) = s.strip_prefix("swap position ") {
Self::SwapPos(
(s.as_bytes().first().unwrap() - b'0') as _,
(s.as_bytes().last().unwrap() - b'0') as _,
)
} else if let Some(s) = s.strip_prefix("swap letter ") {
Self::SwapLet(
*s.as_bytes().first().unwrap(),
*s.as_bytes().last().unwrap(),
)
} else if let Some(s) = s.strip_prefix("rotate left ") {
Self::RotLeft((s.as_bytes().first().unwrap() - b'0') as _)
} else if let Some(s) = s.strip_prefix("rotate right ") {
Self::RotRight((s.as_bytes().first().unwrap() - b'0') as _)
} else if let Some(s) = s.strip_prefix("rotate based on position of letter ") {
Self::RotLet(*s.as_bytes().first().unwrap())
} else if let Some(s) = s.strip_prefix("reverse positions ") {
Self::Rev(
(s.as_bytes().first().unwrap() - b'0') as _,
(s.as_bytes().last().unwrap() - b'0') as _,
)
} else if let Some(s) = s.strip_prefix("move position ") {
Self::MvPos(
(s.as_bytes().first().unwrap() - b'0') as _,
(s.as_bytes().last().unwrap() - b'0') as _,
)
} else {
panic!();
}
}
}
}
Star 1
Implement all the scrambling operations. Rust’s Vec even has functions for rotate_left and rotate_right.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
pub fn scramble(pwd: &str, ops: &[Op]) -> SolType {
let mut pwd = pwd.bytes().collect::<Vec<_>>();
for op in ops {
match *op {
Op::SwapPos(a, b) => (pwd[a], pwd[b]) = (pwd[b], pwd[a]),
Op::SwapLet(v, w) => {
let a = pwd.iter().position(|&b| b == v).unwrap();
let b = pwd.iter().position(|&b| b == w).unwrap();
(pwd[a], pwd[b]) = (pwd[b], pwd[a]);
}
Op::RotLeft(a) => pwd.rotate_left(a),
Op::RotRight(a) => pwd.rotate_right(a),
Op::RotLet(v) => {
let a = pwd.iter().position(|&b| b == v).unwrap();
let a = if a >= 4 { a + 2 } else { a + 1 };
let a = a % pwd.len();
pwd.rotate_right(a);
}
Op::Rev(a, b) => {
let temp = (a..=b).rev().map(|k| pwd[k]).collect::<Vec<_>>();
pwd[a..=b].copy_from_slice(&temp);
}
Op::MvPos(a, b) => {
let v = pwd.remove(a);
pwd.insert(b, v);
}
}
}
String::from_utf8(pwd).unwrap()
}
pub fn star_1(PuzzleData(ops): &PuzzleData) -> SolType {
scramble("abcdefgh", ops)
}
Star 2
The inverse for all but 'rotate based on position of letter X' is obvious. The latter one is only invertible if the password length is equal to 8. Once this is understood, it is not so complicated…
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 unscramble(pwd: &str, ops: &[Op]) -> SolType {
const LEN: usize = 8;
debug_assert_eq!(
LEN,
pwd.len(),
"'rotate based on position of letter' only invertible for len = {}",
LEN
);
let mut pwd = pwd.bytes().collect::<Vec<_>>();
for op in ops.iter().rev() {
match *op {
Op::SwapPos(a, b) => (pwd[a], pwd[b]) = (pwd[b], pwd[a]),
Op::SwapLet(v, w) => {
let a = pwd.iter().position(|&b| b == v).unwrap();
let b = pwd.iter().position(|&b| b == w).unwrap();
(pwd[a], pwd[b]) = (pwd[b], pwd[a]);
}
Op::RotLeft(a) => pwd.rotate_right(a),
Op::RotRight(a) => pwd.rotate_left(a),
Op::RotLet(v) => {
let a = pwd.iter().position(|&b| b == v).unwrap();
let b = if a & 1 == 1 {
// 1) index(v) < 4
// idx_1 = 2 * idx_0 + 1
(a - 1) / 2 + 1
} else {
// 2) index(v) >= 4
// idx_1 = (2 * idx_0 + 2) % pwd.len()
(LEN / 2 + ((a as isize - 2) / 2).rem_euclid((LEN / 2) as _) as usize + 2) & 7
};
pwd.rotate_left(b);
}
Op::Rev(a, b) => {
let temp = (a..=b).rev().map(|k| pwd[k]).collect::<Vec<_>>();
pwd[a..=b].copy_from_slice(&temp);
}
Op::MvPos(a, b) => {
let v = pwd.remove(b);
pwd.insert(a, v);
}
}
}
String::from_utf8(pwd).unwrap()
}
pub fn star_2(PuzzleData(ops): &PuzzleData) -> SolType {
unscramble("fbgdceah", ops)
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"swap position 4 with position 0
swap letter d with letter b
reverse positions 0 through 4
rotate left 1 step
move position 1 to position 4
move position 3 to position 0
rotate based on position of letter b
rotate based on position of letter d
"#;
#[test]
pub fn test_from() {
let PuzzleData(ops) = PuzzleData::from(CONTENT);
assert_eq!(
vec![
Op::SwapPos(4, 0),
Op::SwapLet(b'd', b'b'),
Op::Rev(0, 4),
Op::RotLeft(1),
Op::MvPos(1, 4),
Op::MvPos(3, 0),
Op::RotLet(b'b'),
Op::RotLet(b'd'),
],
ops
);
}
#[test]
pub fn test_star_1() {
let PuzzleData(ops) = PuzzleData::from(CONTENT);
assert_eq!("decab", scramble("abcde", &ops));
}
#[test]
pub fn test_unscramble_rot_let() {
for v in b'a'..=b'h' {
let s = scramble("abcdefgh", &[Op::RotLet(v)]);
assert_eq!(
"abcdefgh",
unscramble(&s, &[Op::RotLet(v)]),
"{} -> {}",
v as char,
s
);
}
}
}
Day 22: Grid Computing
Rust solution to AoC|2016|22.
Input
Parse the input into a sorted vec of x/y coordinates and used and free capacities. The vec is sorted by row (y) first, then by column ('x').
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
pub mod input {
#[derive(Debug)]
pub struct PuzzleData(pub Vec<((usize, usize), (usize, usize))>);
impl From<&str> for PuzzleData {
fn from(s: &str) -> Self {
let mut s = Self(
s.lines()
.filter_map(|l| l.strip_prefix("/dev/grid/node-x"))
.map(|l| {
let mut words = l.split_ascii_whitespace();
let (x, y) = words
.next()
.unwrap()
.split_once("-y")
.map(|(x, y)| (x.parse().unwrap(), y.parse().unwrap()))
.unwrap();
let used = words.nth(1).unwrap().trim_end_matches('T').parse().unwrap();
let free = words.next().unwrap().trim_end_matches('T').parse().unwrap();
((x, y), (used, free))
})
.collect::<Vec<_>>(),
);
s.0.sort_unstable_by_key(|&((x, y), _)| (y, x));
s
}
}
}
Star 1
The warm-up.
1
2
3
4
5
6
7
8
9
pub fn star_1(PuzzleData(data): &PuzzleData) -> SolType1 {
data.iter()
.enumerate()
.flat_map(|(k, &(_, a))| data[k + 1..].iter().map(move |&(_, b)| (a, b)))
.filter(|&((used_a, free_a), (used_b, free_b))| {
used_a != 0 && used_a <= free_b || used_b != 0 && used_b <= free_a
})
.count()
}
Star 2
The 'empty' node is moved until the data node is at the origin.
The key to solve the puzzle in a couple of ms is to use an A* style algorithm. The heuristic is a lower bound for the minimum steps required if there are no non movable nodes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
pub fn star_2(PuzzleData(data): &PuzzleData) -> SolType2 {
let (p, _) = *data.iter().find(|(_, (used, _))| *used == 0).unwrap();
let mn = data.iter().map(|&(_, (u, f))| u + f).min().unwrap();
let grid = data.iter().map(|&(_, (u, _))| u <= mn).collect::<Vec<_>>();
let (w, h) = data.last().map(|((x, y), _)| (x + 1, y + 1)).unwrap();
let d = (w - 1, 0);
let heuristic = |(x, y): (usize, usize), (d_x, d_y): (usize, usize)| {
// move 'empty' left of or above data
// When moving along d_y == 0 or d_x == 0, moving 'D' by one takes 5 steps:
// .D_ .D. .D. .D. _D. D_.
// ... => .._ => ._. => _.. => ... => ...
// ... ... ... ... ... ...
// (the first move of 'D' is the 1 last step in the sequence above)
// Total: 5 * (d_x - 1) + 1 = 5 * d_x - 4
//
// When moving along a diagonal, moving 'D' one up and one left takes 6 steps:
// ... .._ ._. .D. .D. _D. D_.
// .D_ => .D. => .D. => ._. => _.. => ... => ...
// ... ... ... ... ... ... ...
// (the first diagonal move of 'D' is the 4 last steps in the sequence above)
// Total: 5 * (d_x - 1).max(d_y - 1) + (d_x - 1).min(d_y - 1) + 4
// = 5 * d_x.max(d_y) + d_x.min(d_y) - 2
match (d_x, d_y) {
(0, 0) => 0,
(_, 0) => x.max(d_x - 1) - x.min(d_x - 1) + y + 5 * d_x - 4,
(0, _) => x + y.max(d_y - 1) - y.min(d_y - 1) + 5 * d_y - 4,
_ => {
usize::min(
x.max(d_x - 1) - x.min(d_x - 1) + y.max(d_y) - y.min(d_y),
x.max(d_x) - x.min(d_x) + y.max(d_y - 1) - y.min(d_y - 1),
) + (5 * d_x.max(d_y) + d_x.min(d_y) - 2)
}
}
};
let dist = 0;
let weight = heuristic(p, d) + dist;
let mut seen = HashMap::from([((p, d), (weight, dist))]);
let mut queue = BinaryHeap::from([((!weight, !dist), (p, d))]);
while let Some(((_, not_dist), (p, d))) = queue.pop() {
if d == (0, 0) {
return !not_dist;
}
for adj in [(1, 0), (0, -1), (-1, 0), (0, 1)]
.iter()
.map(|&(dx, dy)| (p.0.wrapping_add_signed(dx), p.1.wrapping_add_signed(dy)))
.filter(|&(x, y)| x < w && y < h && grid[x + w * y])
{
let d_adj = if adj == d { p } else { d };
let dist = !not_dist + 1;
let weight = heuristic(adj, d_adj) + dist;
let prev = seen.entry((adj, d_adj)).or_insert((usize::MAX, usize::MAX));
if (weight, dist) < *prev {
*prev = (weight, dist);
queue.push(((!weight, !dist), (adj, d_adj)));
}
}
}
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
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"Filesystem Size Used Avail Use%
/dev/grid/node-x0-y0 10T 8T 2T 80%
/dev/grid/node-x0-y1 11T 6T 5T 54%
/dev/grid/node-x0-y2 32T 28T 4T 87%
/dev/grid/node-x1-y0 9T 7T 2T 77%
/dev/grid/node-x1-y1 8T 0T 8T 0%
/dev/grid/node-x1-y2 11T 7T 4T 63%
/dev/grid/node-x2-y0 10T 6T 4T 60%
/dev/grid/node-x2-y1 9T 8T 1T 88%
/dev/grid/node-x2-y2 9T 6T 3T 66%
"#;
#[test]
pub fn test_from() {
let PuzzleData(data) = PuzzleData::from(CONTENT);
assert_eq!(
vec![
((0, 0), (8, 2)),
((1, 0), (7, 2)),
((2, 0), (6, 4)),
((0, 1), (6, 5)),
((1, 1), (0, 8)),
((2, 1), (8, 1)),
((0, 2), (28, 4)),
((1, 2), (7, 4)),
((2, 2), (6, 3))
],
data
);
}
#[test]
pub fn test_star_2() {
assert_eq!(7, star_2(&CONTENT.into()));
}
}
Day 23: Safe Cracking
Rust solution to AoC|2016|23.
Execute operations on registers … or reverse engineer those operations to come up with a tractable solution.
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::{Op, Program, Val};
impl From<&str> for Val {
fn from(value: &str) -> Self {
let b = value.as_bytes()[0];
match b {
b'a'..=b'z' => Self::Reg((b - b'a') as _),
_ => Self::Val(value.parse().unwrap()),
}
}
}
impl From<&str> for Op {
fn from(s: &str) -> Self {
let mut words = s.split_ascii_whitespace();
match words.next() {
Some("cpy") => {
Self::Cpy(words.next().unwrap().into(), words.next().unwrap().into())
}
Some("inc") => Self::Inc(words.next().unwrap().into()),
Some("dec") => Self::Dec(words.next().unwrap().into()),
Some("jnz") => {
Self::Jnz(words.next().unwrap().into(), words.next().unwrap().into())
}
Some("tgl") => Self::Tgl(words.next().unwrap().into()),
_ => panic!("Cannot parse {}", s),
}
}
}
impl From<&str> for Program {
fn from(s: &str) -> Self {
Self(s.lines().map(Op::from).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
impl Val {
pub fn get(&self, r: &[SolType]) -> SolType {
match self {
Val::Reg(idx) => r[*idx],
Val::Val(v) => *v,
}
}
}
pub fn execute(ops: &mut [Op], r: &mut [SolType], p: &mut usize) {
match &ops[*p] {
Op::Cpy(v, Val::Reg(idx)) => (r[*idx], *p) = (v.get(r), *p + 1),
Op::Inc(Val::Reg(idx)) => (r[*idx], *p) = (r[*idx] + 1, *p + 1),
Op::Dec(Val::Reg(idx)) => (r[*idx], *p) = (r[*idx] - 1, *p + 1),
Op::Jnz(v1, v2) if v1.get(r) != 0 => *p = p.wrapping_add_signed(v2.get(r) as _),
Op::Tgl(v) => {
let p_toggle = p.wrapping_add_signed(v.get(r) as _);
if p_toggle < ops.len() {
ops[p_toggle] = match &ops[p_toggle] {
Op::Cpy(v1, v2) => Op::Jnz(*v1, *v2),
Op::Inc(v) => Op::Dec(*v),
Op::Dec(v) => Op::Inc(*v),
Op::Jnz(v1, v2) => Op::Cpy(*v1, *v2),
Op::Tgl(v) => Op::Inc(*v),
};
}
*p += 1;
}
_ => *p += 1,
}
}
pub fn solve(mut r: [SolType; 4], mut ops: Vec<Op>) -> SolType {
let mut p = 0;
while p < ops.len() {
execute(&mut ops, &mut r, &mut p);
}
r[0]
}
pub fn star_1(Program(ops): &Program) -> SolType {
solve([7, 0, 0, 0], ops.to_owned())
}
Star 2
Reverse engineered instructions in pseudo code:
// 0..=1
b = a - 1
// 2..=18
{
// 2..=9
a *= b
// 10
b--
// 11..=15
c = 2 * b
// 16
toggle c // this will toggle 24, 22, 20, 18, once 18 is toggled, loop ends
// 17..=18 loop
} while b != 1
// 19..=25 (after all even numbers are toggled)
// some final manipulations
The main loop actually calculates factorial a and leaves the registers as [a!, 1, 2, 0] after
the toggle operation is executed the last time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn star_2(Program(ops): &Program) -> SolType {
let mut ops = ops.to_owned();
// init registers, a = factorial(12), b = 1, c = 0, d = 0
let a = (2..=12).product();
let mut r = [a, 1, 0, 0];
// toggle the operations 24, 22, 20, 18
let mut p = 16;
for c in [8, 6, 4, 2] {
p = 16;
r[2] = c;
execute(&mut ops, &mut r, &mut p);
}
while p < ops.len() {
execute(&mut ops, &mut r, &mut p);
}
r[0]
}
Tests
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"cpy 2 a
tgl a
tgl a
tgl a
cpy 1 a
dec a
dec a
"#;
#[test]
pub fn test_from() {
let Program(ops) = Program::from(CONTENT);
assert_eq!(
vec![
Op::Cpy(Val::Val(2), Val::Reg(0)),
Op::Tgl(Val::Reg(0)),
Op::Tgl(Val::Reg(0)),
Op::Tgl(Val::Reg(0)),
Op::Cpy(Val::Val(1), Val::Reg(0)),
Op::Dec(Val::Reg(0)),
Op::Dec(Val::Reg(0)),
],
ops
)
}
#[test]
pub fn test_star_1() {
assert_eq!(3, star_1(&CONTENT.into()));
}
}
Day 24: Air Duct Spelunking
Rust solution to AoC|2016|24.
A path finding problem on a grid…
Input
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 {
fn from(s: &str) -> Self {
Self {
w: s.find('\n').unwrap(),
grid: s.bytes().filter(|&b| b != b'\n').collect(),
}
}
}
}
Star 1
I calculate the shortest paths between all points of interest first using BFS.
Then I use a A* style search to determine the shortest path to visit all points of interest. The A* heuristic uses the maximum distance to any not yet seen point of interest.
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
fn shortest_paths(PuzzleData { w, grid }: &PuzzleData) -> (Vec<SolType>, usize) {
let pois = grid
.iter()
.enumerate()
.filter(|(_, &b)| b.is_ascii_digit())
.map(|(p, &b)| ((b - b'0') as usize, (p % w, p / w)))
.collect::<Vec<_>>();
let n = pois.len();
let mut dists = vec![usize::MAX; n * n];
let all = (1 << n) - 1;
for &(poi, (x, y)) in &pois {
dists[poi + n * poi] = 0;
let mut seen = HashSet::from([(x, y)]);
let mut queue = VecDeque::from([(0, (x, y))]);
// no need to re-calculate known distances
let mut visited = (0..n)
.filter(|adj| dists[poi + n * adj] < usize::MAX)
.fold(0, |v, adj| v | 1 << adj);
while let Some((dist, (x, y))) = queue.pop_front() {
let b = grid[x + w * y];
if b.is_ascii_digit() {
dists[(b - b'0') as usize + n * poi] = dist;
dists[poi + n * (b - b'0') as usize] = dist;
visited |= 1 << (b - b'0');
}
if visited == all {
break;
}
for (x_adj, y_adj) in [(1, 0), (0, -1), (-1, 0), (0, 1)]
.iter()
.map(|&(dx, dy)| (x.wrapping_add_signed(dx), y.wrapping_add_signed(dy)))
.filter(|&(x_adj, y_adj)| {
x_adj < *w && y_adj < grid.len() / w && grid[x_adj + w * y_adj] != b'#'
})
{
if seen.insert((x_adj, y_adj)) {
queue.push_back((dist + 1, (x_adj, y_adj)));
}
}
}
}
(dists, n)
}
fn solve<F1, F2, F3>(data: &PuzzleData, f1: F1, f2: F2, tar: F3) -> SolType
where
F1: Fn(usize, usize, usize, usize) -> bool,
F2: Fn(usize, usize) -> bool,
F3: Fn(usize, usize) -> bool,
{
let (dists, n) = shortest_paths(data);
let w = dists[0..n].iter().max().copied().unwrap();
let d = 0;
let m = 1;
let visited = 0;
let mut qeueu = BinaryHeap::from([(!w, !d, !m, 0, visited)]);
let mut seen = HashMap::from([((0, visited), (w, d))]);
while let Some((_, not_d, not_m, poi, visited)) = qeueu.pop() {
if tar(!not_m, n) {
return !not_d;
}
let visited = visited | 1 << poi;
let m = !not_m + 1;
for adj in (0..n).filter(|&adj| f1(adj, visited, m, n)) {
let d = !not_d + dists[poi + n * adj];
let w = d
+ (0..n)
.filter(|&poi| f2(poi, visited))
.map(|poi| dists[adj + n * poi])
.max()
.unwrap_or(0);
let prev = seen
.entry((adj, visited))
.or_insert((usize::MAX, usize::MAX));
if (w, d).lt(prev) {
*prev = (w, d);
qeueu.push((!w, !d, !m, adj, visited));
}
}
}
panic!("No solution");
}
pub fn star_1(data: &PuzzleData) -> SolType {
solve(
data,
|adj, visited, _, _| (visited >> adj) & 1 == 0,
|poi, visited| (visited >> poi) & 1 == 0,
|m, n| m == n,
)
}
Star 2
This is mostly the same as part 1. The differences are:
- stop only after n + 1 points of interest are visited, because 0 is visited twice
- include POI 0 in the max for the A* weight (although it was already seen)
- if all POIs are seen, add POI 0 to the list of adjacents (although it was already seen)
1
2
3
4
5
6
7
8
pub fn star_2(data: &PuzzleData) -> SolType {
solve(
data,
|adj, visited, m, n| (visited >> adj) & 1 == 0 || (m == n + 1 && adj == 0),
|poi, visited| (visited >> poi) & 1 == 0 || poi == 0,
|m, n| m == n + 1,
)
}
Tests
The test for part 2 is not specified in the puzzle input but a simple extension of the test for part 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#[cfg(test)]
mod tests {
use super::*;
const CONTENT: &str = r#"###########
#0.1.....2#
#.#######.#
#4.......3#
###########
"#;
#[test]
pub fn test_star_1() {
assert_eq!(14, star_1(&CONTENT.into()));
}
#[test]
pub fn test_star_2() {
assert_eq!(20, star_2(&CONTENT.into()));
}
}
Day 25: Clock Signal
Rust solution to AoC|2016|25.
A final day of operations on registers.
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
pub mod input {
use crate::{Op, Program, Val};
impl From<&str> for Val {
fn from(value: &str) -> Self {
let b = value.as_bytes()[0];
match b {
b'a'..=b'z' => Self::Reg((b - b'a') as _),
_ => Self::Val(value.parse().unwrap()),
}
}
}
impl From<&str> for Op {
fn from(s: &str) -> Self {
let mut words = s.split_ascii_whitespace();
match words.next() {
Some("cpy") => Self::Cpy(
words.next().unwrap().into(),
(words.next().unwrap().as_bytes()[0] - b'a') as _,
),
Some("inc") => Self::Inc((words.next().unwrap().as_bytes()[0] - b'a') as _),
Some("dec") => Self::Dec((words.next().unwrap().as_bytes()[0] - b'a') as _),
Some("jnz") => {
Self::Jnz(words.next().unwrap().into(), words.next().unwrap().into())
}
Some("out") => Self::Out(words.next().unwrap().into()),
_ => panic!("Cannot parse {}", s),
}
}
}
impl From<&str> for Program {
fn from(s: &str) -> Self {
Self(s.lines().map(Op::from).collect())
}
}
}
Star 1
Find the initial value for register a that leads to an infinite loop producing the desired output sequence.
Simulate for different initial values of a. Whenever an output is transmit, store the state to detect loops later.
If invalid outputs are produced, the outputs do not come in the right sequence or the program terminates, the initial value of a is inadequate. Otherwise the solution is found once an output state repeats.
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
impl Val {
pub fn get(&self, r: &[SolType]) -> SolType {
match self {
Val::Reg(idx) => r[*idx],
Val::Val(v) => *v,
}
}
}
impl Op {
pub fn execute(&self, r: &mut [SolType], p: &mut usize) -> Option<SolType> {
// println!("Executing ops[{}] = {:?} on {:?}", p, self, r);
match self {
Op::Cpy(v, idx) => (r[*idx], *p) = (v.get(r), *p + 1),
Op::Inc(idx) => (r[*idx], *p) = (r[*idx] + 1, *p + 1),
Op::Dec(idx) => (r[*idx], *p) = (r[*idx] - 1, *p + 1),
Op::Jnz(v1, v2) if v1.get(r) != 0 => *p = p.wrapping_add_signed(v2.get(r) as _),
Op::Jnz(_, _) => *p += 1,
Op::Out(v) => {
*p += 1;
return Some(v.get(r));
}
}
None
}
}
pub fn solve(mut r: [SolType; 4], ops: &[Op]) -> bool {
let mut prev_o = None;
let mut o_states = HashSet::new();
let mut p = 0;
while p < ops.len() {
if let Some(o) = ops[p].execute(&mut r, &mut p) {
let rep = !o_states.insert((o, r));
if o != 0 && o != 1 {
// bad output
return false;
}
if let Some(prev_o) = prev_o {
if prev_o != (o + 1) & 1 {
// invalid sequence
return false;
} else if rep {
// repetition found
return true;
}
}
prev_o = Some(o);
}
}
false
}
pub fn star_1(Program(ops): &Program) -> SolType {
(1..)
.find(|&a| solve([a, 0, 0, 0], ops.to_owned()))
.unwrap()
}