Решение задачи «AAAAAA» с Facebook Hacker Cup методом динамического программирования на B-Prolog / Хабр

Есть много материала по решению запутанных задачек на Прологе (например, страница Hakan Kjellerstrand о B-Prolog). Однако часто приводятся задачи, которые либо создавались для решения вручную (имеют маленькое пространство поиска), либо изначально ориентированы на решение при помощи логического программирования.

Я хочу показать мое решение на Прологе задачи AAAAAA с первого раунда Facebook Hacker Cup 2014. Задача имеет достаточно большое пространство поиска и создана с прицелом на решение опытными спортивными программистами на распространенных языках программирования.

Суть задачи:
Для каждого теста на вход подается сетка размером N × M (N и M до 500). В каждой клетке сетки содержится либо '.' – открытая клетка, либо '#' – закрытая клетка («заблокированная автомобилем»). Цель – сконструировать путь максимальной длины («очередь людей») по открытым клеткам от левого верхнего угла так, что каждая клетка пути (кроме начальной) находится справа или снизу от предыдущей.

Допускается одно исключение – можно двигаться влево или вверх один последовательный участок пути. Каждая открытая клетка может использоваться не более одного раза.

Вывод программы для каждого теста – длина самого длинного пути. В одном файле может быть до 20 тестов.

Примеры входных и выходных данных:

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

В первом примере закрытых клеток нет. Один из возможных путей максимальной длины:

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

Самый длинный путь для последнего примера:

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

Мое решение использует специфическое для B-Prolog «табулирование, направляемое режимами» («mode-directed tabling»), которое является формой мемоизации. Табулирование не является стандартной возможностью Пролога, так что программа не будет работать в других Пролог-системах (похожие возможности есть в XSB и YAP).

В решении используется метод динамического программирования «сверху вниз». Для понимания решения не требуется особых познаний в динамическом программировании: программа просто описывает все возможные способы продолжения очереди и просит B-Prolog найти максимальное значение длины этой очереди.

Вот код, который я написал и отправил во время соревнования:

:- 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)
        )).

Первая строка устанавливает режим табулирования для предиката queue: первые 6 параметров являются входными, а последний – выходным, и его требуется максимизировать в случае, если для каких-либо входных параметров возможно несколько разных значений выходного.

Параметры предиката queue:

R – число строк в сетке
C – число столбцов в сетке
Used – 1, если движение влево или вверх уже использовалось, иначе 0
Prev – направление на предыдущем шаге
X – текущая X-координата
Y – текущая Y-координата
S – длина пути от (X, Y).

Первое правило предиката queue гласит, что если клетка (X, Y) не заблокирована автомобилем, то возможна очередь длины 1 (как минимум) с началом в этой клетке.

Далее идут 4 правила, описывающие 4 возможных способа продолжения очереди: вниз, вправо, вверх, влево.

Правило для продолжения вниз:

номер текущей строки X меньше числа строк в сетке R
предыдущий шаг не был вверх («up»)
клетка (X+1, Y) не заблокирована автомобилем
длина получившейся очереди будет 1 плюс длина очереди, начинающейся в клетке (X+1, Y).

Правило для продолжения вправо аналогично правилу для продолжения вниз.

Правила для продолжения вверх и влево включают дополнительное условие, что либо движение влево или вверх еще не использовалось, либо мы продолжаем последовательное движение влево/вверх:
(Used =:= 0 ; Prev == up).

do_case использует queue для нахождения максимальной длины очереди, начинающейся в левом верхнем углу. Благодаря табулированию результаты для подзадач вычисляются только один раз.

main считывает количество тестов, и для каждого теста считывает R, C и позиции автомобилей в удобном для Пролога формате; для каждого автомобиля в базу фактов Пролога добавляется факт для последующего использования правилами предиката queue.

Можно было бы работать с входными данными задачи сразу в B-Prolog, но я решил,
что будет гораздо проще предварительно обработать их при помощи скрипта на Python
(для каждого автомобиля выводится двухэлементный список координат, и каждая строка заканчивается точкой):

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

Команда для запуска (tail убирает сообщение о версии B-Prolog из результатов):

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

Для сравнения с приведенным решением на B-Prolog можно скачать со страницы таблицы результатов решения других участников (в основном на Java или C++). Большинство из них (если не все) используют ту или иную форму динамического программирования.