60 lines
1.7 KiB
Racket
60 lines
1.7 KiB
Racket
#lang racket
|
|
(require math/number-theory)
|
|
|
|
(define (trinv n) ; OEIS A002024
|
|
(exact-floor (/ (+ 1 (sqrt (* 1 (* 8 n)))) 2)))
|
|
|
|
(define (triangle-neighbour-bl n)
|
|
(define row (trinv n))
|
|
(+ n (- (triangle-number row) (triangle-number (- row 1)))))
|
|
|
|
(define (maximum-triangle-path-sum T)
|
|
(define n-rows (trinv (vector-length T)))
|
|
(define memo# (make-hash))
|
|
(define (inner i)
|
|
(hash-ref!
|
|
memo# i
|
|
(λ ()
|
|
(+ (vector-ref T (sub1 i)) ; index is 1-based (so vector-refs need -1'ing)
|
|
(cond [(= (trinv i) n-rows) 0]
|
|
[else
|
|
(define bl (triangle-neighbour-bl i))
|
|
(max (inner bl) (inner (add1 bl)))])))))
|
|
(inner 1))
|
|
|
|
(module+ main
|
|
(maximum-triangle-path-sum
|
|
#(55
|
|
94 48
|
|
95 30 96
|
|
77 71 26 67
|
|
97 13 76 38 45
|
|
07 36 79 16 37 68
|
|
48 07 09 18 70 26 06
|
|
18 72 79 46 59 79 29 90
|
|
20 76 87 11 32 07 07 49 18
|
|
27 83 58 35 71 11 25 57 29 85
|
|
14 64 36 96 27 11 58 56 92 18 55
|
|
02 90 03 60 48 49 41 46 33 36 47 23
|
|
92 50 48 02 36 59 42 79 72 20 82 77 42
|
|
56 78 38 80 39 75 02 71 66 66 01 03 55 72
|
|
44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
|
|
85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
|
|
06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
|
|
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93)))
|
|
|
|
(module+ test
|
|
(require rackunit)
|
|
(check-equal? (for/list ((n (in-range 1 (add1 10)))) (trinv n)) '(1 2 2 3 3 3 4 4 4 4))
|
|
; 1
|
|
; 2 3
|
|
; 4 5 6
|
|
; 7 8 9 10
|
|
(check-eq? (triangle-neighbour-bl 1) 2)
|
|
(check-eq? (triangle-neighbour-bl 3) 5)
|
|
(check-eq? (triangle-neighbour-bl 5) 8)
|
|
(define test-triangle
|
|
#(55 94 48 95 30 96 77 71 26 67))
|
|
(check-equal? (maximum-triangle-path-sum test-triangle) 321)
|
|
)
|