I'm new to Mathematica and thus don't really have any idea how to code what I need. My current research involves counting all possible paths that start at (0,0) and terminate at (n-1,n-1) on an n x n grid. The restriction is that any such paths cannot travel in the same direction twice in a row - e.g. a path that goes UP, RIGHT, RIGHT, UP on a 3x3 grid is invalid. I talked with a professor of mine about this but I'm still lost, even on the brute forcing methods, so I figured I would ask for help here. Thanks in advance!
1
$\begingroup$
$\endgroup$
5
$\begingroup$
$\endgroup$
ClearAll[f]
f[n_, dir : "UP" | "RIGHT" : "RIGHT"] := Module[{init=If[dir == "RIGHT", {1, 0}, {0, 1}]},
FoldList[Plus, {0, 0}, NestList[Reverse, init, 2 n - 3]]]
Examples:
f[5]
{{0, 0}, {1, 0}, {1, 1}, {2, 1}, {2, 2}, {3, 2}, {3, 3}, {4, 3}, {4, 4}}
f[5, "UP"]
{{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}}
Graphics:
n = 4;
Graphics[{Point[Tuples[Range[0, n], 2]], Red, Line[f[n]], Blue, Line[f[n, "UP"]]}]
Graphics[{MapIndexed[Text[Style[#2-1, 20], #]&, Outer[List, Range[0, n],Range[0, n]], {2}],
Red, Line[f[n]], Blue, Line[f[n, "UP"]]}]
GridGraphandFindPaththen. I suspect that you will still have to figure out logic to exclude the unacceptable paths. $\endgroup$ – MarcoB Feb 9 '17 at 22:37paths = {#, RotateRight@#} &@Flatten@Table[{"RIGHT", "UP"}, {n - 1}]? $\endgroup$ – kglr Feb 9 '17 at 23:30