How varied is my obstacle course?

Question

Background

I have constructed a simple obstacle course by placing boxes in a rectangular room. Now I want to count the number of essentially different ways in which it can be solved. I need you to write me a program for that.

Input

Your input is a non-empty rectangular array of the characters .#. The dots . are empty space, and the # are obstacles.

A path through the obstacle course begins at the top left corner and ends at the bottom right corner, and goes only right or down. Also, a valid path cannot go through an obstacle. Here are some examples drawn with +-characters:

Valid path  Invalid path  Invalid path  Invalid path
++........   ++........    +++++.....    ..+.......
.++++++#..   .+.....#..    ....+++#++    ..++...#..
......+#..   .+.++++#..    .......#.+    ...+++.#..
....#.++++   .+++#.++++    ....#....+    ....#+....

Two paths are essentially similar¹ if one can be transformed into the other by moving one + at a time. The intermediate paths must also be valid, so you can't bend a path over an obstacle. For example, the first two paths here are essentially similar, but the third is essentially different from them, since it can't be wiggled over the two obstacles:

++........   +.........   +++++++++.
.+++++.#..   ++.....#..   .......#+.
.....+.#..   .++++++#..   .......#++
....#+++++   ....#.++++   ....#....+

Output

Your output is the number of essentially different paths through the obstacle course. In other words, if all the valid paths are divided into classes of essentially similar paths, the output is the number of classes. Note that this number may be 0, if there are no valid paths.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There are no time bounds, except that you should evaluate your program on every test case before submitting it.

Test cases

....
....
.... => 1

...#
....
...# => 0

#..#
..#.
.... => 0

......
......
..##..
......
...... => 2

......
...#..
......
..#...
#..... => 3

......
..#...
......
....#.
#..... => 4

.......
##.....
....###
...#...
..##.#.
#....#.
..#.... => 0

......#.
..##....
...#....
.......#
....#...
.##...#.
....#...
##...... => 7

.........
.#.#.#.#.
.........
#.#...#.#
.........
.#.#.#.#.
......... => 17

..........
.#........
..........
.....#....
#.........
........#.
......#...
.......... => 10

.........
.#.......
.........
...#.....
.........
.....#...
.........
.......#.
......... => 16

_{1 The correct technical term is "homotopic".}

Answer 1

Python 2, 170 131 112 bytes

def f(C,t=1):i="#".join(C).find("#")+1;return([]<C)*(i<1or(i<t
and f([r[i:]for r in C],t-i))+(i>1)*f(C[1:],i-1))

A function, f, taking the obstacle course as a list of rows, and returning the number of essentially different paths.

Explanation

The basic concept is this: We choose a certain obstacle, o, such that there are no other obstacles in the box bounding o and the top-left corner.

+--+....
|..|....  
+--#<==== o
.....#..
.#......
........

We then consider the two sub-courses to the east and to the south of o. We only consider either of these sub-courses if o can actually be crossed from a direction that leads to them, that is, crossed from the north to get to the east, and crossed from the west to get to the south. We solve the problem for each of the selected sub-courses, and return the sum of the results. These numbers correspond to the number of essentially different paths when crossing o from the left and from the right, respectively, therefore the two resulting sets of paths are essentially different. Since there are no obstacles between the starting point and o, there is a path between the starting point and any entry point into each of these regions, and all such paths that lead to the same point are essentially similar, hence the above sum is the complete number of essentially different paths in the entire course.

                               A
_
........       ...|////      |....
........       ...|////      |....
...#....  -->  ...#////  -->  ....
.#....#.       .#..//#/       ..#.
........       ....////       ....

   |                           |
   v                           v
                  B
........       ___
........       .#....#.
___#....  -->  ........  -->   +
/#////#/       
////////       

Things are slightly complicated by the fact that the obstacle course alone doesn't convey all the information needed. For example, consider course B in the diagram above. Taken by itself, we can't determine whether each of the obstacles can be crossed from the north. If B were the input course, then, since all paths start at the top-left corner, neither obstacle could have been crossed from the north, but, since we can reach B from either side of the left obstacle when crossing o from the east, we should treat this obstacle as though it can be crossed from the north when solving the course; the same doesn't hold for the right obstacle, however, which can't be crossed from this direction.

We convery this extra information by specifying, along with the obstacle course, the number of characters along the first row, starting from the left, that the path can start at. In the diagram above, this is depcited as the solid line next to each course. While, technically, we also need to specify the corresponding number of characters along the first column that the path can start at, as in the case of sub-course A, in practice we always selected the highest obstacle, so this information is not required.

The actual selection of o is as follows: We pretend that each row, other than the last, is followed by an obstacle (i.e., has a # appended to it), and select the first obstacle in the resulting course, in reading order. For rows (other than the last) that had no obstacle originally, this effectively mean that we skip them (while noting that the path below may start at any character along the top row). Eventually, we end up with a course that has a single row with no obstacles, for which there is only one possible path.

Answer 2

Snails, 53 49 bytes

A^
\.+d!{.l\.+a3(.|~c!~}\.+r!(.u\.+e(.|~},\.,=~d~

For once, I did not have to use t, the dreaded teleport instruction. As a result, the test cases finish instantly instead of taking aeons.

Ungolfed:

A^
r\.+
{
    d\.+
    !{ r\.u \.+ a3 (.|~)}
    r\.+
    !{ d\.l \.+ a3 (.|~)}
},
d\.,
!(dr .)

The options A^ mean to start at the upper-left corner and count all matching paths. The main idea is to check a canonicity condition for the paths. I honestly did not expect it to work, but it nailed the test cases, so.... What it tries to check for is that, within the current path, the greediest route has been selected, i.e. going right as many times as possible, down as many times as possible, etc. without crossing over any obstacles. This is done by checking, after moving right 1 or more times and then down 1 or more times, that the next square (which must be to the right) could not have been reached by going right one more time in the previous rightward segment. The analogous condition is also checked after moving right and then down.

Answer 3

CJam, 85 84 82 81 80 79 bytes

qN/:Q,(Qz,(:R_T]2/e~e!{'#Qs@{\(\@>}%s-},{_}{(a\L{@+_@\-_{2$\f.=0fe=2&},}h;}w;],

Try it online. Or run the entire test suite.

The efficiency of this solution is probably quite horrible but it solves each test case within a few seconds.

Explanation

I'll have to add a full breakdown of the code later, but the algorithmic idea is this:

• Let the width and height of the grid be W and H, respectively.
• We generate all possible paths as the distinct permutations of W-1 copies of 0 and H-1 copies of W-1 (where 0 represents a horizontal step and W-1 a vertical step). We walk all of those paths by repeatedly taking the first element of the grid and then skipping step cells in reading order (where step is 0 or W-1). We discard all paths which contain a #.
• Then we repeatedly remove one group of similar paths (which will be all paths similar to the first of the remaining paths). Checking for similar paths gets a bit easier by relaxing the condition for them slightly: instead of checking whether one x has moved, we check whether the paths differ in exactly two places. If that is the case, those two places will have a vertical and horizontal move swapped. This causes the entire segment between those moves to be shifted diagonally by one cell. But if both of those paths are valid, shifting any part of the path by one cell diagonally cannot cross an obstacle, so they are similar. We still need to find the transitive closure, so we keep doing that until we find no more similar paths before moving on to the next group.
• Finally, we count the groups we've found, which we left at the bottom of the stack.