codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; maximum sum path (define sample '((3) (7 4) (2 4 6) (8 5 9 3))) (define input18 '((75) (95 64) (17 47 82) (18 35 87 10) (20 04 82 47 65) (19 01 23 75 03 34) (88 02 77 73 07 63 67) (99 65 04 28 06 16 70 92) (41 41 26 56 83 40 80 70 33) (41 48 72 33 47 32 37 16 94 29) (53 71 44 65 25 43 91 52 97 51 14) (70 11 33 28 77 73 17 78 39 68 17 57) (91 71 52 38 17 14 91 43 58 50 27 29 48) (63 66 04 68 89 53 67 30 73 16 69 87 40 31) (04 62 98 27 23 09 70 98 73 93 38 53 60 04 23))) (define (max-sum tri) (define (but-last xs) (reverse (cdr (reverse xs)))) (define (step xs ys) (map + ys (map max (cdr xs) (but-last xs)))) (let loop ((tri (reverse tri))) (if (null? (cdr tri)) (caar tri) (loop (cons (step (car tri) (cadr tri)) (cddr tri)))))) (display (max-sum sample)) (newline) (display (max-sum input18)) (newline) (define (max-sum-path tri) (define (sum xs) (apply + xs)) (define (step last next-to-last) (let loop ((last last) (next-to-last next-to-last) (out (list))) (if (null? next-to-last) (reverse out) (loop (cdr last) (cdr next-to-last) (if (< (sum (cadr last)) (sum (car last))) (cons (cons (car next-to-last) (car last)) out) (cons (cons (car next-to-last) (cadr last)) out)))))) (define (fix-last-row tri) (cons (map list (car tri)) (cdr tri))) (let loop ((tri (fix-last-row (reverse tri)))) (if (null? (cdr tri)) (caar tri) (loop (cons (step (car tri) (cadr tri)) (cddr tri)))))) (display (max-sum-path sample)) (newline) (display (max-sum-path input18)) (newline)
Private
[
?
]
Run code
Submit