One-Way Streets

One Way Streets

Let me model a specific assignment of streets with a 12-tuple logical string. Going left to right, top to bottom, (R,R,D,D,D,R,R,D,D,D,R,R) will model the directions. FALSE in the first spot would mean the direction between the top left and top middle vertex is NOT Right (rather Left). A TRUE in the fourth spot means the direction between the top middle vertex and middle vertex is Down.

There are 12 paths from the top left vertex to the bottom right vertex that do not overlap. The following function will take as input a random 12-tuble street assignment and returen TRUE if a path exists and FALSE otherwise.

pathExists <- function(street_assign){
   if(all(street_assign[c(1,2,5,10)]==1) ||
      (all(street_assign[c(1,2,5,9,12)]==1) & street_assign[7]==0) ||
      (all(street_assign[c(1,2,5,8,11,12)]==1) & all(street_assign[c(6,7)]==0)) ||
      all(street_assign[c(1,4,7,10)]==1) ||
      all(street_assign[c(1,4,9,12)]==1) ||
      (all(street_assign[c(1,4,8,11,12)]==1) & street_assign[6]==0) ||
      all(street_assign[c(3,6,9,12)]==1) ||
      all(street_assign[c(3,6,7,10)]==1) ||
      (all(street_assign[c(2,3,5,6,10)]==1) & street_assign[4] == 0) ||
      all(street_assign[c(3,8,11,12)]==1) || 
      (all(street_assign[c(3,7,8,10,11)]==1) & street_assign[9]==0) ||
      (all(street_assign[c(2,3,5,8,10,11)]==1) & all(street_assign[c(4,9)]==0))){
      return(TRUE)
   }
   else{return(FALSE)}
}

Build all 2^12 = 4096 possible street assignments and put them in a huge array.

# A function that takes a decimal number and returns the binary number
binary <- function(x){
   if(x==0){
      return(0)
      break
   }
   j <- trunc(log2(x))
   y <- x%%2^j
   B <- 10^j
   for(i in (j-1):0){
      B <- B + 10^i*y%/%2^i
      y <- y%%2^i
   }
   return(B)
}

## A function that will take any number 12 digits or less and create a vector of 
## length 12 of all the digits with leading 0's.

twelveVec <- function(x){
   if(log10(x+1)>12){
      return("Number too large")
   }
   y <- x
   v <- rep(0,12)
   for(i in 1:12){
      v[i] <- y%/%10^(12-i)
      y <- y%%10^(12-i)
   }
   return(v)
}

## Create a 4096 row matrix of all the binary numbers from 0 to 4095

StreetAssignments <- c()
for(r in 0:4095){
   StreetAssignments <- rbind(StreetAssignments,
                              twelveVec(binary(r)))
}

dim(StreetAssignments)

## [1] 4096   12

Let’s fill a vector of size 4096 full of 0’s or 1’s (FALSE and TRUE) to tell us which of the street assignments have an existing path. Then, we’ll obtain our answer.

Paths <- apply(StreetAssignments, 1, pathExists)
sum(Paths)/length(Paths)

## [1] 0.2770996