# Dynamic programming solution for Facebook Hacker Cup problem "AAAAAA" in B-Prolog

There are lots of material on how to solve puzzles and puzzle-like problems in Prolog (see Hakan Kjellerstrand's B-Prolog page, for example). But often the problems shown are either initially intended to be solved by hand (have small search space), or specifically tailored for logic programming paradigm.

I want to show my Prolog solution to a Facebook Hacker Cup problem, AAAAAA from the round 1 of 2014. The problem has relatively large search space and was intended to be solved by skilled algorithmists using conventional programming languages.

Here is a summary of the problem:

For every test case the input is a `N` × `M` grid of characters (`N` and `M` are up to 500), where '`.`' denotes an open cell, and '`#`' denotes a closed cell ("blocked with a car"). The goal is to construct a longest path ("queue of people") using only open cells from the top-left corner, such that every non-starting cell in the path lies right or down from the previous cell. One exception is allowed – it's possible to go left or up in one contiguous segment of the whole path. Every open cell can be used at most once in the path.

The output of a test case in the length of a longest path. There can be up to 20 test cases in a single test file.

Example input and output:

```5
5 5
.....
.....
.....
.....
.....
1 10
..........
5 5
...#.
...#.
...#.
...#.
.....
3 3
..#
#.#
...
3 8
........
#.#.#.#.
#.#.#.#.
```
```Case #1: 17
Case #2: 10
Case #3: 17
Case #4: 5
Case #5: 10
```

In the first example case there are no closed cells, and a longest path is:

```↓→↓.
↓↑↓..
↓↑↓..
↓↑↓..
→↑→→⊕
```

For the last test case the path is:

```→→→→→→→↓
#.#.#.#↓
#.#.#.#⊕
```

My solution uses a B-Prolog-specific "mode-directed tabling", which is a form of memoization. This is not a standard Prolog feature, so it will not work with other Prolog implementations (similar features exist in XSB and YAP).

The solution uses top-down dynamic programming. You don't have to know much about dynamic programming to understand the solution: the program just describes all possible ways to extend the queue and asks B-Prolog to find max value of the queue length.

This is the actual code I wrote and submitted during the competition:

```:- table queue(+, +, +, +, +, +, max).

queue(_R, _C, _, _, X, Y, 1)  :-
\+ car(X, Y).

% move down
queue(R, C, Used, Prev, X, Y, S) :-
X < R,
Prev \= up,
Xp1 is X + 1,
\+ car(Xp1, Y),
queue(R, C, Used, down, Xp1, Y, Snext),
S is 1 + Snext.

% move right
queue(R, C, Used, Prev, X, Y, S) :-
Y < C,
Prev \= left,
Yp1 is Y + 1,
\+ car(X, Yp1),
queue(R, C, Used, right, X, Yp1, Snext),
S is 1 + Snext.

% move up
queue(R, C, Used, Prev, X, Y, S) :-
X > 1,
(Used =:= 0 ; Prev == up),
Prev \= down,
Xm1 is X - 1,
\+ car(Xm1, Y),
queue(R, C, 1, up, Xm1, Y, Snext),
S is 1 + Snext.

% move left
queue(R, C, Used, Prev, X, Y, S) :-
Y > 1,
(Used =:= 0 ; Prev == left),
Prev \= right,
Ym1 is Y - 1,
\+ car(X, Ym1),
queue(R, C, 1, left, X, Ym1, Snext),
S is 1 + Snext.

do_case(Case_num, R, C) :-
queue(R, C, 0, right, 1, 1, S),
format("Case #~w: ~w\n", [Case_num, S]).

main :-
foreach(Case_num in 1..T, [R, C, N], (
initialize_table, abolish,
assert(car(-1, -1)), % dummy
foreach(_I in 1..N, [X, Y], (read([X, Y]), assert(car(X, Y)))),
do_case(Case_num, R, C)
)).
```

The first line is a tabling mode declaration for my `queue` predicate: the first 6 parameters are input parameters, and the last parameter is an output, which needs to be maximized if several different outputs are possible for some input.

`queue` parameters are:

• `R` - number of grid rows
• `C` - number of grid columns
• `Used` - 1 if a left or up move was already used, 0 otherwise
• `Prev` - direction of the previous step
• `X` - current X coordinate
• `Y` - current Y coordinate
• `S` - length of a path from (`X`, `Y`).

The first clause of the `queue` predicate says that if there is no a car in a cell (`X`, `Y`), then it's possible to have a queue of length 1 starting in this cell (at least).

Next 4 clauses are for the 4 possible ways to extend a queue: go down, right, up, or left.

To go down, the following conditions must be met according to the clause:

• current cell row `X` is less than number of rows `R`
• previous step was not "up"
• there is no car in the position (`X+1`, `Y`)
• the length of the resulting queue is 1 + length of a queue starting from the cell (`X+1`, `Y`).

The clause to go right is very similar.

The clauses to go up and left have extra condition that a left or up move was not used yet, or we continue the sequence of left or up moves:

```(Used =:= 0 ; Prev == up)
```

`do_case` uses `queue` to find the length of a longest queue from the top-left corner. Thanks to tabling, subproblem answers are only computed once.

`main` reads number of test cases, and for each test case reads `R`, `C`, and positions of cars in a Prolog-friendly format; for each car a fact is asserted in the Prolog database to be used by `queue` clauses.

I could have worked with the problem input directly in B-Prolog, but I decided that it's much easier to preprocess the input with a Python script (basically, output a two-element list of coordinates for each car in the input; also end each line with a period):

```T = int(raw_input())
print "%d." % T
for case_num in range(1, T + 1):
R, C = map(int, raw_input().split())
print "[%d, %d]." % (R, C)
cars = []
for i in range(R):
row = raw_input().strip()
for j in range(C):
if row[j] == '#':
cars.append([i + 1, j + 1])
print "%d." % len(cars)
for car in cars:
print "[%d, %d]." % (car, car)
```

Here is the command to run the whole thing (`tail` excludes B-Prolog version info from the output):

```cat in-file | python preprocess.py | bp -g "cl('AAAAAA.pl'),main,halt" -l | tail -n +7 > out-file
```

You can download other participants' solutions for the problem (mostly in Java or C++) from the scoreboard and compare them with my B-Prolog solution. Most of them, if not all, use some form of dynamic programming.

BTW, Facebook Hacker Cup 2015 starts in a month.