comparison 2017/day06/problem @ 34:049fb8e56025

Add problem statements and inputs
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 09 Jan 2018 21:51:44 -0500
parents
children
comparison
equal deleted inserted replaced
33:bc652fa0a645 34:049fb8e56025
1 --- Day 6: Memory Reallocation ---
2
3 A debugger program here is having an issue: it is trying to repair a
4 memory reallocation routine, but it keeps getting stuck in an infinite
5 loop.
6
7 In this area, there are sixteen memory banks; each memory bank can
8 hold any number of blocks. The goal of the reallocation routine is to
9 balance the blocks between the memory banks.
10
11 The reallocation routine operates in cycles. In each cycle, it finds
12 the memory bank with the most blocks (ties won by the lowest-numbered
13 memory bank) and redistributes those blocks among the banks. To do
14 this, it removes all of the blocks from the selected bank, then moves
15 to the next (by index) memory bank and inserts one of the blocks. It
16 continues doing this until it runs out of blocks; if it reaches the
17 last memory bank, it wraps around to the first one.
18
19 The debugger would like to know how many redistributions can be done
20 before a blocks-in-banks configuration is produced that has been seen
21 before.
22
23 For example, imagine a scenario with only four memory banks:
24
25 The banks start with 0, 2, 7, and 0 blocks. The third bank has the
26 most blocks, so it is chosen for redistribution.
27
28 Starting with the next bank (the fourth bank) and then continuing
29 to the first bank, the second bank, and so on, the 7 blocks are
30 spread out over the memory banks. The fourth, first, and second
31 banks get two blocks each, and the third bank gets one back. The
32 final result looks like this: 2 4 1 2.
33
34 Next, the second bank is chosen because it contains the most
35 blocks (four). Because there are four memory banks, each gets one
36 block. The result is: 3 1 2 3.
37
38 Now, there is a tie between the first and fourth memory banks,
39 both of which have three blocks. The first bank wins the tie, and
40 its three blocks are distributed evenly over the other three
41 banks, leaving it with none: 0 2 3 4.
42
43 The fourth bank is chosen, and its four blocks are distributed
44 such that each of the four banks receives one: 1 3 4 1.
45
46 The third bank is chosen, and the same thing happens: 2 4 1 2.
47
48 At this point, we've reached a state we've seen before: 2 4 1 2 was
49 already seen. The infinite loop is detected after the fifth block
50 redistribution cycle, and so the answer in this example is 5.
51
52 Given the initial block counts in your puzzle input, how many
53 redistribution cycles must be completed before a configuration is
54 produced that has been seen before?
55
56 Your puzzle answer was 5042.
57
58 --- Part Two ---
59
60 Out of curiosity, the debugger would also like to know the size of the
61 loop: starting from a state that has already been seen, how many block
62 redistribution cycles must be performed before that same state is seen
63 again?
64
65 In the example above, 2 4 1 2 is seen again after four cycles, and so
66 the answer in that example would be 4.
67
68 How many cycles are in the infinite loop that arises from the
69 configuration in your puzzle input?
70
71 Your puzzle answer was 1086.
72
73 Both parts of this puzzle are complete! They provide two gold stars: **