This is a Travelling Salesman Problem with 8 cities, a small enough number to brute-force. The input is in the form
|
1 2 3 4 5 6 7 8 |
Faerun to Norrath = 129 Faerun to Tristram = 58 Faerun to AlphaCentauri = 13 Faerun to Arbre = 24 Faerun to Snowdin = 60 Faerun to Tambi = 71 Faerun to Straylight = 67 ... |
No prizes for the sources of the city names. Again, the parser framework gets used, and we build up both a list of cities and a hash of city distances. We then use an algorithm from Knuth to permute the list (lexicographically ordered, but it doesn’t really matter) and just go through it until we find the shortest path. Part 2 asks for the longest path, which is a simple enough matter. Here’s the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
require "utils.ang" drop require "parse.ang" import [] !Cities :addifnotin |s,l:| ?s ?l in not if ?s ?l push then ; [%] !Distances :adddist |d,x,y:k| ?x "/" + ?y + !k ?d ?k ?Distances set; :getdist |x,y:k| ?x "/" + ?y + !k ?k ?Distances get dup isnone if drop ?y "/" + ?x + !k ?k ?Distances get then ; :getpathlen |lst:a| ?lst shift !a 0 ?lst each { ?a i getdist + i !a } ; # parser "[A-Za-z]+" regexparser !IdentParser "[0-9]+" regexparser !NumberParser "day9in" "r" io$open io$readfilestr <<"\\s+" regex$compile>> regex$split [?IdentParser,"to" strparser,?IdentParser, "=" strparser,?NumberParser] seq many ( @ dehash dehashlist each { i fst ?Cities addifnotin i third ?Cities addifnotin 4 i get toint i fst i third adddist } )@ # permutator, nicked from Knuth Vol 4A, section 7.2.1.2, Algorithm L (p.319): # lexicographic permutation generation. :g |i,a| ?i 0 <= if -1 else ?i 1- ?a get then; :s |i,a| ?i 0 > if ?i 1- ?a set then; :perm |f,a:j,l,n| ?a len !n { #L1 ?a ?f@ #L2 ?n 1- !j { ?j 0 = if stop then ?j ?a g ?j 1 + ?a g < ifleave ?j 1 - !j } #L3 ?n !l { ?j ?a g ?l ?a g < ifleave ?l 1 - !l } ?j ?a g ?l ?a g ?j ?a s ?l ?a s #L4 0 ?j ?a slice ?j -1 ?a slice reverse + !a } ; # get min distance 0!Min (|l:m| ?l clone getpathlen !m ?Best isnone ?m ?Min < or if ?l clone !Best ?m !Min then ) ?Cities perm ?Best util$show. ?Min. # get max distance 0!Max (|l:m| ?l clone getpathlen !m ?m ?Max > if ?l clone !Best ?m !Max then ) ?Cities perm ?Best util$show. ?Max. |