From fd1fbb916f1ff33142e6fdadfe7a9800ebe240d1 Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Tue, 5 Dec 2023 16:57:54 +0100 Subject: 2023-05 in haskell --- 2023/05-If_You_Give_A_Seed_A_Fertilizer/example | 33 +++ 2023/05-If_You_Give_A_Seed_A_Fertilizer/first.hs | 65 ++++++ 2023/05-If_You_Give_A_Seed_A_Fertilizer/input | 243 +++++++++++++++++++++ .../intervals.excalidraw.svg | 21 ++ 2023/05-If_You_Give_A_Seed_A_Fertilizer/second.hs | 71 ++++++ 5 files changed, 433 insertions(+) create mode 100644 2023/05-If_You_Give_A_Seed_A_Fertilizer/example create mode 100644 2023/05-If_You_Give_A_Seed_A_Fertilizer/first.hs create mode 100644 2023/05-If_You_Give_A_Seed_A_Fertilizer/input create mode 100644 2023/05-If_You_Give_A_Seed_A_Fertilizer/intervals.excalidraw.svg create mode 100644 2023/05-If_You_Give_A_Seed_A_Fertilizer/second.hs diff --git a/2023/05-If_You_Give_A_Seed_A_Fertilizer/example b/2023/05-If_You_Give_A_Seed_A_Fertilizer/example new file mode 100644 index 0000000..f756727 --- /dev/null +++ b/2023/05-If_You_Give_A_Seed_A_Fertilizer/example @@ -0,0 +1,33 @@ +seeds: 79 14 55 13 + +seed-to-soil map: +50 98 2 +52 50 48 + +soil-to-fertilizer map: +0 15 37 +37 52 2 +39 0 15 + +fertilizer-to-water map: +49 53 8 +0 11 42 +42 0 7 +57 7 4 + +water-to-light map: +88 18 7 +18 25 70 + +light-to-temperature map: +45 77 23 +81 45 19 +68 64 13 + +temperature-to-humidity map: +0 69 1 +1 0 69 + +humidity-to-location map: +60 56 37 +56 93 4 diff --git a/2023/05-If_You_Give_A_Seed_A_Fertilizer/first.hs b/2023/05-If_You_Give_A_Seed_A_Fertilizer/first.hs new file mode 100644 index 0000000..18d030b --- /dev/null +++ b/2023/05-If_You_Give_A_Seed_A_Fertilizer/first.hs @@ -0,0 +1,65 @@ +-- 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.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 + +exampleExpectedOutput = 35 + +data Map = Map Int Int Int deriving Show -- destination source range +data Mapping = Mapping String String [Map] deriving Show -- sourceStr destStr +data Input = Input [Int] [Mapping] deriving Show -- seeds mappings + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read <$> some digitChar <* many (char ' ') + +parseMap :: Parser Map +parseMap = Map <$> parseNumber + <*> parseNumber + <*> parseNumber <* eol + +parseMapping :: Parser Mapping +parseMapping = Mapping <$> (some letterChar <* string "-to-") + <*> (some letterChar <* string " map:" <* eol) + <*> some parseMap <* optional eol + +parseInput' :: Parser Input +parseInput' = Input <$> (string "seeds: " *> some parseNumber <* some eol) + <*> some parseMapping <* 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' + +step :: [Map] -> Int -> Int +step [] n = n +step (Map dest src range:ms) n | n>=src && n Mapping -> [Int] +stepMapping values (Mapping _ _ ms) = map (step ms) values + +compute :: Input -> Int +compute (Input values mappings) = minimum $ L.foldl' stepMapping values mappings + +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/05-If_You_Give_A_Seed_A_Fertilizer/input b/2023/05-If_You_Give_A_Seed_A_Fertilizer/input new file mode 100644 index 0000000..d93c0e7 --- /dev/null +++ b/2023/05-If_You_Give_A_Seed_A_Fertilizer/input @@ -0,0 +1,243 @@ +seeds: 1514493331 295250933 3793791524 105394212 828589016 654882197 658370118 49359719 4055197159 59237418 314462259 268880047 2249227634 74967914 2370414906 38444198 3291001718 85800943 2102534948 5923540 + +seed-to-soil map: +3352941879 1247490906 129850502 +1738919961 2189748071 56658550 +1795578511 292133467 518088747 +1519757661 1666834550 130335907 +1650093568 133993362 88826393 +2813914030 2262539545 40894545 +2698412916 2661705133 115501114 +2854808575 810222214 437268692 +410530961 1545057218 121777332 +0 242661076 10731898 +532308293 2303434090 61476099 +3292077267 1797170457 2282798 +2313667258 0 133993362 +2447660620 2410952837 250752296 +3294360065 253392974 38740493 +10731898 1377341408 167715810 +1457582089 2364910189 46042648 +593784392 3009289500 824592362 +3333100558 222819755 19841321 +1418376754 1799453255 39205335 +1503624737 2246406621 16132924 +178447708 2777206247 232083253 +3482792381 1838658590 351089481 + +soil-to-fertilizer map: +3513795976 4258851234 36116062 +3393453635 4148223693 110627541 +3504081176 3494735450 6350258 +2671742993 3596285367 235915393 +991290653 256764866 25867175 +2907658386 3330719253 68855819 +3336496635 4091266693 56957000 +3161141476 2536943456 80523019 +1961696534 304660310 29551079 +812996514 1560772632 178294139 +1562163347 2321959023 78904062 +31289107 1039870587 339682886 +1520029818 1928417376 42133529 +3510431434 3832200760 3364542 +3549912038 3272523584 58195669 +0 149071717 31289107 +3608107707 3501085708 5732766 +503523937 1739066771 189350605 +3071674583 3506818474 89466893 +3241664495 3996434553 94832140 +1708133363 454333361 253563171 +3813493721 3097084118 175439466 +1991247613 1970550905 351408118 +3613840473 2897430870 199653248 +2536943456 2762631333 134799537 +1641067409 244319429 12445437 +3994753216 3913095788 83338765 +2976514205 3399575072 95160378 +1354883134 0 143118415 +1349131883 2400863085 5751251 +1498001549 282632041 22028269 +2342655731 180360824 63958605 +370971993 1379553473 126598642 +4149802438 2617466475 145164858 +1017157828 707896532 331974055 +692874542 334211389 120121972 +497570635 143118415 5953302 +3988933187 3907275759 5820029 +4078091981 3835565302 71710457 +1653512846 1506152115 54620517 + +fertilizer-to-water map: +3053686523 2028998994 1241280773 +1492748555 1562401968 269616514 +554432178 1000324407 562077561 +2944878746 3270279767 108807777 +2501520804 3379087544 52288887 +1762365069 20686928 69653413 +2028998994 3431376431 472521810 +1431309984 814973200 3653900 +409832614 0 20686928 +430519542 818627100 123912636 +1116509739 500172955 314800245 +2553809691 3903898241 391069055 +0 90340341 409832614 +1434963884 942539736 57784671 + +water-to-light map: +2774754469 1598606098 15160294 +3832622498 1469118874 129487224 +4125818569 3997047227 169148727 +1108418694 1130695768 196125912 +637654660 517892123 26551592 +2519230072 3399515763 135968347 +2751000257 3126996880 23754212 +861800165 884077239 88532605 +1469118874 2566660966 63929427 +2789914763 3150751092 63425583 +2853340346 2561960449 4700517 +1692681911 3397592997 1922766 +2858040863 1773257241 287341147 +2655198419 2851614649 15098309 +950332770 972609844 158085924 +591049922 471287385 46604738 +3482333989 3849276196 108901632 +1694604677 1613766392 159490849 +3591235621 3958177828 38869399 +3630105020 4166195954 128771342 +3205039781 3535484110 277294208 +2706794606 2060598388 44205651 +386607659 544443715 110595292 +3962109722 2540862463 21097986 +697311924 0 92263281 +558450415 404456802 11447837 +2409200012 3214176675 110030060 +569898252 862925569 21151670 +1354525884 415904639 55382746 +789575205 790700609 72224960 +3832262624 2690248164 359874 +163757080 181606223 222850579 +1533048301 2967363270 159633610 +497202951 784452458 6248151 +2670296728 3812778318 36497878 +3145382010 2630590393 59657771 +1854095526 2104804039 436058424 +0 655039007 74414138 +2390804262 2690608038 18395750 +1304544606 1326821680 49981278 +3758876362 3324206735 73386262 +664206252 1376802958 33105672 +74414138 92263281 89342942 +3983207708 2709003788 142610861 +503451102 729453145 54999313 +2290153950 2866712958 100650312 + +light-to-temperature map: +2054128675 422374783 216418447 +3729049939 3132111492 565917357 +524183620 1261361039 34450583 +723901655 638793230 74616934 +304496246 795175951 115896188 +1128506994 1008723417 50927515 +958650763 2074746732 3056214 +0 1224918384 36442655 +558634203 1059650932 165267452 +2052385426 713410164 1743249 +833053864 1953862956 120883776 +36442655 715153413 80022538 +1455705971 1506174459 386316618 +1842022589 1295811622 210362837 +2270547122 2077802946 24477429 +116465193 2102280375 188031053 +1179434509 945607414 63116003 +798518589 911072139 34535275 +3373647615 3893335786 195498774 +3696979816 3698028849 32070123 +1242550512 1892491077 43410067 +3051130577 2566857633 322517038 +3002478931 3844684140 48651646 +2311039190 3730098972 114585168 +2425624358 2311039190 187630064 +2819387158 2889374671 183091773 +1285960579 103791186 85466201 +1371426780 338095592 84279191 +1110545182 1935901144 17961812 +953937640 2290311428 4713123 +420392434 0 103791186 +961706977 189257387 148838205 +3637334768 3072466444 59645048 +3569146389 2498669254 68188379 +2613254422 4088834560 206132736 + +temperature-to-humidity map: +2032423062 2486277941 26281270 +333062067 2316624216 6051173 +1716048249 1385455997 91409968 +460397469 2512559211 69041956 +25538975 668468772 15388105 +2090913379 324344034 71221218 +2804805674 3018690414 130533369 +529439425 908821722 476634275 +1106765273 448560048 219908724 +2162134597 1476865965 445565302 +0 395565252 25538975 +4004204691 4019550481 43244121 +2058704332 0 32209047 +1516375281 2116951248 199672968 +3888833667 2764269134 115371024 +40927080 32209047 292134987 +1490276549 2581601167 26098732 +1360818538 2322675389 129458011 +1006073700 2043715496 73235752 +1079309452 421104227 27455821 +1807458217 683856877 224964845 +339113240 1922431267 121284229 +4155917040 2879640158 139050256 +2764269134 4171262830 40536540 +4047448812 4062794602 108468228 +2935339043 3149223783 870326698 +1326673997 2452133400 34144541 +3805665741 4211799370 83167926 + +humidity-to-location map: +3928575650 3147563455 98804874 +2357899446 2418187254 26586982 +449562184 2261875136 59054833 +308294839 60287808 141267345 +1872062279 1591999301 10857495 +1227084719 574109504 259895254 +1980177059 1765508840 13399403 +1162615704 1941046629 64469015 +2384486428 2654234915 114059261 +702311863 1515542756 40659242 +1993576462 2005515644 256359492 +3047301127 3246368329 27789688 +650396000 1713592977 51915863 +3701335066 3862068622 181049310 +1122863338 1673840611 39752366 +3075090815 4174917460 120049836 +3882384376 2778717800 46191274 +1626219043 201555153 245843236 +4027380524 3325898523 267586772 +3417979817 4043117932 13866284 +3281454033 2925002624 18592540 +110359150 1556201998 35797303 +2558833497 2444774236 209460679 +508617017 834004758 141778983 +1574315753 975783741 51903290 +2249935954 1027687031 107963492 +0 463750354 110359150 +2778717800 3593485295 268583327 +3195140651 2824909074 86313382 +3445626269 2943595164 203968291 +3324037823 4080975466 93941994 +742971105 1135650523 379892233 +146156453 1778908243 39038597 +3300046573 4056984216 23991250 +1503331938 1602856796 70983815 +185195050 1817946840 123099789 +3649594560 3274158017 21920411 +1486979973 447398389 16351965 +3671514971 3296078428 29820095 +2498545689 0 60287808 +3431846101 2911222456 13780168 +1882919774 2320929969 97257285 diff --git a/2023/05-If_You_Give_A_Seed_A_Fertilizer/intervals.excalidraw.svg b/2023/05-If_You_Give_A_Seed_A_Fertilizer/intervals.excalidraw.svg new file mode 100644 index 0000000..fcdc205 --- /dev/null +++ b/2023/05-If_You_Give_A_Seed_A_Fertilizer/intervals.excalidraw.svg @@ -0,0 +1,21 @@ + + + eyJ2ZXJzaW9uIjoiMSIsImVuY29kaW5nIjoiYnN0cmluZyIsImNvbXByZXNzZWQiOnRydWUsImVuY29kZWQiOiJ4nO2cW1PiSFx1MDAxNIDf/Vx1MDAxNVx1MDAxNPs4K9un7z1v3mZkvFxmioC6tUVcdTAwMDVcYlx1MDAxMFxyXHRcdTAwMWKCXGJb89+3wyhcdMHMXHUwMDA0JMjsXHUwMDFhq1S6XHUwMDFiTqf7fH0u6eafnVxcLu+P+2b+Yy5vPjZccttqecYo/3tQ/mB6XHUwMDAzy3V0XHUwMDE1nr5cdTAwMWW4Q685bdn1/f7g41x1MDAxZn+E7yg03d73d5m22TNcdTAwMWR/oNv9qV/ncv9Mf0fkeGbTN5yObU7fMK1cbkUxXHUwMDFjLzx3nalUxlx1MDAxOGKYXCI1a2Bcclx1MDAwZbU032zp2rZhXHUwMDBmzLAmKMq7nyfjK/dysv9wQibtPfvk0+iRhELblm2X/bE97dTA1TdcdTAwMTLWXHJ8z703a1bL7z7ff6Q86V2eO+x0XHUwMDFkc1x1MDAxMNw8zErdvtG0/HFQhtCs9PtcYnzMhSWP+pWMtFxi3oElisk+cG3XXHUwMDBiZP9cdTAwMDZm8Fx1MDAxM0pvXHUwMDE4zfuO7oLTmrXxPcNcdTAwMTn0XHJPT0jYbvR0V1Spgopes1x1MDAxNl3T6nT9QHxEujlcdTAwMWRnXG5MXHUwMDAy4zhsXHUwMDFjiOxcdTAwMTdb01x0/ytcdTAwMWNcXM/omcXgXHUwMDFkztC2oyPktJ5G6FkxQtUgTyXfwntcbtpcdTAwMWZFVCqUMOy3jO9zXHUwMDBmXHUwMDAygVCIXCJMgc7qbcu5j4u33eZ9qC47XHUwMDExWctpqeBJWlxukihcdTAwMDBOKEutpsdnvUnphDVOXHUwMDFi7oDdX9X3aO+0ud1qKmJqyml2akpcIrJ+oJiM6qFHlGydXlx1MDAwMkFcdTAwMTgk34heYpKkl0pcbsqI7k9qtXywi1x1MDAwZuUv9lB4jVJZli+qw8HVp19LLVx0znD1TKeWoFdZxJGg/+9cdTAwMDWTycRcdTAwMDVcdTAwMTNptVSAcfpcdTAwMDWTO0eH4nB0+6XYvjm4KV4+guuOtlsz43adZ2jXXHUwMDE5Qlx1MDAwNVx1MDAxNL14KkVVXHUwMDEyI65cdTAwMTBcdTAwMTFbp6haOTBlbF2K6puP/ks6XG6QpKNcdTAwMThR4FxmoyV0lF61b+uqPKmNK6eH5KI06Vx1MDAwMj76tXRcdTAwMTRnaNRcdTAwMDFcboC1ueZSsFx1MDAxN7STLGinXHUwMDEwhFx1MDAwMdGz8HrtnKvIdL1cZnvlOn7Zmpjz5Fx1MDAwNaWfjJ5lj+fmeaqfelx1MDAwMJ38XFzRnm11XHUwMDAyNc3bZntef31Lh2Gzat/th7VNLcKwXHUwMDFj01tcdTAwMWNcdTAwMTLXszqWY9hXi+L0nZnHz5OhZ4pF5nlgXHUwMDA2tVNPdyXKOIpcdTAwMTc+UyaxVlx1MDAwN6JUOPk/g1xm1e3HO//YqdBcdTAwMTK6rt2fX1x1MDAxZPb2J9tcctmC54y2XHQyXHUwMDFk1+nxJ+GtbVx1MDAxYzLAXGa4WMZbfofsXHUwMDA1yFx1MDAxMrMoIFx1MDAxMaeUXHSWnjJWP1x1MDAxYn3mlmT+ccXr9Gt1Pla97aZcZqJ5k6xtXHUwMDE5XHUwMDE2XHUwMDA1vXIhRVJShrSfxVx1MDAwNF5HXG7lXHUwMDE1poxSgaO6mC1lXHUwMDFm7Fxyc1x1MDAxNlx1MDAxNZglaTIxsFx1MDAxMaA9XHUwMDE2XHUwMDFkJabPV+pcdTAwMDFsXffGuH27v9e9XHUwMDFlnlbOdovF7Vx1MDAwNk3JzZmzZTnDTFxuXHUwMDFkzrA1XHUwMDA0NKtyhjHHOrx95+zVnEX87nhwXHUwMDA2XHUwMDE0pKB0ieDMKp+Q60n17NyWVV4/XHUwMDFh3VXO+o3tXHUwMDA2jctQ1jS1xUVM9lx1MDAxYUHjXHUwMDA1zlGQ5U9cdTAwMDWaUpxqXHUwMDBmk6wh9fqrhGZcdTAwMDOvuVnO5lx1MDAwNGbJXHUwMDE5TeRMYtDmTMr09qx6d1hhdr00XHUwMDE2lceLm33PON3t0e3GLJ5cdTAwMDNcdTAwMTFcdTAwMTlmkJfEXGZcYsVIO7ZviFx1MDAxOWDtNKJ3zLI0Z1x1MDAwMjgmgNNTdlj8+1x1MDAxMmpcdTAwMGbFYVx1MDAwNVx1MDAxZUajq9p42LoztpsyQHRcdTAwMWUzwrPDTKpcdTAwMDJVXHUwMDE40uZAsKRSov+XLfugx69jblx1MDAxY7W42LfKiGAmqNQqklx1MDAxYTlvWGl3m7a67Hbx3a5/vXddPuBbjlx1MDAxY+abs2zLXCJcdTAwMDeKUkXwXHUwMDFi5vZcdTAwMDFcdTAwMTMmuIqq4jt0qaGbtnpcdTAwMDG6yHjEnUngSFx1MDAxMpF+N4LfaHtcdTAwMGZm6YCfXFwh8/a0Z6vqrr/dyMV9SZplXHUwMDBlMpKHmaG2uHlLYiyVkpk84sVPJVx1MDAxYtqLXHUwMDEwXHUwMDE5SsPz9y2nZTmd+FtMp5VQY1x1MDAxYlx1MDAwM//A7fUsX3ej5FqOXHUwMDFmbzH93D3Pc0dd01hcdTAwMThcdTAwMGL9yYl1/eDjwlxykMFcdTAwMTX+l1x1MDAwYqdl+mL2/1+/v9g6MrOx9jvRv8uiqVx1MDAxMvOWmHIgTJL05rAtXHUwMDFmneFlsTVcdTAwMTZt1Oy1XHUwMDFl6afrI2vr2SxIhjBRREzzXHUwMDE3c6RKXG5cdTAwMDVcdTAwMWFcZlx1MDAwMdejTzCK92u9ezCBKsFcdTAwMTHHXGKRyO7Xbrgmz3VcdTAwMDVkuEI/XHUwMDFiUFx1MDAwNlx1MDAxMDzRUWswoGvmXHUwMDFhXHUwMDAzU4Sv9DjvP8514sxcdTAwMDfX7uKkr4t7XHUwMDE2L1xmN2JpXHUwMDA3iHGB01x1MDAxYuUr/FhcdTAwMWKi3u3wRFZcdTAwMWJcdTAwMDP3uFK63De3XHUwMDFifK2VXHUwMDA1IFx1MDAxYyjoXHUwMDFi1U5q6I1OnWJcdTAwMGVcdTAwMDVcdTAwMDaSXHUwMDBioVx1MDAxN1x1MDAwN9BOSmbgK1mQnEgmscBcZlx0XHUwMDExmr5cYvjRrmjAI6P0XGY+krpcdTAwMDVcdTAwMTeZ7Hr9OfhzXHUwMDFmtuhSS1x1MDAwMZFA+lx1MDAxZP3nK3Hug2t3cdqXRD8pXHUwMDA0joBcdTAwMWTPOWnTQbTZT/9cdTAwMDSlaeK6L5x2ozK4PD2q7HfrXHUwMDEzsbfd5MvYo0qaYc5cdLAq6OnTo1xuKZO7UmDOdVxi+oaJJ1xmgjFcdTAwMTVcdTAwMGVu1jHwNFx1MDAxMM19yOmgNLeb2/BGnEThmSahXHUwMDEyXHTEWFx1MDAwMaVSLlx1MDAxMVx1MDAxMPdtUby8uTmsVe+aXHUwMDFkvKvuisXL7SZQxVJQMsusLy5ojVZpt75hRJQkalx1MDAxZLv0V8ZP80/pSvZyJfxsrfeB9n/YNHovXG7OMlxylbyxXHUwMDFiQPvegkmUPtitN9pnqtRcdTAwMTl6/a+fL84/Y9MqfVHbzVx1MDAxZKC46ctwl1x1MDAwZSpcYkRcdTAwMTGXQFx0XHUwMDE2QiD1Ukiro2+GgtibUVx1MDAxZIKDWlxiaYX2a7VLXHUwMDAya9iJuu6IXHUwMDE2U20k3yPaXHUwMDE3WifOfHAtzvmSbm1cdTAwMTLdJPHMm1x1MDAwNN1cdTAwMTWmVHq47epcdTAwMTfS3b1RctJ1XHUwMDBlm5ZcdTAwMDPcKLvbXHJ3kMlcIkpIzThcdTAwMTCqbViMdChcdTAwMTDCsVx1MDAxMoJIRFVkXd1O8HVcXC4p45mclntlQKvJV9F9xO/kz1x1MDAxYbxccvmRuYi705wqRiVK704j51x1MDAwMZ1PzKp98Vx1MDAxNcri9sA5Nq687SZ/0axneKhcdTAwMTBHXHUwMDFjy+RcdTAwMDdMIFx1MDAxNVxyNj1n8/VcdTAwMDCvtNva01vtYMl/nN7I1Mbap6IzKdhNPvKLXHUwMDA1XHUwMDBl1lx0np5O96gxUNQ8KJH+8KTbNNqVr+PyltNcdLE9TizLk15cZlxuXCLtflx1MDAwYoyCvCOmb3lcdTAwMDBcdTAwMDVjxind3Fx1MDAwMZQg5vye8nnDoDexXHUwMDAzr1x0fr9cdTAwMDNSs4p/O+Y+XHUwMDE077qlXHUwMDFic1x1MDAwMNdHXHUwMDE3XHUwMDBmXHUwMDE3kTt8kdXp85CYXHKJZkln38AhXG5S61xmoT87ebFIwrpcdTAwMTT9bVx0X1x1MDAwZlx1MDAxZbNTlphcdTAwMTMko1x1MDAxYqkjx4mS1szgXHUwMDBiXHUwMDEyXHUwMDE0nfOMk1x1MDAxN83l3FpgXHUwMDE0Vss7PdPVMlx1MDAwN9G5Wlx1MDAxNtCV2JsjY1x1MDAxNVwi5zu9gOBcdTAwMGZgMypcYpVqtf373ld3PKhWWYtcdTAwMWV3U8GG52FcdTAwMTN8XHUwMDExNsZcboxxrt3pnzw5eIctXHJsVFJtaFx1MDAwMC+kXHUwMDAwg3Ut+bvGkNA/JM1cdTAwMTnZ5VjjRGK20iOWyM7B+Vx1MDAwN1x1MDAxNr9cYm4/f9DyXHUwMDAz4lx1MDAxYXfHXHUwMDAz2Fx1MDAxZJ/Xx96n2+KRXHUwMDE4n1x1MDAxZlx1MDAxY5NUxMWdMLxIXHUwMDFjXHUwMDAw19Lxu3lbXHUwMDBicVJgyVxiiIV9JvlcdTAwMWal6kDqNVx1MDAwZjikOpa+bNYm+PNa8/aS2/aLkJfU/Vx1MDAwNFx1MDAwMHeeXHUwMDAyxbzR75d9PZb551g8/2CZo/1Flf6tPb3yO0/4XHUwMDA26mxOQ/hvO9/+XHUwMDA1zGOPWyJ9 + + + + + nnn+ln+lsrcsrcsrc+rangesrc+rangerange + src - nl - src + nl - range - src + ndestsrc - ndest - src + n \ No newline at end of file diff --git a/2023/05-If_You_Give_A_Seed_A_Fertilizer/second.hs b/2023/05-If_You_Give_A_Seed_A_Fertilizer/second.hs new file mode 100644 index 0000000..66d47db --- /dev/null +++ b/2023/05-If_You_Give_A_Seed_A_Fertilizer/second.hs @@ -0,0 +1,71 @@ +-- 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.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 + +exampleExpectedOutput = 46 + +data Range = Range Int Int deriving Show -- start range +data Map = Map Int Range deriving Show -- destination range +data Mapping = Mapping String String [Map] deriving Show -- sourceStr destStr +data Input = Input [Range] [Mapping] deriving Show -- seeds mappings + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read <$> some digitChar <* many (char ' ') + +parseRange :: Parser Range +parseRange = Range <$> parseNumber + <*> parseNumber + +parseMap :: Parser Map +parseMap = Map <$> parseNumber + <*> parseRange <* eol + +parseMapping :: Parser Mapping +parseMapping = Mapping <$> (some letterChar <* string "-to-") + <*> (some letterChar <* string " map:" <* eol) + <*> some parseMap <* optional eol + +parseInput' :: Parser Input +parseInput' = Input <$> (string "seeds: " *> some parseRange <* some eol) + <*> some parseMapping <* 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' + +step :: [Map] -> Range -> [Range] +step [] n = [n] +step (Map dest (Range src range):ms) r@(Range n l) | n+l<=src || n>=src+range = step ms r + | n>=src && n+l<=src+range = [Range (n-src+dest) l] + | n>=src = Range (n-src+dest) (range+src-n) : step ms (Range (src+range) (l-range-src+n)) + | otherwise = Range dest (l-src+n) : step ms (Range n (src-n)) + +stepMapping :: [Range] -> Mapping -> [Range] +stepMapping ranges (Mapping _ _ ms) = concatMap (step ms) ranges + +compute :: Input -> Int +compute (Input ranges mappings) = minimum $ map (\(Range start _) -> start) $ L.foldl' stepMapping ranges mappings + +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