Thread: having difficulty with this problem

okay, I am doing this problem my friend gave me as a challenge and I want to convert it into code but it almost seems impossible to convert this problem into code to get the solution. any help or suggestions?

here is the problem:
we start from [start] and have to reach the destination [end] only by moving up and right. I cannot move down or left. how many different solutions are there?

Code:

 ____________
|             end
|        |
|            |
|        |
|            |
|        |
|            |
|        |
|  __________|
start

do I need to use some form of nested loop or is there some simple formula to solve this?

ok, how do I solve this problem using Pascal's Triangle algorithm?

Originally posted by Unregistered
ok, how do I solve this problem using Pascal's Triangle algorithm?

this is how it is done...

if you can move Right 8 times and Up 5 times you would do this

(8!*5!)/(8*5)

where 8! would be 8*7*6*5*4*3*2*1

that will give you the number of possible paths :P

hmmm thank god for calculus class hehe

assuming i understand your example this is how it would be done :P

Code:

 ____________
|                      end
|        4|
|                      |
|        3|
|                      |
|        2|
|                      |
|        1|
|  1__2_3__4_|
start

im assuming from the diagram you can move Right 4 times and Up 4 times so the answer would be

(4!*4!)/(4*4) and therefore the answer would be 36 possible paths

are you sure that is correct?

I just drew a chart using Pascal's Triangle algorithm and it turns out to be 70. (there are 5 rows and 5 columns by the way). I think the algorithm uses a combination. I don't understand how to turn this problem into code... or is it even possible? I only have a limited knowledge in math.

Code:

here is the diagram I made to solve this problem:

                01
              01  01
            01  02  01
          01  03  03  01
        01  04  06  04  01
      01  05  10  10  05  01
    01  06  15  20  15  06  01
  01  07  21  35  35  21  07  01 
01  08  29  56  70  56  29  08  01

since it is a 5 * 5 square, I simplified the diagram
(the square is rotated 45 degrees)

        01
      01  01
    01  02  01
  01  03  03  01
01  04  06  04  01
  05  10  10  05
    15  20  15
      35  35
        70

thanks, taylorguitarman. I never knew this stuff was related to networking at all. anyway, I just finished the program but wasted a lot of time doing this even though I answered the problem already.