13 Day 13
| (require aoc-racket/day13) | package: aoc-racket |
The puzzle. Our 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.
13.1 What’s the optimal happiness score for a seating arrangement of eight?
This is a lot like 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 Day 9. We’ll parse the input data and put the happiness scores into a hash table — the keys will be of the form (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 in-permutations and see what the best score is.
(require racket rackunit) (provide (all-defined-out)) (define happiness-scores (make-hash)) (define (parse-happiness-score ln) (define result (regexp-match #px"^(.*?) would (gain|lose) (\\d+) happiness units by sitting next to (.*?)\\.$" (string-downcase ln))) (when result (match-define (list _ name1 op amount name2) result) (hash-set! happiness-scores (list name1 name2) ((if (equal? op "gain") + -) (string->number amount))))) (define (calculate-happiness table-arrangement) (define table-arrangement-rotated-one-place (append (drop table-arrangement 1) (take table-arrangement 1))) (define clockwise-duos (map list table-arrangement table-arrangement-rotated-one-place)) (define counterclockwise-duos (map reverse clockwise-duos)) (define all-duos (append clockwise-duos counterclockwise-duos)) (for/sum ([duo (in-list all-duos)]) (hash-ref happiness-scores duo)))
13.1.1 Optimizing in-permutations
I’m in a math-jock mood, so let’s make a performance optimization. It’s unnecessary for this problem, but when we use in-permutations — 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., '(A B C ...) is the same as '(B C ... A), '(C ... A B), etc. If we have n elements, each distinct arrangement will have 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 #:when clause to select the ones we want. But it’s even more efficient to only permute (sub1 n) names, and then cons our first-position name onto each partial arrangement, which will produce the same set of arrangements. Thus we only have to generate and score (/ 1 n) of the original permutations.
(define (q1 input-str) (for-each parse-happiness-score (string-split input-str "\n")) (define names (remove-duplicates (flatten (hash-keys happiness-scores)))) (define table-arrangement-scores (for/list ([partial-table-arrangement (in-permutations (cdr names))]) (define table-arrangement (cons (car names) partial-table-arrangement)) (calculate-happiness table-arrangement))) (apply max table-arrangement-scores))
13.2 What’s the optimal happiness score, including ourself in the seating?
We can reuse our hash table of happiness-scores, but we have to update it with scores for ourself seated next to every other person, which in every case is 0. (The meaning of (in-list (list list (compose1 reverse list))) is a small puzzle I leave for you.) Then we find the optimal score the same way.
(define (q2 input-str) (define names (remove-duplicates (flatten (hash-keys happiness-scores)))) (for* ([name (in-list names)] [duo-proc (in-list (list list (compose1 reverse list)))]) (hash-set! happiness-scores (duo-proc "me" name) 0)) (define table-arrangement-scores (for/list ([partial-table-arrangement (in-permutations names)]) (define table-arrangement (cons "me" partial-table-arrangement)) (calculate-happiness table-arrangement))) (apply max table-arrangement-scores))
13.3 Testing Day 13
(module+ test (define input-str (file->string "day13-input.txt")) (check-equal? (q1 input-str) 709) (check-equal? (q2 input-str) 668))