2015-day9.rkt

#lang racket
(require threading)

(define (get-input)
  (file->lines "day9.txt"))

(struct edge (from to dist) #:transparent)
(struct step (from to) #:transparent)

(define (parse-line str)
  (define dist (string->number (second (string-split str " = "))))
  (define from (first (string-split str)))
  (define to (third (string-split str)))
  (edge from to dist))

(define (build-lookup edges)

  (define (hash-set-edge lkp edg)
    (~> lkp
        (hash-set (step (edge-from edg) (edge-to edg)) (edge-dist edg))
        (hash-set (step (edge-to edg) (edge-from edg)) (edge-dist edg))))

  (define (lookup-rec edges lkp)
    (if (empty? edges)
        lkp
        (lookup-rec (cdr edges) (hash-set-edge lkp (car edges)))))

  (lookup-rec edges #hash()))

(define (find-cities edges)
  (define (city-rec edgs cities)
    (if (empty? edgs)
        (set->list cities)
        (city-rec (cdr edgs)
                  (~> cities
                      (set-add (edge-from (car edgs)))
                      (set-add (edge-to (car edgs)))))))
  (city-rec edges empty))

(define (build-permutations cities)
  (~> cities
      (in-permutations)
      (sequence->stream)))

(define (build-path pth)
  (define (path-rec pth res)
    (if (< (length pth) 2)
        res
        (path-rec (cdr pth) (cons (step (first pth) (second pth)) res))))
  (path-rec pth empty))

(define (path-len pth lkp)
  (define (len-rec pth lkp acc)
    (if (empty? pth)
        acc
        (len-rec (cdr pth) lkp (+ acc (hash-ref lkp (car pth))))))
  (len-rec (build-path pth) lkp 0))

(define (find-shortest edges)
  (define (search-rec perms lkp sub)
    (if (stream-empty? perms)
        (floor sub)
        (search-rec (stream-rest perms) lkp (min sub (path-len (stream-first perms) lkp)))))

  (search-rec (build-permutations (find-cities edges)) (build-lookup edges) +inf.0))

(define (find-longest edges)
  (define (search-rec perms lkp sup)
    (if (stream-empty? perms)
        sup
        (search-rec (stream-rest perms) lkp (max sup (path-len (stream-first perms) lkp)))))

  (search-rec (build-permutations (find-cities edges)) (build-lookup edges) 0))

(define (part1)
  (~>> (get-input)
       (map parse-line)
       (find-shortest)))

(define (part2)
  (~>> (get-input)
       (map parse-line)
       (find-longest)))

(module+ test
  (require rackunit)
  (require rackunit/text-ui)
  (define part-1
    (test-suite
     "Part 1"
     (check-equal? 1 1 "basic")
     (check-equal? (parse-line "Faerun to AlphaCentauri = 13") (edge "Faerun" "AlphaCentauri" 13) "Parse line")
     ))

  (define part-2
    (test-suite
     "Part 2"
     (check-equal? 1 1 "basic")
     ))

  (run-tests part-1)
  (run-tests part-2))