Day 6 Memory Reallocation
In Day 6, Memory Reallocation, the “richest” memory bank (the one with the most blocks) gets its blocks redistributed among the other memory banks.
6.1 Part I
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.
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?We can take the key facts given in the puzzle description, and translate them to code.
- The first bank with the maximum number of blocks is selected:
position <- which(input == max(input))[1] - All blocks are distributed one-by-one, starting with the next bank:
input[position + 1] <- input[position + 1] + 1,input[position + 2] <- input[position + 2] + 1, etc. - Once we get to the end of the line, we loop back to the beginning and continue distributing blocks until there are none left:
if(position > length(input)) {position <- position - length(input)} - The process repeats until history repeats itself:
any(duplicated(history)) == TRUEwherehistoryis a vector of all inputs up to that point
If we put it all together, we get the following:
input <- c(0, 2, 7, 0)
history <- paste(input, collapse = "")
while(any(duplicated(history)) == FALSE){
max_blocks <- max(input)
position <- which(input == max_blocks)[1] #position of 1st bank with max blocks
input[position] <- 0 #take away all blocks to redistribute
for(i in 1:max_blocks){ #redistribute blocks
position <- position + 1
#deal with looping...
if(position > length(input)){
position <- position - length(input)
}
input[position] <- input[position] + 1
}
print(input) #just so we can check
history <- c(history, paste(input, collapse = "")) #add input as string
}## [1] 2 4 1 2
## [1] 3 1 2 3
## [1] 0 2 3 4
## [1] 1 3 4 1
## [1] 2 4 1 2## [1] 5It works on the sample input. The real puzzle input just takes a little formatting and it’s also good to go:
library(tidyverse)
"14 0 15 12 11 11 3 5 1 6 8 4 9 1 8 4" %>%
str_split("\t") %>%
unlist() %>%
as.integer()## [1] 14 0 15 12 11 11 3 5 1 6 8 4 9 1 8 46.2 Part II
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.
How many cycles are in the infinite loop that arises from the configuration in your puzzle input?Since we saved our history, this part becomes pretty straightforward. We need to determine the positions of the “twin” sequences that stopped the looping process. We know one twin is the last sequence in history and that the other twin matches it. So:
## [1] 4