advent_of_code/year2016/
day22.rs

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
use crate::input::Input;
use std::collections::VecDeque;

struct Node {
    position: (u8, u8),
    size: u16,
    used: u16,
}

impl Node {
    const fn available(&self) -> u16 {
        self.size - self.used
    }
}

fn dist(
    dimensions: (u8, u8),
    mut grid: Vec<bool>,
    start: (u8, u8),
    destination: (u8, u8),
) -> Result<usize, String> {
    let mut queue = VecDeque::new();
    queue.push_back((0, start));

    while let Some((path_length, position)) = queue.pop_front() {
        let grid_idx =
            usize::from(position.1) * usize::from(dimensions.0) + usize::from(position.0);

        if grid[grid_idx] {
            continue;
        }
        if position == destination {
            return Ok(path_length);
        }

        grid[grid_idx] = true;

        if position.0 != 0 {
            queue.push_back((path_length + 1, (position.0 - 1, position.1)));
        }
        if position.0 != dimensions.0 - 1 {
            queue.push_back((path_length + 1, (position.0 + 1, position.1)));
        }
        if position.1 != 0 {
            queue.push_back((path_length + 1, (position.0, position.1 - 1)));
        }
        if position.1 != dimensions.1 - 1 {
            queue.push_back((path_length + 1, (position.0, position.1 + 1)));
        }
    }

    Err(format!("No path found from {start:?} to {destination:?}"))
}

pub fn solve(input: &Input) -> Result<u32, String> {
    let error_mapper = |_| "Invalid input";

    let mut nodes = Vec::new();

    for line in input.text.lines() {
        if let Some(remainder) = line.strip_prefix("/dev/grid/node-") {
            let words = remainder.split_whitespace().collect::<Vec<_>>();

            let name_parts = words[0].split('-').collect::<Vec<_>>();
            let x = name_parts[0][1..].parse::<u8>().map_err(error_mapper)?;
            let y = name_parts[1][1..].parse::<u8>().map_err(error_mapper)?;

            let size = words[1][..words[1].len() - 1]
                .parse::<u16>()
                .map_err(error_mapper)?;
            let used = words[2][..words[2].len() - 1]
                .parse::<u16>()
                .map_err(error_mapper)?;
            nodes.push(Node {
                position: (x, y),
                used,
                size,
            });
        }
    }

    if input.is_part_one() {
        Ok(nodes
            .iter()
            .flat_map(|n1| {
                nodes.iter().filter(move |n2| {
                    n1.position != n2.position && n1.used > 0 && n1.used < n2.available()
                })
            })
            .count() as u32)
    } else {
        // TODO: From https://github.com/galenelias/AdventOfCode_2016/blob/master/src/Day22/mod.rs
        let bottom_right = nodes
            .iter()
            .map(|node| node.position)
            .max()
            .ok_or("No bottom right node")?;
        let dimensions = (bottom_right.0 + 1, bottom_right.1 + 1);
        let wall_threshold = nodes
            .iter()
            .filter(|node| node.position.1 == 0)
            .map(|node| node.size)
            .max()
            .ok_or("No wall threshold")?;
        let mut grid = vec![true; usize::from(dimensions.0) * usize::from(dimensions.1)];

        for node in nodes.iter() {
            grid[usize::from(node.position.1) * usize::from(dimensions.0)
                + usize::from(node.position.0)] = node.size > wall_threshold;
        }

        let empty_pos = nodes
            .iter()
            .find(|node| node.used == 0 && node.size > 0)
            .ok_or("No empty node")?
            .position;
        let payload_pos = (dimensions.0 - 1, 0);
        let dist_to_payload = dist(dimensions, grid.clone(), empty_pos, payload_pos)?;
        let dist_to_home = dist(dimensions, grid, (payload_pos.0 - 1, payload_pos.1), (0, 0))?;
        Ok((dist_to_payload + 5 * dist_to_home) as u32)
    }
}

#[test]
pub fn tests() {
    use crate::input::{test_part_one, test_part_two};

    let real_input = include_str!("day22_input.txt");
    test_part_one!(real_input => 901);
    test_part_two!(real_input => 238);
}