# Apologies, I wrote my solution in R, and it can't be run on SoloLearn. # I'll repost something in python soon. It will probably make for prettier code, as well! # Challenge by GAWEN STEASY (09/14/2017) # https://www.sololearn.com/Discuss/714590/challenge-find-the-longest-path-in-matrix # Find the longest path in a matrix with given constraints # Given a n*n matrix where all numbers are distinct, find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1. # We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1. # Example: # Input: mat[][] = {{1, 2, 9} {5, 3, 8} {4, 6, 7}} Output: 4 The long ################################################################ ################################################################ check <- function(x,y) ifelse(y-x == 1, 1, 0) # It's not really a random walk, is it? valid_walk <- function(i,j,m=1) { z <- T while(z) { if(i-1 > 0) if(check(A[i,j],A[i-1,j])) { i <- i-1; break } if(i+1 <= n) if(check(A[i,j],A[i+1,j])) { i <- i+1; break } if(j-1 > 0) if(check(A[i,j],A[i,j-1])) { j <- j-1; break } if(j+1 <= n) if(check(A[i,j],A[i,j+1])) { j <- j+1; break } z <- F } if(z) { m <- m+1; valid_walk(i,j,m) } else return(m) # m-1 is the true number of "steps," i.e. transitions between cells, # but the challenge tells us to count cells as steps so 'm' reflects this } A <- t(matrix(c(1, 2, 9, 5, 3, 8, 4, 6, 7),nrow=3)) ## example matrix from challenge mymax <- NULL for (i in 1:n) for (j in 1:n) mymax <- c(mymax,valid_walk(i,j)) print(max(mymax)) ################################################################ ################################################################ # A fun probablistic exploration of a the possible solutions to 1000 randomly generated nxn matrices n <- 3 prob.max <- NULL for(i in 1:1000) { A <- matrix(sample(1:n^2,n^2,replace=F),nrow=n) mymax <- NULL for (i in 1:n) for (j in 1:n) mymax <- c(mymax,valid_walk(i,j)) print(max(mymax)) prob.max <- c(prob.max,max(mymax)) } table(prob.max) hist(prob.max) # it's ugly, use ggplot below if you prefer # install.packages("ggplot2") # library(ggplot2) # ggplot(data.frame(prob.max),aes(x=prob.max)) + geom_histogram(binwidth=1)

Longest Path In Matrix (R)