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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

//! # [Day 6: Memory Reallocation](http://adventofcode.com/2017/day/6)
//!
//! A debugger program here is having an issue: it is trying to repair a
//! memory reallocation routine, but it keeps getting stuck in an infinite
//! loop.

/// In this area, there are <span title="There are also five currency banks,
/// two river banks, three airplanes banking, a banked billards shot, and a
/// left bank.">sixteen memory banks</span>; each memory bank can hold any
/// number of *blocks*. The goal of the reallocation routine is to balance the
/// blocks between the memory banks.
pub fn parse_input(input: &str) -> Vec<usize> {
    input[..input.len() - 1]
        .split('\t')
        .map(|x| x.parse::<usize>().expect("Unexpected non-integer number of block"))
        .collect::<Vec<_>>()
}

/// The reallocation routine operates in cycles. In each cycle, it finds the
/// memory bank with the most blocks (ties won by the lowest-numbered memory
/// bank) and redistributes those blocks among the banks. To do this, it
/// removes all of the blocks from the selected bank, then moves to the next
/// (by index) memory bank and inserts one of the blocks. It continues doing
/// this until it runs out of blocks; if it reaches the last memory bank, it
/// wraps around to the first one.
///
/// The debugger would like to know how many redistributions can be done
/// before a blocks-in-banks configuration is produced that *has been seen
/// before*.
///
/// For example, imagine a scenario with only four memory banks:
///
/// -   The banks start with `0`, `2`, `7`, and `0` blocks. The third bank
///     has the most blocks, so it is chosen for redistribution.
/// -   Starting with the next bank (the fourth bank) and then continuing to
///     the first bank, the second bank, and so on, the `7` blocks are
///     spread out over the memory banks. The fourth, first, and second
///     banks get two blocks each, and the third bank gets one back. The
///     final result looks like this: `2 4 1 2`.
/// -   Next, the second bank is chosen because it contains the most blocks
///     (four). Because there are four memory banks, each gets one block.
///     The result is: `3 1 2 3`.
/// -   Now, there is a tie between the first and fourth memory banks, both
///     of which have three blocks. The first bank wins the tie, and its
///     three blocks are distributed evenly over the other three banks,
///     leaving it with none: `0 2 3 4`.
/// -   The fourth bank is chosen, and its four blocks are distributed such
///     that each of the four banks receives one: `1 3 4 1`.
/// -   The third bank is chosen, and the same thing happens: `2 4 1 2`.
///
/// At this point, we've reached a state we've seen before: `2 4 1 2` was
/// already seen. The infinite loop is detected after the fifth block
/// redistribution cycle, and so the answer in this example is `5`.
///
/// ```
/// # use advent_solutions::advent2017::day06::{ parse_input, part1 };
/// # let input = parse_input("0\t2\t7\t0\n");
/// assert_eq!(part1(&input), 5);
/// ```
///
/// Given the initial block counts in your puzzle input, *how many
/// redistribution cycles* must be completed before a configuration is
/// produced that has been seen before?
pub fn part1(banks: &Vec<usize>) -> usize {
    use std::collections::HashSet;

    let mut banks = banks.clone();
    let mut cache = HashSet::new();
    let mut steps = 0;

    loop {
        if !cache.insert(banks.clone()) {
            break;
        }

        let (idx, &blocks) = {
            let (_, max) = banks.iter().enumerate()
                .max_by_key(|&(_, blocks)| blocks)
                .unwrap();

            banks.iter().enumerate()
                .find(|&(_, blocks)| blocks == max)
                .unwrap()
        };

        banks[idx] = 0;

        for i in 1..blocks + 1 {
            let len = banks.len();
            banks[(idx + i) % len] += 1;
        }

        steps += 1;
    }

    steps
}


/// Out of curiosity, the debugger would also like to know the size of the
/// loop: starting from a state that has already been seen, how many block
/// redistribution cycles must be performed before that same state is seen
/// again?
///
/// In the example above, `2 4 1 2` is seen again after four cycles, and so
/// the answer in that example would be `4`.
///
/// ```
/// # use advent_solutions::advent2017::day06::{ parse_input, part2 };
/// # let input = parse_input("0\t2\t7\t0\n");
/// assert_eq!(part2(&input), 4);
/// ```
///
/// *How many cycles* are in the infinite loop that arises from the
/// configuration in your puzzle input?
pub fn part2(banks: &Vec<usize>) -> usize {
    use std::collections::HashMap;

    let mut banks = banks.clone();
    let mut cache = HashMap::new();
    let mut steps = 0usize;

    loop {
        if let Some(initial_steps) = cache.get(&banks) {
            return steps - initial_steps
        }

        cache.insert(banks.clone(), steps);

        let (idx, &blocks) = {
            let (_, max) = banks.iter().enumerate()
                .max_by_key(|&(_, blocks)| blocks)
                .unwrap();

            banks.iter().enumerate()
                .find(|&(_, blocks)| blocks == max)
                .unwrap()
        };

        banks[idx] = 0;

        for i in 1..blocks + 1 {
            let len = banks.len();
            banks[(idx + i) % len] += 1;
        }

        steps += 1;
    }
}

test_day!("06", 11137, 1037);