Untitled

use itertools::Itertools;

#[must_use]
pub fn part1(input: &str) -> usize {
    let mut memory = Vec::with_capacity(51200);

    let input = input.bytes().enumerate();
    let mut digits_rev = input
        .clone()
        .rev()
        .skip_while(|&(_, b)| !b.is_ascii_digit());
    let (mut i_rev, mut i_id_rev, mut b_rev, mut b_remaining_rev);
    (i_rev, b_rev) = digits_rev.next().unwrap();
    if i_rev % 2 == 1 {
        (i_rev, b_rev) = digits_rev.next().unwrap();
    }
    i_id_rev = i_rev / 2;
    b_remaining_rev = b_rev - b'0';

    for (i, b) in input {
        if i >= i_rev {
            for _ in 0..b_remaining_rev {
                memory.push(i_id_rev);
            }
            break;
        }
        if i % 2 == 0 {
            let i_id = i / 2;
            for _ in 0..(b - b'0') {
                memory.push(i_id);
            }
        } else {
            for _ in 0..(b - b'0') {
                if b_remaining_rev == 0 {
                    _ = digits_rev.next().unwrap();
                    (i_rev, b_rev) = digits_rev.next().unwrap();
                    if i >= i_rev {
                        break;
                    }
                    i_id_rev = i_rev / 2;
                    b_remaining_rev = b_rev - b'0';
                }
                b_remaining_rev -= 1;
                memory.push(i_id_rev);
            }
        }
    }
    memory.into_iter().enumerate().map(|(i, id)| i * id).sum()
}

#[must_use]
pub fn part2(input: &str) -> usize {
    let mut files = Vec::with_capacity(10000);
    input
        .bytes()
        .filter(|&b| b.is_ascii_digit())
        .enumerate()
        .fold(0, |mut start, (i, b)| {
            let len = b - b'0';
            if i % 2 == 0 {
                files.push(File {
                    id: i / 2,
                    start,
                    len,
                });
            }
            start += len as usize;
            start
        });

    (0..=files.last().unwrap().id).rev().for_each(|id| {
        let file_id = files.iter().position(|file| file.id == id).unwrap();
        if let Some(new_pos) = files
            .iter()
            .tuple_windows()
            .find_map(|(a, b)| {
                let end = a.start + a.len as usize;
                if end > files[file_id].start {
                    Some(None)
                } else if b.start - end >= files[file_id].len as usize {
                    Some(Some(end))
                } else {
                    None
                }
            })
            .flatten()
        {
            files[file_id].start = new_pos;
        }
        files.sort_by_key(|file| file.start);
    });

    files
        .into_iter()
        .map(|file| {
            (file.start..file.start + file.len as usize)
                .map(|idx| idx * file.id)
                .sum::<usize>()
        })
        .sum()
}

#[derive(Clone, Copy)]
struct File {
    id: usize,
    start: usize,
    len: u8,
}

pub fn main() {
    use super::*;
    use indoc::indoc;

    const SAMPLE: &str = indoc! {"
        2182145329679799934668108710912214845844951226314823525658204550354442854447688517384323661353336272708527767680884030793456642477382883965172346193128942905494881991595540297754477099193345187145574728441145311587911681681840857870978753498326127748931420925832702938139772633883765082975549764060828070241619288246571031152524718777743713244760484976375740573522305852367489606548403285865673388482617985516130717388428994484651496254447710984035432184934512206477687821322169859344383921817219664181998758901559139235404338985763357776395562672315559799473993473187138723669098643960357614809619974810914015688774773399361413812591734658533523478626623456374748962055302943131662522433435379969049862092806662663517223691265793965537747965853966408055799224533075955917954661127831551057163869698254329698832691434241605163986560724179694034311369883598775469158311966090804645458432669567531372181557987772301395559769674413357676278545475668452340793635424466512366854925822268185825836277921783996780834152642841628514297569226693568646634414671689864279573171161162804119865256105910819165777494136569528075814860986263741394243133844544388041682350951822901453983766149456208245662723548934746066327439874918705186841040272324551367757098717663293998189843739866466547493433118026374672539558524067772014756768396335852975351078687177249713955427765830752748181794694922735622934447399634568180583451128187222578112667835611667883944173178032831070229373525646783528968312104828432036295463113652614325516314789646688435524914837331834120225179407619139870172117226881169197523881697966558730277073376385349823127722898175904779544531124837783830813164461780884919729373492378306940607931704584538065418636541454675767503027597430132044805729911494234691405536318975164769234225814947411893546953948044673087959311659139851998249159666327134995271635826180286141419827601766538418294291394146216190495828896515586092822431685568797852756788624735246132974278645562924334504516951370164921562227119659289832852975262268448331967333791298439525216092214119855273313862909213193917389916563699238220908984466510248182346971379095432145609243747146653769314279404225968213715272904978216617361686255121229144539017736422839296975144436928162545478414563417146056489728779262695064183934266775584495288443154494108145158693926851211135909196231149304651943397275028148948971691551522122536377829979896305696814516819233768964596732606795382838569972338488968633807073949419736973607485477575223820396790316222353668141581911884828625442113992799298432942877521688444755309446723321519195426967778514876761978451891973104258345135263933733276428668842385575998829680141933598214534278417846286756135236738465802888196797488661484693918776859580664967639345845623868836635755566157474638951267966531123927787953501875534684491033792454914954563876151139897111813541952727504593365780221872119160628332486422977090333633482928389095104398708125146112698742324268204253913651166297447616483482601199835430452693866053293674596587902473707676545896619352163619478252614545866415543182727256506048503624808491714616936471176047797385908838178730456642201775223943165322745416678533598220229099272581738362301672624039566382839755573154297941837433691765497334958579204784974752674773415138111751804999167233594984971251984482975647609066918997771760363584641150514032458763498572516880847422207449941618556144298952234644323374763837488544388547191768897495175583937356199259731288389843738928459833333112171727793153491510173217688880403513318251593588593869343161899086549051201483542113887655117493742423913163893174812620687571998268154993577456621299106469607385686092192859884164164489943340824023119231859665901579657456765953235455808659401229201544768232487466484016255344426550275624729387378448533299241640798342631856415050459063382887533424713363162864665120664394227934279714887762104662448763676796639214383254104938768861146957387213721253169475933562471427202322621322815959477895506770795756889319398364911456708062502217831528587010555329626554205398748380932844181785485487347910335079126387635062364253775530312755285878451180223172919373679627922641805336572459841266353025453790336278878844454130451117833951675017896616722563523698144483187128753184851913655532709296426227249024166323774459383611759823467034374062712998534730354271665144957469962576317373111364411880627078173462699054555471708315148986183655124743489583465387836667759649227449492065122043443587754919559546692772793051235991648961759436585519257784641911174239691262395218924515269391208769431289854854632921403778585359853857523132798327668192423152205395879828804924841089124150992556205285234619385968487787205249219331929288528657754090561861563210341345744249136982907766518728936197258045961834701913247115571959986350216381944231541464843885917344934632114313195416315877335883256234218576673760344968698645718660724999738335486638615894586493127141632691172356398965461239784321916093269680393392866377172557394224121471786044996272416649402477338866394287919026759587361378693568661610222046769598861247875918326266602513894951289195634458882176749017396345191335221116252635654579917797679586168953113551461925502629987898585692296463935169272295376835903635757556412218257279701992596414392728121326635743928173617257791114427338564912151999649264793688246132281628769383542662837448405073746889385715175929966362339992115861108761269433405950406056437170988532765057208738646672633718782786789412614184916926863397274175672039476798211426365332647464787055452262891950612341417122287739812771957340213195494754854791938770683177767361492064353336822191786077896614195388955364134383428364949274264761792527657387653735539982168179317327677473723974399957581661511949374299105891213058311512736745744550266461484646526115548187719176278675947225918743991691315313191823921291313610344725269932473922274647223214943151946985179498764791149115347925852570688676851018728678677879146415691911329865297162986321103936998527988275151320536240843473915449883275282262682491299927755068314960381646192093114581138865916067123232399720134659291630284756368464625010716686909522196171911599796222209584477741432671831783752731321727294523268854315333245119445531452828135811606865125765201340115525694349186560275491913876759832101484769177732033114788151324576187849731946829539842494285639429241412847939803717246549134935484973482013787078217044878037252397532332388466451416439229456279963260744825524367702694803335714234275420272522867281743459686159368572741995333312748344179323503293435926328835186559418665782085424924677039121698779874943026608244434854988787882941353449712338961895574367428263632535865451645187239387744745224898606687272113865324181123809265362093518638571271655530965134343462777841144213386542449291985664257384421641526733646810452162475118951025455119549042746441948947726422403333558592371770728171198058969610619725775511682274149766658138531050357546231195656919416953689875274627938275798374231732518012288497612034631738666883636647649549511732881440819816418831874054838881121840614550274974136857462445649980704178743954151686223012693098625047263074806729702229217986561769791590142355429630281173492654331292252212838398333525264861136738478157931114329813284251796574825786564867202028274969896744256172503198388530138284663177988040334992437487397071919672721669824549339327702498879348267090473566204872533153768418216614723780226018976151975817971957384453255257223543959139617982396778987912334592332755388012775855108993934195125568103054745189632535448558585179902113891474625714252569756155531568711648661077768559496179289383716328339452428363698669432762548775582274373812721521165311271357868373767649898979163165983179621882604797231566952074439689882039448021547944372387334358689184453838347071496157279032879670808680705480821074343562783459323043629783489626423566546785656664549619781388849959283056103565914594399066908731338472895962546375278717803734946515394533572357183159943654997293368537774843577631936741352015189345288070417452986388774798389758893157852871911446547050805410836238327430266988268891109131662027601382204133762967529497495190867516668017627880228952272949323744322166562922231771404541154846422534504351177799939868943763409296784227175751118360372640672645215084807729794945383857857212826481351971627646655477102790168876987329718338642615263634781395573328395053458845828076677852666187708926286590863348874763826796448449551757615037439065512374769628231162873032535882832663486385537467176754744633486754908996704665643433269540964852121952728013827859832154214376685747581637941652452326775539807422579157815589252247551756816745603867919827745633421676241047653284648855273932992214456855637541452375104732291242376843814494172194608019802441448628384065668252235487598792434164778175384568435950696193427159231936602570687586447689616063734152343816376082189893177769117063952461579915937958697687239787303465744151421168499697459494237452867044879382182391974267807561725122803581681898562237645478157143293814319290823035402730762231954730987042199786172690132684435070289461633510719969954269806288492537748672102630661256383124156424964681391860871942809261819564985862666360911110257629684742755589811035666059261349272749926497993014227730679927486629582319258019365378467034618059549311326723703432563638888824249944694366159910381351305145801421539574719651131917118342179418718356846755812775466689983540519116146975303115734812282933556444612827485828881712878296491026419966451551908529996918619749782285927348648922704422717934335027981060767713375382775141398693426285506638666958489696221892416085964065452553783983556864259969687267464467171270181571798450672581119581354883385514816965566276205158692470628655294159489280543259729194539985579356747093783050926635531972809241475125163483601775974815538288801962664241103820468843495133381091889353605344398057339331817949547687715269283241729692472749525771398178994555201015677513822756659048315092156857414646818556835480627494843696437566796466386095197518292836856684991680319113742111628895289675355258764738961819374946201311456272144260177123793331655542873187446541381593541915952255318430163321386746976159447278838766278249477120772179198551904191393346303031961870579180479096605489178874796714381019758380717044678998217743594191408933453027917166399836312975814088161922186790726776787741603582256966846017593417652543991550128630911595794010252152126144199457171785692253357540713111991844779611529861803830218741534074363381994673272114295639768145966952101288169323934952765021794831313385198487212889212720442697223948111132257251643713855640681774492153975480282372819025945717384941662079731154458372889147201651491836895468884377232825143181959675977393136115785213224849249311733139203036558521237923653067244143852634952454646036754814335486901191176055859222967635864788183398175652771882583643958442939295389666961984368011385527417686416973369937224784466724256024391558758546175169727073275374857753802335108244967632939592522258479157394080875320462857513675967858532144816886876280721648786471147125698962278322182634606971195670338380415890805370613549165890449119529423416195187313154248173386606366893846861426309766464715354870727760705014882528799731635021699158281689754147814589277264414686548934134142145582339948738245177422511942913896371628798313635786452830833769369576379596445162831714377280446839411265998738632457169260566252377060695372167677501199612857224524423527209668215385464641835211557759593239872744607033417164604078666081464334855065891969157110497834413070395196111382475728768070389746566794161711774433707928851065834571847984139720553110647764178991472083621236827636716685619929846485414517504728831673762659125220456872827524423535645234952474816128235036284582801928208121272877224668711317805686597473852888961365454975657026654878746716419755727385987870859619453475187586776263387369423198294354773331707499518886734894452912705173856091931546946388513335655631272986513561743361542391343468382863957418198785201985379848883088826270645228924227132592486510532711313340799472445695827245851599563515896563236959665623813413833846983110194446595418191869964752378649665313647637778655775570122483433174899355567834579261651777534728981020756033809326809570412287799064951569151854493799613232304435711695159321939379348427686270342414452098952291469276999488851412639440344213718479858549962032962534134270687446624845498327752313863518772531994594283828638957568221336240182226662316285187797066886889167780236721437844439945367478834642247854591755307369637842944097223163614565735555297949171190535463519984465975142118146087632927418521426088369019582375988732842083366720889047558173411295474557974060329076147342156573932669538063162734703875272274331761657970272686681717488672357338305158477670432754225947275985832944531818255744262636657510515666543118552024263370307194568050168526202376347385826834458183393352726163367580336626435050472765147030279270301392333525911181518776446180737757414399567184898393745741166749625784263061327726832174797739838040745276259867156323924553262193276618356117555621407554882844484543792518351293172536754114894642531540807329939571508614899840154974524716489145141884524032422545612953114625527929883974654985985273489250245032109211879525698867956798538188304030896724701040643143547478231979111646367446516462491387283732353583105326604743406352216721584832951332789231624873169365938136762467394288335424877946455251241317891312768944662811764849607097529077353280765454806110411952108193581841701264406340652877695430981671277114518470253199505886207162231356192691736035906059268574657429794281589052356329407162122910995845816975658238702954874491566542859440501751411112383048487956683880643237783682392229461690949918658456168257787489243282115562473565896249578179826155224839426547269673116236622187814315237937751085905883302051457616761234888936575554702589772731658129102870988733319432494340664467547566335211137581872077594787277753787783251115988663949660177392728155368893652593118797403495844169475035748784724860952899922841849990415266723089611761751216565524286619381642234777997267579590355238947124277365617814529594243730176857101473969419378322791422646734952731828962808316596296962843798016908485988179869126944821515290208687318862701161776028482649984759409195825361593461147647278760734844146357411628158013415012907641482782793127935528386886434530943161724162765294767448496825401928164840766712957696934333179934775071661823806699757470511232792386434595543579536383311223254098529055935478918027192050416299762476427921784096684574763470677843565951822754744179588946966775672399697817439844185285951181312560399259408392402689315289362649114545408314316026221044655726547613172839317232147827496363582230604377195073139215211092486465996340616147506987239549594669461692288481507629798260721642587936147777675488849960847537757190581264279392359970365559244890768881547750281886447477178318283134633474431345792237623229673370528082145623146144362350771235349161338479318621747252467162297149486724336453342871329142489427733324153249712491691571972017734554718082115125256990702961979130968761796536216327778133401644815989828518907115999647919193555316182080831738203217318732782067663351861667641756257719409468479156537396535424533439527257555323958539315733637795968883896011916371905435183845828660558473609785633126901010358161422051201019477725604076537698709893935932666910768353251370489485745280752834752634201027961437893634342361453583712626579545359836359981652411463211125473834667749848171220909589897449173550579530425259454513607239334381227541878297298753222522351436378129259179381625177484248088413392611599898671876685697645198037523470761189624998293517934387152574364539319922477430111511989654552446492089657653759077272336898180868325554374358220403743186689949678137327793390781463954021914161639761251277676062926950427654651459399868452795569240373871267884432564438159251187271585802249372192638355116444796544672674613925524573358442516750963172632658744552565763978621647769562953422985711933657517234167856162465534486644606860946595815730287082271462953729761149452596812197921720546276367037963796796665683965598548973389911924583361999535901358948368391176699810168421924818464058849517968046763689802633773912563521593613568042166346414185333256178747339256458664197272601045222067989997906383543593318113386050218477212566844454369910482044545362999326521785428231124948294722144910882170503493909743582021442665357240164866689521751382289791367285638045371412978439404621369066444124871323757472749434989444666627826059498049335063184629736611431541226478623276145294258073423268483565829271541012936058257575948687722180978591472436147923868921529980435911987463738398874145484552428714357823198834815136649368727031929319916848702570301129949135505972119131859810897892315233325689185620918974953897853773986265622890372599136559453042713185645226289936371814504843979265552353136152641447217619726810262865425923491039199892588710173061658368321351931895594620407849968730626449328420468295324017396171721623865383608248851890158633513060303049888346709831647019919426765372715586784013778643601270775060605899277648661135197631264413693139503165455897493684347957924383884169421846443320122779684014271676776052906414808864696088768838663336318490858990119110372454169842645069791619459544229157371258205022253993665888255379419879657254875798213384359587182328555158538746363652519774842710265972641194765766825093468030864391238167407662919810945622299495187960744564799052139634168240316343228996809276386443506574447715629934549751457393966711357130788075245285785459105459575367278583476274387916482554406031381680652730876390386327483283143871798028799649645296851676845437192412321547553160318911373127912344847351521090335864734211229073307549217026534878242262794774816165665825186099152947126937824291406244238732725589756626331880186449306323187776603827602045676693136188217417555639475046343767754211204078604378412341132132634523769298849086448632899455882187787569689994955172182274917574964445537386511657181629122769422876561590971557563717401021659119665360736640134546846234196459577975305985929067315636487813547480471411711078815614403026202124683065265786714839611072101676718466224571301710212988778389527797369977144933487391142449845414374733543862566583688149582897906436449323303913304493929446175491199494948065447898128896241231409196669826549020197422176584978683879687559515633146967884887524196410852686361936708186362028799248303294833890146311758260932768992018663413566523446230938094202226537092831679465474436311322011248653938266978858609269693570284289702239284397233196839027934756468476994633544539759368218173445829728883948621345494381393235818994782139777632790566829335357543994355771242488135188943612803897359438165964284618998479908713735619588474736522398057376013116270253071591562643623857991824218504072895464108160554931852528678855201762581762393051832936934970318062264342364620428739836373511792721542929793193241477358241114396226655142447422423658593861147827988486126786521524957662918716767961821183262123369683216254722064915691552020198368953683614197543316507327267686181518826411489369794736485362739571335691855271962938419876492481234018716024192127691445311042143771276845459867507348507048945017191967263380419610667551157633478239556160367491311237694898329360818040176513705085433137227828167115537351696442184192692498957867329653934778799113515194112557593842825099198625899176128572102535994478756818819866752590508237707669237274249782681114227844895117537578999040491460154635554953878124458719149265694551801662879597157018832487902124892088624174524577167587701245528410367142206717348647945530204394563013288061501593883619209787625518941013684410566048522365757889268876959
    "};

    println!("{}", part1(SAMPLE));

    println!("{}", part2(SAMPLE));
}