Tuesday, December 8, 2015

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.

Followers

Contributors