commit e6795db3a88bdc123df78d42ae8cfe7508722e23
parent a8fde4e01fa1684be6df30394d399d9921049f10
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Tue, 12 Dec 2023 23:24:54 -0500
Add 2023 day 12 part 1
Diffstat:
| A | 2023/day12/day12.scm | | | 135 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/day12/input.txt | | | 1000 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 1135 insertions(+), 0 deletions(-)
diff --git a/2023/day12/day12.scm b/2023/day12/day12.scm
@@ -0,0 +1,135 @@
+(use-modules (ice-9 popen))
+(use-modules (ice-9 rdelim))
+(use-modules (ice-9 format))
+(use-modules (srfi srfi-1))
+
+(define (parse-numbers numbers)
+ (filter (lambda (x) x) (map string->number (string-split numbers #\,))))
+
+(define (parse-input filename)
+ (let ((file (open-input-file filename))
+ (records '()))
+ (while #t
+ (let ((line (car (%read-line file))))
+ (if (eof-object? line)
+ (break)
+ (let* ((tmp (string-split line #\ ))
+ (pattern (string->list (car tmp)))
+ (group (parse-numbers (list-ref tmp 1))))
+ (set! records (cons (list pattern group) records))))))
+ records))
+
+(define (check-group pattern curr-count curr-group)
+ (if (null? pattern)
+ (if (> curr-count 0)
+ (append curr-group (list curr-count))
+ curr-group)
+ (case (car pattern)
+ ((#\.) (if (> curr-count 0)
+ (check-group (cdr pattern) 0 (append curr-group (list curr-count)))
+ (check-group (cdr pattern) 0 curr-group)))
+ ((#\#) (check-group (cdr pattern) (1+ curr-count) curr-group)))))
+
+(define (group-cmp prefix-group target-group strict prefix-group-ended)
+ ;; strict forces same length, otherwise only prefix part is checked
+ ;; prefix-group-ended indicates if last group can still change
+ (if (null? target-group)
+ (null? prefix-group)
+ (if (null? prefix-group)
+ (not strict)
+ (if (= (car prefix-group) (car target-group))
+ (group-cmp (cdr prefix-group) (cdr target-group) strict prefix-group-ended)
+ ;; can make this part smarter to cut more branches
+ (if (and (= (length prefix-group) 1) (not prefix-group-ended))
+ (< (car prefix-group) (car target-group))
+ #f)))))
+
+(define (is-prefix-valid max-len prefix group)
+ (let ((prefix-group (check-group prefix 0 '()))
+ (strict (= max-len (length prefix)))
+ (prefix-group-ended (or (= max-len (length prefix))
+ (and (> (length prefix) 0)
+ (equal? (list-ref prefix (1- (length prefix))) #\.)))))
+ ;; (display (list "valid-check" prefix-group group strict prefix-group-ended)) (newline)
+ (group-cmp prefix-group group strict prefix-group-ended)))
+
+(define (get-determined-prefix pattern prefix)
+ (if (null? pattern)
+ prefix
+ (if (equal? (car pattern) #\?)
+ prefix
+ (get-determined-prefix (cdr pattern)
+ (append prefix (list (car pattern)))))))
+
+(define (expand-pattern pattern)
+ (let ((candidates '()))
+ (do ((i 0 (1+ i))) ((or (>= i (length pattern)) (not (null? candidates))))
+ (if (equal? (list-ref pattern i) #\?)
+ (begin
+ (let ((tmp (list-copy pattern)))
+ (list-set! tmp i #\.)
+ (set! candidates (cons tmp candidates)))
+ (let ((tmp (list-copy pattern)))
+ (list-set! tmp i #\#)
+ (set! candidates (cons tmp candidates))))))
+ candidates))
+
+(define (find-valid-permutation pattern group)
+ (let ((queue (list pattern))
+ (valid-count 0))
+ (while (> (length queue) 0)
+ (let* ((curr (car queue))
+ (curr-prefix (get-determined-prefix curr '()))
+ (curr-prefix-valid (is-prefix-valid (length curr) curr-prefix group))
+ (curr-prefix-ended (= (length curr-prefix) (length curr))))
+ ;; (display (list "queue" queue)) (newline)
+ ;; (display (list "curr" curr curr-prefix curr-prefix-valid curr-prefix-ended)) (newline)
+ (set! queue (cdr queue))
+ (if curr-prefix-valid
+ (if curr-prefix-ended
+ (begin
+ ;; (display (list "found valid" curr-prefix)) (newline)
+ (set! valid-count (1+ valid-count)))
+ (let ((candidates (expand-pattern curr)))
+ (set! queue (append candidates queue)))))
+ )
+ )
+ ;; (display (list "found" valid-count "permutations for" pattern group)) (newline)
+ valid-count
+ )
+ )
+
+(define (repeat lst n sep)
+ (if (= n 1)
+ lst
+ (if (null? sep)
+ (append lst (repeat lst (1- n) sep))
+ (append lst (list sep) (repeat lst (1- n) sep)))))
+
+(let* ((records (parse-input "input.txt"))
+ (permutations
+ (map (lambda (x) (find-valid-permutation (car x) (car (cdr x)))) records))
+ (total-permutation (fold + 0 permutations))
+ ;; (permutations-2
+ ;; (map (lambda (x) (find-valid-permutation (repeat (car x) 2 #\?)
+ ;; (repeat (car (cdr x)) 2 #nil))) records))
+ ;; (total-permutation-2 (fold + 0 permutations))
+ )
+ ;; this won't work for part 2, we need a (log n) algo or something that takes
+ ;; the entire sequence into consideration. consider separating the pattern by
+ ;; all the consecutive runs of #\., that gives us the blocks to build on. each
+ ;; block can match from 0 to len / 2 groups. then within each block fromed
+ ;; only by #\# and #\?, we check how many ways there are to form specified
+ ;; groups. some memorization could help. may need to break blocks down further
+ ;; at #\# boundaries, i.e. we need to know ?###??? can never make (1) and
+ ;; needs at least (3). maybe list these as "mergable" blocks: i.e. ?### gives
+ ;; ((() (1)) 3) => ((3) (4)).
+
+ ;; need some kind of memoization/dynamic programming
+
+ ;; 7007
+ (format #t "Part 1: ~d" total-permutation)
+ (newline)
+ ;; (format #t "Part 2: ~d" total-permutation-2)
+ ;; (newline)
+ )
diff --git a/2023/day12/input.txt b/2023/day12/input.txt
@@ -0,0 +1,1000 @@
+#?#???????#?.? 3,1,2,2
+.??.##.?#????.??#? 2,2,1,2,4
+.?.??#?##??#????.. 8,1
+??????????#.. 6,1
+.#.##????.??.? 1,6,1
+?#??#???.??.??? 3,1,1,1,1
+?#???????#? 2,1,5
+##?#??#?????.??? 5,1,4,2
+????.?#??.# 2,1,1
+???????##?????##???? 1,1,11,3
+.####??.??#??????#? 6,6,1
+??#..##?...?#. 2,3,2
+..??##?#?#???#??.??. 12,1
+??.?#???#? 1,3,1
+??.#??????????#.??? 4,1,1,3,1
+???##??.?##? 5,1,2
+???..???..?. 1,1,1,1
+.?????#?#??? 1,1,1,1
+##???????????# 5,3,2
+??..????###?#?.? 1,8
+????????#???.##?? 1,2,1,2,3
+????##.?#????.? 1,4,2,1,1
+##???#.##?.#????? 2,2,3,2,3
+?????.????? 2,3
+?#?#??.##???.?#?. 3,5,2
+?#?..?##???#?????? 1,12
+.??#?????????.?.#.? 11,1,1,1
+???????????#??????. 7,1,1,3,1
+??????????#?????## 1,1,2,1,1,6
+.##?.##?????????? 2,4,1,1
+??#?##????? 5,1
+??#????????????? 5,2,2
+?#.#??##??#???#????? 1,2,13
+#??.????#.?? 1,2,2,1
+#.#?#???????.???#. 1,4,1,1,1,4
+????#??..?.. 2,1,1,1
+.??.#????#?????????? 3,8
+?...#??..??.?? 3,1
+?????#?.?.? 2,2,1
+..?...#?#????#?#???? 4,5
+??.?#???#? 2,2
+.?#?#.???..?? 3,3
+.??.#???#?? 2,3,2
+???##??#??#.?..???? 4,4,1,2
+?????????. 4,1
+????.???.#??# 4,2,4
+?????.?##?#??##?#.?? 4,4,5
+??#?????????????#?# 1,6,1,2,2,1
+#??.??????#..#??#? 1,1,3,1,1,2
+???#????.???? 5,3
+????#????#? 1,2,2
+?#.?.??.?.?????#?? 2,1,1,2,1,2
+???.???#??.?? 2,3
+?.??#?#???#?.????#?? 1,3,1,3,2,2
+?.??.??#?????.? 2,3,2
+??##??????????? 3,3,3
+???##?.#???????? 1,3,2,1,1
+?.???#????????##. 1,2,1,1,3
+.?#.##????##??. 2,3,5
+????#??#?.?# 5,1,2
+..?.??????..? 1,6
+##??..????#?#?# 3,1,6
+?#?.?#????.?#?#???? 2,2,1,5,1
+????###??..??#. 7,1
+??..??..?? 1,2,1
+.?.?.?#??????#??. 1,9
+???????.#?#??????. 2,3,5,2
+.##?????#?## 4,1,1,2
+?#?#.???#?#???? 3,7,1
+#??.??.?#??????? 2,1,8
+?#???#?#??#.?? 8,1,1
+?#??????.?#???? 6,2,2
+##.?????.??? 2,1,3,2
+??????.?#? 1,3,3
+.?..?#?#?#. 4,1
+??#?????.??#???? 1,4,3
+.?#??#??.??#. 5,2
+?.#?.????? 2,1,1
+#?###?????#?.?#? 6,5,2
+#??#?.?#???????.??? 5,1,2,2,1,1
+..???#?#??????#.?#?? 12,3
+?????.??#??????? 2,1,6
+#??.#??#?#? 3,1,4
+???.?????#?#.????? 2,7,3
+???.?.#?#?? 2,3
+???..?????##? 1,1,3
+#?.???#???#??????. 1,2,7,1
+????.????#?#??#??? 1,1,9
+??#?.?#?#???###???? 1,1,10,2
+#??????????.##?? 1,1,1,2,3
+.?.?????.???????? 1,5
+???#?##???????? 1,7,1,1
+?????????#??? 1,1,1,4
+???.??#.????? 1,1,1,2
+.???.???..???. 1,3,1
+????????#??#?? 3,1,1,3
+????.?..#?#??? 2,1,3
+#?#???????#??.? 4,2,2,1
+?????###??? 1,6
+???.?#?????? 1,2,4
+?##????????????. 6,2,1
+??##?????..??????? 9,1,1,3
+???#?#???.#. 7,1
+.????#????????#.? 5,7
+##?#???????????.??# 5,2,5,1,1
+??????#?.???#?? 1,1,3,4,1
+.??#???##??...??.? 10,1,1
+.???.??#????????? 2,2,7
+????.????###? 1,1,1,4
+#?#??#?##????##? 1,1,11
+???.#??????#..?#??# 2,3,1,1,1,2
+?????#?#???#?? 1,5,1,2
+???##.?##?#?????.? 1,2,4,1,2
+??????##??. 1,4
+?#??.?????? 2,1,1
+?#?#???###?#?????#?? 14,2,1
+???#?.#???#?.? 1,1,1,3
+???.???#?#.#?# 1,5,3
+??.#??#????#. 2,2,4,1
+??#?#?..?. 3,1
+?????#????#.????#?# 1,2,4,1,1,4
+?.???#.??? 1,2,1
+.???.???#??.? 1,1,2,1
+.??????.???? 2,3,1
+#.##?????? 1,2,2
+.#?#??#???? 3,3
+??#??.#??????????##? 1,3,1,1,7
+.?#.???????##? 1,2,1,4
+#.???#..#..???.?# 1,2,1,2,2
+?#???.??##.?? 4,2
+??..?????.????#.?? 2,2,1,1,1,1
+??????.?#.##?? 2,1,1,3
+#???.?.??? 1,1,1
+.?##??????#? 3,5
+???#.##???. 1,2,1
+##??######.????#.?? 10,1,1,1,1
+.?.??#?.#. 1,2,1
+???????##?.??? 3,3,3
+.?.#.?.##?#.??? 1,1,2,1,1
+.??#???#?????????? 1,10
+??.?#.?.?? 1,2,1
+??.?#???.??#? 5,2
+#??#???#?##????#?? 5,10
+?#???#??#?#?? 2,7
+??###????????#??#?. 5,12
+??.???#????. 1,6
+??#?#???#.???? 1,3,1,3
+???????#?? 4,2
+??#?.??#???#??#. 1,1,5,1
+??.#.?.??? 2,1,2
+??##???#??????. 1,6,1,1
+?#????#..????#??? 1,2,7
+?#??#??#??#?.? 3,1,5,1
+??#?.#????.# 1,1,3,1
+#???#?????????.??? 13,3
+##?.???????#???# 2,2,5,1
+?#.????.????. 2,1,1,1
+???#.??.???? 1,1,1,2
+?#???#???#?????#? 2,8,1
+?##?.????????.??#? 3,6,4
+?????##??.?#?????? 2,2,8
+??.?##?#???# 1,5,1,1
+?.??#???##??#???# 12,1
+.#.#???#????????? 1,12
+???.?#.???#.???#. 1,1,1,3,2
+.#??#??.??? 1,1,1
+?#???#?..? 2,1,1
+?#????.?#? 1,3,3
+???##??#?#???? 2,6
+#????##???#????????# 2,8,6
+?.?###?..#????# 1,4,2,2
+????#?#...#?#?? 1,2,1,1,1
+.#???????#? 1,1,2
+???.??.#.?? 1,2,1
+.??##?#?????????? 6,4
+?#?#?..#??###?.? 1,2,1,5,1
+.#.??????#?????????? 1,7,1,1,1,1
+???.???#?.#.?? 1,1,1,1
+##..#.?##??? 2,1,6
+?.???.???#??#?#??#.? 1,3,1,6,2,1
+?#?##?????????????? 1,3,7,1
+?#???????.????#.???. 8,4,1
+???#..#??#??? 1,1,1,4
+##???????? 5,1
+???###.?#??..???#? 4,4,1,2
+?.?#??###.??????# 1,6,1,5
+.?????????# 7,1
+?.#.?????? 1,1,1
+??#?.#??#??#? 3,7
+??#?.????#?#??? 3,1,1,1,1
+?.#???????.#??? 1,1,2,2,2
+???????#???..? 1,1,3,1
+?#???#???.#???#??.?# 1,1,3,1,5,2
+?.?####.???? 1,4,1,1
+??#???#?????#?.? 7,1,1,2
+.#?#????.???????.? 5,7,1
+???#.????#?#?????. 1,1,11
+???.#??????#??#? 2,1,1,6
+.?#?????.#. 3,1,1
+.???##.?????.?? 5,1,2
+??#????.??.??##?? 6,2,5
+????????#???? 3,4
+???.?..?#?#?? 1,1,1,2
+?????.?.?????##?? 1,1,1,1,7
+?????#####???.?. 10,1,1
+??????..#?#??? 2,2,3,1
+.???.??.?? 1,1,1
+??##..??.?#??.?? 3,1,3,2
+??????#..??.? 3,1,1,1
+#???#??#?????? 1,4,2,1
+??#????..#????#?#??? 2,1,9
+.?????.?????.#??? 3,1,2,2,1
+?#.#?.??.???? 2,1,1,1
+?..?#??#.?#? 1,2,1,2
+??.???#####? 2,1,5
+.#?#?.??.?? 4,1,2
+???.#?#?#.#??.??#??? 1,3,1,1,1,4
+???#????.??.? 1,4,1,1
+.?.?.????##???. 1,6
+.???.????? 1,1
+#?????#??#??#?.?? 1,1,4,3,2
+????.?#??#??##???. 2,8
+#?.??#????##??#?.## 2,5,6,2
+#.#.???#?#?#.??.??. 1,1,1,5,1,1
+????#?.????#?# 6,5
+.???##?????.???.? 7,3
+???#????##?#?.???#?? 11,2
+?#???#????#???.?#?? 7,2,1,1,1
+???#?????#?..?? 7,1,1
+?##?#???????????#??. 4,1,4,1,2
+???????#???.#????. 8,3
+.??#?.?.?.##?????? 1,1,1,6,1
+???#.???#.?.##? 2,1,1,1,3
+#??#??????#????.? 1,2,6,2,1
+.??#?#?.????.?? 5,1,1
+???????#?? 4,3
+?????.?#????#?????.? 1,11
+???##?##?##????#???# 2,2,5,1,2,2
+???.???#??#??#??#?? 3,1,1,5,1,1
+##???.??#??#? 2,1,6
+?#??????#?????#?? 10,2
+???##?.?.?? 1,3
+.???????##??#.#??#? 3,5,1,5
+.#???..##?? 3,4
+????.#??.??.? 1,1,2,1
+?#?..???#??#?.?### 1,1,4,4
+#..??#..?.??###?#??? 1,2,1,5
+.##.#?..#? 2,2,1
+??#?#?#??#??#..? 5,4
+???.?.???#???##? 1,9
+?????????#??##?##? 1,1,13
+.??????#????. 2,4
+.?#.??#???. 1,2,1
+????????????? 10,1
+####????????????.#?? 7,1,2,2,2
+??#.#??????? 2,3,1,2
+#??????#?#.?.. 4,4
+.?#??#.?#??#??#??? 4,1,6
+#??#.?.?##.?#??? 4,2,4
+?#?##????.#??.???. 5,1,1,1,1,1
+???..?#???#???###? 1,1,8
+?###???.??. 6,2
+?##?..??????? 3,6
+?????##?????###.? 6,3
+#.??????????##?#??? 1,1,1,2,1,6
+??????.????? 2,1,1
+??#???????.??????? 8,3
+???????????##?? 4,1,3
+??.????????#?# 2,1,8
+???#?#.##?????.? 1,1,1,7,1
+#??##?#??##?#????#? 7,6,3
+####?#???###??#??.?? 4,7,2,1,1
+#?.?#.??.#?? 1,1,1,1
+???#??????#?.?????? 1,1,3,3,2,1
+???.????#?. 3,6
+??????.?######?? 5,7
+?#??##??#??????. 1,12
+???#?#####?#?..??#. 10,1
+?#.?#.????#? 1,1,2,2
+??.?.????#?#.?.?#.? 2,7,2
+??#????.?????#.?? 1,1,2,6,2
+??#???.??????????? 1,7
+??.?.?.????. 2,1,2,1
+??#?????????#??#???# 1,1,2,5,4,1
+###..##?#??????? 3,11
+?#????#?#??#? 2,4,2
+.??..##?#?..????? 4,3,1
+????.????? 3,1,1
+.???????????.????# 2,4,1,1,1,1
+??#?#???.??# 5,3
+???????#.?#?#?##?##. 4,1,9
+....???#??#???? 7,1
+?.??#??.?#?????.# 1,1,1,7,1
+?????.?#??? 3,3,1
+??#???????.??? 5,3
+.???#????????#??.? 4,1,6
+..?.?????. 1,2
+.??????????#?????#? 11,3
+?.?????#??????? 1,9
+.?????##??.?? 6,1
+?#?.??#.?? 1,2,1
+#????????????? 1,6,3
+.??????..???#??. 4,1,1
+??????????????. 1,1,1,3,1
+?.???????. 1,2
+?#?????..??.???. 2,2,1,2,1
+#????#???? 4,3
+?????????????. 8,2
+.?##.??#.??#.?? 3,1,1,3,2
+???????##???????#? 10,5
+????#??????.?.?? 7,1,1
+?????????#????#.?# 1,1,1,2,1,2
+??#.?##????.??? 2,6,2
+.??#???.???????.#? 6,1,1,1,1,2
+#?#?.?????#???? 4,6,2
+?##?????#????#?#.#? 2,1,1,6,1
+????????.??????#. 4,1,1,1,1
+??.?#????#.#? 1,4,2,1
+???#.???#? 3,1,2
+?##???????#?? 2,1,4
+?.?.??#?.#??.?????# 1,1,1,3,6
+???#?????#?#?.?###? 1,1,1,2,1,5
+?.##??##?#??#???## 6,1,7
+?.?.????.?# 1,2
+????.#??#??#???? 1,1,9,1
+?.?#????.????#?.. 5,1
+?.??????????#??? 2,7
+#???#?##?????.? 5,2,3,1
+#????????. 5,3
+??#??#??#? 1,3,1
+???#???#?##?###.?? 3,8
+?#????#????#??# 2,9,1
+?.??#??.?.??#?? 1,4,4
+??#?#?#?#?? 3,6
+?#?.?.?##??.###?#? 2,4,5
+????#???.#??.??.??? 7,2,2,1
+?#?????#???.#?? 9,1,1
+#?.?#.#?#???????. 2,1,6,1
+?????#?????? 2,1,2
+.???#???.? 5,1,1
+.?#???.????? 4,1,2
+???????##???? 3,1,2,2
+?????##???? 4,2
+.???#????????## 2,1,1,1,2
+?????????.?#. 3,5,2
+?.???.???#????#??#? 1,3,9,2
+?#???????.??#??????? 2,1,1,1,3,4
+??#??#??#..#???.#?? 8,1,1,1,1
+????.?#????.#?.??? 3,2,1,1,2
+??.?#??????# 1,5,2
+?????.?.????? 3,1,4
+???#?????..?..? 9,1
+?????????#?.?. 2,1,1,3
+#.??#??????.#??. 1,1,7,1,1
+??#.??#??????#..???? 3,3,2,1,2
+.#???????????# 5,1,1,1
+?.?..?????. 1,3
+?????#?#????.??? 3,5,1
+???#???#?.??#?##??? 3,1,2,1,1,4
+??.?#????? 1,4,1
+?..#?.??###. 1,5
+???##?..???? 6,2
+#.??.???#?#.#????? 1,1,3,1,1,1
+??#??#???#??#?? 6,3,2
+???#???????##?#??. 2,3,7
+?????.??.??# 1,1,1,1
+?#??#?###? 2,5
+?#?#?#?.?.#?#?.?? 5,3
+??.??#.????? 1,1,1
+?#.?#.#?##??#???#?? 2,1,5,2,2,1
+..?????.??.???..#??? 1,2,1,2,4
+.???#?????.???????. 1,4,2,1,3
+???#?????.#???#..?. 4,5
+???#?????##?#?# 3,1,2,1,1
+??#???.??????? 3,3
+??.??.???#??? 1,1,1,2
+#???????##.?#?. 1,2,5,1
+???#???.?? 5,1,1
+?.###?##????????? 1,8,1,1
+?##???#??????##. 11,2
+.???#?????#??? 3,3
+.##?#?#???? 4,5
+??#??????? 1,6
+???##??.??.? 2,4
+.??#??##.??.???# 2,3,1,1,1
+???#???#???????? 12,1
+#.?#???##????????#? 1,1,13
+?????#????.?#???#? 1,1,4,7
+?????#???????#????? 8,3
+?#??#.????????. 5,3,1
+?##?#?.#?????? 5,6
+?.??#??#.???#.????# 1,3,1,1,1,2
+???.???##????.??#??? 1,2,2,2,5
+??##?#????????.?.# 8,1,1,1
+???##??..?##.?...?. 2,2
+#.?.?.????.????#?#?# 1,1,1,9
+??.????#?????? 1,10
+.??.##.?#? 2,1
+?#??????.#.? 2,3,1,1
+??????.???. 1,1,1
+.???.??..#? 2,2,1
+??.??????.????. 4,3
+#.?#?????.. 1,2,3
+??#??#????#? 5,4
+??#?????.?. 2,2,1
+??#?#??..##?#???#?. 6,9
+?#??#??#####.???#? 5,5,4
+???#?..??#??#?### 2,8
+.???#.???????#????.? 3,1,6,1,1
+???#?????#????## 5,2,4
+#?#?.?????.????? 1,1,3,1,2
+?????#??????.?#???. 4,4,1,1,1
+##????#?.???????. 8,1,1
+???.??#????#????#? 1,1,1,1,4,3
+#?#?##??#????????? 9,6
+?#???????????? 5,1,1,2
+?.?????#?.??. 5,2
+??.??..????#? 1,1,1,4
+??#?.?#?#??.?? 2,6
+.???..?.?..? 1,1,1,1
+??#...??##?????.??? 1,1,4,3,1
+??#.#?????????????? 1,1,1,8,1,1
+?##??#???????# 2,1,3,1
+?#??#.??..?#?? 4,1,2,1
+?#?????#????.. 3,3
+#??#???###??#?????? 2,2,6,2
+#?#??#???? 1,4,2
+.???.?.?#? 2,2
+??#??##?.?? 6,1
+#???#??.#??# 1,4,1,2
+???????#??? 2,1,1
+?##????????????? 2,2,5
+.##?#?.?#? 5,2
+???????##.???#????? 8,3,1,1
+?...??.?.. 1,1
+#????#?##????? 1,7,1
+?.?..##?#.??##?#?.? 4,5
+??.??.????????# 1,2,1,5
+#??#??#??###?????##? 1,4,12
+??#.?#???.?????#?# 2,3,3,4
+???###?.?? 1,4
+?#????#???. 2,3,1
+?##?#.????#??##.#. 5,2,6,1
+?#?#??.????#??# 4,1,5,1
+????.#.????????##?. 1,1,1,2,6
+.???..??#?..??..#??? 1,1,4,1,2,1
+????##?##?##.???? 11,1
+??.???#?#?#????.#??. 1,9,1,1
+.???#??.????? 1,1,1,3
+??.???#??# 2,1,4
+??????.??? 1,1,1
+?#?#???????.???.?#? 6,2,2,2
+#???#?##??#????#? 1,2,10
+?.##??.??.?#???#?.?? 2,1,2,7,2
+.????#..???? 1,3,1,1
+?.?#??????????#???? 3,9
+???#????#.?.? 4,1,1,1
+.???.#????. 1,1,2
+?#?##?????? 2,3,3
+????????##??? 1,5
+???###??.?#????#?? 1,4,8
+?.?#????.???.#.?.# 1,5,3,1,1,1
+?????##???#?.???#?? 2,4,1,2,2,2
+#????.?.#.?#??? 1,2,1,1,1
+??#?.#?#####????.?? 1,1,8,2,1
+??????#???.#?.. 1,1,1,1,2
+.??.##?.??.#????.??? 2,2
+?#??#??#??.??#.???# 1,5,1,1,1,4
+.?##?.?#???? 2,3
+????#?#??????..#? 2,5,3,2
+????????#????#..? 10,1,1,1
+#?????#???????.??#? 8,1,2
+#??###???.????###??? 1,6,1,7
+?????.?.??# 2,1
+??.???..#????. 2,2,2,2
+#?.#???..#..? 1,4,1
+?#???##?.#???????#?? 7,10
+?????#?#????#??? 9,1
+????????##?.###?? 1,1,4,5
+.???#??#.? 1,4,1
+?????.??#???. 1,3
+???#.??###?#???#???? 2,10
+..#??#.???#??.?. 4,1
+??????#?#??.??.???. 1,2,1,3,1,1
+?##??#?????? 7,1
+?.?#???.??????????? 1,1,2,4,1,1
+??????.?##??? 1,3
+?.?.????##?.????? 1,5,3
+?.#???##?#????#?#.?? 1,2,8,1,1,1
+??.?##???.#.?.?#???# 1,6,1,1,1,1
+??#??????..# 4,1,1
+?.#?.???#??#????#? 1,5,1,2,1
+?###.??#???#.?#?# 3,1,3,1,3
+??#??##????#.??? 3,4,1,1
+#?##?#####?#?#??. 1,12,1
+?##??#????#??..?#?? 4,1,6,2
+?????..???? 1,1,1
+????#?????#?? 4,3
+???#?#???#?? 1,1,5
+??#????????????? 4,5,2
+?##???##?#??.???#? 10,1,3
+.???#??????????#???. 4,2,7
+#????#???#??#?#?.?? 8,2,1,1,1
+?.??#??#??? 1,7
+??????#.????? 2,3,5
+###??..?????#??? 5,1,5,1
+?#?????#?.???.?? 1,4,1,2
+???#???#????????..?# 1,7,1,1,2
+?###???#?????#? 8,2
+.?.???#??? 1,1,3
+#####???#???#?? 5,4,2
+.?#?#?.?.??? 4,1,2
+?????????#??#.?.?#?? 3,6,2
+.?###?##?????????# 4,2,4,2,1
+#?????###???????#??? 1,13
+.#?#?????#?. 3,1,1
+.?#?#???#????#.#.? 1,1,6,1,1
+.##??#??#?##?.?.#?? 3,2,5,1,1,1
+.?#??#.??#?#??#?#??? 5,3,4,1
+??.????.?.##???????? 2,3,6,1
+?#?##??###.??#???#?? 2,2,4,1,1,1
+?#.#..????#?#?#??#?? 1,1,1,1,5,2
+??##????#????..# 3,2,2,2,1
+??.???#?..? 1,2,1
+?##?????#. 3,2
+#?#??????.??##.?? 9,4
+.?????#????? 6,1
+?.?.????#? 1,1,1
+???###??#?...??#??#? 1,4,2,1,1,1
+.??#?????..?#? 4,1,1,2
+??.#?...#?##.?#???# 1,1,4,1,1,1
+????.?.????? 1,1,1,1
+????#????#.?. 8,1
+??#?.?#?##.?. 3,4
+?#????#.##??..?? 1,1,1,4,1
+???????#??????.? 1,1,3
+.?????##..? 1,4,1
+.??.####???? 1,7
+.##??.???.?#?.?? 2,1,3,2,1
+#???#?#?????#.. 1,1,7,1
+.?.?#????????????? 1,4,6,1,1
+???.#?????? 2,3,1
+?##????..?##??#. 2,2,6
+?#.??#??.??#?# 1,2,2,1
+.#??#..?#?????. 4,2
+??#???????#?.???? 3,6,1,1
+.??.??.????### 1,1,5
+#.?#.#????????????? 1,1,12,1
+??#????#????.??#?#? 4,1,2,1,1,4
+??????????##? 1,2,4
+##???#??????.???#??? 7,3,2,1,2
+??.???.#?##... 2,4
+.#??#???#????####?# 10,6
+???#??.????? 1,1,1,1
+.?#?????#???? 3,2
+???#???.?.#???## 2,3,1,6
+?#???..???? 4,2
+??#??.???.# 2,2,1
+??????##?##?#?.?. 12,1
+???#???#?.????.?? 2,6,1,1,1
+#?.???.???????##?#?? 1,1,1,1,10
+?????.?##?#???? 3,5
+?????#.???#?? 4,3
+?##??????... 4,1
+?##??#?.????#.#? 3,1,2,1,2
+.?.?????#. 1,1,4
+??????#?.? 3,3
+#.?#?#.?##?????? 1,1,1,6,1
+?#?.?#?..??. 1,2,1
+???????#?? 3,2
+??#???????#.# 3,2,2,1
+..???.#????.??#??? 3,2,1,1,1,2
+?#?###????.#.???? 7,1,1,1
+??#.?.##?.???.. 3,2
+?????#??..#..??? 3,3,1,3
+???##???????? 6,1
+????#????? 1,1,1
+?#?##.??.??# 4,1,1,1
+?#?.??##??.?#??#?# 2,3,2,4
+????????????#? 2,7,2
+?????#?#.????? 1,3,1,1
+.??.????###??? 1,6,1
+?.?#???.#?. 4,1
+???#?#?#?#????.? 11,1,1
+#??.??????###???#?## 1,1,1,1,3,6
+?????.#?##?..?? 4,4
+.??#?#????.?#.??? 4,1
+.?#.?#???#??##??? 2,2,7
+.#????.?????##?##### 1,1,1,13
+???.??.##?.#? 1,2,3,2
+???#?.???.? 2,2
+?##??###????#?#? 3,10
+?????#????##?#?..??? 7,6
+.#?##.??#???? 4,5
+?.???????#??#? 1,2,1,5
+??.#.#?#??###?? 2,1,1,1,5
+?.???#???#?? 5,3
+???#?##.????#??.??? 1,5,3,2,1,1
+?#??.###????#???# 1,5,2,1
+.???.???????#???. 1,1,6
+?##.#???#.#??? 3,5,1,1
+.???????.?#?#? 1,1,2,4
+??.?.??#.? 2,1,1
+???#??#..#?????. 1,2,1,2,1
+.???.??????.#?.? 1,2,2,2,1
+..?????.????.#??#. 1,2,2,1,1,1
+?#???.????? 1,1,3
+?##???#??#??????? 10,3
+??????????.???#? 3,3,1,5
+??...?????????.. 1,3,4
+#???###?#??..#??#?. 7,2,5
+#.#..#??????#?#????# 1,1,15
+?.??#?..????#?.? 2,5
+????????.?? 1,6,1
+??.???.???.#?#.? 2,2,1,1,3
+..#..??##?? 1,4
+##??#??????.#?? 8,2
+?????.?#?.? 2,2
+##.???#??????. 2,5,2
+???##??.?#?#?? 3,5
+#.?????#????#?? 1,9
+#??##?.?#????#????? 1,2,10
+?..?..??#???? 1,6
+??.???#?#?# 1,5,1
+??####??#? 4,1
+?.????????????.? 1,3,1
+???.??????#..#?.?? 2,1,3,2,1
+????#??.???????#???? 6,8
+??#.?#?#??#?.???? 1,1,1,3,3
+.##??????.##????? 5,5
+#??..???#.#? 2,3,2
+?.???.??#??????#???. 1,2,6,2,1
+?.?#?????? 5,1
+??????#?#????. 1,9
+?????.#??.?.?#?.# 2,3,3,1
+????##?#??.??#?. 5,3,3
+?.??????.#. 1,2,1
+?.##?.??.# 2,1,1
+????#???.????#? 3,2,1,2
+.????##??# 1,5
+?????#?.#..## 2,1,1,2
+??.###?????.???. 7,2
+????????.?.?.#??.??# 7,1,1,1,1,1
+#??##????#??? 8,1,1
+##????#?#?##?#?.??. 2,11,1
+???#???????????#?? 6,5
+?.???..#??.??.?.#?? 2,1,1,2,1,3
+?.??.?##????? 1,2,2
+.??#???#?????#? 6,2,2
+..?????#.. 1,1
+?##?..????. 4,1
+??#????????#?? 2,9
+??????.???###? 4,6
+????..#???#? 1,2,2,3
+??##?.??#???# 5,2,3
+#.??????..?. 1,1,2,1
+.#.???.??#.?#?#?. 1,2,1,1,4
+.??.?.??#???????? 2,1,2,1,3
+#???#.??..?#.???? 5,2
+???.???.?.#? 2,1,1,1
+?.#??.???#??. 1,4,1
+????##?#?#???#???.? 14,1,1
+???.??##?#?#? 1,8
+???????.?##?.??? 3,1,3,1,1
+#???#???.???.???? 1,5,1,2
+?????#???#?#?#? 8,1,1
+??#?#???.#? 6,1
+.??????????.?##???#. 8,3,2
+??.##.?..?. 2,1,1
+.???????#???#?#???? 12,3,1
+??#???.???# 5,1,1
+?##?#?##???? 3,6
+??.#???.????#?. 1,1,1,2,2
+???.#?#????#?#?# 3,1,1,3,1
+...?#.?????#? 2,2
+??..?#.?#???## 2,1,2,2
+????#????.???. 1,6,1
+.???#.#?#?#?. 4,1,1,2
+.??????#??##??#?# 1,5,4
+??#?.??????#?? 1,1,8
+??#??.#?#?????# 1,1,2,1,1
+?#????#???????# 1,1,1,6
+?##??????#. 2,1,1
+????.?????#?.?# 1,1,6,1
+?###??????#?#?. 4,8
+.??.?.??????#. 1,1,2,1
+?#.???#????.? 1,3
+?#???.#?????#?#??? 1,1,1,8
+?#.????????.#?? 1,7,1
+?????????#...?? 1,6,2
+#?.?#??#????.#???.?? 2,5,1,1,1,2
+??????..#?. 2,1,1
+.??###?#??. 4,1,1
+#????#??##???? 10,1
+??#??#?###? 3,1,3
+????.??????#.?##?? 1,1,1,2,1,5
+??#?.?.?#?? 2,1,1
+##.?###??? 2,3,1
+.?.??..?#?.?? 1,3,1
+.#?????.#???? 3,2,2,1
+??.?#??.?#???#??? 1,2,2,5
+#??.???#????##? 1,1,1,1,2
+???????###.? 3,3
+????????.. 1,2,1
+.?#?##?.#??#??.?? 5,5,1
+???????#?#. 4,4
+??#?#???.?? 5,2
+?.?#??#?#?#????? 1,10,1
+?...#????? 2,1
+???..????..?.?#? 2,1,1,1,2
+..?#?????#???# 9,1
+???.#??.?#?.?##???? 3,3,2,3,1,1
+??#???#??#???#..#.? 5,4,1,1,1,1
+.?#.??#??#?#. 1,1,1,3
+..?.???##????.??.?? 5,1
+.??.????#??..#???.?? 1,1,5,2,1,1
+##????##.#???? 3,3,2,1
+????##.???#?????#??. 1,2,1,3,6
+..???##.#?.??#?#?#? 4,1,8
+.?#.????#??#?##??#?? 1,2,2,1,7
+?#?#.?#????#??? 2,1,3,2,1
+?.?##?#?#?????????? 10,2,1
+?????###????????..? 1,6,2,1,1,1
+???#.??#.???##.?## 1,1,1,1,4,2
+????..?#?###? 3,6
+??#.#???.?.? 1,1,1,1
+???????????#?????#. 6,4,2
+...?#??????.?. 4,1
+?##???????.?.??.#. 9,1,1,1
+?#?#?##???...? 3,2,2,1
+.##?.?..#??????#? 2,1,1,3,1
+#??##??#?#?????.?? 5,7,1
+??#?????#?.?#.# 1,1,5,1,1
+???.?#???#?.?? 3,6,1
+?.???#????? 4,1
+?#..??.??? 1,1,1
+?.#???.??? 1,3,1
+#?#????#???? 1,1,3,3
+?#??????????.? 2,4
+#???????.??. 1,1,1,1
+??.?#??#??..??.?## 1,6,1,2
+????#??#?# 3,2,1
+??.#?#..??#???? 1,1,3,2
+.#?...??#????.????#? 1,3,2,6
+#?#?.#..?.??.?.?#?? 3,1,1,2,1,3
+#????.??##? 1,4
+?.?.???????#?. 2,1
+#??#..?#????#???.?.? 1,1,10,1,1
+#????????#?.?... 6,3,1
+????###????? 5,2
+#??.?????. 3,4
+?.?????????#?#.??? 6,3,2
+?????..?.? 3,1
+??#??##??.???. 4,3,2
+.?.????#?? 1,2
+??#??.????.? 3,2,1,1
+????#??.??##? 7,3
+?????#..???? 4,1
+?.??#??##? 3,3
+??.???.?#? 1,3
+??.#?.?#..?? 1,2,1,2
+??..?#???. 2,4
+.#.???#???###?#??.? 1,1,2,3,1,1
+?.##???#???.?????.? 8,4
+????.??.#???.#??? 1,1,4,1,1
+.??#?#?...#?.??? 3,2,1,1
+??.?????#??# 2,1,4,1
+???#??#???#?# 3,7
+?.??#..?????#????#? 1,1,1,2,7
+#?.??.#?.?#?.???###? 2,1,1,2,1,3
+#????#?#??.???. 1,6,1,1,1
+????.???#???#?????? 1,2,6
+.?.???????#???.??? 9,2
+?##??.??##. 2,3
+?#?????#???.#???##? 3,3,1,4
+#??????#?###???#?? 2,13
+???#??#???????? 6,1,1
+??#??##????? 1,3,1
+.??..#??#? 1,1,2
+?.??###???#.?????. 8,2
+#..???#??.???? 1,1,3,1
+??????.??? 2,1,1
+?#???.???# 1,1,1
+?###??.?????# 6,1,1,1
+??????????? 1,1
+?##???#????????#.?#. 4,1,7,1
+.?.#??.??#?#? 3,3
+????.#?.?# 1,2
+?#??.????.???.? 4,3,2,1
+.???#??#???#?.???..? 3,3,3,1,1
+???.???.????#???#? 1,1,1,1,8
+????#??#?.?## 7,2
+#??????.???#?#??#? 6,7,2
+.???..?#?# 1,3
+?????#?#?#?#?????? 12,1
+#?..?.????????#??? 2,1,1,1,2,1
+??#???...??#??? 1,5
+?.??????#.??? 3,2,1
+.?#.?#..??.#??? 1,2,3
+.??????#?#...?#?.? 5,2
+??.???#??#? 1,1,2
+???#??#?????#?##???? 8,4,1
+.#??#????????.????. 6,3,3
+.#?#?.?.#??.?? 4,2
+?#???##??##???? 2,10
+???.???????#?? 2,1,3
+?#???#?##??.#?? 4,5,1
+???????????????#??? 4,1,1,1,2,2
+??#???#?#??????#? 2,5,6
+??#?.??#..?#??? 3,1,1,5
+?#???#.???.#..# 2,2,1,1,1
+#???????##??.#?.? 1,1,1,3,2
+?????#??###??? 2,7
+#????????##.?.??. 2,7,1
+?.??#?..???#?#????. 3,10
+??????#?..???????.? 5,2
+???#????????????? 1,1,2,2,3
+????.#???#?.. 1,6
+??.??.#??#????????? 1,2,9,3
+????.?..##??? 1,1,2,1
+?#?#????.?#??#??? 8,5
+##?#???#???#?#.??? 5,2,4,2
+??.??#?????#? 1,3,1,2
+??.???#?.##? 1,2,2
+..??.?????# 1,6
+?##??#???#??? 3,2,3,1
+?????#???#?###?##??? 1,2,13
+#?#?#??????#.??#?? 12,3
+???.???#?????????? 2,6
+#??##????????????# 10,2,1,1
+.?.?.???????? 2,1
+.?????????##????? 1,4,7
+#????#?##?? 1,5
+??.??#??????..#?. 1,1,2,4,2
+#..???..?.#?? 1,1,1,2
+.#??#?#?.?.????? 1,4,1,3
+#?????????.???#??? 7,1,4,2
+#???##?#??# 2,5,1
+????.#.?..?#?#. 1,1,4
+?#???#?#?????????? 1,1,1,1,4,1
+??????..???????. 1,2
+#????#?.??##.????#? 2,3,4,1,4
+??###???#?.???####? 9,4
+?.?#?#??.?#??## 6,2,2
+?#?.????#???#.?#.? 1,1,5,2
+?.??.???.??? 1,1,1,1
+.??#?????#?? 5,2
+????.?.?#...? 1,2
+.?#...?#??#?#??#?#? 2,12
+???.?????##?? 1,9
+#?#??????.????? 7,1,2
+???#??..#?. 1,2
+???????#?.?.???. 9,1,1
+#???#???????# 1,1,1,5
+???#?????? 3,2,1
+.##.?????.?.#?????? 2,2,1,1,1,2
+.????..##?#?##????# 1,1,10,1
+??#?????#???#?.???# 1,2,1,2,2,1
+##??.?#?#?##?.???.?. 3,7,2
+.#???..???????? 4,4
+?#?##.?.?? 5,2
+??#??..?.??? 3,1,1
+?.#.??#????#??????# 1,1,1,1,10
+????.#?#???? 1,3,1
+????..???#?#?#???? 1,1,1,6,1
+.###???????#????.?? 3,8
+.#??????.. 1,1,1
+???.??#??????. 2,1,3,1
+?#??#?.?????##???.?# 6,1,2,1,1
+.??.#?????.??????. 5,6
+.???.#?##? 1,1,4
+???????.?##? 3,1,2
+.?#??#????? 5,1
+??????#??.##??#?. 7,6
+.????..????## 1,1,2,2
+?..#?.##?#?#????#?.. 2,8,2
+??##.????????#?? 3,5,2
+#?????????##?.?? 2,1,1,3,2
+.?#?.#?????##???? 2,2,7
+.?.?????????## 1,1,9
+?????.?#??. 3,3
+?#?#??..?? 1,1,2
+?.??.?#??.#????.#??? 1,1,2,5,1,2
+???.?.?##????# 1,1,8
+???##???##.???.? 5,1,2,1,1
+.????????#???###? 3,8
+???#??#??.??## 5,1,1,2
+#.????????.#? 1,4,1,2
+?????????? 4,1
+##?#?.???#?#???.?? 5,1,3,1,1
+??.?#????. 1,1,1
+???.?.?????#?????#. 1,1,1,6,1
+?.?????..?### 1,1,1,4
+??##???##???#??.??# 8,1,1,1,1,1
+?.#??#??##?.?.?.???? 1,1,5,1,1,4
+?.??##?.???.? 4,1
+..?#?????? 3,1
+????#??.?????#???#.? 5,1,1,3,3,1
+???????##?#?.#?????? 2,5,1,4
+??.?#??#??#?????##? 1,11,2
+.???????.???###?? 1,1,2,5
+.???#??#????##??? 6,5
+##?#??.??#.. 2,2,1
+.???.????? 2,1,1
+?...??.?.?#?###?##?# 1,1,1,1,8
+??????#?#?#??#.?... 2,9
+??????###???.#???# 1,4,2,1
+.?..??.???.# 1,2,1,1
+.???..?#??#?#??. 1,9
+???.????###?? 3,6
+?##????###???.. 2,8
+???#?#.??#?? 5,4
+??##?###???#???????? 9,1,1,1,1,1
+?..###??????????.? 1,3,2,4
+#??##????###??????? 14,2
+?###?#??#??#??.???# 4,2,5,1,1
+??.###?#???.. 6,1
+#?#?#?..??#? 1,1,1,4
+?#.???#??.#???##???? 2,1,2,2,6
+.?##.?##??#?????..? 2,8
+????.?#.?.?? 2,2,1,1
+#??.??????#? 3,1,5
+??.#???.??#?#? 2,1,1,5
+???.??#?????? 2,1
+???.?????#?.#. 1,3,1,1
+??..??..???????? 1,1,2
+??????#?????#???? 9,2
+??????#???#? 1,1,7
+???#???.????..? 1,3
+?????.???## 1,4
+.##???.##??.???.?#. 4,2,1,3,2
+.#?#?.??????????? 4,4,2,1
+?#???.???. 5,1
+?##????..##?..?#? 7,3,2
+????????????? 5,1,1,1
+.??#??#????????????? 1,1,1,5,1,1
+???.???#??. 1,5
+???.??.#.???. 3,1,1,1
+???...?#?? 2,2
+.?.#??##.??.?? 5,1
+?..????.?#?##?# 1,4,7
+.#.??????. 1,5
+.??????#...?? 3,1,1
+.????#..?.????? 5,2
+#?#???????#???##?.. 9,7
+###???????#.????#??# 3,1,4,3,1,2
+.?.##????#???#??? 1,4,7
+??????????#???#? 1,4,1,4
+??#??#.##????#? 5,3,3
+??.?##???????.?.#?? 1,3,1,1,1,2
+.?#???#?#?????#??##? 7,7
+#..??.???#?????. 1,1,1,5
+??.#.?#???##??.# 1,1,9,1
+???.??#??????##???? 1,4
+???.???#??.?#????#?? 1,4,7
+#???#??#?#.#??.?# 2,7,3,1
+.??.???????#??#? 1,1,9
+.?#?.????.???? 2,2,4
+.????.#????.?? 1,1,3,1
+??????#????#?...?? 12,1
+?##???#????#?#?.#??? 9,1,2,2,1
+??##??..#.? 5,1
+.???.?.???????.. 2,2,4
+#???#?.?????#? 6,1,1,1
+??#??#.?#?. 3,2,2
+?.??????#?#??#?????? 1,12
+?....??????# 1,2,1,1
+.?????#?????#.?.# 1,6,1,1,1
+????#?####???????? 1,10,1,1
+??#?.??.?? 2,1
+?.?.#.?.????#???.? 1,3
+.#?.#?#???#??#?? 1,3,1,3
+..?#???..?????.? 4,2,1,1
+??###?#???.?????#..? 8,6,1
+???.?#???##???#? 2,10
+?##??#???????????? 10,1,2
+????#???.??? 3,1,2
+?.???.????????#????? 3,1,7,1
+.?.?#??#???? 5,1
+?..???#?.?????? 4,1,1
+??#?#?.???.##?### 2,2,2,6
+.???.?#?#?#???# 1,1,7
+???#??..#???. 4,1,1
+?#.????.????#??.. 2,2,7
+????????#.?#.? 1,5,1
+?.?#..??#??? 1,1,3
+?????#???????#???#. 6,1,1,3
+.#.??#??.?# 1,4,1
+.##??.?##?#. 2,5
+????##??#?#?#?#?#?# 1,15
+?#?.#?.##?#?????##? 2,1,6,4
+..?????#?##???. 9,1
+????.#?###???????? 1,7,1,1
+.?#????????.??????? 9,4
+?.?#??#???????# 4,1,2,1
+???#?#?????.?##??# 8,6
+?#????#??. 1,2
+.??????.?.# 5,1,1
+?##??#.???#??.? 5,1,1,1
+?.?????????#? 1,1,1