5

2 files changed, 529 insertions, 0 deletions

diff --git a/2021/5.hs b/2021/5.hs
new file mode 100644
index 0000000..7ab4f3b
--- /dev/null
+++ b/2021/5.hs
@@ -0,0 +1,29 @@
+{-# LANGUAGE TupleSections #-}
+module Main where
+
+import qualified Data.Array as A
+
+import Input
+
+
+main :: IO ()
+main = do
+    let parseLine s = let [a,_,b] = words s in (parsePt a, parsePt b)
+        parsePt s = let (a,_:b) = break (== ',') s in (read a, read b) :: (Int, Int)
+    inp <- map parseLine <$> getInput 5
+    let minmax = (,) <$> minimum <*> maximum
+        (minx, maxx) = minmax (concatMap (\((a,_),(b,_)) -> [a,b]) inp)
+        (miny, maxy) = minmax (concatMap (\((_,a),(_,b)) -> [a,b]) inp)
+    let enumLine diag ((x1,y1),(x2,y2))
+          | (diag && abs (x1 - x2) == abs (y1 - y2)) || x1 == x2 || y1 == y2
+          = let dx = signum (x2 - x1)
+                dy = signum (y2 - y1)
+            in [(x1 + i * dx, y1 + i * dy)
+               | i <- [0 .. max (abs (x2 - x1)) (abs (y2 - y1))]]
+          | otherwise = []
+        bd diag = A.accumArray (+) (0::Int) ((minx, miny), (maxx, maxy))
+                      [((x, y), 1)
+                      | line <- inp
+                      , (x, y) <- enumLine diag line]
+    print (length (filter (> 1) (A.elems (bd False))))
+    print (length (filter (> 1) (A.elems (bd True))))
diff --git a/2021/5.in b/2021/5.in
new file mode 100644
index 0000000..58fb409
--- /dev/null
+++ b/2021/5.in
@@ -0,0 +1,500 @@
+682,519 -> 682,729
+852,131 -> 25,958
+303,481 -> 206,481
+199,682 -> 183,666
+363,190 -> 571,190
+930,290 -> 221,290
+364,627 -> 952,39
+234,309 -> 234,821
+130,864 -> 130,886
+462,347 -> 699,110
+375,969 -> 481,969
+989,859 -> 275,145
+221,748 -> 212,748
+870,173 -> 106,937
+604,33 -> 604,142
+780,35 -> 780,206
+636,808 -> 721,808
+944,989 -> 334,989
+477,113 -> 192,113
+879,265 -> 879,358
+754,974 -> 17,974
+10,989 -> 989,10
+337,320 -> 674,657
+225,96 -> 557,428
+129,354 -> 299,354
+717,695 -> 695,695
+94,255 -> 317,478
+90,87 -> 90,187
+77,942 -> 952,67
+804,315 -> 989,315
+619,470 -> 491,342
+466,90 -> 466,755
+840,121 -> 840,469
+638,127 -> 638,77
+844,40 -> 151,40
+653,987 -> 653,631
+195,583 -> 195,623
+88,985 -> 570,503
+921,897 -> 165,141
+230,27 -> 171,27
+737,771 -> 832,771
+563,365 -> 665,467
+942,940 -> 776,774
+12,903 -> 644,903
+308,390 -> 308,971
+572,943 -> 572,15
+104,389 -> 104,73
+346,721 -> 974,93
+30,53 -> 562,53
+804,682 -> 804,120
+952,45 -> 15,982
+475,456 -> 475,348
+409,247 -> 664,247
+345,18 -> 816,489
+571,158 -> 505,158
+59,195 -> 27,195
+230,681 -> 23,681
+258,711 -> 921,711
+658,112 -> 366,404
+842,220 -> 842,825
+815,744 -> 540,744
+192,314 -> 703,825
+869,573 -> 869,888
+603,268 -> 603,301
+816,668 -> 816,189
+148,606 -> 948,606
+117,461 -> 506,461
+986,955 -> 986,315
+131,250 -> 192,189
+988,148 -> 518,618
+682,900 -> 31,900
+652,839 -> 652,236
+466,812 -> 466,611
+881,346 -> 401,346
+229,639 -> 731,639
+104,476 -> 840,476
+10,988 -> 988,10
+29,15 -> 987,973
+825,348 -> 825,240
+989,989 -> 10,10
+430,796 -> 926,796
+49,293 -> 610,854
+325,288 -> 918,288
+625,309 -> 439,495
+536,150 -> 356,150
+834,558 -> 822,558
+315,408 -> 315,635
+257,973 -> 813,973
+713,52 -> 122,52
+323,970 -> 578,970
+447,49 -> 829,49
+941,709 -> 941,390
+148,323 -> 391,80
+23,171 -> 23,49
+475,265 -> 322,112
+506,407 -> 69,844
+567,284 -> 483,368
+114,745 -> 114,765
+392,252 -> 109,535
+65,188 -> 455,188
+732,779 -> 732,52
+233,214 -> 759,214
+232,969 -> 957,244
+20,669 -> 20,308
+49,972 -> 285,972
+501,383 -> 433,383
+918,15 -> 32,901
+255,268 -> 935,948
+757,588 -> 757,919
+530,803 -> 284,557
+688,926 -> 48,286
+331,245 -> 331,777
+448,544 -> 209,544
+10,970 -> 951,29
+233,11 -> 897,11
+145,392 -> 628,392
+935,971 -> 935,280
+169,632 -> 54,632
+155,244 -> 155,334
+56,284 -> 205,284
+553,428 -> 553,520
+977,176 -> 497,656
+323,339 -> 971,987
+616,355 -> 616,248
+72,660 -> 72,334
+644,822 -> 510,956
+356,841 -> 587,841
+413,468 -> 605,468
+85,22 -> 645,582
+924,850 -> 522,850
+448,45 -> 345,148
+102,566 -> 551,566
+80,39 -> 847,806
+936,436 -> 934,436
+53,24 -> 495,466
+234,173 -> 282,173
+145,680 -> 456,680
+960,759 -> 960,282
+984,814 -> 308,138
+398,808 -> 716,808
+509,536 -> 25,52
+289,777 -> 803,263
+766,892 -> 257,892
+301,733 -> 688,733
+24,109 -> 887,972
+180,32 -> 577,429
+985,801 -> 687,503
+901,582 -> 586,582
+50,56 -> 50,267
+344,373 -> 437,373
+542,133 -> 905,496
+420,624 -> 420,716
+645,106 -> 645,574
+356,37 -> 114,37
+324,919 -> 357,919
+126,797 -> 120,797
+288,689 -> 435,836
+93,915 -> 639,369
+106,391 -> 478,19
+277,501 -> 714,64
+253,277 -> 643,277
+568,972 -> 350,972
+213,235 -> 213,406
+595,888 -> 595,233
+577,63 -> 37,603
+649,732 -> 931,732
+469,892 -> 549,892
+953,895 -> 953,457
+222,213 -> 290,213
+841,800 -> 841,336
+685,143 -> 25,143
+441,127 -> 441,146
+646,586 -> 56,586
+698,122 -> 465,122
+641,502 -> 641,240
+111,91 -> 185,91
+927,755 -> 874,808
+108,151 -> 108,567
+309,453 -> 309,210
+890,657 -> 491,657
+404,244 -> 404,123
+939,28 -> 26,941
+596,970 -> 596,870
+489,556 -> 489,589
+607,621 -> 903,325
+912,284 -> 571,284
+921,702 -> 743,524
+719,36 -> 719,394
+100,905 -> 798,207
+316,260 -> 316,887
+799,940 -> 885,940
+835,287 -> 199,923
+422,760 -> 64,760
+727,113 -> 727,679
+733,56 -> 59,730
+141,399 -> 485,743
+769,629 -> 769,797
+62,486 -> 62,205
+192,332 -> 800,332
+15,931 -> 727,931
+854,915 -> 988,915
+349,610 -> 886,610
+72,110 -> 72,903
+955,110 -> 78,987
+591,553 -> 591,428
+708,467 -> 516,467
+397,589 -> 353,589
+930,336 -> 930,532
+639,50 -> 228,50
+472,17 -> 472,244
+420,825 -> 420,562
+203,197 -> 203,35
+984,964 -> 223,203
+944,269 -> 935,260
+933,119 -> 87,965
+696,290 -> 696,580
+925,960 -> 52,87
+451,470 -> 235,254
+562,71 -> 562,149
+405,126 -> 405,67
+356,424 -> 356,673
+859,649 -> 859,291
+210,651 -> 210,544
+403,783 -> 403,122
+672,87 -> 586,87
+409,668 -> 984,668
+917,352 -> 511,758
+395,953 -> 141,953
+152,795 -> 152,313
+839,344 -> 811,372
+114,649 -> 650,649
+60,517 -> 60,27
+448,392 -> 845,392
+33,849 -> 719,163
+151,988 -> 876,988
+805,556 -> 124,556
+361,538 -> 706,193
+974,941 -> 141,108
+271,813 -> 968,116
+500,697 -> 80,277
+586,731 -> 586,480
+128,147 -> 174,101
+882,681 -> 882,745
+531,730 -> 677,730
+989,11 -> 11,989
+74,332 -> 234,492
+360,326 -> 932,898
+136,288 -> 113,311
+666,645 -> 916,895
+977,478 -> 561,62
+20,83 -> 566,83
+331,942 -> 331,646
+180,291 -> 405,291
+637,763 -> 637,941
+120,138 -> 120,820
+951,24 -> 14,961
+204,304 -> 204,51
+84,168 -> 880,168
+955,145 -> 955,903
+437,427 -> 437,354
+875,67 -> 189,753
+46,767 -> 802,11
+52,59 -> 889,896
+926,56 -> 102,880
+500,30 -> 964,30
+329,488 -> 329,972
+63,11 -> 889,837
+707,168 -> 707,584
+580,10 -> 735,10
+105,620 -> 105,110
+187,531 -> 323,531
+82,947 -> 82,941
+737,199 -> 737,851
+612,650 -> 217,650
+971,15 -> 82,904
+16,590 -> 506,100
+950,877 -> 832,759
+570,470 -> 570,276
+213,411 -> 213,195
+670,755 -> 89,755
+906,963 -> 906,984
+458,463 -> 442,463
+956,969 -> 10,23
+87,215 -> 195,107
+819,454 -> 819,467
+594,793 -> 686,793
+395,724 -> 787,332
+315,461 -> 644,461
+448,247 -> 249,48
+620,302 -> 247,675
+607,134 -> 932,134
+312,776 -> 312,289
+850,942 -> 54,146
+31,538 -> 851,538
+729,126 -> 640,126
+702,199 -> 702,706
+402,783 -> 254,783
+110,59 -> 203,59
+27,10 -> 965,948
+747,261 -> 47,261
+628,742 -> 972,742
+712,742 -> 657,797
+877,871 -> 877,758
+665,313 -> 449,529
+498,157 -> 498,68
+870,922 -> 27,79
+856,697 -> 856,429
+447,271 -> 963,787
+495,302 -> 495,520
+526,47 -> 721,47
+826,179 -> 826,741
+565,461 -> 893,461
+512,328 -> 127,328
+487,920 -> 522,920
+614,452 -> 614,146
+331,574 -> 331,840
+985,79 -> 285,779
+812,320 -> 985,320
+118,69 -> 429,69
+644,525 -> 644,878
+271,132 -> 156,132
+955,782 -> 565,392
+630,939 -> 630,372
+51,203 -> 840,203
+202,490 -> 202,479
+579,868 -> 579,92
+979,336 -> 979,623
+843,865 -> 260,282
+685,872 -> 685,503
+721,193 -> 721,510
+908,661 -> 908,955
+19,950 -> 715,254
+233,730 -> 233,101
+922,954 -> 27,954
+399,444 -> 399,403
+380,712 -> 380,718
+238,264 -> 849,875
+458,577 -> 458,139
+418,244 -> 469,295
+460,375 -> 964,879
+276,445 -> 815,445
+463,910 -> 648,725
+26,384 -> 968,384
+955,385 -> 955,143
+942,775 -> 733,566
+425,326 -> 531,326
+364,545 -> 364,873
+182,759 -> 182,819
+390,757 -> 390,475
+217,417 -> 217,157
+669,286 -> 65,890
+257,11 -> 257,858
+557,397 -> 557,20
+888,946 -> 32,90
+971,938 -> 971,578
+874,248 -> 874,485
+87,268 -> 87,135
+756,679 -> 103,26
+771,250 -> 771,107
+320,711 -> 967,711
+293,219 -> 293,706
+103,565 -> 103,538
+388,256 -> 388,261
+468,953 -> 503,953
+424,142 -> 287,142
+24,930 -> 850,930
+316,167 -> 316,161
+481,421 -> 208,148
+938,926 -> 938,933
+701,653 -> 701,780
+536,390 -> 536,559
+40,954 -> 829,165
+404,985 -> 247,985
+94,628 -> 94,500
+441,637 -> 441,271
+766,946 -> 97,277
+428,363 -> 428,37
+542,694 -> 542,347
+11,16 -> 979,984
+938,651 -> 632,957
+779,127 -> 243,663
+636,294 -> 636,787
+533,744 -> 636,641
+521,950 -> 458,950
+988,12 -> 18,982
+954,621 -> 954,271
+638,951 -> 813,951
+822,911 -> 632,911
+714,849 -> 512,849
+696,88 -> 385,88
+65,451 -> 65,687
+976,973 -> 976,907
+368,489 -> 368,571
+358,831 -> 690,499
+436,704 -> 178,704
+690,619 -> 606,535
+96,701 -> 358,701
+885,562 -> 420,562
+581,480 -> 613,512
+44,970 -> 970,44
+216,796 -> 892,120
+72,623 -> 72,72
+896,283 -> 896,326
+794,195 -> 22,967
+134,326 -> 134,889
+420,141 -> 944,665
+941,194 -> 941,421
+940,525 -> 298,525
+653,300 -> 769,300
+227,424 -> 406,603
+275,850 -> 113,850
+648,850 -> 92,850
+638,389 -> 638,10
+379,404 -> 584,609
+833,931 -> 833,520
+772,286 -> 500,558
+372,262 -> 333,262
+689,18 -> 131,576
+687,499 -> 687,188
+344,499 -> 37,806
+778,496 -> 134,496
+938,87 -> 344,681
+788,401 -> 479,401
+828,903 -> 756,903
+423,625 -> 285,763
+218,489 -> 218,819
+488,384 -> 891,787
+817,532 -> 788,532
+512,27 -> 512,149
+369,794 -> 54,794
+534,590 -> 827,883
+84,310 -> 39,265
+357,545 -> 665,545
+539,807 -> 539,781
+378,683 -> 22,327
+71,909 -> 943,37
+740,552 -> 348,552
+698,315 -> 45,968
+516,835 -> 360,835
+629,141 -> 629,385
+695,908 -> 303,908
+795,707 -> 386,707
+211,397 -> 291,397
+64,620 -> 236,620
+97,638 -> 97,445
+46,103 -> 893,950
+468,122 -> 979,122
+810,486 -> 433,486
+532,899 -> 461,970
+232,60 -> 235,60
+549,708 -> 549,90
+294,978 -> 294,124
+865,406 -> 640,406
+755,305 -> 664,305
+12,989 -> 987,14
+275,249 -> 260,234
+502,783 -> 67,783
+863,938 -> 297,372
+516,961 -> 516,272
+67,510 -> 611,510
+980,951 -> 312,283
+325,512 -> 325,169
+142,429 -> 542,29
+273,964 -> 822,964
+370,217 -> 508,217
+131,131 -> 331,331
+734,824 -> 734,817
+75,89 -> 687,701
+155,255 -> 702,802
+577,395 -> 130,395
+684,94 -> 555,94
+393,881 -> 173,881
+894,750 -> 773,750
+380,269 -> 380,338
+427,36 -> 427,77
+637,107 -> 637,846
+53,437 -> 53,221
+128,979 -> 960,147
+838,211 -> 838,645
+898,39 -> 849,39
+862,495 -> 951,495
+754,406 -> 76,406
+951,960 -> 113,122
+830,125 -> 15,940
+190,117 -> 190,973
+192,956 -> 718,430
+895,162 -> 88,969
+135,196 -> 70,131
+578,642 -> 578,789
+713,268 -> 625,268
+938,719 -> 938,604
+30,863 -> 99,863
+844,309 -> 287,309
+131,837 -> 459,509
+61,206 -> 722,867
+95,974 -> 283,974
+746,672 -> 558,672
+552,32 -> 352,32
+21,637 -> 21,781
+945,847 -> 945,303