2018-4-2

Project Euler Problem 15 - Lattice Paths - solved with R

Solution to the 15th Project Euler Problem coded and visualised with R.

The 15th Project Euler problem - Lattice Paths - is stated as follows. Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?

Number of Lattice Paths

countRoutes <- function(grid.size){
  # Get the binomial coefficient i.e. the number of ways
  # of picking k unordered outcomes from n possibilities.
  k <- grid.size
  n <- k*2
  result <- factorial(n) / (factorial(k)*factorial(n-k))
  return(result)
}

# Call the device driver.
png(file="graph.png",width=1080,height=1080,res=120)

# Set margins.
par(mar=c(5,3,3,3))

# Create a range from 1 to 20 for the x axis.
x <- c(1:20)

# Map the range using the countRoutes function.
y <- countRoutes(x)

# Plot the graph without axes and annotations.
plot(y, type="o", col="blue", axes=FALSE, ann=FALSE, pch=16)

# Draw a box around the plot.
box()

# Add gridd lines.
abline(h=tail(y,3), v=x, col="gray", lty=3)

# Add labels for the last three markers.
text(tail(x,3),tail(y,3),labels=tail(y,3), pos=2)

# Add the X axis.
axis(1, at=x)

# Add a title for the x axis.
title(xlab= "Lattice Grid Size")

# End call to device driver.
dev.off()
Jan Järfalk — User experienced esthete, technician, geek and web worker. Aspiring artist and recreational mathematician. I indulge and travel plenty. Constraints are good.