[Перевод] Решение задачи «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®: row = raw_input ().strip () for j in range©: 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++). Большинство из них (если не все) используют ту или иную форму динамического программирования.
