Advent of Code 2015, Day 9

The Day 9 Puzzle of the 2015 Advent of Code asks for the length of the shortest and longest hamiltonian path on a graph. The vertices are cities and the edges between adjacent cities are labelled with the distance between the cities.

Here's a solution ts.lp in AnsProlog using the Potassco ASP toolkit:

% The distance relation is symmetric.
dist(B, A, N) :- dist(A, B, N).

% Two cities are "adjacent" if there is a defined distance between them.
adjacent(A, B) :- dist(A, B, _).

% A city exists if it has a distance defined to it from somewhere.
city(A) :- adjacent(A, _).

% Assign a city to each stop on the path from 1..n.
1 { path(N, C): city(C) } 1 :- N = 1..n.

% No city can occur twice in the path.
:- path(N, C), path(M, C), N != M.

% There must be a defined distance between successive cities on the path.
:- path(N, C), path(N+1, D), not adjacent(C, D).

% Minimize the sum of distances between successive cities in the path.
#minimize { X, N : path(N, C), path(N+1, D), dist(C,D,X), N = 1..n }.
#show path/2.

It requires the following data file city.lp as input:

dist(faerun, norrath, 129).
dist(faerun, tristram, 58).
dist(faerun, alphacentauri, 13).
dist(faerun, arbre, 24).
dist(faerun, snowdin, 60).
dist(faerun, tambi, 71).
dist(faerun, straylight, 67).
dist(norrath, tristram, 142).
dist(norrath, alphacentauri, 15).
dist(norrath, arbre, 135).
dist(norrath, snowdin, 75).
dist(norrath, tambi, 82).
dist(norrath, straylight, 54).
dist(tristram, alphacentauri, 118).
dist(tristram, arbre, 122).
dist(tristram, snowdin, 103).
dist(tristram, tambi, 49).
dist(tristram, straylight, 97).
dist(alphacentauri, arbre, 116).
dist(alphacentauri, snowdin, 12).
dist(alphacentauri, tambi, 18).
dist(alphacentauri, straylight, 91).
dist(arbre, snowdin, 129).
dist(arbre, tambi, 53).
dist(arbre, straylight, 40).
dist(snowdin, tambi, 15).
dist(snowdin, straylight, 99).
dist(tambi, straylight, 70).
city(alphacentauri;arbre;faerun;norrath;snowdin;straylight;tambi;tristram).
#const n = 8.

Here's the output from running it:

$ clingo city.lp ts.lp
clingo version 4.4.0
Reading from city.lp ...
Solving...
Answer: 1
path(1,faerun) path(3,norrath) path(8,tristram) path(2,alphacentauri) path(6,arbre) path(5,snowdin) path(4,tambi) path(7,straylight)
Optimization: 391
Answer: 2
path(8,faerun) path(3,norrath) path(5,tristram) path(2,alphacentauri) path(6,arbre) path(1,snowdin) path(4,tambi) path(7,straylight)
Optimization: 387
Answer: 3
path(5,faerun) path(3,norrath) path(8,tristram) path(2,alphacentauri) path(6,arbre) path(1,snowdin) path(4,tambi) path(7,straylight)
Optimization: 341
Answer: 4
path(5,faerun) path(1,norrath) path(6,tristram) path(2,alphacentauri) path(8,arbre) path(3,snowdin) path(4,tambi) path(7,straylight)
Optimization: 308
Answer: 5
path(5,faerun) path(1,norrath) path(8,tristram) path(2,alphacentauri) path(6,arbre) path(3,snowdin) path(4,tambi) path(7,straylight)
Optimization: 274
Answer: 6
path(7,faerun) path(5,norrath) path(1,tristram) path(6,alphacentauri) path(8,arbre) path(3,snowdin) path(2,tambi) path(4,straylight)
Optimization: 269
Answer: 7
path(7,faerun) path(5,norrath) path(8,tristram) path(6,alphacentauri) path(3,arbre) path(1,snowdin) path(2,tambi) path(4,straylight)
Optimization: 248
Answer: 8
path(2,faerun) path(5,norrath) path(1,tristram) path(6,alphacentauri) path(3,arbre) path(7,snowdin) path(8,tambi) path(4,straylight)
Optimization: 218
Answer: 9
path(5,faerun) path(8,norrath) path(1,tristram) path(4,alphacentauri) path(6,arbre) path(3,snowdin) path(2,tambi) path(7,straylight)
Optimization: 207
OPTIMUM FOUND

Models       : 9     
  Optimum    : yes
Optimization : 207
Calls        : 1
Time         : 0.050s (Solving: 0.04s 1st Model: 0.00s Unsat: 0.03s)
CPU Time     : 0.040s

So the shortest path is from Faerun-Norrath-Tristram-AlphaCentauri-Arbre-Snowdin-Tambi-Straylight with a length of 207.

Changing #minimize to #maximize in ts.lp yields a longest path of Norrath-Tristram-AlphaCentauri-Arbre-Snowdin-Tambi-Straylight, with a length of 804.