Day 12
Part 1
sample12_1 = """
#.#.### 1,1,3
.#...#....###. 1,1,3
.#.###.#.###### 1,3,1,6
####.#...#... 4,1,1
#....######..#####. 1,6,5
.###.##....# 3,2,1
"""
sample12_2 = """
???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1
"""
input12 = """
????#?#???.??.. 9,2
?.#?????????###.?# 1,1,2,1,5,1
.???#????#?????#?#? 1,9,4
?#?.??.#?.??? 2,1,1,1
?????????#?###???.?. 1,9
????#?.?.?? 1,2,1
.???????#???..? 1,5
#????????#?#??#??. 2,14
?.?????.?? 2,2
???##??###???????#?? 9,4
.#.?.??..?# 1,1,2
.?????#??? 2,1,2
??.?..?#?##?????# 1,1,11
?.???.??.??#?. 1,2,2,4
...#??..????##??. 1,6
?????#.?##?????.??? 5,2,1,1,1
?##?#?.???#?.?? 5,4,1
.?.##???????#????.? 3,5
.?#???#?#..???.?? 6,1,1,1
.???##.???# 5,2,1
?#?#?#?.?#?.?? 5,3
.?#?.??.?# 1,1,1
?#???#?.???????.#. 2,2,6,1
##???.??.?.?? 4,1
.???#??.?#.. 4,2
??#??..#?..## 5,1,2
??##??#?????.??? 2,3,1,1
.????.?##????#?? 2,6,2
.?##????.?##???#?. 3,3,4,2
?#??????????#????## 2,1,1,3,2,4
?????.???????????? 4,1,1,6
???##?##????? 6,1
?.?..??#??#???.. 1,7
?#?????##??##????#.? 3,1,7,1,1,1
#???#???##????#??... 1,14
?????##??.?????. 1,6,2,1
???#????????#? 4,8
##???#..??##??#??.#? 3,2,1,6,1
???????????.#?? 4,3,2
?#???#?????? 1,6,1
?.?.??###...???#?.?? 5,5
..??????#???? 1,1
?????????????? 2,4,1,1
?#.?.?#?#?. 1,4
#?.?#????????#???? 2,3,8
?????#?#.????? 6,1,1,1
????#.??..? 4,2,1
?????????#?.? 2,2,3
???#???..?# 3,2,2
.#??.?.?.?##??##?#. 1,1,1,9
??#?#???#???##? 8,5
#??????###??????.??? 1,2,10,3
#?#?#??????#??? 1,1,5,4
#???.???#?????#?? 1,1,1,5,1
#?.?##??.?? 1,3,1
????????##??? 1,1,4
??..??.??##???????. 1,10
??.?????#?#??##???? 1,1,1,4,6
??#.?????#?#?? 1,1,3,5
?????##????# 1,7
??.?.??#????? 1,1,1,2
..?.???.??????? 1,1,1,2,1
????????#?#???#??? 2,1,8
?????#?##????????.?. 2,5,4,1
#?????..?.??##?# 1,1,1,5
.#??.????? 2,1,1
??#??##??.?#?. 8,1
.?????.#?. 4,1
.?#??#.????. 3,1,1,1
????.???..?#??. 1,1,1,4
?##??.??..#?#? 3,2,3
????#??.????.. 1,3,1
?.?##???##?.???.??? 1,8,3,3
??#??.#?#??? 3,3,1
.?????.?#???????? 1,3,6,2
??#??????????????#? 1,1,1,4,4,1
?.?.??#..???#?. 1,1,1,1,3
??#??....###??? 2,3
?????#?.###???.#?. 3,3,3,1
#..???.#???????? 1,1,2,1,2
???#???.#??# 4,1,2
?.??????????. 4,2
.#??..????? 1,5
?#?#?#???..??#??# 5,1,6
???#?????? 4,1
??#??##??.????? 7,2
..#????..#?#?.? 5,3
?..?.??#???#?? 1,1,2,5
#???##.??.?#?#? 2,3,1,5
????????.?#?? 1,3,1,2
#???..?#??? 1,1,3
#?#???.#..????#.#?? 1,4,1,3,1,3
#??#.???.#?#???. 1,1,1,1,6
???##????????#???.#? 9,1,5,1
?.#????#??.?#?.? 1,1,3,1,1
##?????.?.. 2,1,1
?#???#.#?#.??.??. 3,1,3,1,1
.??#???.?.????.#??#? 6,4,4
?.???####??.#???.??? 6,4,1
#.???#???#??? 1,4,1
???#???#?#??? 1,4,5
???#??.####???##?? 1,2,6,2,1
#?#.?????.??# 3,5,2
.#??.??#?? 1,3
??#?##???#??#..???? 12,1
???.??.???????#???# 1,2,12
??????#??.?#?##?? 4,6
.????.????## 4,2,2
.#????????????.##? 1,2,2,3
???.???#???..????#? 1,5,1,1,1,1
???????#?. 3,4
.???###?#????..? 1,9
.#??#????#?.??#?... 6,1,4
#????#??????.?#?? 1,1,8,1,1
?.????.??#.? 3,1
.????.??.??? 1,1,2,1
???????.?.?.??.?? 3,1,1
#????#????#.??? 1,8,1,1
.???????.?#?#??# 2,4,2,4
#??#???.#??.????##? 2,1,1,2,1,5
?#?#?.????????? 4,1,1,3
..?.?####??.?? 1,7,1
??###????#??? 4,5
...?#?????.???.??.. 2,1
.???????.????##.??# 4,1,1,2,2
.???.?.?#?? 1,1,2
#???...#?#??#?. 2,1,7
??###?#????????. 8,1,2
.??.?#?????#??? 1,9
??.?????#?#?????? 1,7
.????.#??? 4,1,2
?#?.?#?.??# 3,2,1
?.?#.???#?# 2,3
????#.????. 4,1
???????????#?????.? 1,1,8,1
.???##???#?? 1,3,1,1
????.????.#??? 1,3,4
????????.#??#..#?## 4,1,2,1,1,2
..??.?.#???##?.??.. 1,6
??.#????????#?## 4,3,4
??#??????#.##?# 5,2,4
???.#???.? 1,1,1
?#?????.?.?? 1,2,1,1
#????.?.#?? 1,1,2
?#??#????#??#?? 1,2,9
?#????#????.????.?? 10,1,1
????.????.?? 2,1,1,1
?#??#???.???.#?##? 7,3,1,2
??.??#???...????.? 5,1
???????.?? 1,2,1
.#.?####.. 1,4
?.#??.??#?##???. 1,2,5
??.?#??????? 3,2
??#?????????.?? 3,1,1,1,1
?????????? 2,1,1
???????????..? 3,2
????##???? 6,1
?#????##?# 3,4
????????.?#? 4,2,1
####..#?..?#?.? 4,2,1
?#?..?#?.?#.??? 2,1,2,1
???????..?#? 3,1,1,1
?#???????. 1,1,1
#.????????#???.? 1,1,1,7
?#?#??#??? 1,4,2
..??.?..?.??. 1,1
..?#???.???..? 4,3
?#?##.?.#? 4,1
.??#?#.?.??.???? 5,1,1,1
?#??#???????. 5,3
#?#?#?#??????. 1,7,1,1
????????.?. 2,2
???.??.????????#. 2,7
?.#..??????#????.? 1,10
??#?##??.???#?? 3,3,5
???????.????#?.. 2,3,5
..???????????? 1,3,1
?..??#??.?#????? 1,1,1,1,5
????#?..?? 5,1
???#.??#??.????? 4,3,3,1
?#?#??.??.?#?? 3,1,1,3
??.???##??#? 1,1,5
?#.?.???.????? 1,1,3,2
#???..??#???#?????? 1,1,1,3,1,3
??????##????.?..# 8,1,1,1
#????##??#? 2,5,1
#??.???#?..? 2,1,3
???.?.????????#.???? 1,1,8,3
??.#.#?.#???##????? 1,1,2,1,6
.??????????.???# 3,3,3
???#?#????? 4,3
?.????????#????.? 1,2,7
???##?#??.???? 6,1
??#???.?.#??##? 2,1,5
??#?.??###? 1,4
??###????.??#? 7,1,2
????.#????##??? 1,2,6
?#???#???# 7,1
??????#??#..?? 10,1
..##????.?? 2,2
.???.????#??.??????? 1,2,2,1,3
????#?#??#??.. 5,2
?#??.?.?..#??? 4,1,2
??#???.#?????# 3,2,4,1
???##??##.??#?..?#.? 1,6,2,1,1
#?#?#???????#???? 6,3
??????.?#?? 2,1,3
???#???#????#?..?? 2,8,1
????#?#???.??.?. 1,7,1,1
?????.?##?.? 3,3
?????.#?????? 5,1,2,1
?#...???#??#?????.?. 1,4,7
???#????#?? 2,2
.#?#???.???# 1,1,1,1
?#??#??.#?.?.?#??? 7,1,1,2,1
??.#.?????? 1,1
#?#?????#?#?? 5,1,1
??#?##????.???????? 1,4,1,1,2,1
?#????.?.#? 1,2,1
##??????#???#??#? 13,2
.???###?.????##? 5,4
????#?.?..???????? 3,2,1,1,1,1
?.?#??????????.? 3,1,3,1,1
.#?????#.#????? 1,1,2,5
???????#.. 1,1,2
??##??#??#?.#??#... 5,1,1,1,2
..#??##???##????##?# 16,1
??????????? 1,3
??#?#?.????####??.? 3,8
?????.???#?..#?## 2,1,4,4
??.???????##?#??#??? 1,1,3,10
????????#????#??.?# 2,10,2
?#?#??????????????#? 11,4
.#?.#???##. 2,6
??#..#??.?..# 3,3,1,1
???????##?.??????.?? 10,1,1,1,1
????#????????????#.? 3,12
???.?#.?#?. 2,1
.#?.???#??? 1,1,5
????#.#???#? 1,2,2,1
.?.?.???#????#? 1,5,2
???.?#???? 1,3
??.??#?#?.??# 1,5,1,1
.#.????#??????? 1,1,2,1,3
#????#??..?..??????. 8,1,3,1
?#???.??###?.????.. 5,6,1,1
???#???.??? 4,1
????#?#????????#?? 10,4
?.?#???#.?.?###?.?. 1,2,1,1,4,1
?##??????????????. 5,3,5,1
.??????????.???.#. 4,1,1,3,1
.?????#..??.??#..? 4,3
...??#?.???.?##??#?. 2,7
?????###?#???#. 2,6,2
????.??#.? 1,1,3
.?.???#??. 1,4
??.????.?????.?#. 1,2,4,2
??.#???#?? 1,7
.????#??#??#?# 1,11
?...#??.?##?#??????? 1,5
###???????????.#.?? 13,1,1
.????##?????????.?#? 9,1,2,2
.#?##?..??????## 4,1,2
?##?#?????.#??.???? 6,2,3,2
?.?#??##.? 1,6
#????.???.???# 2,1,3,4
...????##???.?### 6,4
.?.?##??????#????? 6,3
.??.#???#??#..?#?..? 1,1,5,3,1
???##?##????.#???? 11,1,1
?????#????????? 1,1,2,1,2
#???..?????? 1,2,1,1
.??????#??#??#??. 7,6
.???????.???#?? 3,1,1,1,1
??#??#..????? 4,2
.????#????.??.? 4,1
#??#??.??.##?.#.?? 1,2,1,2,1,2
??????#?#?#??#? 1,1,7,1
?????????..??? 3,3,1
?.#??????##?##??? 1,1,1,6,1
#???.#?????#.????? 1,1,1,1,1,3
#?#.?#????#?##??? 3,12
#.????#..????#?#? 1,1,2,7
?#??#????.#???? 7,2,1
?.#..??#??##?#.#? 1,1,6,1,2
?#??###?#?.?????? 3,5,1,4
.?.#???#??????##.??? 1,5,7,1,1
?..???#.?. 1,1,1
?#???#??###?#.? 5,5
??????????#???#..?? 6,1,2
???#????.???## 5,5
????#??.?? 1,3,1
?????#?#.? 1,1,3
???#??#??????? 1,1,2,4
???..??#.???? 3,2
????????.#??.????.?. 8,1,1,3,1
?????.?.###?#? 3,5
?.?#?#????#??#????? 1,8,4,1
#..??#??.#.??. 1,3,1,1
??.?#?????#?.# 8,1
.??#???.?#.?#???#? 1,1,2,2,6
.?#.?##?.. 1,3
?#????..##??#??? 6,2,5
??#?#??..#??#? 7,4
#?#???#.#??.??????#? 3,1,1,1,1,6
?##.???????#???? 2,11
#?#.#?#?????###?##?. 1,1,14
?#????#.?? 5,1
??????????.??.?? 3,1,2
??????#??????????. 1,1,8,1,2
??.#?##???? 2,4,2
#.?#?##??????.#???? 1,8,1,2,1
??#???????#.#?#?# 5,1,2,3,1
?????????##???#? 2,1,4,1
?#?..?..?????.?? 3,1,1,1,1
.#?????#??..???##??? 4,3,8
?????..?.?? 2,1,1
#?##?.???#.???#? 4,1,1,3
?#?#?#?###..?.#?# 1,7,1,1,1
??#?..?.##??# 2,1,2,2
??.??#????# 2,4,2
??#?????#??#???# 13,1
??.???????#?#? 1,8,2
.???#??#?#????#???#? 1,15
?????..???. 2,2
.?.###???? 1,5,1
?##?.????#????? 3,9
.???????????##?.? 1,10
??.??#??#????.? 1,7,1,1
?#??.???#?#??.#?#? 1,1,5,3
????.###?? 2,5
??#???##??? 2,2
?.???.#?..?. 1,1
?.??##?##??##?#????? 1,12,1,1
???????????#?###? 2,2,3,3
#?.????##?##????.? 1,9
???##?????.##???.?.? 6,1,3,1,1,1
???.###???##??#..#? 1,1,11,1
#?..#???????#?# 1,3,6
??#???#?.???#?. 8,3
#??#.????#?##??#.? 1,1,3,7,1
.?.?.????? 1,1
?.?.?#?.??#? 1,1,1,2
?#????.???????# 1,2,3,4
??????#.???#?.. 1,1,5
???#?#?#??#??#?? 3,1,7
??#????.???????? 4,1,2,1,2
#???#?.??? 2,2,2
?????#????? 2,3,2
???.?#????. 1,3
##?..???##??? 3,6
.??.#???#?? 2,2,3
.?????#?????##?? 3,1,1,4
???#?????##??? 2,4
????.#???#??#???.? 1,11
???.?.???? 1,1,2
#??###???#???.#? 1,8,1,2
.????.??## 1,1,2
??????????#??????# 1,5,2,1,2,1
.????????#?#??#.? 5,4,2,1
?????.???????#?.?? 4,4
??#?.??###..? 2,5
.?????.??. 1,1,1
??????.??. 1,1,1
.?#?.?#??##?##?? 2,2,6
##?.?#???? 2,3,2
?..?#.##???????#?? 1,1,4,4
??????????##?#? 1,5,1,4
???#?????.? 2,3
?#.?#????.???#??? 1,3,1,4
.?##???.??? 3,1,1
###.????.#????#?##?? 3,2,2,7
.?#??#????#? 3,1,2,2
.#???#?????#????? 5,1,1,3
??#??#?????.???????. 9,4
..????.?.??????.??? 1,1,1,1,3,2
??.????.??.. 1,1,1,1
##???#??????.##??# 8,1,3,1
?????#??.# 7,1
.??.#?..??? 1,2,1
??#?.#?????. 2,1,1,1
.??#.?###?????.#???# 1,1,4,4,5
.??.???#?.#???# 1,2,2,2,2
##???##?.??.?## 8,1,3
?##??#??#?. 2,5
???#.???#???????? 4,10
?.?#?#????? 1,2,1
?#??.??.?..??.? 3,1,1,1
.???#.#??. 1,1,1
?#?.??.????.. 2,1,1,1
???????#?.. 4,2
????.?.??????. 1,3
???#??#???? 6,2
????#??###.??#??. 1,1,1,4,2
??????????# 2,3,1
??#?.??????##??.? 2,3,5
????...????#?# 1,1,7
.?#???.????????.? 4,5
.#?#??.?.????...?.## 1,1,1,4,1,2
?????#?.?..#. 6,1
???..?????.?#?# 3,1,3,3
????#??????#??##???. 8,7,1
#??????##?##.???? 1,7,2,2
#?.#??#????.??. 1,2,1,1,2
?#????#??.?? 3,3,1
?#????????????#?#? 5,4,5
??????????. 2,3,2
???????##?#????#?? 1,1,1,6,2,1
??#?#?#??.??. 7,1,1
??.#???#??????#? 2,1,1,5,1
?.?#.????? 1,1,1
?##???#?#???????.? 8,2
.#?##??????. 4,2
#?.###????#?.?.? 2,5,2,1,1
...??????.??.?##?. 3,4
.#?.????????#? 1,1,1,4
?.?##.?#??###?#?##.? 3,12,1
??#.???#?#?#???#? 1,1,8,2
.??#.?.????????.?? 1,7
???????????. 1,1,1,1
.??????.??. 1,1,2
.##???.?##?.??#.?? 4,3,3
.#??.?..?#???? 2,1,3
????#????? 2,2,2
.#??????####??.. 1,8
??..??#???.# 2,3,1,1
?#????#??????.? 2,4,1,1
?#?.?.?.????????## 2,1,1,1,4
.??#?#?.?#?#?##?##?? 5,10
?#?.?.?????#.?#??? 1,1,1,1,2,2
.???##.?#???#??? 5,3,5
????????.???#?.?.?? 1,4,1,1,1,1
?#?????.?? 6,1
.#?.?????##??### 2,10
?#?????????.? 1,6
?..???????##?#?#?? 1,13,1
.????????? 1,2,1
???????#?.??? 1,6,1,1
?.##??...?. 4,1
??###????##?? 5,3
#??#.??#.???#?##?#?? 2,1,3,1,8
.????????#????.??? 2,1,5,3
???#??????##?????#?? 1,1,1,10
.??#????.???##?????? 1,1,10
###??.?????.?? 3,1,4,1
????.###????#? 1,4,2
..?????????. 1,7
???#.#.?##???? 4,1,3,1
#??#??.#?.?. 2,2,1,1
????#?????#???#? 9,2
.??.##?#?.???? 2,5,2
??#?#.#?##?????? 3,1,5,2
.??#?.?#?????..??#. 2,2,3,2
#?.?#??#?#?#.? 1,8,1
??.?#?.?.?#??.#? 2,2,1,3,1
#.#?????????.????? 1,2,4,1,1
????..??????#.?# 2,3,1,1
..#???#.??.?? 5,1,1
#?.???#??? 2,6
.##.?.#.??#???#?## 2,1,1,10
..????..#??.. 3,1
#??????#??#. 1,1,1,4
??##????..????.?? 3,1,4
????.####?. 2,5
??..#???#?##?? 1,10
???.#?????.? 1,1,1,1
??????.##? 2,3
#?#?###???#??? 1,7,1,1
.?.?#.????????.? 1,4
??##.??##..#?#?#??? 2,4,1,1,4
???###?.????? 4,1
?..?.#???#####? 1,1,1,7
?.###???.??#??#???? 3,1,1,8
?###???.???? 4,3
?.?.##.#???. 1,2,2,1
???.?????#??#??# 1,6,1,2
??????#??.???##?? 9,1,4
??.????#??? 1,3
???..?????? 2,1,1
????.?.##??????. 1,1,2,2,1
.?#??##???.??#???.? 7,4,1
#?????????#??#.?? 6,7,1
???..##???? 1,2,1
###?????.?????? 3,2,1,2,2
???????##?? 5,3
???#???.??#???? 1,1,1,4
??#..??.?#?###????? 1,1,6,4
?.??.??#?? 2,4
?.????#?.?? 2,1,1
????...???????.? 3,1,1
..##?????#??. 4,3
.??..##???? 1,2,1
??.??##?#????. 1,8,1
?.#.???.##..#????# 1,1,2,2,1,3
?????##???#...?? 9,1
??#?.?.??#. 2,1,1
??.??.#???#..?#????. 1,1,1,2,5
????.???#?????###? 1,1,4,4
???????#?#??.???. 2,8,3
?#?#.?.#.?.????????? 2,1,1,1,3,3
?????.##???##?#???? 1,13
????.??#?? 2,1,1
????#??..# 1,3,1
?#??#???????????? 8,1,1,1
????#.???.#???? 1,1,2,5
????????##?#??##??#? 1,2,13
?.??##?#?#??##? 1,12
????????????#?.?# 2,1,2,4,1
#?#????#?. 1,3,2
????#??.?.#?????#? 6,1,1,3
???#??#???#??????# 1,6,1,1,1,1
??.#???###?.#??????. 2,1,1,4,1,5
??.??????###??# 1,11
?.#?#?????.????.?## 7,3,3
.#.?#.??##?#?#?.?? 1,2,8,2
?#??###?.?# 1,5,2
..#??.??????#?#?? 2,9
??#?.?.???##?????#?? 4,1,9,1
???.???#???#?? 2,1,6,1
..???????? 2,3
??????..#.? 1,1,1
????????????## 1,1,4,3
????##???#.?##?#??# 6,1,4,1
#????.#.?#?##?.#? 2,1,1,4,2
#??????...#??#????? 3,2,6
?#?##?.?????.? 5,2,1
??##.?????#?. 3,2,2
???#?.??????##. 5,1,1,4
??#???#??#???##.#.? 14,1
???????..?#??? 5,1,5
??????#?#?.#?? 2,4,1
????#?????. 1,5,1
#.?..##????#.?#???# 1,1,3,3,5
??#?#???#????#.???.? 14,2
.????#?.?? 3,1
???#???????.?????? 1,3,4,1,1,1
???.???????.. 1,2,2
?????.??#.? 1,1,2
?#..?.?#?##????#?.. 1,11
#?.?##??????#.?. 2,2,5
.?#???##???.? 6,2
??#?#????#.???# 7,1,1,1
?.????#??????#?????# 1,3,2,3,1,3
???##?#???##..?#??.? 1,3,1,3,4,1
.?.?.#?#?#?##?##?.?? 1,10
.?????#??#???#?.. 2,5
???..????.?. 2,1,1
..##??????.?? 4,2
????#??.???#??????? 3,1,9
??????..??#???? 3,3,1
...#.#??????##?. 1,1,2,4
???#.??.?#??? 4,1,2,1
???.?#??.#??###? 1,2,6
???#?????????##?.? 1,2,1,6
???????????.???. 9,1,1
?.?###?##???. 1,3,3,1
.#??.?.????????. 1,1,3,1,2
.?.#???..??? 1,1,1,1
#?.??#.?.. 1,1,1
#.#?.???#??###???#.? 1,1,1,11
.???..?###???#?##?? 2,6,5
?.??#???#?##??.?. 4,5,1
??????????#????.?. 2,8,1
.#?....????????. 2,1
??????.?##?. 1,2,4
??????.?#?#??? 2,1,4,1
?.????#?#?????.? 1,7,1,1
#???#???..#.??#. 1,1,4,1,3
#???#?#?#.# 2,5,1
.????.#?????.# 1,1,6,1
??#?????.#???##??? 3,1,1,2,3,1
##???????#?##.??. 13,1
.??.#?#?????? 1,1,6
?????????##?? 1,2,5
??.??.?#.??#?#???#?? 2,1,1,3,6
??.??.#???.??.? 2,1,1,1,1
.??#?????? 2,3
????.??#?##?.?# 1,1,6,1
???#???#?#?? 1,3,1,1
#..?#????????.#??#?# 1,9,1,4
???#????#.?.???#? 3,2,1,4
???##??.??.?#?##.#? 5,5,2
??.?#??#.??.? 2,1
#.???#????.?#?.?? 1,3,3,3,1
.?????#?.??.?? 1,2,1,2
???.??##????? 7,1
???#????.?#??#????? 3,8
????#???.???##? 5,1,1,3
?????????????. 5,1,4
????.#??#?# 1,6
????...?.?#??.????? 1,1,1,4,4
???.??????#?????.#. 1,3,2,3,1
?##????#?#?#?????.? 4,6,1,1
..?#???....?##?##?? 3,7
?.?.?#?.?.?#???.?. 2,3
???#?????? 4,1
..?.??#??.?#??? 4,3
???..????#??.???#?. 2,5,1
?.#?.??.?? 1,1,1
????#?###.???#?#?#?? 7,8
????#?#????#?..???.? 4,7,2
???#?.?.?.?. 1,1
?.##.??#?. 1,2,2
?.?????????????? 4,4
.?#.?.??.????#??? 2,1,7
?.???.????. 1,1,1
?#??#???.?##???#??? 5,9
??#?????##..?# 4,3,2
#????????.?#??#.#.# 9,1,2,1,1
.????????#?? 1,2,2
???????.?? 1,2,1
???????.?##.# 2,1,3,1
???.?#?####??#??#?#? 2,7,7
?.?...??###?????? 1,5,1,1
?.???#?????#????? 10,3
??##?.??##????#????? 4,5,3
#?.???###????. 1,2,6
?#.?????.?. 1,4,1
?????####?.????##? 1,1,6,2,3
..?.??????#????###?? 1,16
???..?#??#?#?????? 1,9,1
?#??#??.?#???#?? 1,4,8
?????????.?##???.?? 1,1,3,3,1,1
?.?#??##??##????.?. 10,1
##.?.?#??. 2,1,4
#.?.#????????#???#?? 1,1,1,1,2,8
????##?#??? 1,4
??????##?? 2,2
?##???.#?#??? 5,3,1
??..????????? 1,2,2,1
????????????? 1,1,5
??..#???##?.?.?# 1,3,2,1,1
?#??#??##?????.. 4,2,1
?#??#??.?#??#??. 5,5
##??????#???? 10,1
#??#??????.?#?? 1,4,1,2,1
??#?#??.??.?.???.??? 7,1,1,1,1
?##?#????. 6,2
????????###???????? 2,1,11
??????#??????? 3,1,2
?.?#.?????????#???.? 1,1,1,8,1,1
#???#?.???#??#?????# 1,2,5,3,1
???.??#.????? 1,1,2,1
.????..#?##??#?#. 2,9
#?#??????? 5,1
##???????#??.?# 3,8,1
????#???#???? 1,2,1,3
?.#.?????###?#???? 1,10
?????...#??.#??.. 4,2,1
..??.??????.? 1,2
.?.?.?.??#.?. 1,1
..??#.??????? 2,4
#??#???#???.?#??.?? 6,1,2,1,1,1
..???????.??#??.?? 5,5
???.?#??..?????. 1,4
?.???#?#???????#. 5,1,1
????##???# 1,5,1
#???##???????#? 2,4,2,3
?#?##??????? 6,1,2
??#??###?????# 11,1
?#??#?????..#??###?? 8,7
#.?????.?# 1,4,1
#?##?????????#????? 5,10,1
#???#??#?.??.?#??#? 9,1,1,1
?###?????#? 5,1
???.????..#?###??. 1,2,7
??.?.?.??#?#?. 2,1,5
??#??##?.???#?#???. 4,3,1,1,2,1
?????#??????##.#.#?? 2,9,1,1
#?.?.#?.??????? 1,1,1,1,2
.?#??????????.??.? 6,2,1,1
?.??..?????#?.? 1,6
.?????.???#?????# 1,2,3,1,2
.#??#??#?#??#..?##? 1,2,1,2,1,3
?.?###?????#?###??. 5,8
??#?#?.???.#?##???? 1,1,1,1,5,2
????.???#???????.??# 1,1,5,2,1,1
??#.????##???#?..#. 3,4,1,1,1
????#?..?#.????? 1,1,2,2,1
??#?####????####???? 8,8
???.#?#??#.?? 1,3,2
???#???##?.#.??????? 1,7,1,1,1,1
?????#?.#?.??##.??.? 5,2,1,2,1
?#??????#??????## 9,2
?#??#?#??#?#???? 1,1,10
???????#?#.?# 1,5,1,2
??#?????????. 1,1,8
??????.??? 4,1
?????#?.??##?##.# 2,3,6,1
?#?#???????#??# 6,4,1
??##?????????#??#??? 1,15,1
??#?#?###????#..?? 8,2,2
??#?#?#??.????????. 6,1,1,1,1,1
???.?.??????#?.??? 2,1,8,1
????#???.?.??? 6,2
?#?.????.?????###### 2,4,1,1,7
#????????#?#??#?? 2,2,9
#????##???.?#.. 8,2
??#?????#????#??#? 3,2,10
???#??#???? 4,2,2
..?.???#.#??#?? 1,3,1,4
???#?.????#? 3,6
.??????##?#?.? 1,2,4,1
??.???#?.?#?##? 1,5,5
??##?#??????##??##.? 4,1,9
.#??#??.?##.? 4,3
.??#??#???#????? 3,7
???????#??#?##??. 5,8
.????????????#?????? 2,11
.##????#??#??.????#? 11,4
?##??..?.? 3,1
???#.?.?#?? 1,1,2
..#??????.??#??? 7,5
??.#?#.????????#?# 1,1,1,2,7
.#????.????#???.? 5,7
#??#???.??? 4,2
##???.?.#.?.#??.# 4,1,1,1,1
?##?.???#?? 2,2
?.??.?#???????###?? 1,1,6
???.?#???.?? 2,1,1,1
.?..?.##???#???# 1,6,2
???#???.#..? 7,1,1
.?.?..#???????? 1,8
??.#?##??????? 1,8,1
?.?#??#?#.??#.#? 1,2,3,3,1
????##?????#?.. 1,2,1,1
???#.??.?????? 1,1,2,2
??###?#?#.?..?.? 9,1,1
..?????#?##? 3,5
??#????.??? 6,2
????##?.??????? 6,2,1,1
?#?#??#??.??? 8,2
?#?????#??. 3,3
??????#?## 2,5
????.#???? 2,1,1
.#?#??..???. 5,3
?????#?##???? 1,2,5
??.#.??.#..#.????? 1,1,1,1,1,3
?????????.? 6,1
?#?????#.??.# 8,1,1
?.?#?#..???? 4,2
???#.????#? 4,5
#??????.???? 1,1,1,3
??#??##????.????? 7,4
#..???????????.??? 1,5,1,1,1
.??#?.??????? 3,6
.???..?#?##? 2,5
?#???#??????#?????? 4,2,1,3,3
??.???????##?# 1,7
??.??.?#.? 2,2
?????????.#?? 2,1,2,3
#.????????#?????.? 1,1,5,1,1
???????.??#? 3,1,2
?.???#??????#.?. 5,1,1,1
#?..?##?????#?#????# 2,5,6,2
?????#.??.?###.#??# 4,1,3,4
?.????.?.? 1,1
???##???.?.?????? 3,1,1
##?.#??????.??? 3,3,1,1
.?????#?#?#.# 1,7,1
#?.???#?????. 1,4,3
?#????.#?#???. 3,1,6
?#????????#????? 4,7
?#??..??.?#??#??#.? 4,2,2,5,1
??.???????.??? 3,1,1,1
???.????.?.??#???.? 1,5
?#???.????..?????.?? 3,1,3,4,1
???#??.#???##???? 1,2,1,8
.#??#?#???#??? 7,2
????????.??#.?? 1,1,1,3,1
??##???#??#. 3,4
???#?.?.?. 1,1,1
??.???????.? 2,4
?#???#?#????. 6,5
?.??##?.?#?????? 5,8
##?????..?.? 3,1,1
..??#??.#???##???? 4,7,1
???.?.##?.. 2,2
?.??????.?.?#??.??#? 4,1,4
.??#?###?#??#????.?. 14,1
????.???.?##??.???# 2,1,5,1,1
.?????.???????#.??#? 4,1,1,4,1,2
???...?????? 2,1,2
??##?#.??????#.? 1,2,1,1,3
?.?##???#? 4,1
.#????.?#?? 3,3
??#??#?????#?.#?#? 7,2,4
???#???#?????#???# 14,2
.?..????????#????##? 1,1,13
????#?##.?????.??#? 8,1,2
?#???#?#???? 1,1,1,1
?#...??..? 1,1
#.???#??.? 1,3
???????????????. 2,4
.??#.???.#?#?# 3,5
..#???????.????#??? 1,2,1,5,1
?#?????..??#?? 5,3
.#?##??.??#??? 4,1,1,1
???.??.????# 1,1,1,4
????#?#??#?? 1,2,1,1
?#?#?.??##??#??. 3,6,1
???##???????#???.#? 1,4,1,4,1,1
#??.#..#?#?? 2,1,1,1
?..??#????. 2,1
????????.?. 1,1
????????????? 2,1,1,1
??#..??#???#?##??# 1,1,1,11
???????????? 1,3,3
..???.????#?#??#?? 1,5,3
?????????.##??? 3,1,1,4
???????#?#?#???. 1,9,1
#?????#?#?.??#????. 5,4,1,1,1,1
????.#.?.??#?.??.. 1,2
??.#??.?..????###?# 2,1,1,1,1,6
????#.?.????#??. 1,2,1,4
?????.??#????.???? 3,3,1,1
?..#?#??#?#?? 1,4,4
????.?#??? 1,3
?.#?#?######?. 1,10
#???#???#.?.?#???? 3,2,2,1,5
#????.???????.#??? 2,1,4,1,1
???###??????? 6,2,1
????.#??#? 1,1,1
???#?#?#?#????.#???? 14,1,2
..?????.??? 4,2
?????.??#?#????? 3,7
?.##??#??##?#????? 3,5,2,3
..??#???.?#? 1,2,2
?#??#????##??#?. 2,4,3,2
##???#?.?#???.?? 3,1,1,1,1
??#????#??.#?#??#.#. 7,3,1,1
????#?#.??.#? 4,1
???#?.???? 2,2
#?????????????.? 1,9,1,1
????#?#?#.??? 8,2
.?????????#?? 1,3,2
?.???###?.??#?#?##?? 1,6,8,1
???.????#?.#???##. 2,1,2,1,3
??##???#?? 2,1,1
..?.??.?##?# 1,5
??????#??.?? 8,1
???#?#?.?#?.?#?? 2,4,1,2,1
?.#.?????#?##?#???.# 1,3,6,1,1
??.????????? 1,2
.????????? 2,3
?????#?#?? 1,4
??????#??#?.????? 1,4,1
?#????#.??##? 1,3,2
???###?#???#?#??#?? 2,11,2
??#???.?????#???? 4,5
??.#????#?..#? 1,1,5,1
???#?????.#.??.?? 5,1,1,1,1
??#????#?.#??. 4,2,1
?.?????#????##????? 1,1,2,1,7,1
?#?.#?.???.#?## 1,1,1,4
???#???.?#????##? 1,4,4,3
??????.?##??##????. 1,1,1,6,1
..?????.##??? 3,2,1
?#?#.?????#?# 3,2,4
?.?##??#???.? 1,7,1
????#.???#??#?## 4,1,1,2,2
?#??###?.??.?#? 7,1,1
???????.#?#?#?????? 4,6,1,1
??#????.#??? 1,1,1,1
.#?#??.?.? 1,1,1
##?#??.#???#? 4,1,2
..????#???#. 2,1,2
?????????.? 1,4
?#####??##?.????#. 11,1,1
####?##.?.?. 7,1
#.?#??.???.###? 1,3,3,4
.#????#???? 1,3
??????#????.??? 9,1,1
????#?????#? 3,1,2
?????##?????#?.? 7,2,1,1
????.##??????#??##?# 1,3,2,6,1
?#????????????. 7,4
???#.?.?#?????##?? 2,9
???..??.?..#?# 1,2,1,3
?#..???.?.#?.????? 1,3,1,1,1,1
??.??#????.?##.? 2,3,2,3
???#??#????? 1,1,2,1
????##??.?????? 2,5,1,2
#?????#.#?#??#??# 1,1,1,7,1
???#??#??.??. 1,4,1
??????#.?#????#? 5,2,3
?.??##??????##??#?# 15,1
??.???????##??#??? 2,11,2
???#??#??..#???.? 5,2
?.#????????#...#? 3,5,1
???#?????#??.?#?##?? 1,1,2,3,5,1
#?#.#?????. 3,3,1
?????.##.??#???? 1,1,2,3,1
??.?#?#????##??????. 1,3,5,1,1
.?????##??.#??. 7,3
#.?????????#?#???. 1,3,6,1
?????#.?.??#??#.? 2,1,5
??#?..?.???? 2,3
?.#.?.?????##?.#?? 1,1,1,1,2,2
.??????.?. 2,3,1
?.??....???? 1,2
?###..??.#????#??#? 4,2,1,1,2,1
?#?.?????#??.#?.?? 1,8,2,1
.????..?#???????? 2,10
.#?????##?? 4,3,1
????#?#?????#??.? 8,2,1
?#????????##??? 3,6
?.??????.???????#.? 1,3,1,2,1,1
???????????????#?..? 2,10,1
#??##??.????#? 2,4,1,3
#?????.??. 3,1
?????.?#??? 1,2
.#??#??#?#??##.?.?# 13,2
?#???#.??? 1,2,3
?.?####?#??.?.?#? 7,1
.??.?.???? 2,1,1
#.??#???.??????????? 1,4,2,2,1,3
?.?.##??.?. 1,3,1
????#????????? 6,5
.??.????##.? 1,5
???#?...#?#??? 3,4
????.?????#?? 1,6
??..?..???#?? 1,1,1,2
?#??#?.?###.# 5,3,1
.?##?#?.#??#???? 6,1,6
.##???#????#.???? 8,2,1,1
.????#.??#..??.##?. 5,3,1,2
?????.??#? 2,3
???####??????# 10,1
.?#??..#.?? 3,1,1
?#??..#???.?? 3,4
#?..???#??. 2,1,2
???????#???###????#. 1,13
????##???#...#??#.? 2,2,1,1,2,1
???#???..? 3,1,1
???.?.???? 1,4
?###????????.#? 8,1
.???#????.?.???? 4,3,4
?#????.???. 1,1,3
??????..?..?#??? 4,1,1,1,1
?????#.???#?. 4,2
?#?#????..????? 1,1,2,1,1
?#?.##??#?. 2,3,1
????.?#?#? 2,2,1
??###?##???#? 5,2,2
?#??#####??#.?.#?#? 2,8,4
??#?????????#? 3,2,3
#???.?#??? 2,1,1
??###?##???#???.??.? 8,3
??...#?#?.#??? 1,3,1,1
####????????... 9,1
.?#?...??#???#??.? 2,6
?#???????#???#???.? 1,1,1,4,5,1
?###???#?.#?.?.?#? 3,1,2,3
?????.?????.?#??? 4,4,3
??#?.?#???? 1,4
#.??#?##????? 1,5,1
#.???????#???#? 1,1,1,2,2
???.?#???????#???##? 2,6,1,6
?#.??#..???#?. 1,1,5
?.?##?.#??..????#? 1,4,3,5
.?#?#?..??? 4,1
?????#??#????????? 2,3,3,3
??.??????#?##?#??#?? 2,10,1
?#?##???????.??. 7,1,1
?#????#?????##?????? 7,1,5,3
???#?#.??? 4,1
?###??##??.?#?.??#? 10,1,2
.?#?#?.#????..????? 4,1,3,4
#???????.???#?????.? 8,1,3,1,1
?.#??#.?#??#?#??#? 1,1,7,2
#?#?????#???.?.. 6,3,1
?.#?#????????? 1,6,1,1
.#????#?..? 2,3
??#????.???#.?????? 6,1,1,1,1,1
??..?????.????????? 5,3,1,2
????????#?? 1,4
?.?#?#.###?.#??.?? 1,4,4,1,1
????.?????? 1,4
.??#?#????# 7,1
.#.????.?#? 1,1,1
###???????????.#.#? 11,1,1,2
.#?#???????#?? 4,2,3
###??#?.###?#??. 4,1,5
##??#..????? 3,1,5
?.?.????#?.??????? 1,1,3,6
.#?#???.??##.????.?. 5,4,1
.?#????#?#?.?#.?? 10,1,1
???###?##?????#??? 12,1
#.#????.?#????#?.# 1,5,2,4,1
.?.?#???#??#?.#.? 1,2,2,1,1
?#.?.????#?. 1,4
..??##?.?????? 5,1,1
???.?##??????#?##?? 1,3,9
??????#??? 3,3
???#????????????.??. 7,1
??.??#?.#??#?.? 3,1,3,1
?.???????#???#?.#?. 1,12,2
#?#?#??.?.?????? 3,2,1,6
????#.??##?? 3,1,3,1
"""
find_ways = fn springs, cur, numbers, find_ways ->
case {springs, cur, numbers} do
{[], nh, [nh]} ->
1
{[], 0, []} ->
1
{[], _cur, _count} ->
0
{["." | st], 0, numbers} ->
find_ways.(st, 0, numbers, find_ways)
{["." | st], nh, [nh | nt]} ->
find_ways.(st, 0, nt, find_ways)
{["." | _st], _cur, _count} ->
0
{["#" | _st], nh, [nh | _gt]} ->
0
{["#" | st], cur, numbers} ->
find_ways.(st, cur + 1, numbers, find_ways)
{["?" | st], cur, numbers} ->
find_ways.(["." | st], cur, numbers, find_ways) +
find_ways.(["#" | st], cur, numbers, find_ways)
end
end
solution12 = fn input ->
input
|> String.split("\n", trim: true)
|> Task.async_stream(fn line ->
[springs, numbers] = line |> String.split(" ")
springs = springs |> String.split("", trim: true)
numbers = numbers |> String.split(",") |> Enum.map(&String.to_integer/1)
find_ways.(springs, 0, numbers, find_ways)
end)
|> Enum.map(fn {:ok, ways} -> ways end)
|> IO.inspect()
|> Enum.sum()
end
solution12.(sample12_2)
solution12.(input12)
Part 2
defmodule Aoc2023.Day12.Part2 do
def find_ways(springs, cur, numbers, cache) do
k = {:find_ways, springs, cur, numbers}
if v = cache |> Map.get(k) do
{v, cache}
else
case {springs, cur, numbers} do
{[], nh, [nh]} ->
{1, cache}
{[], 0, []} ->
{1, cache}
{[], _cur, _count} ->
{0, cache}
{[{".", _} | st], 0, numbers} ->
find_ways(st, 0, numbers, cache)
{[{".", _} | st], nh, [nh | nt]} ->
find_ways(st, 0, nt, cache)
{[{".", _} | _st], _cur, _count} ->
{0, cache}
{[{"#", _} | _st], nh, [nh | _nt]} ->
{0, cache}
{[{"#", s} | st], cur, numbers} ->
find_ways(st, cur + s, numbers, cache)
{[{"?", s} | st], cur, numbers} ->
{op, broken} =
case s do
1 ->
{[{".", 1}], [{"#", 1}]}
s when s > 1 ->
{[{".", 1}, {"?", s - 1}], [{"#", 1}, {"?", s - 1}]}
end
{ways1, cache} = find_ways(op ++ st, cur, numbers, cache)
{ways2, cache} = find_ways(broken ++ st, cur, numbers, cache)
{ways1 + ways2, cache}
end
|> then(fn {v, cache} -> {v, cache |> Map.put(k, v)} end)
end
end
def split_and_find(springs, numbers, cache) do
springs = [{".", 1}] ++ springs ++ [{".", 1}]
k = {:split_and_find, springs, numbers}
if v = cache |> Map.get(k) do
{v, cache}
else
springs
|> Enum.chunk_every(3, 1, :discard)
|> Enum.with_index()
|> Enum.flat_map(fn
{[{".", _}, {"#", _} = broken, {".", _}], i} ->
[{broken, i + 1}]
{[{_, _}, {_, _}, {_, _}], _} ->
[]
end)
|> Enum.sort_by(fn {{_, c}, _} -> -c end)
|> List.first()
|> case do
nil ->
find_ways(springs, 0, numbers, cache)
{{"#", size}, i} ->
spring_parts =
[springs |> Enum.take(i - 1), springs |> Enum.drop(i + 2)]
numbers
|> Enum.with_index()
|> Enum.filter(fn {n, _j} -> n == size end)
|> Enum.reduce({0, cache}, fn {^size, j}, {sum, cache} ->
number_parts =
[numbers |> Enum.take(j), numbers |> Enum.drop(j + 1)]
{ways, cache} =
[spring_parts, number_parts]
|> Enum.zip()
|> Enum.reduce({1, cache}, fn {springs, numbers}, {ways, cache} ->
{new_ways, cache} = split_and_find(springs, numbers, cache)
{ways * new_ways, cache}
end)
{sum + ways, cache}
end)
end
|> then(fn {v, cache} -> {v, cache |> Map.put(k, v)} end)
end
end
def copy_and_find(input, copies) do
input
|> String.split("\n", trim: true)
|> Task.async_stream(
fn line ->
[springs, numbers] = line |> String.split(" ")
springs =
1..copies |> Enum.map(fn _ -> springs end) |> Enum.join("?")
numbers =
1..copies |> Enum.map(fn _ -> numbers end) |> Enum.join(",")
springs =
springs
|> String.split("", trim: true)
|> Enum.reduce({[], nil}, fn cur, {list, last} ->
case {last, cur} do
{nil, cur} -> {list, {cur, 1}}
{{cur, n}, cur} -> {list, {cur, n + 1}}
{other, cur} -> {[other | list], {cur, 1}}
end
end)
|> then(fn {list, last} -> [last | list] |> Enum.reverse() end)
numbers = numbers |> String.split(",") |> Enum.map(&String.to_integer/1)
split_and_find(springs, numbers, %{})
end,
timeout: :infinity
)
|> Enum.to_list()
|> Enum.map(fn {:ok, {ways, %{}}} -> ways end)
end
def run(input, copies \\ 5) do
copy_and_find(input, copies) |> Enum.sum()
end
end
Aoc2023.Day12.Part2.run(sample12_1)
Aoc2023.Day12.Part2.run(sample12_2)
Aoc2023.Day12.Part2.run(input12)
