Solving the “AAAAAA” problem with Facebook Hacker Cup using dynamic programming on B-Prolog

There is a lot of material on solving complicated puzzles in Prolog (for example, Hakan Kjellerstrand page on B-Prolog ). However, tasks are often cited that were either created for the solution manually (they have a small search space), or they were initially focused on the solution using logic programming.

I want to show my solution on the Prologue of the AAAAAA problem from the first round of the Facebook Hacker Cup 2014. The task has a fairly large search space and is created with an eye to the solution by experienced sports programmers in common programming languages.

The essence of the task:
For each test, an N × M grid ( N and M up to 500) is applied to the input. Each cell of the grid contains either ' . '- open cell, or' # '- closed cell ("blocked by car"). The goal is to construct a path of maximum length (“a queue of people”) along open cells from the upper left corner so that every cell of the path (except the initial one) is to the right or below from the previous one.

One exception is allowed - you can move left or up one consecutive section of the path. Each open cell can be used no more than once.
')
The output of the program for each test is the length of the longest path. Up to 20 tests can be in one file.

Examples of input and output data:

 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, there are no closed cells. One of the possible ways of maximum length:

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

The longest way for the last example:

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

My solution uses a B-Prolog- specific “mode-directed tabling” tabulation, which is a form of memoization . Tabulation is not a standard Prolog feature, so the program will not work in other Prolog systems (there are similar features in XSB and YAP ).

The solution uses the top-down dynamic programming method. Understanding the solution does not require special knowledge in dynamic programming: the program simply describes all possible ways to continue the queue and asks B-Prolog to find the maximum length of this queue.

Here is the code that I wrote and sent 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 sets the tabulation mode for the predicate queue : the first 6 parameters are input, and the last is output, and it needs to be maximized if several different output values ​​are possible for any input parameters.

Predicate parameters queue :

• R - the number of rows in the grid
  
• C - the number of columns in the grid
  
• Used - 1 if the movement to the left or up has already been used, otherwise 0
  
• Prev - direction in the previous step
  
• X - current X-coordinate
  
• Y - current Y-coordinate
  
• S is the path length from ( X , Y ).
  

The first rule of the predicate queue states that if a cell ( X , Y ) is not blocked by a car, then a queue of length 1 (at least) with a start in that cell is possible.

Next come 4 rules describing 4 possible ways to continue the queue: down, right, up, left.

Rule to continue down:

• the current row number X less than the number of rows in the R grid
  
• previous step was not up ("up")
  
• the cell ( X+1 , Y ) is not blocked by the car
  
• the length of the resulting queue will be 1 plus the length of the queue starting in the cell ( X+1 , Y ).
  

The rule to continue to the right is similar to the rule to continue down.

The rules for continuing up and to the left include an additional condition that either the movement to the left or up has not yet been used, or we continue the sequential movement to the left / up:
(Used =:= 0 ; Prev == up) .

do_case uses queue to find the maximum queue length starting in the upper left corner. Thanks to tabulation, the results for subtasks are calculated only once.

main reads the number of tests, and for each test it reads the R , C and positions of the cars in a format convenient for Prolog; for each vehicle, a fact is added to the Prolog fact base for subsequent use by the queue predicate rules.

It would be possible to work with the input data of the problem immediately in B-Prolog, but I decided
it will be much easier to pre-process them using a python script
(for each car a two-element list of coordinates is displayed, and each line ends with a full stop):

 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]) 

The command to run ( tail removes the B-Prolog version message from the results):

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

For comparison with the above solution, B-Prolog can be downloaded from the page of the results table of the decisions of other participants (mainly in Java or C ++). Most of them (if not all) use some form of dynamic programming.