;;;
;;; Travelling Salesman Problem
;;;

(define $station string)
(define $price   integer)
(define $graph   (multiset [station (multiset [station price])]))

(define $graph-data
  {["Berlin"    {              ["St. Louis" 14] ["Oxford"  2] ["Nara" 14] ["Vancouver" 13]}]
   ["St. Louis" {["Berlin" 14]                  ["Oxford" 12] ["Nara" 18] ["Vancouver"  6]}]
   ["Oxford"    {["Berlin"  2] ["St. Louis" 12]               ["Nara" 15] ["Vancouver" 10]}]
   ["Nara"      {["Berlin" 14] ["St. Louis" 18] ["Oxford" 15]             ["Vancouver" 12]}]
   ["Vancouver" {["Berlin" 13] ["St. Louis"  6] ["Oxford" 10] ["Nara" 12]                 }]})


(define $trips ; List up all routes that visit each city exactly once and return to Tokyo
  (match-all graph-data graph
    [<cons [,"Berlin" <cons [$s_1 $p_1] _>]
           (loop $i [2 4]
             <cons [,s_(- i 1) <cons [$s_i $p_i] _>]
                   ...>
             <cons [,s_4 <cons [(& ,"Berlin" $s_5) $p_5] _>]
                   _>)>
     [(sum (map (lambda [$i] p_i) (between 1 5)))
      s]]))

(define $main
  (lambda [$args]
    (do {[(print "Route list:")]
         [(each (compose show print) trips)]
         [(write "Lowest price:")]
         [(print (show (min (map (lambda [$x $y] x) trips))))]})))