aoc/year2017/
day06.rs

1//! # Memory Reallocation
2//!
3//! Looking at the input and the reallocation rules, we make an assertion:
4//!
5//! * No memory bank will ever exceed 15 blocks.
6//!
7//! This has a nice effect that we can store the entire memory layout packed into a single
8//! `u64` with each memory bank represented by a nibble.
9//!
10//! This makes it very fast to find the highest nibble using bitwise logic. To detect the cycle
11//! a [`FastMap`] stores each previously seen memory layout along with the cycle that it first
12//! appeared.
13use crate::util::hash::*;
14use crate::util::parse::*;
15
16type Input = (u32, u32);
17
18/// Reallocate a bank and set to zero by rotating this mask the correct number of bits.
19const REMOVE: usize = 0x0fffffffffffffff;
20/// The highest number of banks possible is 15, so each bank will add at most 1 to each of
21/// the banks that come after it.
22const SPREAD: [usize; 16] = [
23    0x0000000000000000,
24    0x0100000000000000,
25    0x0110000000000000,
26    0x0111000000000000,
27    0x0111100000000000,
28    0x0111110000000000,
29    0x0111111000000000,
30    0x0111111100000000,
31    0x0111111110000000,
32    0x0111111111000000,
33    0x0111111111100000,
34    0x0111111111110000,
35    0x0111111111111000,
36    0x0111111111111100,
37    0x0111111111111110,
38    0x0111111111111111,
39];
40
41pub fn parse(input: &str) -> Input {
42    // Accumulate the input into a single `u64`.
43    let mut memory: usize = input.iter_unsigned::<usize>().fold(0, |acc, n| (acc << 4) + n);
44    // Store previously seen configurations for cycle detection.
45    let mut seen = FastMap::with_capacity(20_000);
46    let mut cycles = 0;
47
48    seen.insert(memory, cycles);
49
50    loop {
51        // Find the highest nibble in the integer.
52        // We check each of the 4 bits for all nibbles in descending order by bitwise ANDing with
53        // the mask.
54        // If the mask is zero, then this implies that no nibbles have that bit set so we leave
55        // the mask unchanged.
56        // If some nibbles have that bit set, then we will "narrow" the mask to only consider
57        // those nibbles.
58        let mut mask = 0x8888888888888888;
59
60        let first = memory & mask;
61        mask = if first == 0 { mask } else { first };
62
63        let second = (memory << 1) & mask;
64        mask = if second == 0 { mask } else { second };
65
66        let third = (memory << 2) & mask;
67        mask = if third == 0 { mask } else { third };
68
69        let fourth = (memory << 3) & mask;
70        mask = if fourth == 0 { mask } else { fourth };
71
72        // The mask will have a 1 bit set for each of the joint highest values.
73        // Choose the lowest index which is the most significant bit set.
74        let offset = mask.leading_zeros();
75        let max = memory.rotate_left(offset + 4) & 0xf;
76
77        // Empty the largest memory bank and reallocate its contents to the following banks.
78        memory = (memory & REMOVE.rotate_right(offset)) + SPREAD[max].rotate_right(offset);
79        cycles += 1;
80
81        // Check if we've seen this configuration before
82        if let Some(previous) = seen.insert(memory, cycles) {
83            break (cycles, cycles - previous);
84        }
85    }
86}
87
88pub fn part1(input: &Input) -> u32 {
89    input.0
90}
91
92pub fn part2(input: &Input) -> u32 {
93    input.1
94}
aoc/year2017/day06.rs

aoc/year2017/
day06.rs
