Advent of code Day 24

In [1]:

    

options(warn=-1)


    

In [3]:

    

library(igraph)
library(stringr)
library(combinat)


    

In [4]:

    

input <- readLines("data.txt")
nbOfKey <- 8


    

In [5]:

    

createsquare4NeigboursList <- function(n, m){ ##Create the list of neighbors
    return <- numeric()
    for(i in 1:(n)){
        for(j in 1:(m)){
            current <- ((i-1)*m)+j
            if(j<(m))
                return <- c(return,current,(current+1))
            if(i<(n))
                return <- c(return,current,(current+m))
        } 
    }
    return
}


    

In [6]:

    

row <- length(input)
col <- nchar(input[[1]])
edges <- createsquare4NeigboursList(row, col)
gr <- graph(edges, directed=FALSE) %>% set_vertex_attr("name", value = 1:(row*col)) #Graph is created
keys <- rep(0,nbOfKey)
devNull <- lapply(input, function(x) { #Remove walls and identify markers
    currentRow <- parent.frame()$i[]-1
    theRow <- str_split(x,"")[[1]]
    for (currentCol in 1:length(theRow)){
        vertex <- currentRow*col + currentCol
        if(theRow[currentCol]=="#"){
            gr <<- delete_vertices(gr, toString(vertex))
        } else if(!is.na(as.numeric(theRow[currentCol]))){
            key <- as.numeric(theRow[currentCol])
            keys[key+1] <<- vertex
        }
        

    }
})


    

In [7]:

    

distances <- matrix(0, nrow=nbOfKey, ncol=nbOfKey)
distances <- apply(distances, 1, function(x) {
    currentFrom <- parent.frame()$i[]
    sapply(x, function(y) {
        currentTo <- parent.frame()$i[]
        if(currentFrom>currentTo)
            distances(gr,toString(keys[currentFrom]),toString(keys[currentTo]))[[1]]
        else
            0
    })
})
distances


    

    







	
0  
30 
76 
40 
242
252
260
214
	
0  
 0 
58 
30 
224
234
242
196
	
0  
 0 
 0 
72 
178
188
192
150
	
0  
 0 
 0 
 0 
238
248
256
210
	
0  
 0 
 0 
 0 
  0
 26
 66
 48
	
0  
 0 
 0 
 0 
  0
  0
 76
 62
	
0  
 0 
 0 
 0 
  0
  0
  0
 82
	
0  
 0 
 0 
 0 
  0
  0
  0
  0

In [8]:

    

allOptions <- sapply(permn(2:nbOfKey), function(x) {
    fullPath <- c(1,x)
    currentTotal <- 0
    for (currentIndex in 2:length(fullPath)){
      currentTotal <- currentTotal + distances[fullPath[currentIndex-1],fullPath[currentIndex]]
      currentTotal <- currentTotal + distances[fullPath[currentIndex],fullPath[currentIndex-1]] 
    }
    currentTotal
})
Q1 <- min(allOptions)
Q1


    

    





428

In [9]:

    

allOptions <- sapply(permn(2:nbOfKey), function(x) {
    fullPath <- c(1,x,1)
    currentTotal <- 0
    for (currentIndex in 2:length(fullPath)){
      currentTotal <- currentTotal + distances[fullPath[currentIndex-1],fullPath[currentIndex]]
      currentTotal <- currentTotal + distances[fullPath[currentIndex],fullPath[currentIndex-1]] 
    }
    currentTotal
})
Q2 <- min(allOptions)
Q2


    

    





680

In [10]:

    

cat("Q1- Optimal Path in the maze: ", Q1, '\n')
cat("Q2- Optimal Path in the maze when returning to position 0: ", Q2, '\n')


    

    




Q1- Optimal Path in the maze:  428 
Q2- Optimal Path in the maze when returning to position 0:  680