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.
116 lines
5.9 KiB
116 lines
5.9 KiB
#lang scribble/lp2


@(require scribble/manual aocracket/helper)




@aoctitle[24]




@defmodule[aocracket/day24]




@link["http://adventofcode.com/day/24"]{The puzzle}. Our @linkrp["day24input.txt"]{input} is a list of weights of certain packages.






@chunk[<day24>


<day24setup>


<day24q1>


<day24q2>


<day24test>]




@isection{What's the score of the optimal group of packages, when divided into three groups?}




We need to arrange our packages into three groups of equal weight. There are multiple ways to do this, of course. According to the puzzle, the optimal arrangement is the one that results in a group with the fewest number of packages. If multiple arrangements yield an equally small group, then the winner is the one with the lowest ``quantum entanglement'' score, which is defined as the product of the weights.




This puzzle brings together elements we've seen before. Each group in a valid arrangement needs to have equal weight, which is the total weight divided by 3. Rather than immediately trying to find valid threegroup arrangements, we can start with single groups of the right weight, sorted by our scoring criteria, and find the first one that's part of a valid solution.




In principle, we could reuse the @racket[powerset] function we made for @secref{Day_17} to generate all possible groups, and then @racket[filter] for the groups that are the correct weight. But in truth, we got lucky on @secref{Day_17}. There were only 20 elements, so our power set contained @racket[(expt 2 20)] (about a million) options, which only takes a few seconds to search. This time, we have 28 elements, thus 256 times as many options, which would require 10–15 minutes of searching.




To be more efficient, we'll use @iracket[for*/first] to alternate between generating lists of possible groups, and then testing them. We'll @iracket[sort] these lists by ``quantum entanglement'' so we know we're testing groups from best to worst (similar to what we did in @secref{Day_21} with equipment cost).




After that, we just need to write a function that will test whether a given group is part of a valid solution. The first group that has a solution is our winner. Our @racket[hassolution?] function works by removing the test group from the set of all packages, and seeing if there is another group within that has the same weight. (We don't have to check the third group — if the first two groups are the same weight, then the third one is too.)






@chunk[<day24setup>


(require racket rackunit)


(provide (alldefinedout))




(define (groups packages len goalweight)


(cond


[(= len 0) empty]


[(= len 1) (map list (filter (curry = goalweight) packages))]


[else


(append*


(for/list ([x (inlist packages)])


(define laterpackages (cdr (member x packages)))


(appendmap (λ (ss) (define newgroup (cons x ss))


(if (= goalweight (weight newgroup))


(list newgroup)


empty))


(groups laterpackages (sub1 len) ( goalweight x)))))]))




(define (weight group) (apply + group))




(define (quantumentanglement group) (apply * group))




(define (removegroup group packages)


(filter (λ (p) (not (member p group))) packages))




(define (hassolution? group packages)


(define targetweight (weight group))


(define remainingpackages (removegroup group packages))


(for/first ([len (inrange (length remainingpackages))]


#:when (not (empty?


(groups remainingpackages len targetweight))))


#t))




]








@chunk[<day24q1>




(define (findthreegroupsolution allpackages targetweight)


(for*/first ([len (inrange (length allpackages))]


[group (inlist


(sort


(groups allpackages len targetweight)


#:key quantumentanglement <))]


#:when (hassolution? group allpackages))


(quantumentanglement group)))




(define (q1 inputstr)


(define allpackages (map string>number (stringsplit inputstr)))


(define targetweight (/ (weight allpackages) 3))


(findthreegroupsolution allpackages targetweight))




]








@section{What's the optimal score when divided into four groups?}




The loop is similar, but instead of using @racket[hassolution?] (which in essence tests if there is a twogroup solution), we ask if there is a threegroup solution after our target group is removed. So we create a recursive relationship between the second question and the first.




@chunk[<day24q2>




(define (q2 inputstr)


(define allpackages (map string>number (stringsplit inputstr)))


(define targetweight (/ (weight allpackages) 4))


(for*/first ([len (inrange (length allpackages))]


[group (inlist (sort


(groups allpackages len targetweight)


#:key quantumentanglement <))]


#:when (findthreegroupsolution


(removegroup group allpackages) targetweight))


(quantumentanglement group)))




]








@section{Testing Day 24}




@chunk[<day24test>


(module+ test


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


(checkequal? (q1 inputstr) 10439961859)


(checkequal? (q2 inputstr) 72050269))]






