In [3]:
You arrive at Easter Bunny Headquarters under cover of darkness. However, you left in such a rush that you forgot to use the bathroom! Fancy office buildings like this one usually have keypad locks on their bathrooms, so you search the front desk for the code.
"In order to improve security," the document you find says, "bathroom codes will no longer be written down. Instead, please memorize and follow the procedure below to access the bathrooms."
The document goes on to explain that each button to be pressed can be found by starting on the previous button and moving to adjacent buttons on the keypad: U moves up, D moves down, L moves left, and R moves right. Each line of instructions corresponds to one button, starting at the previous button (or, for the first line, the "5" button); press whatever button you're on at the end of each line. If a move doesn't lead to a button, ignore it.
You can't hold it much longer, so you decide to figure out the code as you walk to the bathroom. You picture a keypad like this:
1 2 3 4 5 6 7 8 9
Suppose your instructions are:
ULL RRDDD LURDL UUUUD
You start at "5" and move up (to "2"), left (to "1"), and left (you can't, and stay on "1"), so the first button is 1.
Starting from the previous button ("1"), you move right twice (to "3") and then down three times (stopping at "9" after two moves and ignoring the third), ending up with 9.
Continuing from "9", you move left, up, right, down, and left, ending with 8.
Finally, you move up four times (stopping at "2"), then down once, ending with 5.
So, in this example, the bathroom code is 1985.
Your puzzle input is the instructions from the document you found at the front desk. What is the bathroom code?
Your puzzle answer was 78293. --- Part Two ---
You finally arrive at the bathroom (it's a several minute walk from the lobby so visitors can behold the many fancy conference rooms and water coolers on this floor) and go to punch in the code. Much to your bladder's dismay, the keypad is not at all like you imagined it. Instead, you are confronted with the result of hundreds of man-hours of bathroom-keypad-design meetings:
1
2 3 4 5 6 7 8 9 A B C D
You still start at "5" and stop when you're at an edge, but given the same instructions as above, the outcome is very different:
You start at "5" and don't move at all (up and left are both edges), ending at 5.
Continuing from "5", you move right twice and down three times (through "6", "7", "B", "D", "D"), ending at D.
Then, from "D", you move five more times (through "D", "B", "C", "C", "B"), ending at B.
Finally, after five more moves, you end at 3.
So, given the actual keypad layout, the code would be 5DB3.
Using the same instructions in your puzzle input, what is the correct bathroom code?
Your puzzle answer was AC8C8.
In [1]:
library(foreach)
data <- readLines("day2a")
data
pad <- matrix(c(1:9), ncol =3, byrow=T)
pad
curX <-2
curY <-2
result <- numeric()
a <- foreach(x=data) %do% {
b <- foreach(y=strsplit(x, "")[[1]]) %do% {
switch(y,
D = {curX <- curX + 1},
L = {curY <- curY - 1},
U = {curX <- curX - 1},
R = {curY <- curY + 1}
)
curX <- max(1,curX)
curX <- min(3,curX)
curY <- max(1,curY)
curY <- min(3,curY)
}
result <- c(result,pad[curX,curY])
}
pad2 <- matrix(c(NA), ncol =7, nrow =7, byrow=T) # Made an oversize table to see when I am out based on value not index
pad2[2,4] <- 1
pad2[3,3:5] <- c(2:4)
pad2[4,2:6] <- c(5:9)
pad2[5,3:5] <- c('A','B','C')
pad2[6,4] <- 'D'
pad2
In [2]:
canMove <- function(x,y) !is.na(pad2[x,y]) #Quick function to verify if we are out of the table
curX <-2
curY <-4
result2 <- numeric()
a <- foreach(x=data) %do% {
b <- foreach(y=strsplit(x, "")[[1]]) %do% {
switch(y,
D = {curX <- if (canMove(curX + 1,curY)) curX + 1 else curX},
L = {curY <- if (canMove(curX,curY - 1)) curY - 1 else curY},
U = {curX <- if (canMove(curX - 1,curY)) curX - 1 else curX},
R = {curY <- if (canMove(curX,curY + 1)) curY + 1 else curY}
)
}
result2 <- c(result2,pad2[curX,curY])
}
In [3]:
cat("Q1 -- The passcode for the door is: ", paste(result,collapse=""),'\n')
cat("Q2 -- The passcode for the funny lock is: ", paste(result2,collapse=""),'\n')
--- Day 3: Squares With Three Sides ---
Now that you can think clearly, you move deeper into the labyrinth of hallways and office furniture that makes up this part of Easter Bunny HQ. This must be a graphic design department; the walls are covered in specifications for triangles.
Or are they?
The design document gives the side lengths of each triangle it describes, but... 5 10 25? Some of these aren't triangles. You can't help but mark the impossible ones.
In a valid triangle, the sum of any two sides must be larger than the remaining side. For example, the "triangle" given above is impossible, because 5 + 10 is not larger than 25.
In your puzzle input, how many of the listed triangles are possible?
--- Part Two ---
Now that you've helpfully marked up their design documents, it occurs to you that triangles are specified in groups of three vertically. Each set of three numbers in a column specifies a triangle. Rows are unrelated.
For example, given the following specification, numbers with the same hundreds digit would be part of the same triangle:
101 301 501 102 302 502 103 303 503 201 401 601 202 402 602 203 403 603
In your puzzle input, and instead reading by columns, how many of the listed triangles are possible?
In [4]:
data <- read.table("day3a") #Using dataframe to align data
str(data)
data$possible <- apply(data, 1, function(x) {t <- sort(x); (t[1]+t[2]) > t[3]}) #Creating new column with the possible value
data2 <- data.frame(do.call(rbind, lapply(data[,1:3], matrix, ncol = 3, byrow=T)))
str(data2)
data2$possible <- apply(data2, 1, function(x) {t <- sort(x); (t[1]+t[2]) > t[3]})
cat("Q1 - The number of possible triangles by row is: ", sum(data$possible), '\n')
cat("Q2 - The number of possible triangles by column is: ", sum(data2$possible), '\n')
--- Day 4: Security Through Obscurity ---
Finally, you come across an information kiosk with a list of rooms. Of course, the list is encrypted and full of decoy data, but the instructions to decode the list are barely hidden nearby. Better remove the decoy data first.
Each room consists of an encrypted name (lowercase letters separated by dashes) followed by a dash, a sector ID, and a checksum in square brackets.
A room is real (not a decoy) if the checksum is the five most common letters in the encrypted name, in order, with ties broken by alphabetization. For example:
aaaaa-bbb-z-y-x-123[abxyz] is a real room because the most common letters are a (5), b (3), and then a tie between x, y, and z, which are listed alphabetically.
a-b-c-d-e-f-g-h-987[abcde] is a real room because although the letters are all tied (1 of each), the first five are listed alphabetically.
not-a-real-room-404[oarel] is a real room.
totally-real-room-200[decoy] is not.
Of the real rooms from the list above, the sum of their sector IDs is 1514.
What is the sum of the sector IDs of the real rooms?
Your puzzle answer was 173787.
The first half of this puzzle is complete! It provides one gold star: * --- Part Two ---
With all the decoy data out of the way, it's time to decrypt this list and get moving.
The room names are encrypted by a state-of-the-art shift cipher, which is nearly unbreakable without the right software. However, the information kiosk designers at Easter Bunny HQ were not expecting to deal with a master cryptographer like yourself.
To decrypt a room name, rotate each letter forward through the alphabet a number of times equal to the room's sector ID. A becomes B, B becomes C, Z becomes A, and so on. Dashes become spaces.
For example, the real name for qzmt-zixmtkozy-ivhz-343 is very encrypted name.
What is the sector ID of the room where North Pole objects are stored?
In [7]:
library(foreach)
library(stringr)
data <- readLines("day4a")
str(data)
ttt <- str_match(data,"(.*)\\-+(\\d+)\\[(.*)\\]")
head(ttt)
parsedData <- gsub("(.*)\\-+(\\d+)\\[(.*)\\]", '\\1:\\2:\\3', data, perl = TRUE)
parsedData <- strsplit(parsedData, ':')
head(parsedData)
dataf <- as.data.frame(matrix(unlist(parsedData), ncol = 3, byrow=T))
colnames(dataf)<- c("code","value","checksum")
head(dataf)
# Simple parsing in int of the value column
dataf$value <- strtoi(dataf$value, base = 0L)
dataf$Valid <- apply(dataf, 1, function(x) {
a<-(sort(table(strsplit(gsub("-","",x[1]),"")), decreasing = TRUE)[1:5])
paste(attributes(a)$dimnames[[1]], collapse = '') == x[3]
})
english.letters <- c('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
'w', 'x', 'y', 'z')
caesar.cipher <- list()
for (index in 1:length(english.letters))
{
caesar.cipher[[english.letters[index]]] <- english.letters[index %% 26 + 1]
}
caesar.cipher[['-']] <- '-'
apply.cipher.to.string <- function(string, cipher)
{
output <- ''
for (i in 1:nchar(string))
{
output <- paste(output, cipher[[substr(string, i, i)]], sep = '')
}
return(output)
}
tmp <- "northpole-object-storage"
possible <- foreach(x=1:26) %do% {
tmp <- apply.cipher.to.string(tmp, caesar.cipher)
#intersect(strsplit(tmp,'-')[[1]], words)
#if( intersect(strsplit(tmp,'-')[[1]], words) != "")
# strsplit(tmp,'-')[[1]][1]
}
dataf$value[dataf$code==intersect(possible,dataf$code)]
paste("Q1 -- Number of good room is ", sum(dataf$value[dataf$Valid]))
paste("Q2 -- Value of the north pole storage room is ", dataf$value[dataf$code==intersect(possible,dataf$code)])
--- Day 10: Balance Bots ---
You come upon a factory in which many robots are zooming around handing small microchips to each other.
Upon closer examination, you notice that each bot only proceeds when it has two microchips, and once it does, it gives each one to a different bot or puts it in a marked "output" bin. Sometimes, bots take microchips from "input" bins, too.
Inspecting one of the microchips, it seems like they each contain a single number; the bots must use some logic to decide what to do with each chip. You access the local control computer and download the bots' instructions (your puzzle input).
Some of the instructions specify that a specific-valued microchip should be given to a specific bot; the rest of the instructions indicate what a given bot should do with its lower-value or higher-value chip.
For example, consider the following instructions:
value 5 goes to bot 2 bot 2 gives low to bot 1 and high to bot 0 value 3 goes to bot 1 bot 1 gives low to output 1 and high to bot 0 bot 0 gives low to output 2 and high to output 0 value 2 goes to bot 2
Initially, bot 1 starts with a value-3 chip, and bot 2 starts with a value-2 chip and a value-5 chip.
Because bot 2 has two microchips, it gives its lower one (2) to bot 1 and its higher one (5) to bot 0.
Then, bot 1 has two microchips; it puts the value-2 chip in output 1 and gives the value-3 chip to bot 0.
Finally, bot 0 has two microchips; it puts the 3 in output 2 and the 5 in output 0.
In the end, output bin 0 contains a value-5 microchip, output bin 1 contains a value-2 microchip, and output bin 2 contains a value-3 microchip. In this configuration, bot number 2 is responsible for comparing value-5 microchips with value-2 microchips.
Based on your instructions, what is the number of the bot that is responsible for comparing value-61 microchips with value-17 microchips?
--- Part Two ---
What do you get if you multiply together the values of one chip in each of outputs 0, 1, and 2?
In [5]:
library(stringr)
data <- readLines("day10.txt")
robotDB <- data.frame(id = integer(0), Low= integer(0), High = integer(0))
robotDB[1, ] <- c(-1,-1,-1)
output <- data.frame(id = integer(0), value= integer(0))
output[1, ] <- c(-1,-1)
addToRobot <- function(robot,value) {
rr <- robotDB[robotDB$id==robot,]
if(nrow(rr)==0){#do not exist
robotDB <<- rbind(robotDB, c(id=robot, Low=value, High=-1))
}
else{
low <- rr$Low
if(as.integer(low)<=as.integer(value)){
robotDB[robotDB$id==robot,3] <<- value
}
else{
robotDB[robotDB$id==robot,3] <<- low
robotDB[robotDB$id==robot,2] <<- value
}
handleFull(robot)
}
}
handleFull <- function(robot) {
if(toString(assign[which(assign$robot == robot), 4]) == "bot"){
addToRobot(toString(assign[which(assign$robot == robot), 5]),robotDB[robotDB$id==robot,3])#high
}
else {
output <<- rbind(output, c(id=toString(assign[which(assign$robot == robot), 5]), Low=robotDB[robotDB$id==robot,3]))
}
if(toString(assign[which(assign$robot == robot), 2]) == "bot"){
addToRobot(toString(assign[which(assign$robot == robot), 3]),robotDB[robotDB$id==robot,2])#low
}
else {
output <<- rbind(output, c(id=toString(assign[which(assign$robot == robot), 3]), Low=robotDB[robotDB$id==robot,2]))
}
}
start <- str_match(data,"^value.*[ ](\\d+)[ ].*[ ](\\d+)$" )
value <- as.data.frame(start[,2:3])
value <- value[complete.cases(value),]
colnames(value) <- c("value","robot")
start <- str_match(data,"^bot (\\d+) .* (\\w*) (\\d+)[ ].* (\\w*) (\\d+)$" )
assign <- as.data.frame(start[,-1])
assign <- assign[complete.cases(assign),]
colnames(assign) <- c("robot","lowType","low","highType","high")
a <- apply(value, 1, function(x) {addToRobot(x[2],x[1])})
robotDB[ which(robotDB$Low==17
& robotDB$High == 61), ]$id
prod(as.integer(output[ which(output$id=='0' |output$id=='1' |output$id=='2'), 2]))
--- Day 14: One-Time Pad ---
In order to communicate securely with Santa while you're on this mission, you've been using a one-time pad that you generate using a pre-agreed algorithm. Unfortunately, you've run out of keys in your one-time pad, and so you need to generate some more.
To generate keys, you first get a stream of random data by taking the MD5 of a pre-arranged salt (your puzzle input) and an increasing integer index (starting with 0, and represented in decimal); the resulting MD5 hash should be represented as a string of lowercase hexadecimal digits.
However, not all of these MD5 hashes are keys, and you need 64 new keys for your one-time pad. A hash is a key only if:
It contains three of the same character in a row, like 777. Only consider the first such triplet in a hash.
One of the next 1000 hashes in the stream contains that same character five times in a row, like 77777.
Considering future hashes for five-of-a-kind sequences does not cause those hashes to be skipped; instead, regardless of whether the current hash is a key, always resume testing for keys starting with the very next hash.
For example, if the pre-arranged salt is abc:
The first index which produces a triple is 18, because the MD5 hash of abc18 contains ...cc38887a5.... However, index 18 does not count as a key for your one-time pad, because none of the next thousand hashes (index 19 through index 1018) contain 88888.
The next index which produces a triple is 39; the hash of abc39 contains eee. It is also the first key: one of the next thousand hashes (the one at index 816) contains eeeee.
None of the next six triples are keys, but the one after that, at index 92, is: it contains 999 and index 200 contains 99999.
Eventually, index 22728 meets all of the criteria to generate the 64th key.
So, using our example salt of abc, index 22728 produces the 64th key.
Given the actual salt in your puzzle input, what index produces your 64th one-time pad key?
Your puzzle input is qzyelonm.
-- Part Two ---
Of course, in order to make this process even more secure, you've also implemented key stretching.
Key stretching forces attackers to spend more time generating hashes. Unfortunately, it forces everyone else to spend more time, too.
To implement key stretching, whenever you generate a hash, before you use it, you first find the MD5 hash of that hash, then the MD5 hash of that hash, and so on, a total of 2016 additional hashings. Always use lowercase hexadecimal representations of hashes.
For example, to find the stretched hash for index 0 and salt abc:
Find the MD5 hash of abc0: 577571be4de9dcce85a041ba0410f29f.
Then, find the MD5 hash of that hash: eec80a0c92dc8a0777c619d9bb51e910.
Then, find the MD5 hash of that hash: 16062ce768787384c81fe17a7a60c7e3.
...repeat many times...
Then, find the MD5 hash of that hash: a107ff634856bb300138cac6568c0f24.
So, the stretched hash for index 0 in this situation is a107ff.... In the end, you find the original hash (one use of MD5), then find the hash-of-the-previous-hash 2016 times, for a total of 2017 uses of MD5.
The rest of the process remains the same, but now the keys are entirely different. Again for salt abc:
The first triple (222, at index 5) has no matching 22222 in the next thousand hashes.
The second triple (eee, at index 10) hash a matching eeeee at index 89, and so it is the first key.
Eventually, index 22551 produces the 64th key (triple fff with matching fffff at index 22859.
Given the actual salt in your puzzle input and using 2016 extra MD5 calls of key stretching, what index now produces your 64th one-time pad key?
Your puzzle input is still qzyelonm.
In [ ]:
library(digest)
library(stringr)
input <- "qzyelonm"
charwith3 <- data.frame(input=integer(),
md5=character(),
ch=character(),
valid=logical(),
stringsAsFactors=FALSE)
charwith5 <- data.frame(input=integer(),
md5=character(),
ch=character(),
stringsAsFactors=FALSE)
current <- 0
goal <- 64
finish <- 99999999
done <- FALSE
while(finish>=current){
if(sum(charwith3$valid)>=goal && finish==99999999){
finish <- current + 1003
}
x <- paste(input,current,sep="")
x <- digest(x,"md5", serialize = FALSE)
#look for 5
search <- TRUE
aa<-x
ttt <- str_match(aa,"(.)\\1{4,}")
if((!is.na(ttt[1]))){
cht <- ttt[2]
charwith5<-rbind(charwith5,data.frame(input=current,md5=x,ch=cht,valid=FALSE))
charwith3$valid[charwith3$ch==cht & charwith3$input>current-1001] <- TRUE
charwith3$solver[charwith3$ch==cht & charwith3$input>current-1001] <- current
}
#Look for 3
aa<-x
ttt <- str_match(aa,"(.)\\1{2,}")
if((!is.na(ttt[1]))){
cht <- ttt[2]
charwith3<-rbind(charwith3,data.frame(input=current,md5=x,ch=cht,solver=0,valid=FALSE))
}
current <- current+1
}
Q1 <- charwith3$input[charwith3$valid][64]
charwith3 <- data.frame(input=integer(),
md5=character(),
ch=character(),
valid=logical(),
stringsAsFactors=FALSE)
charwith5 <- data.frame(input=integer(),
md5=character(),
ch=character(),
stringsAsFactors=FALSE)
current <- 0
goal <- 64
finish <- 99999999
done <- FALSE
while(finish>=current){
if(sum(charwith3$valid)>=goal && finish==99999999){
finish <- current + 1001
}
x <- paste(input,current,sep="")
for (i in 1:2017) {
x <- digest(x,"md5", serialize = FALSE)
}
#look for 5
search <- TRUE
aa<-x
ttt <- str_match(aa,"(.)\\1{4,}")
if((!is.na(ttt[1]))){
cht <- ttt[2]
charwith5<-rbind(charwith5,data.frame(input=current,md5=x,ch=cht,valid=FALSE))
charwith3$valid[charwith3$ch==cht & charwith3$input>current-1001] <- TRUE
charwith3$solver[charwith3$ch==cht & charwith3$input>current-1001] <- current
}
#Look for 3
aa<-x
ttt <- str_match(aa,"(.)\\1{2,}")
if((!is.na(ttt[1]))){
cht <- ttt[2]
charwith3<-rbind(charwith3,data.frame(input=current,md5=x,ch=cht,solver=0,valid=FALSE))
}
current <- current+1
}
Q2 <- charwith3$input[charwith3$valid][64]
paste("Q1 - The 64th key is produce by the index = ", Q1, '\n')
cat("Q2 - The 64th key is produce by the index = ", Q2, '\n')
In [ ]:
In [ ]: