Advent of Code 2023 - Day 17
Mix.install([:heap])
Sample
sample = """
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
"""
"2413432311323\n3215453535623\n3255245654254\n3446585845452\n4546657867536\n1438598798454\n4457876987766\n3637877979653\n4654967986887\n4564679986453\n1224686865563\n2546548887735\n4322674655533\n"
Input
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
"""
"122122122221111223212131233223113223121333442231421433142332434134225233545342212211333112344344134442142433223412123123222112313121212221212\n222211221221231312321313313211342343411142324132123121134452332445155511344312331454432211221131443421221311311132313213121113133212212121121\n122122222123123112133333323222434211131132342432414314214452412531552132441122435121513351133144143322231342334223133211113332223112112212121\n121121122123221323133133124121313314444133314314111435332133355334444335454224312242224554224323414441121443212123222111111321321211121211212\n221122211323221232131333113424242413333242343434255431431524222114514555335533141355541521354112112323124134232112232412122113112231321212221\n122112113332111112211312241113114222334131115345325525553252224253442114313554141223521124145541224124314212142143231424133222231131333222211\n212212213321332113123242342411311111433442125134332211522512512135134454413433131555542522225543342113244321143124141111333313212212211321211\n111222113233231131222412143432342332212424325445154122325221333315223121441513551143423434221424535543443413414433343312211133122213311321111\n121122211212132122314144412132113122134521143321315442521141334521433553332314111441535455212441221412133441223422412413323113211321312211211\n121123313221131212422134134333321412515231255135114131115445421335451435423235211523233534133251531525332444243321231442133141331131331111311\n111321111323223132223324141431314353242311313155433331232415512425453645632225443423445133351122555413323232212313234221111112322131222113221\n213213233232223221144222214333434454513214544423255231433153443662543666342462636543433334445414545114133442433314231223211422211322312332323\n111221112223232243122122321421212241245125114454522522365543465656546642224263635556542642232214554245131431244342333332222233433111112222223\n233312212113123412143231124323422244335132153244522426656525464342366364422443356424233464621455534322155241541431411413441431421111131232332\n233211113333131421333443321151351344444113423244242646332566664266222556455466524354242644245335555232234433443223513323443142441123222111133\n312111233113311341414414431232342323214531455545553566654635256333552425266345422365656324526326425541151541544212511221434432244122222322313\n131332122131314111114323133241451244423521311354233425236524622465555445536565342435565336563325432514153221123314214123332331434141311113222\n231231311222331412324132154121355133321532234534343363466266542355662434334363442553244224224352564632515513424333425211241232312424422121332\n223313133214123314124342111353115332512446333635346644355425364423236256333435432425526444236666362464331343231251553453142224341133421111313\n332113123232234221124212545411551211254546423543323364625245243255345523262644624325265253334354625244354135354511121431232413344232242213122\n233323232121141443421251534243342514544532562336364566523455335463363576553654232523234463556234455234422132255555211315532434442233422312122\n212132232144234422134245243255112345524352552542455453443225565345577474547767565755345256433554633653546641242421312111522223434442124231223\n123321413434131222234421344553411334245226356625435233656577566553337746744743635774375326542552543223464223514114435131312133323313214422112\n331311433212424412324553455113141542523236246546552444375543467447566434346775647346346635636355362654525644235533342342445333422114144332112\n122313422432333243535141412111226566244363245465533665553657737566555564475644565467446545343254254632336563243412543535354334143232242421231\n222334443144224321514322454123462643226424362235574733446377737444643675636375653456655733776543463333422646536453112544535215124231432144411\n113442144242323332354154544325335642225352265663373764434446653675433547735435365476647645647754432256565226223651115542155254311121212212243\n113313124143434211345425154435326642625564656457346447377547765676634654653357374643773357345446635533456564663622454441423212422234234322433\n313222242331414514413444255555253253234656227456433775577557745353634344377335436455677376744456367564626234525346523413" <> ...
Part 1
defmodule Part1 do
def parse(input) do
input
|> String.split("\n", trim: true)
|> Enum.with_index()
|> Enum.reduce({%{}, 0, 0}, fn {row, y}, acc ->
row
|> String.graphemes()
|> Enum.map(&String.to_integer/1)
|> Enum.with_index()
|> Enum.reduce(acc, fn {cell, x}, {map, max_x, max_y} ->
{Map.put(map, {x, y}, cell), max(max_x, x), max(max_y, y)}
end)
end)
end
def dist({ax, ay}, {bx, by}) do
abs(bx - ax) + abs(by - ay)
end
def opposite_dir(:north), do: :south
def opposite_dir(:south), do: :north
def opposite_dir(:west), do: :east
def opposite_dir(:east), do: :west
# Special-case for the start where there's no previous direction
def opposite_dir(nil), do: nil
def a_star(map, frontier, goal, visited, max_x, max_y) do
{_, {x, y, dir, in_a_row, cost}} = Heap.root(frontier)
if {x, y} == goal do
cost
else
{frontier, visited} =
[:north, :south, :west, :east]
|> Enum.filter(fn new_dir ->
new_dir != opposite_dir(dir) && (in_a_row < 3 || new_dir != dir)
end)
|> Enum.map(fn new_dir ->
{nx, ny} =
case new_dir do
:north -> {x, y - 1}
:south -> {x, y + 1}
:west -> {x - 1, y}
:east -> {x + 1, y}
end
{nx, ny, new_dir,
if dir == new_dir do
in_a_row + 1
else
1
end}
end)
|> Enum.filter(fn {x, y, dir, in_a_row} ->
x >= 0 && x <= max_x &&
y >= 0 && y <= max_y &&
!MapSet.member?(visited, {x, y, dir, in_a_row})
end)
|> Enum.map(fn {x, y, dir, in_a_row} ->
{x, y, dir, in_a_row, cost + map[{x, y}]}
end)
|> Enum.reduce(
{Heap.pop(frontier), visited},
fn {x, y, dir, in_a_row, cost}, {frontier, visited} ->
{
Heap.push(frontier, {cost + dist({x, y}, goal), {x, y, dir, in_a_row, cost}}),
MapSet.put(visited, {x, y, dir, in_a_row})
}
end
)
a_star(map, frontier, goal, visited, max_x, max_y)
end
end
end
{map, max_x, max_y} = Part1.parse(input)
Part1.a_star(
map,
Enum.into([{0, {0, 0, nil, 0, 0}}], Heap.new()),
{max_x, max_y},
MapSet.new(),
max_x,
max_y
)
638
Part 2
defmodule Part2 do
def parse(input) do
input
|> String.split("\n", trim: true)
|> Enum.with_index()
|> Enum.reduce({%{}, 0, 0}, fn {row, y}, acc ->
row
|> String.graphemes()
|> Enum.map(&String.to_integer/1)
|> Enum.with_index()
|> Enum.reduce(acc, fn {cell, x}, {map, max_x, max_y} ->
{Map.put(map, {x, y}, cell), max(max_x, x), max(max_y, y)}
end)
end)
end
def dist({ax, ay}, {bx, by}) do
abs(bx - ax) + abs(by - ay)
end
def opposite_dir(:north), do: :south
def opposite_dir(:south), do: :north
def opposite_dir(:west), do: :east
def opposite_dir(:east), do: :west
# Special-case for the start where there's no previous direction
def opposite_dir(nil), do: nil
def a_star(map, frontier, goal, visited, max_x, max_y) do
{_, {x, y, dir, in_a_row, cost}} = Heap.root(frontier)
if {x, y} == goal && in_a_row >= 4 do
cost
else
{frontier, visited} =
[:north, :south, :west, :east]
|> Enum.filter(fn new_dir ->
# Can't reverse
# Must travel at least 4 in a row before turning,
# unless this is the start
# Cannot travel more than 10 in a row
new_dir != opposite_dir(dir) &&
(dir == nil || (in_a_row >= 4 || new_dir == dir)) &&
(in_a_row < 10 || new_dir != dir)
end)
|> Enum.map(fn new_dir ->
{nx, ny} =
case new_dir do
:north -> {x, y - 1}
:south -> {x, y + 1}
:west -> {x - 1, y}
:east -> {x + 1, y}
end
{nx, ny, new_dir,
if dir == new_dir do
in_a_row + 1
else
1
end}
end)
|> Enum.filter(fn {x, y, dir, in_a_row} ->
x >= 0 && x <= max_x &&
y >= 0 && y <= max_y &&
!MapSet.member?(visited, {x, y, dir, in_a_row})
end)
|> Enum.map(fn {x, y, dir, in_a_row} ->
{x, y, dir, in_a_row, cost + map[{x, y}]}
end)
|> Enum.reduce(
{Heap.pop(frontier), visited},
fn {x, y, dir, in_a_row, cost}, {frontier, visited} ->
{
Heap.push(frontier, {cost + dist({x, y}, goal), {x, y, dir, in_a_row, cost}}),
MapSet.put(visited, {x, y, dir, in_a_row})
}
end
)
a_star(map, frontier, goal, visited, max_x, max_y)
end
end
end
{map, max_x, max_y} = Part2.parse(input)
Part2.a_star(
map,
Enum.into([{0, {0, 0, nil, 0, 0}}], Heap.new()),
{max_x, max_y},
MapSet.new(),
max_x,
max_y
)
748
