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 :- read(T), foreach(Case_num in 1..T, [R, C, N], ( initialize_table, abolish, read([R, C]), read(N), 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 rowsC- number of grid columnsUsed- 1 if a left or up move was already used, 0 otherwisePrev- direction of the previous stepX- current X coordinateY- current Y coordinateS- 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
Xis less than number of rowsR - 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[0], car[1])
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.