2021 Day 15

— Day 15: Chiton —

The cave roof is getting lower and you can only move in two dimensions.

What is the lowest total risk of any path from the top left to the bottom right?

library(tidyverse)
library(igraph)

Attaching package: 'igraph'

The following objects are masked from 'package:lubridate':

    %--%, union

The following objects are masked from 'package:dplyr':

    as_data_frame, groups, union

The following objects are masked from 'package:purrr':

    compose, simplify

The following object is masked from 'package:tidyr':

    crossing

The following object is masked from 'package:tibble':

    as_data_frame

The following objects are masked from 'package:stats':

    decompose, spectrum

The following object is masked from 'package:base':

    union

my_file <- here::here("2021", "data-2021-15.txt")
x = read_fwf(my_file, fwf_widths(rep_len(1,100), col_names = 1:100))

Rows: 100 Columns: 100

── Column specification ────────────────────────────────────────────────────────

dbl (100): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19...

ℹ Use `spec()` to retrieve the full column specification for this data.
ℹ Specify the column types or set `show_col_types = FALSE` to quiet this message.

x = as.matrix(x)

Create a matrix and use some kind of graph movement.

define_edges = function(i, j) {
        if (i == 1 & j == 1) {
            e = list(c(1,0), c(0,1))
        } else if (i == 1 & j == 100) {
            e = list(c(1,0), c(0,-1)) 
        } else if (i == 100 & j == 1) {
            e = list(c(-1,0), c(0,1))
        } else if (i == 100 & j == 100) {
            e = list(c(-1,0), c(0,-1))
        } else if (i == 1) {
            e = list(c(1,0), c(0,1), c(0,-1))
        } else if (j == 1) {
            e = list(c(-1,0), c(1,0), c(0,1))
        } else if (i == 100) { 
            e = list(c(-1,0), c(0,1), c(0,-1))
        } else if (j == 100) { 
            e = list(c(-1,0), c(1,0), c(0,-1))
        } else {
            e = list(c(1,0), c(0,1), c(-1,0), c(0,-1))
        }
        
    return(e)
}

g = make_empty_graph(n=10000, directed=TRUE)

for (i in 1:100) { 
    for (j in 1:100) { 
        # define edges that we can move on
        e = define_edges(i,j)
        for (d in e) {
            a = i + d[1]
            b = j + d[2]
            outo = (a-1)*100 + b # from this node
            into = (i-1)*100 + j # into this node
            # cat(outo, into, "\n")
            # print(into)
            g = add_edges(g, c(outo,into), weight=x[i,j])
        }
    }
}

Solve?

distances(g, 1, 10000)

     [,1]
[1,]  299

shortest_paths(g, 1, 10000)

$vpath
$vpath[[1]]
+ 199/10000 vertices, from f70e3ee:
  [1]     1   101   102   103   203   204   304   404   504   505   506   606
 [13]   607   608   609   709   710   711   811   812   813   814   815   816
 [25]   817   818   918   919   920  1020  1120  1220  1320  1420  1421  1422
 [37]  1522  1622  1623  1624  1724  1824  1825  1925  1926  1927  1928  1929
 [49]  2029  2129  2229  2230  2231  2232  2332  2333  2334  2335  2336  2436
 [61]  2536  2636  2736  2836  2936  3036  3037  3038  3138  3238  3239  3339
 [73]  3439  3440  3441  3541  3641  3741  3841  3842  3942  4042  4043  4143
 [85]  4243  4343  4443  4444  4544  4644  4744  4844  4944  4945  5045  5046
 [97]  5146  5246  5346  5446  5546  5646  5746  5846  5946  5947  6047  6048
[109]  6148  6248  6249  6349  6350  6351  6451  6551  6552  6652  6752  6753
+ ... omitted several vertices


$epath
NULL

$predecessors
NULL

$inbound_edges
NULL