commit e2e231b5acd86b067379109f9a877d01f4cb1e62
parent f4934645b1133917a1f27ec042a2b338a0e19099
Author: bsandro <email@bsandro.tech>
Date: Mon, 9 Dec 2024 23:29:29 +0200
Day 09 p1+p2
Diffstat:
8 files changed, 226 insertions(+), 3 deletions(-)
diff --git a/day09/Makefile b/day09/Makefile
@@ -0,0 +1,28 @@
+NAME=$(shell basename ${PWD})
+SRC=$(wildcard *.cpp)
+DEPS:=$(wildcard *.hpp)
+OBJ:=$(SRC:.cpp=.o)
+CXXFLAGS=-O2 -std=c++23 -Werror -Wall -Wextra -I. -I../include
+LDFLAGS=-lstdc++
+
+all: $(NAME)
+
+.PHONY: clean run
+
+clean:
+ rm -f $(OBJ) $(NAME)
+
+%.o : %.c $(DEPS)
+ @$(CC) $(CFLAGS) -c $< -o $@
+
+$(NAME): $(OBJ)
+ @$(CC) $(OBJ) -o $@ $(LDFLAGS)
+
+run: $(NAME)
+ @./$(NAME) input.txt
+
+test1: $(NAME)
+ @./$(NAME) test1.txt
+
+test2: $(NAME)
+ @./$(NAME) test2.txt
diff --git a/day09/input.txt b/day09/input.txt
@@ -0,0 +1 @@
+9371657678826024995120881287893479262072403691149564376524763927552259267360711942931510637284269253338821363644342331492537748295497324648569553340135785853412161260183294194918709443386959501386539328437053966764886789802885663875221426362659468916483272132646385079963628303211419617445497398916949937276422691451421762323793838082429828339284371310541067233345699764378583519365899379703720378241252023143210289014227978385883526312637677309444994916812679375950543318979891361993589072629757877179645750496338262216677133867671639867698996581459898713579995222880862048231094542999622556601379578412117117781974648894877657998817334994571130198790334716493587316195885279945270863519262691596118908724865937436964824144341178248218994055344351767620636219128696267643977942192843246722935244298818687246964881812995107834528269538145668545471055137094132443746075857864873766749947159427359430347499728081438721685937905449283151843068682160376951437533916367542198154175977924513482237575548075462917384791765118393327674522408975884943126345549784417325102396838194614984914245437576715218386965308780489351656660962913367577239689117940913925558979753520197936556982369524804542751123182948946213548917929615821389156929142839153421731432705396523269221081919294298277986298583494762064715024624389873059198783282359805471754377785121748552928436598393749555234663137587856456264948413046452530297957642750519082614188589473233635745073473778632126155456486245504930809968703069613972579655423893457066755217101139624411933693801390536727699433175793214846879882256453365493311393871282789365152991368593444582892666776658817910602389293993744059797283123727689028393281311324437521174842119652933440777036105693976177827356241047251874489237996926574021272412741097774130538987319990968864588355224778619053625677579847847175226736258010239871658914869544427092252499671059793513282986443475104096799888914922511556598569588574765585501834162639194746571760211928247757222481211151794283988881217925339898516969479635476459991985141450273399331116319458426223945895497290429562211227142742291091422259624974844027362666397325887161368534252096129199166689425388154740776234261994915671595587584841363497747945499399819361538969475211318335975756939552792664441482329480284343526626303390436090449311584512522034123629872082683039809064851623449335817115656973492296707599373661383916477293844874409841689270166432119750284167206613936077129156897226909354391876629328464796555631324161737742168411717627952768287044135772148959571346913125154273675156349565197745497964107221363181476489363260682249336455348786129814796126847044508327502952892912454839872347739943796698504131883073892691124462385781789887481871423165145137816256832189254997173667754547444250145394544440591727744346225587943553576480543570513343593246145788661848536122919772141884375032257611373358352490912337421374311569747052537948393975476810941191489443792062261652413142311593548276113081142339437578357930437042926624816916548574245312858135992814693773718265649883244667123840397472617634403652305661781466868079978872752649818789563481849090791276197887921775913381535354156686577550389033944734643333158980231278739680569852175780468375295187137310899224885127442591218126127235168755597225697537761185306668751676726143242615478265909113146272182930602394545495311084433229478245832073302476322938297713758248369892438322232829389827477072454050223191526285948614114320955354346099897052877229953832397560825621364986949647743130844722407211447346425261715571617685822415391676587999428644473297794562274116342792834946687485429565396548168714934211288869512692706034483176354169688439688364509259888150161271745314653250686217586068698385198261658329976573741049891849671962115792212392321219391579258790111874333316724631348641944814923532932515614575435063457943436922553927254995947850931392506735897586577621136676213991393180792723817882149081611825816896811645264388233787371417654797664434956548794394146480316418112226151239818989829398399788731260572433128599377749853262335781298828219540615375545787913474906912709310185324497214438959496216755329261190359719821670103058494722209679925256319013223272302182413075598248274710515368125092817417693882848264711099721486958432378577789748221233299858538723858657825545411786985574828788765463755832387021949861802154732867331630238384759029525859853329383972583146426716756820188857755627361927523015364577463144605722937988516379752167122139788450369899645459766468363378853016584821708080255997855169893085837445215868601774344412237577672315356277618617146284957080196532591043283855922515548428183060125360416162285024436953146734478595447367697080618056278588574647434352633863807235961339133259715543439826422838291813488398143365445714164329541334842938166345894242206173249434715392354410461999709933335177697935108744325077733611227196779164456186109080319443177464659435219699313032517640707677236133807849954416817248489759176098604354856681802518885578795462408798875296283420803375409715535751318630127125105259583388605314311032169351934259509064883082971043162526325031583867723488803197947528776498192326654938141017885940762836809085563689491192821126983530857815916573832343715074479512721547585112546760744460102342695987958423781664573035502587616219342110707895291612658771687665359035428575743194238447767438389349456485301874205896941423113075167787264283365641645996243272529143461414304343957855289780912858962546275184517581546160999512856493297516343919668242745315262416921470251371959953631454311459975937302488427795809486177130494175762497954762182120804697193356382798317812646595635619698737812233556648159975357249524646756933378123359377349721198945748139377542571171425686355865416963172422285512999712135821808477311285945554749520458449608272351977716839451858984832483553117965108170582598216924997746628364198028789985463711419528538669898727982375724435922575446343412036558461611294179158289421216631721297539895452214138528303599925959479548879212173291177317458655459622715661349679637748751654739080719485125134985865764810742593552033122888223325566786673974171526235412663292482992845751967499292182802932582895279478862117504595427430802255469777477291623160597062652150892647617128604940315279155829141879808814689372608848276192179895214966424042357632417350261668775344575038456956946546441427778097268516492516855268221538893868467922386428517458253843439053798132645454421981649220279169431710813182322213556199263890646258532694341069694110276111533531652120804016981055279365589021938573188132532369132671112799738952136571612411764070451991857385991944409678236931881116502056786336124857446682123962474098315835427189429686947647241792646939286647245977576115894636556285893092766697797280113977628983895387486262357089901186454151606874973595307721235816802596977563621996682698485153675835604237154953878916139637772359152952782915236597434939112277566717615923371854151430807192228174688329138526994469353130984813997634742446375858614332359740547734876917363912618379198594307793474523722040878955814296358730263968402446237341426764805751264141379143419925613650801813273278349483371396247177998260977385962952136996808569226456513455124832914091605558435482522042407733384344152439968813189338542225183782128694822348359521501688444550387768177488915115557673209088945729336197657922276884683297602186762573713853481924188933776185709697665875605891762818892762447223905349695873623243752127508016475384326986617367933326709187403789778986857672848866592392678139848682429652306098826337114797702737667831275886562243868589869965943586552667263931769264111554829645455155919961709234388651429391719638286912794543764330801515895462479744272694939269496024891438241629642698784380644748135148779781459953878788647027583443695492541038117873847649784928407251157374925275919822566495569671402637643286414592445599695880638775476743138212958988268959154694754188179931715119839355499488796791699837453374732156862188706058306692144917773831925990333198712165751524382372323268816653807026769546276745984058735863919376773726686468619447154994601933304116243665754598303828417246146921763482965086484419225740216325428517729263553678652628904750884714972127967447303821736856189436792784269575932755439249209470931170334582241875315479269076876910936369398190732077834572336859436661902811551961803273422569412054946748859866158591474815705374289590404928839773591335599936431490651886745416752998355526645622544483458724292050942996393516713493717220563968983549623150911955203177503790796669634033167279326791297727426166167781954124825541857181932486843414185945649759429947117783852249622632602531257262297184589630636286361682295464751119772558458944892469567673388624128011622695529454883499974871851890594955253183689752675816623584848044179475714743455569604311731215211070716593607283558112881591917587296641124287793235145124556866557571872188611544304365896234728867778517752025388627553373262070323915217242928220302023183736524550669961371643661310459728809584638612528057954798973322218137398549232363765814539888195259553532901620456995347992116851162766421594462260736138229577149058212068264959992814735338864725849113355646107548594732719071473375979428229285285163298977662553282460261912421565904333459971386028846957158175423686567494978416676097411433635343565557466421518861168033227792967912882731213952879927295924452650446357909286903984881155849781146528811299653991685045993756128241516195774480966192903153868875217339514981576725724217554942617048865269682366549775874756531712837283776743967997352234499543838866455712257076951884161880679248276096343567525570928752829050245992198617811823533012399097717419255126324553396271584950323677141138618987928140864315802397169130463477452959512490364010202752693915603867218866234297848672791722874116301897327230775927213294903366971796262842292847141792602835191280642311263670436595674624438444101480113245326687945991276933775344766089158258726163817839326695231429591028351864729584312665797472791079635566134187873848297629868295554614984091549173759766616029428293775697153065537211295966505985828581835655132534398726689723519332925453159172779174471151488998524861862098241312944638183893697377339152213616133921493626873512416014283934391258207789848692949254953856879177843838549131311599481451173346133433102292595712631880451995917842667182668297518578973389574495514211762282549883708513262559262679705584565412817591953839444494253696819236975568581164205292458855695367456678168235411338566885383376518463424387249918575262553651158061543644347417259282663161265591876352835549645361632436961315969258506548639332263548271254205347477447446837209660932376847973946024569067925883119341269324675178407631981956368213707677567358549348593995199592542786236440205884647120217119537612509089566973817582359763374233382088828621695485701574872599241328998651687216777455719235158574961222985397287996425320538996204648704872544971964629638371361390416793323154223497535863438242757112612634794096901381882877973014238797448327409536359732721353883323554276594750817960776683274456704153205535746066154749556088883092753720949110476459218611583481562514845427649326866471204610492710991949295062535749491658134770291985504016564399298114848593157210813236619770275447818114108510595156707381853719676746919864752060394830484948407733218345896189252629123541176469454951933092341980364985855133289060431425211863849952128977813445744057846120131497999912308259498348297783524238437031691712926379226353155867464999764687888387346329898050709279409862541475368048551945889352136376682110989951625273416795796220206024165740538270175068732163932730451046603958831318292027195028295880872369373382551092534583854017187063978373802014433448638995879545104055496455864125684374763055328691537448313879615097872462316173689186266832119814973345134047122476688763504984155133888628548628616126114132766950697023907023173680706946802039124422862883433566598197407693308919292272505588702356868843631077656062375959928143135597413640461873413711864810353860723966101510901781251382383648897517934134684933102096913967648053273353637537253424673044927712253719745980651842718491786847867022452284422517112716129758291661513997313422153345636475263394618437133633943988522611208859173344732962337731256383279910777356287924772716508076902823789537324072338864406189682199532322983973691981123813384639579899211229898797151492126743432643314422528868979246548980419324316468211066109141847587411299545783241445212524391420175614217548265581756088628364672680904387282039766272245526126298432059133621424058911376163370914395654117242983496820767015703080241228404525738473636998994084658975752321913016714913564986216443572830233054629474544776235992389285108482746466931499376379408884919586273676996557162572149256828733511326862611451938245369642811554099499639426816829345978151724937975833262469831388749218885296857685222360344458253595907075688116227468868634661812665349424932161588431281476464674297596558345470154515443359444066258457364653702774338622206930458135484357409962125590108713333690817783352365662210552386924382507265653778144088728262538710954493603049997681775965514793164941988540149041312859409821386261779353251931114042931024111875809513324080567570808375501584596017769578752789618653685780639170216485866219319718961830424573374257901423662172967821178627705091647469162978767840496933577417244544786845726322412077472824279799569412305923434474506083207449421537318852305842956325262281666422209129782587361776289590874824753587844865946118342731305089444363984269471268339539924143878333347868415077269198829158688883201551658746299247334290389726975543198851279762155123834042986491912895803729532043372039625481715499126836796043598180984095693361199669285830833860971533622128957765618511954099422764586717401231961013998396884220933147868270497141715949573475481832271930925018712613789133751022149294599172567632944291705442892683985777146275508181442460106845313333417590333627359633524485455611497366805180716893185078556915572730767082886779112436244598616598975181698211122869154230549666266350684513965971101185965681622159861795977529152688956453932378624059716874754882942521117752507772991960715032674458912362566121299868406099586755337588722179773047509747729362235161107259769619184116894978751814775358199755955423277889955435655762518278239572338171131466148815522745611450282220881897501245121074353961206158832287392610847069816081262353819961748491177541289433636086845073783329768554766495263689488714194411708937318655392439354217392969861246658932982789545373655997586484757730561314742587398754293436376462376539276357324025913646426389793241226445375023707868216037404578342514229161115178561555634566998145923326783047132964535398262624902949187681203378446092231296298945177253374035679843822267383227603565129161938726292710598726205963869726508777652659916461143656105416437714712279308795537292503830591296906960176892548528912451672815595974334927797189856923892565655616269979563186382877146338308299914996323861814791382740116979138789728913473072397671572986381021186528263356474932922865146845652275433942214325484536102961136254117093187875292326379670178444364598302078533672826311173852409415554285472478983843146429715493343152191032303653532336484841947190556443789685741264575627205632338617102873304343987830962157962179779780445826722884382069605036535856761937786040101437516846587223817049492963858397919547661471547198822260419745708791629440518666253599792065681034427465723597618932665786669275455584382054486364402456642987794312156852318492943475966086573770385747105359705866912367568329639522579648723385958686941087618279192220748277313150627424985067215034302142539611869341514234381741363478165580135516213944256636925294758397463014461211778459797791307230181494582580762386384578255291276355524728355784244538274577736152804460819522714953575714156060395566949151754747955857646326669526606846178925718965235116439377622519989320985011181999828041278037178552359055813134696276473517718339196328178131631751293440606218908664711322221284791978753895839165504011192023632481853451565322894366836842133398443740667457741662355363396347772822749279833747873365313373402570865918368894221623697940415665877899758639638610278182198965206631668033375841469150338285107545167047893564655575162896573336425491862389993575804155387683215747735870538894101350714813307992987765683157975273803939686477774720244155743785196687941726233618215896178177691992372236293773262556174785909127747457691267178260837774718292274033742199795176467247609137311049139659664574388573126576114553556040729381598011981641174347249770544986242951712683791891947275241618822722783764164077884482856021423640799170223643534277582928518286401233232450182248528498223727446946685367656446885619952784821839856926746690234145699355313956977848178930666226333656187256312533822819468249423118164131684389252694371141194148921314398015165499777281985689803813982346882157726472874463437433201526213687438269196230876825849843119942858178578421423236188659557812367950121477142776244198729060232821608798795253256478225463503690649330547657408995327125641947527462482245327666976160256554296953928430951334327629257072293430233970793678267184523817322352713077749184346467167295984463134095583832974354287733262519508876371657536690543530256582625970477546232060564328489717135981896319696520305486339936569156224931674931422380615215348211985489591265252491963489574789927756841437867643847987533919274931723816833934962837837170839835346730742254413321384829806275415289333993452034787591554391866441249642783598904435559480628562514324999272255916264651911052528884937020861580715040113073519771386071586454751063249662427547209021619833284872193692702174762468911716451633258130847826952690803137766397846155872322176845921481786137603585352185434871432247412083867298166669194266364470204977548896831429533896751737694128644361588754102546212881285177942299397127769457715573985973559255365246829744205012126738428217953485878077186020286879618468331492707765273837576339966865115194945790143199533010322187411439148542473186495550135424475161999035228694816358611416742793987862419278261477481926942084509340969462543246896764138954212917322042918065251478147321401577893073365264686452924260145768867152344436554076904436559021357343546142758835823716816183975837247914387471362752437865252956832092125767351698446829913184538085459657132758609626218891381440142440168372803724552365811527492596442276288350944068185762762040462548717754216392718356369937776790909566449056119673917181781036302215559076765886206070402539267513691840391474357789991892261322918365334096948678311589362020122691879067651566798571445655537051252259835485224580567691438083664822158540268513558921824933506981766140186284579966562029127055278966108481227932546554801655501766505762278612457642807879294080476861905845575724566665749097599698106559395251104652233772168117778763199325837588135032246589687336727561187998785258793868565955533984536215522922479878336253173399259195514072186718143924378362336058445454275810868827693874389719806748387784596095985921357039595323134389807374213772252755254748359153625687329713253330295321249390428673605357988885708711571315208692894258479483724256248797205818491130627351982136241142554541303196488457591232577936296914677671885254729451366887159052549252726958994795828944352446384365991021166478504473748615438696312121414375203726794746674997419424769441892763537677813848704569205314599195463359183381846228608820189733719525945647817180127854682813779970939179392459496270701357789730386974682382145232912764529110189712152821627490738161555353647258382076225046511767996267887688891686719112626529294174635178618418244746532879665013469137821277725089249497864164136152155580677579248554785016979890211259526981343520644
diff --git a/day09/main.cpp b/day09/main.cpp
@@ -0,0 +1,176 @@
+#include <iostream>
+#include <filesystem>
+#include <fstream>
+#include <vector>
+#include <cstring>
+#include <cstdio>
+#include <tuple>
+#include <algorithm>
+#include <deque>
+#include <iterator>
+#include <chrono>
+#include "utils.hpp"
+
+enum class SlotType {
+ file,
+ space
+};
+
+class Slot {
+public:
+ SlotType type;
+ int len;
+ int id;
+ bool moved = false;
+
+ Slot(SlotType _type, int _len, int _id=-1):type(_type),len(_len),id(_id) {}
+
+ bool isSpace() const { return type==SlotType::space; }
+ bool isFile() const { return type==SlotType::file; }
+};
+
+typedef std::vector<Slot> Data;
+
+template<typename T>
+T read_file(const std::string &path) {
+ std::ifstream ifs(path, std::ios::binary);
+ if (!ifs.is_open()) {
+ throw std::runtime_error(path+":"+std::strerror(errno));
+ }
+ std::uintmax_t size = std::filesystem::file_size(path);
+ std::vector<char> buf(size);
+ if (!ifs.read((char *)buf.data(), buf.size())) {
+ throw std::runtime_error(path+":"+std::strerror(errno));
+ }
+ T out;
+ int id=0;
+ for (int i=0; i<(int)buf.size(); ++i) {
+ char c = buf[i];
+ if (c-'0'>=0) {
+ if (i%2==1) {
+ out.push_back(Slot(SlotType::space, c-'0'));
+ } else {
+ out.push_back(Slot(SlotType::file, c-'0', id++));
+ }
+ }
+ }
+ return out;
+}
+
+bool checkEmptySpaces(const Data &input) {
+ for (auto it=input.rbegin(); it!=input.rend(); ++it) {
+ if (it->isSpace() && it->len>0) return true;
+ }
+ return false;
+}
+
+void cleanEmptySpaces(Data &input) {
+ for (auto it=input.begin(); it!=input.end();) {
+ if (it->isSpace() && it->len==0) {
+ it = input.erase(it);
+ } else {
+ it++;
+ }
+ }
+}
+
+void trimSpace(Data &input) {
+ if (input.back().isSpace()) {
+ //std::printf("trimSpace()\n");
+ input.pop_back();
+ }
+}
+
+void printInput(const Data &input) {
+ for (auto &s:input) {
+ if (s.isSpace()){
+ std::printf("[ :%d]", s.len);
+ } else {
+ std::printf("[%d:%d]", s.id, s.len);
+ }
+ }
+ std::cout << std::endl;
+}
+
+int64_t checksum(const Data &input) {
+ int64_t sum = 0;
+ int64_t i = 0;
+ for (auto s:input) {
+ int64_t im = i+s.len;
+ for (; i<im; ++i) {
+ if (s.isFile()) sum+=(s.id*i);
+ }
+ }
+ return sum;
+}
+
+void mergeSpaces(Data &input) {
+ for (auto its=input.begin(); its!=input.end();) {
+ auto itn = std::next(its, 1);
+ if (its->isSpace() && itn!=input.end() && itn->isSpace()) {
+ its->len += itn->len;
+ its = input.erase(itn);
+ } else its++;
+ }
+
+}
+
+int64_t part1(Data input) {
+ while (checkEmptySpaces(input)) {
+ trimSpace(input);
+ for (auto it=input.begin(); it!=input.end(); ++it) {
+ if (it->isSpace()&&it->len>0) {
+ if (it->len>=input.back().len) {
+ auto tr = input.insert(it, input.back());
+ it = std::next(tr, 1);
+ it->len -= tr->len;
+ input.pop_back();
+ } else {
+ auto tr = input.insert(std::next(it, 1), input.back());
+ it = std::prev(tr, 1);
+ input.back().len -= it->len;
+ tr->len = it->len;
+ it->len = 0;
+ }
+ break;
+ }
+ }
+ cleanEmptySpaces(input);
+ }
+ cleanEmptySpaces(input);
+ return checksum(input);
+}
+
+int64_t part2(Data input) {
+ for (auto itf=input.rbegin(); itf!=input.rend(); itf=std::find_if(input.rbegin(), input.rend(), [](auto s){ return s.isFile()&&!s.moved; }))
+ {
+ auto its = std::find_if(input.begin(), input.end(), [&itf](auto s){
+ return s.isSpace() && s.len>=itf->len;
+ });
+ if (its!=input.end()&&std::distance(its, itf.base())>0) {
+ Slot fc = *itf;
+ itf->type = SlotType::space;
+ itf->id = -1;
+ its->len -= itf->len;
+ auto tr = input.insert(its, fc);
+ tr->moved = true;
+ } else {
+ itf->moved = true;
+ }
+ cleanEmptySpaces(input);
+ mergeSpaces(input);
+ }
+
+ return checksum(input);
+}
+
+int main(int argc, char **argv) {
+ Performance perf;
+ const std::string fname = argc>1 ? argv[1] : "test1.txt";
+ std::cout << "AoC 2024 day 09 " << fname << std::endl;
+ Data input = read_file<Data>(fname);
+ std::cout << "part1: " << part1(input) << std::endl;
+ std::cout << "part2: " << part2(input) << std::endl;
+
+ return 0;
+}
diff --git a/day09/test1.txt b/day09/test1.txt
@@ -0,0 +1 @@
+2333133121414131402
diff --git a/day09/test2.txt b/day09/test2.txt
@@ -0,0 +1 @@
+12345
diff --git a/include/utils.hpp b/include/utils.hpp
@@ -0,0 +1,16 @@
+#pragma once
+
+#include <chrono>
+#include <vector>
+
+struct Performance {
+ Performance() {}
+
+ ~Performance() {
+ auto end = std::chrono::high_resolution_clock::now();
+ auto duration = std::chrono::duration<float>(end - start).count();
+ std::cout << "time: " << std::to_string(duration) << " seconds" << std::endl;
+ }
+
+ std::chrono::time_point<std::chrono::high_resolution_clock> start = std::chrono::high_resolution_clock::now();
+};
diff --git a/tpl/Makefile b/tpl/Makefile
@@ -2,7 +2,7 @@ NAME=$(shell basename ${PWD})
SRC=$(wildcard *.cpp)
DEPS:=$(wildcard *.hpp)
OBJ:=$(SRC:.cpp=.o)
-CXXFLAGS=-O2 -std=c++23 -Werror -Wall -Wextra -I.
+CXXFLAGS=-O2 -std=c++23 -Werror -Wall -Wextra -I. -I../include
LDFLAGS=-lstdc++
all: $(NAME)
diff --git a/tpl/main.cpp b/tpl/main.cpp
@@ -27,10 +27,10 @@ T read_file(const std::string &path) {
return buf;
}
-int part1(Data &input [[ maybe_unused ]]) {
+int64_t part1(Data &input [[ maybe_unused ]]) {
return 0;
}
-int part2(Data &input [[ maybe_unused ]]) {
+int64_t part2(Data &input [[ maybe_unused ]]) {
return 0;
}
