AoC2020 Days 13 to 16

2020-12-16

Here we are in lockdown again. Luckily the advent of code does brighten the day somewhat. And some challenges were noticeably harder this week (though still not remotely as hard as last year I must say). It started with day 13: the given input was a list of buses (whose names correspond to their periodicities), and find out a time t from which each bus arrives at t+n where n is their place in the list. As someone pointed out on reddit, this problem is known as the Chinese Remainder Problem. Though one (like me) didn't need to know that to solve it thankfully. Brute-focing it (by trying all integers until we find one) was clearly not the best idea (as you will see with the solution) so one had to find a way to solve it faster. And the solution ended up fairly trivial: finding an integer i at which the first bus arrive, and then incrementing only by the periodicity of that bus until we end up on a time at which the second one arrive, then incrementing by the product of both, etc.
``````options(digits=22)
bus <- as.integer(el(strsplit(input,",")))
spot <- which(!is.na(bus))-1 # -1 one as R vectors are 1-based but we need 0-based spots
bus <- bus[!is.na(bus)]
t <-0
pace <- 1
for(i in seq_along(bus)){
while((t+spot[i])%%bus[i]) t <- t+pace
pace <- pace*bus[i]
}
t
#471793476184394``````

Note that `options(digits=22)` again that I end up using on every odd challenge those days. Day 14 was again fairly difficult. The first part required reading a series of integers, transforming to a 36 bit length binary number, then using masks to force some positions into 1s or 0s, reconverting it to a base-10 integer and placing it in a specific place in "memory" (i. e. a master vector). Easy enough, but the second part required that operation to be done on the memory index rather than the value, and the mask rule changes to forcing 1s and Xs with Xs being both 1 and 0 (i. e. sending the value to several place in the master vector). As those numbers are fairly high it prohibits actually using a proper vector: the maximum length of a vector in R is 2^31 while here we can have indices as high as 2^35.

``````options(digits=22) #If it wasn't for reproducibility sake I would put it in my Rprofile at that point
mem <- c()
intTo36Bits <- function(x){ #Homemade binary transformation
res <- c()
for(i in 35:0){
res <- c(res,x%/%(2^i))
x <- x%%(2^i)
}
res
}

bitsToInt<- function(x)sum(x*2^(35:0)) #And the reverse

for(i in seq_along(input)){
}else{
dig <- as.integer(el(regmatches(input[i],gregexpr("\\d+",input[i])))) #Parsing the input
index <- dig
value <- dig
b <- as.matrix(intTo36Bits(index))
for(k in w1) b[k,]<-1
for(k in wx){ #Duplicate the binary number and make one side 0s and the other 1s
b <- cbind(b,b)
b[k,] <- c(rep(0,ncol(b)/2),rep(1,ncol(b)/2)) #Put 0s in half of them and 1s in the other half
}
#Instead of a mostly-empty vector, a key-value matrix:
mem <- rbind(mem,cbind(apply(b,2,bitsToInt),value))
#We "overwrite" values by getting rid of older duplicates
mem <- mem[!duplicated(mem[,1],fromLast=TRUE),]
}
}
sum(mem[,2])
#3705162613854``````

Funnily, day 15 required to do an opposite trick. We have a sequence of number where the u(n+1) is 0 if u(n) appears for the first time in the list or its age if it appeared before (i. e. n-m where m was the previous time it appeared). The standard one starting with 0, 0 is referred to as the Van Eck's sequence, but here we each got a unique starter. The problem was to figure out which will be the 30 000 000nth integer in that sequence. Actually creating a sequence that long would take forever (increasing a vector's length in R is time consuming). What I ended up doing though was having a 30 000 000-long vector of "ages", that I updated each iteration with the most recent age for a given integer (given by the index), as looking up into a vector by its index is almost costless timewise, whereas checking the full stack of values for a condition is time-consuming.

``````input <- c(13,16,0,12,15,1)
last <- 0
current <- 7
maxn <- 30000000
age <- rep(NA,maxn)
age[1+input]<-seq_along(input) #The additional 1 is because we need a space for O
while(current<=maxn){
x <- age[1+last]
age[1+last] <- current
if(is.na(x)){
last <- 0
}else{
last <- current-x
}
current <- current + 1
}
which(age%in%maxn)-1
#2424``````

Day 16 finally was way simpler and thus not really worth explaining here (all operations involved were trivial in R: checking whether numbers belongs to a list, checking which row only has a single TRUE value, etc.), but you can always check it out on my repository.