2020-09 in haskell

4 files changed, 1098 insertions, 0 deletions

diff --git a/2020/09-Encoding_Error/example b/2020/09-Encoding_Error/example
new file mode 100644
index 0000000..28d66e4
--- /dev/null
+++ b/2020/09-Encoding_Error/example
@@ -0,0 +1,20 @@
+35
+20
+15
+25
+47
+40
+62
+55
+65
+95
+102
+117
+150
+182
+127
+219
+299
+277
+309
+576
diff --git a/2020/09-Encoding_Error/first.hs b/2020/09-Encoding_Error/first.hs
new file mode 100644
index 0000000..400c15f
--- /dev/null
+++ b/2020/09-Encoding_Error/first.hs
@@ -0,0 +1,31 @@
+module Main (main) where
+import Control.Monad (when)
+import Data.List (foldl')
+import System.Exit (die)
+
+exampleExpectedOutput = 127
+
+parseInput :: String -> IO [Int]
+parseInput filename = do
+  input <- readFile filename
+  return $ map read $ lines input
+
+validate :: [Int] -> Int -> Bool
+validate list n = processInput list
+  where
+    processInput :: [Int] -> Bool
+    processInput (_:[]) = False
+    processInput (x:xs) = (foldl' (\acc i -> acc || (x + i == n && x /= i)) False xs) || processInput xs
+
+compute :: Int -> [Int] -> Int
+compute len list
+  | validate (take len list) (list !! len) = compute len $ tail list
+  | otherwise = list !! len
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute 5 example
+  when  (exampleOutput /= exampleExpectedOutput)  (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute 25 input
diff --git a/2020/09-Encoding_Error/input b/2020/09-Encoding_Error/input
new file mode 100644
index 0000000..92d4a0f
--- /dev/null
+++ b/2020/09-Encoding_Error/input
@@ -0,0 +1,1000 @@
+4
+10
+17
+48
+18
+24
+14
+33
+6
+34
+47
+29
+2
+38
+45
+27
+40
+22
+43
+35
+49
+5
+1
+9
+3
+7
+15
+10
+4
+11
+8
+12
+75
+13
+6
+53
+14
+20
+23
+16
+52
+24
+27
+17
+18
+40
+57
+5
+19
+9
+21
+22
+33
+38
+45
+31
+35
+43
+25
+42
+26
+30
+53
+32
+48
+36
+39
+50
+71
+37
+14
+55
+54
+23
+40
+61
+44
+90
+94
+46
+45
+82
+58
+49
+56
+63
+68
+136
+87
+51
+127
+53
+59
+153
+77
+138
+79
+98
+74
+130
+114
+89
+91
+171
+209
+122
+121
+119
+100
+104
+152
+151
+110
+112
+125
+132
+127
+133
+156
+187
+153
+163
+165
+216
+241
+180
+191
+195
+204
+229
+226
+210
+212
+237
+360
+351
+328
+422
+239
+252
+580
+260
+289
+309
+316
+379
+423
+371
+403
+375
+390
+407
+399
+414
+436
+438
+449
+820
+476
+491
+785
+890
+684
+499
+794
+549
+569
+625
+680
+959
+1048
+746
+802
+866
+765
+789
+806
+813
+975
+1500
+1194
+998
+1278
+990
+1426
+1068
+1124
+1305
+1288
+1597
+1315
+1249
+1371
+1445
+1721
+2482
+1511
+1554
+1571
+1578
+1595
+1874
+3295
+2318
+2058
+2639
+1988
+2649
+2114
+3092
+3445
+2373
+2537
+3711
+4220
+4910
+3082
+3173
+2956
+3065
+3106
+4376
+3125
+3932
+7665
+3469
+3862
+7458
+6265
+4046
+5070
+4102
+4487
+4651
+6231
+5329
+6399
+6642
+6793
+6987
+8034
+6021
+6062
+14299
+10641
+7593
+9002
+6594
+7331
+7571
+7515
+12327
+8148
+8533
+8589
+12057
+10164
+15479
+9980
+14235
+11391
+12615
+16185
+12083
+12656
+13352
+13393
+21814
+16126
+20231
+23516
+13925
+14109
+14846
+16737
+17679
+18128
+25626
+22458
+27502
+24215
+21371
+22063
+22636
+24006
+23474
+44239
+28198
+25435
+34865
+26745
+31604
+28771
+30662
+50834
+32237
+28034
+31788
+31583
+40137
+35807
+39499
+43434
+43829
+44007
+45377
+44699
+45537
+62450
+76039
+54136
+70984
+57407
+53469
+54779
+90586
+58696
+68171
+59617
+59822
+60271
+63371
+67390
+75412
+75306
+88811
+134002
+90914
+87836
+88706
+120843
+142947
+115050
+107605
+108248
+108915
+120859
+110876
+112165
+114396
+122988
+118313
+196271
+120093
+127212
+127661
+130761
+142696
+150718
+163142
+199687
+273457
+205310
+230783
+221080
+215853
+216520
+217163
+336071
+219124
+261594
+358444
+223041
+293903
+232709
+238406
+245525
+247305
+346614
+254873
+258422
+438093
+293414
+368452
+386183
+428351
+421163
+438894
+807346
+434977
+555195
+435644
+480014
+442165
+680502
+591153
+468566
+679585
+1026199
+706972
+686773
+492830
+502178
+513295
+693767
+626874
+661866
+714577
+821827
+814534
+856140
+934995
+870621
+903543
+877142
+1421549
+993309
+972844
+1173332
+961396
+1497495
+970744
+1314657
+1015473
+1200068
+995008
+1487838
+1129052
+1529111
+1288740
+1341451
+1376443
+1536404
+1685155
+2616890
+1726761
+1747763
+1774164
+1838538
+1847886
+1965752
+2170812
+1943588
+2507148
+2309665
+2470503
+2010481
+2514725
+2144525
+2482846
+2124060
+4018698
+2976938
+3255872
+2630191
+2717894
+2912847
+3221559
+3474524
+3622050
+4565780
+4288889
+3944976
+3686424
+3791474
+3909340
+3954069
+4067648
+4640672
+4155006
+4268585
+4134541
+4606906
+4774716
+4754251
+7200848
+5348085
+6931007
+7567026
+9503091
+5630741
+6134406
+6696083
+7160948
+7308474
+8356537
+10237647
+7841430
+7477898
+7863409
+7976988
+8021717
+8909257
+8289547
+8403126
+8741447
+10102336
+10909122
+9528967
+10384992
+12509033
+15002378
+11765147
+15450495
+12326824
+14033867
+13612304
+14673071
+19817507
+15285462
+16130977
+15319328
+15341307
+15454886
+15840397
+19631303
+30626769
+17144573
+16692673
+24848295
+18270414
+19913959
+20438089
+31290892
+27794495
+24091971
+25377451
+28909720
+25939128
+29874264
+27646171
+28285375
+29958533
+30604790
+30660635
+30774214
+54752606
+39932368
+31295283
+32533070
+52642790
+40784644
+58568709
+68217743
+38184373
+38708503
+40352048
+44530060
+49469422
+50031099
+80717012
+54848848
+53585299
+54224503
+55931546
+57604704
+83134223
+69313293
+61265425
+73317714
+131886423
+109245661
+63828353
+79060551
+70717443
+76892876
+78536421
+99973928
+82714433
+83238563
+84882108
+70639851
+93999482
+99500521
+103616398
+107809802
+134545796
+124941946
+117196971
+130578718
+118870129
+125093778
+131905276
+131982868
+161250854
+146542786
+159607309
+140721229
+239792670
+147532727
+149176272
+153354284
+228558344
+153878414
+202622719
+178881590
+164639333
+285337152
+203116919
+211426200
+225006773
+236067100
+272626505
+375101130
+243963907
+285861282
+256999054
+279438003
+272704097
+287264015
+311182119
+302530556
+288253956
+296708999
+351798991
+428614275
+365304614
+318517747
+332760004
+611168230
+447080826
+367756252
+428123692
+583973014
+436432973
+461073873
+749611382
+500962961
+516668004
+773667058
+589794571
+529703151
+552142100
+559968112
+575517971
+584962955
+717103605
+683822361
+615226746
+1076480932
+746641439
+698064618
+651277751
+916733018
+1036591844
+1301753482
+864556665
+889197565
+1026227544
+897506846
+990777024
+1017630965
+1030666112
+1076636116
+1081845251
+1626386415
+1112110212
+1798948856
+1135486083
+1160480926
+1200189701
+1266504497
+1381886979
+1313291364
+1349342369
+1397919190
+1568010769
+1515834416
+1753754230
+1762063511
+1855333689
+1786704411
+2126263107
+1888283870
+1915137811
+2072622275
+2461452581
+2107302228
+2158481367
+2217331334
+2247596295
+3314783272
+4450269355
+2295967009
+2360670627
+2513481065
+2579795861
+6667600689
+2662633733
+2747261559
+3159982701
+3894006639
+5473264639
+3548767922
+4004035745
+8740222964
+3674988281
+4373859402
+3803421681
+3987760086
+4179924503
+4265783595
+7765052627
+6162517112
+4464927629
+4543563304
+4874151692
+4656637636
+4875762870
+7389243935
+7621413251
+5242429594
+5409895292
+7425766296
+8159790234
+6708750623
+8437569943
+8013695551
+10342441615
+7478409962
+11064232216
+10819154748
+11801337754
+8460059317
+8167684589
+8445708098
+8730711224
+19224022450
+9008490933
+9121565265
+15938469279
+15146320566
+12278050887
+10118192464
+15549034169
+11951180217
+13256125145
+12118645915
+14876435212
+14187160585
+14722446174
+16897629260
+15646094551
+15924118060
+29833255136
+16613392687
+16627743906
+31620075434
+16898395813
+33946468624
+17176419322
+19239757729
+18130056198
+19126683397
+21072745482
+22069372681
+27000497061
+22236838379
+35867501635
+24069826132
+25207305362
+32382808542
+32544490364
+32259487238
+66490958988
+30646564234
+49750131632
+31570212611
+32537510747
+33241136593
+33511788500
+38249164804
+34074815135
+36138153542
+36303102719
+51499244967
+64920319289
+37256739595
+40199428879
+43142118163
+73124241230
+124623486197
+46306664511
+49277131494
+54716390366
+56777517973
+62906051472
+62216776845
+63184074981
+63887700827
+64107723358
+64811349204
+65082001111
+115606968325
+66752925093
+67586603635
+105010778083
+70212968677
+72441256261
+79445220882
+77456168474
+80398857758
+89448782674
+126793752299
+92419249657
+95583796005
+101023054877
+103084182484
+116030056587
+127717400676
+119961592954
+125122828317
+145042772109
+127071775808
+127995424185
+128919072562
+129893350315
+131834926204
+134339528728
+136965893770
+147031824517
+239451074174
+142654224938
+166904951148
+156901389356
+169847640432
+172818107415
+181868032331
+198667978489
+223579220190
+196606850882
+204107237361
+219114239071
+243101832395
+330946379610
+245084421271
+252194604125
+343710750598
+270649649123
+376416967944
+260753998766
+438119052663
+271305422498
+276993753666
+279620118708
+289686049455
+380480609546
+299555614294
+353508240238
+326749029788
+434062636456
+516528858013
+378474883213
+610566498318
+400714088243
+522078174937
+578943633913
+550060618681
+488186253666
+670459780386
+547643402789
+589241663749
+531403647889
+537747752432
+532059421264
+765180007332
+548299176164
+918228361978
+579175733002
+569306168163
+616435079243
+680257270026
+957650616215
+1129004252594
+858808451052
+812537519669
+932117736132
+779188971456
+888900341909
+1158119366915
+1577717527001
+1158547831912
+1019589901555
+1020245674930
+1228556446190
+1063463069153
+2641180596154
+1127474909166
+1069807173696
+1080358597428
+1117605344327
+1706418543079
+1148481901165
+1185741247406
+1296692349269
+1395624050699
+2075881320725
+2074641589315
+1591726491125
+1671345970721
+2691591645651
+1995580805285
+1952363411062
+2275956810331
+2039835576485
+2083052970708
+2083708744083
+2523098959865
+2147720584096
+2266099844834
+4766233234966
+2187412518023
+2150165771124
+2303346591733
+2777467738531
+2266087245492
+2334223148571
+2445174250434
+2482433596675
+2692316399968
+2987350541824
+3937433216213
+3263072461846
+3544089902187
+4194444930586
+3947944216347
+4233218741832
+3992198987547
+4349152815542
+6124845734236
+6067188862052
+4231429328179
+4297886355220
+4335133102119
+5137516312948
+5321573690395
+4337578289147
+5111690887102
+4569433837225
+4600310394063
+4711261495926
+5708246712280
+6820011885822
+5745506058521
+5679666941792
+6250423003670
+7457517392432
+6807162364033
+7492034118534
+9656706792514
+7940143203894
+8223628315726
+11376596201258
+8672711391266
+9409577242322
+9475094602095
+10314939895746
+8633019457339
+10017245230939
+9921884084458
+18947959353085
+8907012126372
+13070434889492
+10308557106343
+14615258838652
+10390928437718
+14380958103546
+11425173000313
+11930089945462
+12486829305825
+19293991669858
+14264679756465
+16847155330266
+15715662434260
+21033302993772
+22321018383180
+18147805993361
+27140835434573
+19939129315397
+17540031583711
+24655608194183
+18554903541797
+18650264688278
+18828896210830
+19215569232715
+19297940564090
+22795386412168
+37852844105887
+24689515209889
+21816101438031
+22877757743543
+23355262945775
+23912002306138
+26194769701927
+26751509062290
+41528022431821
+37479160899108
+35497420018544
+33255694017971
+36094935125508
+35687837577072
+39356133021742
+36190296271989
+36368927794541
+36755600816426
+41706653954373
+37205168230075
+37865833920993
+45967078295005
+43905084442604
diff --git a/2020/09-Encoding_Error/second.hs b/2020/09-Encoding_Error/second.hs
new file mode 100644
index 0000000..d9d3a62
--- /dev/null
+++ b/2020/09-Encoding_Error/second.hs
@@ -0,0 +1,47 @@
+module Main (main) where
+import Control.Monad (when)
+import Data.List (foldl')
+import Data.Maybe (fromJust, isNothing)
+import System.Exit (die)
+
+exampleExpectedOutput = 62
+
+parseInput :: String -> IO [Int]
+parseInput filename = do
+  input <- readFile filename
+  return $ map read $ lines input
+
+validate :: [Int] -> Int -> Bool
+validate list n = processInput list
+  where
+    processInput :: [Int] -> Bool
+    processInput (_:[]) = False
+    processInput (x:xs) = (foldl' (\acc i -> acc || (x + i == n && x /= i)) False xs) || processInput xs
+
+isContiguousSum :: Int -> [Int] -> Int -> Maybe Int
+isContiguousSum target list counter
+  | sum' == target = Just $ (minimum lst) + (maximum lst)
+  | sum' < target = isContiguousSum target list (counter + 1)
+  | otherwise = Nothing
+  where
+    lst = take counter list
+    sum' = sum lst
+
+compute :: Int -> [Int] -> Int
+compute len list
+  | validate (take len list) (list !! len) = compute len $ tail list
+  | otherwise = list !! len
+
+compute' :: Int -> [Int] -> Int
+compute' target list = case isContiguousSum target list 2 of
+    Nothing -> compute' target (tail list)
+    Just a -> a
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute 5 example
+      exampleOutput' = compute' exampleOutput example
+  when  (exampleOutput' /= exampleExpectedOutput)  (die $ "example failed: got " ++ show exampleOutput' ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute' (compute 25 input) input