Given a bag B of integers, find the minimum of the sum of | m - b | for all b in B and some integer m.
$ cat 07a.rkt #lang racket (provide read-input example-data ) (require (prefix-in aoc: "aoc.rkt") ) (define (aoc07a . args) ; Return the most fuel-efficient meeting point for the given ; crab navy positions. If no positions are given, use the ; contest problem input; otherwise assume the argument is the ; string representation of a problem input. (cheapest-crab-fleet-fuel-burn (apply read-input args))) (define (cheapest-crab-fleet-fuel-burn positions) ; Return the minimum amount of fuel needed for the crab navy at ; the given positions to rendezvous at the same point. ; There is lots of juicy math to exploit to provide a good (that is, ; linear) solution, but this solution skips all that and relies on ; brute-force search. (let ((mn (apply min positions)) (mx (apply max positions)) (fuel-used-moving-to (lambda (pt) (foldl (lambda (sp fu) (+ fu (abs (- sp pt)))) 0 positions)))) (let loop ((p mn) (min-f (* mx (length positions)))) (if (> p mx) min-f (loop (+ p 1) (min (fuel-used-moving-to p) min-f)))))) (define (read-input . arg) ; Return the given crab navy positions. If no argument is ; given, use the contest problem input; otherwise assume the ; argument is the string representation of a problem input. (map string->number (string-split (caaar (aoc:aoc-read-input (if (null? arg) 7 (car arg)))) ","))) (define example-data "16,1,2,0,4,2,7,1,2,14") (define example-result 37) (module+ main (aoc07a) ) (module+ test (require rackunit) (define positions (read-input example-data)) (check-equal? (cheapest-crab-fleet-fuel-burn positions) example-result) (check-equal? (aoc07a) 331067) ) $ raco test 07a.rkt raco test: (submod "07a.rkt" test) 2 tests passed $