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    avail: u32,
70}
71
72pub fn parse(input: &str) -> Vec<Node> {
73    input
74        .iter_unsigned()
75        .chunk::<6>()
76        .map(|[x, y, _, used, avail, _]| Node { x, y, used, avail })
77        .collect()
78}
79
80/// Filter the used and available space in ascending order to find the viable pairs efficiently.
81pub fn part1(input: &[Node]) -> usize {
82    let mut used: Vec<_> = input.iter().map(|n| n.used).filter(|&n| n > 0).collect();
83    used.sort_unstable();
84
85    let mut avail: Vec<_> = input.iter().map(|n| n.avail).collect();
86    avail.sort_unstable();
87
88    let mut i = 0;
89    let mut viable = 0;
90
91    for next in used {
92        while i < avail.len() && avail[i] < next {
93            i += 1;
94        }
95        viable += avail.len() - i;
96    }
97
98    viable
99}
100
101pub fn part2(input: &[Node]) -> u32 {
102    let mut width = 0;
103    let mut empty_x = 0;
104    let mut empty_y = 0;
105    let mut wall_x = u32::MAX;
106
107    for &Node { x, y, used, .. } in input {
108        width = width.max(x + 1);
109
110        if used == 0 {
111            empty_x = x;
112            empty_y = y;
113        }
114
115        // Large nodes are bigger than 100T.
116        if used >= 100 {
117            wall_x = wall_x.min(x - 1);
118        }
119    }
120
121    // Move left to avoid wall.
122    let a = empty_x - wall_x;
123    // Move up to first row.
124    let b = empty_y;
125    // Move right to spot in front of data.
126    let c = width - 2 - wall_x;
127    // Move data into empty spot.
128    let d = 1;
129    // Repeatedly move empty spot 4 places around from behind data then move data one spot left.
130    let e = 5 * (width - 2);
131
132    a + b + c + d + e
133}
aoc/year2016/day22.rs

aoc/year2016/
day22.rs
