0
$\begingroup$

I had to solve this riddle from my book but so far I'm stuck at by doing several attempts and I felt it is like counting grains of sugar or some kind of sisyphean task. Can somebody help me with this?

The problem is as follows:

Using the figure from below, find the number of different routes which exist to go from point B to point A by traveling only in the directions indicated, being upwards, to the left, and in upward diagonals.

Sketch of the problem

The existing alternatives given were:

$\begin{array}{ll} 1.&63\\ 2.&39\\ 3.&48\\ 4.&56\\ 5.&52\\ \end{array}$

Well for this one I'm totally lost. The only thing that I could come up with was to draw what it was the obvious choice, or in other words to draw the figure as depicted in orange line. But that was only one path that I could find. I tried to go in with another route which is colored as pear color, but that's how far I went.

Sketch of the attempted solution

Does it exist a way to solve this riddle more systematically and not just guessing or playing around with different combinations?.

An answer which would help me the most is one which could include perhaps an improved graphics or some sort of redrawing in Asymptote or any program showing a path or a way to solve this perhaps graphically if required.

I'd like somebody could help me with this question as I tried much effort and has not yet yielded results. Hence require assistance. Can somebody guide me on this?.

$\endgroup$
  • 1
    $\begingroup$ How do you get started if you can't use downward diagonals? $\endgroup$ – Jens Feb 14 at 17:46
  • $\begingroup$ You can view this as a directed graph, and use linear algebra to count walks in a directed graph $\endgroup$ – Peter Kagey Feb 14 at 17:46
  • $\begingroup$ If the question was "how many ways to get from B to A", the answer would be $52$. $\endgroup$ – Jens Feb 14 at 18:09
  • $\begingroup$ @Jens I'm sorry. I tried to copy my attempt from my handwritten notes, the first thing I could come up with was to draw lines between $A$ to $B$. But because I was in a rush I didn't realized that it was the other way around in other words from $B$ to $A$. Please check the edited question. Yes I noticed that downward diagonals were not allowed. $\endgroup$ – Chris Steinbeck Bell Feb 15 at 16:28
  • $\begingroup$ @Jens You're indeed correct, the question was find the way from $B$ to $A$ not as it was written earlier I edited the question to reflect what it was in the original source. I'm sorry because I did it in a rush. Now for the second part I don't know how you got to $52$. $\endgroup$ – Chris Steinbeck Bell Feb 15 at 16:30
1
$\begingroup$

You can do this using dynamic programming. You will label each node with the number of legal paths from $B$ to that node. Initially, $B$ itself is labeled with $1$. Starting with the nodes which are closer to $B$, write label each node with the sum of the labels of its neighbors in the $\to,\searrow,\downarrow$ and $\swarrow$ directions. If there are no nodes in those direction, skip them in the sum. If you try to add up the label of an unlabeled node, first find the label of that earlier node. This works because every path to a node is preceded by a path to one of its $\to,\searrow,\downarrow,\swarrow$ neighbors. Adding the numbers of these paths gives the number of paths to the original node.

If I compute correctly, the answer is $52.$

enter image description here

$\endgroup$
  • $\begingroup$ This concept of dynamic programming is totally new for me. It took me time to understand what you did but I think I got it. Because there are limitation of characters in the comment box, I had to split my questions in the coming comments. Can you take some time to read them please?. :-) $\endgroup$ – Chris Steinbeck Bell Feb 15 at 16:47
  • $\begingroup$ In your graph each node has a number which indicates the number of paths allowed from $B$ to that node, am I right?. For example the one which is on the right of label $4$ says $1$, this is $1$ because the only allowed route to get there is an upward diagonal and a straight line up, so that accounts for one path, right?. Then $4$ is $1+1+2$ the other three left corners in that square. $\endgroup$ – Chris Steinbeck Bell Feb 15 at 16:47
  • $\begingroup$ But precaution must be taken as $5$ which is in the upper square is $4+1$ and not $4+1+1$ because there is no link between the $1$ which is in the bottom right of that square with the label numbered $5$. Is this part right?. Gee I hope to be understanding you well because at looking at this maze initially I felt dumbfounded. $\endgroup$ – Chris Steinbeck Bell Feb 15 at 16:47
  • $\begingroup$ @ChrisSteinbeckBell You got it! $\endgroup$ – Mike Earnest Feb 15 at 16:48
  • $\begingroup$ I believe that your answer could be improved if you add zeros to the top corners on the right side of $A$ as you did below to the left side of $B$ as they indicate they're not nodes. The more I look on it, seems that this riddle wasn't that hard as it seemed to be. I'm left curious does this approach will work with this kinds of problems or should I be aware or some caveat or advise on using this what you called dynamic programming?. Since I don't know much about it, I'd like to be careful to not incur into any misunderstanding or any error. $\endgroup$ – Chris Steinbeck Bell Feb 15 at 16:51

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.