diff options
| -rw-r--r-- | AoC2023/day17/eg-in | 13 | ||||
| -rw-r--r-- | AoC2023/day17/input | 141 | ||||
| -rw-r--r-- | AoC2023/day17/solver.lisp | 132 |
3 files changed, 286 insertions, 0 deletions
diff --git a/AoC2023/day17/eg-in b/AoC2023/day17/eg-in new file mode 100644 index 0000000..f400d6e --- /dev/null +++ b/AoC2023/day17/eg-in @@ -0,0 +1,13 @@ +2413432311323 +3215453535623 +3255245654254 +3446585845452 +4546657867536 +1438598798454 +4457876987766 +3637877979653 +4654967986887 +4564679986453 +1224686865563 +2546548887735 +4322674655533 diff --git a/AoC2023/day17/input b/AoC2023/day17/input new file mode 100644 index 0000000..c0689bc --- /dev/null +++ b/AoC2023/day17/input @@ -0,0 +1,141 @@ +534415514135453124461333615152111172677134533636656271274236365616565137415273525511165575327363331241741557653113666233613115623152664423332 +143153553532652144244555514665734545167762313231334475322557762622752145154167727645126513352223423415651656133121126453225343466255353344324 +431231423644152164112135132615556326276246113351777544176256511561764724256562566422367116247525362264766445567115621232144511654116644221442 +425112541336332234654342545214351652572172316456737222125677244536164452131262721226545725765227744454452372645522325411234233321414435114313 +333322512434455165453611427363633244553411531716322136116465566556725287838862767327666631213226747356156745324362547346612431145111316162222 +111514411336235512434444722163142532326377265214477474772227434242342487248563656855381764455575443361236276175665733434666412316634222625432 +141463114244415543252465174452177273546126747241275378348335524748634687254422624326485536775674735465743152735472613365122645655326361561134 +134653525652435431235625115231515114422634276355327264488345322457327577336525263756684486556413673514652631745334477413724124144242416562364 +434616262562242243346234454655134362454141337665258437457763523262865265676844582783487233862482357347212322641527462516415365134321145512424 +353433635165154445216737761473212433367151711344884646786288727388682537235754633528622423642343267676557653373252736324131431534241261612624 +535615234511545246516346262344152117454443774583448446657364527357552232352434576756858266262525523551653164511467127723215346233625622165551 +231653426453544512572173275441612612663732727322537445574356487336284775283336572372467376626887535687344753435441261141761331551664333532444 +236225356626321263631234733432532122217863566633725667447746588453345684243745863267773675523574827578685136411344611122414161343312335613311 +461442663642664613611212153714523655525727747886855882872352268628385875675656428682784745474866528478767465675454576242747556364563365533345 +235516112452617534221523251215633327684642774455582744454432653632663385788245473237856636588357775688555238612412764126237253373113125451211 +554126643325367353521466261744747333266574465262885865853664734835482232538827357464886342245884668488367534426742241621543122316311112143422 +234522524632163352713473132442554535244857335254754323244728372383524234632427343647438643288777723723447538538615457651524666555651133323553 +421261554413571373672433437574763482622586677388856845274774733653638779985648352732582782737337656453244353668867347455116615321754152551355 +351353342433572637145116624252437536486848242228584277342375854365493384594846835984253244438886785788423556782746626274532164152146451226411 +565564361172562162776327653656863878722422532276353247372336695938495676348577649877684384837355375252568666257834754374124472421164745256131 +244511514517375224665667415847488385867364744587645684567444899478367948453936433569898389277444822526553582555486471615744231363254776235525 +652231123276743453446765525768842635466257223326886959596965566977563679848768499386497935598725883564386578773876634317334376155476666666361 +345245346674114223653527462553638552564535727362364779936457969678493778946455544457554389938484785583632352473458263377762577143336473411611 +552332356127765265621174358564476888342482685288793375874696375865674397583436676496484594945959478537283242536427332483772374442134361626422 +544664154661637774671612856388833878588423434648656685779644585788369889539486837853367399757586957553246638464678374575426354675242173655231 +654664761756144662472474835855834643337643575954956454756888897566975879739687869679786677345687377654535233778635684687343237313445644316444 +634263424461271713551624366344576823288866938748445439359877487884667939977686534597945454845343888437227462467826648523786264337622226424353 +534213415514342132746272734737285627552459769494464677468358863997994876588384483784739443348534988434378735687243754252855245121611566552414 +355122664125227723657584672235778528835855996686857953596859554477547545793379466677864667539765633798988738384337784377745844677363654711732 +451422325171376461588422835654277873234597573963797648867697393465575359953985779866763935693657849885757872484472473354663766413125123116425 +147512513322221371582375845384746648976378649874469584566595439686588489397678738389363874888787646358993454837457822373726841637442143353742 +141735646163156428677787384268725769963479764954588699845558585487948796686489987745673587973768987468385489355376788865856366613213654642522 +753142372125655585458574476773623265377969854865338398634936774994444787445789948859777953686746484454675675365823773583453376314747433723146 +245741165457173375367474328273434489385936398553965897588676978864769895578556886689947899495557637368566938547737843727884854462267733116641 +375613234515634846466545642777365755453795357393577876695598897969846468468757674479655854896963498535988548556884652834655883682273147214633 +142334425663573763233676275843345697938553477537467464759569946578798565897685987549445888756748388657745485353386387227663425726776264536222 +767564476241124338562456283854764739563737343884848945786455459845865496987449966895748566577466368579359389887952773245638552665132432146247 +463376163734176445652626262675644877754446893657676454885864956448597499596686574544755588954697934488587684477693475458385324487421611722637 +342263463322646282757665638336586388666363837365679874675594977548656457484664755756449795469544648453994873854766476823882727678327753752743 +536735332312235682776826877553783699856378966889699966964784774876756656679464757499987699857775754777588835773395653723474737584784771111721 +443513421717782325685558455497447743798687484455746587687747485885766987648766946954747479956749563458637769787338496582846624785448364647457 +753474227124465665228478489473453899744356575469654569946744854954696845858878886794954758694657954647954959359669534873827685747672462515251 +666773657666348378827647379355936767948876947679556799489679669887486989565944456998489745848976699833349738396944355876672352832784464241155 +756277546626222245745368635866653447957845659595945845964659549947779889564878974487597446755956577666834539874978976947744422768766342631762 +213661414175386688225557549883756493984535966564858545675566765767967458947595746584954979759645588548965987873866369433574824364356865647623 +475232731233284282888284484565363366854689844644559645854858965885998559657775565656679845577769445767474378576883467978675588438642445244432 +445647145645642768385568686576858797736745578979749486765468599999556569859957586964459448744975555869754353886453585955777834222765323133664 +235557456253733727462485575776539655933954878445957898577958678785688955658676975698446975555979758765866654847379636544738687474828783113272 +441372758738567556557625995886765974997749798977978794644557558767698589685779599899994999758975985566995499676738695977574876455787484716541 +146433637657867633765369346677397965347675847545447969976699698765578679859577678599769555498554784889764585463945539556948842545685753217125 +465127582384587626363646996473775434854584597874669459767899976889775798699556986755887764558478744444746967385964594636358623772878283275312 +151364275768688482822979887983978368654988768445746678758856765576868669675879885597558755767789998644949765834357767477494467458587344836537 +215531732828587567752369839346579495474669469744599658997967678556589896568896657958858659968457946865556597877453984466747252368346276516124 +662513728842323542737634683376379586556864484999656685889895969958566559986958987679565696566878756558849448986596735353794443787685584781252 +523446885357236827248577378664659478999586866569477867567587565985576698568569978878667979896968799564757896656863973977667228857834256787356 +211311884258626284489634536357978888579475494697566565795757569957586575757796797578599577866597984997467449883986653574698538555647534287251 +466661736853662848357464753659894795557649797784959886857678779997585959769867956588896986875957765797784655855635599667948468453722587887424 +111312365225863284499986968566548849484466674544878859578796979586865777977957757786986685978765856785499976687845486996664586788738244423427 +516676232254833262768769468757544474889845796794857959656857589568567676676559755656595755999566644699458844654584566995859664754525573234734 +431142623233528247835635939793968687846795798578859585665955655988868989686778666789959685775667864978499688654474448688566477562428766376575 +744752732382447637675557544774786594864499878475668596965857658778796686969977999569658996578959569745955454969837788494794634734558736487132 +745342438238877336974635656794496898467587849466887659568588856668989766678967969767695687797676587769779978678649784653697586326842567744757 +511558425343666383989888374386845497985549767768967776755699897886788867978667789896579678595757995757496455586689746785665356436272232274874 +517388482454756428856774849647395997579444576876897597585987668967798887896997976778799576687969958694694854655977863788946485328384573885735 +155525775783888322494779755836365964487665989767965777789868897676786967888999779678689955858757585974447454596449973893339893782477456554345 +414135583473533472348796677746964957485456999888876886978878867989878879796668879768779987857879598649464456497568553563768898657327774852562 +246563665666434567734566795899959969765465859885787878875779998789878799977986699799886588579598585684648468775454978847495646436564862266347 +721765872733376428447398733987854688575957784658585756595579899978798676999789777896769855579956955785484477688985838887639387584372744832576 +341267842585563327386548739577954889658787478868695888556986986967777686799667787987787967788779888969877845885783658434554537828385837475276 +647534578864453238839885598334466485548987775569868585786968796867888687886696998667976959767685685944955987949584359764888686542226662533651 +671352655352423376848587599896565946785588687679956555697996776978667779886676887789757788869968589469558989978946388453573439338588887878575 +773347877454647328958545345989878475547689855769779777768687798877667978869777666976798975668879698976886584747859948554857358365342558386816 +474222633223386649873683946337959475569879697859679695685969688889676866766789669897986569977559865798649575968845737734358453445225752538565 +734467526268754489657844754745965979978964547997979588665888667899667697979898789768659996578766666944678859757965755398776564884633847735653 +121635723655736356439854587856574674598859567967966776767879686996799776986978688969866666756969667769446546744988563845954365564646683574555 +553455564664244582435793979683957776576876865887967759897698789999666687879899979698585896798579557958476764754784576974545345666646433535277 +572443376682437452569986763786684547947897485976779589778657867776787666897979678799679598969685998989485689596557473689736833583338772538443 +355425735685624285949664656689995695676798668687965568578886678869967776797779766887685857986666569958784694964779774856434534847876427833327 +256284528623652482678475496864775444668567778666576878556765687678999787666687677887789658995855559788699676996784683863948594435583773584317 +432667672286323844358788783784588999789488677779585956875668886679766678989799987958587975856757945794994794898559396639498895525555644526733 +721724477828346855977584387867654488494568456658999995559578567698877888778869798887875596896656695566667678969648968889583556446566785763656 +233724586442255363567669586745447976955569465769957895779599677688876686688668786687678655889858966644846877945979493333393586577565636285525 +164353383342837643243375573743785446587559644956655955757566675986989898899987776879557587755665465586846646587385947987459473277882686624217 +565615552853548658278684574495354868999778544646978987765787679877899696787798596865895767996788599979989457684345498537575466425857363577344 +345638656252748342759783375933956756584488888986977766989675895676799876877979565767968679686657454499856869988397765894994384562834667838467 +276464633643688525438848963996375876497759667649769967578577669575896777986785878556998565889979488447994498764798335873755946387647386525512 +556476548384684684747839463487747747677594499474576595898779999758866796585776759886965858755746846995766795976653668969959783533624474561716 +212147855848323775377774944587656698488794555859875598967989976985776588555555866698867577855796489796658644767835876766963823363486365587214 +263673778857574832648764734449445535744567448497459778677597566599869766656765857565896859999754658478975558478437475958444847845847476273744 +277173245483827546468738785757338546567649554479645655778957867866885995999596876955756998578487955486445556845876385553656278548368864853454 +346622225346485386555887553995389694598779685745655457756998757568777958966656676577999899779867655555897748584497989646873248468664855317362 +121564532233277785467583753698673764456478674948986445897598689759578886895878667796686599977686774986855974495963669656476725728684486246475 +727267373755567234376783444575783936676494959979964475575799866659969599756897976779865798845686498947858797884997685366438227426452525727224 +544314154452746278626779683776698388496656999794774878869686876989756687798859856569695546696654764997484765564793465593753756657424673645112 +426334173466474242576326976455988688774685598898876688474698698979878587678998978597959695499547657974957477634488643644654628642357645126715 +221164646742527333275258865488838554956796776454656649569655779675656956557679868979645596759877659969744684986483833796438784776777672444535 +276773631343388587538634786573364646757487464586455968447964488679899658757786667689855967648769967859789443377996348585427678846354674212555 +412765711352782282523537643489439646353657994468687664775658997986888668585558574847556486456575465684879488438554765376688766665652463231145 +261643766725828834835638353374944685754898794868958698974454889895556459864545868669699787965474688468757583763786935964575437863524456322324 +564744461547572345735766567587446969793798476859565846596869976868878595958645887698544979978858894564375459466569977587258267757583654755145 +571152457224545346785462736537659578388976485556494478497954994558794789449685487859545444867446674765565576834674976582237633633755833115657 +544243742657483528734476824455854585749959795549655554846777644449849755744784554768597599469549458535943659586549738764722227627247113674533 +465376454533465887782328464373539496444433376689568748879656679588657875979985754945479847494748669788474957993333495558862754882275517361356 +522322621562252546456278536847398793876444788798479684547767588595964476664494759564646558548687735683493588967658367324433447742287124454551 +754745177477547553447757642226496337774335895487988979857586455669469949769584688854546474799653989849543935898756576788787244358555631262267 +633716767167335633763823625659365464497635598768968988675757846669944657566444448944894694548848755879443674867377788377845564463846113372711 +771625161217123842748632367334558488575798675445794844994847467476867898555785468779759775667837969887446476385485428386854428238364656353455 +573163124275667733438428834356369879356846584785868438896479748788856645964966576548996869998837788758379474737453724553526238556135763452246 +723727545315762283447867476368348546385496955666674787875779994759568468957968989785798984436755669889954879796643463367436326236154445266135 +156132757137733552887547588722543874834866897443745339749665794586776885646899759884584467788768667369853963736858737556473582214663236721114 +671632221275173663768228645264555369399877384695855538534899854756498556779495697973457398593784783948455643485833583822838565253723565135257 +237655473243421665433644822854475846473746974765644955347585495667859979545876696958644443788537855668768449276543236877674458174341257711127 +435731365262641316665227486587283844346756574775677874499534998487987876689437557554456777386439768536843756462758384658258887726313711521241 +613311751267562472536846342365762357378444474497983935978575885936676364899959755856796583435534363867736547388663236457476351272751176751375 +423547215173421762125786572864653546375545683657564783447553476753478893688997596663438344697986539575784854728585287672742255751124541643323 +145515235317411572656357743633528662878548667354387847553686684498963934448633598365367766599766345873424334334778388678587173751363223615711 +232312761271227562413536578564848447252466393677443365548367793388663535648748559489934935578793686778233778252633832748575255475244651351716 +213221411636634731216722487428847864847744695445996383364364793899585686979695863867435549754853446436686745446562628572315154461516146515446 +132437367352246256527565357274656758625674565487337575895389538763857649765979488594697888867965394684274457388743764736571536116317224551224 +256346535731162646453573832224772648433633836785443833895633889444975577855979868348375559365635772233224556774552353753711414261632746143455 +134366355344175664142754446752768464562652524244249688948586897574665539499888694974745958535823367455382233686324826863721774142563453162543 +232521167626233775674441775355572237756262555387486675966785484954744857865639973874877576583274725757437785544482535171662457115144131356642 +535523551677464635576122764546285443426583345447328647379446733349879869463979947986693897776576274368676368623374463441224713635166567656322 +322554246276744511612756773585582344584388533824364675266783345399793854674435693886332378487228564643287886653285571223561126164434676232635 +133151525444131721267152434745367582475624526577543485874827268553547956497948985558268636462824482738878374373247745611327722224223516562164 +631113666321523115544756536623447836378675737477388484657467785742258365867785875347648572646383235437573357658646277371715771412637614613564 +613454432142746143246236746677746258526435255322868367366533448387566444222856357666444777253388426544473752443317652243566214327345531415111 +612552142334225716575367613772135736285434643266582676644278553428734447252373746338245386648224378542235327641417474274764425114344236654561 +566521154163322457512764656442315247474444466623647758737853344443466222847728583745538822776482775667884627272364424271734721746325642142641 +525433525365543323574127647653346564184466665437544833374488864824774274448577747533783768553354232856364621565362631775234372425263465413634 +641232642454261355565153272414365552253574756623558626286358742284346768687345838623743224473827446863626763421574575143445115131445425342443 +565615644253346552353573323243171115674268236734574476384323835756863446337746238734754823364243344332315322433524256212217414414524316232321 +144411644624563614616335155521431617445252863366554358636555762225656385543542577285355663277745374226126252535743144236225222326151213162114 +164465123453311466631745437761513754736163113523342655835562534742636588426578375584884542574286746172215171731433726362521252526125226316644 +266412313626412456352255523122162552246467472564672572624335752886865853443364264337252488686566447241463771242574574646723632616631165231566 +125243416621545466254631426261643517757142337233365327537426344452743478323433545334333776886455363744322261161533367475226466455121145421555 +243636124536216413242417371755621123365122522612246447676874322547422775322663555232775224452767462351722432314711417511366165335354121363443 +552314332145641535152245776413475576234176511166111374535652333587354682554337348283541653553653477621777653427172723523115611616466341145443 +433356555154161312562332651636363533565751644223741645722355435554442236322545558476342436565143746544227225743667122345363463455414415536235 +423154245165125624414155562224431557461334117361562221661757752155721727456434522371755771164266243445632653752753526633124126431462336111334 +124444552364152561665532531634233615724764471561612226344134256716317667432613647737247777667745522756612542716752564161336133565445451234112 diff --git a/AoC2023/day17/solver.lisp b/AoC2023/day17/solver.lisp new file mode 100644 index 0000000..94598db --- /dev/null +++ b/AoC2023/day17/solver.lisp @@ -0,0 +1,132 @@ +;; 11:45 +;; +(ql:quickload '(fiveam arrows cl-heap)) + +(defun in-bounds (field crucible) + (destructuring-bind (maxrow maxcol) (array-dimensions field) + (destructuring-bind (dir row col) crucible + (declare (ignorable dir)) + (and (< -1 row maxrow) + (< -1 col maxcol))))) + +(defun advance (row col dir) + (cons dir + (ecase dir + (up (list (1- row) col)) + (lf (list row (1- col))) + (dw (list (1+ row) col)) + (rt (list row (1+ col)))))) + +(defun parse-input (filepath) + (let* ((input (uiop:read-file-lines filepath)) + (rows (length input))) + (make-array (list rows (length (car input))) + :initial-contents + (mapcar (lambda (line) + (map 'vector (lambda (c) + (logand 15 (char-code c))) + line)) + input)))) + +(defstruct (walker (:copier nil)) + (path (make-hash-table :test #'equal)) + dir row col + (track 0)) + +(defun backtrack (dir) + (ecase dir + (up 'dw) + (rt 'lf) + (dw 'up) + (lf 'rt))) + +(defun next-direction (walker adv) + (with-slots (path dir track) walker + (destructuring-bind (move nrow ncol) adv + (let ((np (alexandria:copy-hash-table path))) + (setf (gethash adv np) t) + (make-walker :path np + :dir move + :row nrow + :col ncol + :track (if (eq move dir) (1+ track) 0)))))) + +(defun next-moves (field tried walker) + (with-slots (dir row col track) walker + (arrows:->> + (remove dir '(rt dw lf up) :key #'backtrack) + (remove-if (lambda (d) (and (eq d dir) + (<= 2 track)))) + (mapcar (alexandria:curry #'advance row col)) + (remove-if-not (alexandria:curry #'in-bounds field)) + (remove-if (lambda (p) + (gethash (cons (if (eq (car p) dir) (1+ track) 0) p) tried))) + (mapcar (lambda (p) + (let ((nt (if (eq (car p) dir) (1+ track) 0))) + (setf (gethash (cons nt p) tried) t) + (next-direction walker p) + ;; (destructuring-bind (dir row col) p + ;; (make-walker :dir dir :row row :col col :track nt)) + ))) + ;; (mapcar (lambda (d) (next-direction walker d))) + ))) + +(defun finish-p (field step) + (destructuring-bind (maxrow maxcol) (array-dimensions field) + (with-slots (row col) step + (and (= row (1- maxrow)) + (= col (1- maxcol)))))) +(defun path-cost (field walker) + (let ((cost 0)) + (maphash (lambda (k v) + (declare (ignorable v)) + (destructuring-bind (dir row col) k + (declare (ignorable dir)) + (incf cost (aref field row col)))) + (walker-path walker)) + cost)) + + +(defun try (options known field iters) + (let ((next (cl-heap:dequeue options))) + ;; (with-slots (dir row col) next + ;; (format t "i: ~d cost: ~d/~d p: ~a~%" iters (path-cost field next) (hash-table-count (walker-path next)) (list dir row col))) + (when next + (if (finish-p field next) + (progn (format t "Took ~d iters\n" iters) + next) + (progn + (dolist (newm (next-moves field known next)) + (cl-heap:enqueue options + newm + (path-cost field newm))) + ;; (print (cl-heap:queue-size options)) + (try options known field (1+ iters)))))) + + + ) + +(let* ((field (parse-input "input")) + ;; (maxloss (apply #'* 9 (array-dimensions field))) + (options (make-instance 'cl-heap:priority-queue)) + (known (make-hash-table :test #'equal)) + (w (make-walker :dir 'rt :row 0 :col 0))) + ;; (setf (gethash '(rt 0 0) (walker-path w)) 1) + ;; (next-moves field w) + ;; (carry field w maxloss 0) + ;; (cl-heap:dequeue + ;; options) + (cl-heap:enqueue options w 0) + ;; (cl-heap:enqueue options '(rt 0 0 0) 0) + ;; options + ;; (print) + (time + (let ((r + (try options known field 0))) + (list (path-cost field r) r))) + ) + +;; (let ( (w (make-walker :dir 'rt :row 0 :col 0)) +;; (y (make-walker :dir 'rt :row 0 :col 0)) ) +;; (equalp w y)) +;; (make-hash-table :test #'equalp) |