2024-09 in haskell

4 files changed, 125 insertions, 0 deletions

diff --git a/2024/09-Disk_Fragmenter/example b/2024/09-Disk_Fragmenter/example
new file mode 100644
index 0000000..f96c390
--- /dev/null
+++ b/2024/09-Disk_Fragmenter/example
@@ -0,0 +1 @@
+2333133121414131402
diff --git a/2024/09-Disk_Fragmenter/first.hs b/2024/09-Disk_Fragmenter/first.hs
new file mode 100644
index 0000000..218c4dd
--- /dev/null
+++ b/2024/09-Disk_Fragmenter/first.hs
@@ -0,0 +1,52 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import           Control.Monad        (void, when)
+import qualified Data.List            as L
+import           Data.Void            (Void)
+import           Text.Megaparsec
+import           Text.Megaparsec.Char
+
+exampleExpectedOutput = 1928
+
+type Input = [Int]
+
+type Parser = Parsec Void String
+
+parseBlockSize :: Parser Int
+parseBlockSize = read . pure <$> digitChar
+
+parseInput' :: Parser Input
+parseInput' = some parseBlockSize <* eol <* eof
+
+parseInput :: String -> IO Input
+parseInput filename = do
+  input <- readFile filename
+  case runParser parseInput' filename input of
+    Left bundle  -> error $ errorBundlePretty bundle
+    Right input' -> return input'
+
+compute :: Input -> Int
+compute input = sum $ map (\(x, y) -> x * y) $ zip [0..] $ computeFile files' free []
+  where
+    files = [s | (i,s)<-zip [0..] input, even i]
+    files' = zip [0..] files
+    free = [s | (i,s)<-zip [0..] input, odd i]
+    computeFile :: [(Int, Int)] -> [Int] -> [Int] -> [Int]
+    computeFile ((fId, fSize):fs) free acc = computeFillFree fs free (acc ++ L.replicate fSize fId)
+    computeFillFree :: [(Int, Int)] -> [Int] -> [Int] -> [Int]
+    computeFillFree [] _ acc            = acc
+    computeFillFree files (free:frees) acc | free == fSize = computeFile fs frees (acc ++ L.replicate fSize fId)
+                                           | free > fSize  = computeFillFree fs (free-fSize:frees) (acc ++ L.replicate fSize fId)
+                                           | free < fSize  = computeFile (fs++[(fId, fSize-free)]) frees (acc ++ L.replicate free fId)
+      where
+        (fId, fSize) = last files
+        fs = init files
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute example
+  when  (exampleOutput /= exampleExpectedOutput)  (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute input
diff --git a/2024/09-Disk_Fragmenter/input b/2024/09-Disk_Fragmenter/input
new file mode 100644
index 0000000..b632cf8
--- /dev/null
+++ b/2024/09-Disk_Fragmenter/input
@@ -0,0 +1 @@
+8344894997247919706132254734322836346242207378552420699813367551416968491319512518592646626569964818974774915246474191615273835822122155863392343212388744802787509799317530256568863245614923305254301264433187808740258581391832216685255339465627821626616160796945678659742070505679162048351230462662134657336289125134609127637587179556211660248637174420289644745168422036297546281549714924698458874741151732877249461472972669785854652059743054161990184821114157695754917385788865696479538349175585329885343058959381137281419831724581867380443739887240649848497322891016775379905054433583235160808342443451429574552368601424932361247614871595742215112932129063537419107597154373762065534521923013699876168357613257215173576498973275143516765579884554871346649196969343219716736881915813332919372978425457289315465050792727931114482510927152306049917116203314407165241180253046975177829098509817168556923844454053506150402070986528277083357373192284318798115868758477312710272286968949561558747783545346702177445768789511682385238564696917682372236758392745584411349227834926896633403087456985715425934058858250394764475853507528229071851939383621481792629933878667906284878978952571939423328470793169422018932186215466816755205244172257179759441239627953614252511392161669478728616032624275786479837918134323306153943213904623341544476241748937683319124569491629166317588063205760641948298341226389538843931096428279691316198655935487902711173289234237874965432867729988157114833613512833721677315222145552241514356668773229416599524726822943338163359869508668724182183371299797566779143327945481583361985720626090649592266346853696546371595972364395978644595279339213495113764756151995923791623523831066659719963394897642771499479751426319264195658172779354688586274370705645805018842028675628739369718951257769855549399554252756163658262884535172664478298867172112605274494015775743793359761829419567938312725097941247923814546318206777436058622760309317361650577362671745809282184098485097275511811824542364858831241020763830479122616066184693717694196456632460267270818870208099266528101212696746801264565893423367732419387472945566714796546295475448386795883079416961256624245633516217267658559318993394384091698853692727955946123829533932315191907552587652197659238859364847465396312763436296572051884046863352492568181167697418391750421990107951929843274285793781233572631841501239594434423797264730325846441268663014826117806310653838634551948576815789185676235067998828287091282240235360148989699931702454679776941344239174833865461428542129774513122545454477345639816612847021681414461014895528749970122833781915254795355466237210672420522419362214458771833088784516195557276082323054496857985769842252223947403242595638923562438862777447557145868254376344413182467179877547245927663563534823835320186844969246577155852965273213788755544263195154716384752485997350446216262511694992616744622847791941672112973235446567188367475360357318822392272885641883523770466256714739976173743980816271905235834473613338326551266986635496106378448940779285252478283212935255144386466939174148991636754545825158137076879239839057756443996167131486181074658428636349951270885161599797567224274890431234597715461654993241129078451727888313533895509575219572137264369374416920908871782546369144198991218649216032376225716090756184993418275766768058167129389182757513738663957110985078233164178819232567836626529177711814916925152771411657621524477365336459364781212474336763292032829276668110652937904039414654916710506897663897788624983288392724267699305992939991191515241117247957351213374468639254333058667240142879254847543516409710812438484652875730885826496019439435184626304920567470616525569954439386147764389618259288301694821733754528272564371589689581324547183356767849376158996122178812756422922365345760802064579291495549337611641937114391372530136631511183696546203382178741676245899213662599181219279899792465265148264318962032137932924095468847159826227048788449243255846943717933118360528920942017271164354280546079643432506432722253677815104298748867838332121963621553602472848163745952472450833915204264534689938115456825646497161477691545769935844585115881952791588798711442144120226670146163228691622122377084191813953092346566317269262211351346624342964145255786226762437344282255191946137596344295945462955319374831646980148247159752376144914963746894687377795814849167624174239121132177251547109061655569609612308730883548438681369623389371881499139051593311964033293474795343768113673422997354186044546348203151859523913462255716772424527367478838418883237942888367173588809125946247998298642674308225937821522878183152371062148146526140128979878773486356709011378011599731697637736984321044693145574422388589598671437083351096321633241637891159924652561834633523613517419677259885379151484846527569435186157071933818449566474793725614497187593626448599916961391632593681397354857591498396415531233937477858543594228734282814328439359358667579728876281543909970499678882540634370934942694518798158632251863332161192454015298943418470352537507891711669351510491929149341492384658353489111675432141731814816486810471640204438893552455716895474288350595695773461425140984391648096337354398582302736948020432515373150781652426562247229765682251446519461805284786848162774288170204566353711151163371347563642135729387095349227937940797037848831208064371781986678895075601449715099566198594229298141336937734820465113459911227920817092233082913636259867937623661853802724221849163931728541156411219587427492621083734820695294784834253297679681787837395220578338793028957195134414174864329958743138859234495396628125501542815114266992646760562855865739516774793021249323872171135766544315311856209547851284659329783441314944377563384717996016232011886143967557971287938551987245334734772051905269476384145322199271431844444165235972679776862886218280201420903971837631942082934151884935885416153022652657823529936237618175514592459921126312443254321527441396386988167777366816836754825483142476275134649881243011651755841225683592719477636092841270355927969662556898509859742911507445637377718399876535972098812751883098383631683980704423139081646299943264406720383294252667435564818026802125261991712736625814965623829837903421201387285083122618989127982659614818401192259382586168248885805331245557997340521255782733888156471766709982979753915925907511531728273341702248597176563551814647193141222429888866441096437830173630292638442987417232406410683020562192134464464436975367408821135979363116627210152184663967303765505723539392459254807285497331794783828292956795407859599469108788156181371133853021491993155569944472112275701281894785422045491844426723706345944759222719741250224761128859902764622155673964396744685355612259468974381660207347145224164761812194291245883223171474553918559230661639624922341214901739879617897879325318866074625740417869205890797899873143428751778435507487586060107911742185573460344512265633645121413961261956968461131654215646378525995971497342101733654767694089696315891656858925208924862889847258812765516277649847277448992975737481688752408164459611764410586297362535363829146929598589585218205066534911414872851059253893919060751065441172627171917065309263324045114713623192141338679420486344894399498564259487491312529911924366624856808055113441217232425528888815118288339090218070644096878812488855858557102541757860938728755223256518843453606524923550782161272450263097235223876685486394553471709611464684671867438382668670921193692159992136856353544521891247569228403695114774461151157118612071103526764114156743782825374780639350744696988848822741677496109010841447745521895844884987411676512131775183988760896495926432899779308757172073926681944552932351972233748359316063452624364977312869926185857242344619483631744986621156616798881687949355705555399958595558818789264181276742145768119555117710217715639779435828392213197644597554242172522917428989968661529570467150478073646123471296117727375088112576153725961995514225863040456138146820481125727141269112318076906387344836753770451954307549764676533255445051607883576570993228237714692667781555791087909553364250218950147265232438497352574217651521841571664888489454789069562997721597468697235879569355746046462477867874512297598439577291546320423747465962223072165411797941806524113791469174248829633923685779606193909937708268145733794921285945713329284687595236899472209246371829214164969748628924562633934987951753378768967034701248919532612227202119997678937930967529825665443387492334944792555633694267288091414123648382756649699538396999415840786560205132981447461189583399915369861016187338242664207892242468875036692022736022186317976966727234469756817160639195442118391690802035941391993617267880972350148795986950903920263938909928968974433443645337517273462195566561963975203659283688227792445753142782585723751481917441996077256285747275548455285074886998674130487967825587889027519257875092111727868222183136428652121225385821412986253641142927654169544074623872437972253613656229888221304520664260443399358929211272982824417564562950857165142343252392976831988879214811345988604867819090525196913585659689568993964736712917439432427141495147149053817733244174278032209761581361411324487089239214565923387485174617749244864274557744591784487322623656502948409512417588398016982472162271768412283099466683755050206685889836824868194068409554648265573437953828389872189931944035566263625157686449424877904744346991754436871374579472656239172797849371497443598592369083895680526059178338848354666365142861915966734937839231735444796621875454912317673876931073231762346316349069479337633767569581168275497393145342765935324332435112231947597722483582165285871975581493397093536790681278729385231315976598645437254134303444188928856239402438158538896871925117692565439884594019698088261122726919311188149484891576778536613257453623207794844166557616738582366829311062496466335676495693612675515298779321929868794580528246558014721070423017508036353144631943533752877566792746442475435481292283424383891783833642774183163619873925963349586042945360618950737342297486709369181558813521707753418177113985239753278571771516473817151022501418124696114628673149884075467151792128426345898917951240204121739059307711415692862431542127253683281751571443454754518557422786162440877830117524273117485125812146874457418634397976221340594067811831723381698318934867423347489190829228195854447289608821987751615787414410391579135738648766758292686554177321355531225357337768865842468678414767611672443684269662237773502429135754376885432310586794506931867134796782221859527491745010449459423946809514772116576846135780891780444194904720171857612842989754754488757727469885608888762139426126278640621492808833644641786530984585604767988652608340751892297037923738707931745489661561299850423916331256678829659437602999914559102178626278665173712198774096721563948174163315965219347526165037505153271471905731992750162452999273279898552887676460921252207254659142154140408873133474796872982682542880324691248879457295271240996142702178287727309884828343347336428145484339106073991492405936186480924758621086827886354782362045616915661517851912105949698324719615256113929138938665877765615667677854989418612151552937159255677931433437732312597280105571149582769413966981923182346466278065225733109639821710455284182068887382332054974616927080792359911642219129648648172333628217178388727431992232124437667420786267912275954430392443156751656210498788217644501095127241773759906155166960259898938114149999396914257834561673341790626360849288674718868936149449244789423337187078331239579395823619895157477865241331332630683265167177686223209832342913122556556266338113133777775853686828284620207566332165277079345146128956907311688255547384883993964627813597208381811171768140457861107044106343962946356485323099303523216824661544759251549130226524918326417515432678611415827239564385287868709074948145776343394586579265772455531577946016414148781060377436259461372213132983935111106686961574569198693253373179166592946321299818417985112590512499605734814172363027245660839574646162561365555390534391406278221463833915561091335534913315181045591119745892561173844195132591743768481043138729169911985519537710334075285810503546232240352483571549876112741124603067903382489975436373794445625121746773751010473815899527454142992293952667831329422217964328632176749948345825228944235254169029649381462164177840519815936146642834468386452435602357257767972984917161639467101717395498688321373777584831311168833696563665966549739298861183212722844997439386953845528813161346427380113944641412701345858394351068717145108428118087532876448330142094601776638177374336387587632963566880234582909354916611777173852066205553216251507782781754534115299453351526826979307269874784467453989317195580889340191526779181676014816478223036988454669210661268294845677799753043547812871687668057845311589495599769342463394270432553944428928774754689246017238278314754538783588894902170918768773870167481758222416766646489174859296393237643759161275073684885722242589534585474908688567380161914945967737739352556839824472430459930874039556212868670167273298223766854767398876023745886901922521049959661867377439499235276392492488737512436473120752796834781812863497710287999522721516474793755631243183353396657275828572255696092535417946266746210201275946628786619898533882799962050223095525258939373637620991444738791646395125232936426496758745277437284904886149553243169478692215999141570188215506839523958323316579423754631185767919488994852287996939441348387321868975789383159243036968459556026807884163447732497489388944826174667259721863548546037406719887572132168795019168585492522899929384368569431674024926213754193614236102661718544285480444586265567879538789856174014765296543897638785367979773914556723673719234565471952778945995313719224726627873950975128771876301665564150159487881156822188814451948921612461766593396288156288604334369179489222743521351392904390945353909230537068739360898777361184611421933852288091657214166364435596979175346789401612605499177111928691693438164363424618801745161057418410664428775472973489973814637981612723389234119743805780892591829088578869455855353597484263844833575298973996706854312079933653201261152235482763768078423288958292407143971512123218782956488433947393498749621977443337585824213614165142696388559215678289499467211872204663906055426824983715735766917395683853698999419750231250487531285177372426601564799581245224698786688152276342325310378931749671177161563780701333296577525632173520697623993789418234188142403515924651789631326116185195247744805888115668601244795776597696987086267380413071749097285850622876577564188888463131782356971596692997567898904277405169488069604522896451726630816786387092613074633133765446701679294896885592665935905032719470467690681668142161332679183729102627728172828655963715116653939932567367552277982794596736338265665021601035846625329222675445791022414426662935613816379990785532591139949232434219931033533765883783642273381921596961715366278136101451594543787171969563651222851738239448343178358263733486793195175998384062777457869620996070708894663452431623378478915889591420777921391859472760915347393784494746654446681118516799802642219774524471655980528269498093691537972010988396605425816053168335548455332983132858135736831548525265894155885019917995456555928573496578467320334746312133622226919688732355146670548477767762596820694783893077372641562613675561291778463339432530876738982474281688824436439179307183405380526777659463874998386963228764494473402866134579876831326858529849616261433417873243794614354391112379832734146262319540955572324126445696542023557366883598224228917244196273344195313818296246504529839492583039323568205475597124796117495648614148934821563450783225281928658167823055248215175765997099901257925674948769409398574397468688688296192018463189912839662186792196164133526556676735799186649124545310995840136955713170432266747243968331204682114893374482424923432247592776492362675098155246214358537538433012178113163135476026949521393870283097608064283940336489472186441344391134111297348269253937732770847767132718709293667654796867277744552121794414855649261334402168382444114272585525149938178693335572293143503118727724736829683942302447357314984741747193691079809320584928381928409248856817514396227567389686135540664924559596676951567223923638764032634629917117433879794280181943373752537879114599947482266596736314941097289450924633882851395152795836416175774522313715903755657798516979572566313555237239958272869941123199665674566361254688325446589148185234266173466989107363944192798620541611209019911974142793433556892292319252348110311119773494859599531018909999481561168763821479215553993493493997203442573090643927667894225582161665927917197867812256212149179054772275523299382385732196957012661024629759802732628769577862692775977616645155978797407118304080311314193590521193463333299129144219448461545235351398203292811131997519403253506075826118779646513631176193831335765893587813653690324995214319967491299829107352403213752139136720559138282559272337745221943843533611492151736233769556183542369341173927782139409069868571534079601545891962631862598987811560966060482871793345669692426333317242864716387654588531721777132011617119523098753310916621288840967062255145204110925862115166971771381653982733613969715121137975621788502690497799742497942647274968441898433849925693854673788237614922425917211839757446928161133465264941246951276992366965302962524377681758892756498070769112953691959849567936931074598428432662872798265296356676146324179073799763612190325990956399226256756255495413427058182753252952975335557826981710951465612935109567962311319031694592419825765392348854714651131984818258806258181575158370204732749625559080959032354611423338717913776273469689994622314781186948399943528823842675463052838864778278121278651015998625221840786252259282932284892386696830962462994994396073736270729946722428661473101958451168628954489583691116336039429951125017687726595494373671163867328688864552762960481137787491154756957391361537368581738229468838645380396840174882701091537972907884563968907964972899482612357011836678479788959229844133787274312067711365736440281989989373502560547043407418753571976515931114387491198669338942686041307949505461422768734376175873568278374220806757467113881916113686774095788176652379187875658873196827796686347787934489212542288660439090731785642397778877807241353791881085221511859724212142909175353482738986501051835556784027184975839369168416343951902263223714569329911259457831495493771722114494163240264074799479954342791877935417732610651110512221365412518791256495611586418148915286306072142067196869625732881873898517248858602373346653471081567270556369795740678720282866569611618265682414642017824363509025468696415233881742121641761335158415159768195045583616411913894819923353964768921520561518997651571437888124283569766714345781358555126441957472244677825585178022291464805672592081931999464560447884157928784171413165677542979831558425374971619790321511211184327249189875825183853346745852184640936572684359209238747797995557897490166611771682669180395999943078142898182843519039844047439414246872142787979314712840642592871493628533138483191164605220312864131513516082347721511768454875639984114746874915398899352926566813676662299518213064598618368290924312228758378232493858436388696532863712603919664361903350587449595188514084262292586957392854154239777228715472828139912048561994661646424153792690346750862587511619515984481188389138769883456587397820982248377657793940616668936634572085409516661055134380321215793642209011492063381915753332198038652832709441189689562589865577945419416810854853867974892154621485257926766072507298823585697921538473481324114692791881875699857794215917558036462396675014118336182570206713107930316152611574942351385680732132948932911432143124414960312845127143135299439861759098114576334147375981265924804512151510949430823637365643681041775623581475539198479
diff --git a/2024/09-Disk_Fragmenter/second.hs b/2024/09-Disk_Fragmenter/second.hs
new file mode 100644
index 0000000..358ea08
--- /dev/null
+++ b/2024/09-Disk_Fragmenter/second.hs
@@ -0,0 +1,71 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+-- very slow with runghc, use ghc -O3 -o second second.hs and get the result in seconds
+module Main (main) where
+
+import           Control.Monad        (void, when)
+import qualified Data.List            as L
+import           Data.Maybe
+import qualified Data.Vector          as V
+import           Data.Void            (Void)
+import           Text.Megaparsec
+import           Text.Megaparsec.Char
+
+exampleExpectedOutput = 2858
+
+type Input = [Int]
+
+type Parser = Parsec Void String
+
+parseBlockSize :: Parser Int
+parseBlockSize = read . pure <$> digitChar
+
+parseInput' :: Parser Input
+parseInput' = some parseBlockSize <* eol <* eof
+
+parseInput :: String -> IO Input
+parseInput filename = do
+  input <- readFile filename
+  case runParser parseInput' filename input of
+    Left bundle  -> error $ errorBundlePretty bundle
+    Right input' -> return input'
+
+type Disk = V.Vector (Maybe Int) -- Maybe fileId
+type File = (Int, Int, Int) -- fileId, fileIndex, fileSize
+type Free = (Int, Int) -- index, size
+
+compute :: Input -> Int
+compute input = V.sum $ V.imap checksum defragmentedDisk
+  where
+    checksum _ Nothing  = 0
+    checksum i (Just n) = i * n
+    defragmentedDisk :: Disk
+    (_, defragmentedDisk) = L.foldr defragment (frees, startingDisk) files
+    startingDisk :: Disk
+    startingDisk = V.replicate (sum input) Nothing
+    (files, frees, _, _) = computeFileIndexAndSize input ([], [], 0, 0)
+    computeFileIndexAndSize :: Input -> ([File], [Free], Int, Int) -> ([File], [Free], Int, Int)
+    computeFileIndexAndSize [] acc = acc
+    computeFileIndexAndSize (fileSize:[]) (files, frees, fileId, fileIndex) = (files ++ [(fileId, fileIndex, fileSize)], frees, 0, 0)
+    computeFileIndexAndSize (fileSize:freeSize:fs) (files, frees, fileId, fileIndex) = computeFileIndexAndSize fs
+                                                                                       ( files ++ [(fileId, fileIndex, fileSize)]
+                                                                                       , frees ++ [(fileIndex + fileSize, freeSize)]
+                                                                                       , fileId + 1
+                                                                                       , fileIndex + fileSize + freeSize )
+    defragment :: File -> ([Free], Disk) -> ([Free], Disk)
+    defragment (fileId, fileIndex, fileSize) (frees, disk) = (frees', disk V.// [(i, Just fileId)|i<-[fileIndex'..fileIndex'+fileSize-1]])
+      where
+        (fileIndex', frees') = findHole frees []
+        findHole :: [Free] -> [Free] -> (Int, [Free])
+        findHole [] _ = (fileIndex, frees)
+        findHole (f@(freeIndex, freeSize):fs) acc | freeIndex > fileIndex = (fileIndex, frees)
+                                                  | freeSize == fileSize = (freeIndex, acc ++ fs)
+                                                  | freeSize > fileSize = (freeIndex, acc ++ ((freeIndex + fileSize, freeSize - fileSize):fs))
+                                                  | freeSize < fileSize = findHole fs (acc ++ [f])
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute example
+  when  (exampleOutput /= exampleExpectedOutput)  (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute input