Mercurial > hg > aoc
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: ** |