Я хочу показать мое решение на Прологе задачи 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++). Большинство из них (если не все) используют ту или иную форму динамического программирования.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий