use bidivec::pathfinding::*;
use bidivec::*;
use std::time::Instant;

// 🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄
// Solves the 15th advent-of-code 2021 challenge using pathfinding calls.
// See the exercise at https://adventofcode.com/2021/day/15
// 🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄

// Your data may vary; adjust WIDTH and DATA accordingly.
const WIDTH: usize = 100;
const DATA: &[u8] = b"\
    9288988799169797672494749255119669898996573999583986189239999598984799822348965745856766795499834649\
    9336897879889887886178547878932383343897969375528317888596414912984889899896681582897852799987698919\
    1897778869898975348195967299799218929299986987238888983439837668176288929486984281998883997689928399\
    9929379596989975588919354989848824879259338981764649316939699414591798996277899778297863349896687529\
    9299536973198975989668639599981992969988798261739729688719716614897359549861961677579672523167986511\
    7987961623297525864967191899298165876452579892878669981979557529983329311935283984796198899331498766\
    9933188395912993489929878928979164799949214314685899999949959978164816779811128692799288826655771954\
    9879411158118811985997999759791869896995299827179998882766687888891885997982991692167933582892854156\
    9998631525957988118287969721874572682352527971791899771898918585995689953667683999169491381879997972\
    9148272678595823589879662996981998894898844679741994169298499959867934999532187299167299186241998292\
    8967886285928969877498814378999894469497368728914983178727691699718399654813956289713487981828996297\
    2999393515291995229979897899399596921679288483969795189979696985897255988985689416376934128997218299\
    7817696897253996999651997969929981349899123948992659879897887667199775989882958778899293892998989276\
    9638635592568249933748715589514111329963291898199473693991698996362848147964599284195681914957329467\
    4958169729641951781983588759859969499895795879488199984497178298368899238979649719927899818641998489\
    9975869369989998759115433978632495978793749977511549989984223394977735997142889411977899995898137993\
    9459965977995489288474399895689998695961956993692699421769614323193479393955974793991182999979389958\
    8994981918488815875941366194919798679996477924993929237972119998926286352895291999868513555622933869\
    9978788955499954429538318136599937492729898626382799896379749839156697643991476929999443913972759281\
    9789326441993961917529769129211514818927459529999665126819834992573899989577699452197919499789111899\
    5645266999796592329963869997412285981628471859718122319982899417968932949924886989359739949384198886\
    4151433899456957966682999728989743799492988668799291189825989779923276699886797988429994794438971668\
    7192698711984233938996888119995889991972929159599994289919539966249787249972571194978959978992687611\
    2188999661989826988581693997894588683797868679171937998388999529486952918189269993969428519963791967\
    9861892485895498492212599425976855994975985912626678899459997129997798893717498885748998996987987997\
    6362488549459179788479968499975364362547921271989899979997419937987319622952986237496986284699314297\
    5497988785661358759985368549985499987879978818164923953194687168865459988799882727999431919418957792\
    8921689612499495196716939839129969948877994484939159896618549595749671852996979999898289792879849397\
    9117892818987897191767559599815947974867469568839917771471898394159117985171699936812298616598548579\
    9499687172935737495154289999572674963694459699667979694997258367529924396919185817635144899393296999\
    9359917393876189496794996228496429878984488199998998519969886192894999822998691883882855832938745789\
    5991899864977697724629999715775227413957489939767875967492379866938689479737899737238139929793229691\
    8773773941114912996998195388691327897589927937565864699875956954763217688963799581693978929456769918\
    3789413727298922758699481168799996951192669889822813961131496997515599269239941498598558992664989219\
    6593995867928869718437459956978746861975998936541855894996991791844649276462868699996942599192789759\
    1993341135872935287172387257312453769899771419861468869997994169176169949614122255777814279818269918\
    2969135998691189572857989199653891178966992543799975499874487811962496191967999489743499839598884687\
    9787789572211797194337999256191563897691817781945298867986284396979988791729938633187393569589869918\
    2299959163318689978729376684584292391777894958897598287996132978169997894991998998599977549738278923\
    3691949798949888798168941149915567331911818129929718518938167387689939299824771197638987817379892989\
    9749785619856999652449487875688981561193591826594362649994939666967979778512799696341955711919984978\
    9881927664728581359934177289639895786194274231975664274195899997999687929598893691365837899273425129\
    9919419886679822926611867726862553187195651759289168197679985899689947964717915885111276899888197966\
    9231598837249477616689995515695824792669591942461898459897688991749911988958996929699359978565275725\
    2892658244889159188897479599898949898749977971288388998787787997948558944985976998979898962172685897\
    9979588759684339829796553677828895958589919229599989589392589747761568985977998861579949161187997233\
    6287215915683729958932894699999247639399978989597899848299991995847221899992518166862818775179559971\
    2799894917998999998874784789594789858417957771571473748859999329599135947687373576896989993589961874\
    5921848262785779887771299979768834439798859747883569786946978457756498658975779671982998713657998999\
    9997786782929186285839956198479977866697199917635186717999819821816856594838498858245992265954264934\
    9954997215627599265929978387691134766992481123697456499693917895998289479717119612991968988158439691\
    9916272332984989918199969936999599699155379896778714667674586619938853681649448451872845859999239829\
    1256399471117548567985989955892899689887699697686297558119846998699918385686487875399995279928741588\
    7177168446299683823212949816929791389289577545289534897191769788823948882469977935993994579671821187\
    6979892421886929946739955799883719139893871273491387787287522865999759437718571283535249569138967648\
    4145997935994642989996771886889569927531998999268917912388818819496782276477165999995719866649747764\
    8898899748735667899752999477989593963868993879144929617748885292969974337666618879885768988931287698\
    9196988991448764896467189989479747838137156849499359959399476958168494834619648549898691614999879739\
    7925876418947885867316298842933587498796372993949569174199698294898468184868798782855986566997769253\
    5999995536941691894699798926989158981998299942565537791869569799989677238748115794415979948626971297\
    8896561829785751826769983485679999991699195576827934937515391627992938198466316849988998981931463975\
    1678992985845917991999559999398498659179639589116974399879277638914599511895856993791955948698936769\
    8723555973519986597726497991769996916871959668366828894199899193915299198488937535299891992439299937\
    9859879779999559469859989149991235571476226458448738485449684831869569129983688918615773979995919197\
    1762274915495299837161988958831218291579987895596819387889529513259546684889197517888399895193724779\
    2329987489878172595959982221592989791917892847896794565689456987698924854979316862189958639879898937\
    7711657684176742515913464892986549152966165389597999969269518687598991498112999894982942789276718458\
    9989179928937989827799268436844255995598521878597942899959459198973751659286887993912795839916999399\
    4567145965886799947748995493953341996258925919999689739976496999948828257798971787719678969851996746\
    8553979659889688912787934849749991288998219549994188353936124999195218388671689915579964878413489665\
    2458758981536446277157958999192653841815897922998795986691787998661699134582798739519913786926595735\
    9233467899499484399916213919898118589935927969443759859978699389889676999696349897998592979919998299\
    1621957847935871765819681398937934599688352958522142283796985527189865829779968678199997198567691768\
    9673864188986737727887346587481936992239789665514689835781751549838861996989972756948968698623688959\
    7897146188799288444495998299966977488868899799997994924917119827858775911816351681497482299111997691\
    2568718799789199779398689847783149889479969577949265239141878557193889688765334449955197999914987965\
    6939937695943799169928279532995937199758313658599658967819433777451979789913959439926566929189199369\
    5999854888947964889779299422517269958222959149218639862111399697889988998988495479874922759149779792\
    8898165192853343774932725119999895929144898798828668998787399878577998661677495889352267795135479958\
    9578193578475986498984689899679398178897882619949696877398898259198963869894573999782235189917995779\
    9614779614699666248931887454849181959988389121797844916823925964183788999781794279997178499292189339\
    7154633697899892718176319474169673818225779991699839667193959375999134917851861694489619849782799983\
    7616913966129714997489291681867995117771128927779449285994725191838843376673798698999374745869928979\
    9818776583846956356779687821191959633714565781299649977899949519971939492224983479969178589787741359\
    8699924979993138798977989952516599159628999129974189852977567885894191476728992769469629699859245899\
    9913371369899982359888716676984987479626245958159698436779975279878971677837387679871384371297934939\
    8599771948779192996924339399766946995298899149959179412988741928283199591227819893228869673194965697\
    8489944889371697897296993939299713849254969988799792753882795824818789664812129936966999988791751921\
    6976789988678861958199499445892799332971227632999989936177688529771589699899882978971429758899779998\
    5968497692829128995138725999979828117911719698428448259968286871278658929934846599584982263818912698\
    8958452959267676424741399686862372997728797445179742993896977988979989612483887199299999714618977759\
    4999382992857889814779859518559958458978116999689569869899929626199925858874989715889286699966189192\
    6821852498859387994787881789359711946699741427195989164226682888818389599911297889796498646148759263\
    9985999614831878291177496865999896852915236956397629682728379999748678194954611317891917837599992421\
    1898728946843198193289979889889991686685685399948883227849222754865945897392179762979369894261974859\
    8239479653435399988579899419849928235496516187895769626582993984392699899597869988769889562986328589\
    2749999498518999696779743457991992199779379529978126229362411788511691877869319879963998164177714684\
    5499969865189779991198556392918514799593899919672411987351966179399942999818128941959596331883477879\
    4719866799939881495699681785999974276299998443822677143998839821795639964258984499989679929197977689\
    6994796719999998996693827884457853594797687747694968116959893999957898943799975585881539179956768118\
";

