You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
80 lines
3.3 KiB
80 lines
3.3 KiB
#lang scribble/lp2


@(require scribble/manual aocracket/helper)




@aoctitle[9]




@defmodule[aocracket/day09]




@link["http://adventofcode.com/day/9"]{The puzzle}. Our @linkrp["day09input.txt"]{input} consists of a list of distances between fictional cities, e.g., @italic{AlphaCentauri to Straylight = 133}.




@chunk[<day09>


<day09setup>


<day09q1>


<day09q2>


<day09test>]




@isection{What's the shortest route that visits all the cities?}




This puzzle is a version of the famous @link["https://simple.wikipedia.org/wiki/Travelling_salesman_problem"]{travelingsalesman problem}. The problem is famous because there's no reasonable algorithm to solve it for arbitrarily large sets of cities. This version, however, has only eight cities. So it is possible (and easiest) to simply try all the options and see which is shortest.




The solution has two parts. First, we'll parse our input data and put the distances into a mutable hash table. One small wrinkle — the distance between city A and city B is the same whether our path takes us from A to B or B to A. So the keys for our hash will be of the form @racket[(list citya cityb)], with the cities always in alphabetical order.




In the second part, we'll loop through every possible path between the cities with @iracket[inpermutations]. We'll split each path into pairs of cities, look up each distance between pairs, and sum them. This will give us a list of distances, and we can find the smallest with @iracket[min].




@marginnote{The reason the travelingsaleman problem is generally difficult is that the number of permutations of @racket[_n] cities is @racket[(factorial (sub1 _n))], which gets very large, very quickly.}




@chunk[<day09setup>


(require racket rackunit)


(provide (alldefinedout))




(define distances (makehash))




(define (str>hash ln)


(matchdefine (list _ here there dist)


(regexpmatch #px"^(\\w+) to (\\w+) = (\\d+)" ln))


(define key (places>key here there))


(hashset! distances key (string>number dist)))




(define (places>key here there)


(sort (list (stringdowncase here) (stringdowncase there)) string<?))




(define (calculateroutedistances)


(define (pairify xs)


(map list (dropright xs 1) (drop xs 1)))


(define (distance here there)


(hashref distances (places>key here there) +inf.0))




(define cities (removeduplicates (append* (hashkeys distances))))


(for/list ([route (inpermutations cities)])


(for/sum ([pair (inlist (pairify route))])


(apply distance pair))))


]




@chunk[<day09q1>






(define (q1 strs)


(foreach str>hash strs)


(apply min (calculateroutedistances)))]








@isection{What's the longest route?}




Exactly the same, except we look for the @iracket[max] value among the distances rather than the @racket[min].




@chunk[<day09q2>




(define (q2 strs)


(apply max (calculateroutedistances))) ]






@section{Testing Day 9}




@chunk[<day09test>


(module+ test


(define inputstrs (file>lines "day09input.txt"))


(checkequal? (q1 inputstrs) 251)


(checkequal? (q2 inputstrs) 898))]






