2f:T4e40,inputs = `213132332242244333314552211545514241212233422661112133361246131263251423221122555246536242354216434511222434442322532244312121132113144331132 332222312334242214215213533231522424244123625553556341164345622616263262321635342626654563463554526432131533235542344351353313411144123123413 222422141311333442213552541251431154133342653346211612462535134456443215324233142165225513333455456215112145444444223311235424413113124121213 122131231423344444253422432444244122336241144566552145515322136665251541212355262152555144311622534613612211341111411442424144311112411313433 233333224143333124325532345535424111266151625311655513641324154413653131135436565243154454522626535123252511435515324134453213114231333441113 242132131142344252213254314352241254422566211153435111424441366545141321452416253246262644565321261614452144553343242125111352423223232141444 113221211123421543521421134154345222132126151432616315262243232325763633174135213122353451444252325461115452325551211321111223134121131144322 213434314321134324354245455213252553316331122165655311346547566314625775477516541673143463511333433464424343455652255451225455342213313233213 314432432342143132123525431424545241435315655153135246431274731411533147114115144316367215643531356165451654666621224544234345231541311431141 244111212125225532255354111234122351653616351114511376351637441457131614155567564574454117255352562521664626556346211224545522152153144321311 322141311414451142143214235361311363166415164556662233167471577435625562677736177751713241753512516621511643566124225533554355243123331124433 123214443455245253154434115565525321442645664124244416624263555411426654663131521417353273424564764224523242321321532232224524223524154144331 422413315322351534412556416165414424464422364251117253773657477237437376272244436143432372334725726223326165222536246121543333452542341221212 244411332535515431445365512211612416534662441374175742771431143564477645515114535765342655553473425155445434233156215411325543214214531314231 242111544224355224314415315446611634363562273211674465276211533311546473631234762473335666314757423761426655431146265213334514433341522253433 443244254222332432116512142425412115563214327673463441223667265727675217774424125247667525632233461372624215142261561511136112233322131124444 213131542224212324266164436324566565553437333737645125455653153724565653543261713217234126161425115145411264331434441343635651543113233251212 221452441123451544443245646331161427745471547472646616163223753122473288552357522741734643221373443522755161332163224131124513543351345211533 315523541523443333115452552526266426424271372774756157356543688622646673255634466253367362466443467765242347314442253462356411413242523442214 214115355343113154342121633244147324424413516645712512785582742762437486588245735784847234343223525155737351147441642616134352141551522332122 432322341444325611362536316546437713723324375642155178844458724427782535463455274225246883463373444667773341272714245446446436222313145454435 223122454135113235265424256347444776275424561265516536643288243627235564433666253728742782363444313412674755163416265424461522326235313143131 233224323214241436222262335644465641417336124442642484333725728744733284533384624343366762565622744766523757634375353536363121222654141313541 414411133321445166211462131157135142533437312742628438244783235672483588232638762638876823726543663212336727372714662661144164364213211335114 253231423123532643513123545654462462613745526437763767435283324838477432386235558574632686688288566116236634517633742322234641644365223322143 544141253243445655665415627332644516637317662648637657665422352786846386645276734387528667832856848676631233352757573412643453521434251114531 152222132232641435663446157116453416555547688734258566325742528782486454534572485753742743773753787447454342727757715524425653253321625433123 445412524662313344543465771545136133251755222335268434272368467262774556744767648347622625872476568587343553751475211227455441252145413453312 433111145442666223156452442167227364728673265726387737374766786238699777867853684825387865565675528344627456375632753227145446154221452225114 111211234245616652641147357324456455523662422553487524442368787686739367896953759543633852433282878333353662735441217352552212322646612414252 134541232264325532334674514215432317224852638246642477222683378665398877775434949835794355546522482674423637244447346111121326541535461621242 343443344345514563133153316626347766572645776652755248847756574355935454779737443757439675747758864254526247253145465346671432564364425252143 414323335236316514124464743362614344535562832323437875656866575748574777638747483448654966785536264843288822422267456244645215544544526544142 411413156464343253377634277341711846654848425724846837363579878956673473459763354757846647698548222532777856681575134452326722214236314116435 424142154554155541221457516351562542652458728862559755858468687384494739634744484335984397377855876222773777336141173653613466645545415116523 245444235646332241224612472541242537434688588576463777863854936957476783573948449358746389969936267282685383878461221426651264531436362145211 321415243115432642333524221572335462776735823897888756843785394395995475643639994847659686987657878828544233536882542437754612113522263455224 513126421135243666243116772366274524722748365435594689986435585783765385987773777687737459699654934264863435684534774542372134263132313331132 313421652524221776466633521455845462785532396768784357845448387947649638976749654499345753588448473357458244228727641465224323261633544341114 344232511646164353561117532373673376526768493485656557863585695397658684859675663795336856435784985538665287654734881736135431763551166355463 421253265314526635221124512377344434472234684846769849598459499967565479795547747846737984589763693757388487842864783522637325452541114664252 311213635524457777426644152567385832747646747733787636886338549885595979946875766965467566875348553485462853632434324276136674266142621213216 463134341555471651233473655482632775533398443843548757768786465566746658575974794859868843568568369987464774735434453364231211444441264514112 326143243211642473546651167387775252435983864763845986979977785764574785559776764587846754654594647373965327466656883344517544674472415346355 641255615655471156213277473737586682563465583547765585697994448599974466688457664486674569936588993757669786735283386333476334532534343323531 131515226365351555451467353653873788756693493443396544477958454454748478788875499956769576694384468347987932264736288556266731351575642532266 256455543623645456463167528554233825465875545773848975655984556648594844977646788777569865748338969447554943235725663458512623277365545333424 442253525332573355666232283625768863436339737568754957564959956776644888489878699969787677598633483663863477767872855722642654333365655426436 361326161453412342763765463574473623838337896336668655975786797974696658984896576887767647995666556477865688346626732355753567473777522262633 155365664151352165562678726578772685553988435668847678799856785588477698688887488656559488984947777474887874985455375767216777523542135244135 353413411136153141462745446653335373378696487478466644578569784549896987897769745568487985794947949347383554542277222852663477245565523526231 246462551615162273661442322463227753474978994969567747544784585588665975759876757987558958668768754648789683464485432485672463356237362126366 544466252127357143228644235676868654966539547599746479956646775777755659889766755754577685579649877485437853753562542687855732563672261513352 646556114374523657544347786237529378649974496877947787995898687995569667789898779889486588779568657448363839848354823382757556447232733234124 452524162741267456127885346566856389475655885499495859995987879659765658685855865695744955577567985875559539689375353665854141433713663115266 532112331151143721136742432653758847483889649894956796555767766677577678958885867959699459778674548636467679843972775283825662523564723614226 222554357736423276466454557656537496989494577445556885886859867896657878667998788788787794984489547756556777988877632425368552366354455255425 512464235332127553667528537846676474664779854685945795655976587999859986886686869986577566874667766485375367854872276523326532733763674241614 352435547136611463555658733835757545445487698998679494685767886859678769557575588986597985955689967798477946833782526383766372177235166763565 353213214555262345552545237347965793577395599494945897997997665597866976758885589857995998969748978995567599798368475744374444261364654661345 316566336635142622266684786464785549959854464695956988766899586679586785766559589868585856958596544959345955684634876823457535536564332265244 315225542645442731337862732367579385849797786755887868687857987598988769886758878769578595994987864659956798948743454546254882166533337725211 462442377522622773346786536384763995959958559489575977577695767896866969778999655876958656966577568974499955593594566485572726673477731231165 542125674377146446682662842658586565737697868777895776659865878889889666677786765597959789597578455998738935949645877483222833627432271534225 111456553674521263736244322484387496587847969544554955598859969866768896976767669669857866595588996689996754954447766487562764465452421153336 454314672541364662358362642848449338885776454494858588988695667778977876977766687965876899975567474896849763375776456765378485324375333211352 266216724556123524428628255647456946564987456778557886796569688788887976966979876769989656788868496896796464946737327842884587554457422173614 552656364444416664373256737338977988997854995474488556956587678967999788898987897957967977588564597557679536756458553626825868562713227422625 262134574142436547465487257355497447996786498488755995669866769966999798779796868976585976659799784495855544536567376876567748527254135762462 512511225125542272436567743734965555576475457568985599985998767999696867696698786959899555758895968488698748387376972577572782377775665351335 215646441374136353434438328487887844487864998956869756996686567887688867866987988897678656868847757676699988834936327662573644147322417633246 521251632257437445335657635543885684396965866657476566796589597897668698979767779965888965686477565595686473845555677462767452224777355154423 331351413237115467438788852444459577897786699857597768779578978897978666899667887897595565886455799476696845387996755286286783143116622671153 435333772147653463886225484597737635595567799886877577795756789767979889886796666779686579879877847549465479634845323825448468264146611372143 122612767212164467732267376356758458799684575779656896867556868687869688997897888678795998887757885587755997958638587368573556611471777735416 162453274311743515248836838858477534483669486466678775785698796997798967687886988898585995765696557768973355737537327474367725555452174766515 455516244662415327555526242649736995499799895854496969855957597698868869696878987965566696986746968489778779477856427627686255752354244422253 226341633611644122724375377378545647576785445754598776758958567787699966678689988555687976556468845445655567834445645476824784536766277462652 155464227146412111574258345835734648345448654455946678788586598697889988696668668568686765789677884544954986367959524723636486427621622314415 542416431634164221438477685657334749888869699748755989885777876596898966667978655689675768594947547869588645768556258587842584474536151221116 536146453277165431488464466669649874748384894776997697666799989568999789867767965567895585696965756695597839869386524586263854567635211451264 446425271231571767856748736589568533667845457867849967968999776758567996989865996569576688799656676675589577488679425535637455241363232735226 316235346433147513275427436489575786666676657987544969699979665875567755799558558595676796874697754499946764359545773242786765471651316216554 351133135215343737328872672345336759743558584784794878576977655657579686599687959875999565569785498957343795744973456346426681341266624316221 244222414442723644568468828274356639754544698859594444999569555899967965568765585569975956785879498568649873467477265485274713751157515564625 114446424333564545686327336544684968773893589748494976869697998795968557888957598588885675666689688484378844364672467746473327676233263132421 641622547773334353244783777623477836964556968459875897697597589577885666875587696566979655984889965756967548679866378555567563652326136242343 125166317345714573646722382623859777859937659767989696964978855786996996995887755587674557776998989675763564436353442226768756453116427411236 215131215776352711745428647245797973853385864954586958694459888876655776968966959689866767675644544766637633759328378383642321723453264424264 542642122314777525525284243754443663989466768547498655597975876666569596788587756978685844845749674877899877546487328588478561246243176254263 333313113317151563758752283247388563867445773764649994954775668668688688697568757948696954898879856468357359978738285665653337432323343664366 223164352622745141241758783252645398377956679586644959495464669595856958878697794596468998958765955386484836673636463446753155516732225126143 242415512456623771476873342537874394443483666879966994475656766788586689765595587586676988568979856774764763457847746786783231216543735355233 622164163223664346436733544272745493948366953655666594755966974677597444499958477487676647856678945984367646854456458338414313572121436412532 624244252427413156646432346555733788785938384875997484787669499674794946948944497457767769997794886553879336457667458342641553646347514354644 214265434516356644424436456824557526776448364344367954868886595956696854489985956797564659748884647779485383465564628567216474575416162233621 254551113642675273431317487236666254994756834835535485555568964945966687777477456998775459459397868658583336543522644656431363221767124525625 665642236462315557244447723485853386889947387677683565994478985579666579868698666684849578649343353554738476322586732624362421362473133433135 625543613336534242544362535427354664673686763688353586648559695867769995964466578858475467956837679836677322578625872875417237465565256333236 254222645362511545155524347363855628586738339843838334364455977898896864874978776445454637663543474588375535557622757833422754334612353261646 365554555212553232555173176553474544766973543583469977836484954846948786985799484945549676475637499447795532555543886252221675344366216526563 144233321265177142633746753484345247352386474483894334449489685595458594698755786596883583737769983568826676365545847737473575723114353611252 212624365314413122157613147567348254385564653749987898457655389567847765594695587777885389436676397435225638787758825747674376723166654624645 523532336266553241335572651456627884365725574548535855576535795677685748558555655434894789355684956752453467582757437417466454743226263556414 454461255562442755343766361478242584668445555366633348953577536936766974539968349759657533743697596856768462378744253732471634623562332213632 412352324653615132232141437757352842848778756564794744794343795577643776679874933463478493849769339333376776662644175476456422231431211146555 124121136126313466516262533612263256684782836438896334868593764579878337568977686444376865674588657765686748338452712121766571324363452541521 154536664631661341432716115712224686548847274283584674997445757459747648454963785776497647656397644435725683755631466344472774641423663344535 434511256264512236771617235316417543755488827243457539564638358395674647675333548739964885674964328448558857828327631277413134445664145341453 111546662266662542164542314326144888277487364223284966643586546694834644969454544334764657363475746222834838262433334427673246336111164312322 452231132563156224122134613575425142432566642828678686598476683653577335343947469966837763756422652753774572426564213556341146421226244612124 443533313622243113467613152425472534222627878654357648733888783436369838636958394963683792634263565232865578573567157765777656514423122541154 341133156663553435362361233434764727876887534564865557355467664586338885894566459935956342344658834488284882544621433555566414526335531111342 511424244614222464333316365643736145783282768275746825257224746795737568466374948378744388738585675476253454666236562725652236146513154434244 151534525111442235265566635577653627577464367627532264362426727356879388356477324474634267485563527832426747454512531216766512125455634433332 311351353132121336141427734461624117355788836226687765456733583387856825425552466325622888437363678635774447723767673533614541622532554524352 355245342215662266362213251127474316154624277374574567872777755256244236458842843663645234246786763658212763251122161461514655424566634425514 131542421515663144523323264756631473733776244367772263563247842386577767847732674384285474466575465885662372425766143131651414653446352551333 442422234254651565551222561622622624413744532335747288436674388866244648654233234623787886225524586316377657714127752466626615544424211115541 444215441113411421426462132761744243154355377533565233327254486782377447337572544242234425238828562764565414275715266646412651423661311544552 153453113351544656623635531247335516637267472275288872887222782874484483323888254835276674557626223667224527274213146653526566156221342545333 344552545331213352154314366213656726216324265433217287672263856286785657332785323525556445835511721467663152721155525634462562132321242511235 423113314154415144315266341626426643555574127313713426534527352753256553783364554452326255667676252153556461114445263221154562235135522454113 315155445215432466624166143351637737462357754516617273286626376344675325866485464662836413615214653717517125122156564363656133645312131254234 232345535552233452125146633115336335716213411544512517521517437873857657657563265325214467612412563654342634444421235361435433155534343112113 241533351331543235124261661364124634214256554734517761124145143616826483838386312755433177434564616373626443421163333536616325443445231411233 244354323325434453561166543133536644662744565537467744744321732614267732546265344544166511124333177737421475235321646352224554331452541552234 134314411452535252121652225656251355511722124356674172454174322155545554376625154617276473633626522233327554364434656252552141143445345453443 233333413133441131244116366645134566626553552536377125245241654135755521147666636272553331132751564342134241425351362263132143135145413442322 343424342551122242453226136145622651221232664473656463447561344333161251747466265132173534653674274565263636446266145411421345253231314524131 124411414352242143142543453512132164512254345241465514135447664352373536722362276566731432361556454743266515265421233324531522254242255242234 141111213313422124432254532411365622623332555471774771477147516755376771725273123627411455343225732261362333556215325413514344235452411412343 234233421125523511511315221333413534146412265566244554273633165367645525311461367514224532517664111623556352642146411344242355131124211313122 331431213451353555441435335534154523536463334456352262171337534277226253777211251622323461722115131352561362146155354354451422222231414431444 222142113335241245434331532333114644361465426364425364455452531733376453647516224227172342441324166255465262242321325152212141553433211231321 131142444141533241154113123211143525141125452642116453513144242243273616737636127366613521644166266135354316613133533135252353115251243443433 411334114214433134143432243243153416244546121463446322213356561426237344276326664516245415331612112256514653244533532343541511312213212312322 213322212314343133111531153255214425354565452541164645653563221665565561431331633514552635242166461235451531525234243325534433241232331323433 423244234333343233155453224124322521214656615525321246366535161135364636142133162313464521634636241252426563413243233333514253222341123144332 142343142231411124244555532352451231452231664125211465423222544145112636113654352544664441625515233446241242554324422451434334311314343214424 132223124321331314532111155333251542233231212643341236552134512211645555665241443155532354142316134112523134344425252542255352141343143114431`30:T40e,function* kruskal(weightMap) { let log = []; let kruskalMap = new Array(weightMap.length) .fill(0) .map((row) => new Array(weightMap[0].length).fill(null)); let x = 0; let y = 0; kruskalMap[y][x] = 0; while (x < weightMap[0].length && y < weightMap.length) { let nextx = (x + 1) % weightMap[0].length; let nexty = nextx == 0 ? y + 1 : y; for (let dir of Object.keys(directions)) { let newx = x + directions[dir].dx; let newy = y + directions[dir].dy; let weight = kruskalMap[y][x]; if ( newx >= 0 && newy >= 0 && newx < weightMap[0].length && newy < weightMap.length && (kruskalMap[newy][newx] == null || weight + weightMap[newy][newx] < kruskalMap[newy][newx]) ) { kruskalMap[newy][newx] = weight + weightMap[newy][newx]; nextx = Math.min(nextx, newx); nexty = Math.min(nexty, newy); } } if (y < nexty) { yield [y, x]; } x = nextx; y = nexty; } yield kruskalMap; }31:T4eb,function* kruskalBacktrack(kruskalMap) { let pos = { x: kruskalMap[0].length - 1, y: kruskalMap.length - 1, loss: kruskalMap[kruskalMap[0].length - 1][kruskalMap.length - 1] }; let path = [pos]; //let weight = kruskalMap[pos.y][pos.x]; while (!(pos.x == 0 && pos.y == 0)) { let neighbors = Object.keys(directions) .map((key, i) => ({ dir: Object.keys(directions)[(i + 2) % Object.keys(directions).length], x: pos.x + directions[key].dx, y: pos.y + directions[key].dy })) .filter( (n) => n.x >= 0 && n.y >= 0 && n.x < kruskalMap[0].length && n.y < kruskalMap.length ) .map((n) => ({ ...n, weight: kruskalMap[n.y][n.x] })) .sort((a, b) => a.weight - b.weight); pos.dir = neighbors[0].dir; pos = { x: neighbors[0].x, y: neighbors[0].y, loss: neighbors[0].weight }; path.unshift(pos); } pos.dir = "E"; yield path.reduce( (newpath, p, i) => newpath.concat([ { ...p, straight: i == 0 ? 1 : newpath[i - 1].dir == p.dir ? 1 + newpath[i - 1].straight : 1 } ]), [] ); }32:T8ba,function* kruskalWithHistory(weightMap) { let kruskalMap = new Array(weightMap.length).fill(0).map((row) => new Array(weightMap[0].length).fill(0).map((el) => Object.keys(directions).reduce((dirMap, k) => { dirMap[k] = new Array(3).fill(null); return dirMap; }, {}) ) ); let x = 0; let y = 0; let steps = 0; kruskalMap[0][1]["E"][0] = weightMap[0][1]; kruskalMap[1][0]["S"][0] = weightMap[1][0]; while (x < weightMap[0].length && y < weightMap.length) { let nextx = (x + 1) % weightMap[0].length; let nexty = nextx == 0 ? y + 1 : y; for (let dir of Object.keys(directions)) { let newx = x + directions[dir].dx; let newy = y + directions[dir].dy; let minWeight = Math.min( ...Object.keys(directions) .filter((k, i, arr) => k != dir && arr[(i + 2) % arr.length] != dir) .reduce((minWeights, k) => minWeights.concat(kruskalMap[y][x][k]), []) .filter((el) => el != null) ); let dirWeights = kruskalMap[y][x][dir]; if ( newx >= 0 && newy >= 0 && newx < weightMap[0].length && newy < weightMap.length ) { if ( (minWeight != null && Number.isFinite(minWeight) && kruskalMap[newy][newx][dir][0] == null) || minWeight + weightMap[newy][newx] < kruskalMap[newy][newx][dir][0] ) { kruskalMap[newy][newx][dir][0] = minWeight + weightMap[newy][newx]; nextx = Math.min(nextx, newx); nexty = Math.min(nexty, newy); } dirWeights.forEach((dirWeight, i) => { if ( i < dirWeights.length - 1 && dirWeight != null && (kruskalMap[newy][newx][dir][i + 1] == null || dirWeight + weightMap[newy][newx] < kruskalMap[newy][newx][dir][i + 1]) ) { kruskalMap[newy][newx][dir][i + 1] = dirWeight + weightMap[newy][newx]; nextx = Math.min(nextx, newx); nexty = Math.min(nexty, newy); } }); } } if (y < nexty) { yield [steps, y, x]; } x = nextx; y = nexty; steps++; } yield kruskalMap; }33:Td27,function* kruskalHistoryBacktrack(kruskalMap, weightMap) { let log = []; let minLoss = Math.min( ...Object.values( kruskalMap[kruskalMap[0].length - 1][kruskalMap.length - 1] ) .flat() .filter((el) => el != null) ); let pathes = []; Object.keys(directions).forEach((k) => kruskalMap[kruskalMap[0].length - 1][kruskalMap.length - 1][k].forEach( (loss, idx) => { if (loss == minLoss) { pathes.push([ { x: kruskalMap[0].length - 1, y: kruskalMap.length - 1, dir: k, loss: minLoss, straight: idx + 1 } ]); } } ) ); yield pathes; let steps = 0; let completePathes = []; while (pathes.length > 0) { let path = pathes.shift(); let pos = path[0]; while (!(pos.x == 0 && pos.y == 0)) { steps++; let dir = Object.keys(directions)[ (Object.keys(directions).indexOf(pos.dir) + 2) % Object.keys(directions).length ]; let x = pos.x + directions[dir].dx; let y = pos.y + directions[dir].dy; let loss = pos.loss - weightMap[pos.y][pos.x]; if (x == 0 && y == 0) { pos = { x: 0, y: 0, dir: pos.dir, loss: loss, straight: pos.straight - 1 }; path.unshift(pos); completePathes.push(path.slice()); yield completePathes; } if (pos.straight == 1) { let next = Object.values(kruskalMap[y][x]) .reduce( (dirs, dir, k) => dirs.concat( dir.reduce( (straights, loss, i) => straights.concat([ { dir: Object.keys(directions)[k], straight: i + 1, loss: loss } ]), [] ) ), [] ) .flat() .filter((el) => el.loss == loss && el.dir != pos.dir); let last = next.pop(); let sameValues = new Set([last?.dir, loss].join("-")); next.forEach((n) => { let key = [n.dir, loss].join("-"); if ( !sameValues.has(key) && path.filter((p) => p.x == x && p.y == y).length == 0 ) { sameValues.add(key); pathes.push( [ { x: x, y: y, dir: n.dir, loss: loss, straight: n.straight } ].concat(path) ); } }); if (last) { pos = { x: x, y: y, dir: last.dir, loss: loss, straight: last.straight }; path.unshift(pos); } } else { if ( kruskalMap[y][x][pos.dir][pos.straight - 2] == loss && path.filter((p) => p.x == x && p.y == y).length == 0 ) { pos = { x: x, y: y, dir: pos.dir, loss: loss, straight: pos.straight - 1 }; path.unshift(pos); } } } } yield completePathes; }34:T8e9,function* kruskalWithHistory2(weightMap) { let kruskalMap = new Array(weightMap.length).fill(0).map((row) => new Array(weightMap[0].length).fill(0).map((el) => Object.keys(directions).reduce((dirMap, k) => { dirMap[k] = new Array(10).fill(null); return dirMap; }, {}) ) ); let x = 0; let y = 0; let steps = 0; kruskalMap[0][1]["E"][0] = weightMap[0][1]; kruskalMap[1][0]["S"][0] = weightMap[1][0]; while (x < weightMap[0].length && y < weightMap.length) { let nextx = (x + 1) % weightMap[0].length; let nexty = nextx == 0 ? y + 1 : y; for (let dir of Object.keys(directions)) { let newx = x + directions[dir].dx; let newy = y + directions[dir].dy; let minWeight = Math.min( ...Object.keys(directions) .filter((k, i, arr) => k != dir && arr[(i + 2) % arr.length] != dir) .reduce( (minWeights, k) => minWeights.concat(kruskalMap[y][x][k].slice(3)), [] ) .filter((el) => el != null) ); let dirWeights = kruskalMap[y][x][dir]; if ( newx >= 0 && newy >= 0 && newx < weightMap[0].length && newy < weightMap.length ) { if ( (minWeight != null && Number.isFinite(minWeight) && kruskalMap[newy][newx][dir][0] == null) || minWeight + weightMap[newy][newx] < kruskalMap[newy][newx][dir][0] ) { kruskalMap[newy][newx][dir][0] = minWeight + weightMap[newy][newx]; nextx = Math.min(nextx, newx); nexty = Math.min(nexty, newy); } dirWeights.forEach((dirWeight, i) => { if ( i < dirWeights.length - 1 && dirWeight != null && (kruskalMap[newy][newx][dir][i + 1] == null || dirWeight + weightMap[newy][newx] < kruskalMap[newy][newx][dir][i + 1]) ) { kruskalMap[newy][newx][dir][i + 1] = dirWeight + weightMap[newy][newx]; nextx = Math.min(nextx, newx); nexty = Math.min(nexty, newy); } }); } } if (y < nexty) { yield [steps, y, x]; } x = nextx; y = nexty; steps++; } yield kruskalMap; }35:T777,function* backtracker(blocks, directions, maxSteps) { let shortestPath = []; let steps = 0; let log = []; let start = [{ x: 0, y: 0, loss: 0, dir: "E", straight: 1 }]; let pathes = [start]; while (pathes.length > 0 && steps < maxSteps) { steps++; if (steps % 100 == 0) { yield [steps, pathes, shortestPath]; } //log.push("step is " + steps); let path = pathes.shift(); //log.push("path is " + JSON.stringify(path)); let x = path[path.length - 1].x; let y = path[path.length - 1].y; //log.push("x=" + x + ", y=" + y); if ( x == blocks[0].length - 1 && y == blocks.length - 1 && (shortestPath.length == 0 || shortestPath[shortestPath.length - 1].loss > path[path.length - 1].loss) ) { shortestPath.push(path.map((p) => Object.assign({}, p))); yield [steps, pathes, shortestPath]; } else { for (let dir of Object.keys(directions)) { if ( x + directions[dir].dx >= 0 && x + directions[dir].dx < blocks[0].length && y + directions[dir].dy >= 0 && y + directions[dir].dy < blocks.length && path.filter( (p) => p.x == x + directions[dir].dx && p.y == y + directions[dir].dy ).length == 0 && (path[path.length - 1].dir != dir || path[path.length - 1].straight < 3) ) { pathes.push( path.concat([ { x: x + directions[dir].dx, y: y + directions[dir].dy, loss: path[path.length - 1].loss + blocks[y][x], dir: dir, straight: path[path.length - 1].dir == dir ? path[path.length - 1].straight + 1 : 1 } ]) ); } } } } yield [steps, pathes, shortestPath]; }36:Te76,function* backtracker1(blocks, directions, maxSteps) { function isValidNewPos(x, y, dir, path) { if ( !( x >= 0 && x < blocks[0].length && y >= 0 && y < blocks.length && path.filter((p) => p.x == x && p.y == y).length == 0 ) ) { return false; } let straight = path[path.length - 1].dir == dir ? path[path.length - 1].straight + 1 : 1; let loss = path[path.length - 1].loss + blocks[y][x]; let cacheKey = [x, y, dir, straight].join("-"); let cachedValue = cache.get(cacheKey); return cachedValue == undefined || cachedValue > loss; } function createNextPos(x, y, dir, path) { let straight = path[path.length - 1].dir == dir ? path[path.length - 1].straight + 1 : 1; let loss = path[path.length - 1].loss + blocks[y][x]; let cacheKey = [x, y, dir, straight].join("-"); cache.set(cacheKey, loss); return { x: x, y: y, loss: loss, dir: dir, straight: path[path.length - 1].dir == dir ? path[path.length - 1].straight + 1 : 1 }; } function getSourroundingBlocks(x, y, path) { return Object.keys(directions) .map((dir) => ({ dir: dir, loss: x + directions[dir].dx >= 0 && x + directions[dir].dx < blocks[0].length && y + directions[dir].dy >= 0 && y + directions[dir].dy < blocks.length ? blocks[y + directions[dir].dy][x + directions[dir].dx] : undefined })) .sort((a, b) => a.loss - b.loss); } function tryNextDir(dirIdx, action, x, y, path) { let dirBlocks = getSourroundingBlocks(x, y, path); while (dirIdx < 4 && action != "next") { if ( path[path.length - 1].dir != dirBlocks[dirIdx].dir || path[path.length - 1].straight < 3 ) { let dir = dirBlocks[dirIdx].dir; if ( isValidNewPos( x + directions[dir].dx, y + directions[dir].dy, dir, path ) ) { path.push( createNextPos( x + directions[dir].dx, y + directions[dir].dy, dir, path ) ); action = "next"; } } dirIdx++; } return action; } let shortestPath = []; let steps = 0; let action = "next"; let dirIdx = 0; let path = [{ x: 0, y: 0, loss: 0, dir: "E", straight: 1 }]; let cache = new Map(); while (path.length > 0 /*&& steps < maxSteps*/) { steps++; if (steps % 100000 == 0) { yield [steps, path, shortestPath]; } let x = path[path.length - 1].x; let y = path[path.length - 1].y; if ( x == blocks[0].length - 1 && y == blocks.length - 1 && (shortestPath.length == 0 || shortestPath[shortestPath.length - 1].loss > path[path.length - 1].loss) ) { shortestPath = path.map((p) => Object.assign({}, p)); yield [steps, path, shortestPath]; action = "back"; } else { switch (action) { case "next": // add step dirIdx = 0; action = tryNextDir(dirIdx, "back", x, y, path); break; case "change": // change dir dirIdx++; action = tryNextDir(dirIdx, "back", x, y, path); break; // go back case "back": { let dirBlocks = getSourroundingBlocks(x, y, path); dirIdx = dirBlocks.indexOf(path[path.length - 1].dir); path.pop(); action = "change"; break; } } } } yield [steps, path, shortestPath]; }37:[] 2d:{"title":"Day 17 - Clumsy Crucible","cells":[{"id":0,"value":"# Day 17 - [Clumsy Crucible](https://adventofcode.com/2023/day/17#part2)","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"inputs0 = `2413432311323\n3215453535623\n3255245654254\n3446585845452\n4546657867536\n1438598798454\n4457876987766\n3637877979653\n4654967986887\n4564679986453\n1224686865563\n2546548887735\n4322674655533`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"blocks = inputs0\n .split(\"\\n\")\n .map((line) => line.split(\"\").map((el) => Number(el)))","pinned":true,"hidden":false,"mode":"ojs"},{"id":23,"value":"directions = ({\n N: { dx: 0, dy: -1, arrow: \"^\" },\n E: { dx: 1, dy: 0, arrow: \">\" },\n S: { dx: 0, dy: 1, arrow: \"v\" },\n W: { dx: -1, dy: 0, arrow: \"<\" }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":311,"value":"plotPath = (blocks, path) => {\n let map = blocks.map((row) => row.slice());\n path.forEach((p, i) => {\n if (i > 0) {\n //map[path[i - 1].y][path[i - 1].x] = directions[p.dir].arrow;\n map[path[i].y][path[i].x] = directions[p.dir].arrow;\n } else {\n map[path[i].y][path[i].x] = \">\";\n }\n });\n return html`

${map\n    .map((row, y) => row.join(\" \"))\n    .join(\"
\")}

`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"## Part 1","pinned":false,"hidden":false,"mode":"md"},{"id":90,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":424,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":456,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":544,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":93,"value":"// loss mapp with default navigation (i.e. without regarding additional constraint)\nkruskalMap = kruskal(blocks)","pinned":true,"hidden":false,"mode":"ojs"},{"id":429,"value":"// extracted default path(es) of minimum loss\nkruskalPath = kruskalBacktrack(kruskalMap)","pinned":true,"hidden":false,"mode":"ojs"},{"id":524,"value":"// loss mapp regarding constraint of not more than 3 straight moves (might take some time!)\nkruskalHistMap = kruskalWithHistory(blocks)","pinned":true,"hidden":false,"mode":"ojs"},{"id":534,"value":"// extracted default path(es) of minimum loss regarding constraint\nkruskalHistPath = kruskalHistoryBacktrack(kruskalHistMap, blocks)","pinned":true,"hidden":false,"mode":"ojs"},{"id":813,"value":"// minimum loss is the lowest reachable value at the destination (i.e. in the lower right corner)\nresult1 = Math.min(\n ...Object.values(\n kruskalHistMap[kruskalHistMap.length - 1][kruskalHistMap[0].length - 1]\n )\n .flat()\n .filter((el) => el != null)\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":665,"value":"Plot.plot({\n aspectRatio: true,\n axis: false,\n color: { scheme: \"PuOr\" },\n marks: [\n Plot.cell(\n // reformat array to objects with x/y coordinates for plotting)\n blocks\n .map((row, y) => row.map((el, x) => ({ x: x, y: y, val: el })))\n .flat(),\n {\n x: \"x\",\n y: \"y\",\n fill: \"val\"\n }\n ),\n // plot (first) default path as orange line\n Plot.line(kruskalPath, {\n x: \"x\",\n y: \"y\",\n stroke: \"orange\",\n strokeWidth: 4\n }),\n // add (first) corrected path on top in green\n Plot.line(kruskalHistPath[0], {\n x: \"x\",\n y: \"y\",\n stroke: \"darkgreen\",\n strokeWidth: 2\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"## Part 2","pinned":false,"hidden":false,"mode":"md"},{"id":1003,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":1013,"value":"// loss mapp regarding 2nd constraint of only 4-10 straight moves (might take some more time!!)\nkruskalHistMap2 = kruskalWithHistory2(blocks)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1072,"value":"// extracted default path(es) of minimum loss regarding constraint\nkruskalHistPath2 = kruskalHistoryBacktrack(kruskalHistMap2, blocks)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1046,"value":"// minimum loss is the lowest reachable value at the destination (i.e. in the lower right corner)\nresult2 = Math.min(\n ...Object.values(\n kruskalHistMap2[kruskalHistMap2.length - 1][kruskalHistMap2[0].length - 1]\n )\n .flat()\n .filter((el) => el != null)\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1083,"value":"Plot.plot({\n aspectRatio: true,\n axis: false,\n color: { scheme: \"PuOr\" },\n marks: [\n Plot.cell(\n // reformat array to objects with x/y coordinates for plotting)\n blocks\n .map((row, y) => row.map((el, x) => ({ x: x, y: y, val: el })))\n .flat(),\n {\n x: \"x\",\n y: \"y\",\n fill: \"val\"\n }\n ),\n // plot (first) default path as orange line\n Plot.line(kruskalPath, {\n x: \"x\",\n y: \"y\",\n stroke: \"orange\",\n strokeWidth: 4\n }),\n // add (first) corrected path on top in green\n Plot.line(kruskalHistPath2[0], {\n x: \"x\",\n y: \"y\",\n stroke: \"darkgreen\",\n strokeWidth: 2\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":923,"value":"## _old stuff","pinned":false,"hidden":false,"mode":"md"},{"id":17,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":173,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}