blob: 69bfdaed743592e541acb9611fb18ed183424e3d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#lang racket
(require "../lib/utils.rkt")
(define lines
(call-with-input-file "input"
(λ (fp)
(get-lines fp))))
(define (unfold-pattern x)
(append x (list #\?) x (list #\?) x (list #\?) x (list #\?) x))
(define (unfold-num x)
(append x x x x x))
(define (parse-line line)
(define line-splited (string-split line))
(define arr-list (string->list (car line-splited)))
(define conds (map string->number (string-split (cadr line-splited) ",")))
(cons (reverse (cons #\. (reverse (unfold-pattern arr-list)))) (unfold-num conds)))
(define (cont-lava scanned)
(define nums (filter (λ (n) (not (= 0 n)))
(map string-length (string-split scanned "."))))
(if (null? nums)
#f
(car nums)))
(define (can-match? scanned remain)
(if (null? scanned)
'unknown
(if (char=? #\# (car scanned))
'unknown
(let ()
(define num (cont-lava (list->string scanned)))
(if (not num)
'unknown
(if (null? remain)
'no
(if (= num (car remain))
'yes
'no)))))))
(define (check-terminal scanned remain)
(define can-match (can-match? scanned remain))
(if (and (eq? 'yes can-match)
(null? (cdr remain)))
1
(if (eq? 'no can-match)
0
(if (null? remain)
1
0))))
(define (possible-arr-num instance)
(define conds (cdr instance))
(define (impl recur scanned unscanned remain)
(define can-match (can-match? scanned remain))
(define (gen-next-scanned c lst)
(if (and (null? lst) (char=? c #\.))
'()
(cons c lst)))
(if (null? unscanned)
(check-terminal scanned remain)
(if (eq? can-match 'no)
0
(let ()
(define next-scanned
(if (eq? 'yes can-match)
'()
scanned))
(define next-remain
(if (eq? 'yes can-match)
(cdr remain)
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)))))))
(define memo (make-hash))
(define (memo-impl recur 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))
(hash-set! memo (list unscanned remain) ret)
ret))
(impl recur scanned unscanned remain)))
(memo-impl memo-impl '() (car instance) conds))
(apply + (map possible-arr-num (map parse-line lines)))
|
