From 95417d3684bd31bdc3e603cbdbaf441cdea191da Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Sat, 9 Dec 2023 18:28:43 +0100 Subject: 2023-09 in haskell --- 2023/09-Mirage_Maintenance/example | 3 + 2023/09-Mirage_Maintenance/first.hs | 53 ++++++++++ 2023/09-Mirage_Maintenance/input | 200 +++++++++++++++++++++++++++++++++++ 2023/09-Mirage_Maintenance/second.hs | 53 ++++++++++ 4 files changed, 309 insertions(+) create mode 100644 2023/09-Mirage_Maintenance/example create mode 100644 2023/09-Mirage_Maintenance/first.hs create mode 100644 2023/09-Mirage_Maintenance/input create mode 100644 2023/09-Mirage_Maintenance/second.hs diff --git a/2023/09-Mirage_Maintenance/example b/2023/09-Mirage_Maintenance/example new file mode 100644 index 0000000..539a763 --- /dev/null +++ b/2023/09-Mirage_Maintenance/example @@ -0,0 +1,3 @@ +0 3 6 9 12 15 +1 3 6 10 15 21 +10 13 16 21 30 45 diff --git a/2023/09-Mirage_Maintenance/first.hs b/2023/09-Mirage_Maintenance/first.hs new file mode 100644 index 0000000..9d91564 --- /dev/null +++ b/2023/09-Mirage_Maintenance/first.hs @@ -0,0 +1,53 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 114 + +type History = [Int] +type Input = [History] + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read <$> some (char '-' <|> digitChar) <* hspace + +parseInput' :: Parser Input +parseInput' = some (some parseNumber <* eol) <* eof + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> error $ errorBundlePretty bundle + Right input' -> return input' + +compute :: Input -> Int +compute = sum . map next + where + next :: History -> Int + next = sum . map last . takeWhile (any (/= 0)) . iterate differences + differences :: History -> History + differences xs = zipWith (flip (-)) xs (tail xs) + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input diff --git a/2023/09-Mirage_Maintenance/input b/2023/09-Mirage_Maintenance/input new file mode 100644 index 0000000..1ac7a3b --- /dev/null +++ b/2023/09-Mirage_Maintenance/input @@ -0,0 +1,200 @@ +20 42 73 115 170 240 327 433 560 710 885 1087 1318 1580 1875 2205 2572 2978 3425 3915 4450 +25 39 53 67 81 95 109 123 137 151 165 179 193 207 221 235 249 263 277 291 305 +12 29 76 164 312 559 976 1678 2836 4689 7556 11848 18080 26883 39016 55378 77020 105157 141180 186668 243400 +15 33 71 131 206 285 367 491 804 1710 4164 10190 23711 51809 106702 209391 397981 749035 1432725 2848761 5941580 +-3 -3 6 45 156 417 980 2153 4553 9363 18732 36363 68340 124251 218670 373067 618221 997217 1569114 2413377 3635172 +12 21 30 39 48 57 66 75 84 93 102 111 120 129 138 147 156 165 174 183 192 +-7 -12 -7 25 100 241 508 1055 2222 4675 9605 18988 35921 65168 114446 197962 345822 627164 1203113 2441664 5157899 +8 26 61 125 250 518 1113 2405 5081 10345 20218 37980 68809 120687 205660 341558 554302 880948 1373643 2104695 3172988 +8 29 63 115 187 275 366 435 442 329 17 -597 -1643 -3281 -5704 -9141 -13860 -20171 -28429 -39037 -52449 +17 26 49 101 197 352 581 899 1321 1862 2537 3361 4349 5516 6877 8447 10241 12274 14561 17117 19957 +13 22 35 56 94 157 258 453 948 2346 6161 15809 38401 87815 189718 389450 763975 1439454 2616407 4604910 7872824 +8 25 44 56 43 -24 -169 -357 -377 373 3254 11001 28763 65952 139808 282852 559230 1100809 2185188 4398318 8959855 +14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 +0 6 20 42 72 110 156 210 272 342 420 506 600 702 812 930 1056 1190 1332 1482 1640 +5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 +15 42 96 204 410 775 1386 2400 4167 7493 14116 27474 53860 104154 196688 362880 659993 1201557 2229064 4274711 8515044 +15 27 60 124 229 385 602 890 1259 1719 2280 2952 3745 4669 5734 6950 8327 9875 11604 13524 15645 +2 -4 -9 -6 25 136 440 1150 2628 5444 10445 18834 32259 52912 83638 128054 190678 277068 393971 549482 753213 +25 40 65 110 195 354 643 1165 2130 3987 7711 15414 31588 65493 135487 276471 552103 1074034 2031149 3732670 6670009 +8 21 52 109 201 340 536 795 1145 1740 3143 6991 17437 44107 107898 251917 561426 1199103 2465650 4901305 9451837 +6 17 46 96 174 298 514 931 1778 3478 6720 12491 22006 36445 56372 80672 104798 118071 99722 13306 -200946 +11 30 60 101 153 216 290 375 471 578 696 825 965 1116 1278 1451 1635 1830 2036 2253 2481 +16 33 72 150 301 595 1160 2213 4119 7527 13697 25272 48036 94738 192986 400697 834924 1723731 3497735 6951565 13533315 +-7 -8 -9 -3 43 203 607 1456 3037 5738 10063 16647 26271 39877 58583 83698 116737 159436 213767 281953 366483 +20 24 30 47 100 251 622 1410 2878 5299 8829 13317 18199 23031 30198 53409 139564 418662 1208316 3218487 7931346 +8 33 72 139 274 553 1094 2064 3706 6424 10986 18928 33264 59626 107972 195007 347460 606347 1032324 1712193 2766566 +-1 2 22 80 213 482 987 1894 3477 6179 10706 18193 30527 50985 85451 144621 247795 429096 747254 1300454 2248177 +10 17 24 41 100 275 720 1733 3859 8065 16081 31159 59858 116178 230676 469428 971284 2017349 4154698 8407833 16627316 +17 41 73 117 193 357 735 1586 3419 7198 14687 29049 55996 106236 200932 383802 747033 1484423 2995713 6083285 12309647 +6 11 23 61 153 335 662 1247 2347 4515 8840 17327 33588 64352 123091 238686 475116 973511 2036781 4291061 8979563 +10 21 43 87 159 258 389 614 1187 2866 7575 19706 48499 112096 243994 502677 985209 1845841 3322433 5780038 9800050 +14 29 53 88 128 160 170 154 134 179 431 1136 2680 5630 10780 19202 32302 51881 80201 120056 174848 +17 32 47 62 77 92 107 122 137 152 167 182 197 212 227 242 257 272 287 302 317 +6 6 19 61 164 392 865 1804 3620 7083 13630 25915 48784 90993 168200 308080 558866 1003244 1780365 3119825 5392852 +13 40 81 132 188 260 422 903 2239 5500 12607 26754 52950 98696 174812 296429 484161 765472 1176253 1762624 2582976 +21 35 53 76 105 141 185 238 301 375 461 560 673 801 945 1106 1285 1483 1701 1940 2201 +12 35 74 135 227 362 555 824 1190 1677 2312 3125 4149 5420 6977 8862 11120 13799 16950 20627 24887 +4 17 38 68 119 232 517 1223 2846 6288 13099 25892 49171 91150 167824 311820 590752 1143407 2247740 4443192 8742335 +24 41 64 93 135 216 412 920 2202 5266 12212 27282 58825 122835 249056 491087 942476 1761479 3207992 5697155 9875291 +5 1 8 40 119 279 568 1059 1895 3423 6527 13363 28861 63659 139699 300753 631998 1296034 2598655 5108763 9878196 +9 28 66 136 256 461 833 1559 3029 5988 11758 22548 41872 75097 130145 218375 355673 563780 871890 1318552 1953912 +15 26 31 31 32 45 99 284 851 2423 6441 16128 38572 89098 200030 437386 931283 1929535 3890785 7647382 14697248 +6 10 28 70 142 246 380 538 710 882 1036 1150 1198 1150 972 626 70 -742 -1860 -3338 -5234 +21 45 94 178 302 466 664 885 1137 1540 2571 5606 14012 35225 84545 191831 412941 848695 1675412 3192762 5896866 +7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 +8 18 49 109 209 375 679 1298 2604 5283 10493 20127 37392 68231 124758 233137 450732 901756 1848445 3828109 7908407 +7 8 6 11 49 174 492 1215 2771 5999 12456 24856 47649 87731 155254 264478 434575 690258 1062066 1586089 2302865 +15 20 18 11 14 60 213 599 1463 3267 6874 13940 27807 55549 112560 232584 489227 1041641 2231346 4787844 10265872 +22 40 77 154 299 554 996 1782 3230 5949 11031 20319 36791 65239 113907 199122 358373 685173 1416140 3136067 7236646 +-3 3 14 30 51 77 108 144 185 231 282 338 399 465 536 612 693 779 870 966 1067 +16 42 80 142 248 428 730 1233 2069 3468 5853 10023 17461 30772 54161 93665 156555 249083 372155 517101 671863 +3 -3 -4 5 22 34 14 -70 -201 -152 879 4994 16977 46978 115924 266658 586727 1253787 2622842 5387415 10866116 +12 20 38 84 200 461 994 2017 3906 7307 13348 24100 43622 80248 151288 292083 572448 1125038 2192170 4200228 7874076 +2 -6 -4 36 157 417 889 1661 2836 4532 6882 10034 14151 19411 26007 34147 44054 55966 70136 86832 106337 +25 46 78 123 187 277 403 607 1048 2183 5114 12241 28496 63655 136540 282303 564347 1092632 2049906 3726495 6562361 +16 24 46 103 224 441 795 1373 2413 4541 9241 19706 42275 88728 179788 350266 656382 1185902 2071848 3510665 5785866 +-5 -5 -5 -14 -30 -25 70 380 1101 2515 5005 9070 15340 24591 37760 55960 80495 112875 154831 208330 275590 +11 30 67 139 283 582 1211 2524 5215 10605 21153 41406 79872 152852 292296 561524 1085535 2107076 4086235 7870761 14977445 +2 9 17 27 50 121 317 783 1778 3773 7677 15347 30666 61661 124393 249695 494274 958241 1811801 3334635 5972450 +-7 -1 17 48 94 164 286 531 1070 2319 5283 12292 28435 64146 139580 291635 584727 1126719 2091781 3752512 6524580 +23 34 48 69 116 243 582 1438 3479 8082 17923 37955 77053 150914 287438 537013 992203 1824718 3352774 6159709 11295838 +5 10 28 69 143 260 430 663 969 1358 1840 2425 3123 3944 4898 5995 7245 8658 10244 12013 13975 +27 42 55 65 84 154 373 941 2239 4960 10336 20570 39721 75566 143501 274594 531959 1043606 2067497 4118543 8212374 +-7 -2 23 80 181 338 563 868 1265 1766 2383 3128 4013 5050 6251 7628 9193 10958 12935 15136 17573 +21 27 34 58 128 296 659 1393 2799 5361 9816 17236 29122 47510 75089 115331 172633 252471 361566 508062 701716 +15 23 38 84 211 521 1210 2634 5412 10584 19847 35897 62910 107200 178097 289093 459309 715341 1093548 1642850 2428109 +10 19 35 70 164 396 894 1846 3514 6252 10536 17055 27033 43224 72555 132365 263902 559701 1216505 2633828 5592118 +10 22 44 75 114 160 212 269 330 394 460 527 594 660 724 785 842 894 940 979 1010 +15 31 59 110 202 368 664 1181 2082 3717 6921 13677 28437 60567 128708 268584 547603 1094058 2159389 4256547 8472302 +8 28 63 113 178 258 353 463 588 728 883 1053 1238 1438 1653 1883 2128 2388 2663 2953 3258 +24 49 88 152 259 445 798 1528 3093 6411 13211 26635 52339 100623 190660 358867 675130 1273341 2407062 4547826 8553583 +17 27 39 58 107 237 529 1090 2050 3572 5892 9411 14866 23612 38052 62257 102823 170017 279269 453072 723357 +17 38 79 152 287 555 1115 2299 4749 9620 18863 35602 64619 112961 190683 311741 495049 765714 1156463 1709276 2477239 +-1 6 26 79 199 436 853 1528 2589 4335 7527 13965 27495 55616 111899 219533 416563 763928 1358476 2355087 4005415 +-3 -1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 +14 23 29 43 82 177 393 858 1801 3622 7080 13821 27724 57991 125686 276844 607988 1315253 2788839 5794615 11821690 +18 30 63 143 311 626 1168 2041 3376 5334 8109 11931 17069 23834 32582 43717 57694 75022 96267 122055 153075 +-4 4 17 41 98 236 554 1266 2841 6273 13569 28630 58917 118781 236322 467475 924202 1828890 3615241 7108295 13834284 +14 21 25 28 46 132 416 1170 2908 6535 13570 26491 49290 88388 154149 263353 443146 737185 1214943 1985438 3217006 +20 47 94 171 294 501 877 1595 3001 5802 11457 22922 45961 91306 178030 338588 626082 1124417 1962136 3330853 5509344 +16 33 67 132 260 510 980 1825 3289 5777 10050 17769 32932 65413 139144 310051 703659 1591044 3537510 7686105 16286453 +6 14 36 99 249 567 1200 2414 4685 8857 16410 29891 53560 94282 162644 274180 450432 719344 1114160 1669555 2413147 +-4 3 35 112 262 532 1017 1914 3606 6779 12576 22797 40156 68584 113492 181784 281384 420627 610337 878442 1323562 +25 49 86 139 224 386 720 1397 2695 5035 9022 15491 25558 40676 62696 93933 137237 196069 274582 377707 511244 +5 -1 -12 -15 21 151 463 1090 2225 4139 7202 11907 18897 28995 43237 62908 89581 125159 171920 232565 310269 +11 39 85 158 270 440 702 1125 1872 3348 6509 13423 28194 58394 117221 226753 422957 763617 1341169 2303704 3889282 +17 26 35 61 141 343 781 1639 3220 6062 11226 21001 40556 81609 170156 362011 772902 1635232 3403608 6950711 13934398 +-6 -8 -9 -9 -8 -6 -3 1 6 12 19 27 36 46 57 69 82 96 111 127 144 +14 31 72 162 341 673 1257 2252 3940 6861 12071 21626 39555 74023 142457 283793 586898 1253611 2731846 5983494 13000249 +15 17 28 61 128 233 358 442 360 -73 -1017 -2334 -2914 873 18699 74262 223033 590357 1449862 3377911 7545392 +3 5 10 17 34 88 235 570 1237 2439 4448 7615 12380 19282 28969 42208 59895 83065 112902 150749 198118 +5 3 -1 -6 -6 31 203 743 2132 5282 11850 24844 49923 98298 193092 382667 767111 1548229 3119537 6221574 12200112 +-2 5 33 111 283 608 1160 2028 3316 5143 7643 10965 15273 20746 27578 35978 46170 58393 72901 89963 109863 +3 19 47 87 139 203 279 367 467 579 703 839 987 1147 1319 1503 1699 1907 2127 2359 2603 +13 35 76 145 250 402 630 1021 1811 3569 7536 16205 34256 69992 137458 259465 471785 828831 1411188 2335417 3766614 +8 17 28 38 56 125 363 1034 2660 6185 13202 26254 49220 87797 150089 247314 394640 612161 926024 1369718 1985536 +8 25 48 77 112 153 200 253 312 377 448 525 608 697 792 893 1000 1113 1232 1357 1488 +12 21 37 57 77 106 189 437 1076 2557 5818 12860 27895 59448 123950 251548 495084 943461 1740923 3114131 5409321 +15 13 12 29 88 219 475 983 2051 4377 9459 20405 43526 91443 189118 385554 776487 1548205 3061254 6007625 11699548 +15 24 32 34 36 74 256 853 2483 6455 15380 34237 72237 146103 285867 545187 1020019 1883403 3452614 6322987 11639994 +2 -2 -9 -10 11 77 221 500 1043 2178 4715 10516 23585 52107 112228 235006 479028 952886 1854307 3536586 6618515 +8 18 43 83 138 208 293 393 508 638 783 943 1118 1308 1513 1733 1968 2218 2483 2763 3058 +-7 -3 17 65 168 380 794 1554 2867 5015 8367 13391 20666 30894 44912 63704 88413 120353 161021 212109 275516 +5 27 60 98 140 202 340 692 1547 3449 7344 14778 28154 51056 88648 148156 239441 375671 574100 856962 1252488 +11 16 32 60 108 214 483 1149 2686 6005 12795 26111 51402 98330 183979 338409 613985 1100506 1948862 3406730 5870636 +23 38 73 156 324 614 1053 1660 2486 3743 6117 11437 24016 53272 118853 260775 559661 1177128 2435585 4973482 10042336 +11 25 49 80 118 167 243 406 846 2079 5350 13403 31893 71974 155234 323696 661203 1340508 2727535 5609875 11688426 +0 7 30 87 204 431 871 1722 3332 6279 11526 20779 37308 67691 125223 236110 450056 857463 1616214 2991911 5416508 +14 13 4 -16 -50 -101 -172 -266 -386 -535 -716 -932 -1186 -1481 -1820 -2206 -2642 -3131 -3676 -4280 -4946 +14 37 67 97 127 173 273 490 912 1649 2827 4579 7033 10297 14441 19476 25330 31821 38627 45253 50995 +11 16 31 77 184 394 761 1351 2258 3671 6052 10516 19541 38179 75988 149960 288781 538826 972365 1698535 2877718 +1 13 39 79 133 201 283 379 489 613 751 903 1069 1249 1443 1651 1873 2109 2359 2623 2901 +12 27 48 77 116 167 232 313 412 531 672 837 1028 1247 1496 1777 2092 2443 2832 3261 3732 +10 22 48 97 177 296 463 683 941 1173 1227 824 -462 -3175 -7856 -14772 -23420 -31712 -34726 -22885 20599 +7 20 49 102 181 291 461 783 1484 3068 6616 14434 31421 67828 144541 302702 620449 1240888 2417199 4583130 8460169 +9 12 19 30 45 64 87 114 145 180 219 262 309 360 415 474 537 604 675 750 829 +10 27 63 136 275 524 959 1726 3117 5725 10763 20700 40469 79676 156596 305542 590960 1135287 2174803 4170928 8027451 +6 12 11 14 57 224 689 1784 4102 8647 17047 31851 56937 98065 163617 265575 420798 652670 993203 1485692 2188033 +9 12 29 72 150 276 492 937 2012 4739 11464 27119 61364 132165 271918 538448 1035663 1953190 3642211 6757682 12517478 +-3 4 26 84 218 502 1072 2183 4324 8433 16267 30995 58095 106649 191143 333892 568223 942562 1525584 2412598 3733352 +14 19 28 41 58 79 104 133 166 203 244 289 338 391 448 509 574 643 716 793 874 +18 24 37 66 116 189 303 553 1256 3258 8557 21550 51502 117344 256749 542762 1113270 2221544 4320285 8197454 15190144 +11 35 77 142 235 361 525 732 987 1295 1661 2090 2587 3157 3805 4536 5355 6267 7277 8390 9611 +9 11 26 66 145 286 537 1006 1947 3964 8448 18423 40051 85133 175043 346645 660869 1214761 2157974 3714832 6213277 +7 15 28 46 69 97 130 168 211 259 312 370 433 501 574 652 735 823 916 1014 1117 +-2 -3 -5 -8 -1 59 274 838 2072 4445 8538 14869 23483 33326 41878 46690 52974 96290 298637 993983 2994435 +22 46 77 112 143 168 232 514 1472 4053 9979 22145 45220 86640 158386 280488 488760 853425 1525289 2848141 5621063 +8 6 0 -3 17 105 364 1032 2644 6349 14496 31666 66413 134090 261280 492531 900312 1599368 2766960 4670835 7707185 +14 28 56 108 206 400 792 1583 3167 6298 12361 23817 45021 83929 155901 292238 558964 1096956 2205030 4506586 9273472 +1 8 31 89 201 395 730 1331 2448 4572 8674 16677 32326 62687 120583 228363 423499 766616 1352681 2326209 3901487 +17 31 53 83 121 167 221 283 353 431 517 611 713 823 941 1067 1201 1343 1493 1651 1817 +0 -5 -3 20 84 216 449 822 1402 2387 4416 9320 21716 52113 122650 277395 600628 1249279 2510623 4904888 9366748 +16 32 50 70 92 116 142 170 200 232 266 302 340 380 422 466 512 560 610 662 716 +24 33 56 121 277 608 1267 2552 5053 9914 19295 37223 71249 135773 258702 494493 949007 1825758 3510739 6727468 12822050 +11 18 28 49 106 257 614 1370 2842 5564 10512 19640 37104 71950 143831 294852 613598 1283112 2675755 5539955 11367623 +5 8 10 6 -9 -40 -92 -170 -279 -424 -610 -842 -1125 -1464 -1864 -2330 -2867 -3480 -4174 -4954 -5825 +14 20 37 84 191 403 786 1433 2480 4164 6994 12177 22564 44578 91878 191917 397078 802720 1575223 2993958 5511977 +20 30 39 48 59 87 191 539 1522 3931 9213 19827 39722 74940 134283 229855 377161 594723 905355 1349742 2049180 +5 19 49 122 279 578 1107 2011 3546 6193 10896 19530 35758 66500 124312 231059 423363 760415 1334859 2287586 3827417 +6 10 20 53 134 312 695 1517 3272 6998 14894 31659 67349 143308 304080 640540 1333491 2734047 5510188 10914195 21276343 +20 45 99 211 439 896 1790 3476 6517 11755 20418 34380 56950 95189 166074 311373 630704 1350358 2959773 6473472 13924803 +17 42 92 191 373 680 1162 1888 2982 4698 7553 12566 21742 39173 73663 144918 297591 631686 1365346 2958925 6350507 +6 6 3 8 47 161 406 853 1588 2712 4341 6606 9653 13643 18752 25171 33106 42778 54423 68292 84651 +-5 -13 -12 12 73 198 465 1074 2454 5411 11352 22723 44070 84753 165628 334463 699244 1496046 3220671 6873853 14403602 +-1 -3 4 35 113 266 532 986 1817 3512 7261 15806 35163 78034 170462 364705 764132 1571713 3185657 6390725 12745254 +8 29 64 111 166 223 274 309 316 281 188 19 -246 -629 -1154 -1847 -2736 -3851 -5224 -6889 -8882 +17 25 32 44 79 170 374 808 1743 3789 8204 17379 35631 70653 136460 259674 492925 942701 1825264 3574962 7046935 +6 1 -8 -14 3 96 390 1145 2847 6330 12931 24679 44518 76563 126387 201336 310868 466911 684234 980824 1378261 +12 24 48 80 106 112 104 128 288 784 2043 5111 12648 31200 76075 181425 420540 945688 2064266 4380234 9049078 +15 27 48 77 112 162 284 671 1832 4920 12279 28296 60659 122137 233013 424316 742013 1252337 2048442 3258591 5056098 +1 4 8 18 57 183 526 1359 3217 7078 14620 28568 53145 94641 162114 268237 430305 671416 1021840 1520590 2217209 +15 30 56 107 209 407 772 1408 2459 4116 6624 10289 15485 22661 32348 45166 61831 83162 110088 143655 185033 +12 33 72 148 291 544 983 1768 3238 6063 11466 21528 39589 70758 122545 205628 334768 529885 817308 1231212 1815255 +11 13 12 16 44 138 386 966 2232 4874 10195 20559 40075 75593 138099 244607 420657 703539 1146374 1823194 2835174 +22 36 61 106 180 292 451 666 946 1300 1737 2266 2896 3636 4495 5482 6606 7876 9301 10890 12652 +21 46 92 179 341 642 1214 2333 4556 8947 17415 33160 61158 108502 184274 298560 460519 676672 953882 1318697 1878747 +21 31 40 41 20 -52 -230 -599 -1237 -2062 -2428 -258 9595 38227 107657 259844 574662 1209142 2487229 5105340 10590935 +21 31 32 20 -9 -59 -134 -238 -375 -549 -764 -1024 -1333 -1695 -2114 -2594 -3139 -3753 -4440 -5204 -6049 +20 45 77 111 142 165 175 167 136 77 -15 -145 -318 -539 -813 -1145 -1540 -2003 -2539 -3153 -3850 +24 37 45 46 42 51 127 389 1075 2672 6236 14115 31431 68872 147600 307404 619626 1206871 2272087 4140276 7316880 +24 47 77 127 233 460 920 1829 3648 7382 15157 31274 64087 129335 256082 497340 948984 1783001 3304813 6049833 10942109 +10 16 20 15 0 -12 14 143 478 1168 2416 4487 7716 12516 19386 28919 41810 58864 81004 109279 144872 +21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201 211 221 +23 43 84 158 278 455 694 989 1317 1631 1852 1860 1484 491 -1426 -4661 -9709 -17181 -27820 -42518 -62334 +-2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 +11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96 101 106 111 +23 32 51 90 156 255 394 583 837 1178 1637 2256 3090 4209 5700 7669 10243 13572 17831 23222 29976 +6 3 13 59 179 426 864 1556 2543 3821 5334 7013 8902 11420 15811 24830 43700 81351 151915 276399 484389 +2 6 25 67 150 313 623 1186 2198 4124 8178 17404 38836 87453 192952 410747 839074 1644650 3100007 5636409 9917170 +27 48 86 149 245 382 568 811 1119 1500 1962 2513 3161 3914 4780 5767 6883 8136 9534 11085 12797 +5 19 33 55 116 281 660 1419 2791 5087 8707 14151 22030 33077 48158 68283 94617 128491 171413 225079 291384 +18 46 90 149 223 329 541 1081 2500 5993 13897 30446 62937 123648 233214 426802 765446 1356448 2388988 4194211 7343299 +11 11 21 50 124 300 680 1425 2769 5033 8639 14124 22154 33538 49242 70403 98343 134583 180857 239126 311592 +7 30 76 151 254 378 525 756 1303 2778 6539 15342 34563 74575 155393 315560 628571 1232082 2377922 4514749 8420336 +21 49 100 184 325 569 996 1746 3084 5569 10475 20762 43142 92165 197805 418804 865087 1733953 3366542 6333348 11560371 +11 23 35 47 59 71 83 95 107 119 131 143 155 167 179 191 203 215 227 239 251 +3 8 13 18 23 28 33 38 43 48 53 58 63 68 73 78 83 88 93 98 103 +14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71 74 +29 44 63 91 135 207 339 631 1365 3230 7715 17739 38599 79329 154575 287103 511069 876192 1452983 2339195 3667671 +-4 -4 9 57 175 421 889 1730 3206 5830 10684 20072 38788 76514 152291 302740 596900 1162388 2230311 4210263 7812169 +-5 5 34 89 177 305 480 709 999 1357 1790 2305 2909 3609 4412 5325 6355 7509 8794 10217 11785 +17 32 63 137 305 658 1362 2729 5355 10395 20135 39199 77043 152902 305171 608512 1204200 2353225 4529206 8582564 16034588 +28 44 62 82 104 128 154 182 212 244 278 314 352 392 434 478 524 572 622 674 728 +13 27 62 132 252 437 718 1201 2202 4492 9681 20773 42974 85002 161527 298053 540574 973550 1750651 3142119 5598111 +9 25 58 120 230 428 809 1596 3274 6808 13975 27862 53637 99838 180763 321314 567277 1007298 1819268 3366505 6394114 +0 9 30 77 182 410 883 1813 3544 6603 11760 20097 33086 52676 81389 122425 179776 258349 364098 504165 687030 +-5 1 22 70 167 350 679 1249 2211 3826 6620 11787 22111 43857 90325 188080 387275 777983 1515058 2854764 5207255 +7 15 23 32 43 57 75 98 127 163 207 260 323 397 483 582 695 823 967 1128 1307 +19 23 34 70 165 377 810 1663 3315 6450 12236 22625 40977 73482 132324 242276 453523 865081 1665326 3198992 6073677 +22 47 78 115 167 257 422 712 1200 2027 3541 6681 13955 31726 75129 177921 411197 917897 1976121 4117455 8355354 +-2 12 43 98 201 409 835 1692 3381 6655 12900 24583 45926 83874 149434 259471 439056 724470 1166977 1837488 2832247 +21 31 54 100 180 303 467 654 855 1176 2114 5147 13858 35914 86351 192779 403321 798341 1507302 2732430 4781248 +1 10 32 71 137 257 491 959 1894 3745 7363 14312 27356 51182 93428 166094 287423 484348 795610 1275661 1999475 +22 28 37 53 80 122 183 267 378 520 697 913 1172 1478 1835 2247 2718 3252 3853 4525 5272 +14 25 30 30 28 39 108 345 1005 2676 6703 16099 37423 84516 185710 397426 829545 1692920 3389905 6691225 13089923 +24 47 79 126 211 380 708 1305 2322 3957 6461 10144 15381 22618 32378 45267 61980 83307 110139 143474 184423 +27 50 95 181 333 582 965 1525 2311 3378 4787 6605 8905 11766 15273 19517 24595 30610 37671 45893 55397 +4 4 6 25 95 289 755 1774 3854 7899 15559 30028 57906 113430 227640 467231 971500 2021814 4167860 8450995 16791197 +16 33 60 110 207 403 802 1595 3128 6050 11619 22291 42812 82254 157962 303601 586212 1142943 2259690 4536000 9220961 +-1 -1 11 54 149 323 634 1243 2578 5657 12672 28006 59994 123993 247753 480751 910145 1687419 3071729 5498542 9685515 diff --git a/2023/09-Mirage_Maintenance/second.hs b/2023/09-Mirage_Maintenance/second.hs new file mode 100644 index 0000000..77e9b97 --- /dev/null +++ b/2023/09-Mirage_Maintenance/second.hs @@ -0,0 +1,53 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 2 + +type History = [Int] +type Input = [History] + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read <$> some (char '-' <|> digitChar) <* hspace + +parseInput' :: Parser Input +parseInput' = some (some parseNumber <* eol) <* eof + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> error $ errorBundlePretty bundle + Right input' -> return input' + +compute :: Input -> Int +compute = sum . map (next . reverse) + where + next :: History -> Int + next = sum . map last . takeWhile (any (/= 0)) . iterate differences + differences :: History -> History + differences xs = zipWith (flip (-)) xs (tail xs) + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input -- cgit v1.2.3