egison-3.5.0: sample/salesman.egi

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

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

(define $graph-data
  {
   ["Tokyo"     {              ["Shinjuku" 200] ["Shibuya" 200] ["Mitaka" 390] ["Kinshicho" 160] ["Kitasenju" 220]}]
   ["Shinjuku"  {["Tokyo" 200]                  ["Shibuya" 160] ["Mitaka" 220] ["Kinshicho" 220] ["Kitasenju" 310]}]
   ["Shibuya"   {["Tokyo" 200] ["Shinjuku" 160]                 ["Mitaka" 310] ["Kinshicho" 220] ["Kitasenju" 310]}]
   ["Mitaka"    {["Tokyo" 390] ["Shinjuku" 220] ["Shibuya" 310]                ["Kinshicho" 470] ["Kitasenju" 550]}]
   ["Kinshicho" {["Tokyo" 160] ["Shinjuku" 220] ["Shibuya" 220] ["Mitaka" 470]                   ["Kitasenju" 220]}]
   ["Kitasenju" {["Tokyo" 220] ["Shinjuku" 310] ["Shibuya" 310] ["Mitaka" 550] ["Kinshicho" 220]                  }]
   })

(define $trips ; List up all routes that visit each city exactly once and return to Tokyo
  (match-all graph-data graph
    [<cons [,"Tokyo" <cons [$s_1 $p_1] _>]
           (loop $i [2 5]
             <cons [,s_(- i 1) <cons [$s_i $p_i] _>]
                   ...>
             <cons [,s_5 <cons [(& ,"Tokyo" $s_6) $p_6] _>]
                   _>)>
     [(sum (map (lambda [$i] p_i) (between 1 6)))
      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))))]})))