Mercurial > hg > aoc
annotate 2017/day06/problem @ 35:1d99d733cf13 default tip @
day08: replace static foreach with workaround
author  Jordi Gutiérrez Hermoso <jordigh@octave.org> 

date  Tue, 16 Jan 2018 11:28:55 0500 
parents  049fb8e56025 
children 
rev  line source 

34
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

1  Day 6: Memory Reallocation  
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

2 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

3 A debugger program here is having an issue: it is trying to repair a 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

4 memory reallocation routine, but it keeps getting stuck in an infinite 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

5 loop. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

6 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

7 In this area, there are sixteen memory banks; each memory bank can 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

8 hold any number of blocks. The goal of the reallocation routine is to 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

9 balance the blocks between the memory banks. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

10 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

11 The reallocation routine operates in cycles. In each cycle, it finds 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

12 the memory bank with the most blocks (ties won by the lowestnumbered 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

13 memory bank) and redistributes those blocks among the banks. To do 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

14 this, it removes all of the blocks from the selected bank, then moves 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

15 to the next (by index) memory bank and inserts one of the blocks. It 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

16 continues doing this until it runs out of blocks; if it reaches the 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

17 last memory bank, it wraps around to the first one. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

18 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

19 The debugger would like to know how many redistributions can be done 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

20 before a blocksinbanks configuration is produced that has been seen 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

21 before. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

22 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

23 For example, imagine a scenario with only four memory banks: 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

24 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

25 The banks start with 0, 2, 7, and 0 blocks. The third bank has the 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

26 most blocks, so it is chosen for redistribution. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

27 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

28 Starting with the next bank (the fourth bank) and then continuing 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

29 to the first bank, the second bank, and so on, the 7 blocks are 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

30 spread out over the memory banks. The fourth, first, and second 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

31 banks get two blocks each, and the third bank gets one back. The 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

32 final result looks like this: 2 4 1 2. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

33 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

34 Next, the second bank is chosen because it contains the most 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

35 blocks (four). Because there are four memory banks, each gets one 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

36 block. The result is: 3 1 2 3. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

37 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

38 Now, there is a tie between the first and fourth memory banks, 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

39 both of which have three blocks. The first bank wins the tie, and 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

40 its three blocks are distributed evenly over the other three 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

41 banks, leaving it with none: 0 2 3 4. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

42 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

43 The fourth bank is chosen, and its four blocks are distributed 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

44 such that each of the four banks receives one: 1 3 4 1. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

45 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

46 The third bank is chosen, and the same thing happens: 2 4 1 2. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

47 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

48 At this point, we've reached a state we've seen before: 2 4 1 2 was 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

49 already seen. The infinite loop is detected after the fifth block 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

50 redistribution cycle, and so the answer in this example is 5. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

51 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

52 Given the initial block counts in your puzzle input, how many 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

53 redistribution cycles must be completed before a configuration is 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

54 produced that has been seen before? 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

55 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

56 Your puzzle answer was 5042. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

57 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

58  Part Two  
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

59 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

60 Out of curiosity, the debugger would also like to know the size of the 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

61 loop: starting from a state that has already been seen, how many block 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

62 redistribution cycles must be performed before that same state is seen 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

63 again? 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

64 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

65 In the example above, 2 4 1 2 is seen again after four cycles, and so 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

66 the answer in that example would be 4. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

67 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

68 How many cycles are in the infinite loop that arises from the 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

69 configuration in your puzzle input? 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

70 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

71 Your puzzle answer was 1086. 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

72 
049fb8e56025
Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff
changeset

73 Both parts of this puzzle are complete! They provide two gold stars: ** 