Do i need pathfinding for this?

[MisterWhite]

Here is the task:
How many different paths there exist from one corner to another under given rules:

1) A hero should travel from upper left corner (marked with @) to lower right corner (marked with $).

2) He only can move by safe squares ("+", stepping on "X" causes you to drown), and from each square he only can move in two directions - either right or down.

The map:

@ + + + +
+ + + X X
+ X + + +
+ + + X +
+ X + + X
+ + + + $

 

So i am not sure how to even start solving this problem.

[madknight3]

1 hour ago, MisterWhite said:

So i am not sure how to even start solving this problem.

Start with recursion.

[fizzlesticks]

It can be done with path finding but that isn't the intended solution. 

Look into "dynamic programming".

[PlutoNZL]

Because your hero can only move right or down, the number of valid paths at any square is equal to the number of valid paths from the square below your hero plus the number of valid paths from the square to the right of your hero.

 

That is:

P(x, y) = P(x+1, y) + P(x, y+1)

 

For example, lets say that we have to below grid of squares:

@ 6 + + +
4 + + X X
+ X + + +
+ + + X +
+ X + + X
+ + + + $

And suppose that we know that the square at (1, 0) has 6 valid paths and the square at (0, 1) has 4 valid paths (6 and 4 are completely made up). The hero can either go down one square and have 4 valid paths, or he can go right one square and have 6 valid paths. Therefore, he has 10 valid paths from point (0, 0).

 

In other words, do what @madknight3 said.

 

[Blade of Grass]

If you want to look at this from a mathematics perspective: http://staff.argyll.epsb.ca/jreed/math30p/perms_combs/pathways.htm

this is what you want

[MisterWhite]

On 2016-02-20 at 6:50 PM, madknight3 said:

Start with recursion.

 

On 2016-02-20 at 7:08 PM, fizzlesticks said:

It can be done with path finding but that isn't the intended solution. 

Look into "dynamic programming".

 

On 2016-02-20 at 8:21 PM, PlutoNZL said:

In other words, do what @madknight3 said.

 

Ok, so i've read about recursion, dynamic programming, a bit about backtracking, Pascal's triangle, memoization (did not understand most of it just that recursion calls the function within function, DP breaks big task into smaller ones, understood the pascal's triangle and some of memoization, and that backtracking eliminates wrong solutions or something but isn't very effective in speed) and sadly i have no idea how to start, i would know how to count all of the paths but those "obstacles" are out of my league
 

[fizzlesticks]

Memoization is just caching what you've already calculated. For example, to calculate the 5th fibonacci number you have to calculate the 4th and 3rd number first. By doing this with just recursion, you would end up making all of these calls.

fib(5)

--fib(4)

----fib(3)

------fib(2)

--------fib(1)

--------fib(0)

------fib(1)

----fib(2)

------fib(1)

------fib(0)

--fib(3)

----fib(2)

------fib(1)

------fib(0)

----fib(1)

 

With just recursion you end up calculating fib(3)  twice, fib(2) 3 times and fib(1) 5 times. 

Memoization would add some look up table for already calculated values. In the fib function the first thing you would do it check the look up table to see if you already calculated fib for that number and if you did just return the value in the table. If you didn't, calculate the number then store it in the look up table. This eliminates all those redundant calls and a lot of the recursion.

 

Dynamic programming is essentially recursion and memoization without the recursive calls. Since you know you'll have to calculate all the previous numbers in order to get fib(5), just calculate them all in order starting with fib(0) and fib(1). After those 2 numbers, you know the previous numbers you need to calculate the next number have already been done, so you can just pull the values out of the array and add them. 

 

 

So for this problem, you can have a 2d array where each cell represent the number of paths there are to get to that cell. Since you can only move down or right, the number of paths to  a cell is equal to the number of paths to the cell above it plus the paths to the cell to the left of it (if they exist.) By calculating the cells in a particular order, you'll already have the values you need for the cell your calculating (besides the very first cell which has a known value of 1, this would be the base condition if you were to do it recursively.) 

For the obstacles, just treat them as if there was no way to get to that cell, which would give them a value of 0.