aoc/year2016/
day22.rs

1//! # Grid Computing
2//!
3//! Part two is a decoy that can be solved in constant time with some analysis.
4//! Printing the actual node layout shows a structure similar to:
5//!
6//! ```none
7//!     O......G
8//!     ........
9//!     ..######
10//!     ........
11//!     .....-..
12//! ```
13//!
14//! * `O` is our destination
15//! * `G` is the data
16//! * `#` are large nodes that can't be moved to neighbours, effectively acting as walls.
17//! * `-` is the empty node.
18//!
19//! First we move the empty spot in front of the data:
20//!
21//! ```none
22//!     O>>>>>>G
23//!     .^......
24//!     .^######
25//!     .^......
26//!     .<<<<-..
27//! ```
28//!
29//! Then we move the data into the empty spot.
30//!
31//! ```none
32//!     O.....G_
33//!     ........
34//!     ..######
35//!     ........
36//!     ........
37//! ```
38//!
39//! Finally, we move the data to the origin by repeating the same sequence of 5 moves.
40//! First moving the empty spot back around to in front of the data in 4 moves.
41//!
42//! ```none
43//!     O....^G_
44//!     .....^<v
45//!     ..######
46//!     ........
47//!     ........
48//! ```
49//!
50//! Then moving the data another spot to the left.
51//!
52//! ```none
53//!     O....G_.
54//!     ........
55//!     ..######
56//!     ........
57//!     ........
58//! ```
59//!
60//! To find the minimum number of steps we only need to find the `(x, y)` coordinates of the empty
61//! spot and the width of the wall, then add up the sequence of moves.
62use crate::util::iter::*;
63use crate::util::parse::*;
64
65pub struct Node {
66    x: u32,
67    y: u32,
68    used: u32,
69}
70
71pub fn parse(input: &str) -> Vec<Node> {
72    input.iter_unsigned().chunk::<6>().map(|[x, y, _, used, _, _]| Node { x, y, used }).collect()
73}
74
75/// No need to actually check node pairs: only the empty node can receive data, and all but
76/// the wall nodes can pair with the empty node but not each other.
77pub fn part1(input: &[Node]) -> usize {
78    // Skip the empty node and the large nodes bigger than 100T.
79    input.iter().filter(|Node { used, .. }| (1..100).contains(used)).count()
80}
81
82pub fn part2(input: &[Node]) -> u32 {
83    let mut width = 0;
84    let mut empty_x = 0;
85    let mut empty_y = 0;
86    let mut wall_x = u32::MAX;
87
88    for &Node { x, y, used } in input {
89        width = width.max(x + 1);
90
91        if used == 0 {
92            empty_x = x;
93            empty_y = y;
94        }
95
96        // Large nodes are bigger than 100T.
97        if used >= 100 {
98            wall_x = wall_x.min(x - 1);
99        }
100    }
101
102    // Move left to avoid wall.
103    let a = empty_x - wall_x;
104    // Move up to first row.
105    let b = empty_y;
106    // Move right to spot in front of data.
107    let c = width - 2 - wall_x;
108    // Move data into empty spot.
109    let d = 1;
110    // Repeatedly move the empty spot 4 places around from behind the data then move the data one spot left.
111    let e = 5 * (width - 2);
112
113    a + b + c + d + e
114}
aoc/year2016/day22.rs

aoc/year2016/
day22.rs
