1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ This is a problem in mathematics (combinatorics), and not the Mathematica programming language. $\endgroup$ – David G. Stork Feb 9 '17 at 22:12
  • $\begingroup$ Yes, but I wish to enumerate small cases of this problem. $\endgroup$ – SAWblade Feb 9 '17 at 22:24
  • $\begingroup$ @SAWblade You might be interested in GridGraph and FindPath then. I suspect that you will still have to figure out logic to exclude the unacceptable paths. $\endgroup$ – MarcoB Feb 9 '17 at 22:37
  • $\begingroup$ It isn't clear whether you can only have UP and RIGHT as moves, or if LEFT and DOWN also work. You might find inspiration from the answers here $\endgroup$ – Jason B. Feb 9 '17 at 23:26
  • $\begingroup$ assuming "RIGHT" and "UP" are the only allowed directions: maybe paths = {#, RotateRight@#} &@Flatten@Table[{"RIGHT", "UP"}, {n - 1}]? $\endgroup$ – kglr Feb 9 '17 at 23:30
5
$\begingroup$
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"]]}]

Mathematica graphics

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"]]}]

Mathematica graphics

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.