Count Grid Paths with No Three Equal Moves
SIG (Susquehanna)Data Scientist · Online Assessment
Last updated
Count lattice paths from `(0, 0)` to `(5, 5)` that never use three identical directions consecutively. The solution converts paths into alternating runs of length one or two, counts bounded compositions for equal and unequal run totals, and derives 84 valid paths.
Count Grid Paths with No Three Equal Moves
A frog moves from (0, 0) to (5, 5). Every step is either one unit right or one unit up. The frog refuses to make three moves in the same direction consecutively.
How many valid paths are there? Derive the count without enumerating all C(10, 5) paths one by one.
Follow-up questions
- How would a dynamic program count paths to a general point `(m, n)`?
- What changes if at most three consecutive moves in one direction are allowed?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.