From 8f3312a9da654303ed516e6ef92f86e2a8f5d57c Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sun, 17 Dec 2023 21:13:44 -0600 Subject: feat(wip): impl day 17 --- input/day_17.txt | 141 ++++++++++++++++++++++++++++++++++++ src/day_17.rs | 213 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 1 + 3 files changed, 355 insertions(+) create mode 100644 input/day_17.txt create mode 100644 src/day_17.rs diff --git a/input/day_17.txt b/input/day_17.txt new file mode 100644 index 0000000..17b462f --- /dev/null +++ b/input/day_17.txt @@ -0,0 +1,141 @@ +211332313114143133434324222211434511424134345413413656654231245423216434424452613141163242122214533442323255355354312412122214412112342123223 +212132234434344413224223425412235542511125134445554136543213263136623362163641265326312152424545214412311153541215242114423212142423234121313 +312213432321414114421421534422141235341514243544323331644633255352613264125144313663652436641115123244235341524131322551432111124121424141133 +232222342122131443143122115235512315453225332325351441254326156322532114434164152223211446321335162131511325552313415212433132411331332122332 +113212423223324413243152325443115151441344255546152124344662543645561546222266536335441232222652425143155324525433513315532224141442323423121 +112334244244442112411222555352454335211645524122125562555564534262244513663352151141455236153423255541343251414453144411223323431231442341231 +211212144144434341152224542414152324326641133515233625561222335224356463654426454463254664642545256214344443142131224212125554132341141144144 +221341314343422251412124455131125552126553342622354121224134632245164113141552516435463143332561413133462411321144444244312433312432322243131 +142134341333232124411331233515335415452163655412565353415453544154777441333277244422232446416552553421463633325552253515332214211433221134244 +441214311113114212211151531552136345224151365616345531236123154523323616716752612311524421511153244142451463323413314145314213454412322143332 +432444111121253325244312131241314423351553632213114622432363763664345735276532632127273535426265424656214664266654312515222453142231132431343 +233112421241542144442113435346662415641434434562626377171132753213451327412273627141523635411126631356164566665525344423225512534112412144412 +433432334121145441154533523616515255264644563432551332247677636754327665216315577344574721265712253554134616315314133411111422321512144113441 +314114323245433431244251234543225626141325622671777141457146735424321712243644137223742153357216424625441463452536131253535353112255411133343 +311442141533322215234332265154434123514225225472761542375513313731143766331115151356641465313514212331663135542126324363324544344544331213413 +131243214511522132151511144563515231624125535645123671531153562272734175551673374553515771754766777222311314232454161423322251345243241443413 +331123223252513355555431554234466456434442576374713435526637414333167417466143244521155327552343452577231446222362145141223434121215121424333 +132312313222454122553462635415641213423343153727254734432145663763217324551522165642233533613563415561726121615246462633663454323452322424323 +133322424412251244415336533551356332667554645174321174652732445524474411175331221355122161531467211366521535321254465342641421225354354534231 +212232511443425212345342543342165545234715576626246314674172575674857886836524578542244661724711367116457562243532124161113221315242511553433 +344231514234451222352444443552235524753634577123756144627654647232773832586435687546552415421131251323333243255146623465632361241534212214242 +142222254414133416325152256524135327661173154155545677388847864642266578532566572263575461755365513265373416264535316432445325221552251115442 +132523421524511133123114416651231215577376432432651585487554247274338254474464533666383648562445513461776237261133242612646141422315451555454 +441123142415354333566254365632471372141131473331637876366557264368753424225828443867276435324744617336654242464274465452324433432541235354455 +221521424242551314511161463112521536645311257478846428638457245555845373274225588644747458626558151412757771652321434566144554154121115421152 +434452234315222616636216462331421513336424374537758472278483363246774344855425266877468546753653577716777517423764124564311443541423252352314 +242511412343332661115345561772451643246425656255533536857268763866272828373525822682657735223832864553456671743171511536532311534513133431312 +441545524532234144633614644336433332756447378746546256664235782424776857765742554873355455737326346726233143711453673221552616211255411224312 +354242151356131155561635345473355423233215725854224633338635567782433886623446584843573752737224883345467717433551242316211126613143454241511 +541123221143356154153341174555541433621765868546453876683325785775844845473468756224526833545435637677427444427572744275636614551112134541234 +344311515263344524635245465645434451217456738524425828785483434653736365635687365542372444784386782574878675462274616366643366442613133352354 +445421445234142442553627731742425626753827427282567427528769668745938688735345674364958783547248364565354431547576325566446223135136355421535 +122312452242664256646112565112711517724722245847645637355343745976485536858889989775656372827583453642877746433122647137312623441313324445224 +324334331513132244123254453315772253344836666558677257345737784563954833337973775746795594688624376786762672276535153233332255455414315333411 +135542114441512656435616624445147424624547355673264898936596433385347538533769477478695957433778736527723422245371426572763635156322346453522 +534243423562463252671724515737157622582528456567299883835338463363995997953643474959979833788966675254558756446442676271253236216665316423131 +531423444141444263134215271424254686348556564337497938569448546433478436564859766854594873839442523222385386727127323153423423354131322325422 +515332652645656425617756433311774875866268646685343493436554958553783433583833958867984673765575976728366622438434374542561423121645155154545 +545543215161556142534525634241467742484583464798384678473453596746987496597648378434593876868687752826757478684444721254315774342156315535431 +451544512612143256652661512344656685846282553765398535666898949378835354867349834789444775454843584484532285782344174376721546453532143515524 +242156552653516547611722173154876643766723737595676975959935467365998595579995487686469674776336444988753772237565134444444561535661522315435 +411245134221524116714364153382537847858833357365657888483939545668597755945846956648634564748936386447785624225477363714665425334361621555611 +314334223432435165446675546343767854577859794746477547959779468685859988499846975886843338574568995549374873667234574233647355326644552625125 +114513141234531655163417626487264653528586669587984585949844598786857874464868599475489458656944767648535767344685566431352657141321465653364 +453364611154661776225354253876588726565654994744654473748859547797886579774644744858664598535484539639858865756883488661534623562632524152441 +143253266163424146757425678826254743247938997348778836447548986659587574795588855664455458946848895838739646745273433171174237173326435561642 +113225142651112261536554162778244336456976746585763697778795469644978884775885665755797495493564756338465747568523666536672141317151421524214 +553431145225572232716126542322622445678588697844376678496787495964646664955989467995474669686976434936389465257586886343555513561131546126526 +341642624521274673121172534774276563483969699885779496455886467468485985799699745569888854984437697734897546755543234667133325543216233531415 +536141624215613232411751545442524323367367643349589674674449994867746486568556497977796476989789744744554464677233278834514735326572623155121 +212651352426232653264438638266634744973735696959596759684865474598779558876989788867586498685596635458676785647853244667235472755623214413321 +526662242466551127435328462588363539973397784939765966789976765457868898797775458874946789744699757536399687788263678773173145333274343121116 +633343243467257163732724375324864787964953984454498445666685669955675789585777898967786875445688784649568986557857854523463346617726366351133 +542652124312251655513163777233842577993936653469664665555695857556557998769598967755487779974697958697457694963773473332252672163173135632634 +633134331122157164734323883758448665464395339974799445576867575799755669779657759876989554599559547495498937586763678486857716461535623451362 +515452611234571533646458756625365433964555839649697648976867879789885768567658768798768745475779857656688993573535258846262554342441314364315 +443621531343625514426457775688574475956777849769579766894675678586896956668699885756555579878944475653599574979664488744444556163142144243552 +666355246374427573413886675672524783596546869668647658466898979865675789755975895767878754598757944933673848664752833588881636247122313116646 +635322552252446173675546426374859488848859654756967466997758578779967557656957999976866887768559498487858633733762533878445363351343613512621 +116645455311151516113436432535464869644747599688469698986679555965699956876677776968996955745679988996348787359758468628354312566142632536246 +121123641562156174767753278484474878335939954968765687786876898565777779659675686696785669795957747964659556547965742244633152746331563554623 +355644121355143544367583885222399575363465599968554865668598969957588769779595677977868695488569764557558494766874538543827175344641612464232 +121546466164147161146825283632867698666999564854867996585879897799868966896869797665885575867985674855398583887644236237343746346143226215265 +436614516626117247668488855535485789844537869864568767656875655596888866789868586798988755984746596474359368688647478456242414542235563641621 +633634564616335723546828253633486743945789945997996857586696968699666669667796998697878895567997774785333575795833444254786322455271543633436 +361331351416517162585778826487465855878374958445767585768797888987988879878799665767596898876975578886454737447354327265647325664161445541521 +362414517626415637354754282382467859764655658487984785758989587688986797687666678598969885768577497544436455785994662456446672652261774552155 +252225416361273633676457477649489539647889867656954575789755976996768687967998966696988686795568546865743839835945444684825432326276442313465 +256454416774332513724877466836869839573955445587558778699567767976868898969988876799868888566958856595588768477878256624332315722227712266645 +251431311664672646266448727783799686334367786886688977585688978666878778776897699899879569689465985696488966754437277233268437266612262226215 +132551456214274276534657643478683959437594957854777956575758998869887796688868678996995766598888956499598773645786526766275312746416677343621 +416315261334225464438257273888854933973989697595858958596968897696867788879877789859698786689744766458963938695336833627626422542122267456554 +421345644577661173534532325586889679455376687994985975999997888699768899696976986875856555597779996958468333963747664365856233531631423451523 +553363132763565264587743826248598664698986894799549967858869886999886868796869996987956685688796754756684755939648686555873874142254566436534 +653524334616134442368847847588569397939797677658495777877775867679868899867666967797958877597478549848764648959793736632568711647571311522361 +623616451765456225766474833754639596548767557746467875959898578798899796687996987759967858974475897566596448674388383844656211233624562155235 +541421363353615321547277647723796893756779999844558987997777759766867878876988677778599885765774596768694755895735688553743567157516224224643 +543116516776144736368458687483889773593994464977897665756589568888777897979786998787868595677784669858774956758433235578555264734123174464115 +636541536445572254645338548743776997447888888866695676659677999586988888896989685758575595946746898975653396568565864268723732431233565661212 +513222252246445175143753847837734765679344688477676698769698865679976797897897589898798698559486567658694457848455254787532753212745675331241 +625136445374663123663655832755345354976634956459944485788979878957788897877985879859768775884699677489767333846983422382666647421352226425225 +324443225174677461748683365672347478738555788774844897999798869576887687986978789886666578476648657444585493879576577478474134611721734355163 +424314254211444744532768584466499489649935678588669579659987866969875557798699976968777786888957459787865346389828272827668522435735372264463 +265125521227517713633838388828644363898737796686877789589855788695588958689657665876966777855975549975634333844338837247526355562544551233222 +525336633272215466423626368846466456464787455579666747779566785755555969757788597968655666856794648685567879553367274863385533273645155515446 +243311312465162534151636583364739696567398469878599466485665898655758785785687565866687788958985474969433866453677655856831354347443762145131 +264443244614476736234852323645273556749677447846557799448968886878656677859599889759594785494888946787986655644875754742255465153417125235324 +662164354524445157747425657647689346866394695788688888885797999776859985577958969868876947787449589543464567396733553353521634753225622665254 +514425236451223756735764726344352896573675835799645465748759767985855966587885768758799649579985847766868449368873684325821363423347125523531 +624454214667235623342258323445784877367564656585857778949688688569889577596876876574958468546474464458477796632224766646426562366616222415521 +251123656312532521715722736583532466476666474584464687598845898866579975955569965664879774646598483795585484646845622587652525117627162132333 +163154153244326523535174467822736788387965448734965694994489944798588556785595685675488848888899749863469698684588575773173761233622613525333 +151331512646714153226228566325542338478578764536574949498689674685599985685794874588989884548984585998857839424246746683274524445665446564241 +522125436653516611267735652575462746493657677565758588979487954444677467985944759669487585597983397398648644355678344837257177434554366456214 +425156155136745622777632255745828643699849839675874455756949656956754955659575659887798969587549347857474687556443424785335416411662456222412 +456112456662645651321367533625343887465933988375989859769944944885846958468976468558974779483979539968978826652443873732254557744743321421511 +252543516516116471113422584687254755473679944983455574459989899499996746675975464655485684783535448659593568228464743613721311276625563522566 +126441624643131422661477674383358855857653655754785449744795986875774569474886594786685558473734658369644484838832457356267122113643266642214 +515612113264144171331622232265463255585988984757677793854649994965967566864844579895576797898777565376797833738632784756735365277152445331424 +254225242565334134137745631683742274237453876668369633846477956845454594864486897574944735957999686663758553243756377567262664371336341355164 +443411616466643174343244136362258366276233735799868977765644765785754648465689786978677878383449888387455852572642846211361423556144134456424 +214461256112666374743527244124355566666443443834965658546456494847697654995699975467758679638894695967587655888755321115373467561335215443141 +424166241432664123466515253266378746622565593939778835444683896337955666789459748395338595759636337566735372672548113661661252645642325365355 +234143514562565144143635177173337876725533767733546393395474635873545758393445694696747735466548857368587374546253275236111252612254135134453 +342315422564522166632274173515358224583585568786877394844445594466474353789785739593459945448487933638277644247425745441363252456555462243323 +421145213536544343211461477334364327357333467783393654367676489599468948585553334349889834579685453723225344262851633511155612262236664163254 +445453246121426262366374476466363784853622663745986555363375659999385769766996839463888346333656424354248668485121245352157725216266426643345 +511314136536341441524364755652766785686853462326369674894967485785554446748998683569557747596762788764824584731445143123765264113565454514125 +421113241123431631646623316311257443262665643835654679697933858673843737847787484394934457457665273585225753714614116416737612443624432444333 +432322514152551326562161445126524175683478454227745436644649489573773743595577756765933646436267337573352476227253336437412656541355342341145 +441331424431232262132224244632546611683245632564372256654473488446395647686784448697358543247236357742487764261517365722346651214311532522132 +454323422326524542343366473376237356378846232442565827878298334893977847667584457584786472363548623324444377756116351145412236216232122411331 +535215433315131612541256367421446743238337552467336755247464343979447677656596456572556345446354445746385342135143523413631352115315324432221 +153234343224152425256146575563345432752576735432852856237657275824647958995768547643522738458554435226756267241475212322433255433356144445312 +142512142152165155341634256732265747443115824683874824485832375475336557554528486856733323433668826733265236415314736655234616224663352422234 +431345144124253623644632464342575566322774845876477683223254765547225556783234827547723757348745587746315327637752722124355255513621522234212 +142344553222466231151411663436714616176454748664263422463633276288362757658622826622387252226577236617254721126472711252665451513225111342452 +251525235241235162344614426124333552474561565723586768453536525783664575573648223363338684376443457225337627351667163226643532513443323144212 +442544325435321313613523424455655114131153475765573448734727534658425364264358763662577468435726252773375671675727312661631164442135132534253 +224511553345154644342524521234722554172247326113476284458754687532483454757255572458274674332772433317745677122164112354141423165134231332152 +442313111215315161343636334441112263531144232647723558583558466853464823776643255438358655763336453357232121754665553425125561145555141414523 +233445234212244211116323116362314324673537777714561211136488384484342736664582545482355831474314167541164723656113262563221116541314442245344 +431245343331514534521134111345252327442542313271611473766274782225377322743852383337515263452644643447341652742256451551254461212311443113332 +444431354311552442442461661111651156711762233333166445564415545476888434638882738647577113426745163414273235134211613435462132525553152112114 +232434535113145531525364251645553226433236344747772174463644621645726521743717274321153726241545645264217156136522255646222124432225121443333 +342423245553252444241151231665432544541733727534426443374676265537114134236717523372166344421232622362311123133411161244615151354453141513324 +123112342234321355254345451454115322255473315614354221314116145231536731626175136534353326234744437162562652155213234226625555425441444223132 +312321124555122312314431646262226125513615675446326612521412324666545247254731652233651237166243211234412122164362462223133133223131441233434 +413132133241542542131351136235662524441121266445577537232444372642311712423624235533163575446452133436343551256554361525224315334332451231144 +122232442221532514523535221334233614322532142156616214173612731334644454373741431663367772627765255141563453536662152411234525353311542221114 +122432134121552221111312325313143263326162133264773327217254215712252275124276172111156356311411425225133364411331611125145212313232142322234 +134142343234154243425124151162254416531362235516161637411151131345343521271246734363174665714634132413442235225564432414355512513432234141311 +423244241241224144313115541343631412413312666216611512362352654734126155457267512773726455431313245221663633663241233323143215415443121323342 +224132224333121321212341341311463524164225531331531152444645216524113215162716255662233356115316615662524565313642255454413214542334134112114 +411124314243132345222223143422522315526243251366223624261435664413571136641472554343354325566114156153421332312221145211533315411344411321144 +244412441113233453342124311143132532543513253512611344325543442551242156465142136643124332641365146163135121425241121424224522121343121442313 +134421231232142243552433355231532332435243511655462223433565552442446513242622325323252412455343613452651163234441445531525322442222114444131 +322421221111414411413542543412445332436314312152256436111351351112443643145563414563561153341314355656424124413535534155142334324222222344431 +212113322331443213434455432121143512121332123655111235243261361364332132153242614136115431456622664336232455232522435352424311133422412332311 +332312332222443434241132515152122341335533226461126526512545145464625526451521662623433245422136461122541141154353214153521223312144341333322 +323133213424312311241324224511441433415211233531156215452452353635353165434233223513541552216241435245242413453131315554233444141232133243323 diff --git a/src/day_17.rs b/src/day_17.rs new file mode 100644 index 0000000..0f90905 --- /dev/null +++ b/src/day_17.rs @@ -0,0 +1,213 @@ +use std::collections::{hash_map::Entry, BinaryHeap, HashMap, HashSet, VecDeque}; + +use anyhow::Context; + +use crate::{Problem, Solution}; + +pub struct Day17; + +impl Problem for Day17 { + const DAY: u8 = 17; + + const INPUT: &'static str = include_str!("../input/day_17.txt"); +} + +impl Solution for Day17 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> anyhow::Result { + let grid = parse_grid(input).context("Failed to parse grid")?; + + let path = astar(&grid, (0, 0), (grid.len() - 1, grid[0].len() - 1)) + .context("Failed to find path")?; + + let mut visited = HashSet::new(); + for (p, cost) in path { + visited.insert(p); + println!("{p:?}: {cost}"); + } + + for (row, v) in grid.iter().enumerate() { + let mut output = String::new(); + for (col, _) in v.iter().enumerate() { + if visited.contains(&(row, col)) { + output.push('#'); + } else { + output.push('.'); + } + } + println!("{output}") + } + + todo!() + } + + fn part_2(input: &str) -> anyhow::Result { + todo!() + } +} + +fn parse_grid(input: &str) -> Option { + input + .lines() + .map(|v| { + v.chars() + .map(|c| c.to_digit(10).map(|n| n as usize)) + .try_collect::>() + }) + .try_collect::() +} + +fn astar(grid: &Grid, start: Position, goal: Position) -> Option> { + let mut queue = BinaryHeap::from([Node::start(start)]); + let mut cache = HashMap::from([(start, usize::MAX)]); + + while let Some(node) = queue.pop() { + for next in node.successors(grid, goal) { + if next.position == goal { + return Some(rebuild_path(cache, next)); + } + + match cache.entry(next.position) { + Entry::Vacant(e) => { + e.insert(next.cost); + } + Entry::Occupied(mut e) => { + if next.cost < *e.get() { + e.insert(next.cost); + } else { + continue; + } + } + } + + queue.push(next) + } + } + + None +} + +fn rebuild_path(cache: HashMap, node: Node) -> Vec<(Position, usize)> { + let mut path = node + .parents + .into_iter() + .map(|p| (p, *cache.get(&p).unwrap())) + .collect::>(); + path.push((node.position, node.cost)); + path +} + +type Grid = Vec>; +type Position = (usize, usize); + +#[derive(Debug, Default, Clone, PartialEq, Eq)] +struct Node { + estimated: usize, + cost: usize, + position: Position, + parents: Vec, + trail: VecDeque, +} + +impl Node { + fn start(position: Position) -> Self { + Node { + position, + estimated: usize::MAX, + ..Default::default() + } + } + + fn successors(&self, grid: &Grid, goal: Position) -> Vec { + Edge::ALL + .into_iter() + .filter(|e| self.trail.len() < 3 || !self.trail.iter().all(|t| e == t)) + .inspect(|e| print!(" {e:?}")) + .filter_map(|e| { + let (row, col) = self.position; + + let position = match e { + Edge::North if row < grid.len() - 1 => (row.checked_add(1)?, col), + Edge::East if col < grid[row].len() - 1 => (row, col.checked_add(1)?), + Edge::South => (row.checked_sub(1)?, col), + Edge::West => (row, col.checked_sub(1)?), + _ => return None, + }; + + let mut next = self.clone(); + next.position = position; + next.cost += grid[position.0][position.1]; + next.estimated = next.cost + next.dist(goal); + next.parents.push(self.position); + + if next.trail.len() >= 3 { + next.trail.pop_front(); + } + next.trail.push_back(e); + + Some(next) + }) + .collect() + } + + fn dist(&self, p2: Position) -> usize { + self.position.0.abs_diff(p2.0) + self.position.1.abs_diff(p2.1) + } +} + +impl PartialOrd for Node { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.cmp(other)) + } +} + +impl Ord for Node { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + match self.estimated.cmp(&other.estimated) { + std::cmp::Ordering::Equal => self.cost.cmp(&other.cost), + c => c, + } + } +} + +#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +enum Edge { + North, + #[default] + East, + South, + West, +} + +impl Edge { + const ALL: [Edge; 4] = [Edge::North, Edge::East, Edge::South, Edge::West]; +} + +#[cfg(test)] +mod tests { + use super::*; + + const INPUT: &str = indoc::indoc! {r#" + 2413432311323 + 3215453535623 + 3255245654254 + 3446585845452 + 4546657867536 + 1438598798454 + 4457876987766 + 3637877979653 + 4654967986887 + 4564679986453 + 1224686865563 + 2546548887735 + 4322674655533 + "#}; + + #[test] + fn test_part_1() -> anyhow::Result<()> { + Ok(assert_eq!(102, Day17::part_1(INPUT)?)) + } +} diff --git a/src/lib.rs b/src/lib.rs index 2a9c662..47562cb 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -22,6 +22,7 @@ pub mod day_13; pub mod day_14; pub mod day_15; pub mod day_16; +pub mod day_17; pub trait Problem { const DAY: u8; -- cgit v1.2.3-70-g09d2