pub fn main() -> Result<(), BidiError> {
    println!(
        "🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄"
    );
    println!("Solves the 15th advent-of-code 2021 challenge.");
    println!("See the exercise at https://adventofcode.com/2021/day/9");
    println!(
        "🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄"
    );
    println!();

    println!();
    println!("=== PART 1 ===");
    part1()?;

    println!();
    println!("=== PART 2 ===");
    part2()?;

    Ok(())
}

fn part1() -> Result<(), BidiError> {
    const NORMAL: &str = "\x1b[0m";
    const HIGHLIGHT: &str = "\x1b[1;33m";

    let map = BidiSlice::new(DATA, WIDTH)?;

    let start = Instant::now();

    let res = pathfind_to_dest(
        &map,
        (0, 0),
        (map.width() - 1, map.height() - 1),
        BidiNeighbours::Adjacent,
        |_, _, to, _| Some((*to - b'0') as u32),
    )?;

    let duration = start.elapsed();

    if let PathFindDataResult::ShortestPathFound(cost) = res.result {
        // For part 1, we dump the map with nice colours!
        for y in 0..map.height() {
            for x in 0..map.width() {
                if res.tiles[(x, y)].in_shortest_path {
                    print!("{}{}{}", HIGHLIGHT, map[(x, y)] as char, NORMAL);
                } else {
                    print!("{}", map[(x, y)] as char)
                }
            }
            println!();
        }

        println!(
            "Path found on a {}x{} map: shortest path is {} calculated in {:?}",
            map.width(),
            map.height(),
            cost,
            duration,
        );
    } else {
        println!("Path not found 🤷 in {:?}", duration);
    }

    Ok(())
}

