diff options
Diffstat (limited to '')
-rw-r--r-- | 2023/19-Aplenty/example | 17 | ||||
-rw-r--r-- | 2023/19-Aplenty/first.hs | 117 | ||||
-rw-r--r-- | 2023/19-Aplenty/input | 718 | ||||
-rw-r--r-- | 2023/19-Aplenty/second.hs | 130 | ||||
-rw-r--r-- | 2023/20-Pulse_Propagation/example | 5 | ||||
-rw-r--r-- | 2023/20-Pulse_Propagation/example2 | 5 | ||||
-rw-r--r-- | 2023/20-Pulse_Propagation/first.hs | 119 | ||||
-rw-r--r-- | 2023/20-Pulse_Propagation/input | 58 | ||||
-rw-r--r-- | 2023/20-Pulse_Propagation/second.hs | 119 | ||||
-rw-r--r-- | 2023/21-Step_Counter/example | 11 | ||||
-rw-r--r-- | 2023/21-Step_Counter/first.hs | 85 | ||||
-rw-r--r-- | 2023/21-Step_Counter/input | 131 | ||||
-rw-r--r-- | 2023/21-Step_Counter/second.hs | 92 | ||||
-rw-r--r-- | 2023/22-Sand_Slabs/example | 7 | ||||
-rw-r--r-- | 2023/22-Sand_Slabs/first.hs | 109 | ||||
-rw-r--r-- | 2023/22-Sand_Slabs/input | 1280 | ||||
-rw-r--r-- | 2023/22-Sand_Slabs/second.hs | 125 | ||||
-rw-r--r-- | 2023/23-A_Long_Walk/example | 23 | ||||
-rw-r--r-- | 2023/23-A_Long_Walk/first.hs | 148 | ||||
-rw-r--r-- | 2023/23-A_Long_Walk/input | 141 | ||||
-rw-r--r-- | 2023/23-A_Long_Walk/second.hs | 148 |
21 files changed, 3588 insertions, 0 deletions
diff --git a/2023/19-Aplenty/example b/2023/19-Aplenty/example new file mode 100644 index 0000000..e5b5d64 --- /dev/null +++ b/2023/19-Aplenty/example @@ -0,0 +1,17 @@ +px{a<2006:qkq,m>2090:A,rfg} +pv{a>1716:R,A} +lnx{m>1548:A,A} +rfg{s<537:gd,x>2440:R,A} +qs{s>3448:A,lnx} +qkq{x<1416:A,crn} +crn{x>2662:A,R} +in{s<1351:px,qqz} +qqz{s>2770:qs,m<1801:hdj,R} +gd{a>3333:R,R} +hdj{m>838:A,pv} + +{x=787,m=2655,a=1222,s=2876} +{x=1679,m=44,a=2067,s=496} +{x=2036,m=264,a=79,s=2244} +{x=2461,m=1339,a=466,s=291} +{x=2127,m=1623,a=2188,s=1013} diff --git a/2023/19-Aplenty/first.hs b/2023/19-Aplenty/first.hs new file mode 100644 index 0000000..799b6b5 --- /dev/null +++ b/2023/19-Aplenty/first.hs @@ -0,0 +1,117 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 19114 + +data Category = X | M | A | S deriving (Eq, Show) +data Op = Gt | Lt deriving (Eq, Show) +data Action = Accept | Reject | Jmp String deriving (Eq, Show) +data Rule = Cmp Category Op Int Action | RuleAction Action deriving (Eq, Show) +type Workflow = (String, [Rule]) +type Workflows = M.Map String [Rule] +data Part = Part Int Int Int Int deriving (Eq, Show) +type Parts = [Part] +data Input = Input Workflows Parts deriving (Eq, Show) + +type Parser = Parsec Void String + +parseCategory :: Parser Category +parseCategory = char 'x' $> X + <|> char 'm' $> M + <|> char 'a' $> A + <|> char 's' $> S + +parseOp :: Parser Op +parseOp = char '>' $> Gt + <|> char '<' $> Lt + +parseNumber :: Parser Int +parseNumber = read <$> some digitChar + +parseLabel :: Parser String +parseLabel = try $ count' 2 4 letterChar + +parseAction :: Parser Action +parseAction = char 'A' $> Accept + <|> char 'R' $> Reject + <|> (Jmp <$> parseLabel) + +parseRule :: Parser Rule +parseRule = (RuleAction <$> parseAction) + <|> (Cmp <$> parseCategory <*> parseOp <*> parseNumber <* char ':' <*> parseAction) + +parseWorkflow :: Parser Workflow +parseWorkflow = (,) <$> parseLabel <* char '{' + <*> some (parseRule <* optional (char ',')) <* char '}' + +parseWorkflows :: Parser Workflows +parseWorkflows = M.fromList <$> some (parseWorkflow <* eol) + +parsePart :: Parser Part +parsePart = Part <$> (string "{x=" *> parseNumber) + <*> (string ",m=" *> parseNumber) + <*> (string ",a=" *> parseNumber) + <*> (string ",s=" *> parseNumber <* char '}') + +parseParts :: Parser Parts +parseParts = some (parsePart <* eol) + +parseInput' :: Parser Input +parseInput' = Input <$> (parseWorkflows <* eol) + <*> (parseParts <* 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 (Input workflows parts) = sum $ map compute' parts + where + compute' :: Part -> Int + compute' (Part x m a s) = case evaluate entryPoint of + Accept -> x + m + a + s + Reject -> 0 + where + evaluate :: [Rule] -> Action + evaluate (RuleAction (Jmp s):_) = evaluate $ workflows M.! s + evaluate (RuleAction a:_) = a + evaluate (Cmp cat op n r:xs) | matches cat op n x m a s = evaluate [RuleAction r] + | otherwise = evaluate xs + matches X Lt n x _ _ _ = x < n + matches X Gt n x _ _ _ = x > n + matches M Lt n _ m _ _ = m < n + matches M Gt n _ m _ _ = m > n + matches A Lt n _ _ a _ = a < n + matches A Gt n _ _ a _ = a > n + matches S Lt n _ _ _ s = s < n + matches S Gt n _ _ _ s = s > n + entryPoint = workflows M.! "in" + +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/19-Aplenty/input b/2023/19-Aplenty/input new file mode 100644 index 0000000..430a4e2 --- /dev/null +++ b/2023/19-Aplenty/input @@ -0,0 +1,718 @@ +jtx{s<3181:R,R} +rkd{s>2386:tdr,R} +svj{x>1520:A,A} +vkv{x<3627:A,x>3794:A,A} +ksz{m<1450:R,a<2837:R,a<2928:R,A} +fp{x<1293:sjt,bv} +jq{m>1493:R,m>1377:A,m<1344:R,R} +gts{m<3166:R,A} +xxr{s<231:R,x<3055:R,R} +rz{a<2982:A,m<1763:R,x>1878:A,A} +kq{s<2900:R,s>3591:A,R} +tmg{s<1500:A,x>2504:R,a<1166:A,R} +dvn{s<1632:R,A} +znj{m>1884:A,R} +db{m<1554:cg,m>3173:R,x<1203:A,xsm} +chr{a<682:R,x>3120:R,m>2313:A,R} +pd{x<1433:kp,a<2715:fjd,xtx} +qkd{s<666:R,R} +rbf{x>2541:R,R} +gx{s>1347:A,m<812:gxz,s>1079:tpg,lt} +fqb{x<1290:A,R} +jf{x<1340:A,s>2972:dq,x>1378:bqh,jps} +sr{m>776:A,A} +vs{s<1377:R,R} +vx{x>1237:R,A} +dz{m<192:A,m<271:A,R} +mhr{m<2568:R,m<3466:R,a>3791:A,R} +vv{m<3559:A,s>3108:R,R} +psk{a>2830:A,a<2278:A,A} +gvv{a>2993:A,a>2553:A,R} +gsx{x<2656:A,A} +jps{a<1216:A,R} +lt{s<967:A,A} +ng{s<3259:R,s<3674:R,A} +zd{s>2267:R,R} +ks{a>1951:bg,m<1522:gpf,gj} +prk{m<2242:R,s>56:R,R} +nr{x>3432:R,sg} +fkd{s>2014:mxf,sps} +tk{x<1133:jzj,vq} +sgl{a<1237:R,A} +smg{x<2071:R,m<387:R,A} +qd{s<3197:sl,x>1479:lqs,m>1300:rrp,gm} +tr{s<1306:R,x>1183:A,A} +bxh{a>1123:fpp,R} +hjp{a>2545:nb,a>2381:qx,m>2463:nn,bt} +zg{s<1932:smc,m<1443:rq,jf} +nnq{m>3341:lx,s<2737:A,a<3408:A,R} +lx{s>3219:A,a>2886:A,m<3691:A,R} +stl{s<2701:R,m>3442:A,s<3282:A,A} +gsp{m<619:R,s<529:R,A} +fkk{x<3359:svx,sp} +dsk{x<1499:kn,xj} +jmx{m<1426:zq,fvz} +st{s>2257:slt,rvv} +prm{a<470:A,tts} +fkj{x<2514:R,x>2784:R,a>2830:R,qft} +bh{m<1740:mmf,a>503:zn,s>1702:vfp,fft} +rv{m<2642:A,sfv} +qk{s<1846:A,A} +nqr{a>786:ssx,qbh} +kng{a<3059:A,a<3463:A,a<3661:A,A} +tcd{m<3753:R,a<2566:pq,m<3792:R,hsq} +rhc{x>1415:mzt,x>1395:qp,x>1386:rk,nnq} +hn{x>3532:A,a>1227:R,a>1109:A,R} +btd{s<2462:ftz,A} +xv{s>1573:pv,m>730:pn,s<1201:vtz,fjk} +sm{a>787:R,R} +mqz{m<645:R,m<682:A,A} +rvv{m<867:vkv,a>556:R,mx} +fft{x>581:jb,a<314:R,R} +txz{s<1338:R,x>2633:A,m<1168:A,A} +pcq{x<1531:A,R} +kvj{s<2721:A,x>2637:A,R} +kfj{x<1129:kz,s>1501:zfm,pk} +rd{m<3742:A,A} +qft{x<2653:A,s>1281:A,A} +zzr{a<3875:R,m>249:A,a<3917:R,A} +nh{a>3744:zcn,gxg} +fsp{m>3306:R,R} +rt{m<310:zlk,qgj} +mpb{m>2954:R,R} +qgj{s>1083:R,m<502:A,s<949:A,A} +hq{x<1527:dfg,m>3017:jvm,a>947:jts,gqf} +bfc{x>1423:R,a<2789:A,A} +bnv{a>900:R,A} +tdr{a>518:R,m>657:A,x>2576:R,R} +jmm{a<3410:mq,fv} +qjr{a>2534:R,s<1365:A,m<261:A,R} +in{x<1624:zsf,ks} +jgs{m<702:R,A} +qg{a<1733:A,R} +pv{x<1559:hnp,x>1588:gbv,R} +rpx{m<2361:zv,A} +bzm{x<1510:rhc,x<1580:lct,m>3357:rrj,zld} +dnf{x>2931:xkp,s>1747:A,s<858:qhb,zf} +sk{x>3528:A,x<3113:bnx,psk} +xgt{s>2544:vn,sft} +kjv{s>1334:gsh,a>95:rbf,a>50:bmf,trd} +pvt{s>2784:A,s<2303:qk,a<1589:A,R} +nv{a>3108:R,x>1923:R,s>652:A,A} +nlg{m>383:A,s>1520:A,s>749:R,R} +lk{a<2425:R,s>598:R,a>2517:R,A} +nt{m>1682:R,m>999:A,m>428:A,A} +rmp{m>2634:R,s<317:nt,lk} +fs{m<2408:A,x<1842:R,R} +sjt{x<1133:nqr,vt} +tbk{m<2779:R,a>3554:R,a>3415:A,R} +jr{m>3312:A,R} +bmf{s<509:xxs,a<68:qxr,R} +xz{s<1845:A,x<1392:A,A} +tpn{m>2419:A,x>2999:A,s<2347:A,R} +fcg{a<196:A,m>1248:nbt,a>276:R,R} +kv{x>1467:R,m>891:R,s>2429:A,A} +rq{m>570:bft,x<1349:R,m<215:R,A} +cpr{s>140:cdl,m<2079:znj,prk} +fc{a<3507:R,x<1454:A,s<1296:A,A} +kfs{x<2459:R,A} +vr{m<3596:A,a<2837:R,A} +vg{a>3513:xl,x<569:sr,x>740:bp,qxs} +mzc{m<3026:R,a>1169:A,A} +jhk{m<3520:A,m<3692:A,a<701:R,A} +qx{s<1241:A,A} +bv{x<1412:zg,m<1721:hh,hq} +pj{s>3641:A,x>1535:mj,m<1145:A,jxb} +svx{x<3194:A,m<1734:gsp,m<2937:zk,kng} +kp{x<1404:jj,m>1015:R,x>1415:bfc,A} +cxh{m>619:R,m>536:A,R} +ffj{x<2728:R,s<231:A,R} +fh{m<1629:A,a<1260:A,A} +trd{a>29:qc,A} +hj{a<706:kvj,s<3197:grd,a>1057:mzc,gsx} +qcx{a<265:R,R} +bhz{x<1415:R,A} +ccq{a<3195:mtr,a<3700:jzv,x>1501:xv,tj} +qpn{s>499:vpz,a>804:qsc,lsm} +jk{x<3497:R,x>3734:A,A} +bz{x>568:A,a<773:A,R} +hkv{a<1753:R,x<2544:A,a>1849:R,ps} +gj{m>2405:fkd,s>1405:pf,qpn} +lg{a<1611:rlx,a<1731:fps,A} +ln{a<1637:R,s<3175:A,A} +shk{a<1729:htt,m>1833:R,A} +sct{m>1497:A,R} +rnj{a>2878:R,m>1475:R,a<2792:R,A} +qp{a<3308:R,m>3268:vv,A} +vq{s<2622:R,R} +nbt{s<1656:A,m<1413:R,m>1485:A,A} +bdm{x<2476:gv,x>2650:vhv,kh} +bjh{x<2660:R,A} +fnx{a<3874:A,A} +qzt{s>3620:A,A} +ft{a<1286:A,m>1846:R,R} +cx{a>2841:A,m<425:qjr,s>1229:qm,R} +rrj{m<3695:nm,m>3867:sz,a>3080:cd,tcd} +ghj{s<2416:A,m<2698:R,R} +xm{a<3638:pcq,m>2433:pnx,tsc} +hkg{a<1186:A,R} +ts{s>905:A,m<299:R,R} +dbf{m<1691:sct,s<3740:mnr,A} +ssq{s>3183:A,m<2388:A,A} +bd{s>291:jbg,s<217:R,s<250:ffj,vl} +dq{a<1136:R,R} +rpf{s>2706:ll,x<2910:ghj,A} +qxr{s<877:A,A} +lct{s>3272:kx,hcp} +bbc{a<3031:R,x<1554:A,R} +zlk{m>176:R,A} +lh{a<3217:fld,x<504:jr,rgg} +zct{x>2738:sk,x>2209:bdm,gdm} +dj{x>1137:A,a>2578:A,R} +gc{a>2861:R,a<2739:A,A} +lhn{s>2175:jz,m>1213:hcq,lxj} +qm{x<1501:R,s>1724:R,A} +bnx{s>3556:R,x<2924:A,a>2767:A,R} +zr{s<2643:A,ms} +smc{x<1354:R,x>1374:R,s>1279:fh,cxb} +jvm{s>1609:zmn,a<1172:jhk,cxl} +sz{s>3310:A,R} +bxf{a>2995:A,rnj} +qn{x>1577:A,R} +rm{x>3502:sm,x<3166:rzf,R} +zzd{a<2945:A,s<530:A,a<3360:A,A} +ns{x<1515:A,a<2501:A,R} +rnb{s<1360:A,m>2498:R,s<1805:R,A} +srj{x>1408:R,R} +jzv{m>750:ltd,s<1511:rt,tcc} +gps{a>3444:A,x>1039:R,x<989:R,A} +cmr{x<2302:A,R} +mgq{a>3431:A,m<2513:R,R} +zps{m<2495:R,x>1582:A,a>3314:R,A} +xj{s<2468:A,x>1516:A,a>3292:A,A} +hfv{a>2835:phz,x<1072:jc,dj} +vmf{a<2879:qdv,m<1506:xsn,x>2082:rr,xdq} +ndj{m>605:A,a>1367:R,A} +sd{x>1431:A,a<3334:A,s>3667:A,A} +fjt{a<2589:R,A} +slp{x<583:A,A} +jfx{s>639:R,s>549:R,zc} +zrc{m<2490:A,fsp} +sqf{s>3315:A,m<2054:A,R} +hlm{a<3112:R,m>1347:A,R} +bp{s>2210:A,R} +htt{a<1620:R,R} +lhg{x>1534:rb,m>1305:qmz,a>2889:dsk,rs} +cxl{a<1794:R,a<2060:R,m>3613:R,R} +lrt{x>1214:A,m<826:A,x<1148:R,A} +kdt{a>3422:A,a>3354:vx,a<3313:A,ff} +qc{s>566:R,a<43:R,A} +jnn{s>1664:zsx,m<3370:tmg,m<3740:R,lj} +rlx{s>2568:A,s>1841:R,x<2496:A,R} +cxb{x>1364:R,A} +vp{m<625:mt,m>1209:psm,prx} +jbz{x<1581:A,R} +fld{x>580:A,a<2939:vz,qt} +gz{m<2078:A,m>2102:A,m>2086:R,A} +pq{s<3162:R,s<3713:R,R} +nvr{a>3064:R,x>1573:A,a>2695:R,A} +mt{m<212:xgt,m<391:msk,a<1427:dh,nqj} +qq{m<1871:A,x>2374:A,m>2819:R,R} +kx{s>3712:R,a<3138:A,a>3552:A,sb} +zl{a<3279:R,s>3644:R,s<3369:R,A} +zhr{x>1414:mhr,s<1315:R,R} +lr{a<3472:fl,x<1240:qzt,m>1702:A,A} +zn{m>3032:bz,R} +kdb{m>2017:lh,vg} +xdq{a>3298:fs,s>454:nv,R} +jj{x<1385:R,s>2524:A,a<2778:R,R} +hh{s>1624:bqx,m<725:lf,m<1340:hkg,qkd} +tt{x>3601:A,R} +ff{m>2244:A,x>1175:R,s>652:A,A} +nb{m<2342:sx,s<1466:A,gc} +gg{x>2442:R,A} +zf{x>2749:A,R} +ms{a<3730:A,A} +pnx{a>3878:A,R} +thm{a<2994:R,m<2863:R,R} +dcn{x<1937:R,x>2071:A,m<1510:R,R} +zh{x<1391:A,a<2729:A,R} +mzt{m>3358:R,s>2801:thm,x>1477:kzl,A} +vk{x<1245:hfv,a<2636:rmp,ldb} +cdl{x>2787:A,A} +gsh{x>2372:A,s<2731:tgk,ng} +ss{s>1887:A,R} +lsm{a<346:qqd,s<179:pls,a<518:hxk,bd} +kl{m<767:cm,s>2943:hlm,s<2861:R,R} +jc{a>2461:R,R} +lq{x<3091:A,m>3019:R,s<338:R,A} +dc{m>3120:R,s<2936:R,A} +fjx{a<3729:R,m>577:bhz,A} +slh{s<2472:A,x>841:A,x>782:A,R} +jn{a>3008:A,m<154:R,A} +rnt{m<1544:fqb,pt} +lzl{a>2640:kk,s<3306:A,x<1073:R,kft} +rjm{a<2579:R,x<1122:A,x<1178:A,A} +xxn{a>3097:R,x>2616:R,x>2520:A,R} +gmk{a>432:rkd,m<699:mp,np} +gk{a<343:xnh,st} +mtr{m<974:cx,a>2634:lp,a>2480:mb,vvl} +sn{s<1735:R,x>3011:R,A} +hcp{m<2836:A,A} +bzv{m<2882:A,m>3102:A,x>1615:A,R} +gpf{a>786:vp,x>3204:gk,fgh} +bqh{x>1390:A,a<781:A,a<1479:R,A} +zk{s<581:R,a>3168:R,A} +rzf{x>2996:R,A} +pt{m>2840:R,sqf} +dr{a<1633:R,rx} +bj{m<2330:A,R} +rp{a<2416:A,x<1528:A,R} +fv{x<1478:zhr,xm} +zkq{s>2684:zct,jmx} +hg{x>1427:xkb,s>2386:R,s>2348:jgs,R} +ljp{x<3070:qmk,vkc} +qcd{x>2958:kq,m<1982:R,A} +dh{a<1030:A,x<2896:tns,s>1349:hn,A} +nn{a<2330:A,s<1631:A,x>1119:R,A} +tcc{x<1454:xz,s>1712:xb,x>1524:dvn,tb} +prd{m>3593:R,s<3539:A,A} +prx{s<1392:pm,a<1410:bxh,lg} +dnj{s>2561:zr,m>1174:nh,s<2439:hg,fjx} +ltr{s<2819:chr,x>3007:fmv,ndx} +zls{s<2833:R,x>2257:R,R} +tj{a>3851:bfb,gx} +cqn{x>1072:rjm,s<3160:ktb,fjt} +sps{a<845:gts,a>1373:hkv,s>1282:jnn,mcd} +pk{x>1234:A,s>1197:tr,x<1173:cl,R} +lp{a>3002:R,s>1470:R,m<1336:A,ksz} +bnl{a<1615:A,s<1889:R,a<2234:R,R} +px{x>2650:ln,m>3593:A,zls} +bqx{m<671:zvx,m>1076:A,x>1511:R,kv} +tg{x<1547:R,a>3186:A,a<2861:R,A} +bbv{x>1046:A,R} +nl{m>2498:A,s<1270:R,s>1844:R,R} +gxg{a<3560:A,A} +htm{a>1548:R,ft} +jzj{a<3414:R,s>2535:R,a<3803:A,R} +tl{m>591:R,s<2128:R,A} +lj{a>1135:R,A} +qt{x>217:A,a>3101:A,R} +zmn{x>1568:R,m<3662:A,s>2942:R,A} +gqf{a<319:A,lc} +pn{x<1566:fnx,R} +lm{x<748:A,m>1097:slh,mnc} +xb{a>3483:A,R} +hbn{x<2347:rz,s<1021:xxn,bj} +fps{s<2809:R,m>978:R,a<1677:R,A} +tns{m>508:A,R} +ftz{m<1047:A,R} +hsq{s<3306:A,R} +rcf{m<789:R,a>3811:A,R} +zsx{m<3362:A,A} +qnm{m<1707:jq,m>1918:A,klh} +ktb{a>2476:R,a<2324:R,m<1618:R,R} +tts{s<974:A,a>655:R,x>2433:A,A} +nf{a<3288:vk,zpd} +cj{x<1368:dll,m>2179:bzm,s<2729:ntm,qd} +vtz{s>967:zzr,x<1579:R,ts} +zv{a>3078:R,A} +xxs{a>80:R,m<655:R,A} +tsc{a<3864:A,a>3938:R,m>1924:R,R} +bf{x>2895:fkk,vmf} +rk{m>3266:R,m>2870:dc,a<3009:zh,mgq} +nqj{s>1829:R,s>913:vs,mnk} +fd{s<871:A,R} +mj{m>871:A,a>2639:R,a<2371:A,A} +qbm{m>1109:A,s>3601:R,x>1512:R,A} +dpc{m<2093:sgl,R} +vkc{a>3311:ghs,a>2714:bxf,rv} +sx{s>1313:R,A} +gl{x>1498:qbm,m<1020:rg,A} +jbx{a>706:R,x>2598:A,pb} +hxk{a>436:tgn,gs} +tpg{s>1250:R,m>1185:A,s<1173:A,R} +qdv{s<616:mkj,qq} +msk{a<1506:sn,s>2324:A,qg} +xjk{s>2290:R,R} +grd{s<2548:R,A} +xlg{s>3562:A,a>543:A,A} +xnh{x<3580:nr,m>777:fcg,m<313:vpk,vbp} +kh{m<1498:A,A} +zsf{x<948:mf,a<2235:fp,s>2045:cj,zhj} +xsm{s<799:R,x<1241:R,a>872:A,R} +xp{m<1016:R,R} +vpk{x<3813:tv,R} +rr{s<604:R,R} +slt{s<3054:tt,s>3473:A,R} +pxn{m<2918:R,R} +tqg{m>2713:gvv,x<1585:zps,A} +xl{a<3724:R,m<814:A,m<1249:R,R} +lqs{a<3226:pj,x<1533:gl,a>3574:nqz,cnm} +qhb{m>398:R,s>521:A,x<2791:A,R} +pp{a>3287:A,s<2490:R,a<3039:A,A} +klh{a>3097:A,a<2627:A,x>1416:A,R} +kzl{x>1498:A,R} +cd{m>3789:R,s>2774:rd,jjh} +qvj{s>2916:lb,m>1773:gg,A} +nm{m<3503:stl,a>3204:jtx,s<3198:vr,prd} +zfm{a<3405:cf,x>1270:dk,A} +dll{a>2858:kr,x<1210:cq,rnt} +zvx{m<440:A,R} +rs{s>2487:A,m>583:A,m<352:zvt,ns} +gv{x>2386:A,x<2306:A,A} +tsg{x>1593:R,A} +bft{m<1111:R,A} +zld{x<1595:tqg,a<3278:pxn,ds} +nlj{s<37:A,R} +dd{m<360:jn,x<1406:xlx,zl} +xkp{a>723:R,a>685:A,a>649:A,A} +phz{a>3010:R,R} +zvv{m>587:btd,m<276:jbx,x>2637:dnf,smg} +ldb{s>500:R,s<176:A,x>1432:svj,sv} +gm{m<544:dd,sd} +rrp{s>3471:dbf,qnm} +tgk{s>1833:R,m>698:A,a<170:A,A} +tf{a<2989:R,s<2648:R,m<978:A,A} +jv{a>1049:bk,bh} +zjq{x<394:A,s<2172:A,x>409:R,A} +sb{a>3392:A,s<3499:A,s<3590:A,A} +gbv{s>1783:R,m<518:A,R} +mb{a<2566:R,A} +jbg{x<2977:A,R} +cq{m>2591:lzl,cqn} +gpp{s>127:A,R} +qxs{x<630:R,R} +ltd{m<1040:fc,s<1339:R,fzh} +tv{m<191:R,R} +vbp{m>508:A,a<198:hc,m<391:R,qcx} +qhx{s<1393:A,A} +zt{x<829:A,s>2272:A,m>3119:R,A} +xlx{s<3549:R,s<3703:R,a<2825:A,A} +mnc{m>410:R,x<820:R,A} +jts{s>2528:A,a>1459:A,nl} +vfp{a<268:slp,a<349:A,A} +xkb{s>2400:A,a>3661:R,s<2364:A,R} +jxb{x>1512:R,m>1668:R,s<3371:R,A} +jjh{s>2302:A,s<2157:R,R} +dfg{m<3080:bnv,R} +sft{m>85:R,A} +kft{s<3765:R,x<1151:A,A} +ql{m<2989:bnl,A} +hmq{s>328:A,R} +zgl{s<3038:xp,s>3136:R,tg} +jz{x<1535:nz,vcx} +fpp{a<1269:A,s<2540:R,m<877:A,A} +sl{x<1465:kl,zgl} +ghs{s<1180:jk,A} +gdm{s<3410:A,dcn} +mp{a>355:nlg,x>2257:A,R} +tgn{s>384:A,A} +rck{a>3096:A,m<729:R,R} +bfh{s<2430:A,A} +dm{x<3740:A,a<84:A,R} +cl{x>1152:A,a>3659:A,A} +lf{s<590:A,m<384:dz,ndj} +kr{s<3089:tk,x>1116:lr,fq} +ps{x<3131:R,a>1808:R,R} +zc{a<3742:R,s<459:A,A} +hdq{a>1180:A,a<969:A,m<1327:xjk,vxc} +vtn{x>2571:gz,A} +vsp{m<1477:kf,m>1506:A,x<1988:A,R} +pf{m<1916:zj,nsl} +qqb{a<3381:R,a<3544:A,R} +qmk{s>1137:fkj,hbn} +fjk{m<484:qhx,s>1346:mqz,a<3843:qn,cxh} +fzh{a>3465:R,s<1753:A,R} +ll{a<1599:A,m>2800:R,m<2548:R,R} +pm{x<2958:A,A} +ds{s>3322:A,x>1607:bzv,s<2559:A,tbk} +qqd{a>147:xxr,x<2716:hmq,x<3308:R,dm} +zj{x>2856:rm,a>694:qvj,jkr} +ntm{s<2328:lhn,x>1477:lhg,a<3351:pd,dnj} +gs{x>3009:R,m>1822:R,m>1623:A,A} +vpz{a<955:prm,htm} +fl{s<3647:A,R} +vf{m>1405:R,x<364:R,x<439:zjq,A} +sfv{m>3249:R,a<2323:A,a<2508:A,R} +ssx{s<1450:R,R} +xtx{s<2531:bfh,tf} +fvz{s<1875:R,a<2683:tpn,s<2272:kfs,pp} +zpd{s<374:gpp,a<3568:kdt,jfx} +bq{a>2468:A,R} +mx{x>3691:R,A} +zvt{m<232:R,x<1498:R,R} +qbh{a>359:bbv,A} +rx{s<1895:R,x<93:A,R} +pls{s<102:nlj,m>1957:A,x>2610:R,R} +gxz{x<1441:A,a>3782:A,a<3736:A,A} +vcx{x<1581:A,x>1598:R,A} +mnk{x>2686:R,A} +hc{m>386:R,s<1896:R,x>3841:A,R} +jkr{x<2289:R,a<434:bjh,s>2706:xlg,ddr} +lxj{x<1526:A,a<2868:tl,s<2105:A,R} +cs{s>2587:A,s<2454:R,x>1605:A,A} +tb{a<3403:R,x<1483:A,m<408:A,R} +jrk{x<1493:R,A} +np{s<2392:txz,R} +fgh{a<278:kjv,a>610:zvv,gmk} +nsl{a>1286:pvt,m>2128:ltr,m<2048:qcd,vtn} +sp{x<3783:zzd,R} +mnr{a<2963:R,R} +kn{s>2492:R,R} +sg{x>3309:R,A} +kf{x>1948:A,A} +sv{x>1311:A,m>2072:A,R} +ddr{a>588:R,A} +mmf{s>1614:A,a<588:fd,s>637:A,R} +mzd{a>3041:kfj,hjp} +jb{x>749:A,x<663:R,a<217:R,A} +zq{x<2680:rck,zd} +kk{s>3062:A,x<1054:R,x>1150:R,A} +mcd{s>737:R,lq} +km{a<454:ssq,x>1215:A,R} +jp{m>1384:R,a>1361:A,m<1302:R,A} +zcn{m>1641:A,x<1412:R,a<3907:R,R} +hnp{m<624:R,m<1118:R,a>3867:A,A} +vvl{a>2360:jrk,A} +vt{a>1209:zrc,s>2239:km,a>526:db,rnb} +xsn{a<3485:A,x>2424:rcf,x<2143:R,cmr} +fmv{m>2241:A,A} +mq{a<2726:rp,rpx} +qsc{a>1561:shk,s>289:dpc,cpr} +vn{x<2495:A,R} +zhj{s<820:nf,x<1349:mzd,m<1523:ccq,jmm} +rb{x>1585:cs,x<1567:bbc,m>1281:nvr,R} +vl{a<701:A,a<749:R,R} +bk{m>2181:ql,x>534:lm,x>246:vf,dr} +bt{s<1575:R,x>1110:lrt,A} +cg{x<1226:R,R} +pb{s>1976:R,R} +qmz{x>1511:R,hx} +hx{s<2479:A,a>3026:R,x>1492:A,R} +vxc{s<1908:R,R} +psm{x>2500:vmq,m<1395:hdq,vsp} +bg{s>1448:zkq,s<952:bf,ljp} +rg{a<3524:R,R} +mxf{a<1247:hj,m<3013:rpf,px} +cnm{m<854:A,s>3702:A,A} +fjd{m>911:A,s>2513:bq,A} +mkj{x>2290:R,m<1691:A,s>347:A,A} +vhv{s>3440:A,x<2695:R,R} +hcq{a>2835:R,R} +vmq{s>2256:A,s<1332:jp,x<3237:ss,A} +nz{a<3118:A,x<1466:R,s<2259:A,R} +ndx{m>2236:R,x>2459:A,s<3532:R,A} +kz{s<1342:R,R} +lb{s>3471:A,a>1457:A,A} +vz{a>2782:R,A} +cm{a<3264:R,a>3609:R,A} +nqz{s>3591:R,m>1381:jbz,m<596:A,tsg} +dk{x<1297:A,a>3642:R,A} +mf{a<2621:jv,kdb} +lc{x<1574:A,m>2523:R,a<541:A,A} +cf{a<3177:R,R} +rgg{x>754:zt,a<3650:qqb,mpb} +fq{s<3534:R,s<3736:gps,R} +bfb{s>1404:R,s>1128:R,srj} + +{x=61,m=577,a=1750,s=1892} +{x=8,m=603,a=567,s=987} +{x=1398,m=1265,a=702,s=949} +{x=2322,m=693,a=2401,s=946} +{x=348,m=2812,a=613,s=1788} +{x=3353,m=2070,a=1617,s=3088} +{x=24,m=963,a=4,s=1053} +{x=396,m=877,a=3375,s=127} +{x=1490,m=100,a=1060,s=724} +{x=413,m=95,a=944,s=847} +{x=1580,m=960,a=880,s=1400} +{x=1956,m=597,a=3294,s=284} +{x=1924,m=21,a=726,s=1276} +{x=1338,m=1630,a=348,s=114} +{x=11,m=1649,a=475,s=1091} +{x=1660,m=563,a=1047,s=150} +{x=18,m=226,a=33,s=3744} +{x=3145,m=482,a=866,s=629} +{x=474,m=260,a=1408,s=9} +{x=361,m=1348,a=592,s=380} +{x=2632,m=1281,a=234,s=1114} +{x=1871,m=543,a=1285,s=383} +{x=1870,m=364,a=106,s=70} +{x=536,m=528,a=272,s=2050} +{x=1519,m=1564,a=434,s=103} +{x=301,m=2005,a=1069,s=79} +{x=293,m=143,a=3201,s=68} +{x=1308,m=1701,a=271,s=1627} +{x=1538,m=1576,a=249,s=290} +{x=320,m=110,a=1490,s=492} +{x=494,m=904,a=2049,s=1122} +{x=13,m=695,a=1851,s=145} +{x=136,m=1102,a=90,s=879} +{x=1786,m=8,a=663,s=86} +{x=238,m=2582,a=1288,s=3169} +{x=1628,m=1807,a=373,s=116} +{x=86,m=51,a=500,s=1893} +{x=2848,m=36,a=2897,s=1757} +{x=774,m=530,a=970,s=2379} +{x=353,m=1490,a=844,s=2085} +{x=1363,m=938,a=1103,s=1200} +{x=1843,m=6,a=1853,s=882} +{x=1966,m=3149,a=327,s=201} +{x=1116,m=849,a=1822,s=326} +{x=233,m=3172,a=32,s=1141} +{x=3523,m=19,a=38,s=176} +{x=2896,m=511,a=1180,s=2859} +{x=292,m=843,a=98,s=98} +{x=923,m=606,a=2898,s=2343} +{x=46,m=1317,a=78,s=51} +{x=462,m=1255,a=1485,s=737} +{x=1238,m=1292,a=27,s=1525} +{x=2731,m=411,a=1831,s=1574} +{x=202,m=426,a=483,s=349} +{x=33,m=394,a=941,s=1705} +{x=2648,m=510,a=703,s=2332} +{x=1429,m=836,a=316,s=63} +{x=2817,m=1701,a=174,s=160} +{x=261,m=206,a=76,s=2192} +{x=204,m=2989,a=283,s=597} +{x=1068,m=1881,a=3293,s=2503} +{x=31,m=37,a=826,s=2983} +{x=547,m=466,a=1586,s=481} +{x=1419,m=822,a=273,s=1670} +{x=392,m=168,a=452,s=61} +{x=1245,m=2719,a=778,s=2034} +{x=1150,m=1565,a=1098,s=502} +{x=1180,m=30,a=1228,s=223} +{x=727,m=6,a=224,s=144} +{x=1784,m=863,a=741,s=1461} +{x=1200,m=1331,a=113,s=1114} +{x=3108,m=312,a=246,s=1943} +{x=970,m=1845,a=3752,s=940} +{x=2062,m=420,a=290,s=264} +{x=1626,m=1844,a=337,s=321} +{x=1124,m=1302,a=335,s=1250} +{x=205,m=203,a=102,s=292} +{x=228,m=1798,a=562,s=326} +{x=897,m=832,a=1193,s=1826} +{x=336,m=1941,a=1348,s=2270} +{x=162,m=275,a=3043,s=1022} +{x=361,m=268,a=2199,s=1749} +{x=328,m=1482,a=1865,s=1420} +{x=474,m=2434,a=2447,s=1199} +{x=1066,m=3051,a=1482,s=50} +{x=252,m=1317,a=349,s=894} +{x=1241,m=283,a=3431,s=503} +{x=958,m=403,a=928,s=487} +{x=1193,m=830,a=3266,s=2617} +{x=914,m=1239,a=275,s=3325} +{x=2885,m=1206,a=1998,s=313} +{x=831,m=1327,a=447,s=181} +{x=3912,m=2397,a=522,s=1136} +{x=2222,m=375,a=1129,s=595} +{x=3340,m=205,a=1197,s=1910} +{x=2206,m=20,a=1354,s=63} +{x=1068,m=916,a=10,s=1564} +{x=316,m=827,a=371,s=1808} +{x=3287,m=329,a=2730,s=22} +{x=863,m=2792,a=321,s=1546} +{x=1470,m=301,a=795,s=249} +{x=582,m=96,a=2814,s=1126} +{x=387,m=461,a=1526,s=355} +{x=23,m=1590,a=1448,s=269} +{x=1983,m=165,a=714,s=1140} +{x=513,m=1006,a=835,s=1438} +{x=25,m=280,a=1263,s=2950} +{x=823,m=973,a=949,s=166} +{x=720,m=255,a=92,s=184} +{x=867,m=1262,a=153,s=569} +{x=443,m=376,a=4,s=656} +{x=108,m=600,a=958,s=64} +{x=609,m=1212,a=3436,s=1060} +{x=267,m=645,a=2807,s=959} +{x=159,m=2,a=557,s=1673} +{x=2744,m=49,a=49,s=2043} +{x=835,m=33,a=1119,s=440} +{x=2697,m=499,a=386,s=1553} +{x=456,m=110,a=666,s=625} +{x=1274,m=1335,a=336,s=124} +{x=2341,m=1835,a=100,s=2163} +{x=2104,m=1161,a=234,s=1831} +{x=915,m=1660,a=792,s=429} +{x=314,m=384,a=33,s=294} +{x=628,m=579,a=2605,s=1746} +{x=2,m=2227,a=1151,s=38} +{x=294,m=1196,a=1330,s=295} +{x=517,m=2634,a=994,s=267} +{x=272,m=25,a=882,s=217} +{x=599,m=652,a=951,s=126} +{x=255,m=650,a=955,s=102} +{x=25,m=1704,a=2216,s=13} +{x=142,m=817,a=208,s=921} +{x=1932,m=746,a=1646,s=2252} +{x=1157,m=6,a=2213,s=3366} +{x=595,m=10,a=2,s=2750} +{x=696,m=955,a=3215,s=8} +{x=2223,m=3582,a=47,s=1055} +{x=302,m=330,a=420,s=495} +{x=128,m=2241,a=1155,s=387} +{x=225,m=151,a=682,s=916} +{x=844,m=181,a=1842,s=2310} +{x=270,m=837,a=1311,s=2122} +{x=3135,m=829,a=1974,s=164} +{x=1061,m=1019,a=2238,s=571} +{x=2109,m=1065,a=316,s=1054} +{x=1523,m=512,a=42,s=342} +{x=1378,m=2105,a=1968,s=3674} +{x=51,m=94,a=683,s=832} +{x=235,m=1036,a=121,s=741} +{x=18,m=713,a=250,s=484} +{x=193,m=2650,a=569,s=210} +{x=1203,m=2854,a=644,s=515} +{x=3,m=881,a=967,s=1500} +{x=375,m=2028,a=214,s=135} +{x=1693,m=696,a=2186,s=138} +{x=1347,m=655,a=722,s=111} +{x=678,m=995,a=3274,s=183} +{x=1720,m=242,a=1637,s=933} +{x=798,m=1710,a=3735,s=1521} +{x=3046,m=335,a=1055,s=296} +{x=632,m=6,a=207,s=591} +{x=109,m=2344,a=40,s=413} +{x=387,m=121,a=171,s=2554} +{x=1546,m=159,a=2373,s=1578} +{x=875,m=21,a=377,s=2524} +{x=1641,m=1125,a=694,s=2737} +{x=188,m=310,a=378,s=498} +{x=589,m=174,a=2495,s=2769} +{x=2918,m=258,a=643,s=47} +{x=833,m=214,a=333,s=24} +{x=1982,m=200,a=569,s=1014} +{x=341,m=196,a=1404,s=286} +{x=1009,m=248,a=281,s=1903} +{x=547,m=2531,a=215,s=117} +{x=904,m=249,a=46,s=109} +{x=186,m=1706,a=1307,s=732} +{x=1182,m=1615,a=299,s=1275} +{x=2136,m=1349,a=1907,s=523} +{x=13,m=1375,a=1617,s=1599} +{x=786,m=131,a=541,s=67} +{x=12,m=223,a=1565,s=129} +{x=837,m=261,a=22,s=363} +{x=1011,m=249,a=146,s=251} +{x=711,m=230,a=3042,s=246} +{x=2794,m=1052,a=243,s=457} +{x=2289,m=1093,a=2061,s=1219} +{x=2223,m=176,a=1227,s=444} +{x=1744,m=37,a=1590,s=87} +{x=2590,m=2444,a=894,s=1864} +{x=13,m=1356,a=648,s=121} +{x=117,m=125,a=1222,s=669} +{x=1048,m=419,a=1031,s=210} +{x=397,m=2126,a=412,s=977} +{x=1256,m=875,a=3898,s=3195} +{x=3273,m=322,a=702,s=4} +{x=956,m=500,a=522,s=596} +{x=339,m=1107,a=2588,s=970} +{x=493,m=43,a=1683,s=1244} +{x=303,m=484,a=425,s=207} diff --git a/2023/19-Aplenty/second.hs b/2023/19-Aplenty/second.hs new file mode 100644 index 0000000..c59f079 --- /dev/null +++ b/2023/19-Aplenty/second.hs @@ -0,0 +1,130 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 167409079868000 + +data Category = X | M | A | S deriving (Eq, Show) +data Op = Gt | Lt deriving (Eq, Show) +data Action = Accept | Reject | Jmp String deriving (Eq, Show) +data Rule = Cmp Category Op Int Action | RuleAction Action deriving (Eq, Show) +type Workflow = (String, [Rule]) +type Workflows = M.Map String [Rule] +data Part = Part Int Int Int Int deriving (Eq, Show) +type Parts = [Part] +data Input = Input Workflows Parts deriving (Eq, Show) + +type Parser = Parsec Void String + +parseCategory :: Parser Category +parseCategory = char 'x' $> X + <|> char 'm' $> M + <|> char 'a' $> A + <|> char 's' $> S + +parseOp :: Parser Op +parseOp = char '>' $> Gt + <|> char '<' $> Lt + +parseNumber :: Parser Int +parseNumber = read <$> some digitChar + +parseLabel :: Parser String +parseLabel = try $ count' 2 4 letterChar + +parseAction :: Parser Action +parseAction = char 'A' $> Accept + <|> char 'R' $> Reject + <|> (Jmp <$> parseLabel) + +parseRule :: Parser Rule +parseRule = (RuleAction <$> parseAction) + <|> (Cmp <$> parseCategory <*> parseOp <*> parseNumber <* char ':' <*> parseAction) + +parseWorkflow :: Parser Workflow +parseWorkflow = (,) <$> parseLabel <* char '{' + <*> some (parseRule <* optional (char ',')) <* char '}' + +parseWorkflows :: Parser Workflows +parseWorkflows = M.fromList <$> some (parseWorkflow <* eol) + +parsePart :: Parser Part +parsePart = Part <$> (string "{x=" *> parseNumber) + <*> (string ",m=" *> parseNumber) + <*> (string ",a=" *> parseNumber) + <*> (string ",s=" *> parseNumber <* char '}') + +parseParts :: Parser Parts +parseParts = some (parsePart <* eol) + +parseInput' :: Parser Input +parseInput' = Input <$> (parseWorkflows <* eol) + <*> (parseParts <* 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' + +type Interval = (Int, Int) +data Combination = Combination Interval Interval Interval Interval deriving (Eq, Show) + +compute :: Input -> Int +compute (Input workflows _) = compute' (Combination (1, 4000) (1, 4000) (1, 4000) (1, 4000)) [RuleAction (Jmp "in")] + where + compute' :: Combination -> [Rule] -> Int + compute' comb (RuleAction Accept:_) = score comb + compute' comb (RuleAction Reject:_) = 0 + compute' comb (RuleAction (Jmp s):_) = compute' comb (workflows M.! s) + compute' comb@(Combination (xl, xr) m a s) (Cmp X Lt n act:xs) | xr < n = compute' comb [(RuleAction act)] + | xl >= n = compute' comb xs + | otherwise = compute' (Combination (xl, n - 1) m a s) [(RuleAction act)] + compute' (Combination (n, xr) m a s) xs + compute' comb@(Combination x (ml, mr) a s) (Cmp M Lt n act:xs) | mr < n = compute' comb [(RuleAction act)] + | ml >= n = compute' comb xs + | otherwise = compute' (Combination x (ml, n - 1) a s) [(RuleAction act)] + compute' (Combination x (n, mr) a s) xs + compute' comb@(Combination x m (al, ar) s) (Cmp A Lt n act:xs) | ar < n = compute' comb [(RuleAction act)] + | al >= n = compute' comb xs + | otherwise = compute' (Combination x m (al, n - 1) s) [(RuleAction act)] + compute' (Combination x m (n, ar) s) xs + compute' comb@(Combination x m a (sl, sr)) (Cmp S Lt n act:xs) | sr < n = compute' comb [(RuleAction act)] + | sl >= n = compute' comb xs + | otherwise = compute' (Combination x m a (sl, n - 1)) [(RuleAction act)] + compute' (Combination x m a (n, sr)) xs + compute' comb@(Combination (xl, xr) m a s) (Cmp X Gt n act:xs) | xl > n = compute' comb [(RuleAction act)] + | xr <= n = compute' comb xs + | otherwise = compute' (Combination (xl, n) m a s) xs + compute' (Combination (n + 1, xr) m a s) [(RuleAction act)] + compute' comb@(Combination x (ml, mr) a s) (Cmp M Gt n act:xs) | ml > n = compute' comb [(RuleAction act)] + | mr <= n = compute' comb xs + | otherwise = compute' (Combination x (ml, n) a s) xs + compute' (Combination x (n + 1, mr) a s) [(RuleAction act)] + compute' comb@(Combination x m (al, ar) s) (Cmp A Gt n act:xs) | al > n = compute' comb [(RuleAction act)] + | ar <= n = compute' comb xs + | otherwise = compute' (Combination x m (al, n) s) xs + compute' (Combination x m (n + 1, ar) s) [(RuleAction act)] + compute' comb@(Combination x m a (sl, sr)) (Cmp S Gt n act:xs) | sl > n = compute' comb [(RuleAction act)] + | sr <= n = compute' comb xs + | otherwise = compute' (Combination x m a (sl, n)) xs + compute' (Combination x m a (n + 1, sr)) [(RuleAction act)] + score (Combination (xl, xr) (ml, mr) (al, ar) (sl, sr)) = (xr - xl + 1) * (mr - ml + 1) * (ar - al + 1) * (sr - sl + 1) + +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/20-Pulse_Propagation/example b/2023/20-Pulse_Propagation/example new file mode 100644 index 0000000..2dc1bab --- /dev/null +++ b/2023/20-Pulse_Propagation/example @@ -0,0 +1,5 @@ +broadcaster -> a, b, c +%a -> b +%b -> c +%c -> inv +&inv -> a diff --git a/2023/20-Pulse_Propagation/example2 b/2023/20-Pulse_Propagation/example2 new file mode 100644 index 0000000..2738ceb --- /dev/null +++ b/2023/20-Pulse_Propagation/example2 @@ -0,0 +1,5 @@ +broadcaster -> a +%a -> inv, con +&inv -> b +%b -> con +&con -> output diff --git a/2023/20-Pulse_Propagation/first.hs b/2023/20-Pulse_Propagation/first.hs new file mode 100644 index 0000000..8704be9 --- /dev/null +++ b/2023/20-Pulse_Propagation/first.hs @@ -0,0 +1,119 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 32000000 +example2ExpectedOutput = 11687500 +data Pulse = Low | High deriving (Eq, Show) +data Module = Normal | FlipFlop Bool | Conjunction (M.Map String Pulse) | Broadcaster deriving (Eq, Show) +data Configuration = Configuration Module String [String] deriving (Eq, Show) +type Conf = (Module, [String]) +type Input = M.Map String Conf + +type Parser = Parsec Void String + +parseModule :: Parser Module +parseModule = char '%' $> FlipFlop False + <|> char '&' $> Conjunction M.empty + <|> lookAhead (string "broadcaster") $> Broadcaster + <|> lookAhead letterChar $> Normal + +parseLabel :: Parser String +parseLabel = some letterChar + +parseConfiguration :: Parser Configuration +parseConfiguration = Configuration <$> parseModule + <*> parseLabel <* string " -> " + <*> some (parseLabel <* optional (string ", ")) + +parseInput' :: Parser Input +parseInput' = M.fromList . map (\(Configuration m s l) -> (s, (m, l))) <$> some (parseConfiguration <* 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 input = let (x, y) = computeX 1000 (0, 0) $ initConjuctions input in x * y + where + computeX :: Int -> (Int, Int) -> Input -> (Int, Int) + computeX 0 n _ = n + computeX i n input = let (n', input') = compute' (1, 0) [("button", Low, "broadcaster")] input + in computeX (i-1) (scoreAdd n n') input' + compute' :: (Int, Int) -> [(String, Pulse, String)] -> Input -> ((Int, Int), Input) + compute' n signals input | length stepAll == 0 = (n, input) + | otherwise = compute' (scoreAdd n $ score stepAll) stepAll alterAll + where + alterAll :: Input + alterAll = L.foldl' alterOne input signals + alterOne :: Input -> (String, Pulse, String) -> Input + alterOne acc (prev, p, me) = alter p prev me acc (M.lookup me input) + alter :: Pulse -> String -> String -> Input -> Maybe Conf -> Input + alter _ _ _ input (Just (Normal, _)) = input + alter High _ _ input (Just (FlipFlop _, _)) = input + alter Low _ me input (Just (FlipFlop False, l)) = M.insert me (FlipFlop True, l) input + alter Low _ me input (Just (FlipFlop True, l)) = M.insert me (FlipFlop False, l) input + alter p prev me input (Just (Conjunction m, l)) = M.insert me (Conjunction $ M.insert prev p m, l) input + alter p _ _ input (Just (Broadcaster, l)) = input + alter _ _ _ input Nothing = input + score :: [(String, Pulse, String)] -> (Int, Int) + score = L.foldl' scoreOne (0, 0) + scoreOne :: (Int, Int) -> (String, Pulse, String) -> (Int, Int) + scoreOne (x, y) (_, Low, _) = (x + 1, y) + scoreOne (x, y) (_, High, _) = (x, y + 1) + stepAll :: [(String, Pulse, String)] + stepAll = L.foldl' stepOne [] signals + stepOne :: [(String, Pulse, String)] -> (String, Pulse, String) -> [(String, Pulse, String)] + stepOne acc (prev, p, s) = step p prev s acc (M.lookup s input) + step :: Pulse -> String -> String -> [(String, Pulse, String)] -> Maybe Conf -> [(String, Pulse, String)] + step _ _ _ acc (Just (Normal, _)) = acc + step High _ _ acc (Just (FlipFlop _, _)) = acc + step Low _ me acc (Just (FlipFlop False, l)) = acc ++ map (set me High) l + step Low _ me acc (Just (FlipFlop True, l)) = acc ++ map (set me Low) l + step p prev me acc (Just (Conjunction m, l)) = let p2 = if length (M.filter (\x -> x == High) $ M.insert prev p m) == length m then Low else High + in acc ++ map (set me p2) l + step p _ me acc (Just (Broadcaster, l)) = acc ++ map (set me p) l + step _ _ _ acc Nothing = acc + initConjuctions :: Input -> Input + initConjuctions input = let r = M.foldrWithKey initConf input input in r + initConf :: String -> Conf -> Input -> Input + initConf c (_, l) input = L.foldl' initOne input l + where + initOne :: Input -> String -> Input + initOne input s = case M.lookup s input of + Just (Conjunction m, l) -> M.insert s (Conjunction (M.insert c Low m), l) input + _ -> input + scoreAdd (x, y) (x', y') = (x + x', y + y') + set :: String -> Pulse -> String -> (String, Pulse, String) + set me p s = (me, p, s) + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + example2 <- parseInput "example2" + let example2Output = compute example2 + when (example2Output /= example2ExpectedOutput) (error $ "example2 failed: got " ++ show example2Output ++ " instead of " ++ show example2ExpectedOutput) + input <- parseInput "input" + print $ compute input diff --git a/2023/20-Pulse_Propagation/input b/2023/20-Pulse_Propagation/input new file mode 100644 index 0000000..32d7954 --- /dev/null +++ b/2023/20-Pulse_Propagation/input @@ -0,0 +1,58 @@ +%bz -> rb, mf +%tn -> kb, md +broadcaster -> nr, tn, bx, nx +%jp -> ps +&kc -> rx +%dh -> kb, lt +%lt -> cq, kb +%ps -> mf, fh +%sr -> nh, jh +%jg -> tv +%bx -> fd, jg +%kg -> fd, lg +%fh -> dp +%hv -> mf, bz +%mj -> zv +%rz -> gq, mf +%tc -> td +%bl -> fd +%lg -> fd, qj +%gq -> hc, mf +%kh -> ck +%td -> kb, bm +%cq -> kx, kb +%zv -> tk +&nh -> kh, zv, tk, mj, nx, qm, ph +%tk -> mc +%nr -> jp, mf +%bt -> rz +%dj -> nh, qm +%qt -> gb, fd +%rb -> mf +&ph -> kc +%dp -> bt, mf +&kb -> hn, md, tc, tn, mr +%gb -> fd, qs +&vn -> kc +%rt -> kg, fd +%ck -> nh, sr +%qx -> rt, fd +%jh -> pt, nh +%mr -> rs +%nx -> nh, dj +%qm -> mj +&fd -> bx, kt, jg +%rs -> kb, dh +%bm -> kb, mr +%tv -> qx, fd +%pt -> nh +%qj -> qt, fd +%kx -> kb +%qs -> bl, fd +%md -> hh +%hh -> tc, kb +%mc -> kh, nh +%hc -> hv +&kt -> kc +&mf -> fh, vn, bt, hc, nr, jp +&hn -> kc diff --git a/2023/20-Pulse_Propagation/second.hs b/2023/20-Pulse_Propagation/second.hs new file mode 100644 index 0000000..5eaf39e --- /dev/null +++ b/2023/20-Pulse_Propagation/second.hs @@ -0,0 +1,119 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +data Pulse = Low | High deriving (Eq, Show) +data Module = Normal | FlipFlop Bool | Conjunction (M.Map String Pulse) | Broadcaster deriving (Eq, Show) +data Configuration = Configuration Module String [String] deriving (Eq, Show) +type Conf = (Module, [String]) +type Input = M.Map String Conf + +type Parser = Parsec Void String + +parseModule :: Parser Module +parseModule = char '%' $> FlipFlop False + <|> char '&' $> Conjunction M.empty + <|> lookAhead (string "broadcaster") $> Broadcaster + <|> lookAhead letterChar $> Normal + +parseLabel :: Parser String +parseLabel = some letterChar + +parseConfiguration :: Parser Configuration +parseConfiguration = Configuration <$> parseModule + <*> parseLabel <* string " -> " + <*> some (parseLabel <* optional (string ", ")) + +parseInput' :: Parser Input +parseInput' = M.fromList . map (\(Configuration m s l) -> (s, (m, l))) <$> some (parseConfiguration <* 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 input = L.foldl' lcm 1 $ computeX 0 (take (length targets) $ repeat Nothing) $ initConjuctions input + where + computeX :: Int -> [Maybe Int] -> Input -> [Int] + computeX i acc input | all isJust acc = fromJust <$> acc + | otherwise = let (acc', input') = compute' [("button", Low, "broadcaster")] i acc input + in computeX (i+1) acc' input' + compute' :: [(String, Pulse, String)] -> Int -> [Maybe Int] -> Input -> ([Maybe Int], Input) + compute' signals i acc input | length stepAll == 0 = (acc, input) + | otherwise = let acc' = map (accStep i stepAll) $ L.zip targets acc + in compute' stepAll i acc' alterAll + where + alterAll :: Input + alterAll = L.foldl' alterOne input signals + alterOne :: Input -> (String, Pulse, String) -> Input + alterOne acc (prev, p, me) = alter p prev me acc (M.lookup me input) + alter :: Pulse -> String -> String -> Input -> Maybe Conf -> Input + alter _ _ _ input (Just (Normal, _)) = input + alter High _ _ input (Just (FlipFlop _, _)) = input + alter Low _ me input (Just (FlipFlop False, l)) = M.insert me (FlipFlop True, l) input + alter Low _ me input (Just (FlipFlop True, l)) = M.insert me (FlipFlop False, l) input + alter p prev me input (Just (Conjunction m, l)) = M.insert me (Conjunction $ M.insert prev p m, l) input + alter p _ _ input (Just (Broadcaster, l)) = input + alter _ _ _ input Nothing = input + stepAll :: [(String, Pulse, String)] + stepAll = L.foldl' stepOne [] signals + stepOne :: [(String, Pulse, String)] -> (String, Pulse, String) -> [(String, Pulse, String)] + stepOne acc (prev, p, s) = step p prev s acc (M.lookup s input) + step :: Pulse -> String -> String -> [(String, Pulse, String)] -> Maybe Conf -> [(String, Pulse, String)] + step _ _ _ acc (Just (Normal, _)) = acc + step High _ _ acc (Just (FlipFlop _, _)) = acc + step Low _ me acc (Just (FlipFlop False, l)) = acc ++ map (set me High) l + step Low _ me acc (Just (FlipFlop True, l)) = acc ++ map (set me Low) l + step p prev me acc (Just (Conjunction m, l)) = let p2 = if length (M.filter (\x -> x == High) $ M.insert prev p m) == length m then Low else High + in acc ++ map (set me p2) l + step p _ me acc (Just (Broadcaster, l)) = acc ++ map (set me p) l + step _ _ _ acc Nothing = acc + initConjuctions :: Input -> Input + initConjuctions input = let r = M.foldrWithKey initConf input input in r + initConf :: String -> Conf -> Input -> Input + initConf c (_, l) input = L.foldl' initOne input l + where + initOne :: Input -> String -> Input + initOne input s = case M.lookup s input of + Just (Conjunction m, l) -> M.insert s (Conjunction (M.insert c Low m), l) input + _ -> input + set :: String -> Pulse -> String -> (String, Pulse, String) + set me p s = (me, p, s) + targets = pointsTo toRx + [toRx] = pointsTo "rx" + pointsTo :: String -> [String] + pointsTo name = L.foldl' (\acc (k, (_, l)) -> if isJust (L.elemIndex name l) then k:acc else acc) [] $ M.assocs input + accStep :: Int -> [(String, Pulse, String)] -> (String, Maybe Int) -> Maybe Int + accStep _ _ (_, Just x) = Just x + accStep i stepAll (t, Nothing) | triggered = Just (i + 1) + | otherwise = Nothing + where + triggered = L.foldl' (trigg t) False stepAll + trigg _ True _ = True + trigg t False (_, Low, u) = t == u + trigg _ _ _ = False + +main :: IO () +main = do + input <- parseInput "input" + print $ compute input diff --git a/2023/21-Step_Counter/example b/2023/21-Step_Counter/example new file mode 100644 index 0000000..9e1d842 --- /dev/null +++ b/2023/21-Step_Counter/example @@ -0,0 +1,11 @@ +........... +.....###.#. +.###.##..#. +..#.#...#.. +....#.#.... +.##..S####. +.##..#...#. +.......##.. +.##.#.####. +.##..##.##. +........... diff --git a/2023/21-Step_Counter/first.hs b/2023/21-Step_Counter/first.hs new file mode 100644 index 0000000..ff7404f --- /dev/null +++ b/2023/21-Step_Counter/first.hs @@ -0,0 +1,85 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 16 + +data Tile = Start | Plot | Rock deriving Eq +instance Show Tile where + show Start = "S" + show Plot = "." + show Rock = "#" +type Line = V.Vector Tile +type Input = V.Vector Line + +type Parser = Parsec Void String + +parseTile :: Parser Tile +parseTile = char 'S' $> Start + <|> char '.' $> Plot + <|> char '#' $> Rock + +parseLine :: Parser Line +parseLine = do + line <- some parseTile <* eol + return $ V.generate (length line) (line !!) + +parseInput' :: Parser Input +parseInput' = do + line <- some parseLine <* eof + return $ V.generate (length line) (line !!) + +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' + +type Steps = M.Map (Int, Int) () + +compute :: Input -> Int -> Int +compute input s = M.size $ compute' s start + where + compute' :: Int -> Steps -> Steps + compute' 0 steps = steps + compute' i steps = compute' (i-1) next + where + next :: Steps + next = M.foldrWithKey nextSteps M.empty steps + nextSteps :: (Int, Int) -> () -> Steps -> Steps + nextSteps (x, y) _ = nextOne (x-1, y) . nextOne (x+1, y) . nextOne (x, y-1) . nextOne (x, y+1) + nextOne :: (Int, Int) -> Steps -> Steps + nextOne (x, y) acc = case input V.!? y of + Just line -> case line V.!? x of + Just Rock -> acc + Just _ -> M.insert (x, y) () acc + _ -> acc + Nothing -> acc + start = M.singleton (mid, mid) () + mid = V.length input `div` 2 + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example 6 + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input 64 diff --git a/2023/21-Step_Counter/input b/2023/21-Step_Counter/input new file mode 100644 index 0000000..9a2f251 --- /dev/null +++ b/2023/21-Step_Counter/input @@ -0,0 +1,131 @@ +................................................................................................................................... +..............#............#..#......#.##.....#..##..##.#...............#.........#......#....#..#.......#............#.#.......... +.......##.......#..#..................#.......#...#..##.##.................##......#.......#..#.....##........##..#.....#......###. +.......#...#..#...........#............#..#..........#.#..#................#.....#......#.................###.....#.#....#......... +...........#......#....#...#...#........#.............#....................#......#...............#..#..........#..............#... +...#.#..#.#............................#.....##........#........#..................#.#....##.............#.##...#......###......... +..#......#.........#...........#....#.....#..........#.................................#.................#............#..#......##. +.##...#...#....#................#.#.#.....#..................................................#...#.....#...#..#...............##... +.......#.............#.#..#........#.#...........#.#............#..#...........##.#....##...........#.........#..#.....#........... +......#......#...............#........#.....#...##.#...........................#....#..#.#......#....#.....#...#....#.........#.... +..................##.#.......#.....#.......#......#...........#.#...............#.....#.##..#....#....#..............#.#..#...#.... +...........#..........#......................#.............#...##......##...............#.......##.......#.......#..#....#......... +.....#..................#............#...#.......#...........#.......#................#..#...#....#.......##...#.....#........#.... +...#...........#..............##...##.....#.#..#...............#....................#.......#..#..#.....#..#...#.............#..#.. +.#......#.......................#......#.#..#.#...............#...............................#.#..#......#..........#....#....#... +..........#........#.........##.#...#.....................#.......#...#...............#...#..#......#..#.#........#...#...#........ +.##.....#..#...............#............................#.............#..................#.....#...#.#....#......#.....#........... +....#...#..#.##.#........#..#.............................#..............#....#............#.....#.....#.#...#...#.......#....#.#.. +......#.......#..#........#...........##............#.....##...##.............#........#....................#......#.......#....... +.#......#............#...#..#..#..##..................#...#...............#...............#.............#..#..#.##..#......#..#.... +............#.............#...#.......#..........#....#..##....#...#...#.#.....#..............#...#....##.......................... +...##...#.......#........#.#...#....#...#................................#.....#.#........#.......#.....#.......................... +.#......#.......#...##.#..##.......#.......................#.#.....#.......................#.....#.......#.........#..........#.#.. +.........#...........#...........................#.........##.......#......##..#............#..#.........#.......#....#............ +......................#....##..................#.......#..........#..#...#.##.#.....................#.#...#....#.......#.......##.. +..##.##...........#....#...#...#..#.#........##.....#.........#...#......#.#........#.............................#...#............ +...........###...#..##.....#..................................#....##........#.#....#..............#...#..##.....#.....#......#..#. +....#....##.#........#.........##...............#............#....#..........#.....................#................#.#............ +.#..##.#....#...............##.#.............#..#..............#......###.....#.#......................#.....##.........##.......#. +...#............#.......#..#...#...........#........#....#......#..............#.....................#..#.......................... +.#...................#........#.........#.#.................#............#............#.#..................#...#....#....#......... +.......#..#........#..........#..........#.#.....#..##.........#..............#......#........................##.....#.#........... +............#.............................###........#.........#...#......#...#.#.....#...............#....##...#....##..##....#... +....#...#.##.......#.#..............##..................###..##......#........#.....#.#...................#...#......#........#..#. +..............##...#....##................###....###.#...#........#.....#..................#..............#...#.....#...#.......... +..##......#.##......##....#........#...#..#...#............#...#....#..#.............#........#..................#........#........ +..#....................#.#........#....#.....................#............#......#...#.....##.............#..........#..........#.. +.........#...##..#........................#.##.....#...............#..##...#.....#..#............................#...#..##.#.....#. +.......................#........#.#.........#..#.......##..........................#..#.....#..................##.................. +...............#...............#...#.........##......#.........#..#......#..#.........#....#...................#..#.#...###........ +..#.#...#..#......##.......................#...#......#..............#......................#..#...............##.................. +...........#.................#.....#..........##.........#..........#.....#............#....#.........................#.....#...... +.........#..##....#..............#...#..........#......#..#.#.#..........#..#....#............##..#............#........#.#....#... +.....#.#..###....#.........#...#.....#........#..#.....##...#......#.................##...............#................#.....#..... +.......#....#..............#.#...#........#.....#...............#..#..#................#.........#...................##.....#...... +......#...#.................#.#...........#.#.................................#.#.##.......#......#...#..#...................#.##.. +..#...........#........#...#...#.....#...#.......#........##...#.......#...................................#..........#............ +......#..#..#..........#..#...#......#..............#..#....#.....#.#....#........#.###.......#..#.#.....................#...#..... +..#..................#..#........#...#..........#..#.#....#...........#.#...#...#..#..#.#........#..#.......##...................#. +..#......##.............#.........#......#.##...##.#.#...#...........#.........#.##...#..#.....#...#....#.......................... +................................##............#..#.............#...........#........#.##.......#.#...#..#...#.#........#.......#... +..........................#.........................#..........#....#.....#......#.#.......#.#..#.....#.....#..#.................#. +...#.............#...#...#...#...#.....#.........#.................#...##.....#......................#.....#.#.#.........##....#... +.....#...........#.##.#...#...#.#.#....#......#...#..#..#...#...#.#.#.#.##.......#.........#..........#...................#....##.. +......#..................##..##.#.......#..............#.#...............#.#...#...##.......#.......#.....#....#...............#... +...#.........................#........##........#....#...#.....#....................#......#..#...........#.#.##..............#.... +.............#........#....####..##..........#.#..............#...#............#.............##...####..........##...........##.... +................#.....##..........#........#..##.#................#.......#.##....#.......#..#...##......##........................ +.#.........#...#.......#.#.#....#.....#..................##.#.......#......#......#....#.......#...#.....#...#.....#...#.......#... +..........#...#..............#....#..#..#...............##.....#.......#...............#................#.#.#.#.........#.......... +..............#.#...........#.......#............#..#..#.#..............#....#..##.#.#........#...#................#...#.#......... +.................................#............#...#................#...#......#.#...#..#............#............#................. +..............##....#........#............#.#...#.#....#...##..##........#.#.#....................#.#..........#.#....#....#....... +..........#.......#...#...#...#.#..#..#......#.......#..........#.........#..#.....................#........#....#..#.....#........ +.....#....#........................#...#.#..#.....#...#.#.........#..........#.....#..#..#..###..#..............#.................. +.................................................................S................................................................. +...............#................#.........#....#.#...........##.....#........................#.......#..#.#.....###..##.#.......... +..........#....#........#...#..#.......#.#.........#.........#..#.....###......#.........#...#........#....#...#....##............. +.......##..............#........##.........#........#..#.#......#..........#........#....#............##.#........#....#..#........ +.........##...........#....#.#.....#.........#.#....#.....##..#.....#.......#..#.#..................#.#......#..................... +..........##....##....#......##.......#...........#............#.......###.......##..#.#.#..#....#...#.........#.###.#.#........... +.................#.#..........#...#...#........#........#..###..............#....#............#.........#.......#.#....##.......... +.##...............................#..#.#.......#...#....#...#............#......#........#....#.#....#..#.......#..#............... +................#..................#.......###..#..........#.#.................#..##......##.#........#......####.................. +.....#...............................#..#.#.#....#.#............#....#....................##....#..............................#... +..#............#.#...#...........#.........#......#.................##.#...#.......................##..#........................... +................#......#....#...##..#........##..#.##..#.......#........#..........#................#.............................. +.................................#..###..........#.....##............##.....##.......#.#.#....#..#.............#..#............#... +..#...#..............#............###...........#.#.#.#..#....#.#..#...#.....#..........................#....#...........#.#..#..#. +.#.###...#........#..............#.#........#.......#.......#.........#.....#...#..###...##..##..#....#.#......#.........#......#.. +..........#.........#.......#..##.#.....#.##..#.........#..#...#.....#.#.##....#.........#.#.....#......#..............#...#....... +..#..#..#...#.........#..##...#..#...#......#.............#.#.........#.#...##.....#.....#...#..#.....#..##...........#........#... +..#....#....#................###...#......#.....#..#....#..........#.........#.#..#.................#.#..#............#.....##..#.. +....#.......##........##...#..##........#........#..##............#.........#..##...#.....#..#...#.......#.............#........#.. +.#...#...##.............#........##...#.....#.##....#...#.....#..........##..............#................................##.#.#... +.....#.......##.........#.....#.....#..#.###..#......#......##..............#................#..##..................##......###..#. +.##...####.......#..........#.........#...#........................##....#......#.......#........#.....#.........#..........#.#.... +..................#...........#..#.....#..#........#...................#............#..........#..#.#...........#.#....#....#...... +........#..#....................................#..................#.#................#..#....#.#.......................#....#..... +.#..............##..............##.##....##..##...#...##......##......#......#..........#....#..................................#.. +.#....#.....#....##..............#.##..##...#.......#.##.......##..#.............#.#.....#...#......#............#..........##..... +..................##............#...##.................#...#.##...#.........#....#....#....#..#.....#........#..........#...#.#..#. +.##.......#........#.#.........#......................#.#..#.#........#.....................#.#.............###........#.#......... +.#..........#....#.....#...........#....#..........###................#.#.#...#.##......#...................#....#.....#.......#... +...#....#..#..#.......#.#..............#........#........###.#.....#....#...#.....##.......................#....#...........#....#. +..#.................................#.....###......#......##...#...#.......#............##.....#........#.#........................ +.#...........#....#......#.......................#........##........#.........#.....#.....#....#............###..#...#.#....#...... +.......#.#......#.#....................#.##................#.#...........#...........#.#...##........................#............. +....#......#....#.......#.....................#.#..#........#..........#..#..#.......#.#..............#......#..............#...... +.....#......#.......#....................#.......#..#...####.##....#...#.#.......##...#.#...........#..............#..........#.... +..#.........#........##....#.............##.#.#.........#....##........#..#........................#...#.#..#....#................. +.#....#..#.##.......#..#..#...##............##.##..#..#......#.##.......#.................#......................##.....#........#. +..................#.........#............#...##......................#...............#...........#................#.....#....#.#... +..#......##............#.......#.#................#.....#..........................#..#...................#....#....#.........#.... +.#.#........#....#..##..#.....#.#...............#.......##..#.........#.....#........#...............##............................ +..#.........##...................#.#........##......#.#.......##......##.#..#....#.#.#...........#..##...................#.......#. +....#.#.##.....###..#..........#....#..............#.###....#......##.............##...........#........#...........#...........##. +.#...##..#......##....#........##.#..............#.......##..#.....#....##.....................#...##..#............#..........#... +....#...#..........#...........#.#.#..............##.#.#.....###..................#.............#....#.....####.................... +........#..#.........###........................#.#..#..........#.............................#...#......#.............##.......... +.....#...#.............#.....#....#...#..............##.##........#..#...##.....#...............#..............#....#...#....#..... +....#.#...........#...#.##.....##....#.#...........##....#.....#...............................#.#.#...#.....#..#........#......... +...##...........................##..##.................##....#........#.....#...........#....#.....#............##.......#......... +............#.....#.....#......##...........................................#.........#.....#......#............#........#.#.#..... +......##...#....#...#...#.......#...........................#..#...#.#................#..........#...#.##..........#....##.#....... +.....#...#.#..###.#.#.........#.#..........#...........#.....#.............................#..#.#....#.#.....#.....#..#......#..... +.#.....#...#....................#...............................#.....#.............#.##.....####..##.....#.###....#..#............ +....#...#.............#.#....#.....#..#..#...#.............#.......................#.#........#..#...#.................#...#.#...#. +..........#..#...#.....#..........#...#....#.#.....................#............................#....#.#......#.#.............#.... +..##.....#...#......#.#....#....#.##.#....#......#........##........#...........#..#........#......#.#.....................#.#..... +......#...####.......#......#..##..###.......#...............#........#.........#....#.#.............##........##..#.#......#...... +....##.##..........#.#.#.#.#..#.....##......................#.....#.#......................#....#.................#...........#.... +.......#..##.#.#..##...#...........................#............................#....##.......#........#......#..........#.#....... +.....#.##.......#................#...#........#...#.............................#..#........#......###.###....#...##.............#. +.......#............##..........##..#.#.....#...................#................................#..#...#...#........#....#......#. +.#.#.#.#..#...#...........#.#.....#...................#.#......................#......##.....#..................#...##..#.#........ +............#...............#...#........##....#..#...........................#.#..#.....#.##.................#...#....#......#.... +.....#.......#.............................#......#..#.#..#.....................#...........#...#........#.#........#....#......... +.#.##..#............#..#.................................................#...#..###................##........##.#..#......#......#. +.........#...............##......#............#.....#...........................#.............##.#.#.#.......###.....#..........#.. +................................................................................................................................... diff --git a/2023/21-Step_Counter/second.hs b/2023/21-Step_Counter/second.hs new file mode 100644 index 0000000..eb91370 --- /dev/null +++ b/2023/21-Step_Counter/second.hs @@ -0,0 +1,92 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +data Tile = Start | Plot | Rock deriving Eq +instance Show Tile where + show Start = "S" + show Plot = "." + show Rock = "#" +type Line = V.Vector Tile +type Input = V.Vector Line + +type Parser = Parsec Void String + +parseTile :: Parser Tile +parseTile = char 'S' $> Start + <|> char '.' $> Plot + <|> char '#' $> Rock + +parseLine :: Parser Line +parseLine = do + line <- some parseTile <* eol + return $ V.generate (length line) (line !!) + +parseInput' :: Parser Input +parseInput' = do + line <- some parseLine <* eof + return $ V.generate (length line) (line !!) + +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' + +type Steps = M.Map (Int, Int) () + +-- 26501365 = 202300 * 131 + 65 +compute :: Input -> Integer +compute input = let steps = compute' 65 start + steps' = compute' 131 steps + steps'' = compute' 131 steps' + steps''' = compute' 131 steps'' + -- lagrange polynomial interpolation for the quadratic function + f :: Integer -> Integer + f x = let lamb xi = product (map (\xj -> (x-xj)) (L.delete xi xs)) `div` product (map (\xj -> (xi-xj)) (L.delete xi xs)) + in sum $ zipWith (*) ys (map lamb xs) + xs = toInteger <$> [x*131+65|x<-[0..3]] + ys = toInteger . M.size <$> [steps, steps', steps'', steps'''] + in f 26501365 + where + compute' :: Int -> Steps -> Steps + compute' 0 steps = steps + compute' i steps = compute' (i-1) next + where + next :: Steps + next = M.foldrWithKey nextSteps M.empty steps + nextSteps :: (Int, Int) -> () -> Steps -> Steps + nextSteps (x, y) _ = nextOne (x-1, y) . nextOne (x+1, y) . nextOne (x, y-1) . nextOne (x, y+1) + nextOne :: (Int, Int) -> Steps -> Steps + nextOne (x, y) acc = case input V.!? (y `mod` len) of + Just line -> case line V.!? (x `mod` len) of + Just Rock -> acc + Just _ -> M.insert (x, y) () acc + _ -> acc + Nothing -> acc + start = M.singleton (mid, mid) () + mid = len `div` 2 + len = V.length input + +main :: IO () +main = do + input <- parseInput "input" + print $ compute input diff --git a/2023/22-Sand_Slabs/example b/2023/22-Sand_Slabs/example new file mode 100644 index 0000000..43a7fc5 --- /dev/null +++ b/2023/22-Sand_Slabs/example @@ -0,0 +1,7 @@ +1,0,1~1,2,1 +0,0,2~2,0,2 +0,2,3~2,2,3 +0,0,4~0,2,4 +2,0,5~2,2,5 +0,1,6~2,1,6 +1,1,8~1,1,9 diff --git a/2023/22-Sand_Slabs/first.hs b/2023/22-Sand_Slabs/first.hs new file mode 100644 index 0000000..91b4d49 --- /dev/null +++ b/2023/22-Sand_Slabs/first.hs @@ -0,0 +1,109 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 5 + +type Coord = (Int, Int, Int) +data Brick = Brick Coord Coord deriving (Eq, Show) +instance Ord Brick where + (Brick (_, _, z1) (_, _, z2)) `compare` (Brick (_, _, c1) (_, _, c2)) = min z1 z2 `compare` min c1 c2 +type Input = [Brick] + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read <$> some digitChar <* optional (char ',') + +parseCoord :: Parser Coord +parseCoord = (,,) <$> parseNumber + <*> parseNumber + <*> parseNumber + +parseBrick :: Parser Brick +parseBrick = Brick <$> parseCoord <* char '~' + <*> parseCoord <* eol + +parseInput' :: Parser Input +parseInput' = some parseBrick <* 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' + +type Height = (Int, Maybe Int) -- (Height, BrickId that achieved that height - 1) +type HeightMap = V.Vector (V.Vector Height) +type SupportMap = M.Map Int [Int] -- BrickId -> [supports brickIds] + +compute :: Input -> Int +compute input = L.length $ L.filter (not . isSupportBrick) [0..(length input - 1)] + where + isSupportBrick :: Int -> Bool + isSupportBrick brickId = L.any isSoleSupport $ M.elems supportMap + where + isSoleSupport :: [Int] -> Bool + isSoleSupport [l] = brickId == l + isSoleSupport _ = False + (_, settledInput, heightMap, supportMap) = L.foldl' settle (0, [], startingHeightMap, M.empty) startingInput + where + settle :: (Int, Input, HeightMap, SupportMap) -> Brick -> (Int, Input, HeightMap, SupportMap) + settle (brickId, acc, hm, sm) (Brick (x1, y1, z1) (x2, y2, z2)) = (brickId+1, (Brick (a1, b1, height) (a2, b2, height-c1+c2)):acc, hm', sm') + where + (a1, a2, b1, b2, c1, c2) = (min x1 x2, max x1 x2, min y1 y2, max y1 y2, min z1 z2, max z1 z2) + (height, supports) = V.foldl' heightLine (0, []) (V.ifilter (\i _ -> i>= b1 && i <= b2) hm) + where + heightLine :: (Int, [Int]) -> V.Vector Height -> (Int, [Int]) -- height, [support] + heightLine acc line = V.foldl' heightElt acc (V.ifilter (\i _ -> i >= a1 && i <= a2) line) + where + heightElt :: (Int, [Int]) -> Height -> (Int, [Int]) + heightElt a@(hacc, _) (1, Nothing) | hacc > 1 = a + | otherwise = (1, []) + heightElt a@(hacc, sacc) (h, Just p) | hacc == h = (hacc, if elem p sacc then sacc else p:sacc) + | hacc > h = a + | otherwise = (h, [p]) + hm' = V.imap updateLine hm + where + updateLine :: Int -> V.Vector Height -> V.Vector Height + updateLine y line | y < b1 || y > b2 = line + | otherwise = V.imap updateElt line + where + updateElt :: Int -> Height -> Height + updateElt x z | x < a1 || x > a2 = z + | otherwise = (height+c2-c1+1, Just brickId) + sm' = M.insert brickId supports sm + startingHeightMap = V.replicate (ymax+1) (V.replicate (xmax+1) (1, Nothing)) + where + (xmax, ymax) = L.foldl' findBounds (xs, ys) input -- xmin and ymin are 0 for both example and input + where + Brick (xs, ys, _) _ = head input + findBounds :: (Int, Int) -> Brick -> (Int, Int) + findBounds (a, b) (Brick (x1, y1, _) (x2, y2, _)) = (maximum [a, x1, x2], maximum [b, y1, y2]) + startingInput = L.sort input + +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/22-Sand_Slabs/input b/2023/22-Sand_Slabs/input new file mode 100644 index 0000000..30e822f --- /dev/null +++ b/2023/22-Sand_Slabs/input @@ -0,0 +1,1280 @@ +7,0,231~7,2,231 +3,8,44~4,8,44 +4,2,331~4,4,331 +4,3,236~4,4,236 +4,6,155~4,8,155 +7,5,141~7,7,141 +7,7,72~7,9,72 +4,8,190~6,8,190 +6,2,107~8,2,107 +0,4,122~0,5,122 +6,1,177~6,3,177 +5,5,247~5,8,247 +0,1,184~3,1,184 +5,3,306~5,4,306 +1,2,13~3,2,13 +0,7,198~2,7,198 +5,7,333~8,7,333 +5,6,281~5,6,282 +3,6,8~5,6,8 +2,2,277~2,3,277 +2,4,229~3,4,229 +1,3,121~2,3,121 +5,4,317~7,4,317 +4,4,103~5,4,103 +3,6,200~3,8,200 +3,2,248~3,2,250 +3,4,162~3,7,162 +6,7,169~6,9,169 +0,9,148~1,9,148 +6,0,190~7,0,190 +6,3,247~6,5,247 +0,0,289~0,1,289 +0,2,228~3,2,228 +8,8,230~8,8,233 +2,4,221~2,6,221 +4,0,215~4,0,217 +3,4,250~6,4,250 +9,3,205~9,3,205 +1,2,227~1,4,227 +1,5,322~4,5,322 +7,4,18~7,5,18 +7,9,220~8,9,220 +0,9,326~1,9,326 +9,6,90~9,8,90 +0,1,62~0,3,62 +4,6,264~6,6,264 +5,0,100~7,0,100 +4,0,212~7,0,212 +2,5,289~2,7,289 +8,6,67~9,6,67 +7,5,20~7,5,22 +6,4,27~7,4,27 +0,3,225~0,4,225 +3,2,161~5,2,161 +4,8,269~5,8,269 +3,9,115~4,9,115 +6,7,222~6,7,224 +8,1,78~8,1,80 +9,3,301~9,5,301 +4,6,35~6,6,35 +0,6,14~0,8,14 +3,6,9~3,7,9 +6,6,99~8,6,99 +2,1,150~2,4,150 +5,5,248~5,7,248 +3,4,110~6,4,110 +5,6,65~5,8,65 +8,6,46~8,8,46 +6,7,168~8,7,168 +0,4,23~1,4,23 +9,3,14~9,5,14 +4,2,30~4,2,32 +7,1,244~7,2,244 +2,5,179~2,8,179 +0,2,44~0,3,44 +6,2,7~6,5,7 +3,8,39~5,8,39 +3,7,117~5,7,117 +2,7,196~5,7,196 +2,4,84~2,7,84 +4,2,150~4,5,150 +1,3,8~2,3,8 +7,7,136~7,8,136 +3,3,238~6,3,238 +3,1,25~5,1,25 +6,5,9~6,5,11 +0,9,109~2,9,109 +3,7,44~3,7,46 +5,7,37~5,9,37 +5,1,132~5,4,132 +6,8,100~7,8,100 +3,0,186~5,0,186 +2,3,305~2,5,305 +1,6,81~1,8,81 +1,0,325~3,0,325 +0,7,145~0,9,145 +3,5,135~4,5,135 +4,0,24~4,2,24 +0,0,188~0,0,190 +7,6,170~7,8,170 +5,1,186~7,1,186 +1,2,11~4,2,11 +5,1,271~8,1,271 +1,3,171~3,3,171 +2,0,187~2,3,187 +1,0,71~4,0,71 +1,7,295~1,8,295 +9,2,74~9,3,74 +3,7,233~3,9,233 +4,8,118~7,8,118 +2,7,24~2,9,24 +9,1,68~9,2,68 +2,9,144~3,9,144 +6,7,284~8,7,284 +6,9,95~6,9,96 +1,6,54~4,6,54 +8,2,204~8,3,204 +2,4,30~4,4,30 +2,2,42~3,2,42 +5,4,209~7,4,209 +8,6,24~8,8,24 +6,7,106~8,7,106 +6,7,181~6,9,181 +6,5,213~6,6,213 +5,1,75~5,2,75 +6,8,95~8,8,95 +6,4,230~7,4,230 +2,7,207~4,7,207 +2,0,100~3,0,100 +0,5,234~0,7,234 +0,7,226~0,7,228 +1,5,154~1,7,154 +1,3,297~1,5,297 +5,0,263~5,2,263 +9,7,288~9,8,288 +0,8,276~2,8,276 +1,3,47~3,3,47 +5,0,53~8,0,53 +5,4,264~7,4,264 +4,2,75~4,4,75 +3,0,312~3,3,312 +8,7,34~8,9,34 +7,0,101~9,0,101 +1,6,55~1,8,55 +0,7,205~1,7,205 +6,6,210~8,6,210 +1,9,272~3,9,272 +3,8,74~6,8,74 +4,8,286~6,8,286 +2,6,144~5,6,144 +7,5,23~7,5,24 +9,0,42~9,2,42 +3,5,131~5,5,131 +5,9,311~6,9,311 +0,7,207~0,7,207 +4,5,51~4,7,51 +9,6,40~9,8,40 +6,2,133~8,2,133 +9,4,233~9,4,233 +6,5,92~6,7,92 +0,4,326~3,4,326 +6,7,207~6,9,207 +6,4,166~6,7,166 +4,0,38~5,0,38 +5,3,252~7,3,252 +0,1,69~3,1,69 +5,1,69~7,1,69 +6,5,83~6,6,83 +8,8,218~8,9,218 +4,2,129~6,2,129 +7,0,233~7,2,233 +9,5,28~9,8,28 +1,7,232~4,7,232 +1,9,270~3,9,270 +6,7,220~6,7,221 +3,1,33~6,1,33 +5,6,102~7,6,102 +5,2,164~6,2,164 +9,4,110~9,6,110 +1,9,317~4,9,317 +8,0,109~8,3,109 +0,5,61~0,7,61 +1,4,225~1,6,225 +4,3,328~4,3,330 +1,8,280~3,8,280 +0,3,321~0,7,321 +2,8,72~3,8,72 +4,5,60~5,5,60 +4,3,195~4,5,195 +8,5,319~8,7,319 +4,4,149~5,4,149 +3,7,52~3,7,53 +7,5,67~9,5,67 +4,0,282~6,0,282 +6,6,192~6,7,192 +6,4,151~6,7,151 +3,2,106~6,2,106 +7,7,56~7,9,56 +7,2,1~7,4,1 +4,2,325~4,5,325 +0,3,51~2,3,51 +6,1,131~6,3,131 +8,0,241~8,3,241 +3,4,245~6,4,245 +6,7,286~9,7,286 +4,2,159~4,4,159 +3,5,299~3,7,299 +6,4,171~6,6,171 +7,0,238~9,0,238 +3,5,254~3,7,254 +6,3,86~6,5,86 +2,5,201~2,8,201 +1,8,274~2,8,274 +7,3,100~7,4,100 +4,8,192~5,8,192 +5,3,207~7,3,207 +7,4,316~8,4,316 +0,6,52~0,7,52 +7,7,101~9,7,101 +6,0,254~8,0,254 +2,6,245~6,6,245 +1,4,139~3,4,139 +9,3,305~9,4,305 +3,6,108~5,6,108 +1,6,249~1,6,250 +1,9,275~2,9,275 +0,4,292~0,6,292 +5,2,109~6,2,109 +3,7,256~3,7,259 +4,5,59~4,7,59 +1,5,27~1,8,27 +3,2,53~5,2,53 +5,9,26~7,9,26 +3,3,180~3,5,180 +6,3,24~6,5,24 +6,6,283~6,8,283 +9,1,289~9,3,289 +2,4,56~2,4,58 +6,4,97~9,4,97 +2,4,206~2,6,206 +4,9,277~5,9,277 +1,0,227~2,0,227 +6,6,121~6,8,121 +4,6,136~5,6,136 +3,1,55~6,1,55 +7,3,295~9,3,295 +5,6,122~5,9,122 +3,7,239~3,8,239 +1,5,235~1,7,235 +7,4,214~7,6,214 +5,6,21~7,6,21 +6,1,99~6,1,102 +7,2,323~8,2,323 +5,4,252~7,4,252 +0,7,25~2,7,25 +3,0,278~4,0,278 +2,6,91~2,9,91 +5,2,133~5,3,133 +4,3,152~6,3,152 +2,5,232~4,5,232 +3,1,181~3,4,181 +1,1,152~1,2,152 +4,4,251~6,4,251 +3,4,324~4,4,324 +5,3,60~5,3,60 +4,7,189~5,7,189 +5,2,36~7,2,36 +3,6,315~3,9,315 +6,8,104~6,8,106 +8,1,110~9,1,110 +2,8,42~2,9,42 +5,9,34~7,9,34 +7,0,288~7,3,288 +8,8,37~9,8,37 +5,7,90~5,9,90 +6,4,307~6,7,307 +9,5,233~9,8,233 +0,2,293~0,2,294 +9,2,45~9,2,45 +5,5,15~7,5,15 +1,2,41~3,2,41 +5,0,166~5,3,166 +6,5,105~6,7,105 +5,3,173~8,3,173 +4,6,115~4,8,115 +1,1,237~1,4,237 +6,5,194~9,5,194 +0,7,107~0,8,107 +5,1,142~6,1,142 +4,4,254~4,6,254 +4,6,134~6,6,134 +5,4,259~5,4,261 +4,3,297~4,4,297 +9,3,65~9,5,65 +1,3,52~2,3,52 +3,5,2~3,7,2 +7,2,270~7,4,270 +5,4,323~5,7,323 +3,1,150~3,2,150 +7,0,56~7,2,56 +9,0,35~9,3,35 +2,3,181~2,3,184 +2,7,185~5,7,185 +7,7,123~8,7,123 +8,4,294~8,7,294 +0,0,222~2,0,222 +4,0,254~5,0,254 +7,2,228~7,4,228 +5,1,260~5,2,260 +1,3,329~3,3,329 +9,5,153~9,7,153 +6,7,194~8,7,194 +4,4,32~4,6,32 +6,9,42~8,9,42 +1,7,294~1,8,294 +0,7,210~0,7,211 +8,8,49~8,9,49 +6,0,97~6,1,97 +0,6,140~1,6,140 +0,7,204~3,7,204 +7,9,227~9,9,227 +3,2,242~3,2,243 +5,0,193~7,0,193 +0,5,47~0,5,50 +7,9,136~9,9,136 +0,4,293~0,4,297 +9,5,303~9,6,303 +7,4,146~7,5,146 +5,2,335~7,2,335 +1,9,322~4,9,322 +7,7,75~7,9,75 +9,9,140~9,9,141 +1,3,120~3,3,120 +4,1,324~4,2,324 +8,7,297~8,9,297 +2,6,279~4,6,279 +1,4,312~1,6,312 +5,1,52~5,3,52 +6,5,62~9,5,62 +3,6,271~3,8,271 +1,2,184~4,2,184 +2,7,62~5,7,62 +2,2,130~3,2,130 +3,0,98~6,0,98 +3,7,236~4,7,236 +6,3,15~9,3,15 +6,1,268~7,1,268 +9,3,298~9,5,298 +3,4,230~3,6,230 +7,3,182~7,7,182 +9,3,308~9,6,308 +7,9,37~7,9,39 +4,5,193~4,7,193 +2,3,327~2,4,327 +2,8,94~4,8,94 +7,1,269~9,1,269 +4,5,246~4,5,250 +1,5,208~1,6,208 +4,1,74~6,1,74 +0,2,9~3,2,9 +0,4,56~0,6,56 +3,9,294~5,9,294 +7,0,52~9,0,52 +5,6,289~5,6,290 +0,3,13~0,4,13 +5,1,169~7,1,169 +3,5,59~3,8,59 +1,4,248~1,7,248 +0,4,88~2,4,88 +3,1,235~3,4,235 +0,3,28~0,6,28 +2,9,7~3,9,7 +1,8,211~1,9,211 +1,5,296~3,5,296 +1,8,221~2,8,221 +0,8,49~0,8,52 +7,0,6~7,3,6 +2,5,31~4,5,31 +6,5,260~6,6,260 +4,4,285~7,4,285 +6,4,313~8,4,313 +3,3,149~3,6,149 +2,6,272~4,6,272 +7,1,182~9,1,182 +6,4,215~9,4,215 +7,1,181~7,1,181 +3,6,92~3,6,92 +3,7,263~6,7,263 +0,0,38~1,0,38 +0,4,226~0,4,228 +7,1,234~7,1,234 +5,8,18~8,8,18 +9,4,232~9,5,232 +6,3,288~6,6,288 +6,3,325~7,3,325 +4,2,122~4,3,122 +4,1,102~4,4,102 +4,1,105~5,1,105 +6,8,3~6,9,3 +3,1,155~6,1,155 +2,3,118~2,5,118 +5,5,209~8,5,209 +6,1,229~6,3,229 +2,4,122~4,4,122 +2,8,111~2,9,111 +3,5,126~3,7,126 +7,9,36~9,9,36 +7,0,210~9,0,210 +3,2,241~5,2,241 +1,7,56~1,9,56 +1,7,60~1,9,60 +4,2,120~4,4,120 +2,7,177~4,7,177 +1,2,232~2,2,232 +2,0,38~2,2,38 +5,9,4~7,9,4 +6,5,265~6,7,265 +2,8,5~4,8,5 +0,0,9~2,0,9 +3,7,42~3,9,42 +7,1,241~7,2,241 +4,7,216~7,7,216 +2,8,311~5,8,311 +2,1,9~3,1,9 +8,4,15~9,4,15 +5,3,94~5,3,97 +1,0,77~3,0,77 +1,9,202~5,9,202 +3,6,313~3,9,313 +2,8,45~4,8,45 +3,4,322~5,4,322 +1,3,182~1,5,182 +6,3,201~9,3,201 +2,5,291~2,5,292 +5,7,91~5,8,91 +3,0,318~5,0,318 +3,1,245~3,3,245 +3,7,30~3,9,30 +3,4,65~3,4,67 +3,8,20~6,8,20 +6,3,226~9,3,226 +4,0,276~4,2,276 +7,9,205~9,9,205 +7,8,43~9,8,43 +3,8,157~3,8,160 +6,6,320~9,6,320 +0,7,82~0,7,82 +3,6,57~5,6,57 +1,7,79~4,7,79 +6,2,206~6,4,206 +2,0,14~2,0,17 +5,1,26~7,1,26 +8,4,318~8,5,318 +8,5,176~8,6,176 +5,5,328~7,5,328 +0,0,315~3,0,315 +6,7,23~6,9,23 +7,1,294~7,3,294 +6,1,92~6,3,92 +9,1,213~9,4,213 +1,0,150~1,2,150 +3,2,68~6,2,68 +6,5,205~6,8,205 +0,6,241~2,6,241 +2,5,211~4,5,211 +2,7,27~2,8,27 +4,9,94~7,9,94 +2,6,290~4,6,290 +4,3,206~4,3,208 +5,2,67~8,2,67 +3,7,159~5,7,159 +4,6,295~6,6,295 +0,8,22~0,8,24 +4,1,307~6,1,307 +7,8,89~9,8,89 +1,7,182~2,7,182 +2,9,43~3,9,43 +2,1,280~2,4,280 +3,8,148~5,8,148 +0,6,9~2,6,9 +9,4,211~9,4,211 +0,7,237~0,9,237 +3,5,106~3,6,106 +3,1,129~5,1,129 +6,1,323~6,3,323 +1,4,17~1,7,17 +5,5,329~5,6,329 +2,7,147~2,9,147 +9,7,105~9,8,105 +5,7,328~5,7,329 +6,2,54~7,2,54 +4,6,275~7,6,275 +8,3,286~9,3,286 +5,0,304~5,3,304 +4,2,186~6,2,186 +0,7,44~0,8,44 +9,4,16~9,7,16 +0,2,148~3,2,148 +8,3,20~8,5,20 +2,0,221~2,3,221 +0,0,297~0,2,297 +0,5,119~2,5,119 +1,3,228~1,5,228 +2,5,105~2,7,105 +6,6,106~8,6,106 +3,2,45~3,3,45 +5,6,84~5,8,84 +6,4,319~8,4,319 +6,0,147~8,0,147 +1,0,41~1,1,41 +7,7,289~7,9,289 +3,7,219~5,7,219 +7,7,173~9,7,173 +7,5,205~9,5,205 +3,5,10~3,7,10 +5,4,326~5,7,326 +5,2,58~5,4,58 +7,5,199~7,8,199 +3,0,27~5,0,27 +1,3,142~1,6,142 +1,2,299~1,3,299 +5,6,88~5,8,88 +5,2,332~5,5,332 +7,9,215~8,9,215 +2,0,224~5,0,224 +2,3,74~2,5,74 +0,2,108~2,2,108 +1,8,271~2,8,271 +4,1,71~4,3,71 +7,3,151~8,3,151 +2,5,57~2,6,57 +5,5,145~5,8,145 +7,6,209~8,6,209 +4,3,49~7,3,49 +0,1,174~2,1,174 +1,2,320~3,2,320 +0,4,287~2,4,287 +1,2,46~4,2,46 +1,7,289~1,9,289 +8,6,228~8,8,228 +1,3,239~1,4,239 +6,6,137~6,8,137 +4,0,105~6,0,105 +7,0,36~7,0,39 +4,5,321~4,7,321 +0,9,141~2,9,141 +2,4,147~5,4,147 +2,2,3~2,4,3 +5,2,29~5,2,30 +0,5,223~0,7,223 +6,6,93~6,8,93 +0,4,54~3,4,54 +8,3,143~8,3,143 +7,5,84~8,5,84 +7,7,3~7,9,3 +3,5,174~3,5,177 +3,8,21~5,8,21 +1,6,15~1,8,15 +2,3,82~2,6,82 +8,6,288~8,8,288 +2,2,289~2,2,289 +9,0,209~9,2,209 +3,0,324~6,0,324 +8,0,58~9,0,58 +9,1,16~9,3,16 +7,3,197~7,6,197 +6,9,82~8,9,82 +2,3,185~3,3,185 +6,1,153~6,3,153 +8,2,229~8,4,229 +0,2,327~2,2,327 +5,3,91~8,3,91 +3,4,74~5,4,74 +4,8,259~7,8,259 +4,0,168~7,0,168 +4,4,117~4,6,117 +2,3,169~5,3,169 +3,0,314~5,0,314 +9,7,156~9,8,156 +9,6,92~9,6,93 +0,2,224~0,4,224 +6,3,102~7,3,102 +4,8,147~6,8,147 +8,4,125~8,7,125 +4,0,21~4,2,21 +9,1,302~9,3,302 +3,2,282~4,2,282 +7,3,59~7,5,59 +5,6,19~5,8,19 +7,7,137~8,7,137 +1,0,45~2,0,45 +5,7,104~9,7,104 +2,5,235~2,7,235 +2,0,6~2,2,6 +6,4,185~7,4,185 +4,2,60~6,2,60 +2,8,212~5,8,212 +1,9,203~2,9,203 +7,4,283~9,4,283 +6,4,126~8,4,126 +5,7,22~7,7,22 +3,3,204~6,3,204 +6,5,291~9,5,291 +0,7,143~0,9,143 +4,6,234~4,6,236 +6,6,190~8,6,190 +1,0,21~2,0,21 +1,0,74~3,0,74 +3,1,151~3,1,154 +2,2,105~4,2,105 +6,6,48~8,6,48 +8,4,141~8,4,143 +2,6,10~2,8,10 +0,9,31~3,9,31 +3,7,73~5,7,73 +0,3,31~0,6,31 +4,5,270~6,5,270 +1,7,266~3,7,266 +6,1,31~8,1,31 +7,8,84~7,8,87 +7,1,104~7,3,104 +0,8,142~0,9,142 +6,4,310~8,4,310 +4,0,285~7,0,285 +7,7,129~7,7,132 +0,9,284~1,9,284 +7,4,322~8,4,322 +2,4,12~2,7,12 +3,5,3~5,5,3 +4,2,127~4,4,127 +7,9,216~9,9,216 +7,6,201~9,6,201 +5,5,179~8,5,179 +6,0,338~6,2,338 +2,6,7~5,6,7 +2,2,29~2,3,29 +5,1,36~7,1,36 +3,2,113~3,4,113 +0,4,229~0,4,232 +4,1,187~4,1,189 +9,0,75~9,2,75 +4,6,276~6,6,276 +7,4,150~7,5,150 +6,6,270~8,6,270 +5,5,121~6,5,121 +7,7,28~7,7,28 +5,0,60~8,0,60 +5,4,263~5,6,263 +2,8,234~4,8,234 +6,3,89~6,5,89 +8,6,222~9,6,222 +5,5,95~8,5,95 +9,0,243~9,0,244 +5,4,203~7,4,203 +2,7,267~2,9,267 +8,3,285~8,5,285 +0,7,273~0,9,273 +5,5,154~5,8,154 +4,9,280~6,9,280 +9,1,38~9,1,41 +6,0,180~6,1,180 +1,8,322~3,8,322 +2,2,152~2,3,152 +9,2,218~9,6,218 +1,9,5~1,9,6 +4,8,162~6,8,162 +0,5,271~0,8,271 +0,2,101~0,4,101 +6,7,97~6,8,97 +1,2,66~1,5,66 +3,7,49~6,7,49 +5,7,308~5,8,308 +7,3,37~9,3,37 +5,3,4~5,3,5 +1,3,180~1,5,180 +0,0,42~2,0,42 +3,1,309~3,4,309 +4,5,13~6,5,13 +7,6,77~7,6,79 +9,1,153~9,3,153 +2,2,162~4,2,162 +7,2,295~9,2,295 +6,6,261~6,7,261 +2,5,116~5,5,116 +7,1,28~7,2,28 +8,1,70~8,2,70 +4,4,125~4,5,125 +0,7,231~1,7,231 +5,6,269~8,6,269 +4,2,25~4,5,25 +2,9,234~4,9,234 +5,8,268~7,8,268 +3,4,323~3,7,323 +4,1,277~4,1,279 +1,3,310~1,5,310 +3,8,146~4,8,146 +8,7,212~8,9,212 +3,3,108~3,5,108 +3,7,249~6,7,249 +6,0,96~6,2,96 +8,6,55~8,8,55 +4,2,319~4,4,319 +8,4,64~8,6,64 +3,0,339~6,0,339 +2,5,14~2,8,14 +3,4,55~3,5,55 +8,1,231~8,3,231 +5,4,21~6,4,21 +0,0,40~0,3,40 +4,7,238~5,7,238 +9,0,241~9,1,241 +4,9,38~5,9,38 +5,7,252~5,7,256 +2,6,95~2,9,95 +2,6,187~2,8,187 +2,0,80~5,0,80 +5,1,135~7,1,135 +0,1,220~0,4,220 +3,0,104~5,0,104 +5,9,74~7,9,74 +8,7,227~8,8,227 +5,1,340~7,1,340 +6,7,52~6,8,52 +0,4,213~2,4,213 +2,1,310~2,4,310 +5,4,288~5,7,288 +8,1,177~8,2,177 +1,0,35~5,0,35 +9,5,63~9,8,63 +1,2,234~2,2,234 +0,9,204~1,9,204 +7,1,10~7,2,10 +3,5,91~3,8,91 +8,4,85~8,5,85 +0,3,83~0,6,83 +7,1,148~7,4,148 +3,8,96~3,8,98 +2,7,218~4,7,218 +1,4,135~1,6,135 +7,4,280~7,6,280 +2,6,223~3,6,223 +6,0,171~9,0,171 +3,1,325~3,4,325 +6,7,100~8,7,100 +6,1,56~6,3,56 +3,4,68~3,4,69 +8,1,257~8,4,257 +7,5,260~7,5,260 +7,0,51~7,3,51 +6,5,316~8,5,316 +4,4,296~6,4,296 +5,1,243~5,2,243 +1,2,230~3,2,230 +0,3,314~2,3,314 +9,2,79~9,4,79 +9,2,202~9,3,202 +0,4,298~0,6,298 +0,5,92~3,5,92 +7,6,172~7,8,172 +0,1,193~0,4,193 +9,4,302~9,7,302 +3,1,247~3,1,249 +6,3,11~7,3,11 +4,6,250~6,6,250 +3,5,222~6,5,222 +4,2,231~6,2,231 +4,4,114~4,7,114 +0,6,11~1,6,11 +1,7,90~1,8,90 +1,3,155~1,4,155 +1,4,89~3,4,89 +1,1,27~3,1,27 +3,1,58~5,1,58 +6,3,8~6,4,8 +6,5,255~6,8,255 +3,6,292~3,9,292 +1,5,294~2,5,294 +0,2,48~2,2,48 +3,9,204~5,9,204 +1,9,283~4,9,283 +0,9,33~0,9,35 +8,3,218~8,6,218 +1,2,186~1,4,186 +5,0,65~7,0,65 +2,5,142~2,6,142 +7,9,137~9,9,137 +5,6,175~8,6,175 +6,7,258~6,9,258 +4,0,146~6,0,146 +7,6,236~8,6,236 +8,0,11~8,0,13 +5,7,258~5,8,258 +0,4,277~3,4,277 +2,7,222~4,7,222 +1,3,317~3,3,317 +0,8,41~3,8,41 +5,4,254~7,4,254 +9,1,216~9,1,218 +2,3,5~2,6,5 +7,9,290~7,9,292 +7,6,291~9,6,291 +6,7,219~6,9,219 +4,4,162~4,6,162 +4,6,161~4,9,161 +0,8,21~2,8,21 +5,3,223~6,3,223 +2,3,38~2,5,38 +3,3,220~6,3,220 +1,5,19~1,8,19 +0,3,176~1,3,176 +2,1,159~4,1,159 +6,2,238~9,2,238 +3,5,153~5,5,153 +0,4,20~2,4,20 +5,6,279~7,6,279 +3,6,69~3,8,69 +0,7,320~4,7,320 +9,0,240~9,2,240 +2,9,27~5,9,27 +4,7,70~8,7,70 +0,0,113~0,2,113 +1,5,132~1,7,132 +6,5,18~6,6,18 +4,3,33~4,5,33 +6,7,310~6,9,310 +7,4,206~7,7,206 +2,9,5~4,9,5 +4,4,317~4,6,317 +0,8,296~1,8,296 +0,0,114~0,2,114 +4,1,47~4,3,47 +0,1,292~0,2,292 +1,7,221~4,7,221 +1,5,129~3,5,129 +1,8,93~3,8,93 +2,4,212~6,4,212 +4,4,194~4,5,194 +2,3,249~2,5,249 +4,3,250~6,3,250 +1,7,200~1,9,200 +9,2,76~9,4,76 +4,0,30~4,1,30 +6,9,83~6,9,85 +6,7,266~6,7,269 +2,5,209~3,5,209 +5,6,166~5,8,166 +2,8,189~4,8,189 +7,6,294~7,7,294 +0,3,179~3,3,179 +7,0,102~9,0,102 +7,1,76~9,1,76 +5,7,221~5,7,223 +2,5,304~2,8,304 +7,4,202~9,4,202 +7,1,138~7,3,138 +6,7,83~9,7,83 +3,7,250~4,7,250 +6,9,261~7,9,261 +1,2,153~1,5,153 +3,2,62~3,5,62 +0,4,215~0,4,217 +2,7,107~2,9,107 +8,3,256~8,4,256 +3,6,155~3,8,155 +2,2,237~5,2,237 +3,7,72~6,7,72 +0,9,287~2,9,287 +6,9,103~8,9,103 +4,2,273~4,5,273 +3,1,28~3,2,28 +0,4,290~0,5,290 +4,3,3~7,3,3 +2,1,224~3,1,224 +0,1,324~0,4,324 +6,5,252~6,7,252 +7,8,306~9,8,306 +8,5,86~8,7,86 +1,5,205~4,5,205 +1,3,63~3,3,63 +4,9,295~6,9,295 +6,1,34~6,3,34 +9,0,307~9,2,307 +7,3,269~7,5,269 +7,1,170~7,1,172 +6,4,299~7,4,299 +7,9,30~9,9,30 +3,4,171~3,6,171 +9,5,108~9,8,108 +0,2,314~2,2,314 +5,5,22~6,5,22 +9,2,229~9,4,229 +6,3,315~8,3,315 +7,2,174~7,4,174 +4,5,220~4,8,220 +0,2,46~0,5,46 +0,7,106~2,7,106 +4,2,279~7,2,279 +6,9,171~7,9,171 +0,5,78~3,5,78 +2,7,302~4,7,302 +3,6,152~5,6,152 +7,4,221~9,4,221 +8,3,234~8,6,234 +0,1,190~2,1,190 +3,7,67~5,7,67 +4,2,2~4,3,2 +2,8,144~4,8,144 +0,6,204~3,6,204 +9,5,70~9,5,74 +8,4,230~8,4,230 +5,1,138~5,1,140 +9,2,66~9,4,66 +4,4,198~4,4,201 +4,2,181~6,2,181 +9,2,13~9,5,13 +2,3,274~2,5,274 +3,6,175~3,8,175 +6,2,93~8,2,93 +4,7,280~6,7,280 +3,5,316~3,6,316 +9,2,221~9,2,223 +7,1,305~9,1,305 +3,6,95~4,6,95 +3,6,231~4,6,231 +6,4,186~8,4,186 +0,1,42~0,3,42 +2,6,139~2,9,139 +0,4,51~2,4,51 +9,2,242~9,2,243 +6,5,31~9,5,31 +3,9,92~7,9,92 +1,3,141~3,3,141 +8,6,220~8,7,220 +6,2,175~8,2,175 +4,7,186~5,7,186 +6,7,193~9,7,193 +2,1,313~2,4,313 +7,9,95~9,9,95 +7,5,213~7,7,213 +3,5,301~4,5,301 +7,7,133~7,9,133 +6,4,258~6,4,261 +0,7,110~0,9,110 +9,5,152~9,7,152 +7,5,103~9,5,103 +3,3,98~5,3,98 +6,6,223~8,6,223 +2,0,37~2,3,37 +5,2,324~6,2,324 +5,9,32~8,9,32 +9,1,71~9,3,71 +4,5,27~4,6,27 +5,0,183~5,2,183 +6,6,96~7,6,96 +0,6,138~2,6,138 +3,6,178~5,6,178 +6,8,48~8,8,48 +7,2,100~9,2,100 +2,7,220~2,8,220 +3,1,37~6,1,37 +2,6,128~4,6,128 +0,2,30~0,4,30 +6,7,128~8,7,128 +8,4,2~8,6,2 +3,0,323~3,2,323 +0,2,59~0,4,59 +0,3,49~0,4,49 +3,4,151~4,4,151 +3,1,186~4,1,186 +3,1,158~5,1,158 +4,4,16~4,6,16 +5,6,148~7,6,148 +2,3,247~2,5,247 +2,7,210~2,9,210 +0,1,110~0,3,110 +0,2,1~0,4,1 +5,5,16~5,8,16 +2,2,286~2,5,286 +5,6,267~5,8,267 +4,2,239~4,4,239 +5,0,286~5,0,288 +5,5,93~8,5,93 +5,2,235~5,4,235 +1,9,207~1,9,208 +3,0,60~3,1,60 +7,1,49~9,1,49 +4,5,192~7,5,192 +3,4,314~6,4,314 +0,8,17~2,8,17 +8,6,239~8,7,239 +6,4,255~8,4,255 +0,9,2~2,9,2 +4,1,274~4,3,274 +3,7,4~3,9,4 +2,1,217~2,3,217 +3,7,165~6,7,165 +4,5,267~6,5,267 +6,2,179~6,3,179 +2,0,167~2,2,167 +5,0,341~7,0,341 +5,1,66~7,1,66 +3,6,194~4,6,194 +1,0,302~1,2,302 +3,7,319~3,9,319 +5,3,134~7,3,134 +2,8,142~3,8,142 +6,0,38~6,1,38 +3,7,197~5,7,197 +4,2,243~4,5,243 +8,0,56~8,2,56 +1,7,92~3,7,92 +3,3,51~5,3,51 +6,3,290~6,3,291 +2,4,72~4,4,72 +1,6,222~3,6,222 +5,9,28~7,9,28 +7,0,177~7,2,177 +4,6,188~7,6,188 +6,9,79~8,9,79 +2,5,55~2,6,55 +7,6,151~9,6,151 +5,2,37~5,2,40 +2,3,86~2,6,86 +3,6,22~5,6,22 +0,0,11~2,0,11 +0,1,43~0,2,43 +0,1,223~0,1,223 +7,8,21~8,8,21 +9,6,5~9,8,5 +2,5,103~5,5,103 +6,0,62~8,0,62 +5,2,62~5,3,62 +7,9,207~9,9,207 +3,4,169~6,4,169 +0,4,26~0,6,26 +1,7,326~3,7,326 +4,1,185~6,1,185 +7,0,34~7,2,34 +1,8,324~1,8,326 +6,4,19~8,4,19 +5,6,119~5,8,119 +0,1,188~0,4,188 +6,7,54~8,7,54 +6,7,101~6,9,101 +6,2,291~8,2,291 +3,7,275~3,9,275 +4,5,120~6,5,120 +3,2,206~3,4,206 +2,4,243~2,7,243 +4,2,100~4,5,100 +5,5,225~7,5,225 +2,9,274~5,9,274 +8,1,272~8,1,273 +4,8,48~4,9,48 +2,7,318~3,7,318 +8,1,81~9,1,81 +3,7,210~6,7,210 +2,0,170~2,0,170 +0,0,285~0,2,285 +4,8,260~6,8,260 +1,2,165~3,2,165 +3,4,233~5,4,233 +2,4,226~2,6,226 +5,0,187~8,0,187 +6,2,134~9,2,134 +0,3,81~0,5,81 +3,7,116~4,7,116 +5,5,220~5,7,220 +6,6,120~6,9,120 +2,7,186~2,9,186 +8,7,71~8,9,71 +9,0,32~9,3,32 +1,1,195~1,1,197 +3,5,76~3,8,76 +0,0,287~0,2,287 +8,4,138~8,7,138 +4,7,120~4,8,120 +7,2,236~9,2,236 +7,1,39~7,3,39 +7,0,8~8,0,8 +4,3,217~4,7,217 +5,9,78~7,9,78 +7,6,219~7,8,219 +8,6,89~8,6,92 +1,0,68~1,3,68 +8,2,111~9,2,111 +1,9,324~3,9,324 +6,6,183~6,6,185 +7,6,140~7,8,140 +8,7,242~9,7,242 +3,5,202~7,5,202 +0,0,187~0,3,187 +4,6,29~4,7,29 +6,0,189~7,0,189 +7,2,29~9,2,29 +2,0,19~4,0,19 +2,7,23~5,7,23 +5,8,40~7,8,40 +2,5,299~2,7,299 +2,4,214~2,6,214 +0,4,58~0,6,58 +2,0,177~2,1,177 +5,5,17~5,5,20 +6,3,317~6,3,320 +5,2,258~8,2,258 +4,7,331~5,7,331 +3,2,124~3,5,124 +4,9,276~5,9,276 +4,2,322~7,2,322 +7,0,57~7,0,59 +2,0,33~4,0,33 +1,1,123~1,3,123 +1,3,308~3,3,308 +5,5,104~8,5,104 +2,1,14~2,2,14 +0,5,106~2,5,106 +4,4,190~4,6,190 +1,2,27~5,2,27 +1,2,147~4,2,147 +5,3,246~5,4,246 +6,4,181~6,6,181 +0,0,230~3,0,230 +4,0,36~6,0,36 +4,1,32~5,1,32 +1,5,41~3,5,41 +0,2,150~0,3,150 +3,9,97~5,9,97 +8,3,312~8,5,312 +9,8,225~9,9,225 +5,4,324~5,5,324 +3,7,277~6,7,277 +3,5,291~5,5,291 +0,1,70~3,1,70 +2,7,306~6,7,306 +2,9,114~3,9,114 +5,3,182~5,5,182 +6,5,174~7,5,174 +1,0,173~1,3,173 +6,6,149~7,6,149 +0,0,283~0,2,283 +7,3,286~7,6,286 +1,1,239~1,2,239 +0,6,46~0,8,46 +6,6,225~7,6,225 +0,6,49~0,6,49 +0,8,291~1,8,291 +6,8,4~9,8,4 +6,5,315~8,5,315 +7,5,82~7,8,82 +4,0,101~6,0,101 +5,4,301~7,4,301 +2,4,174~4,4,174 +5,0,176~7,0,176 +0,7,294~0,9,294 +1,2,138~1,4,138 +0,5,80~0,7,80 +1,2,311~3,2,311 +0,4,98~0,7,98 +0,0,44~2,0,44 +2,1,283~2,2,283 +2,8,66~5,8,66 +5,0,3~5,2,3 +7,5,121~7,8,121 +9,3,100~9,5,100 +7,0,68~8,0,68 +3,6,251~4,6,251 +1,3,143~1,6,143 +6,5,258~7,5,258 +4,0,236~7,0,236 +4,6,81~7,6,81 +1,4,201~1,8,201 +4,7,179~6,7,179 +1,5,271~4,5,271 +9,1,44~9,1,46 +2,1,239~5,1,239 +3,6,111~5,6,111 +7,6,74~7,8,74 +0,2,181~0,3,181 +7,3,152~9,3,152 +6,0,143~6,2,143 +2,2,91~2,4,91 +8,5,30~9,5,30 +1,1,191~1,3,191 +2,5,28~5,5,28 +5,3,302~5,6,302 +9,1,245~9,3,245 +8,2,98~8,4,98 +7,3,227~7,4,227 +2,6,114~3,6,114 +4,0,173~7,0,173 +4,8,87~6,8,87 +0,5,94~0,5,96 +3,4,97~3,6,97 +6,5,2~6,5,5 +0,8,268~3,8,268 +1,0,304~1,1,304 +5,7,157~8,7,157 +2,3,186~5,3,186 +4,0,40~4,0,40 +0,5,270~0,8,270 +1,2,56~5,2,56 +1,5,59~1,7,59 +6,4,216~6,4,218 +4,0,251~7,0,251 +2,3,81~2,5,81 +1,1,193~1,1,193 +3,5,208~5,5,208 +3,3,210~4,3,210 +6,0,145~7,0,145 +6,4,68~9,4,68 +8,7,102~8,9,102 +7,4,267~8,4,267 +2,2,144~2,4,144 +3,1,127~3,3,127 +5,4,256~5,5,256 +8,8,210~8,9,210 +3,6,172~3,9,172 +1,6,239~4,6,239 +4,5,168~4,8,168 +0,0,280~4,0,280 +3,9,293~5,9,293 +3,0,81~5,0,81 +7,8,220~7,8,222 +4,3,132~4,6,132 +8,0,172~8,1,172 +5,9,203~8,9,203 +1,5,246~3,5,246 +0,8,88~4,8,88 +8,3,140~8,6,140 +2,1,219~2,4,219 +2,7,195~4,7,195 +6,3,273~8,3,273 +2,1,236~4,1,236 +6,5,289~6,7,289 +0,3,222~0,5,222 +5,3,170~5,3,170 +4,5,235~7,5,235 +1,8,3~1,8,5 +3,4,184~3,4,186 +3,4,278~3,6,278 +9,2,47~9,2,49 +2,3,215~2,5,215 +5,2,8~8,2,8 +2,4,22~2,4,25 +9,1,208~9,4,208 +0,3,11~2,3,11 +3,1,313~3,1,315 +6,0,58~6,1,58 +6,3,12~9,3,12 +6,8,224~9,8,224 +5,6,101~7,6,101 +0,2,317~1,2,317 +9,7,303~9,9,303 +1,1,109~1,2,109 +4,0,179~6,0,179 +7,5,57~7,8,57 +4,4,293~4,6,293 +1,8,12~3,8,12 +3,7,278~3,9,278 +0,1,231~0,3,231 +7,0,308~7,1,308 +6,1,267~6,4,267 +4,3,156~4,6,156 +7,1,179~9,1,179 +4,1,154~6,1,154 +1,8,18~2,8,18 +9,2,17~9,4,17 +8,3,94~8,5,94 +7,7,27~9,7,27 +2,3,27~2,6,27 +0,2,139~1,2,139 +0,3,323~2,3,323 +0,7,140~2,7,140 +7,0,27~7,2,27 +7,0,146~9,0,146 +5,1,65~5,4,65 +5,0,249~5,3,249 +9,5,109~9,7,109 +7,5,144~7,8,144 +7,3,199~7,4,199 diff --git a/2023/22-Sand_Slabs/second.hs b/2023/22-Sand_Slabs/second.hs new file mode 100644 index 0000000..8acbb10 --- /dev/null +++ b/2023/22-Sand_Slabs/second.hs @@ -0,0 +1,125 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 7 + +type Coord = (Int, Int, Int) +data Brick = Brick Coord Coord deriving (Eq, Show) +instance Ord Brick where + (Brick (_, _, z1) (_, _, z2)) `compare` (Brick (_, _, c1) (_, _, c2)) = min z1 z2 `compare` min c1 c2 +type Input = [Brick] + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read <$> some digitChar <* optional (char ',') + +parseCoord :: Parser Coord +parseCoord = (,,) <$> parseNumber + <*> parseNumber + <*> parseNumber + +parseBrick :: Parser Brick +parseBrick = Brick <$> parseCoord <* char '~' + <*> parseCoord <* eol + +parseInput' :: Parser Input +parseInput' = some parseBrick <* 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' + +type Height = (Int, Maybe Int) -- (Height, BrickId that achieved that height - 1) +type HeightMap = V.Vector (V.Vector Height) +type SupportMap = M.Map Int [Int] -- BrickId -> [supports brickIds] + +compute :: Input -> Int +compute input = sum $ map howManyWouldFallIf $ L.filter (isSupportBrick supportMap) $ [0..(length input - 1)] + where + howManyWouldFallIf :: Int -> Int + howManyWouldFallIf brickId = length . snd $ removeFalling (supportMap, []) [brickId] + where + removeFalling :: (SupportMap, [Int]) -> [Int] -> (SupportMap, [Int]) + removeFalling acc@(sm, l) f | supportBricks == [] = acc + | otherwise = removeFalling (sm', l ++ supportBricks) supportBricks + where + removeOne :: SupportMap -> Int -> SupportMap + removeOne sm i = M.map (L.delete i) $ M.delete i sm + sm' :: SupportMap + sm' = L.foldl' removeOne sm f + supportBricks :: [Int] + supportBricks = L.filter unsupported $ M.keys sm' + where + unsupported :: Int -> Bool + unsupported i = sm' M.! i == [] && let (Brick (_, _, z) _) = settledInput L.!! i in z > 1 + isSupportBrick :: SupportMap -> Int -> Bool + isSupportBrick sm brickId = L.any isSoleSupport $ M.elems sm + where + isSoleSupport :: [Int] -> Bool + isSoleSupport [l] = brickId == l + isSoleSupport _ = False + (_, settledInput, heightMap, supportMap) = L.foldl' settle (0, [], startingHeightMap, M.empty) startingInput + where + settle :: (Int, Input, HeightMap, SupportMap) -> Brick -> (Int, Input, HeightMap, SupportMap) + settle (brickId, acc, hm, sm) (Brick (x1, y1, z1) (x2, y2, z2)) = (brickId+1, acc ++ [(Brick (a1, b1, height) (a2, b2, height-c1+c2))], hm', sm') + where + (a1, a2, b1, b2, c1, c2) = (min x1 x2, max x1 x2, min y1 y2, max y1 y2, min z1 z2, max z1 z2) + (height, supports) = V.foldl' heightLine (0, []) (V.ifilter (\i _ -> i>= b1 && i <= b2) hm) + where + heightLine :: (Int, [Int]) -> V.Vector Height -> (Int, [Int]) -- height, [support] + heightLine acc line = V.foldl' heightElt acc (V.ifilter (\i _ -> i >= a1 && i <= a2) line) + where + heightElt :: (Int, [Int]) -> Height -> (Int, [Int]) + heightElt a@(hacc, _) (1, Nothing) | hacc > 1 = a + | otherwise = (1, []) + heightElt a@(hacc, sacc) (h, Just p) | hacc == h = (hacc, if elem p sacc then sacc else p:sacc) + | hacc > h = a + | otherwise = (h, [p]) + hm' = V.imap updateLine hm + where + updateLine :: Int -> V.Vector Height -> V.Vector Height + updateLine y line | y < b1 || y > b2 = line + | otherwise = V.imap updateElt line + where + updateElt :: Int -> Height -> Height + updateElt x z | x < a1 || x > a2 = z + | otherwise = (height+c2-c1+1, Just brickId) + sm' = M.insert brickId supports sm + startingHeightMap = V.replicate (ymax+1) (V.replicate (xmax+1) (1, Nothing)) + where + (xmax, ymax) = L.foldl' findBounds (xs, ys) input -- xmin and ymin are 0 for both example and input + where + Brick (xs, ys, _) _ = head input + findBounds :: (Int, Int) -> Brick -> (Int, Int) + findBounds (a, b) (Brick (x1, y1, _) (x2, y2, _)) = (maximum [a, x1, x2], maximum [b, y1, y2]) + startingInput = L.sort input + +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/23-A_Long_Walk/example b/2023/23-A_Long_Walk/example new file mode 100644 index 0000000..ea945a4 --- /dev/null +++ b/2023/23-A_Long_Walk/example @@ -0,0 +1,23 @@ +#.##################### +#.......#########...### +#######.#########.#.### +###.....#.>.>.###.#.### +###v#####.#v#.###.#.### +###.>...#.#.#.....#...# +###v###.#.#.#########.# +###...#.#.#.......#...# +#####.#.#.#######.#.### +#.....#.#.#.......#...# +#.#####.#.#.#########v# +#.#...#...#...###...>.# +#.#.#v#######v###.###v# +#...#.>.#...>.>.#.###.# +#####v#.#.###v#.#.###.# +#.....#...#...#.#.#...# +#.#########.###.#.#.### +#...###...#...#...#.### +###.###.#.###v#####v### +#...#...#.#.>.>.#.>.### +#.###.###.#.###.#.#v### +#.....###...###...#...# +#####################.# diff --git a/2023/23-A_Long_Walk/first.hs b/2023/23-A_Long_Walk/first.hs new file mode 100644 index 0000000..297105f --- /dev/null +++ b/2023/23-A_Long_Walk/first.hs @@ -0,0 +1,148 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = Just 94 + +data Direction = N | S | E | W deriving (Eq, Show) +data Tile = Floor | Wall | Slope Direction deriving (Eq, Show) +type Line = V.Vector Tile +type Input = V.Vector Line + +type Parser = Parsec Void String + +parseDirection :: Parser Direction +parseDirection = char '^' $> N + <|> char 'v' $> S + <|> char '>' $> E + <|> char '<' $> W + +parseTile :: Parser Tile +parseTile = char '#' $> Wall + <|> char '.' $> Floor + <|> Slope <$> parseDirection + +parseLine :: Parser Line +parseLine = do + line <- some parseTile <* eol + return $ V.generate (length line) (line !!) + +parseInput' :: Parser Input +parseInput' = do + line <- some parseLine <* eof + return $ V.generate (length line) (line !!) + +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' + +newtype Cost = Cost Int deriving (Eq, Num, Ord, Show) +newtype NodeId = NodeId Int deriving (Eq, Num, Ord, Show) +newtype X = X Int deriving (Eq, Num, Ord, Show) +newtype Y = Y Int deriving (Eq, Num, Ord, Show) +type Adjacencies = M.Map NodeId [(NodeId, Cost)] -- keys are nodeIds and values are a list of (NodeId, cost) +type Nodes = M.Map (X, Y) NodeId -- keys are (x, y) and values are nodeIds +type Visited = M.Map (X, Y) () + +compute :: Input -> Maybe Cost +compute input = longuestPath adjacencies (let Just (a:[]) = M.lookup 0 adjacencies in a) + where + longuestPath :: Adjacencies -> (NodeId, Cost) -> Maybe Cost + longuestPath adj (n, c) | n == 1 = Just $ c + 1 + | l' == [] = Nothing + | otherwise = Just $ c + maximum l' + where + Just l = M.lookup n adj + l' = catMaybes $ L.map (longuestPath adj') l + adj' = M.delete n $ M.map (L.filter (\(i, _) -> n /= i)) adj + (adjacencies, nodes, _) = explore 0 (M.fromList [(0, []), (1, [])]) (M.fromList [((startx, 0), 0), ((finishx, finishy), 1)]) (M.fromList [((startx, 0), ()), ((finishx, finishy), ())]) startx 1 S + explore :: NodeId -> Adjacencies -> Nodes -> Visited -> X -> Y -> Direction -> (Adjacencies, Nodes, Visited) + explore node adjacencies nodes visited x y d = L.foldl' explore' (adjacencies, nodes, visited) $ nextSteps x y d + where + explore' :: (Adjacencies, Nodes, Visited) -> (X, Y, Direction, Bool) -> (Adjacencies, Nodes, Visited) + explore' acc@(adjacencies, nodes, visited) (x, y, d, u) | isNothing destination = acc + | otherwise = case M.lookup (x', y') nodes of + Nothing -> explore node' adjacencies'' nodes' visited' x' y' d + Just id -> (adjacencies'', nodes', visited') + where + destination = let s = goDownAPath visited False x y 1 d in s + Just (visited', x', y', cost, u') = destination + adjacencies'' = M.adjust (\l -> (node', cost):l) node $ M.adjust (\l -> if u || u' then l else (node, cost):l) node' adjacencies' + nodes' = M.insert (x', y') node' nodes + (node', adjacencies') = case M.lookup (x', y') nodes of + Nothing -> let s = NodeId (M.size nodes) in (s, M.insert s [] adjacencies) + Just node' -> (node', adjacencies) + goDownAPath :: Visited -> Bool -> X -> Y -> Cost -> Direction -> Maybe (Visited, X, Y, Cost, Bool) -- returns the next intersection's coordinates and cost, and if it is unidirectional + goDownAPath visited u x y c d | M.member (x, y) nodes = Just (visited, x, y, c, u) -- we reached an already known intersection + | M.member (x, y) visited = Nothing -- this tile has already been visited + | isImpossibleSlope = Nothing + | ns == [] = Nothing -- we hit a deadend + | L.length ns > 1 = Just (visited', x, y, c, u'') -- we hit a crossroads + | otherwise = goDownAPath visited' u'' x' y' (c+1) d' + where + (x', y', d', u') = head ns + u'' = u || u' + ns = nextSteps x y d + visited' = M.insert (x, y) () visited + isImpossibleSlope = case getTile (x, y) of + Slope s -> s /= d + otherwise -> False + getTile :: (X, Y) -> Tile + getTile (X x, Y y) = input V.! y V.! x + nextSteps :: X -> Y -> Direction -> [(X, Y, Direction, Bool)] -- get the list of possible next steps at a point, given where we came from + nextSteps x y d = L.map augmentWithUnidirectionality $ L.filter possible [(x-1, y, W), (x+1, y, E), (x, y-1, N), (x, y+1, S)] + where + augmentWithUnidirectionality :: (X, Y, Direction) -> (X, Y, Direction, Bool) + augmentWithUnidirectionality (x, y, d) = (x, y, d, isSlope $ getTile (x, y)) + isSlope :: Tile -> Bool + isSlope (Slope _) = True + isSlope _ = False + possible :: (X, Y, Direction) -> Bool + possible (x', y', d') | t == Wall = False + | d == opposite d' = False -- no going back + -- | t == Floor = True + | otherwise = True -- o == d' -- our direction must match the slope <- NO, this prevents us from properly finding intersections + where + t = getTile (x', y') + Slope o = t + Just start = V.findIndex (== Floor) $ input V.! 0 + startx = X start + Just finish = V.findIndex (== Floor) $ input V.! finishyy + finishx = X finish + finishyy = V.length input - 1 + finishy = Y finishyy + xydToxy :: (a, b, c) -> (a, b) + xydToxy (x, y, _) = (x, y) + opposite :: Direction -> Direction + opposite N = S + opposite S = N + opposite E = W + opposite W = E + +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/23-A_Long_Walk/input b/2023/23-A_Long_Walk/input new file mode 100644 index 0000000..50127c5 --- /dev/null +++ b/2023/23-A_Long_Walk/input @@ -0,0 +1,141 @@ +#.########################################################################################################################################### +#.............#...#...###...#...#.......#...###...#...#...#.....#...#...#...###...#...#...#.....###...#.....#...#####...#...#...............# +#############.#.#.#.#.###.#.#.#.#.#####.#.#.###.#.#.#.#.#.#.###.#.#.#.#.#.#.###.#.#.#.#.#.#.###.###.#.#.###.#.#.#####.#.#.#.#.#############.# +#.............#.#...#.#...#.#.#...#.....#.#...#.#.#.#.#.#.#.#...#.#.#.#.#.#.#...#.#.#.#.#.#.#...#...#.#...#...#...#...#.#.#.#.......#.......# +#.#############.#####.#.###.#.#####.#####.###.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.###.#.#.#.#.#.#.###.###.###.#######.#.###.#.#.#######.#.####### +#.............#.....#.#...#.#.#.....#...#.#...#.#.#.#.#.#...#...#.#...#.#.#.#...#.#.#.#.#.#.#...#...#.###.....#...#...#...#...#...#.#.......# +#############.#####.#.###.#.#.#.#####.#.#.#.###.#.#.#.#.#######.#.#####.#.#.###.#.#.#.#.#.#.###.###.#.#######.#.#####.#######.#.#.#.#######.# +#.............#...#.#.#...#.#.#...>.>.#.#.#.###.#.#.#...#.......#.....#.#.#.###.#.#.#.#.#...#...#...#.#...#...#.#...#.....#...#.#.#.#.....#.# +#.#############.#.#.#.#.###.#.#####v###.#.#.###.#.#.#####.###########.#.#.#.###.#.#.#.#.#####.###.###.#.#.#.###.#.#.#####.#.###.#.#.#.###.#.# +#.........#...#.#.#.#.#...#...#...#.#...#.#.###.#.#.#.....#...#####...#.#.#...#.#.#.#.#.....#...#...#...#.#...#.#.#.#...#.#...#.#.#.#...#.#.# +#########.#.#.#.#.#.#.###.#####.#.#.#.###.#.###.#.#.#.#####.#.#####.###.#.###.#.#.#.#.#####.###.###.#####.###.#.#.#.#.#.#.###.#.#.#.###.#.#.# +#.........#.#.#.#...#...#.#...#.#.#.#.#...#.#...#.#.#.....#.#.#.>.>.#...#.#...#.#.#.#.###...#...###.....#.....#.#.#...#.#.#...#.#...#...#...# +#.#########.#.#.#######.#.#.#.#.#.#.#.#.###.#.###.#.#####.#.#.#.#v###.###.#.###.#.#.#.###.###.#########.#######.#.#####.#.#.###.#####.####### +#.#.......#.#.#...#.....#...#...#.#.#...###.#.###.#.....#...#.#.#.###.....#...#.#...#...#.#...#...#...#.......#...#...#.#.#...#.#...#...#...# +#.#.#####.#.#.###.#.#############.#.#######.#.###.#####.#####.#.#.###########.#.#######.#.#.###.#.#.#.#######.#####.#.#.#.###.#.#.#.###.#.#.# +#.#.#.....#.#.###.#...#...#.....#.#.....###.#.###.#...#.#.....#.#.#.....#.....#.....#...#.#.###.#.#.#.###...#.......#.#.#...#...#.#...#...#.# +#.#.#.#####.#.###.###.#.#.#.###.#.#####.###.#.###.#.#.#.#.#####.#.#.###.#.#########.#.###.#.###.#.#.#.###.#.#########.#.###.#####.###.#####.# +#...#.#.....#.#...#...#.#.#...#.#.#...#...#...###.#.#...#.......#...#...#.>.>...#...#.#...#...#.#...#.>.>.#.#.....#...#...#.#.....###...#...# +#####.#.#####.#.###v###.#.###.#.#.#.#.###.#######.#.#################.#####v###.#.###.#.#####.#.#######v###.#.###.#.#####.#.#.#########.#.### +###...#.....#...###.>.#.#.....#...#.#...#.......#.#.###...###.........#.....#...#.#...#.....#.#.....###...#.#...#.#.....#...#.....#...#.#...# +###.#######.#######v#.#.###########.###.#######.#.#.###.#.###.#########.#####.###.#.#######.#.#####.#####.#.###.#.#####.#########.#.#.#.###.# +#...#...#...#.......#...#...........###.........#...#...#.....#...#...#.....#.....#.....#...#...#...#.....#.#...#.......#.......#...#.#.#...# +#.###.#.#.###.###########.###########################.#########.#.#.#.#####.###########.#.#####.#.###.#####.#.###########.#####.#####.#.#.### +#.#...#.#.###...###...###.#.................#.....#...#.....#...#...#.###...###...#...#...#####.#.###.....#.#.....#...#...#...#.......#...### +#.#.###.#.#####.###.#.###.#.###############.#.###.#.###.###.#.#######.###.#####.#.#.#.#########.#.#######.#.#####.#.#.#.###.#.############### +#.#.###...#...#.....#...#...#...............#.#...#.#...#...#.#.......#...#...#.#.#.#.#...###...#.....#...#.......#.#.#.....#.......#.......# +#.#.#######.#.#########.#####.###############.#.###.#.###.###.#.#######.###.#.#.#.#.#.#.#.###.#######.#.###########.#.#############.#.#####.# +#.#...#.....#.....#...#.....#.................#...#...#...#...#.....#...#...#...#.#.#...#...#.........#.....#...#...#.#...###.......#.#.....# +#.###.#.#########.#.#.#####.#####################.#####.###.#######.#.###.#######.#.#######.###############.#.#.#.###.#.#.###.#######.#.##### +#.#...#.....#...#.#.#.......###.....#...#.......#.#...#...#.#...#...#...#.#.......#.....#...###...#...###...#.#.#...#.#.#...#.........#.....# +#.#.#######.#.#.#.#.###########.###.#.#.#.#####.#.#.#.###.#.#.#.#.#####.#.#.###########.#.#####.#.#.#.###v###.#.###.#.#.###.###############.# +#...#...###...#.#...###.....#...###...#...#####...#.#.###...#.#.#.#...#...#.......#...#.#.#...#.#.#.#.#.>.>.#.#...#.#.#...#.#...#...#...#...# +#####.#.#######v#######.###.#.#####################.#.#######.#.#.#.#.###########.#.#.#.#.#.#.#.#.#.#.#.#v#.#.###.#.#.###.#.#.#.#v#.#.#.#.### +#...#.#.#...###.>.#...#...#.#.###...#####...###...#.#.#.......#...#.#.#...#.......#.#...#...#.#.#.#.#...#.#...#...#.#...#.#...#.>.#...#...### +#.#.#.#.#.#.###v#.#.#.###.#.#v###.#.#####.#.###.#.#.#.#.###########.#.#.#.#.#######.#########.#.#.#.#####.#####.###.###.#.#######v########### +#.#...#...#...#.#.#.#.#...#.>.>.#.#...#...#...#.#.#.#.#...........#.#.#.#.#.......#.........#.#.#.#.#.....#...#...#...#.#.#.....#...#...##### +#.###########.#.#.#.#.#.#####v#.#.###.#.#####.#.#.#.#.###########.#.#.#.#.#######v#########.#.#.#.#.#.#####.#.###.###.#.#.#.###.###.#.#.##### +#.......#...#.#.#...#.#.#.....#.#.#...#.....#.#.#.#.#.#...###...#.#.#.#.#.#.....>.>.#...#...#...#.#.#.......#...#.#...#.#.#...#.###...#.....# +#######.#.#.#.#.#####.#.#.#####.#.#.#######.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#####v#.#.#.#.#######.#.###########.#.#.###.#.###.#.###########.# +#.....#...#.#.#...###.#.#.....#...#...#...#.#.#.#.#.#.#.#.###.#.#.#.#.#.#...#.....#.#.#.#.......#...#...........#...#...#...#.#.............# +#.###.#####.#.###.###.#.#####.#######.#.#.#.#.#.#.#.#.#.#.###.#.#v#.#.#.#####.#####.#.#.#######.#####.###############.#####.#.############### +#...#.....#.#.#...#...#.#.....#...###.#.#.#.#...#.#.#.#.#.#...#.>.>.#...#...#.....#...#...#...#.#.....#.........#...#...#...#...#...........# +###.#####.#.#.#.###.###.#.#####.#.###.#.#.#.#####.#.#.#.#.#.#####v#######.#.#####.#######.#.#.#.#.#####.#######.#.#.###.#.#####.#.#########.# +#...#...#.#.#...###.....#.#.....#...#.#.#.#.#.....#.#...#.#.#.....#.....#.#.....#.......#...#...#.......#####...#.#.###.#.#.....#.#.........# +#.###.#.#.#.#############.#.#######.#.#.#.#.#.#####.#####.#.#.#####.###.#.#####.#######.#####################.###.#.###.#.#.#####.#.######### +#.....#.#.#.###.......###...#...#...#.#.#...#.....#.....#...#.......#...#.....#...#...#.#...#...#...#...#.....#...#...#...#.......#.........# +#######.#.#.###.#####.#######.#.#.###.#.#########.#####.#############.#######.###.#.#.#.#.#.#.#.#.#.#.#.#.#####.#####.#####################.# +#.......#.#.....#.....#.......#...###...###...#...#.....###...#...#...#...#...###.#.#...#.#...#.#.#...#.#...#...#...#.....#...###...........# +#.#######.#######.#####.###################.#.#.###.#######.#.#.#.#.###.#.#.#####.#.#####.#####.#.#####.###.#.###.#.#####.#.#.###.########### +#.......#.......#.....#...............#...#.#.#.....#...#...#...#...###.#.#.....#.#...###.#.....#...#...###...#...#.......#.#.#...#.........# +#######.#######.#####.###############.#.#.#.#.#######.#.#.#############.#.#####.#.###.###.#.#######.#.#########.###########.#.#.###.#######.# +#.......#.....#.#...#.#...#...#.......#.#.#.#...#.....#.#...........#...#.......#.#...#...#...#...#.#...#.....#.............#.#...#.#.......# +#.#######.###.#.#.#.#.#.#.#.#.#.#######.#.#.###.#.#####.###########.#.###########.#.###.#####.#.#.#.###.#.###.###############.###.#.#.####### +#.......#.#...#...#...#.#...#.#...#####.#.#.#...#.....#.......#.....#...#.......#.#...#.....#.#.#...#...#...#...#.............###...#...#...# +#######.#.#.###########.#####.###.#####.#.#.#.#######v#######.#.#######.#.#####.#.###.#####.#.#.#####.#####.###.#.#####################.#.#.# +#.......#.#.###.........#...#.....#.....#.#.#.#.....>.>.#...#.#...#.....#.#.....#.....#...#.#.#.....#.#...#.#...#.#...#.......#.....###...#.# +#.#######.#v###.#########.#.#######.#####.#.#.#.#####v#.#.#.#.###.#.#####.#.###########.#.#.#.#####.#.#.#.#.#.###v#.#.#.#####.#.###.#######.# +#.#.......#.>.#...........#.......#.....#.#.#.#.#...#.#.#.#.#.....#.......#...#...###...#.#.#.#.....#...#...#...>.>.#.#.#.....#...#.........# +#.#.#######v#.###################.#####.#.#.#.#.#.#.#.#.#.#.#################.#.#.###.###.#.#.#.#################v###.#.#.#######.########### +#...#...#...#...###.....#.........#.....#.#.#...#.#.#.#...#...#...#...........#.#.#...###.#.#.#.#...............#.#...#.#.#.....#...........# +#####.#.#.#####.###.###.#.#########.#####.#.#####.#.#.#######.#.#.#.###########.#.#.#####.#.#.#.#.#############.#.#.###.#.#.###.###########.# +#...#.#.#...#...#...#...#.........#.....#.#...#...#...#.....#...#.#.........#...#.#.....#.#.#.#.#...#.........#...#.....#.#.#...###...#...#.# +#.#.#.#.###.#.###.###.###########.#####.#.###.#.#######.###.#####.#########.#.###.#####.#.#.#.#.###.#.#######.###########.#.#.#####.#.#.#.#.# +#.#...#.....#...#...#.#...###...#.#...#.#.....#.........#...#.....#...#####.#...#.......#...#...###...#.......#...#.......#.#.#...#.#.#.#.#.# +#.#############.###.#.#.#.###.#.#v#.#.#.#################.###.#####.#.#####v###.#######################.#######.#.#.#######.#.#.#.#.#.#v#.#.# +#.............#...#.#.#.#...#.#.>.>.#...###...............###...#...#...#.>.>.#.#...###...###...###...#.....###.#.#.....#...#.#.#.#.#.>.#...# +#############.###.#.#.#.###.#.###v#########.###################.#.#####.#.#v#.#.#.#.###.#.###.#.###.#.#####.###.#.#####.#.###.#.#.#.###v##### +#.............###.#.#.#...#.#...#...###...#...#...#.......###...#.#.....#.#.#...#.#...#.#.#...#.#...#.......#...#...###...#...#.#.#.#...#...# +#.###############.#.#.###.#.###.###.###.#.###.#.#.#.#####.###.###.#.#####.#.#####.###.#.#.#.###.#.###########.#####.#######.###.#.#.#.###.#.# +#...............#.#.#.#...#.#...###...#.#.###...#...#...#...#.#...#.#...#.#...###.#...#.#.#...#.#.......###...#.....#...###.....#...#.....#.# +###############.#.#.#.#.###.#.#######.#.#.###########.#.###.#.#.###.#.#.#.###.###.#.###.#.###.#.#######.###.###.#####.#.###################.# +###.............#...#...###.#.#.......#.#.....#.......#.....#...###...#...###.#...#.....#...#.#.#.....#...#...#...#...#.#...#...#...###...#.# +###.#######################.#.#.#######.#####.#.#############################.#.###########.#.#.#.###.###.###.###.#.###.#.#.#.#.#.#.###.#.#.# +#...#...#.....#.......#...#...#.......#.#.....#.........###...#...###...#...#...###...#.....#.#.#...#.#...###.#...#.#...#.#.#.#.#.#.#...#.#.# +#.###.#.#.###.#.#####.#.#.###########.#.#.#############.###.#.#.#.###.#.#.#.#######.#.#v#####.#.###.#.#v#####.#.###.#.###.#.#.#.#.#.#v###.#.# +#...#.#.#.#...#.#.....#.#.....#.......#.#...#...........#...#.#.#.#...#.#.#...#...#.#.>.>.#...#.#...#.>.>.....#.....#.#...#.#.#...#.>.###...# +###.#.#.#.#.###.#v#####.#####.#.#######.###.#.###########.###.#.#.#.###.#.###.#.#.#.###v#.#.###.#.#####v#############.#.###.#.#######v####### +###...#...#.....#.>.#...#.....#.......#.#...#...........#.#...#.#.#...#.#.###.#.#.#.#...#...###...#.....#.....#...###.#...#...#.......###...# +#################v#.#.###.###########.#.#.#############.#.#.###.#.###.#.#.###.#.#.#.#.#############.#####.###.#.#.###.###.#####.#########.#.# +#.................#.#.#...###.......#...#.....#...###...#.#.###.#.#...#...###.#.#...#.....#.........#...#.###...#...#.#...#...#.......#...#.# +#.#################.#.#.#####.#####.#########.#.#.###.###.#.###.#.#.#########.#.#########.#.#########.#.#.#########.#.#.###.#.#######.#.###.# +#.#.........#.....#...#.#...#.#.....#...#.....#.#.#...#...#.#...#.#.....###...#...#.......#...#...#...#.#.#.........#...###.#.........#.#...# +#.#.#######.#.###.#####.#.#.#.#.#####.#.#.#####.#.#.###.###.#.###.#####.###.#####.#.#########.#.#.#.###.#.#.###############.###########.#.### +#.#.#.......#.#...###...#.#...#...#...#...###...#.#...#.#...#.#...#...#...#...#...#.........#.#.#.#.#...#.#...............#.........#...#...# +#.#.#.#######.#.#####.###.#######.#.#########.###.###.#.#.###.#.###.#.###.###.#.###########.#.#.#.#.#.###.###############.#########.#.#####.# +#...#.........#.....#.#...#.......#.........#...#.###.#.#.#...#...#.#...#...#.#.#...........#...#.#.#...#.#...............#.........#.#.....# +###################.#.#.###.###############.###.#.###v#.#.#.#####.#.###.###.#.#.#.###############.#.###.#.#.###############.#########.#.##### +#...#...#...........#...#...#...#...#...#...###.#...>.>.#...#...#.#...#.#...#...#.........###...#...#...#.#...............#.....#.....#.....# +#.#.#.#.#.###############.###.#.#.#.#.#.#v#####.#####v#######.#.#.###.#.#.###############.###.#.#####.###.###############.#####.#.#########.# +#.#...#.#...#...........#...#.#.#.#.#.#.>.>...#.#...#.........#.#.....#.#.#...#.........#.....#.....#.#...#.....#...#.....#####...#.........# +#.#####.###.#.#########.###.#.#.#.#.#.###v###.#.#.#.###########.#######.#.#.#.#.#######.###########.#.#.###.###.#.#.#.#############.######### +#.....#...#...#.....#...###...#.#.#.#.#...###...#.#.#.......#...###...#...#.#.#.......#.............#.#...#...#...#...#####.........#...#...# +#####.###.#####.###.#.#########.#.#.#.#.#########.#.#.#####.#.#####.#.#####.#.#######.###############.###.###.#############.#########.#.#.#.# +#####...#.#...#.###...###...###...#...#.......#...#...#...#...#...#.#.#...#.#.#.....#...........#...#.....###.............#...........#...#.# +#######.#.#.#.#.#########.#.#################.#.#######.#.#####.#.#.#.#.#.#.#.#.###.###########.#.#.#####################.#################.# +###...#.#.#.#.#.....#...#.#.#...###...###.....#.......#.#.#...#.#.#.#.#.#.#.#.#.#...#.......#...#.#.#.....#...............#.................# +###.#.#.#.#.#.#####.#.#.#.#.#.#.###.#.###.###########.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#####.#.###.#.#.###.#.###############.################# +#...#...#...#.......#.#.#.#.#.#...#.#.#...#.......###...#.#.#.#.#.#.#.#.#...#.#.#...#.....#.#.#...#.#.#...#...............#.#...............# +#.###################.#.#.#.#.###.#.#.#.###.#####.#######.#.#.#.#.#.#.#.#####.#.###.#####.#.#.#.###.#.#.#################.#.#.#############.# +#.......#...#.....###.#.#.#.#.#...#.#.#...#.....#...#.....#.#.#.#.#.#.#...#...#.#...#...#.#...#.#...#.#.#...#...........#.#...#.......#.....# +#######.#.#.#.###.###.#.#.#.#.#.###.#.###v#####.###.#.#####.#.#.#.#.#.###.#.###.#.###.#.#v#####.#.###.#.#.#.#.#########.#.#####.#####.#.##### +#.......#.#...#...#...#...#...#.#...#...>.>.#...#...#...###.#.#.#.#.#.#...#.#...#.#...#.>.>.###.#.#...#...#.#.........#.#.#...#.....#.#.....# +#.#######.#####v###.###########.#.#######v#.#.###.#####v###.#.#.#.#.#.#.###.#.###.#.#####v#.###.#.#.#######.#########.#.#.#.#.#####v#.#####.# +#.........#...#.>...#...#...###...#...#...#...#...#...>.>...#...#...#.#...#.#.###.#...#...#...#.#.#.......#.#...#.....#...#.#.#...>.#.#.....# +###########.#.#v#####.#.#.#.#######.#.#.#######.###.###v#############.###.#.#.###.###.#.#####.#.#.#######.#.#.#.#.#########.#.#.###v#.#.##### +#...........#.#.......#...#.....#...#.#.......#...#.#...###...#...###...#.#.#.#...#...#.....#.#.#.#...###.#.#.#.#.###.....#.#.#.#...#...#...# +#.###########.#################.#.###.#######.###.#.#.#####.#.#.#.#####.#.#.#.#.###.#######.#.#.#.#.#.###.#.#.#.#v###.###.#.#.#.#.#######.#.# +#.#.........#.#.....#.....#.....#...#...#.....###...#.....#.#.#.#.#####.#.#.#.#...#.#.......#.#.#.#.#...#.#.#.#.>.>.#...#.#.#.#.#.#...###.#.# +#.#.#######.#.#.###.#.###.#.#######.###.#.###############.#.#.#.#.#####.#.#.#.###.#.#.#######.#.#.#.###.#.#.#.###v#.###.#.#.#.#.#.#.#.###.#.# +#.#.#.....#.#...###.#.#...#.#...###.#...#.........#...###...#...#.....#.#.#...#...#.#.......#...#.#.#...#.#.#.###.#.#...#.#.#.#.#.#.#.....#.# +#.#.#.###.#.#######.#.#.###.#.#.###.#.###########.#.#.###############.#.#.#####.###.#######.#####.#.#.###.#.#.###.#.#.###.#.#.#.#.#.#######.# +#...#...#.#.#...###...#...#.#.#.....#...#...#...#.#.#.................#.#...###...#.#.......#...#.#.#...#.#.#.#...#...#...#.#.#.#.#.#.......# +#######.#.#.#.#.#########.#.#.#########.#.#.#.#.#.#.###################.###.#####.#.#.#######.#.#.#.###.#.#.#.#.#######.###.#.#.#.#.#.####### +###...#.#.#...#.........#...#...#.....#.#.#.#.#...#...................#...#.....#...#.........#.#...###...#...#.......#...#.#...#...#...#...# +###.#.#.#.#############.#######.#.###.#.#.#.#.#######################.###.#####.###############.#####################.###.#.###########.#.#.# +#...#...#...#...#.....#.###...#...###.#.#.#.#.#.....#.................###...#...#.............#.#...#...#####...#...#...#.#...#...#...#...#.# +#.#########.#.#.#.###.#.###.#.#######.#.#.#.#.#.###.#.#####################.#.###.###########.#.#.#.#.#.#####.#.#.#.###.#.###.#.#.#.#.#####.# +#.........#.#.#.#.###...#...#...###...#...#...#.#...#.........###...#...###...###.........###...#.#...#...#...#.#.#.#...#.#...#.#...#.......# +#########.#.#.#.#.#######.#####.###.###########.#.###########.###.#.#.#.#################.#######.#######.#.###.#.#.#.###.#.###.############# +#.........#...#.#.....#...#...#.....#...#...#...#...#...#...#.....#...#.......#.....#...#.......#.......#.#.###...#...###.#.###.............# +#.#############.#####.#.###.#.#######.#.#.#.#.#####.#.#.#.#.#################.#.###.#.#.#######.#######.#.#.#############.#.###############.# +#.............#.......#.....#.......#.#.#.#.#...#...#.#.#.#.#.................#...#...#.#.......###.....#.#.......#...###...#...#...........# +#############.#####################.#.#.#.#.###.#.###.#.#.#.#v###################.#####.#.#########v#####.#######.#.#.#######.#.#.########### +#.......#.....#...#...#...###.......#.#.#.#.#...#...#.#.#.#.>.>.....#...###...###.....#...###...#.>.>...#.........#.#.#...###.#.#...........# +#.#####.#.#####.#.#.#.#.#.###.#######.#.#.#.#.#####.#.#.#.#########.#.#.###.#.#######.#######.#.#.#####.###########.#.#.#.###.#.###########.# +#.....#.#...###.#.#.#...#...#.....#...#...#.#.....#.#.#.#.#...#.....#.#.#...#.#.....#.......#.#...#.....#...#.....#.#...#.#...#...#...#.....# +#####.#.###.###.#.#.#######.#####.#.#######.#####.#.#.#.#.#.#.#.#####.#.#.###.#.###.#######.#.#####.#####.#.#.###.#.#####.#.#####.#.#.#.##### +#.....#.....#...#.#.#.......#...#.#.......#.#...#.#.#.#.#.#.#.#.....#.#.#...#.#...#...#.....#.#.....#...#.#.#.#...#.#.....#.....#...#.#.....# +#.###########.###.#.#.#######.#.#v#######.#.#.#.#.#.#.#.#.#.#.#####.#.#.###.#.###.###.#.#####.#.#####.#.#.#.#.#.###.#.#########.#####.#####.# +#.#...#.....#...#.#.#.#.....#.#.>.>...#...#.#.#.#.#...#...#.#.......#.#.###.#.###...#.#...#...#.#...#.#...#.#.#.###.#.#.......#.....#.###...# +#.#.#.#.###.###.#.#.#.#.###.#.#######.#.###.#.#.#.#########.#########.#.###.#.#####.#.###v#.###.#.#.#.#####.#.#.###.#.#.#####.#####.#.###.### +#...#...#...###.#...#...###.#.#.......#.###...#.#.#.........#...#...#.#.#...#...#...#.#.>.>.#...#.#.#.#...#...#...#.#.#.#.....#...#.#.#...### +#########.#####.###########.#.#.#######.#######.#.#.#########.#.#.#.#.#.#.#####.#.###.#.#####.###.#.#.#.#.#######.#.#.#.#.#####.#.#.#.#.##### +#.........#.....#...###...#.#.#...#...#.......#.#.#...#.....#.#.#.#.#.#.#...###.#.###...#.....#...#.#.#.#.........#.#.#.#.#...#.#.#.#.#...### +#.#########.#####.#.###.#.#.#.###.#.#.#######.#.#.###.#.###.#.#.#.#.#.#.###.###.#.#######.#####.###.#.#.###########.#.#.#.#.#.#.#.#.#.###v### +#.........#.......#.....#.#.#.#...#.#.....#...#.#.###...###...#.#.#.#.#.#...#...#.......#.....#...#...#.#...#.....#.#.#.#.#.#.#.#.#.#.#.>.### +#########.###############.#.#.#.###.#####.#.###.#.#############.#.#.#.#.#.###.#########.#####.###.#####.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#v### +#.........#...#...#...#...#.#.#...#.....#.#...#.#.#.............#.#.#.#.#.###...#.....#.....#.#...#.....#.#.#.#...#.#.#.#.#.#.#.#.#.#.#.#.### +#.#########.#.#.#.#.#.#.###.#.###.#####.#.###.#.#.#.#############.#.#.#.#.#####.#.###.#####.#.#.###.#####.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.### +#...........#...#...#...###...###.......#.....#...#...............#...#...#####...###.......#...###.......#...#.....#...#...#...#...#...#...# +###########################################################################################################################################.# diff --git a/2023/23-A_Long_Walk/second.hs b/2023/23-A_Long_Walk/second.hs new file mode 100644 index 0000000..f065ea8 --- /dev/null +++ b/2023/23-A_Long_Walk/second.hs @@ -0,0 +1,148 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import qualified Data.Char as C +import Data.Either +import Data.Functor +import qualified Data.Heap as H +import qualified Data.List as L +import qualified Data.Map as M +import Data.Maybe +import qualified Data.Set as S +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = Just 154 + +data Direction = N | S | E | W deriving (Eq, Show) +data Tile = Floor | Wall | Slope Direction deriving (Eq, Show) +type Line = V.Vector Tile +type Input = V.Vector Line + +type Parser = Parsec Void String + +parseDirection :: Parser Direction +parseDirection = char '^' $> N + <|> char 'v' $> S + <|> char '>' $> E + <|> char '<' $> W + +parseTile :: Parser Tile +parseTile = char '#' $> Wall + <|> char '.' $> Floor + <|> Slope <$> parseDirection + +parseLine :: Parser Line +parseLine = do + line <- some parseTile <* eol + return $ V.generate (length line) (line !!) + +parseInput' :: Parser Input +parseInput' = do + line <- some parseLine <* eof + return $ V.generate (length line) (line !!) + +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' + +newtype Cost = Cost Int deriving (Eq, Num, Ord, Show) +newtype NodeId = NodeId Int deriving (Eq, Num, Ord, Show) +newtype X = X Int deriving (Eq, Num, Ord, Show) +newtype Y = Y Int deriving (Eq, Num, Ord, Show) +type Adjacencies = M.Map NodeId [(NodeId, Cost)] -- keys are nodeIds and values are a list of (NodeId, cost) +type Nodes = M.Map (X, Y) NodeId -- keys are (x, y) and values are nodeIds +type Visited = M.Map (X, Y) () + +compute :: Input -> Maybe Cost +compute input = longuestPath adjacencies (let Just (a:[]) = M.lookup 0 adjacencies in a) + where + longuestPath :: Adjacencies -> (NodeId, Cost) -> Maybe Cost + longuestPath adj (n, c) | n == 1 = Just $ c + 1 + | l' == [] = Nothing + | otherwise = Just $ c + maximum l' + where + Just l = M.lookup n adj + l' = catMaybes $ L.map (longuestPath adj') l + adj' = M.delete n $ M.map (L.filter (\(i, _) -> n /= i)) adj + (adjacencies, nodes, _) = explore 0 (M.fromList [(0, []), (1, [])]) (M.fromList [((startx, 0), 0), ((finishx, finishy), 1)]) (M.fromList [((startx, 0), ()), ((finishx, finishy), ())]) startx 1 S + explore :: NodeId -> Adjacencies -> Nodes -> Visited -> X -> Y -> Direction -> (Adjacencies, Nodes, Visited) + explore node adjacencies nodes visited x y d = L.foldl' explore' (adjacencies, nodes, visited) $ nextSteps x y d + where + explore' :: (Adjacencies, Nodes, Visited) -> (X, Y, Direction, Bool) -> (Adjacencies, Nodes, Visited) + explore' acc@(adjacencies, nodes, visited) (x, y, d, u) | isNothing destination = acc + | otherwise = case M.lookup (x', y') nodes of + Nothing -> explore node' adjacencies'' nodes' visited' x' y' d + Just id -> (adjacencies'', nodes', visited') + where + destination = let s = goDownAPath visited False x y 1 d in s + Just (visited', x', y', cost, u') = destination + adjacencies'' = M.adjust (\l -> (node', cost):l) node $ M.adjust (\l -> if u || u' then l else (node, cost):l) node' adjacencies' + nodes' = M.insert (x', y') node' nodes + (node', adjacencies') = case M.lookup (x', y') nodes of + Nothing -> let s = NodeId (M.size nodes) in (s, M.insert s [] adjacencies) + Just node' -> (node', adjacencies) + goDownAPath :: Visited -> Bool -> X -> Y -> Cost -> Direction -> Maybe (Visited, X, Y, Cost, Bool) -- returns the next intersection's coordinates and cost, and if it is unidirectional + goDownAPath visited u x y c d | M.member (x, y) nodes = Just (visited, x, y, c, u) -- we reached an already known intersection + | M.member (x, y) visited = Nothing -- this tile has already been visited + | isImpossibleSlope = Nothing + | ns == [] = Nothing -- we hit a deadend + | L.length ns > 1 = Just (visited', x, y, c, u'') -- we hit a crossroads + | otherwise = goDownAPath visited' u'' x' y' (c+1) d' + where + (x', y', d', u') = head ns + u'' = u || u' + ns = nextSteps x y d + visited' = M.insert (x, y) () visited + isImpossibleSlope = case getTile (x, y) of + Slope s -> s /= d + otherwise -> False + getTile :: (X, Y) -> Tile + getTile (X x, Y y) = input V.! y V.! x + nextSteps :: X -> Y -> Direction -> [(X, Y, Direction, Bool)] -- get the list of possible next steps at a point, given where we came from + nextSteps x y d = L.map augmentWithUnidirectionality $ L.filter possible [(x-1, y, W), (x+1, y, E), (x, y-1, N), (x, y+1, S)] + where + augmentWithUnidirectionality :: (X, Y, Direction) -> (X, Y, Direction, Bool) + augmentWithUnidirectionality (x, y, d) = (x, y, d, isSlope $ getTile (x, y)) + isSlope :: Tile -> Bool + --isSlope (Slope _) = True + isSlope _ = False + possible :: (X, Y, Direction) -> Bool + possible (x', y', d') | t == Wall = False + | d == opposite d' = False -- no going back + -- | t == Floor = True + | otherwise = True -- o == d' -- our direction must match the slope <- NO, this prevents us from properly finding intersections + where + t = getTile (x', y') + Slope o = t + Just start = V.findIndex (== Floor) $ input V.! 0 + startx = X start + Just finish = V.findIndex (== Floor) $ input V.! finishyy + finishx = X finish + finishyy = V.length input - 1 + finishy = Y finishyy + xydToxy :: (a, b, c) -> (a, b) + xydToxy (x, y, _) = (x, y) + opposite :: Direction -> Direction + opposite N = S + opposite S = N + opposite E = W + opposite W = E + +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 |