4

2 files changed, 629 insertions, 0 deletions

diff --git a/2021/4.hs b/2021/4.hs
new file mode 100644
index 0000000..bee4780
--- /dev/null
+++ b/2021/4.hs
@@ -0,0 +1,28 @@
+module Main where
+
+import Data.Foldable
+import Data.List
+import Data.Maybe
+import Data.Ord
+
+import Input
+import Util
+
+
+data Board = Board [[Maybe Int]]
+  deriving (Show)
+
+main :: IO ()
+main = do
+    inp <- getInput 4
+    let order = read <$> splitOn (== ',') (head inp)
+        boards = Board . map (map (Just . read) . words) <$> splitOn null (drop 2 inp)
+        won (Board l) = any (all isNothing) l || any (all isNothing) (transpose l)
+        cross (Board bd) n = Board (map (map (>>= \x -> if x == n then Nothing else Just x)) bd)
+        timetowin bd = find (won . snd) . zip [0::Int ..] $ scanl cross bd (toList order)
+        wins = catMaybes . toList $ timetowin <$> boards
+        score idx (Board l) = (toList order !! (idx - 1)) * sum (catMaybes (concat l))
+        wonboard = minimumBy (comparing fst) wins
+        lostboard = maximumBy (comparing fst) wins
+    print (uncurry score wonboard)
+    print (uncurry score lostboard)
diff --git a/2021/4.in b/2021/4.in
new file mode 100644
index 0000000..c14a3da
--- /dev/null
+++ b/2021/4.in
@@ -0,0 +1,601 @@
+74,79,46,2,19,27,31,90,21,83,94,77,0,29,38,72,42,23,6,62,45,95,41,55,93,69,39,17,12,1,20,53,49,71,61,13,88,25,87,26,50,58,28,51,89,64,3,80,36,65,57,92,52,86,98,78,9,33,44,63,16,34,97,60,40,66,75,4,7,84,22,43,11,85,91,32,48,14,18,76,8,47,24,81,35,30,82,67,37,70,15,5,73,59,54,68,56,96,99,10
+
+61 96 92 39  0
+35 25 50 22 60
+ 3 88 69 48 62
+75 24 97 51 67
+87 74 94 77 83
+
+ 1 70 59 40 55
+42 88 10 17 80
+27 24 82 45 23
+ 5 19 48 51 11
+75 72 97 74  7
+
+58 40 78 83 74
+ 4 94 17 63 62
+55 61  5 27 69
+99 84 89 81 59
+64 28 91 49 97
+
+92 88 51 12 22
+ 0  5 65 32 77
+80 40  3 10 90
+91 47 58 57 14
+86 71 94 36 75
+
+71 24 16 66 29
+ 8 47 93 68 36
+42 67 69 55 15
+75  6 34 60 70
+95 92 14  0 81
+
+52 49 37 41 67
+ 9  8  2 13 17
+92 89 38 16 53
+63 46 60  4 87
+57 96 77 85 39
+
+84 98 52 95 89
+81 67 99 85 50
+88 11 76 49  8
+ 4 30 51 78 20
+70 64 74 40 79
+
+45 65 87 79 14
+11 26 98 70 28
+46 85 54 55 48
+97 59 62 57 16
+30 40 95  7 18
+
+97 25 38  1 26
+20 86  7 68 39
+ 2 55 29 33 65
+46 14 72 47 18
+60 48 41  9 50
+
+71 81 15 49 50
+72 28 51 11 35
+20  7 36 84 65
+93 33 14 47 45
+89  0 75 60 16
+
+98 90 47 94 55
+69 41 81  1 43
+73 95 65 15 80
+85 99 60 92  0
+13 33 82 51 22
+
+47 58 82 67 30
+88 23 64  4 39
+94 52 61  1 75
+ 3  8 34 87 49
+13 38 60 54 35
+
+91 62 88 29 33
+84 27  6 18 11
+47 87 58 42 34
+69 46 75 40 43
+63 97 53 49 66
+
+80 57 73 65 44
+95 55 27 46 10
+82 24 90 97 75
+33 41 31 84  9
+ 5 48 18 49 12
+
+92 63 91 14 13
+32 12 66 87 79
+44 60  7 96 84
+58 41 42  3 27
+16 59 43 77 11
+
+80 36 53 56 62
+26  8  4 79 51
+22 91 69 78  2
+59 13 23 81 93
+30 16 49 33 65
+
+52 88 12 67 85
+74 78 75 72 79
+81 26 82  5  0
+23 56 41  3 32
+31 69 15 66 87
+
+22 71 80  0 63
+94 31 13 60 42
+41 77 90 92 91
+64 95  5 23 73
+85 15  3 88 10
+
+72 75 88 52 38
+17 86 54 79 87
+66 61 51  3 26
+68 47 89 11 41
+50 33 92  7 81
+
+82 80  9 65 34
+ 3 49 42 36 76
+95 94 61 32 43
+72 67 56 45 54
+77 48 14  6 25
+
+44 75 99 62 11
+43 73  2 87 83
+96 63 85 14 30
+32 70 18 29 55
+ 1 88 15 27 24
+
+ 2 38 46 61  7
+45 19 97 31 54
+88 40 14 81 87
+69 39 32 16 21
+22  5  0 29 92
+
+78 57 85  4 70
+82 43 12 69 79
+60 34 15 63 45
+90 77 93 31 47
+27 49 25 71 19
+
+49 10 40 51 45
+ 9 44 86 26 27
+93 98 22 63 95
+88 66 33 74 57
+81 24 28 91 72
+
+14 83 60 54 57
+18 15 41  4 47
+39 98 62 33  5
+30 70  6 91 90
+86 21 28 84 81
+
+91 46 49  9 32
+85 33 87 83 76
+17 14 37 94  6
+31 13 92 89 78
+15 66 47 74 63
+
+55  6 83 19 96
+71 22 88 99 50
+89 84 26 45 38
+57 77 87 93 25
+44 49 16 64 34
+
+79 76 46 19 51
+85 90 58 29  3
+34  2 81 62 99
+84 60 78 91 96
+ 4 27 43 47 98
+
+66  2 38 39 37
+35 25 51 10 82
+91 62  1 12 93
+83 29 47 32 56
+74 19 50 95 49
+
+59 57 35 50 51
+27 38 62 76  3
+52 49 83 75  4
+64 16 93  7 91
+40 17 65 41 97
+
+18 37 45 44  4
+72  7 28  0 75
+ 9  2 95 90 38
+24 79 93 22 88
+94 70 57  6 20
+
+11 61 65 50 23
+74 51 80 91 22
+ 5 32 27 57 14
+59 86 70 17 10
+21 62 20 18 67
+
+98  9 88 79 78
+99 56 91 41 67
+17 39 65 16 38
+75 84 11 21 61
+22 81 52 55 87
+
+45 36 74 47 19
+15 22 88 85 32
+38 63 54 16 13
+29  7 48 90 43
+68  3 24 17 30
+
+72 77 68 75 57
+43 74 32 61 34
+37  2 47 25 85
+56 12 95 98  0
+80 36 39 22 11
+
+77 58 24 57 99
+70 16 33 41 94
+54 61 20 90 30
+29 17 55  0 83
+13 37 42 49 38
+
+86 58 13 11  6
+73 26 25  0 67
+56 44 87  5 49
+ 4 91 51 66 22
+28  8  1 15 57
+
+61 24 50 25 66
+92 42 98 55 96
+46 79 22 33 91
+97  0 69 90 54
+17 38 34 39 52
+
+68 28 67 45 87
+ 8 80 52 41 54
+34 47  4 78 59
+10 29 32 11 26
+17 33  7 93 35
+
+10 15 33 46 14
+ 6 56 52 16 92
+47 36 17  8 69
+77 45 73 84  9
+55 60 80 44 64
+
+58 18 25 11 83
+75  7 53 42 68
+48 52  6  0 43
+80 97 16 60  1
+29 67 15  5 17
+
+77 55 54 24 66
+58  2  4 39 12
+57 86 69 91  8
+67 84 65 13 20
+87 59 40 34 27
+
+39  7 40 77 91
+13 76 32 92 56
+34 17 81 27 66
+37 80 83 85 15
+43 36 30 26 63
+
+11 50 72 85 34
+ 3 92 58 53  7
+98 10 49 97 12
+26 42 14 24 56
+28 20 59 54  4
+
+55 56 29 80 96
+63 68 44 22 12
+65  4 95  6 26
+21 35 14 87  8
+17 92 86 30 53
+
+ 9 42 20 37 19
+65 46 11 54 92
+52  4 56 80 99
+41 55 43 90 17
+60 87 13 50  3
+
+ 3 29  4 41 95
+14  9 11 23 10
+ 7 63 68 58 66
+13 46 67 86 51
+28 36  0 73 84
+
+45  1 19 74 36
+58 64 30 86 83
+99 42 70 97 54
+17 75 56 80 81
+93 41 90 10 88
+
+24 25  0 94 22
+70  1 50 10 14
+89 77 76 63 46
+33 72 81 28 60
+68 40 12 31 20
+
+79 33 30 55 71
+31 91 54  0 82
+10 78  9 49 14
+85 72  5  3 24
+86 38 97 46 61
+
+20 84 97 52 79
+45 73 11 18 58
+63 86 21  9 87
+48 90 13 77 49
+44 85 56 71 55
+
+16  1 54 13 83
+38 32 69 28 43
+ 5 50 57 95 47
+34 76 45 74 89
+46 91 71 39 17
+
+82 45 14 28 57
+27 21 17 29 51
+95 32 31 80 91
+89 74 67 76 79
+ 6  0  4 43 94
+
+52 66 44 74 95
+85 51 79 76 54
+89 34 59 10 27
+45  6 69 98 48
+88 19  3 65 94
+
+61  9 67 72 71
+93 48 64 52 11
+74 85 12 13 23
+41  4 94 16 57
+63 88 28 89 40
+
+68 23 54 56 44
+13 77 26  2 46
+28 81 15 16 62
+82 51 71 86 72
+99  0 52 41 32
+
+99 38  7 87  9
+69 96 22 57 24
+64 81 29 67 14
+48 52  6 88 92
+90 44 51 40  8
+
+41  1 23 24 73
+10  4 66 60 22
+17  9 69 53 63
+42 34 99 86 56
+75 82 81 18 79
+
+58 64 12 59 30
+21 94 28 77 53
+88 90 97 62 83
+35 70 27 98 26
+65 34 25 73 75
+
+81  7 90 91 74
+23 34 67 31 50
+60 87  5 40 77
+69 93 27 49 53
+39 62 68 16 89
+
+82 13 28 65 35
+ 5 42 90 12 51
+15 85 64 86 25
+87 22 88 37 98
+39 10 46 56 49
+
+62 25 93 75 34
+42 89 27 36 18
+32 54 59 26  6
+51 19 47 85 95
+33 39 73 29 79
+
+15 27  0 79 69
+13 73 25 19 43
+30  8 46 34 58
+ 4 86 66 74 18
+83 33 92 11 47
+
+45 25 22 14  4
+83  3 65 17 85
+91 26  5 19 87
+66 89 29 49 64
+52 20 58 93 53
+
+30 64 52 14 34
+63 16 97  9 15
+ 2 72 65 45 17
+47 98 77 23  0
+50 20 38 60 26
+
+46 67 84 66 55
+ 7 32 31 75 19
+71 85 37 12 52
+39 27  8 81 44
+89 47 42 16 58
+
+74 99 81 86 89
+92 20  7 58 30
+63 96 25 45  2
+97 50 94 33 87
+38  6 51 21 62
+
+52 27 20 32 19
+17 80 70 92 96
+49 44 62 60 94
+40 28 86  4  7
+38 91  3 77 29
+
+ 8 28 89 99  6
+46 54 34 95  3
+88 60 29 91 10
+42 13 62 94 76
+56 52 72 85 59
+
+85 50 42  5 91
+67  7 21  6 56
+14  8 70 10 78
+77 80 57 29 96
+17 23 73 16 38
+
+59 61 47 43 13
+ 7 93 11 72 83
+ 0 96 67 27  2
+42  5 41 65 94
+40 34 33 50  3
+
+25 79 52 11 94
+73 14  7 99 19
+92 40  2 28 45
+55 34 87 24 96
+36 16 66 78 35
+
+11 27 90 50 55
+68 84 63 57 89
+35 14 29 77 24
+92 81  7  1 85
+99 64 20  2 49
+
+20 66 85 88 57
+49 17 78  1 80
+18 24 11 31 65
+30 34 45 99 19
+69 40 94  2 58
+
+49  2 55 54 61
+48 19 34  5 83
+80 52 67 24 96
+51 91 20 45 68
+87 79 59  9  3
+
+47 12 71 88 74
+28  5 79 58 26
+93 67 62 86 23
+66 13 96 46 17
+94 59 19 54 15
+
+21 89 98 54 53
+49 44 79 10 93
+64 24 25  9 56
+57 70 55 65 23
+14 36 31 13  4
+
+62 60 30 89 94
+88 19 59 41 75
+25 45 74 17 47
+ 5 16 76 33 58
+53 68 65 39 67
+
+55  2 76 32 26
+37 25  5 27 24
+61 88 33 45 46
+20 96 51 42 49
+66  3 15 11 36
+
+60 21 80  9 96
+91 39 24 28 13
+52 11 34 41 82
+66 85 72 38 76
+69 25 67 64 81
+
+67 75 42 79 74
+36 26 85 30 25
+50 19  3 33 28
+12 95 54 71 91
+ 0 17 87 92 40
+
+51 85 12 86 40
+28 36 35 50 97
+55 16 20 14 73
+ 7  5  4 68 22
+47  3 67 93  2
+
+48 33 92 35 31
+73 40 71 75 62
+19 54 49 20 38
+23 37  9 11 10
+80 63 39 52 56
+
+59 70 61 65 62
+42 73 99 39 66
+67  8 93 30 97
+53 37 51 55 11
+48 26 94 44 63
+
+99  5 21  8 13
+ 0 35 25 19  6
+93 83 40 98 43
+84 18 66 50 62
+86 94 32 52 11
+
+55 15 85 39  4
+95 83 27 46 45
+19 47 61  9 66
+82 32 72 77 16
+50 96 14 60 35
+
+66 13 84 74 97
+85 67 20 43 34
+95  0  3 58 38
+48 69 93 28  7
+91 98 56 94 35
+
+11 15 73 51 77
+13  7 22 53 10
+ 2 40 98 79 50
+71 83 49 45 56
+ 0  1 68 99 24
+
+34 84 37 31 93
+55  7 18 15 65
+80 40 29 44 36
+51 26 99 59  2
+57 45 67  1 41
+
+79 90 56 76 58
+78 70 20 26 48
+87 82 46 59 98
+51 81 91 52 44
+21 86 68 64  7
+
+12 26 73 30 87
+99 58 45 25 38
+95 97 27 22 37
+98 72 10  6 79
+ 4 61 20 85 67
+
+ 9 26  5 68  2
+97  4 31 11 69
+75 64  0  6 17
+25 95 89 59 38
+16 99 27 53 10
+
+89 71 42 70 90
+12 38  8 63 23
+95 77  0 29 43
+81 93 56  2 34
+46 44 55 13 41
+
+72 21 50  1 81
+67 44 88 90 82
+98 19 30 48 85
+66 20 79 13 28
+29 62 38 74 89
+
+ 1 62 20 28  0
+59 52 11  6 74
+32 16 50 34 76
+79 91 31 24 56
+26 37 87 53 57
+
+47 79 55 45  9
+63  2  1 60 75
+18 39 97  7 44
+33 29 91 31 23
+50 80 32 49 71
+
+41 52 85  2 83
+28 27 49 14 44
+20  1 34 19 17
+62 59 68 86 82
+89 31 37 95 80
+
+67 70 59 17 91
+ 3 60 12  6 93
+99 44 34  9 21
+31 26 61 20 25
+23 15 43 53 42
+
+52 19 16 91 35
+65 29  4  2 48
+90 44 77 38 60
+49 62 53 47 74
+61 15 30 28 70
+
+14 97 34 88 55
+50 28 80 36 64
+93 40 60 90 22
+29 77  1 26 56
+33  9  4 67 68