



#lang scribble/lp2





@(require scribble/manual aocracket/helper)










@aoctitle[13]










@defmodule[aocracket/day13]










@link["http://adventofcode.com/day/13"]{The puzzle}. Our @linkrp["day13input.txt"]{input} is a list of descriptions of ``happiness units'' that would be gained or lost among eight people sitting next to each other at a dinner table.










@chunk[<day13>





<day13setup>





<day13q1>





<day13q2>





<day13test>]










@isection{What's the optimal happiness score for a seating arrangement of eight?}










This is a lot like @secref{Day_9}, where we had to compute the optimal path between cities. In that puzzle, the distance between city A and city B was a single number. In this case, the ``happiness score'' between person A and person B is the sum of two numbers — A's happiness being next to B, and B's happiness being next to A. (Unlike distances, happiness scores can be negative.)










Also, whereas a path between cities had a start and end, a seating arrangement is circular. So if we model a seating arrangement as a list of people, we have to compute the happiness between each duo of people, but also between the last and first, to capture the circularity of the arrangement.










Those wrinkles noted, we'll proceed as we did in @secref{Day_9}. We'll parse the input data and put the happiness scores into a hash table — the keys will be of the form @racket[(list name1 name2)] and the values will be the happiness scores for that duo, in that order. Then we'll loop through all possible seating arrangements with @iracket[inpermutations] and see what the best score is.




















@chunk[<day13setup>





(require racket rackunit)





(provide (alldefinedout))










(define happinessscores (makehash))










(define (parsehappinessscore ln)





(define result





(regexpmatch #px"^(.*?) would (gainlose) (\\d+) happiness units by sitting next to (.*?)\\.$" (stringdowncase ln)))





(when result





(matchdefine (list _ name1 op amount name2) result)





(hashset! happinessscores (list name1 name2)





((if (equal? op "gain") + ) (string>number amount)))))










(define (calculatehappiness tablearrangement)





(define tablearrangementrotatedoneplace





(append (drop tablearrangement 1) (take tablearrangement 1)))





(define clockwiseduos





(map list tablearrangement tablearrangementrotatedoneplace))





(define counterclockwiseduos (map reverse clockwiseduos))





(define allduos (append clockwiseduos counterclockwiseduos))





(for/sum ([duo (inlist allduos)])





(hashref happinessscores duo)))










]















@isubsection{Optimizing @tt{inpermutations}}










I'm in a mathjock mood, so let's make a performance optimization. It's unnecessary for this problem, but when we use @iracket[inpermutations] — which grows at factorial speed — we should ask how we might prune the options.










Notice that because our seating arrangement is circular, our permutations will include a lot of ``rotationally equivalent'' arrangements — e.g., @racket['(A B C ...)] is the same as @racket['(B C ... A)], @racket['(C ... A B)], etc. If we have @racket[_n] elements, each distinct arrangement will have @racket[_n] rotationally equivalent arrangements. We can save time by only checking one of each set.










How? By only looking at arrangements starting with a particular name. Doesn't matter which. This will work because every name has to appear in every arrangement. To do this, we could generate all the permutations and use a @racket[#:when] clause to select the ones we want. But it's even more efficient to only permute @racket[(sub1 _n)] names, and then @racket[cons] our firstposition name onto each partial arrangement, which will produce the same set of arrangements. Thus we only have to generate and score @racket[(/ 1 _n)] of the original permutations.










@chunk[<day13q1>










(define (q1 inputstr)





(foreach parsehappinessscore (stringsplit inputstr "\n"))





(define names





(removeduplicates (flatten (hashkeys happinessscores))))





(define tablearrangementscores





(for/list ([partialtablearrangement (inpermutations (cdr names))])





(define tablearrangement (cons (car names) partialtablearrangement))





(calculatehappiness tablearrangement)))





(apply max tablearrangementscores))]




















@section{What's the optimal happiness score, including ourself in the seating?}










We can reuse our hash table of @racket[happinessscores], but we have to update it with scores for ourself seated next to every other person, which in every case is @racket[0]. (The meaning of @racket[(inlist (list list (compose1 reverse list)))] is a small puzzle I leave for you.) Then we find the optimal score the same way.










@chunk[<day13q2>










(define (q2 inputstr)





(define names





(removeduplicates (flatten (hashkeys happinessscores))))










(for* ([name (inlist names)]





[duoproc (inlist (list list (compose1 reverse list)))])





(hashset! happinessscores (duoproc "me" name) 0))










(define tablearrangementscores





(for/list ([partialtablearrangement (inpermutations names)])





(define tablearrangement (cons "me" partialtablearrangement))





(calculatehappiness tablearrangement)))





(apply max tablearrangementscores))










]















@section{Testing Day 13}










@chunk[<day13test>





(module+ test





(define inputstr (file>string "day13input.txt"))





(checkequal? (q1 inputstr) 709)





(checkequal? (q2 inputstr) 668))]










