Lattice Paths Visualization

Imagine that we have a square lattice (grid) and the objective to go start from one corner and go to the other corner. The number of possible paths that can take you from the starting point to the ending point would be dependent on the dimensions of the lattice. One can write an algorithm to visualize how the paths evolve before reaching the final position.

For this demonstration,  I have chosen an 8×8 lattice which means there would be a total of (8+1)*(8+1) points. The image below shows the lattice.


Walking from the lower-left corner to the upper-right corner 

The algorithm explained at the end of the page details the methodology for walking from one corner to the other corner in succession. Note that the paths have been intentionally randomized to make the distinct overlapping paths more visible.


Code

I have used two languages for this exercise. Python for simulating the paths and Mathematica for plotting the paths generated by the Python script.

Python Script

if __name__ == '__main__':
    import csv

    with open("$$Path$$\\ProjectEuler00015.txt", 'w') as textFile:
        maximum = 9
        paths = [[[1, 1]]]
        fullPaths = []
        while any(path[-1] != [maximum, maximum] for path in paths):
            tempFullPaths = []
            for path in paths:
                endPoint = path[-1]
                if endPoint == [maximum, maximum]:
                    fullPaths.append(path)
                    paths.remove(path)
                elif endPoint != [maximum, maximum]:
                    appendList = []
                    if endPoint[0] < maximum:
                        appendList.append([endPoint[0] + 1, endPoint[1]])
                    if endPoint[1] < maximum:
                        appendList.append([endPoint[0], endPoint[1] + 1])
                    for appendPoint in appendList:
                        tempFullPaths.append(path + [appendPoint])
                paths = tempFullPaths
            fullPaths += tempFullPaths

        for path in fullPaths:
            textFile.write(str(path).replace('[', '{').replace(']', '}'))
            textFile.write('\n')

Mathematica Script

Module[{paths},
  paths =
      ToExpression /@
          StringSplit[
            Import[StringReplace[NotebookFileName[], ".nb" -> ".txt"]], "\n"];
  paths = GroupBy[paths, Length@# &];
  Framed[Graphics[{Opacity@0.1,
    Line[RandomReal[{-0.15, 0.15}, {Length@#, 2}] + #]} & /@ #,
    PlotRange -> {{0, 10}, {0, 10}}, ImageSize -> 500]] & /@
      Values[paths]
] // Column

End of the post 🙂