aoc/year2017/
day06.rs

1//! # Memory Reallocation
2//!
3//! Looking at the input and the reallocation rules, when there is at most one bank with
4//! 15 blocks, it is easy to see that no other bank will exceed 15 after reallocation.
5//! However, some input files have early scenarios where there are a couple of banks with
6//! 15, which can result in the next round or two needing to process 16 or even 17 blocks.
7//! The overflow issue only occurs early; in the long run, the banks settle into a pattern
8//! where overflow does not interfere.
9//!
10//! With that in mind, it is possible to design a compact layout that stores each bank in
11//! one nibble of a u64 in the common case, but with manual iterations managing the overflow
12//! as needed.
13//!
14//! For all but the few manual overflow cases, it is very fast to find the highest nibble
15//! using bitwise logic. To detect the cycle a [`FastMap`] stores each previously seen
16//! memory layout along with the cycle that it first appeared.
17use crate::util::hash::*;
18use crate::util::parse::*;
19
20type Input = (u32, u32);
21
22/// Reallocate a bank and set to zero by rotating this mask the correct number of bits.
23const REMOVE: u64 = 0x0fffffffffffffff;
24/// The highest number of banks when overflow is not a concern is 15, so each bank will
25/// add at most 1 to each of the banks that come after it.
26const SPREAD: [u64; 16] = [
27    0x0000000000000000,
28    0x0100000000000000,
29    0x0110000000000000,
30    0x0111000000000000,
31    0x0111100000000000,
32    0x0111110000000000,
33    0x0111111000000000,
34    0x0111111100000000,
35    0x0111111110000000,
36    0x0111111111000000,
37    0x0111111111100000,
38    0x0111111111110000,
39    0x0111111111111000,
40    0x0111111111111100,
41    0x0111111111111110,
42    0x0111111111111111,
43];
44
45pub fn parse(input: &str) -> Input {
46    // Accumulate the input into a single `u64`.
47    let mut memory: u64 = input.iter_unsigned::<u64>().fold(0, |acc, n| (acc << 4) + n);
48    // Store previously seen configurations for cycle detection.
49    let mut seen = FastMap::with_capacity(20_000);
50    let mut cycles = 0;
51
52    loop {
53        // Find the highest nibble in the integer.
54        // We check each of the 4 bits for all nibbles in descending order by bitwise ANDing with
55        // the mask.
56        // If the mask is zero, then this implies that no nibbles have that bit set so we leave
57        // the mask unchanged.
58        // If some nibbles have that bit set, then we will "narrow" the mask to only consider
59        // those nibbles.
60        let mask = (0..4).fold(0x8888888888888888, |mask, shift| {
61            let result = (memory << shift) & mask;
62            if result == 0 { mask } else { result }
63        });
64
65        // The mask will have a 1 bit set for each of the joint highest values.
66        // Choose the lowest index which is the most significant bit set.
67        let offset = mask.leading_zeros();
68        let max = (memory.rotate_left(offset + 4) & 0xf) as usize;
69
70        // Common case: no overflow
71        if max < 15 || mask.count_ones() == 1 {
72            // Empty the largest memory bank and reallocate its contents to the following banks.
73            memory = (memory & REMOVE.rotate_right(offset)) + SPREAD[max].rotate_right(offset);
74            cycles += 1;
75
76            // Check if we've seen this configuration before
77            if let Some(previous) = seen.insert(memory, cycles) {
78                break (cycles, cycles - previous);
79            }
80        } else {
81            // Overflow case.  This can happen in the early steps of the system, but resolves
82            // fairly quickly - in practice, the worst known input file had a total of 10 overflow
83            // cycles, with at most two adjacent overflows per encounter, with all overflows
84            // before cycle 200, well before the first repeated configuration.  Thus, it is
85            // okay to not cache these states in seen.
86            let mut array = [0; 16];
87
88            for i in (0..16).rev() {
89                array[i] = memory & 0xf;
90                memory >>= 4;
91            }
92
93            while array.iter().any(|&n| n >= 15) {
94                let max = *array.iter().max().unwrap();
95                let first = array.iter().position(|&n| n == max).unwrap();
96
97                array[first] = 0;
98                (0..max as usize).for_each(|i| array[(first + i + 1) % 16] += 1);
99
100                cycles += 1;
101            }
102
103            memory = array.iter().fold(0, |acc, n| (acc << 4) | n);
104        }
105    }
106}
107
108pub fn part1(input: &Input) -> u32 {
109    input.0
110}
111
112pub fn part2(input: &Input) -> u32 {
113    input.1
114}
aoc/year2017/day06.rs

aoc/year2017/
day06.rs
