From 9d68d71e8176812de18d86efee2d5767feda92ea Mon Sep 17 00:00:00 2001 From: Mistivia Date: Mon, 4 Mar 2024 22:23:57 +0800 Subject: refactor DP --- 12/2.rkt | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) diff --git a/12/2.rkt b/12/2.rkt index 69bfdae..3878695 100644 --- a/12/2.rkt +++ b/12/2.rkt @@ -54,7 +54,7 @@ (define (possible-arr-num instance) (define conds (cdr instance)) - (define (impl recur scanned unscanned remain) + (define (impl scanned unscanned remain) (define can-match (can-match? scanned remain)) (define (gen-next-scanned c lst) (if (and (null? lst) (char=? c #\.)) @@ -75,19 +75,21 @@ remain)) (define head (car unscanned)) (if (not (char=? head #\?)) - (recur recur (gen-next-scanned head next-scanned) (cdr unscanned) next-remain) - (+ (recur recur (gen-next-scanned #\. next-scanned) (cdr unscanned) next-remain) - (recur recur (gen-next-scanned #\# next-scanned) (cdr unscanned) next-remain))))))) + (impl (gen-next-scanned head next-scanned) (cdr unscanned) next-remain) + (+ (impl (gen-next-scanned #\. next-scanned) (cdr unscanned) next-remain) + (impl (gen-next-scanned #\# next-scanned) (cdr unscanned) next-remain))))))) (define memo (make-hash)) - (define (memo-impl recur scanned unscanned remain) + (define original-impl impl) + (define (memo-impl scanned unscanned remain) (if (null? scanned) (if (hash-has-key? memo (list unscanned remain)) (hash-ref memo (list unscanned remain)) (let () - (define ret (impl recur scanned unscanned remain)) + (define ret (original-impl scanned unscanned remain)) (hash-set! memo (list unscanned remain) ret) ret)) - (impl recur scanned unscanned remain))) - (memo-impl memo-impl '() (car instance) conds)) + (original-impl scanned unscanned remain))) + (set! impl memo-impl) + (impl '() (car instance) conds)) (apply + (map possible-arr-num (map parse-line lines))) \ No newline at end of file -- cgit v1.0