30:T4e3f,input = `122122122221111223212131233223113223121333442231421433142332434134225233545342212211333112344344134442142433223412123123222112313121212221212 222211221221231312321313313211342343411142324132123121134452332445155511344312331454432211221131443421221311311132313213121113133212212121121 122122222123123112133333323222434211131132342432414314214452412531552132441122435121513351133144143322231342334223133211113332223112112212121 121121122123221323133133124121313314444133314314111435332133355334444335454224312242224554224323414441121443212123222111111321321211121211212 221122211323221232131333113424242413333242343434255431431524222114514555335533141355541521354112112323124134232112232412122113112231321212221 122112113332111112211312241113114222334131115345325525553252224253442114313554141223521124145541224124314212142143231424133222231131333222211 212212213321332113123242342411311111433442125134332211522512512135134454413433131555542522225543342113244321143124141111333313212212211321211 111222113233231131222412143432342332212424325445154122325221333315223121441513551143423434221424535543443413414433343312211133122213311321111 121122211212132122314144412132113122134521143321315442521141334521433553332314111441535455212441221412133441223422412413323113211321312211211 121123313221131212422134134333321412515231255135114131115445421335451435423235211523233534133251531525332444243321231442133141331131331111311 111321111323223132223324141431314353242311313155433331232415512425453645632225443423445133351122555413323232212313234221111112322131222113221 213213233232223221144222214333434454513214544423255231433153443662543666342462636543433334445414545114133442433314231223211422211322312332323 111221112223232243122122321421212241245125114454522522365543465656546642224263635556542642232214554245131431244342333332222233433111112222223 233312212113123412143231124323422244335132153244522426656525464342366364422443356424233464621455534322155241541431411413441431421111131232332 233211113333131421333443321151351344444113423244242646332566664266222556455466524354242644245335555232234433443223513323443142441123222111133 312111233113311341414414431232342323214531455545553566654635256333552425266345422365656324526326425541151541544212511221434432244122222322313 131332122131314111114323133241451244423521311354233425236524622465555445536565342435565336563325432514153221123314214123332331434141311113222 231231311222331412324132154121355133321532234534343363466266542355662434334363442553244224224352564632515513424333425211241232312424422121332 223313133214123314124342111353115332512446333635346644355425364423236256333435432425526444236666362464331343231251553453142224341133421111313 332113123232234221124212545411551211254546423543323364625245243255345523262644624325265253334354625244354135354511121431232413344232242213122 233323232121141443421251534243342514544532562336364566523455335463363576553654232523234463556234455234422132255555211315532434442233422312122 212132232144234422134245243255112345524352552542455453443225565345577474547767565755345256433554633653546641242421312111522223434442124231223 123321413434131222234421344553411334245226356625435233656577566553337746744743635774375326542552543223464223514114435131312133323313214422112 331311433212424412324553455113141542523236246546552444375543467447566434346775647346346635636355362654525644235533342342445333422114144332112 122313422432333243535141412111226566244363245465533665553657737566555564475644565467446545343254254632336563243412543535354334143232242421231 222334443144224321514322454123462643226424362235574733446377737444643675636375653456655733776543463333422646536453112544535215124231432144411 113442144242323332354154544325335642225352265663373764434446653675433547735435365476647645647754432256565226223651115542155254311121212212243 113313124143434211345425154435326642625564656457346447377547765676634654653357374643773357345446635533456564663622454441423212422234234322433 313222242331414514413444255555253253234656227456433775577557745353634344377335436455677376744456367564626234525346523413234531444111124123231 234124424214211524123352224626233325345524664473373535773347657456436565357553375563677455675434564622453556536223343312211135132434143343241 314223324221211151133432356545644332443347777536754354374665345545747757547557536636455566356777634676343653623666253552425151125111313124133 411432414444422443515413332323655623663677673645546774756743445545884584744568887546563435746377776743354365536655346324314234524212431312341 112244323223411445151512662434565532454734755653547347767358748877755884777648584548653743775573637777554466525633426251432231415131122244131 331212134433452323233434542562336565263344644744333575576784744686467788544678847876764347776556673434767726536235644342145154533443223141311 144223143322414541141526263242263466435443573476757354555687486788744755578445677587574655755664654345446634545543225643112344243425544243214 211211133311315353455524632446523366777546655477466388688487754875444878458554748868687674647735745546477555655535423234422322223422214122332 233323332451434545112243556662225233665445763747333558657577647644677878675688446866665464776546644334363437442454266655343334213213321233324 231312413341215423223635646634566355537566476444388687576655766687788565766688684447666678646537343553547554455643546642542312435344351423122 313223325341552155426532255526425546547737657655545485445645644747875684466476788564646675675847676434367747353455636325554111223444524434421 313123233242152334525566532545665344375473366755655487584557568465585847744686484446444487557857766336674354743262456225534442324142434414413 431431124241141212263254643262673746433375466588677858465664875557485554584766657847458665474787474354537364577626364443552224431324243433213 221321314531554134523344446564537455733736634687688755447577544887569678585677447464647885478768547636453463633633542243445235152222312232431 131134115135241554536422256224464564746667668658758478867875658586995598966779877578558658875764747577336564337734346462264545123321353322413 123421114152115123452565655566657355443454564546865774587649578598978599655999858585447488774785576553346375767545452523653445151135523321234 224422431425553423622462325637343634776737677744464464467598696979997867696898756585984566476466885674336435355455753322323433232411545155312 414311352435124263223444455635745467476664887464785748566656865567786877787658858859777744487568656867536377353476452346262556224511521225443 223114153345343246554656663354535563567585655685876555979689788777855688765667896889786657586464687878477477365356743325236635311242532412242 123122325432225325522362544773453743736464578484748658666665985899785775886888579795689885885854847748647737737467434332235334651541341553334 443352143214532263453554427657664436735458865786676655579768896689789986987959875959755569877767477557544556336777576453644354561324451251512 121452413251312242546332336633337373756788687555766968565968979666787997968597868556877586876656485877786653354633564442463442362541244125224 424124541535452643445252476377676354374875445574885857878987987657655556889585555975795677966654647686757575436656633742254463335251221312344 442231145454245523353645554743563557867448558568969796957867599569966898697686599585997577896864466476674577455436764545262645522432355145213 233354114345336444533456437343457777658566566456877668559598895867796987768986685767756566857885755778745887467765644633562255433431234351143 324253342114343544244534675743375535768786586887668888886795977869879878866769698876985686759796678654768474747557563442633532665644452515454 114221444443244223644424366376364386648564655896586789898968767796786977779787696888599798697978788567677757666633534565646253566451334212454 231324515512325242535245455467675768588854567989787886666878776967999767878879879979996998665685875667865886455364335677254455642324552234125 123335241124524366456344746675645476445445564767797955968577686666686667788996777698895868778677795767786486845454354747562263264622152553142 231312152241525364542236367736373868458667666779885897585667886777666696769996697899878976676998677778578677886463537647626326654663511112343 331331513311444364256353367734745744545664856969878699566968868997779887978889766677897775886779767476578544443633553536436626625345313454421 311541535146254465342645333566578678568468487678685879887799978886979689787667788999676767566578997656474678758355474646655262523522152524231 451251515414632223243357445374375787644478567996798579778668797886877698979789768899788686758566669664576746684677667734554226323432313522344 312435235356534526643344674354564688886666767659955698886877689967676778876696679986799865887856759577778867444534473534334252443642442551112 315222511556322242562347537534678876487554978596598969689897699688888889888986769669666697798777697575588744547554556557366454224542353433353 425515431314443324446456745644487668777765897686895879799686896697779989879978988786779898678757569666776745678873556477463454524525151442254 131431325313553226425634656745565844664566576586556979796877886679989997978989987667666976655865988864865656775744335663443624652436424325531 331152143452533542664477374777485676554479868958665977868688897897877887987997896899887967697857559567767655574573444337555653226566254113133 255253351164333322455334454735364887645786757955765868767899867977879879977989877699786799988987876687644786656753774437344362634226212342223 341325252336244465354535753473368785645846688777855996896698888778787787899797988879866967688798779898487758847847636774576563352656341411335 412155212433254555566676547343356768875455868866568967667697889887999797977897778886989999666596889665865858768577775545342446542456534425541 511435114262464254434567436757745848466689665575568686766977899878799887898799787898779988976858986899585846555764436555672646532255213214135 235135235456433443255643733544444586687565798557565898666868877777977789899899879876896676779975778859887665874733467535353655622336411132154 355221152564242253526675554634758687685569665798667968999689998977799898988999979779689668679588596899447685845873474455345566623253441453525 144515535232354443223644466635648545558655587768758978796698887978797979888787877966889799779769775868488586668456563746574453352624611541545 551231142423244223353464335537757654777546558756665779688789797788977778887898799779869666789859799879888488746454467775676436542263235131445 522543525436556635654735466736586558485855979659958799699677767777888978797789788897897666867797599969877576665645734356433246526233343135513 151215345452433662463573567646376747544748576798589888998677769787877978877777789996788667685586578587576868646874634436646454265322235432555 433212251254262522364635745743388864886455758886698968977779666988789797997788796966768678966878888568484854776463757346645435553465313553322 544132151312562323225767567633447447857689758975596889667789979987779877897889989898776888859758688957655588855443657477473565664543214423442 132533522454443664563553646546584784544867596878765666877698877999897889777999778796867869999695998698466685875766733646335435456534133231411 431142312344522524452477637567588555474688958959868596969676998879978987898797688989986866685975656554558746687865453566353535655653123241131 115455114346263343465744776567338855564648579889569857869987778876889788878798697766868979689999857858778884466774336433572662363526312322114 124423142232246442653755647363365877767867897756668575996866767687886889987789797967798969958756997668547678466746454443532323233226355235342 232532223216264564333443766675555444844655458885595987989996679699766776878888988667899876985589999645778885546437665576535456356642433242555 112435522536545326463444747756576778855777776896885578668967866998798767676789699776896967799668777756457777786345647437625425325262514152431 141255321434436364434567776573475764878488487879687685758897897779699968677997799868976688657969896464844867884637443556366336564243454535311 111534441325652665664446566674344848447887547897677867968687879976698878888786777988968776987886586777846485554346366733556533552624123255542 331325221254333336643467375367454374854656644655685976999896866669778968799896969778656688787659777756487844455477337464434225235431353141243 341524514145465442443636437655366665675574545698896886987596668976999767966898986968989897676696584865466667744656347443222636656523455235322 341525245521446332553646463474543665645656476868786995857565776787899669777798866678799789599766976878545456745456454434636642446454544134545 431212551454443563543546343347764754885487858649897676956988866779787687876869767655985559587576884558657678673546353755553635464253522311355 442223245413436353365545777475454566548786775558887889575775659867997769898976857796586996998585458867454784433544534336365626436443542114324 412521114534256333553563253657345445578574748884966896579999556586986787688875965656899886565886687664654576346373446346533345342425144253542 141134244215513433356245255736645756358576765676879558578887759589655659999659597659886999786666675568584467535654753662245545242244331433321 241124212314412324422333464566774476578555555746885867968668765795577777868559659587655575959755765465874737343774753562366426635525432324422 344321454522543342555342656764553677656744757674764785995877578857988666675575567558595899998445857848587745663745377424322622225412211551113 142321545532451526325642547477757566378565868764557568666866966798869875698666797598566858655664457575664364367637463545662436345233543455244 121325132533225424534264663333575675777477784764655885796558579879565689959755565968888854567464467584664756436763454322643335345134533322241 411132145535425426545646566554747547667358468876885854897898696965559797959659888786656978844765445685537747477534546535554653641345413535442 443224242533213122545543223635733774363436887564777678764996786677557569568788669698974787688878444488767765436347462324543446414522545514322 213112524141422325632222556463336333457753845647454658644865977989779789559688975897475844844766754565777344463664552224425654444353122512221 123443432412252524564255362252736643346755588866445576656678748669985758875867768544564467884874488756735576653545464556263343231123111522321 211323341425143324532535522334757677737474375667554654845878448789676575559565755844675457876474846747646757737465642253334234224155335533414 111432111251144512226623533254237535754663575485675544765887485484567486767488478777444576487475875457644745443735442644555544454253133512231 333132344143445411444242323553364644365464444367778676886556648654665466444744454655845865464564536636477763643554632323522555531534144331442 244323122552131443225544335344342767763474577436866475644768574755456444465858447688468646585854777676374647546452622455344222113421143212122 342231141215552514353236463563632665374337734364468865868546455888557547486866488867574884486876376443635754362234234533421223244453342434434 123124122115243354253633543434444367464463677335536567748475445854678657857686778754875678554764764344744356753232324645543552134132232311413 412322222335233534224524645543263436773564533357454384844565855787755756655857656556775447657356465376444574535325643655232224413244242422241 442124331351453453124232352455644554433457574575654367447547444644484764557787767678565583555446344647463335334565544545134555514343421111212 222431312412133313414544343363225345263337357477543357466876456578557875877564574776863577563645546533577734644235445653433223115555413123221 131142311424325131231415626545565522454765756454433633355654786445568748857677555746773554366765445745554525326622254363353251441122313112432 332332333141444153453342266254436226562646347634565634766375744666754755757747473453555467576445474576726532225334562353311455111253244421433 224444231141243443114221246563325466323637576764337656757766755435564377745535757444554644733745543766455355553252536334133443232223133343211 133433133133432512223141551334545556423623267367767544777346476677533345447344753644364546563644456424436232554434623334555321531422132144432 113233124412224451124113215455646254646222225767467475745657746436546455745637665743555573675466735433654535623522543143541252412133344213133 113313113211312333511154552344363326562554546537466665744576457647554346656734756374654377776545545235644646664262515124413312421141213121323 322222421342222214252232215221435422626363454264634545634676663446357773673747573356657377576367455445624632655425434255223522324111123233143 111322131331343245153453232455262354632243324442567445464764374563466356563433437566763536645436456656653443332235534125521522233144343121221 133324123332312444331234225442144255265352646244532253575445466747744556753756534345533443534236655362622225363354323122255134344334341431222 313314123434442124331334115143441553656224434463336433763645464656564773553454765757377755433623554654556242621253142342224422433444142414222 113232423231443231215512312555324225222535255224542442362635577345446476355436667773376632652343234523454234432555442151434342333334234331133 111221111223233443443513121412314425366244523343343363346542377465367435774664773666342342464454634465656364152515332142331234424343341113332 123123131422312322244134515214441154254626336325442536544262626326425654545246352322256622345565455425654132445343443221334443442344332131132 321223131221322223424321343535452552544643563425665663523652322466242442625366465252244445533355526523361235252141251151443433442124111112311 311312213323313332331111342422441335255544255533622536525426325635454556233265652646556652264344664363441313232433113353213111311112332132131 212322231122222112122432215115412133452444143534343236642464362242254462346523633246526625322335356435211312122232452444222133334414213221113 121221313222313433332143242344531312422454351362665223243633332665344332342636353543543423256355435554115254431122425211324233313242312232111 223221132233331323111144312125545255234555545132336362242365466543245433652666455322542425323335251452515243245532544124442343122333331333321 123222322233243112214113133123524333145353344253232643624253565332666444256556343643323223636624214313113234353353412132443232224331221321323 112223231132232214112441124433412223131511441332144236555624533625326635255544253436325565225422351433334314423411343224222323242312111312133 211131221333311111213411432341224154123123133213515431566564646662444222522324253444522622244144454154425142324341144331421244443223213213232 222111122132232224442324344124122123145224125132335155435126345534565663625452325465323554352221224252232244354223233123243143132312331212232 222133212113123231111224134212122153524554333333545213311153115535525423242642442243225422214244542445413325424323323121312422322132222332312 222123213213213232321331324114422443445312325135244243412455434334354311235235431455431554343125142511555353431333143213323143311121132322311 211213333322113111322243441224441224331423432342354253312145451242413254113552255541333211122424333322523224332234331241223323323322333212221 211112231331213122221322142211314421423152552133251424314431245455332235144212425512331213434225534511323334233142443124423132222322322222121 212122111211312312131311212444422113421122214351134125323221441453341253521324413552232513235135452552141234211333233413213333331112111112211 111211211233232221231332234241143232142124231314152232241153452525451125324423425353544334544233125321313124222331431212222231121213322221221 121211112132133312113121214332221431322243421112211153533111512234544332113252332432432345454334113213213231341443334233123121231132132122112 111222121232211113231212313332413312441232221142313113334242353313211241554252255321445435111412223321342124431124242322212121111113121121121 222121122221132313332132311231324312421333341214231343251244511153233344424212224145455513442444314313441334222211132131211221133322212122212`31:[] 2e:{"title":"Advent of Code 2023 - #17","cells":[{"id":0,"value":"# Advent of Code 2023 - #17","pinned":false,"hidden":false,"mode":"md"},{"id":11,"value":"This is [dijkstra](/@fil/dijkstra) with an additional constraint 🤔","pinned":false,"hidden":false,"mode":"md"},{"id":543,"value":"show(tree01)","pinned":true,"hidden":false,"mode":"ojs"},{"id":122,"value":"cost = [...input.replaceAll(\"\\n\", \"\")].map(Number)","pinned":true,"hidden":false,"mode":"ojs"},{"id":29,"value":"W = Math.sqrt(cost.length)","pinned":true,"hidden":false,"mode":"ojs"},{"id":37,"value":"I solved this initially with a suboptimal approach; now, cleaned up: a node is a position in (x, y, z) where z is 0 if the previous movement is horizontal, 1 if vertical. We create a graph for all permissible connections between these nodes, and compute the shortest path from either (0,0,0) or (0,0,1) to either (${W-1}, ${W-1},0) or (${W-1},${W-1},1) with Dijkstra’s algorithm. We import our implementation:","pinned":false,"hidden":false,"mode":"md"},{"id":56,"value":"import { shortest_tree } from \"@fil/dijkstra\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":467,"value":"The graph is specified as three arrays: sources, targets, costs. The function below takes as arguments the cost matrix, and the constraints on minimal and maximal edge lengths, and returns the graph:","pinned":false,"hidden":false,"mode":"md"},{"id":474,"value":"makeGraph = (cost, min, max) => {\n const sources = [];\n const targets = [];\n const costs = [];\n for (let x = 0; x < W; ++x) {\n for (let y = 0; y < W; ++y) {\n for (let z = 0; z <= 1; ++z) {\n for (let dir = -1; dir <= 1; dir += 2) {\n let c = 0;\n let x0 = x;\n let y0 = y;\n for (let i = 1; i <= max; ++i) {\n if (z) {\n y0 += dir;\n if (y0 < 0 || y0 >= W) break;\n } else {\n x0 += dir;\n if (x0 < 0 || x0 >= W) break;\n }\n c += cost[x0 + y0 * W];\n if (i >= min) {\n sources.push(((x + W * y) << 1) + z);\n targets.push(((x0 + W * y0) << 1) + (1 - z));\n costs.push(c);\n }\n }\n }\n }\n }\n }\n return { sources, targets, costs };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":690,"value":"graph01 = makeGraph(cost, 0, 3)","pinned":true,"hidden":false,"mode":"ojs"},{"id":503,"value":"tree01 = shortest_tree({ graph: graph01, origins: [0, 1] })","pinned":true,"hidden":false,"mode":"ojs"},{"id":515,"value":"answer01 = d3.min(tree01.cost.slice(-2))","pinned":true,"hidden":false,"mode":"ojs"},{"id":628,"value":"---\n## Part 2","pinned":false,"hidden":false,"mode":"md"},{"id":530,"value":"tree02 = shortest_tree({ graph: makeGraph(cost, 4, 10), origins: [0, 1] })","pinned":true,"hidden":false,"mode":"ojs"},{"id":533,"value":"answer02 = d3.min(tree02.cost.slice(-2))","pinned":true,"hidden":false,"mode":"ojs"},{"id":583,"value":"show(tree02)","pinned":true,"hidden":false,"mode":"ojs"},{"id":635,"value":"---\n## Part 3\n\nThere is no part 3, but since we generalized, let's make it interactive. Note that there might be no solution when min=max is not a divisor of ${W-1}. (Same, of course, when min > max.)","pinned":false,"hidden":false,"mode":"md"},{"id":641,"value":"show(tree03)","pinned":false,"hidden":false,"mode":"ojs"},{"id":652,"value":"viewof min = Inputs.range([1, 10], { step: 1, value: 1, label: \"min\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":655,"value":"viewof max = Inputs.range([1, 30], { step: 1, value: 1, label: \"max\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":647,"value":"tree03 = shortest_tree({ graph: makeGraph(cost, min, max), origins: [0, 1] })","pinned":true,"hidden":false,"mode":"ojs"},{"id":630,"value":"---\n*data & visu*","pinned":false,"hidden":false,"mode":"md"},{"id":542,"value":"function show(tree) {\n let node = d3.minIndex(tree.cost.slice(-2)) + ((W ** 2 - 1) << 1);\n const path = [node];\n while ((node = tree.predecessor[node]) > -1) path.push(node);\n return Plot.plot({\n inset: 2,\n grid: true,\n x: { domain: [0, W - 1] },\n y: { domain: [W - 1, 0] },\n color: { scheme: \"blues\" },\n aspectRatio: 1,\n marks: [\n Plot.raster(cost, {\n x: (_, i) => i % W,\n y: (_, i) => Math.floor(i / W),\n fill: Plot.identity,\n interpolate: \"nearest\"\n }),\n Plot.frame(),\n Plot.line(path, {\n x: (i) => (i >> 1) % W,\n y: (i) => Math.floor((i >> 1) / W),\n stroke: \"orange\",\n z: null\n })\n ]\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":3,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}