Introduction

This puzzle was published in New Scientist in June 2020¹. It is a practical example of a problem in graph theory. This vignette explains how the puzzle can be solved with redecison.

The puzzle

Three friends agree to drive from A to B via the shortest road possible (driving down or right at all times). They are hungry, so also want to drive through a Big Burger restaurant, marked in red. They are arguing about how many shortest routes will pass through exactly one Big Burger. Xenia: “I reckon there are 10.” Yolanda: “I’d say more like 20.” Zara: “No you’re both wrong, I bet there are more than 50.” Who is right, or closest to right?

Constructing the graph

The grid has 25 nodes and 40 edges (20 horizontal and 20 vertical). These form a directed graph because it is allowed to drive down or right only. Seven of the edges are defined as “Big Burger” edges. Because it is not possible to find a path from any node which revisits that node, the graph is acyclic (a directed acyclic graph, DAG).

Although it possible to construct the graph by creating 25 node objects explicitly, it is more compact to create a list of vertices in a loop construct. Indices \(i = [1 .. 5]\) and \(j = [1 .. 5]\) are used to identify grid intersections in the vertical and horizontal directions respectively. Each node is labelled as \(N_{i,j}\) and the index of node \(N_{i,j}\) in the list is \(5(i-1)+j\). Similarly, the 40 edges (arrows) are constructed more compactly in a list, with horizontal edges being labelled \(H_{i,j}\) (the horizontal edge joining node \(N_{i,j}\) to node \(N_{i,j+1}\)) and the vertical edges similarly as \(V_{i,j}\).

# node index function
idx <- function(i, j) {
  return(5L * (i - 1L) + j)
}
# create vertices
N <- vector(mode = "list", length = 5L * 4L)
for (i in seq(5L)) {
  for (j in seq(5L)) {
    N[[idx(i, j)]] <- Node$new(paste0("N", i, j))
  }
}
# create edges
H <- vector(mode = "list", length = 5L * 4L)
ie <- 1L
for (i in seq(5L)) {
  for (j in seq(4L)) {
    a <- Arrow$new(
      N[[idx(i, j)]], N[[idx(i, j + 1L)]], paste0("H", i, j)
    )
    H[[ie]] <- a
    ie <- ie + 1L
  }
}
V <- vector(mode = "list", length = 4L * 5L)
ie <- 1L
for (i in seq(4L)) {
  for (j in seq(5L)) {
    a <- Arrow$new(
      N[[idx(i, j)]], N[[idx(i + 1L, j)]], paste0("V", i, j)
    )
    V[[ie]] <- a
    ie <- ie + 1L
  }
}
# create graph
G <- Digraph$new(V = N, A = c(V, H))

Finding the paths

Method paths finds all possible paths between any two nodes, where a path is defined as a sequence of distinct and adjacent nodes. Because the restaurants are specific edges, each path is converted to a walk, which is a path defined as sequence of connected, non-repeating edges.

In this case, the number of restaurants traversed by each path is counted by comparing the label associated with each edge in each path with the labels of the edges which contain a restaurant.

Note that although we cannot guarantee that node A is saved within the graph at index 1 and node B is saved at index 25, we do know that A and B are saved at indices 1 and 25 in the local list V.

# get all paths from A to B
A <- N[[1L]]
B <- N[[25L]]
P <- G$paths(A, B)
# convert paths to walks
W <- lapply(P, FUN = G$walk)
# count and tabulate how many special edges each walk traverses
BB <- c("V11", "H22", "V25", "H33", "V32", "H44", "V43")
nw <- vapply(W, FUN.VALUE = 1L, FUN = function(w) {
  lv <- vapply(w, FUN.VALUE = TRUE, FUN = function(e) e$label() %in% BB)
  return(sum(lv))
})
# tabulate
ct <- as.data.frame(table(nw))

Solution found by rdecision

The number of paths which pass through exactly one Big Burger is 23. In total there are 70 paths from A to B, with the number of restaurants \(n\), traversed by each path as follows:

Provided solution

Yolanda’s estimate is closest - there are 23 shortest routes from A to B that pass through exactly one Big Burger. One way to solve this kind of puzzle is to systematically work from A and keep track of how many ways there are of reaching each point. With this problem, you should keep a separate count of how many ways there are of reaching each point after (a) zero or (b) one Big Burger visits. For line segments that contain a Big Burger, (b) becomes equal to (a) then becomes equal to 0 with the old value for (b) effectively discarded.