Advent of Code 2019 solutions in Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData {
        pub masses: Vec<usize>,
    }

    impl From<&str> for PuzzleData {
        /// parse the puzzle input
        fn from(s: &str) -> Self {
            Self {
                masses: s
                    .lines()
                    .map(|line| line.parse())
                    .collect::<Result<_, _>>()
                    .unwrap(),
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn req_fuel(m: &usize) -> Option<usize> {
    if *m >= 6 {
        Some(m / 3 - 2)
    } else {
        None
    }
}

pub fn star_1(data: &PuzzleData) -> SolType1 {
    data.masses.iter().filter_map(req_fuel).sum()
}

1
2
3
4
5
6
pub fn star_2(data: &PuzzleData) -> SolType2 {
    data.masses
        .iter()
        .flat_map(|mass| successors(req_fuel(mass), req_fuel))
        .sum()
}

1
2
3
4
5
6
7
pub fn star_1(memory: &Memory) -> SolType {
    let mut code = IntCode::new(memory);
    code[1] = 12;
    code[2] = 2;
    code.run();
    code[0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
pub fn star_2(memory: &Memory) -> SolType {
    let mut code = IntCode::new(vec![]);
    (0..100 * 100)
        .find(|res| {
            code.reset(memory);
            code[1] = res / 100;
            code[2] = res % 100;
            code.run();
            code[0] == 19_690_720
        })
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
pub mod input {
    use std::iter::once;

    #[derive(Debug)]
    pub struct PuzzleData {
        pub wire_1: Vec<((isize, isize), isize)>,
        pub wire_2: Vec<((isize, isize), isize)>,
    }

    /// parse poly-line into a sequence of points together with the cumulative
    /// length to each of the points
    fn parse_line(line: &str) -> Vec<((isize, isize), isize)> {
        once(((0, 0), 0))
            .chain(
                line.split(',')
                    .map(|part| (part[1..].parse::<isize>().unwrap(), part.as_bytes()[0]))
                    .scan(((0, 0), 0), |((x, y), cum_steps), (steps, dir)| {
                        ((*x, *y), *cum_steps) = match dir {
                            b'R' => ((*x + steps, *y), *cum_steps + steps),
                            b'U' => ((*x, *y - steps), *cum_steps + steps),
                            b'L' => ((*x - steps, *y), *cum_steps + steps),
                            b'D' => ((*x, *y + steps), *cum_steps + steps),
                            _ => panic!("Unexpected direction: {}", dir as char),
                        };
                        Some(((*x, *y), *cum_steps))
                    }),
            )
            .collect()
    }

    impl From<&str> for PuzzleData {
        /// parse the puzzle input
        fn from(s: &str) -> Self {
            let mut lines = s.lines();
            Self {
                wire_1: parse_line(lines.next().unwrap()),
                wire_2: parse_line(lines.next().unwrap()),
            }
        }
    }
}

 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
/// Find intersections of two poly-lines (each segment is either horizontal 
/// or vertical)
/// 
/// Assumption: there are only real intersections of a horizontal segment
/// with a vertical segments, no overlapping horizontal or vertical segments
/// 
/// Each intersection is represented by its coordinates and the steps from 
/// the origin to the intersection
pub fn intersections(
    wire_1: &[((isize, isize), isize)],
    wire_2: &[((isize, isize), isize)],
) -> Vec<((isize, isize), isize, isize)> {
    wire_1
        .iter()
        .zip(wire_1.iter().skip(1))
        .flat_map(|(((x_1_a, y_1_a), l_1), ((x_1_b, y_1_b), _))| {
            wire_2.iter().zip(wire_2.iter().skip(1)).filter_map(
                move |(((x_2_a, y_2_a), l_2), ((x_2_b, y_2_b), _))| {
                    if (x_2_a != &0 || y_1_a != &0)
                        && x_2_a == x_2_b
                        && y_1_a == y_1_b
                        && x_2_a >= x_1_a.min(x_1_b)
                        && x_2_a <= x_1_a.max(x_1_b)
                        && y_1_a >= y_2_a.min(y_2_b)
                        && y_1_a <= y_2_a.max(y_2_b)
                    {
                        Some((
                            (*x_2_a, *y_1_a),
                            *l_1 + (x_2_a - x_1_a).abs(),
                            *l_2 + (y_1_a - y_2_a).abs(),
                        ))
                    } else if (x_1_a != &0 || y_2_a != &0)
                        && y_2_a == y_2_b
                        && x_1_a == x_1_b
                        && y_2_a >= y_1_a.min(y_1_b)
                        && y_2_a <= y_1_a.max(y_1_b)
                        && x_1_a >= x_2_a.min(x_2_b)
                        && x_1_a <= x_2_a.max(x_2_b)
                    {
                        Some((
                            (*x_1_a, *y_2_a),
                            *l_1 + (y_2_a - y_1_a).abs(),
                            *l_2 + (x_1_a - x_2_a).abs(),
                        ))
                    } else {
                        None
                    }
                },
            )
        })
        .collect()
}

pub fn star_1(data: &PuzzleData) -> SolType1 {
    let xs = intersections(&data.wire_1, &data.wire_2);
    xs.iter()
        .map(|((x, y), _, _)| x.abs() + y.abs())
        .min()
        .unwrap()
}

1
2
3
4
pub fn star_2(data: &PuzzleData) -> SolType2 {
    let xs = intersections(&data.wire_1, &data.wire_2);
    xs.iter().map(|(_, l_1, l_2)| *l_1 + *l_2).min().unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7
"#;

    #[test]
    pub fn test_intersections() {
        let content = "R8,U5,L5,D3\nU7,R6,D4,L4\n";
        let data = PuzzleData::from(content);
        let mut xs = intersections(&data.wire_1, &data.wire_2);
        xs.sort_unstable();
        assert_eq!(vec![((3, -3), 20, 20), ((6, -5), 15, 15)], xs);
    }

    #[test]
    pub fn test_from() {
        let content = "R8,U5,L5,D3\nU7,R6,D4,L4\n";
        let data = PuzzleData::from(content);
        assert_eq!(
            vec![
                ((0, 0), 0),
                ((8, 0), 8),
                ((8, -5), 13),
                ((3, -5), 18),
                ((3, -2), 21)
            ],
            data.wire_1
        );
        assert_eq!(
            vec![
                ((0, 0), 0),
                ((0, -7), 7),
                ((6, -7), 13),
                ((6, -3), 17),
                ((2, -3), 21)
            ],
            data.wire_2
        );
    }

    #[test]
    pub fn test_star_1() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(135, star_1(&data));
    }

    #[test]
    pub fn test_star_2() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(410, star_2(&data));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData {
        pub range: (usize, usize),
    }

    impl From<&str> for PuzzleData {
        /// parse the puzzle input
        fn from(s: &str) -> Self {
            Self {
                range: s
                    .trim()
                    .split_once('-')
                    .map(|(from, to)| (from.parse().unwrap(), to.parse().unwrap()))
                    .unwrap(),
            }
        }
    }
}

 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 const N: usize = 6;

/// Convert number to array of six (lowest) digits
///
/// # Examples
/// ```
/// # use mr_kaffee_2019_04::*;
/// let v = 123456;
/// let d = to_digits(v);
/// assert_eq!([1, 2, 3, 4, 5, 6], d);
/// ```
pub fn to_digits(mut v: usize) -> [u8; N] {
    let mut d = [0; N];
    for k in 0..N {
        d[N - 1 - k] = (v % 10) as _;
        v /= 10;
    }
    d
}

pub fn solve<F: Fn(&[u8; N]) -> bool>((from, to): (usize, usize), f: F) -> SolType1 {
    let mut d = to_digits(from);
    let to = to_digits(to);

    // make sure d meets 'never decrease' condition
    for k in 1..N {
        if d[k] < d[k - 1] {
            for l in k..N {
                d[l] = d[k - 1];
            }
            break;
        }
    }

    let mut count = 0;
    while d < to {
        // increment counter if condition is met
        if f(&d) {
            count += 1;
        }

        // increment digits respecting 'never decrease' rule
        let (mut inc, mut k) = (1, N - 1);
        while inc > 0 {
            (inc, k) = if d[k] < 10 - inc {
                d[k] += inc;
                for l in k + 1..N {
                    d[l] = d[k];
                }
                (0, k)
            } else {
                (1, k - 1)
            }
        }
    }
    count
}

pub fn star_1(data: &PuzzleData) -> SolType1 {
    solve(data.range, |d| (1..N).any(|k| d[k] == d[k - 1]))
}

1
2
3
4
5
6
7
pub fn star_2(data: &PuzzleData) -> SolType2 {
    solve(data.range, |d| {
        (1..N).any(|k| {
            d[k] == d[k - 1] && (k == 1 || d[k - 2] != d[k]) && (k == N - 1 || d[k + 1] != d[k])
        })
    })
}

1
2
3
4
5
6
pub fn star_1(memory: &Memory) -> SolType {
    let mut code = IntCode::<isize,isize>::from(memory);
    code.input = 1;
    code.run();
    code.output
}

1
2
3
4
5
6
pub fn star_2(memory: &Memory) -> SolType {
    let mut code = IntCode::<isize,isize>::from(memory);
    code.input = 5;
    code.run();
    code.output
}

 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 std::collections::{HashMap, HashSet};

    #[derive(Debug)]
    pub struct PuzzleData<'a> {
        pub map: HashMap<&'a str, HashSet<&'a str>>,
        pub inv_map: HashMap<&'a str, &'a str>,
    }

    impl<'a> From<&'a str> for PuzzleData<'a> {
        /// parse the puzzle input
        fn from(s: &'a str) -> Self {
            let (map, inv_map) = s.lines().map(|l| l.split_once(')').unwrap()).fold(
                (HashMap::new(), HashMap::new()),
                |(mut map, mut inv_map), (c, o)| {
                    map.entry(c).or_insert_with(HashSet::new).insert(o);
                    inv_map.insert(o, c);
                    (map, inv_map)
                },
            );
            Self { map, inv_map }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
fn count_orbits(map: &HashMap<&str, HashSet<&str>>, center: &str) -> (usize, usize) {
    let (mut cnt_obj, mut cnt_orb) = (0, 0);
    if let Some(orbits) = map.get(center) {
        for orbit in orbits {
            // everything that orbits around orbit, indirectly orbits around
            // center, orbit also orbits directly around center
            let (cnt_obj_, cnt_orb_) = count_orbits(map, orbit);
            (cnt_obj, cnt_orb) = (cnt_obj + cnt_obj_ + 1, cnt_orb + cnt_orb_ + cnt_obj_ + 1);
        }
    }
    (cnt_obj, cnt_orb)
}

pub fn star_1(data: &PuzzleData) -> SolType1 {
    count_orbits(&data.map, "COM").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
pub fn star_2(data: &PuzzleData) -> SolType2 {
    // path from YOU to COM
    let mut path_you = VecDeque::new();
    let mut cur = "YOU";
    while let Some(&obj) = data.inv_map.get(cur) {
        path_you.push_back(obj);
        cur = obj;
    }

    // path from SAN to COM
    let mut path_san = VecDeque::new();
    let mut cur = "SAN";
    while let Some(&obj) = data.inv_map.get(cur) {
        path_san.push_back(obj);
        cur = obj;
    }

    // remove common parts
    while path_you.back() == path_san.back() {
        path_you.pop_back();
        path_san.pop_back();
    }

    path_you.len() + path_san.len()
}

 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
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT_1: &str = r#"COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
"#;

    const CONTENT_2: &str = r#"COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
K)YOU
I)SAN
"#;

    #[test]
    pub fn test_from() {
        let data = PuzzleData::from(CONTENT_1);
        assert_eq!(
            HashMap::from([
                ("COM", HashSet::from(["B"])),
                ("B", HashSet::from(["G", "C"])),
                ("G", HashSet::from(["H"])),
                ("C", HashSet::from(["D"])),
                ("D", HashSet::from(["E", "I"])),
                ("E", HashSet::from(["J", "F"])),
                ("J", HashSet::from(["K"])),
                ("K", HashSet::from(["L"]))
            ]),
            data.map
        );
        assert_eq!(
            HashMap::from([
                ("B", "COM"),
                ("C", "B"),
                ("D", "C"),
                ("E", "D"),
                ("F", "E"),
                ("G", "B"),
                ("H", "G"),
                ("I", "D"),
                ("J", "E"),
                ("K", "J"),
                ("L", "K")
            ]),
            data.inv_map
        );
    }

    #[test]
    pub fn test_count_orbits() {
        let data = PuzzleData::from(CONTENT_1);
        assert_eq!((0, 0), count_orbits(&data.map, "L"));
        assert_eq!((1, 1), count_orbits(&data.map, "K"));
        assert_eq!((2, 3), count_orbits(&data.map, "J"));
        assert_eq!((4, 7), count_orbits(&data.map, "E"));
    }

    #[test]
    pub fn test_star_1() {
        let data = PuzzleData::from(CONTENT_1);
        assert_eq!(42, star_1(&data));
    }

    #[test]
    pub fn test_star_2() {
        let data = PuzzleData::from(CONTENT_2);
        assert_eq!(4, star_2(&data));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pub fn star_1(memory: &Memory) -> SolType {
    let mut max_out = 0;
    for phases in Permutations::from(0..5) {
        let mut out = 0;
        for phase in phases {
            let mut code = IntCode::from((memory, VecDeque::from([phase, out]), 0));
            code.run();
            out = code.output;
        }
        max_out = max_out.max(out);
    }
    max_out
}

 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(memory: &Memory) -> SolType {
    let mut max_out = 0;
    for phases in Permutations::from(5..10) {
        // initialize codes
        let mut codes = phases
            .iter()
            .map(|&phase| {
                let mut code = IntCode::from((memory, (), 0));
                code.run();
                code.run_with_input(phase);
                code
            })
            .collect::<Vec<_>>();
        'outer: loop {
            for k in 0..phases.len() {
                // get output from previous, this also works for initial output,
                // since outputs are initialized to 0
                let out = codes[(k + phases.len() - 1) % phases.len()].output;
                if !codes[k].run_with_input(out) {
                    // if code is not expecting inputs anymore, stop
                    break 'outer;
                }
            }
        }
        max_out = max_out.max(codes.last().unwrap().output);
    }
    max_out
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData<'a>(pub &'a [u8]);

    impl<'a> From<&'a str> for PuzzleData<'a> {
        /// parse the puzzle input
        fn from(s: &'a str) -> Self {
            Self(s.trim().as_bytes())
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub const W: usize = 25;
pub const H: usize = 6;

pub fn star_1(PuzzleData(data): &PuzzleData) -> SolType1 {
    (0..data.len())
        .step_by(W * H)
        .map(|k| {
            (k..k + W * H).fold((0, 0, 0), |(zeros, ones, twos), l| {
                (
                    zeros + (data[l] == b'0') as usize,
                    ones + (data[l] == b'1') as usize,
                    twos + (data[l] == b'2') as usize,
                )
            })
        })
        .min_by_key(|(zeros, _, _)| *zeros)
        .map(|(_, ones, twos)| ones * twos)
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub fn star_2(PuzzleData(data): &PuzzleData) -> SolType2 {
    let image = (0..data.len())
        .step_by(W * H)
        .fold(vec![b'2'; W * H], |mut image, k| {
            image
                .iter_mut()
                .enumerate()
                .filter(|(_, v)| **v == b'2')
                .for_each(|(l, v)| {
                    *v = match data[k + l] {
                        b'0' => DARK as u8,
                        b'1' => LIT as u8,
                        v => v,
                    }
                });
            image
        });
    image.decode(0).unwrap()
}

1
2
3
4
5
pub fn star_1(memory: &Memory) -> SolType {
    let mut code = IntCode::from((memory, 1, 0));
    code.run();
    code.output
}

1
2
3
4
5
pub fn star_2(memory: &Memory) -> SolType {
    let mut code = IntCode::from((memory, 2, 0));
    code.run();
    code.output
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
pub mod input {
    use crate::Asteroid;

    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<Asteroid>);

    impl From<&str> for PuzzleData {
        /// parse the puzzle input
        fn from(s: &str) -> Self {
            let w = s.find('\n').unwrap();
            Self(
                s.bytes()
                    .enumerate()
                    .filter(|(_, v)| *v == b'#')
                    .map(|(p, _)| (p % (w + 1), p / (w + 1)).into())
                    .collect(),
            )
        }
    }
}

 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 gcd(mut a: isize, mut b: isize) -> isize {
    while b != 0 {
        (a, b) = (b, a % b);
    }
    a
}

pub fn get_in_sight(
    asteroids: &[Asteroid],
    k_1: usize,
) -> HashMap<(isize, isize), BTreeSet<(isize, Asteroid)>> {
    let mut directions = HashMap::new();
    let a_1 = asteroids[k_1];
    for (_, a_2) in asteroids.iter().enumerate().filter(|(k_2, _)| k_1 != *k_2) {
        let (d_c, d_r) = (
            a_2.col as isize - a_1.col as isize,
            a_2.row as isize - a_1.row as isize,
        );
        let q = gcd(d_c.abs(), d_r.abs());
        directions
            .entry((d_c / q, d_r / q))
            .or_insert(BTreeSet::new())
            .insert((d_c.abs() + d_r.abs(), *a_2));
    }
    directions
}

pub fn star_1(PuzzleData(asteroids): &PuzzleData) -> SolType1 {
    (0..asteroids.len())
        .map(|k_1| get_in_sight(asteroids, k_1).len())
        .max()
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
pub fn star_2(PuzzleData(asteroids): &PuzzleData) -> SolType2 {
    let (_, map) = (0..asteroids.len())
        .map(|k_1| (k_1, get_in_sight(asteroids, k_1)))
        .max_by_key(|(_, map)| map.len())
        .unwrap();

    // add directions to vec and sort by angle
    //          0.5                    0.0
    //     (-/+) | (+/+)          (-/-) | (+/-)
    // 1.0 ------+------ 0.0  1.5 ------+------ 0.5
    //     (-/-) | (+/-)          (-/+) | (+/+)
    //         -0.5                    1.0
    // standard math          laser beam rotation
    // => have to use atan2(col, -row)
    let mut dirs = map
        .keys()
        .map(|(col, row)| {
            (
                (f64::atan2(*col as _, -*row as _) + 2.0 * PI) % (2.0 * PI),
                (col, row),
            )
        })
        .collect::<Vec<_>>();
    dirs.sort_unstable_by(|(a_1, _), (a_2, _)| a_1.partial_cmp(a_2).unwrap());

    // get 200th direction
    let (_, (&d_c, &d_r)) = dirs[199];
    // get first asteroid in that direction
    let (_, asteroid) = map.get(&(d_c, d_r)).unwrap().first().copied().unwrap();

    100 * asteroid.col + asteroid.row
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"......#.#.
#..#.#....
..#######.
.#.#.###..
.#..#.....
..#....#.#
#..#....#.
.##.#..###
##...#..#.
.#....####
"#;

    const CONTENT_SMALL: &str = r#".#..#
.....
#####
....#
...##
"#;

    #[test]
    pub fn test_from() {
        let data = PuzzleData::from(CONTENT_SMALL);
        assert_eq!(
            vec![
                Asteroid::from((1, 0)),
                Asteroid::from((4, 0)),
                Asteroid::from((0, 2)),
                Asteroid::from((1, 2)),
                Asteroid::from((2, 2)),
                Asteroid::from((3, 2)),
                Asteroid::from((4, 2)),
                Asteroid::from((4, 3)),
                Asteroid::from((3, 4)),
                Asteroid::from((4, 4))
            ],
            data.0
        );
    }

    #[test]
    pub fn test_star_1() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(33, star_1(&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
#[derive(Debug)]
pub struct HullPaintingRobot {
    pub pos: (isize, isize),
    pub dir: (isize, isize),
    pub hull: HashMap<(isize, isize), bool>,
    pub exp_direction: bool,
}

impl Default for HullPaintingRobot {
    fn default() -> Self {
        Self {
            pos: (0, 0),
            dir: (0, -1),
            hull: HashMap::new(),
            exp_direction: false,
        }
    }
}

impl Input for HullPaintingRobot {
    fn read(&mut self) -> isize {
        self.hull.get(&self.pos).copied().unwrap_or(false) as _
    }
}

impl Output for HullPaintingRobot {
    fn write(&mut self, value: isize) {
        if self.exp_direction {
            match value {
                1 => self.dir = (-self.dir.1, self.dir.0),
                _ => self.dir = (self.dir.1, -self.dir.0),
            }
            self.pos = (self.pos.0 + self.dir.0, self.pos.1 + self.dir.1);
        } else {
            match value {
                1 => self.hull.insert(self.pos, true),
                _ => self.hull.insert(self.pos, false),
            };
        }
        self.exp_direction = !self.exp_direction;
    }
}

1
2
3
4
5
6
7
pub fn star_1(memory: &Memory) -> SolType1 {
    let robot = HullPaintingRobot::default();
    let wrapper = RefCell::new(robot);
    let mut code = IntCode::from((memory, &wrapper, &wrapper));
    code.run();
    wrapper.take().hull.len()
}

 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(memory: &Memory) -> SolType2 {
    // simulate robot
    let robot = HullPaintingRobot {
        hull: HashMap::from([((0, 0), true)]),
        ..Default::default()
    };
    let wrapper = RefCell::new(robot);
    let mut code = IntCode::from((memory, &wrapper, &wrapper));
    code.run();

    // calculate bounding box
    let hull = wrapper.take().hull;
    let (col_min, row_min, col_max, row_max) = hull.iter().filter(|&(_, &c)| c).fold(
        (isize::MAX, isize::MAX, isize::MIN, isize::MIN),
        |(c_mn, r_mn, c_mx, r_mx), ((c, r), _)| {
            (c_mn.min(*c), r_mn.min(*r), c_mx.max(c + 1), r_mx.max(r + 1))
        },
    );

    // interpret result
    use letters::{DARK, HEIGHT, LIT, WIDTH};
    let w = ((col_max - col_min) as usize).div_ceil(WIDTH) * WIDTH;
    let h = ((row_max - row_min) as usize).div_ceil(HEIGHT) * HEIGHT;
    let mut display = vec![DARK as u8; w * h];
    for ((col, row), _) in hull.iter().filter(|&(_, &c)| c) {
        display[(col - col_min) as usize + w * (row - row_min) as usize] = LIT as u8;
    }
    display.decode(0).unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<[isize; 6]>);

    impl From<&str> for PuzzleData {
        /// parse the puzzle input
        fn from(s: &str) -> Self {
            Self(
                s.lines()
                    .map(|line| {
                        line.strip_prefix('<')
                            .and_then(|line| line.strip_suffix('>'))
                            .unwrap()
                            .split(", ")
                            .map(|p| p[2..].parse().unwrap())
                    })
                    .map(|mut it| {
                        [
                            it.next().unwrap(),
                            it.next().unwrap(),
                            it.next().unwrap(),
                            0,
                            0,
                            0,
                        ]
                    })
                    .collect(),
            )
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
pub fn simulate(moons: &[[isize; 6]], steps: usize) -> SolType {
    let mut moons = moons.to_owned();
    for _ in 0..steps {
        for m_1 in 0..moons.len() - 1 {
            for m_2 in m_1..moons.len() {
                for d in 0..3 {
                    match moons[m_1][d].cmp(&moons[m_2][d]) {
                        Ordering::Less => {
                            moons[m_1][d + 3] += 1;
                            moons[m_2][d + 3] -= 1;
                        }
                        Ordering::Greater => {
                            moons[m_1][d + 3] -= 1;
                            moons[m_2][d + 3] += 1;
                        }
                        _ => (),
                    }
                }
            }
        }
        for moon in &mut moons {
            for d in 0..3 {
                moon[d] += moon[d + 3];
            }
        }
    }

    moons
        .iter()
        .map(|moon| {
            moon[0..3].iter().map(|p| p.abs()).sum::<isize>()
                * moon[3..6].iter().map(|v| v.abs()).sum::<isize>()
        })
        .sum::<isize>() as _
}

pub fn star_1(PuzzleData(moons): &PuzzleData) -> SolType {
    simulate(moons, 1_000)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
pub fn find_period(moons: &[[isize; 6]], dim: usize) -> usize {
    let mut moons = moons
        .iter()
        .map(|moon| [moon[dim], moon[dim + 3]])
        .collect::<Vec<_>>();

    let moons_0 = moons.clone();

    for k in 1..usize::MAX {
        for m_1 in 0..moons.len() - 1 {
            for m_2 in m_1..moons.len() {
                match moons[m_1][0].cmp(&moons[m_2][0]) {
                    Ordering::Less => {
                        moons[m_1][1] += 1;
                        moons[m_2][1] -= 1;
                    }
                    Ordering::Greater => {
                        moons[m_1][1] -= 1;
                        moons[m_2][1] += 1;
                    }
                    _ => (),
                }
            }
        }
        for moon in &mut moons {
            moon[0] += moon[1];
        }

        if moons_0 == moons {
            return k;
        }
    }

    unreachable!()
}

pub fn gcd(mut a: usize, mut b: usize) -> usize {
    while b != 0 {
        (a, b) = (b, a % b);
    }
    a
}

pub fn star_2(PuzzleData(moons): &PuzzleData) -> SolType {
    let period_x = find_period(moons, 0);
    let period_y = find_period(moons, 1);
    let period_z = find_period(moons, 2);

    let q = gcd(period_x, period_y);
    let lcm = period_x * period_y / q;
    let q = gcd(lcm, period_z);
    
    lcm * period_z / q
}

 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#"<x=-8, y=-10, z=0>
<x=5, y=5, z=10>
<x=2, y=-7, z=3>
<x=9, y=-8, z=-3>
"#;

    #[test]
    pub fn test_from() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(
            vec![
                [-8, -10, 0, 0, 0, 0],
                [5, 5, 10, 0, 0, 0],
                [2, -7, 3, 0, 0, 0],
                [9, -8, -3, 0, 0, 0]
            ],
            data.0
        );
    }

    #[test]
    pub fn test_simulate() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(1_940, simulate(&data.0, 100));
    }

    #[test]
    pub fn test_star_2() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(4_686_774_924, star_2(&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
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
#[derive(Debug, Default)]
pub struct Arcade {
    map: HashMap<(isize, isize), u8>,
    output_counter: u8,
    col: isize,
    row: isize,
    score: isize,
    cur_ball: Option<(isize, isize)>,
    prev_ball: Option<(isize, isize)>,
    paddle: Option<(isize, isize)>,
}

impl Display for Arcade {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let (c_mn, r_mn, c_mx, r_mx) = self.map.iter().fold(
            (isize::MAX, isize::MAX, isize::MIN, isize::MIN),
            |(c_mn, r_mn, c_mx, r_mx), ((c, r), _)| {
                (c_mn.min(*c), r_mn.min(*r), c_mx.max(c + 1), r_mx.max(r + 1))
            },
        );
        for r in r_mn..r_mx {
            for c in c_mn..c_mx {
                match self.map.get(&(c, r)).unwrap_or(&0) {
                    0 => ' '.fmt(f)?,
                    1 => '#'.fmt(f)?,
                    2 => '$'.fmt(f)?,
                    3 => '='.fmt(f)?,
                    4 => 'O'.fmt(f)?,
                    _ => unreachable!(),
                }
            }
            '\n'.fmt(f)?;
        }
        Ok(())
    }
}

impl Input for Arcade {
    fn read(&mut self) -> isize {
        #[cfg(feature = "animate")]
        {
            print!("\x1B[1;1H\x1B[J"); // clear console
            println!("Score: {:>8}", self.score);
            print!("{}", self);
            std::thread::sleep(std::time::Duration::from_millis(3));
        }
        if self.cur_ball.is_none() || self.paddle.is_none() {
            return 0;
        }

        let (c_cur_ball, r_cur_ball) = self.cur_ball.unwrap();
        let (c_prev_ball, r_prev_ball) = self.prev_ball.unwrap_or((c_cur_ball, r_cur_ball));
        let (c_paddle, r_paddle) = self.paddle.unwrap();

        let c_tar = if r_prev_ball < r_cur_ball {
            // predict where the ball will be once it is just above the paddle
            c_cur_ball
                + (r_paddle - 1 - r_cur_ball) * (c_cur_ball - c_prev_ball)
                    / (r_cur_ball - r_prev_ball)
        } else {
            // just follow the ball
            c_cur_ball
        };

        match c_tar.cmp(&c_paddle) {
            Ordering::Less => -1,
            Ordering::Equal => 0,
            Ordering::Greater => 1,
        }
    }
}

impl Output for Arcade {
    fn write(&mut self, value: isize) {
        match self.output_counter {
            0 => self.col = value,
            1 => self.row = value,
            2 => {
                if self.col == -1 && self.row == 0 {
                    self.score = value;
                } else {
                    match value {
                        3 => self.paddle = Some((self.col, self.row)), // paddle
                        4 => {
                            // ball
                            self.prev_ball = self.cur_ball;
                            self.cur_ball = Some((self.col, self.row))
                        }
                        _ => (),
                    }
                    self.map.insert((self.col, self.row), value as _);
                }
            }
            _ => unreachable!(),
        }
        self.output_counter = (self.output_counter + 1) % 3;
    }
}

1
2
3
4
5
6
pub fn star_1(memory: &Memory) -> SolType1 {
    let arcade = Arcade::default();
    let mut code = IntCode::from((memory, (), arcade));
    code.run();
    code.output.map.iter().filter(|&(_, &t)| t == 2).count()
}

1
2
3
4
5
6
7
8
pub fn star_2(memory: &Memory) -> SolType2 {
    let arcade = Arcade::default();
    let wrapper = RefCell::new(arcade);
    let mut code = IntCode::from((memory, &wrapper, &wrapper));
    code[0] = 2;
    code.run();
    wrapper.take().score
}

 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::HashMap;

    #[derive(Debug)]
    pub struct Reaction<'a> {
        pub inputs: Vec<(usize, &'a str)>,
        pub output: (usize, &'a str),
    }

    impl<'a> From<&'a str> for Reaction<'a> {
        fn from(s: &'a str) -> Self {
            s.split_once(" => ")
                .map(|(inputs, output)| Self {
                    inputs: inputs
                        .split(", ")
                        .map(|v| {
                            v.split_once(' ')
                                .map(|(q, n)| (q.parse().unwrap(), n))
                                .unwrap()
                        })
                        .collect(),
                    output: output
                        .split_once(' ')
                        .map(|(q, n)| (q.parse().unwrap(), n))
                        .unwrap(),
                })
                .unwrap()
        }
    }

    #[derive(Debug)]
    pub struct PuzzleData<'a>(pub HashMap<&'a str, Reaction<'a>>);

    impl<'a> From<&'a str> for PuzzleData<'a> {
        /// parse the puzzle input
        fn from(s: &'a str) -> Self {
            Self(
                s.lines()
                    .map(Reaction::from)
                    .map(|r| (r.output.1, r))
                    .collect(),
            )
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
pub fn required_ore<'a>(
    reactions: &HashMap<&'a str, Reaction<'a>>,
    inventory: &mut HashMap<&'a str, usize>,
    mut quantity: usize,
    name: &'a str,
) -> usize {
    if let Entry::Occupied(mut o) = inventory.entry(name) {
        if *o.get() >= quantity {
            *o.get_mut() -= quantity;
            return 0;
        } else {
            quantity -= *o.get();
            o.remove();
        }
    }

    if name == "ORE" {
        return quantity;
    }

    let reaction = reactions.get(name).unwrap();
    let n = quantity.div_ceil(reaction.output.0);
    if n * reaction.output.0 > quantity {
        *inventory.entry(name).or_insert(0) += n * reaction.output.0 - quantity;
    }

    reaction
        .inputs
        .iter()
        .map(|&(quantity, name)| required_ore(reactions, inventory, n * quantity, name))
        .sum()
}

pub fn star_1(PuzzleData(reactions): &PuzzleData) -> SolType {
    let mut inventory = HashMap::new();
    required_ore(reactions, &mut inventory, 1, "FUEL")
}

 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(PuzzleData(reactions): &PuzzleData) -> SolType {
    let avl = 1_000_000_000_000;

    let (mut fuel_l, mut fuel_h) = (0, 1);

    let mut inventory = HashMap::new();
    let mut req = required_ore(reactions, &mut inventory, fuel_h, "FUEL");

    while req <= avl {
        (fuel_l, fuel_h) = (fuel_h, (fuel_h + 1).max(avl / (req / fuel_h)));

        inventory.clear();
        req = required_ore(reactions, &mut inventory, fuel_h, "FUEL");
    }

    while fuel_h - fuel_l > 1 {
        let fuel = (fuel_l + fuel_h) / 2;

        inventory.clear();
        let req = required_ore(reactions, &mut inventory, fuel, "FUEL");

        *(if req > avl { &mut fuel_h } else { &mut fuel_l }) = fuel;
    }

    fuel_l
}

 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#"157 ORE => 5 NZVS
165 ORE => 6 DCFZ
44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL
12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ
179 ORE => 7 PSHF
177 ORE => 5 HKGWZ
7 DCFZ, 7 PSHF => 2 XJWVT
165 ORE => 2 GPVTF
3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT
"#;

    #[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!(13_312, star_1(&data));
    }

    #[test]
    pub fn test_star_2() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(82_892_753, star_2(&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
#[derive(Debug)]
struct RepairDroid {
    /// map of the area
    map: HashMap<(isize, isize), u8>,
    /// status received
    status: isize,
    /// current position
    pos: (isize, isize),
    /// requested next position
    req_pos: (isize, isize),
    /// path traveled so far
    path: Vec<Direction>,
    /// minimum moves to oxygen
    min_moves: usize,
    /// coordinate of oxygen
    oxygen: Option<(isize, isize)>,
}

impl Default for RepairDroid {
    fn default() -> Self {
        Self {
            map: HashMap::new(),
            status: 1,
            pos: (0, 0),
            req_pos: (0, 0),
            path: Vec::new(),
            min_moves: usize::MAX,
            oxygen: None,
        }
    }
}

 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 RepairDroid {
    const EMPTY: u8 = b'.';
    const WALL: u8 = b'#';
    const OXYGEN: u8 = b'O';

    /// process response ([`RepairDroid::status']) and calculate next command
    ///
    /// Return `None` to stop the int code program.
    pub fn update(&mut self) -> Option<isize> {
        // process response
        match self.status {
            0 => {
                self.path.pop();
                self.map.insert(self.req_pos, Self::WALL);
            }
            1 => {
                self.pos = self.req_pos;
                self.map.insert(self.pos, Self::EMPTY);
            }
            2 => {
                self.min_moves = self.min_moves.min(self.path.len());
                self.pos = self.req_pos;
                self.oxygen = Some(self.pos);
                self.map.insert(self.pos, Self::OXYGEN);
            }
            _ => panic!("Unexpected status: {}", self.status),
        }

        // calculate command
        Direction::DIRECTIONS
            .iter()
            .find(|d| !self.map.contains_key(&d.adjacent(self.pos)))
            .copied()
            .or(self.path.last().map(Direction::reverse))
            .map(|dir| {
                // set requested next position
                self.req_pos = dir.adjacent(self.pos);

                // update path (push or pop if reversing last element)
                match self.path.last() {
                    Some(last) if last.is_reverse(&dir) => {
                        self.path.pop();
                    }
                    _ => self.path.push(dir),
                }

                // send command
                dir.command()
            })
    }
}

impl Output for RepairDroid {
    fn write(&mut self, status: isize) {
        self.status = status;
    }
}

impl Input for RepairDroid {
    fn read(&mut self) -> isize {
        self.try_read().unwrap()
    }

    fn try_read(&mut self) -> Option<isize> {
        self.update()
    }
}

 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
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum Direction {
    East = 0,
    North = 1,
    West = 2,
    South = 3,
}

impl Direction {
    pub const DIRECTIONS: [Self; 4] = [Self::East, Self::North, Self::West, Self::South];
    pub const DELTAS: [(isize, isize); 4] = [(1, 0), (0, -1), (-1, 0), (0, 1)];
    pub const COMMANDS: [isize; 4] = [4, 1, 3, 2];

    pub fn command(&self) -> isize {
        Self::COMMANDS[*self as usize]
    }

    pub fn delta(&self) -> (isize, isize) {
        Self::DELTAS[*self as usize]
    }

    pub fn reverse(&self) -> Self {
        Self::DIRECTIONS[(*self as usize + 2) & 3]
    }

    pub fn is_reverse(&self, other: &Self) -> bool {
        ((*self as usize) + 2) & 3 == (*other as usize)
    }

    pub fn adjacent(&self, pos: (isize, isize)) -> (isize, isize) {
        let delta = self.delta();
        (pos.0 + delta.0, pos.1 + delta.1)
    }
}