Advent of code, Day 9

Задача: http://adventofcode.com/day/9

Ну, думаю, если не для этой задачки был придуман Prolog, то для чего же ещё? К счастью, сейчас не нужно ставить на компьютер интерпретаторы и компиляторы, можно писать код прямо в браузере.

Моё решение ниже, наверное, насмешит опытных прологеров, но я уже 10 лет не брал его в руки, поэтому как получилось, так и получилось.

Собственно решение.

Для начала разберёмся с исходными данными. Prolog понимает данные в виде фактов, поэтому подготовим их ему в следующем виде: пункт А, пункт Б и расстояние между этими пунктами:

d(faerun, tristram, 65).
d(faerun, tambi, 129).
d(faerun, norrath, 144).
d(faerun, snowdin, 71).
d(faerun, straylight, 137).
d(faerun, alphacentauri, 3).
d(faerun, arbre, 149).
d(tristram, tambi, 63).
d(tristram, norrath, 4).
d(tristram, snowdin, 105).
d(tristram, straylight, 125).
d(tristram, alphacentauri, 55).
d(tristram, arbre, 14).
d(tambi, norrath, 68).
d(tambi, snowdin, 52).
d(tambi, straylight, 65).
d(tambi, alphacentauri, 22).
d(tambi, arbre, 143).
d(norrath, snowdin, 8).
d(norrath, straylight, 23).
d(norrath, alphacentauri, 136).
d(norrath, arbre, 115).
d(snowdin, straylight, 101).
d(snowdin, alphacentauri, 84).
d(snowdin, arbre, 96).
d(straylight, alphacentauri, 107).
d(straylight, arbre, 14).
d(alphacentauri, arbre, 46).

Важный момент: расстояние от пункта A до пункта B равно и расстоянию от пункта B до пункта A. Зададим это в правилах:

f(X,Y,Z) :- d(X,Y,Z).
f(X,Y,Z) :- d(Y,X,Z).

По условиям задачи Санта-Клаус посещает все пункты не более одного раза. Значит, мы просто берём все пункты, которые он должен посетить, объединяем их в единый набор и берём все возможные перестановки этого набора (тут явно чувствуется влияние опыта процедурного программирования, но именно в таких категориях мне в тот момент думалось):

locations(List) :-
setof(X, (Y,Z)^f(X,Y,Z), Locations),
permutation(Locations,List).

Что такое длина всего пути A, B, …, Z? Она складывается из длины пути между пунктом A и пунктом B плюс длина пути B…Z, которая вычисляется рекурсивно:

route_length([],0).
route_length([_],0).
route_length([X,Y|Tail],Distance) :-
f(X,Y,D1),
route_length([Y|Tail],D2),
Distance is D1 + D2.

Для простоты решения этой задачи я ввёл ещё одно правило, с одним аргументом. Перебирает все возможные комбинации и вычисляет их длину.

distance(Distance) :-
locations(Z),
route_length(Z,Distance).

Ну и совсем просто уже вычислить минимальное и максимальное расстояние:

shortest_distance(Distance) :-
aggregate(min(D, _), distance(D), min(Distance, _)).

longest_distance(Distance) :-
aggregate(max(D, _), distance(D), max(Distance, _)).

Для запуска программы на Prolog важно ещё правильно сформулировать к ней вопрос. Но тут тривиально:

?- shortest_distance(X),longest_distance(Y).

Ответ:

X = 117,
Y = 909

0.493 seconds cpu time

Что касается решений к прошедшим дням Advent of code, то они в большинстве своём не требуют умственного напряжения, слишком детские, поэтому вряд ли это кому-то интересно.

В основном, я использую Groovy для того, чтобы быстро накропать решение (хотя есть и такие задачи, которые решаются в Notepad++ без программирования). Но 8-й день поколебал мою уверенность в правильном выборе языка, поскольку в Groovy и Java экранирование символов через \x не существует, а исходные данные сплошь кишели ими, и на их присутствии завязан подсчёт символов. Элегантное решение не вырисовывалось. Ситуацию усугублял издевательский список языков, которыми предлагалось решать задачу: C, JavaScript и PHP. Полный отстой! На Perl было бы слишком просто решить, но стало так обидно за Groovy… После небольших манипуляций с исходными данными в том же Notepad++, Groovy всё-таки справился.

Запись опубликована в рубрике Uncategorized с метками , . Добавьте в закладки постоянную ссылку.