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

//! # Grid Computing
//!
//! Part two is a decoy that can be solved in constant time with some analysis.
//! Printing the actual node layout shows a structure similar to:
//!
//! ```none
//!     O......G
//!     ........
//!     ..######
//!     ........
//!     .....-..
//! ```
//!
//! * `O` is our destination
//! * `G` is the data
//! * `#` are large nodes that can't be moved to neighbours, effectively acting as walls.
//! * `-` is the empty node.
//!
//! First we move the empty spot in front of the data:
//!
//! ```none
//!     O>>>>>>G
//!     .^......
//!     .^######
//!     .^......
//!     .<<<<-..
//! ```
//!
//! Then we move the data into the empty spot.
//!
//! ```none
//!     O.....G_
//!     ........
//!     ..######
//!     ........
//!     ........
//! ```
//!
//! Finally we move the data to the origin by repeating the same sequence of 5 moves.
//! First moving the empty spot back around to in front of the data in 4 moves.
//!
//! ```none
//!     O....^G_
//!     .....^<v
//!     ..######
//!     ........
//!     ........
//! ```
//!
//! Then moving the data another spot to the left.
//!
//! ```none
//!     O....G_.
//!     ........
//!     ..######
//!     ........
//!     ........
//! ```
//!
//! To find the minimum number of steps we only need to find the `(x, y)` coordinates of the empty
//! spot and the width of the wall, then add up the sequence of moves.
use crate::util::iter::*;
use crate::util::parse::*;

pub struct Node {
    x: u32,
    y: u32,
    used: u32,
    avail: u32,
}

pub fn parse(input: &str) -> Vec<Node> {
    input
        .iter_unsigned()
        .chunk::<6>()
        .map(|[x, y, _, used, avail, _]| Node { x, y, used, avail })
        .collect()
}

/// Filter the used and available space in ascending order to find the viable pairs efficiently.
pub fn part1(input: &[Node]) -> usize {
    let mut used: Vec<_> = input.iter().map(|n| n.used).filter(|&n| n > 0).collect();
    used.sort_unstable();

    let mut avail: Vec<_> = input.iter().map(|n| n.avail).collect();
    avail.sort_unstable();

    let mut i = 0;
    let mut viable = 0;

    for next in used {
        while i < avail.len() && avail[i] < next {
            i += 1;
        }
        viable += avail.len() - i;
    }

    viable
}

pub fn part2(input: &[Node]) -> u32 {
    let mut width = 0;
    let mut empty_x = 0;
    let mut empty_y = 0;
    let mut wall_x = u32::MAX;

    for &Node { x, y, used, .. } in input {
        width = width.max(x + 1);

        if used == 0 {
            empty_x = x;
            empty_y = y;
        }

        // Large nodes are bigger than 100T.
        if used >= 100 {
            wall_x = wall_x.min(x - 1);
        }
    }

    // Move left to avoid wall.
    let a = empty_x - wall_x;
    // Move up to first row.
    let b = empty_y;
    // Move right to spot in front of data.
    let c = width - 2 - wall_x;
    // Move data into empty spot.
    let d = 1;
    // Repeatedly move empty spot 4 places around from behind data then move data one spot left.
    let e = 5 * (width - 2);

    a + b + c + d + e
}