commit fbf3f987e153a05c6fed487dfd94c2ce5677b575 parent db13595fbfe221cdbdfbe5dd8134ed28f25c8f71 Author: Lukas Henkel <lh@entf.net> Date: Mon, 9 Dec 2024 07:54:47 +0100 Day 9 Diffstat:
| A | input/9.txt | | | 1 | + |
| A | src/day-9.lisp | | | 85 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | t/day-9.lisp | | | 11 | +++++++++++ |
3 files changed, 97 insertions(+), 0 deletions(-)
diff --git a/input/9.txt b/input/9.txt @@ -0,0 +1 @@ +5494127165299041769368254544348579253534463146626075859412978550423628199489366421358011375233253946425054622791607827395269819132214074215789602335988971147773637310652122277238899913785535614123886367787789624548344015321770745447188713612090479445616539416277248833633555361056692029957638104934468879249049788227717456558675813679945944432837613197298787301111428141206798505038394896242274933433916691357546658595758833974742215489624452681149589328889294557199956935962261115858728155936644545893177670601581171077556512359581538372193862256679361238518869296213309423231729425453469059124134988766652810259262499927471671911121569951144287889239472055322376684079466778815038284112474226871216462155144087695823705623168398506396496474552170119118648948392780759594329060768890644387593620544455589758816260687527361211166670901939256277647188825078155679642367832297463792798793507656112584497092758980199576839085567911453847573723564412921048605225176085374387242130238058229930151471771237139410659371859532596494916075273966156357258583988883213240136855331791343169703754779770849252956087233749752012321176993169633868493732843388852568363336469254669519289363171271709068342475627024359537448542762148257868153412232039211656978738867948541633926514724185442181727985618721467045297925363666537249925721851141234386612428488870166242567642385646526298921532327950932933317739174427306070941944138632211274364473666950353913524336981229819070192697343535474251396863446227807786724834513815486345822032108573379636252995671417962990199654721760694177411253381120352594438549414911953885727818392760127296122696246489759290588417861323405222243116689745191922644827673624195455713014401760148036664670215949198433887436872832539512978890232765538557807853524824661597657190909458402268396739122820214419724022817090149860881735894083514452399598852430574619627397732944833351236558663676354327247136924335501737306162852446136270192212342112313336581394157477114340975634635930975180323516748574758791678343527220371357204735911881206535985791974414333355984395577768589641857914524333299855802125537735826084114878619680666338397811951924305093925519607684495763575295251529657718799892594629341972575129566998368033207215647758737290528028305854356594869686901965405134163873159230455856806032272960103782328155411113813912478163964131593638236820657940291723176193973065139173966956952862986947491399557229235255554529796255388198863486284051534596231065617097886722702669478680429935209426148535514267212331856649829018754497126126817343287627628539869845866284581478715591715791962629686266321796884650392861997522581327817774817327346924172988666864406045977571186825294961476020983322332222651448896343135713137442213819618047676735771698574235101063569315149812224887494089629720542835263989124448268398421599811072668940494795276184716985685033521258953554166547405145355378358119343231466414794299622571366861156036591128961197267980314377514578252443234223169747747266305041737891261084595735266213952477848186827227337561107471517684559696772859381397565418308190139328322017292655996657291582725157634663623098623430244927532593874219923669995644472411944056885882487264324793356447589585477645487835514919764349275169959814425645282165294211123455443968851162752089592885123151775637256886706285748259404746742879655143103038808929201412603043655676987454114495214994327836483021893243128722371697329419351198967385645677291580832727122165686735598831519454432436377929606957838611799259671247163057901348564819462441323365793596324046706113726485957754166991713870608349401287671198588228575445752881368049718638818219506242777685506172298818614234688375602042946052885882289824899645765590773627544783876680963540186042842365527993644193299675326449618889944845846155252271968477275194916986939659596515625768104629351549223695243376768518754275377983735267249496565751623648229033389613354228706749633522173781115048952746923983267348241134841827221890516589912626726187186826306682337954642041876048114728509528884224161473246359464937359582544727621034833676216547915560782528471521849033312415964199317732115212383275885588574925828049505274115826205436695635154719881336845961292733811097462591938350839422121165599161349934636299799175621288245151861198245024721799471620936921351523419381692940745489327747225086748755724344957569728773565322447321667659731861518423813158476773897964274222518795677219351040775835256993372822968556517847961020719472227488946277521484484334778991526810468260461198696334826539189484806231777356323982314630843668418321575844525677384073873156935410163551387964396125403850185052382892713431566782656664887629657828654688202625642773305953802830829519446627965667669052311849827760196473567547776173764484398094648123154797195066794759921343967276545996527848954494799166918797896778549062823137135957711127155888662918875972604594927540893017133828598184103729795799196534607825169445416815167814901972699124831228687342426511262611876210669596356176762575593888175785391052435559337128486927931437812045332564874348914477332372863975861727392942675811185167324213822144105068772264589041503717275125175942848855121941694069763087753877248158497912663543247842959841833260458167795394113295553044224771136393929014405697167860567983404614608930492395971052665734365243636680339869138226126745875342623171441567402924873125472220953661606231287485713154161297485668525390774966484620583570992595682929655292771522354846298513722145143096177570435170895816757198144539377710617517215537757979948766776565781084307220659944304743158947383956898032706693632068372419332576757382582060322488319715255216183379178827907910173157374491857068922872148286504182271439443140823312851026507438515314578392458518209496478441698333211849204383624466376290898942699827907119601017644185419054811875473893206489451868305213772022381841162175256268825754462740303761697279208041456322463354245467634274724090152448369813411840353647673215532237324799158630821359675153361766618590614767275167613495598785194444189847645259856420693734739353434415241865223085754678201984359882784865289683516420347046486229993358292518617750769244331286689454519021183470593566769179365842903769596018941594267861236222658764401753355252441180855721412425949480567798838892786131919575451847294143704312608343562954298918899038884197345445175372275997806976995486632383143459358322716178175042952419729863406457484244811016711024875777869357483088753358945157991417962598452674888589634963311394865086661152757452789440397421453067323474172069803219385747962761664884348061199631331785983568988467139622202440567364528571856462694642356596987713767610663666189549642072394739506876955985291481218720539595294951918458497265538513668357224840714398484287474864813837592052745481745034391619715464113088695329193841111921743125867159924096396514125466718792568340256563546082805583437319417260111365948688336994318892157262917740408825686040877639548671321631347296234474707990889970656122308735597084604880831757843773929410466074637762353516444083933299928059959391826398414716227457114085933386844215515261133856293214324931998856155934661786906566715589864184335484532126785226424950661041969272414440336519172394265811933455818828577735465631423322246930368550721516452946191967314282175865917578599596825080811130368211652386616859943076472324437584243913273180583631966933644974151025222762252599907247422541388115517114619935339669966636776581859951719769897325608737743369897667633443976735406836329995607044419672434987432944413942875098205485737370433255954371716821386167454431334214994047641970842950554870553560724371911239403790888114342666124696141597251377396161562529683613442669269274316598511540465581175134292910797899321274823011561279133486541629974799286178483799596818883811528675327273936276217083307568724095234395264250215510302212262250413523494482436174851129868871195810832453828561956850728228742635814838722892621728765311153034318086195162542385186939325567891130714030922424355754687821824188717750355730839569534818424481509791313230319475763474539617613632528772126952135796467988217824109963239070689694724664561513668833472198787928715463553340736665486555733069783097914899796016983078553464904783405295748478552223581712134469712723879635197496817865204030782915772184321780282090638454511959759133203161532512707886483158641688498353131758167237477126183443973946901142246052645350737194609129743540748073318050436726124364392186986910823633179611248035128127391196857885554863563275351271691159713974995448506036707283129251844038315171124180629399799453651595993383436735943326218260876979827473696272723215514517275729481423124517909031383771622845801020632717184167933924423892926220118228249939644764181013526988609413895829433486587140695585449351345160897616793045213550511854625620651832618183735396431713658176649196525370346694926977124810829956132668407842629275167246215923489030178048951011622572468995837992207840337859503098568290528019862388456547477515705532224149921676395234352197338791486482417890886371404836341874823754872978113862112651898772426481352297603914786342791079266723436865876760493317716671247464438824231896771141416661264636649683759883829526247220171161704836912310255098763832437753803474163717456613628267885779454086751746824055317363384330196272541236262485656669728892358647269978265024892281412641503269225671665463278918891363228624429021393032481171394116686314345471842754218059615157377887965010326217949717131497213219403113998476496325575383973591222062939137417254793524821919538938116436412187521124125218885917892799886781945523886760535677817380224848512719437975993096162151128350434555985431539796834461361922131158183326547831362281401118416043506082138444749535235193182010818258626522262864222412589628477834296453279629408043496565858476158540829898378213914114429885699098882269274543818771242814194794385330888990901553347399464173522211208073214833505161705311469444379484641271723780824170434829427515864514735531909040558312431421286367728886362494586827476121665771183741249655553171837630354066239957988338323985257384187235513380466675996833597446171040352349772969678426236010282815934468301239927116222619872241998698679432294589972868357727559383953383477433399243586210321175588556268138452936365631609774867152396036915672301453207085935253634120386910729236973565561317452012291591959025541584506150974142719915225648879386296524888093631865733683919728936963733232684982455699903961584147341561406821132764967074263965979511571246361140691711842321275129105162394328831291634436327832402413983566763665862656754660446597782610889173655969713498978668576876895178429875699784799558741445503916287130703653134721462392321018568472938444692036524229735458378521603478582684527635699488666239527175446422786864294345546212771243339415829049471021964677532633657718307148741628275949646970964074791167108253149225542594777393322790705969846990322590822232636561721336677714865218573958734094187891849229203711295186535131386033499780485970942829167438842812664186232032975690692727319083548588486651546421176982576618974469962362885963725843223967519357913914144554354945415920699732755013106127157556371416619785643820716411506199144712479538687827896381307761513238925564639880881183771822131474951965881854707630324256135968549036587214888922136593672919131792968350894177733673304762905994464772844937507015816323446570194618982562957256764223719977117240774834177523761115144030748486643013721444496127617346492822945469219328945652793988527127771736965071115459192954861234969235185555597116472589666055148611219478989328587458887420161558323215243295682463727480889971794617771244116520151954727267412733601791855531477626491691307861889537933145218961839947174065973615408055863164463496643454331491667497138083854737115598655283358498206920654926953894871018248445587168421348226366546215871752732743959035284869247779492390364575145644714123239435464889751148267221684569411752725947559027122629505357651258639094556265209160982315492585349984292161595022576850667041504435324122381584473132862455475275588486897754985015589163138923575569389682119420449484464362981499351911492864546387719191294018663714743481491854421059387584656197713197929178479143477844892465863056866227485687799414398852192220641912864141945275983099684281696690896651158612856446367060113245631750926715178611634511988745727258424729349169887615701831586133958074827090511952861254479043608779906277892427148449995938224647572040703731155234547288551258888638534418436888647696712448163428207747619881847833546910974870752558939026141645955069557915382918323092611019849018581611262573151297323217696848448554169087885686548381139782167352272830816438565860821241293045934873385798449792634266353830716586383828761493367585205887143019583315326585257071126428182777223378598770278375699427229240338636596866866871705594457351385543855111551044389481805546552158683872728135812143555975725981216873606793465591521612106578506899602950155590955044702691551156942117318863559117571577195262344653536015553437338637417211448853499296523610613648722727149213779168234913526044392954582578539736193358549359559175541333178728896462217228339788328271568765304540733239365740126754719194346159364044233996126226963943769339271044151973818998541591389911671658733665128675747252191616165794149352906253979582779526657339592836398186274511209563313132842379518420676714586833605667216119476941137989485188342083556094479151661435254878677019976888427044665824655483487536313817377821775619352167809697852097565337503015617087584581779059259661872296732088584511122192497618512043285165659667123584688214832362679366953874166966885426763858417174823336724011496657111817766339985374851191264536232648382438876329625675482450949069311282699085696388783397951260119412163626769439141339703979769276153875121622224690231012709615709028399974179130719569528977987262467984125375579679374224287044603313482158959437761843234097693531211075424413702211793031898694724261557972344711335052606524587285413395413558757495696835984693768760604289477784784090951940513494189940417427369420941668838894661660873370842066204530914162971395261321968050819585157878935324792366437369508447462092125020357699226322278455557798239642409125984549721013227146675048691779412120489496815016164510843264754837785743991152375136615258447030423080237022766712488738597368569019612916311799376175625778103946948466212128968225164825135572329362207356743743315570451485474666664669909699226131283326772049499993152475373190948597921955669767277258504280948535882727516215996870555552492171373876665780824946574814328674397112788048559943317328661612631514856553401262361577375262649941961817279178904576131677715369147296829285352365631440531030475481502984984832869630706517185454675924291320133229779042108233304399791714276623643747439259368478126039802012539916582124434151575148722719356186258841586885573639264631396745703146777815269776803398282272286046142827633284239847615748184324806063591375977438144930292490172485175026372025954453961771167568112418639087669383323887874780584723797184383253959785208071135733378868648685835599426270643141801261969095222199998390378780772822773562563192106594957924907849766591688096143697516668235367702428455323824010446729554768608714605171723148492520314724779751348682303884999949876959986764931631892987636889325557193763744532658199241289103650899496821874354769792047276355572647853841589330151016342451487085713565218327811473357695817115318956142846582029737974384493954556896052597222156983417974108121775666241982595789637547951759664461725453208960338968636017562139201513558283891028237384633653831271754258159179718194696231746848192591981999323557482366554167221364216436115335188829112983853851607899896174615250255680767935872333791236368066371953415769708991813667226579689868257993282146842381126888856148741962552554361175323430278026135165521187664686664535894520345851931170206775459566713696992184464279988435903912789773132016262053834451785081522510948555386431224023375077454591924186772615349735828691574639669249215257738233842991791645486972871362338539954321338812327894602322442919546893271375557779819120174182577556524598959775608597456071559810567131975266319911458836941693281937747262884328947226877895267448555595345816779445314865566073374910518224832531303161472163718217789777249432135661698036471046739297267446636856388622864646224792152791117651672371622134174277615677333021834252289369427363788389819683506096197449852572204344216163695161919070587862115138568655924960211677901395424895757899654661474361344225723365953446116714472697588112957219727373985566906444939675525116192373959281111680629692214137647686987764144182662270735182354212424480775287192333116230483599798783138653386556916149454625366287157267667592107819129312747299773546675837357469506028543747356295468283262864721374893186367048723953288532812044195331335690373665102697176776692575962991477368315858688966516465935286391219977292476670785362701291439536392311283015326354426536365757496062353471966487527676135763511144387948774445402545258520216765303590307754816349485827913767203368645714889053152460958618809356144464111772822681826173374143203656352591418849859170569120998964327921392788694370997083295660302852951767137015631280239171638493927062369591583985671669551479461649194445268797895424162723114577997643477536384429176419109233524473492048159110801868758540652843848254706196865518916571636926453629964934332841854829993666249342168280853169444450863723413891652110738686581196517528323897295779811822796767806548639918273792638698792382765045681439174549372017877958997687779259835229744691542017504165142635906167841232487119388876401316498397325587511746253044556850897199775094876263244131926651259650205023254043372133196026792540392092514678285527138183806467206739898379473246491870418076345535658593871093416831337412797653247476806124536331143621319570974868105738181697402552265375226766323619382756547316152283699718739559786447935466434674351793158734524224434260764646902218824555704246398751192731126225656781391342723697148494477675317863754584372952295641531043903067649474958620863171986621189741533843911841883445948688125817883253251030461075385519953168282573157745121845184540855417655549671736758870425522177478119964265960612544773076578639224775603740363699459946103982962536478281585016668915312127274963697016794438292171211457935785632044229682435974971213193362947933642464207978815868133690639086832239203661394560683597924231532837659247327820661391867919567362832248658267322590993698719485171444696967248321501467736650729276837026801479745813603528795388192387577771278280384446272181439632189879695035748731568033281475298673691273572464958019333458883158734085668337225346449732978914642915619315935787725383278057148838324563418315122599651257784192642930566326832615244321613553215230488383567186222750349837317858173767581744684868266851233613724263974993771948191818311459827492223465861928844223658118115325954619468119844543397098745259462275525844696813996322486122676293364655785948898057256890241180824152723747281272998224199092627173295731662367929656684193678436231675642939931778911549213461365714117643919631733952268389404179585796423361874266447431699397329768907749843951563614382510376064216556474293253227395816808124169562149685817678868676504177477794152315523474402271872814579759463665671359365425707869324758424158773860395052854048178881345441767461426720532624237917381323729412407119716328288788437672125230995597482844543223645925685165525894378550918169685545122498768387236963717166483549349618921347485466398686314551261767533426349887681562889747908648782676936088233193636352975698604066158999565877132819232881325689815961426114198662336864792151694490739687161719354645639623264998535419262739909939492916301210136299776645464522277571884438755 diff --git a/src/day-9.lisp b/src/day-9.lisp @@ -0,0 +1,85 @@ +(defpackage #:aoc/day-9 + (:use #:cl #:aoc/utils) + (:export #:day-9)) +(in-package #:aoc/day-9) + +(defun repeat (item n) + (loop repeat n collect item)) + +(defun parse-hdd (input) + (loop for cf = (read-char input nil) + for ce = (read-char input nil) + for file-id from 0 + until (null cf) + nconc (repeat file-id (char-number cf)) into hdd + unless (null ce) + nconc (repeat nil (char-number ce)) into hdd + finally (return (values (coerce hdd 'vector) + (1- file-id))))) + +(defun not-eql (a b) + (not (eql a b))) + +(defun compact (hdd) + (loop for empty = (position nil hdd :start (or empty 0)) + for block = (position nil hdd + :test #'not-eql + :from-end t + :end (or block nil)) + until (or (or (null empty) (null block)) + (< block empty)) + do (setf (aref hdd empty) (aref hdd block) + (aref hdd block) nil) + finally (return hdd))) + +(defun find-empty-space (hdd length end) + (declare (optimize debug)) + (loop for empty-start = (position nil hdd + :start (or empty-start 0) + :end end) + for empty-length = (and empty-start + (- (or (position nil hdd + :test #'not-eql + :start empty-start) + (length hdd)) + empty-start)) + until (null empty-start) + when (>= empty-length length) + do (return empty-start) + do (setf empty-start (position nil hdd + :test #'not-eql + :start empty-start + :end end)) + when (null empty-start) + do (return nil))) + +(defun defrag (hdd max-file-id) + (loop for file-id from max-file-id downto 0 + for pos-end = (position file-id hdd + :from-end t) + for pos-start = (1+ (or (position file-id hdd + :test #'not-eql + :from-end t + :end pos-end) + -1)) + for block-length = (1+ (- pos-end pos-start)) + for fitting-space = (find-empty-space hdd block-length pos-start) + when fitting-space + do (loop repeat block-length + for ep from fitting-space + for bp from pos-start + do (setf (aref hdd ep) (aref hdd bp) + (aref hdd bp) nil)) + finally (return hdd))) + +(defun calculate-checksum (hdd) + (loop for id across hdd + for pos from 0 + unless (null id) + sum (* pos id))) + +(defun day-9 (input) + (multiple-value-bind (hdd max-file-id) + (parse-hdd input) + (values (calculate-checksum (compact (copy-seq hdd))) + (calculate-checksum (defrag (copy-seq hdd) max-file-id))))) diff --git a/t/day-9.lisp b/t/day-9.lisp @@ -0,0 +1,11 @@ +(defpackage #:aoc-test/day-9 + (:use #:cl #:lisp-unit2) + (:import-from #:aoc/day-9)) +(in-package #:aoc-test/day-9) + +(define-test test-day-9 + () + (multiple-value-bind (task-1 task-2) + (aoc:run-day 9 "2333133121414131402") + (assert= 1928 task-1) + (assert= 2858 task-2)))