26 lines
889 B
Racket
26 lines
889 B
Racket
#lang racket
|
||
|
||
(define (memoize f)
|
||
(define table (make-hash))
|
||
(λ args (hash-ref! table args (thunk (apply f args)))))
|
||
|
||
(struct $ (cost expl))
|
||
(define @ vector-ref)
|
||
|
||
(define (+: #:combine [combine (thunk* #f)] . xs)
|
||
($ (apply + (map $-cost xs)) (apply combine (map $-expl xs))))
|
||
|
||
(define (min: . xs) (argmin $-cost xs))
|
||
|
||
(define (compute dims)
|
||
(define loop
|
||
(memoize
|
||
(λ (left right)
|
||
(cond
|
||
[(= 1 (- right left)) ($ 0 left)]
|
||
[else (for/fold ([ans ($ +inf.0 #f)]) ([mid (in-range (add1 left) right)])
|
||
(min: ans (+: (loop left mid) (loop mid right)
|
||
($ (* (@ dims left) (@ dims mid) (@ dims right)) #f)
|
||
#:combine (λ (left-answer right-answer _)
|
||
(list left-answer '× right-answer)))))]))))
|
||
(loop 0 (sub1 (vector-length dims))))
|