2

Suppose I have an n-high pyramid of numbers like:

    1
   5 8
  2 5 4
 8 9 3 1
2 8 3 7 2

How can I algorithmically walk through every possible path from the top of the pyramid to the bottom?

To better explain, let me represent the pyramid this way:

1 2 3 4 5
-----------
1         | a
5 8       | b
2 5 4     | c
8 9 3 1   | d
2 8 3 7 2 | e

For example:

        On the path | a b c d e (Path)
       -------------|------------------
Path 1:  1 5 2 8 2  | 1 1 1 1 1
Path 2:  1 5 2 8 8  | 1 1 1 1 2
Path 3:  1 5 2 9 8  | 1 1 1 2 2
Path 4:  1 5 2 9 3  | 1 1 1 2 3
...
Path m:  1 8 4 1 2  | 1 2 3 4 5

Where m is the total number of paths.

I understand that the problem can be reduced to simply generate all the possible paths denoted in the second column of the table, and I could come up fairly easily with an algorithm to generate those for a 5-high (or any other fixed high) pyramid, but I can't seem to come up with a general solution.

The algorithm cannot be recursive, for the simple reason that I've already solved the problem recursively and I'm interested in a non-recursive solution to get a complete view of the problem.

8
  • 2
    This problem is inherently recursive. Even if you cheated by creating your own stack and iterating, you are just shifting the recursion from the call stack to some other data structure that you manage, as opposed to the CPU.
    – user22815
    Oct 4 '15 at 20:49
  • I think all he wants is a non recursive algorithm without calling the function again. (of course a recursion can always be made non recursive using your own stack)
    – Gabriel
    Oct 4 '15 at 21:13
  • 1
    No need to be recursive. At each level, you have a position, and the position of the next level can only be (-0.5) or (+0.5) (if you use the isosceles triangle diagram at the top of your post), or { (0) , (1) } (if you use your right-angle triangle diagram that is easier to implement in code).
    – rwong
    Oct 4 '15 at 22:51
  • 1
    In other words, at every node you only have a binary choice: left or right.
    – rwong
    Oct 4 '15 at 22:51
  • 2
    The non-recursive part refers to the fact that breadth-first search (BFS) or depth-first search (DFS) can always be re-implemented as non-recursive algorithms by using suitable data structure sto store nodes that are "to be visited later".
    – rwong
    Oct 4 '15 at 22:55
2

If you start at the top of the triangle there's only 2 choices to continue the path - left or right. If you chose left, then there's only 2 choices to continue the path - left or right. If you chose right, then there's only....

Let's encode the "left or right" decision at each level as 1 bit, where 0 = left and 1 = right. If there are 5 levels you can encode a path as 4 bits. If there are N levels you can encode a path as (N - 1) bits. The number of paths is 1 << (N - 1).

Now let's think about the bottom row. If you always choose "left" then it'd be path 0000b, which has no set bits, and you end up at the 0th number on the bottom row. If you always choose "right" then it'd be path 1111b, which has 4 set bits, and you end up at the 4th number on the bottom row. If you alternate (left, right, left, right) it'd be path 0101b, which has 2 set bits, and you end up at the 2nd number on the bottom row. If you alternate the opposite way (right, left, right, left) it'd be path 1010b, which has 2 set bits, and you end up at the 2nd number on the bottom row. The position of the number on the bottom row depends on how many set bits in the path.

Now think about the second to last row - it's the same as the last row, except you ignore the last bit! Just shift the path number right once, and count the number of set bits to determine the position of the number on the second to last row.

If you think about this; you probably don't even need to bother generating a table of paths in the first place - you could write a get_number(path, row) function and use that instead.

0

Maybe this:

Make a list t of left or right markers (0: left, 1: right) for all levels-1: So in your example t has 4 entries initially all set to zero (marking the first path) through your pyramid (tree).

so now you need to count through all left or right possibilities at each level (except level 0, which is the first node) we either go right or left :

Python:

pyr = [
        [1] ,     
        [5 ,8]     ,  
        [2,5, 4]   ,  
        [8, 9, 3, 1]   ,
        [2, 8,3, 7, 2] ]

pyrD = len(pyr)-1

t = [0]*pyrD

def getNodes(t):
      print("---------------")
      print("leftRightIndices: " , t)
      nodesIdx = [0]
      nodes = [ pyr[0][nodesIdx[0]] ]
      for idx,LorR in enumerate(t):
          nodesIdx.append( nodesIdx[idx]+LorR )
          nodes.append(pyr[idx+1][nodesIdx[idx+1]])

      print("nodes: " , nodes)
      print(nodes)


done = False
while not done:

    getNodes(t)

    for i in range(0,pyrD):
        carryOver = (t[i] + 1) > 1
        if not carryOver:
            t[i]+=1
            break;
        else:
            if i == pyrD-1:
                done = True
            t[i] = 0;

Which gives:

    ---------------
leftRightIndices:  [0, 0, 0, 0]
nodes:  [1, 5, 2, 8, 2]
---------------
leftRightIndices:  [1, 0, 0, 0]
nodes:  [1, 8, 5, 9, 8]
---------------
leftRightIndices:  [0, 1, 0, 0]
nodes:  [1, 5, 5, 9, 8]
---------------
leftRightIndices:  [1, 1, 0, 0]
nodes:  [1, 8, 4, 3, 3]
---------------
leftRightIndices:  [0, 0, 1, 0]
nodes:  [1, 5, 2, 9, 8]
---------------
leftRightIndices:  [1, 0, 1, 0]
nodes:  [1, 8, 5, 3, 3]
---------------
leftRightIndices:  [0, 1, 1, 0]
nodes:  [1, 5, 5, 3, 3]
---------------
leftRightIndices:  [1, 1, 1, 0]
nodes:  [1, 8, 4, 1, 7]
---------------
leftRightIndices:  [0, 0, 0, 1]
nodes:  [1, 5, 2, 8, 8]
---------------
leftRightIndices:  [1, 0, 0, 1]
nodes:  [1, 8, 5, 9, 3]
---------------
leftRightIndices:  [0, 1, 0, 1]
nodes:  [1, 5, 5, 9, 3]
---------------
leftRightIndices:  [1, 1, 0, 1]
nodes:  [1, 8, 4, 3, 7]
---------------
leftRightIndices:  [0, 0, 1, 1]
nodes:  [1, 5, 2, 9, 3]
---------------
leftRightIndices:  [1, 0, 1, 1]
nodes:  [1, 8, 5, 3, 7]
---------------
leftRightIndices:  [0, 1, 1, 1]
nodes:  [1, 5, 5, 3, 7]
---------------
leftRightIndices:  [1, 1, 1, 1]
nodes:  [1, 8, 4, 1, 2]
6
  • I guess paths with "leaps" are not legal. The path [2, 0, 0, 0, 0] for instance has a leap from column 2 to column 0.
    – COME FROM
    Oct 5 '15 at 8:43
  • yes, of course, if this is the case? then its a tree! we could add a leapCheck routine for every solution and discard it :-)
    – Gabriel
    Oct 5 '15 at 11:37
  • @Gabriel If you look at my example, you will find that I've discarded the path 1 1 1 2 1, which contains a leap. Oct 5 '15 at 11:39
  • Jeah you are correct!
    – Gabriel
    Oct 5 '15 at 11:59
  • I correct the code, it becomes even simpler, in a moment
    – Gabriel
    Oct 5 '15 at 12:01

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.