• + 4 comments

    Just thinking through the problem, I realized it's just a sideways Pascal's Triangle. Let's say our word is "ABCDE".

    • A B C
    • B C D
    • C D E

    Let's look at each individual spot and how many paths there are to them. The "C" in the top right and bottom left have only one path to them, and the same can be said of the "B"s and "A". So, we can write the grid like:

    • 1 1 1
    • 1 C D
    • 1 D E

    Now, looking at the remaining "C", there are two ways to reach it. You can either come in from above, or come in from the left. There is only one way to come in from the top and one way to come in from the left, we can say that there are two ways to reach it:

    • 1 1 1
    • 1 2 D
    • 1 D F

    Now, for the right-most D, we can see that there are two ways to come in from the left, and one way to come in from above:

    • 1 1 1
    • 1 2 3
    • 1 D E

    Following a similar process for the last two letters, we can map out the number of paths to each spot in the matrix as:

    • 1 1 1
    • 1 2 3
    • 1 3 6

    Giving us a final answer of 6.

    This pattern should look familiar. It is actually a Pascal's Triangle in a different orientation. With a much larger matrix, we would get (sorry for terrible formatting):

    • 1 1 1 1 1 1
    • 1 2 3 4 5 6
    • 1 3 6 10 15 21
    • 1 4 10 20 35 46
    • 1 5 15 35 70 116
    • 1 6 21 46 116 232

    For a Pascal's Triangle, one can simply use a Combination function to find the value for any point in the triangle.

    I haven't solved it yet, but for those completely clueless about where to even start, hopefully this helps.