fn part2() -> Result<(), BidiError> {
    let base_map = BidiSlice::new(DATA, WIDTH)?;
    let mut tiled_map = BidiArray::with_elem(0u8, 5 * base_map.width(), 5 * base_map.height());

    for ty in 0..5 {
        for tx in 0..5 {
            bidivec::editing::blend(
                &base_map,
                &mut tiled_map,
                &base_map.bounding_rect(),
                (tx * base_map.width(), ty * base_map.height()),
                |s, d| {
                    let incr = (tx + ty) as u32;
                    let base_val = (*s - b'0') as u32;
                    *d = ((base_val + incr - 1) % 9 + 1) as u8;
                },
            )
            .unwrap();
        }
    }

    let start = Instant::now();

    let res = pathfind_to_dest(
        &tiled_map,
        (0, 0),
        (tiled_map.width() - 1, tiled_map.height() - 1),
        BidiNeighbours::Adjacent,
        |_, _, to, _| Some(*to as u32),
    )?;

    let duration = start.elapsed();

    if let PathFindDataResult::ShortestPathFound(cost) = res.result {
        const NORMAL: &str = "\x1b[0m";
        const HIGHLIGHT: &str = "\x1b[1;32m";

        println!(
            "Path found on a {}x{} map: shortest path is {}{}{} calculated in {}{:?}{}",
            tiled_map.width(),
            tiled_map.height(),
            HIGHLIGHT,
            cost,
            NORMAL,
            HIGHLIGHT,
            duration,
            NORMAL,
        );
    } else {
        println!("Path not found 🤷 in {:?}", duration);
    }

    Ok(())
}