- commit
- a59a12207c481260b0a184f37ec8fd4077114217
- parent
- 74af053a50c6371925e64936aca414ee72a46e3a
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2023-12-18 08:25
2023-12-17
Diffstat
| A | 2023/17/input.txt | 141 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/17/solution.rs | 92 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/17/test.txt | 13 | +++++++++++++ |
3 files changed, 246 insertions, 0 deletions
diff --git a/2023/17/input.txt b/2023/17/input.txt
@@ -0,0 +1,141 @@ -1 1 232114215134442123523324142646654624561442465233136447364262354735336647656264256722136447555363236142564144512552612662311121123132331125334 -1 2 132353343453554441525165425422234546621144622531374477574432752334323641341612264213747336436132332333646464556624332234522432345545121553244 -1 3 311513222342514213245651641632225132646561334436253531436157272664217657214743625426451635726346223326434465435424112364344554522453241453123 -1 4 152511143351441224455664566346262265542345431144571651522623467536477375734551121144253312533645636343441352626414334312241135123521421132522 -1 5 554223521251423345611445354356624242465423673323421452545716336261471543525317177673647256513116647355646114653623241326341324221122543215332 -1 6 344532522551413252122211232253442124361177736254751451722414312665774443533753636446371225327542166514642141666355421664521163451511212322213 -1 7 253322355141114242611463166366253653655311556642564554434337433167435717752653152725733615221122646246226722162431522253324212131422535414231 -1 8 455332252412233344422264156132345542441171745311322172247425616616246646336612461323113176572343141454165155555241665331135621262354534211335 -1 9 442534524125525365153443612166453652733535246632247616554665424251753172373755431161552721554564236224417175725536455653624155652414135441142 -1 10 334522223223111563356432245236445742776512464516425663123153714335757114521554154135276211441257454645475673377113152614322666366551534114152 -1 11 311341341425452252136244123235223134147111474546322722653424443361775256636433213745337456466451762142663431265423214322232341524516535221235 -1 12 235534312422416266615621225412127633643642274414427361247737877354653628277475274765752217274341412553742621732272615436562426465332534244522 -1 13 535255423535315215325413313272714152447325325441621621338378526326244765867374568827238655372577435521746323447473753156415431526424561251434 -1 14 241121225414113263563622144216116112716757726443342184876745558724747624827365776537353884756373347112545334552461115215524523532465516542352 -1 15 444512443513662655324263122667427273254524126723256545577868763843484772526455232647757727474777672265467467547554215413421356544546154145324 -1 16 331142411442633344613444777112626224323224257156887335372527676887863828467583584274264577782545512563125366322425376356555665326121612523532 -1 17 541353432643144141545266151554537523417514377582546664626465837336823824582372327642566642376322442542143215366236747751451412325335453653542 -1 18 415253632162316346564455116772141224617312463235225683733635483773352657375853736774343353528644734675567615514542322451451234566312224622355 -1 19 222523332453412614516332762715465445246524727377643885255743547236674442283534835846878434432587647247161165234364132332634514434442411643331 -1 20 341265413445664264162746444722131124511322628335678623885635642664343683246443743737867582788442533625766427622346562372176155216541532214355 -1 21 332214416614166415212346412736134734175255465472342267835474533725738227858726862887228324876785422242237153314621554534235743343664444124443 -1 22 212533225221125664735526634223656326876268354482748287646458367335432328653534637477543477678532824722682556365477433514256754442411436614155 -1 23 232145135115324262773674351417454646884464682467857865263327667876538684228385465433664324472468875327324884171755141144642626313326664553211 -1 24 356614166341141375156655576664534478738524886286636362262833338859843668597453854233325777574354532886477236472453431223221537766116551334454 -1 25 651142115344413443111347657123673864763757342852353542785659483748593654955658447568556362653886256748536243368626333157364672176235223626141 -1 26 544445356315341417542127473575426237575725447467546853388755455585444963587859789689564587772655226666536273377773471567721725164262411112412 -1 27 453254244215261712547236766116753426636746788252466683967939694644584763455696669955733339678558773474477236853721623445717366267145352411362 -1 28 262253644211512663151255735278853384254342423788489463974637683577935843888766787783683869388883277263526622684632367267117755121745431656354 -1 29 413611223151271656733156153128767753832837483874436353556893557453354773996978395448853694648388854254554363478244332715766115346474353631633 -1 30 524616126561562645216642351722424224355488477377567448373555998699738635586475759747649665894746943267882344625346377567556121764737132245354 -1 31 651444625255223537626332714587446374567537425693868593779345566957385643777899675777395446374385732844873763245342467653332136424371324452453 -1 32 141131533211235566674625652562727587736823696797394785339478389886938878547476563965469848443758445582747466672425363361232544415663721343623 -1 33 245154451613161431121657246436376684858374397638456595738478836393943673696797354887494479435794674497877222466345427276471644652653135426133 -1 34 126342515765226112416262447635266854643237586773473888697757978945696534347743894746497754488953689474564784268235236764653471373252413252622 -1 35 424552544177555435623444774458572264857835775748698359387579773443753968598433986686756436969957743687736583377248655527473414412271655344613 -1 36 332436127575225637571142386846675865476843449833889834788976675894468669749848499645357988935437998388693842447424422252455725352561327744533 -1 37 114151666534127254621246385855825728556787944899484555595749666854557894485898986999745499689784987836537763355767568572265714234243433353313 -1 38 365141426325435667357564467327528635686598784549656398896457878696744779497668495844695334964365679569454964278775527286452144517367612662221 -1 39 534353526627122355714626472342682727898778749899399735445996454669998547854485588946568584756638947499584784744552655248763425426553322672644 -1 40 315153636631212471456835248373455793465389858667694848699794464598587578997985565596948779769994497966468558585248834266448614566654157515434 -1 41 161463265154534313225875878766848784344335446973837877864565776988678556977986976846944849693498857583587487743786348276534515644267714535451 -1 42 434673461644175351268237638583258783337898474753377668999877456448745946858574875785596775698988897964593963758722838378585533275133526347341 -1 43 535136473457125116753477252624829598833367943875597786845795687969746467559658468489966575788988338588438994989835868642256357521547511236632 -1 44 655276434744673453323582688853667474743633585957574996589479975558856456554876496948945569465899936875498655478984746485833335576222134713311 -1 45 155555761432367266742748267465396743775463577884544664966958558785566746789764875986976959489597397468797994647632877566477466563473346157351 -1 46 136435372337345327434352273653585344739954875948678667786596476895664449954744785668467976794794873977877387583946686624527576326622614176322 -1 47 136263422671565755273852437535378673346837769449888895795886745984778767696595684644687559864868499687759737537793855254275265461644257414233 -1 48 362535747124322723446348758423773795746365474987855697559965968686985866779585945789774599967549696777694836593456565273857855271635362733514 -1 49 167375651264425365563623566287753345473648795679957899585996794587777688795885589458985566665497864749539633574494586424785575561225775434466 -1 50 423173553211363354535628532237695559543343884645546766469759458696578567995965879999545645868755846676965875387654344537733488638676531641637 -1 51 442422334312135387854436486555346686496766857545765548646688888589895965595569588558546769755864964669459988759353774335364243886564617611737 -1 52 546567452426716822725532643589689966883537578648895554467765576598697878757998775787656846975876955955463547976558867856473268343213645675227 -1 53 134625134741646833652236355837436443655649879589479497499786668556995996988869896777888846475885549579494746795968456868534826462545475565617 -1 54 741436517171555366485478568666488358896675958585586859885569768997697759586985775995897678474776887666878854658945495783324286282856533231716 -1 55 235532366541187424242686449395796994498979589545746587757988966765585595557988859585569594487468778894878375533787759588723337222673165711457 -1 56 547376272663658764254882544766595694665449997887799495869887987575889759678685565666869996566496555475789696939569589374685342732271333275525 -1 57 412512554117842533847438869646334879966594994985789855979966985869589897768757775699986567698998967545796968654789688647248678563886174416356 -1 58 734143646331326678533663398569636676437674878947685778697679877567985966677799667669786898565965997755584544748738735565346867885667575173421 -1 59 746727774224332222878858359748567676375885446958899779956797558777965996955798986589869675589956999794487665394668757586787656322887317527223 -1 60 544743425272585285282323543634783659899476677886546676759678688866857776687858898988765795996549997684888847856378375885254465326248663332745 -1 61 447127671422557743372355856339955648865769996496769866588658565668767787876885776896589978659744788597665676443496666442684774642237653263235 -1 62 773776126122763255756273679798994753496794854545879876897569675796769679679896677959585589757779959499876564675657866966586684778485454157225 -1 63 327711316563666333485734337387866944794876775848466979996876897868787989766696667995967567857776988556775984957649733447236727442563646166514 -1 64 417247447624752776323628873994549583675665787948686895997678557978797697766669979876658885955679795655654586836599888888882382645772612526457 -1 65 434253664256846856472248954887846475957444554684888767798779868788888977977676967796976875957584985888945999333969778349622324672486572242763 -1 66 117324622446856276627886686544334799479875494496668966587559866788798788778867886995869959668995475867995454445445897954542878875648563313113 -1 67 141744627622372558545485849386979887695747955647598765658976789678788786998669696687859796955576976679784945855963635839227726476384426454261 -1 68 211757643543436326784323786675336935886664488457876897988677998796689878977997798996578678687577559784787746574858953667777423852826312336367 -1 69 521367572764745857828844335636487496665654689597975879897959976689869699779766889786785558798557847497844944864475396634722488377683334412743 -1 70 141754515753876287544524937695973878566578659745555599586696996879696896697896967666998877596557995549774965558678377679466884536358764321212 -1 71 244572763668545874422643454578683539998665998866559599556869968799687877896997777786665655777969747775774777734853745985753668334637745127437 -1 72 662657632555547862335264765563634479748577579486995675665997677669797988988767989988756695956579669546596944347856868495888568478328224326662 -1 73 762745526484568277627746837445664649944757755475756997569796797978699776766869876987555957866686688855579896463988665967564544258746762561337 -1 74 225332657673855562728527337988956585688786889696997977555757767977767896677997776697775878598768748564487899749379443673573823534277512453477 -1 75 724146351686352633672738599455869668766657664468795859575976797677977797987886887786988665685895659875487558575395687378223782266755221746233 -1 76 141165441278633584664333764756947397498976947977987959578959699698666776967989788995555567867886644698456546576575439835284648388364216515266 -1 77 731772242568625624327669384456859337877866745784755665659677887686677866667677969777766775997956869674495985955665546493437824385243667227314 -1 78 272375271474678483524777887336868948884967566698889587656768999877699877769776896968855869695665475978969477666475895944742376467254463331455 -1 79 446313773645363222263525548345877458597858887494696966678568567866999879987786776896799576997777956854566784765788967894665782588652145667574 -1 80 734523111135758438328385369345358486544477996847567975676596896767998686776987798976585995775984866449548747656563346546568827684385672355474 -1 81 421655123575374844473267853954973469486959486666667979887586986979678987998897896568796665687747455756478843376469375996343288343622431175416 -1 82 466655734254554244272276438955896564899897989585568776856567758577966967686988978669858599587988845868794546648489768633287337278576626721666 -1 83 465641251328874535465756985344746999778458897974668978887666985665677677977888569777967875967856996958576986596945994384688576257838534755414 -1 84 137437435672643273522636585863359693969787574464887667998688677955668697968768598759765787857775874777579494935354645737485837683832467412745 -1 85 467215215261668482656328984483637676687698765496548897885577775976797986679788568559877589657485696984697845643847945382254473782841331366252 -1 86 376452342364467444462267898664599379789669766687499958978698959675857785688998857688668798584984894765666986659555967376886535232655272623216 -1 87 116162221324347345862748666697685555697686596556644576667958656776877889878687596879565665848685788878987384487894579464245833455544751462242 -1 88 442647426464268783254875347855358759585969444949958776858686698795766775889777968679986895555775694747657377668553653385866283428825657163147 -1 89 712314366423368238653866358349574733555579849645986858698687579687797587659679759995655589555884586494953763674534334884256335587443637352621 -1 90 735512575767765332454528539388733883947658996496666894496956769899698976898797996885876558659967574778753389937573387844728454358745355342651 -1 91 336635114224453353382357263365386366449356778847868485947797866979869965569995987886566744485969889596738494689756486856663373874554345672232 -1 92 262317422441623686744233746998679484736379784454896887748775986665868765677896988887589787847547556647784995549846665825722557556131312257645 -1 93 137366356147417622548635547878745944586557496746988847948559875597789678987977578769596866964785584479983647586487573644736538677173753634472 -1 94 554131656567127282263347775267987946473837897868464559545887686567765685886598855986466969975498957655765754648857825785523256687275734641142 -1 95 137543676324755375446434454457568396564974959498565577669684446689955596966869564764884667545989564846985584555485645486253588647475263513362 -1 96 522411477743563843627238678349599464876554857997999776848956957785466656857869689546689574894887977684344739467395648348824726723134475677515 -1 97 225452726126366432566644284435754578593865834995989479796675864594575756667846959946776975988554465376877485769598352743852885844431134244461 -1 98 212437746623216424384658288263587793943943888544798645678758966975945757996478749446975547444676473937779743685877253357567785566463753217715 -1 99 463576467762116536684356566752587563574374753566656954557669979457878856499889757997657584984967576363987564344782383468347538517142146754755 -1 100 336514165253263153353732463342558735349854594754648597474998487844666668594574695497674947875464457754696436686562667638656253273527161543634 -1 101 652614626141743557756462473383726533979786883367958958885744469958665944666649945597554996878465637459736648693776236322525245674436462533324 -1 102 243412753463135514473852758728847965947699666775848755894879455975985758797664784975688695557688583534847447385652247583747545526113351511355 -1 103 242562127556576374435464275265366287344639364537635785945779679978996599856544977675768895537383969663474698333827757846262765553664213711555 -1 104 532451661241561651683288432538432778583967478546934578774448945458466898685954687947846796347995549348799789828825286545862854673357351314151 -1 105 414161533652566333637877332243328356584474547435339389858647865475775456954667466944884869666757683465736986877455673646862771133131361211623 -1 106 334353447175436274731573844236473744498366493796554835454886945849887979658845548554896638766866434756738895864453666526835663332127723531266 -1 107 312133255245232134423357654764355235599677585938687863835553789444958969868986445579974734774883573756533424736632586378627754414216536445625 -1 108 113354547467163532716726674672252675456647679478699573358688343589587796955578966579636478453777566993778646755678677354276772172725662264414 -1 109 456341561142665646146476565562546573547845488755575387498646348785445837894998884987897335395349693366385482576334374886154722335746122243514 -1 110 635244355623477551324214782434672573663255684686635659964733559653655347499364657493566385373478953376647486363622754234255736546124365121326 -1 111 245626611544522437235126435776242886482685895868466433638483499949487493667677335373986535737447753668233434638742274853442633737137515433665 -1 112 664612644472545432277545452584824856254456454787849984853966373944548979365854754375744968799585337976733348376252574225414661562241111535456 -1 113 364242511424142626266153765784663485267764423644853398438949375467854476459478486365545469835969592484547542744558237613234763113233641546345 -1 114 133436361551452155314761255484432327885362722263336887877783664554998449886875936796336497698456766758757825248583664617764771666666633523111 -1 115 141321333416355755442252646228555443626727565574566677798787558574369897548673884859983784567388226648437575445527334767467622137743442316643 -1 116 462316533244324422754265277768242256572523425332643676485459476755765384987757585936886554538487827262387265662386152154363635441753644253621 -1 117 325455131534256162262463267236647582523458568667673265837543636338765984433556954365483647778425858842343765276654722121152144554143415363143 -1 118 116116443325535354643536672152578224376335324564572446488559495364968977774973869976458837244426572685766663822421344365265664151136554236245 -1 119 251126214423112635277673522545426364667624355228437457737599769939965587898495537567835757552636462724436842728517714517256615714535424145134 -1 120 154255656666213216223644155167322655244445777347484737523825764868585479479438668784584526444764637783282476451262763126372357551644513445154 -1 121 434322344622225143117263247361534717858488558282634627773644634464447255773533524284445238446223433857665823175634175643361622416146424634144 -1 122 424613135346234115376532727431142253776387768233268532242632682553244585748782543745387627545688677337563827341745416251617111656563655163454 -1 123 522256645552336352524573443534141616637676253565378374538283684563325327862632848624846688357644457437462452474766546722374121326341311325512 -1 124 453415661252523516527113314337627626452266368455754777265375836744435367275652545425457555736283637546526344216713561554363363453355334166113 -1 125 314336546616665564622735151154543544346116352548858776373574535286484227246442785453345747745564673354244464734515354641752324653141224264414 -1 126 552331532614411422316562437445625675747636583526262248647583488368276546777332328588584633755254634775453562656775134743334362442564151514124 -1 127 352255334466342356241317432711661753636251665333645246426284853324577646526686438278323336763327641264655535777467174351514515565634346653324 -1 128 314211534514636116161452664324177655614153554425254374627653754534657358435845766626472332662383317475653241336721676246661444561545445434521 -1 129 454255125352534334245346661711737412435733557547462763666828486274357538238673283325832458736855766145471722172625526221124121621532134435452 -1 130 224233334263242135232211524725122721244216716646663385458346862672248484525348357567252333553251536146251723437127347263643443626136252435323 -1 131 134222332521316264311222446665676576652442377312671232648345755373658752554877235782342647521315227511346216371643425516351313224133523325224 -1 132 353432453543322465165343111663574537373723331776511363424448562884478685374256343655172767472662176625351434472632452132363616233514515334325 -1 133 354212551441142352134265256552545263111156117575344324162515733146646478837257527473427467431116623544531365533745165363413546213146153233325 -1 134 424322142512536425442664245254166213326217611457111626543772775544235655255631636754637743164713743675275647146332525546366553435155431441212 -1 135 514341213443464241222414313235326253316354225516517571445157244417275166626736242556342324426133472314256453446515343412661115343122112223513 -1 136 335421314222145355144632355242551624363724167461155131121264411544157151265263646372655225524272465436365333211416211326654554341555344243125 -1 137 431233252115111553434232552654614251474434162264752742343427245172461261416746751474615316657517566127325126316515536445433511535243531351111 -1 138 242223323135514344241524121653433342515663646377215451624265737151376777171115657471741436242261561374762361251632316366665523421551522143125 -1 139 512513114344114232624361244253666213154235611355626363677225161776244223147316621172457725675736544246536611634256244656364633452413553143555 -1 140 254331131114233234151252345555542323211116335462416753521722423662766714435445311674535423122137136664232455623666331552531113334222313112215 -1 141 135342322424251334442555152253524442642225366151172571462613466745143145315674172762345744772144764442336344344532211243333543112344122315542
diff --git a/2023/17/solution.rs b/2023/17/solution.rs
@@ -0,0 +1,92 @@
-1 1 use std::collections::HashMap;
-1 2 use std::collections::VecDeque;
-1 3
-1 4 #[path = "../lib.rs"]
-1 5 mod lib;
-1 6
-1 7 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
-1 8 enum Dir {
-1 9 Left,
-1 10 Right,
-1 11 Up,
-1 12 Down,
-1 13 }
-1 14
-1 15 impl Dir {
-1 16 fn inverse(&self) -> Self {
-1 17 return match self {
-1 18 Dir::Left => Dir::Right,
-1 19 Dir::Right => Dir::Left,
-1 20 Dir::Up => Dir::Down,
-1 21 Dir::Down => Dir::Up,
-1 22 };
-1 23 }
-1 24
-1 25 fn apply(&self, x: usize, y: usize, n: usize) -> Option<(usize, usize)> {
-1 26 return match self {
-1 27 Dir::Left => if x > 0 { Some((x - 1, y)) } else { None }
-1 28 Dir::Right => if x + 1 < n { Some((x + 1, y)) } else { None }
-1 29 Dir::Up => if y > 0 { Some((x, y - 1)) } else { None }
-1 30 Dir::Down => if y + 1 < n { Some((x, y + 1)) } else { None }
-1 31 };
-1 32 }
-1 33
-1 34 fn iter() -> [Self; 4] {
-1 35 return [Dir::Left, Dir::Right, Dir::Up, Dir::Down];
-1 36 }
-1 37 }
-1 38
-1 39 fn parse_input() -> Vec<Vec<u32>> {
-1 40 return lib::iter_input()
-1 41 .map(|line| {
-1 42 return line.chars().map(|c| c.to_digit(10).unwrap()).collect();
-1 43 })
-1 44 .collect();
-1 45 }
-1 46
-1 47 fn find_path(map: &Vec<Vec<u32>>, min_steps: usize, max_steps: usize) -> u32 {
-1 48 assert!(map.len() == map[0].len());
-1 49 let n = map.len();
-1 50
-1 51 let mut queue = VecDeque::new();
-1 52 let mut min = HashMap::new();
-1 53 let mut result = u32::MAX;
-1 54
-1 55 min.insert((0, 0, Dir::Right, 1), 0);
-1 56 queue.push_back((0, 0, Dir::Right, 1));
-1 57
-1 58 min.insert((0, 0, Dir::Down, 1), 0);
-1 59 queue.push_back((0, 0, Dir::Down, 1));
-1 60
-1 61 while let Some((y, x, dir, steps)) = queue.pop_front() {
-1 62 let v = *min.get(&(y, x, dir, steps)).unwrap_or(&u32::MAX);
-1 63 if (x, y) == (n - 1, n - 1) && steps >= min_steps {
-1 64 result = result.min(v);
-1 65 }
-1 66 for ndir in Dir::iter() {
-1 67 if (ndir == dir && steps >= max_steps)
-1 68 || ndir == dir.inverse()
-1 69 || (ndir != dir && steps < min_steps)
-1 70 {
-1 71 continue;
-1 72 }
-1 73 if let Some((nx, ny)) = ndir.apply(x, y, n) {
-1 74 let s = if ndir == dir { steps + 1 } else { 1 };
-1 75 let key = (ny, nx, ndir, s);
-1 76 if v + map[ny][nx] < *min.get(&key).unwrap_or(&u32::MAX) {
-1 77 min.insert(key, v + map[ny][nx]);
-1 78 queue.push_back(key);
-1 79 }
-1 80 }
-1 81 }
-1 82 }
-1 83
-1 84 return result;
-1 85 }
-1 86
-1 87 fn main() {
-1 88 let map = parse_input();
-1 89
-1 90 println!("part1: {}", find_path(&map, 1, 3));
-1 91 println!("part2: {}", find_path(&map, 4, 10));
-1 92 }
diff --git a/2023/17/test.txt b/2023/17/test.txt
@@ -0,0 +1,13 @@ -1 1 2413432311323 -1 2 3215453535623 -1 3 3255245654254 -1 4 3446585845452 -1 5 4546657867536 -1 6 1438598798454 -1 7 4457876987766 -1 8 3637877979653 -1 9 4654967986887 -1 10 4564679986453 -1 11 1224686865563 -1 12 2546548887735 -1 13 4322674655533