From 2cade691a86583689f7d3be0fdd8ec2b9638ec67 Mon Sep 17 00:00:00 2001 From: Tom Smeding Date: Sun, 5 Dec 2021 09:58:41 +0100 Subject: 5 --- 2021/5.hs | 29 ++++ 2021/5.in | 500 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 529 insertions(+) create mode 100644 2021/5.hs create mode 100644 2021/5.in 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 -- cgit v1.2.3-54-g00ecf