README.md

Advent of Code Day 17 - Part 1: Clumsy Crucible

Problem Summary

In this challenge, the objective is to navigate a crucible filled with lava from the starting point to the destination within a city grid. Each block in the grid has a heat loss value, and the goal is to find the path that minimizes the total heat loss while adhering to specific movement rules.

Movement Rules

• The crucible can move up to three blocks in a single direction but must turn 90 degrees left or right after moving three consecutive blocks.
• It can turn before completing three straight moves.
• It cannot reverse direction immediately; it can only turn left, continue straight, or turn right after entering each city block.

Modified Dijkstra's Algorithm

We adapted Dijkstra's algorithm, traditionally used for finding the shortest paths between nodes in a graph, to fit the unique requirements of this problem. The modifications include:

1. Graph Representation:
   • Each position in the grid is treated as a node.
   • The state of each node includes the position on the grid, the current direction of movement, and the number of consecutive moves in that direction.
2. Priority Queue:
   • A priority queue is used to keep track of the nodes to be processed, prioritized by the current heat loss.
3. Processing Nodes:
   • When a node (grid block) is processed, we calculate the heat loss for all valid next positions based on the movement rules.
   • The next positions include only those blocks where a turn is possible, ignoring straight moves directly to the next decision point.
   • This significantly reduces the number of states to consider.
4. Symmetry Handling:
   • North and south directions are treated equivalently, as are east and west, due to the symmetry of turning options.
   • This reduces the complexity of the problem by minimizing redundant paths.
5. End State Check:
   • The algorithm terminates when the destination node is processed, and the least heat loss path is found.

Using this modified approach, the algorithm efficiently explores the grid while adhering to the movement constraints and successfully finds the path that incurs the least heat loss.

Challenges and Solutions

• The main challenge was adapting the algorithm to handle the unique movement rules and efficiently navigate the grid.
• By focusing on decision points for turns and leveraging the symmetry in the movement options, we significantly reduced the search space and complexity.

This tailored approach to Dijkstra's algorithm proved effective for this problem, balancing the need to explore different paths with the efficiency of avoiding unnecessary calculations.

Part 2: Ultra Crucibles

Problem Description

• Similar to Part 1 but with different movement constraints for the "ultra crucibles."
• Ultra crucibles must move a minimum of four blocks and a maximum of ten blocks in the same direction before turning.

Solution Adaptation

• Refactored the existing solution to accommodate the new movement rules.
• Created a separate function for each crucible type, sharing the core logic.
• Adjusted the range of steps the crucible can move in a single direction within the algorithm.

main.py

from heapq import heappush, heappop

def solve_crucible(grid, min_steps, max_steps):
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up

    # Convert grid to integers
    int_grid = [[int(cell) for cell in row] for row in grid]

    # Priority queue: (heat_loss, x, y, direction)
    pq = []
    heappush(pq, (0, 0, 0, None))  # Start at (0, 0) with no initial direction

    visited = set()

    while pq:
        heat_loss, x, y, direction = heappop(pq)

        # Check for the end state
        if (x, y) == (rows - 1, cols - 1):
            return heat_loss

        # Skip if this state has already been visited
        if (x, y, direction) in visited:
            continue
        visited.add((x, y, direction))

        # Enqueue all valid blocks to the left and right
        for dir_idx, (dx, dy) in enumerate(directions):
            # Skip the straight direction if we have an initial direction
            if direction is not None and (dir_idx == direction or (dir_idx + 2) % 4 == direction):
                continue

            # Move within the allowed range of steps in the new direction
            for steps in range(min_steps, max_steps + 1):
                nx, ny = x + dx * steps, y + dy * steps
                if 0 <= nx < rows and 0 <= ny < cols:
                    # Calculate the new heat loss
                    new_heat_loss = heat_loss
                    for step in range(1, steps + 1):
                        new_x, new_y = x + dx * step, y + dy * step
                        new_heat_loss += int_grid[new_x][new_y]
                    heappush(pq, (new_heat_loss, nx, ny, dir_idx))
                else:
                    break  # Stop if out of bounds

    return float('inf')  # Return inf if no path found

def solve_clumsy_crucibles(grid):
    return solve_crucible(grid, 1, 3)

def solve_ultra_crucibles(grid):
    return solve_crucible(grid, 4, 10)

example_grid = [
    "2413432311323",
    "3215453535623",
    "3255245654254",
    "3446585845452",
    "4546657867536",
    "1438598798454",
    "4457876987766",
    "3637877979653",
    "4654967986887",
    "4564679986453",
    "1224686865563",
    "2546548887735",
    "4322674655533"
]

least_heat_loss_clumsy_example_1 = solve_clumsy_crucibles(example_grid)
least_heat_loss_ultra_example_1 = solve_ultra_crucibles(example_grid)

print("Least heat loss for clumsy crucibles first example:", least_heat_loss_clumsy_example_1)
print("We expected 102")
print("Least heat loss for ultra crucibles first example:", least_heat_loss_ultra_example_1)
print("We expected 94")

example_grid_2 = [
    "111111111111",
    "999999999991",
    "999999999991",
    "999999999991",
    "999999999991",
]

least_heat_loss_clumsy_example_2 = solve_clumsy_crucibles(example_grid_2)
least_heat_loss_ultra_example_2 = solve_ultra_crucibles(example_grid_2)

print("Least heat loss for clumsy crucibles second example:", least_heat_loss_clumsy_example_2)
print("We expected 59 - clumsy should win this battle")
print("Least heat loss for ultra crucibles second example:", least_heat_loss_ultra_example_2)
print("We expected 71")

with open('map.txt', 'r') as file:
    grid = [line.strip() for line in file]

least_heat_loss_clumsy = solve_clumsy_crucibles(grid)
least_heat_loss_ultra = solve_ultra_crucibles(grid)

print("Least heat loss for clumsy crucibles puzzle input:", least_heat_loss_clumsy)
print("Least heat loss for ultra crucibles puzzle input:", least_heat_loss_ultra)

map.txt

123143232522132362565522552366665466444444354354765573477364677553744554544367373475353674435736776364364225646566345432455654256253553441544
513554112134545522424636644264364636423433734634574764734674335773453337467475335776347476447443456553366343436536344433322355656411245352352
334132411532364365225542263426336654323554453566537436754563453756534455435556373777356773767445744365753523332263433566233526636225333232555
341223414232233322244334453225423235453535467444774364576474666443637644447334656337367647536767347665647722454562236334622462526532224554113
215343144656422326322563632225254465556673677434733476346766774433675633335653457775633744455337667735437754532435256566345526254522523432513
531522235224332356225564244256645357353563766554375447737774333736636743354367366463643467455453765556744466332363636343265522424524536333235
212421462652356556432642564536626435646437465437576437636635743455373445563777734744465576766374365733673776555563656346653644636453546343255
423123235254552242326466625643534774755356775755337636444437344334374634756655457764573533564533345367676567753436432526334425236236454263525
254346522562326652524642646443446346777455654465765355455574365537546376354566455435565543346776743356655376355743626232244442423433462263144
131563556352364324236426466476453766375667746755765535735463747437467574353457477475535476557354643344676545775457474625533424565564322646425
242344435642542245466333334537333655373345664436737743455345376763757355737736353754344334645555754437335566477457657245533342454463346453322
424623432335543435435655363574573375335744564556647444437653885485647874464486464653546777574544536746666764646353734542442345434556635625245
554436643554335325233653537644666345344637363633535547576468768755485765566866658677875664445744744765355436337653355334652633666654253625445
424236626242463266666445564765645433767745635765367565746766646674476677556466648756555845367546534375475373774566335376352324554654635422242
234442455443342245553665555356654774463754343373544874574776858858855646555454467667766745875643757363337356353764473476662533365233645253354
564465353545656643633536546466765364673753344356656588677876788458456786665775557884554587644684763644677763777374454435534422652236555625355
246642462566353323463575567476673567373353637467568876478765776678757767644648444446874565558448663343375564547536344753575532424366352252455
446442435655646522453476334377546555737337447688674765784847476575864466456844675748785446676768676576675477476665766465773763343433422424455
642522452643426257675367345763656337673667755665764847777677765568587887544574748666654547887456648545535655647554435566333447236435665624653
542432253455644354733376755577435473677748878658657656854585646845546545847486866446744856845856485454634456546743734546573633546443332543564
533566253433224746667673465773656744738645657465658776567548777877477444748664647546478654785858585477445777777445745336654637336525653262255
535664336523624476776564674556543776768857874647754886685544658656668677484476578785774776858477468787588637446734554477763656645323536343422
532665655644274435445767654336667534578686466564455748875455877754478646885675747747678774655466647564857665556576365567476344554563636332225
366233346635447665565437737776767747657655647456844857465575477846765456486844758556886667845644768676786844444747755375474757774465526342352
243663253344676673647353636546666668768665655855577587666884676887577864675667757554855844778467765754847477566466465735364744746547235452266
466562626537467676663343457554386747774648854488684475768884578668865766447465784767654744757757477764686645858845445664577635653664435423644
335665444347357375634657374346655778554574646558855866588587568867966697579985668467487565686866678854888657684844357537364354366345765226323
636656354736453737536357653644878745667877474558548586775467958775995755887766588667644784746446874755776846576545353757535436374637445562555
524526236763676774564767643577557886465456655458545687549775766976675668585679699558678656884778887856474545888487463347757765365733445255325
224532565663535675346474354746846787466564688457546446689757555677576657875897669856585786644854685646567786656675843757377643453753736243333
646436267446563476744655546745487786648674656555764996886579757698788866759596556798669798877775878564455585554444786535547647436574575753343
325565243656354764566453786455756444867876785775869587987977995969777858866659969695698955695676874686777757467456468677464736443637554366534
556465556673456665647353766557674746468758686485657956676969696566667878956799656796558756958856646576556486845584475433563774443656676442463
644365475765446435545376467447776488477576887876565975758586575958997765699877597675866567557975945864548648448587486855776677334556373344644
645253467436477673557536755854757868656668488575955978686995977858965877975579979588865757659897568586777584585865887577755663667333757553242
435354644634775763464667766647776758478578597798556785679989795988656878688897978789868857995988978764864685744465884744766363365734756647526
236443563446637473555687468867486878566656979779796979857896668959576889579595876679568668978677889576588585766775474758457776747647434763544
223557347555533366474687458676466577444468888985889667596668899899889878555876989988976966786955575976846876558686767878565345545633434547444
345464666575656757346745488875864585748885857869555777665558765887569886997876668578795768657799967957756554546555578855566466654644743733364
224477635454537365676446774888868686766977766759975988898956965755855589995698888966569586879888585686997557565686587756678445434645754765546
536675635435677643444467485865756776877698869896669786787756695795658997899996985598578555655968698568769868848578488464655774455637477344777
634736656435343457786855786847654668657556876597669567768885875695899787987976589778897555558659978958956866474584446478777746765336753547374
655335455453344536466447548856578487795856675598697669958569669689887866986697969598876778997879866856768598868647745564885757355677363636766
435474455354463547465666476564646557596857769987659796597989976767997987976667787798678998795556699576695967744557886786464867375336667644776
336744444554374368577568455776887766569956798697599668555789687797967896967889787768686965798598699785559655766755466888455687675344474446667
464355746733557747478587877758747578975568676788876956957867886687776899997889968989796865656888796985598777586576874758684664873775764644535
546434665567577567668447466577645866859777566888569995877768876896886866887677669866699685759568889878996857665478775466745778756564666777734
577556637574353866474655886466488688555566986656995769997876876796976787877777967878887998589856886786559686765487646668568544746336663367365
764467765543455774868664674884767556679569965679669799876879668968678986998798776999668788869755855695786578596854468785887587665556677764677
675674775533467576656854778587757697989686595576677897767676798998799689878896699788988889876885655599658877659654565556464845743643647454657
464355335773576856486884576786586785669959956865769869997767798867866886698989766977697686989796589796897565687957864744675645888467433766363
357466766476366456884874777574567786977879765695889766998789966996976697888979787668869786979996696955679586996887567685884847775534544775375
555647566474678656544574556448679666858965775676798879687866687996667999687887996896699679897666896656879598589576485847545764844757334736756
467533464375678548444554874886665767889966867658896866686787799697899897986868979687779799979676977966968869658986578856464688486746365474536
666443356745375584645568846467698875877895687997677876869877799866666768787796986996787998799886997578996985656958444884688655754537353633733
575753773376574568775877765585985658877977786878879686969699779777899896799877789768689669899686797958585988697585764454884587888467665557666
537344544753477466848646867459659985859766668766788796686698866977777999999779667796889787869898665668567869955789878485686758445886336373375
434375643576748864555675847865657895758698976897889898977796797679798898987878677686688686888688988665797668687868854445758476856446573556755
765734633566855774447544878579955859878595557769786899669899898678998797977877976869986666899789976656895796687885648777555445868887364556776
575547657573664758648877756858695877959998766767778879876998887877888798798997977799687968867968686869658667986979758788855456774444647654643
544356664454756765887644445695896677567796986878877696898679689777788778799888889786977898876999668977689889579786676746576885644465337635766
653554366554747646668767588796796899975668887677677679868999979877999977787899979787878769968699697958688976697878567688657876855546534477547
357453443734546844675748775976676995757665967888887966978988877779888777897787797989678786678977688797756795857879697457848667867646533664655
776334634577545656568476867896555585658766986688769666677879798988887788788979879798767699989689977866999768956859676877768585577577556465645
643655363466478875574568847898695688658787867676666778867879999978989778898797798897789887967666976689557898598688689645875857474657556545373
757436346477475477645485656978865788869656867889767686896989978888779778897998999989777786897886678777898999566886768766757566544668554454674
653337674454876856878888468778968995985877876769697678778989879798799798877878788997989997977686879966966986795995777687485777445778563543635
457347476535446458854757447988757988978997786787766989869979977999979979898888799887797968888896998787796999877765989754488457778886447364477
334547743667778544667464765567688656599679898888669978677788788788879979999887798777888797777696689768586889678986595876685668684785656677664
374775447564765746577548785566655556679877776797886986788997879887979778779878997777798777967788996779576575676987589674785678444776654666474
537365567465786446464774768955877897565567968696696986999898789889788899787987987998889797877978896697886899556856958887784655548764877665433
366354653765664657857578775567898559575889997989776867869997879997789789987979999888889976989767877999865887568897995474678448864467633547357
664346577755766747686747466568897859969859687779766766799888878979898878877799878979889967889768968967965979859676887654767586774858476667773
364646753456457677484784469586666696686778696967768796997789788998797799777778987779898679796968996996755586577786987665587765578585553576757
466746336364775568644847747996789766985779698776896689897789789787877989797898798787988697686767978679587787998888698458857686847486675735645
454656653367888875465644777657976867875858998989967986979777789977898877877888789887978996786966867699896677879798759786546566775486434534373
644753356477864746758586675558887995657677699887887976977798778798878797788898878878796789689999676677975689868669558647745564648878573745476
363574337736654488646757669556697789795899986768878967867897799887789797877887888777977977766978976878987895567578577764648667758775334363675
675574473775886664477785589597988957575886787998976669877997887977779987778999898889876987869867887775657578976969987787544544774864765574676
563364457636686454785476867567699687658579679986989788868678787788889878798787877788878797866666977897576885668985559576684875588785556776676
675475466745564585854586557976896559758895697896887688997678979997798977997788898979869876799898768969579878588986588758677748475788733437454
634646354636777868875668784559769769585655898887999877678987787888997797987898987896698787686769998679585675575657675545446555567566543337565
657533773365674487847544576587688896589965597797999689767799799888898889987988977867887697768966677679568598559557694566844446477787557543753
354353673355775645675678454959668785787885999876697887877787779987979878999788998988877977967679977969975966796966678544776665447783337566363
544767457644748688468484547495895666759657656977877877987699769897878897798777779696976867998878989699699965766865985677464786454475757643753
764755677544667766557466754458858687558777999788668667776668978878878888877778986697976798899986776669598767696695584484675888877743533633374
555434665435654458854564874496659588789569755796978988669669866869686888987669776796689899687866675969676895588876754754488675675473465455363
564537374365484445774775468867755999779989598969966799997768867886896766677689876786878786678986796855765688799799587885568845756536377474463
657334756766785576868877677685896895989787766676767796879968787679789687889797976788696997876699778786788855558955688568865844684634373564635
573665375546465858684886677477797766569998669599798769979777699666689779777998688789687769978996769879869977895699447546556554578846445735436
443343357565565648548865567488956665675665997767897977778969999896797889688886999968969887686887555869587998859578787454885546864555475366676
634474575465635445648848475554577958686798965985967987799789898667776986889988878997966688899876789776586987855678886455468467676635736755636
464444446646376846477557556584565967987986596668868786667769698966779877686798787979988796976799789666995779875955664475788765566657664375346
477333473765376546866658545656588769977689678595777779696676968789688797889996679777986886866768757976889785677854454546744567553773644576766
743445343377675484745448667888868877758695585856989787697878986899798866898879966896677978866888857765796769698688556874584767483743646557675
463536736366635666475754768546457758697697775658795969696787666688778966688876867877766986689796886566779669665564447857485485687557375373544
535746676565734474684487775776857656977977786695857998786897767696868898896896976679669776585767789596798656774884756567454458847333365437553
535766467334657364587786677764767767869788769699999979558986688999779699986668678799996885868957675869968968684646874746778674844477547363377
547745464657455775584775674654554785778798975888879979865696669966968668969668676887789965757795577975558687685848564458477767336564565463334
377766676735375448455444675465446476598987895786769568868977687678876969678669899896966976899599786578598587877847847546565667373573773665743
353737675635354633544778764774755585775778656666599686789977759898686786789869688986799755966575788956875885747585446584474677473436477754765
457444337673347567767846864455765585696656956668698559859866888969997798796877968559666695667566579966657648568886654885468566536356375563737
237637737775774537557557486668487746465966877577789966658667667867577779966969996855689586998557568956587654566545868447667764453455636735445
664573534374543453776548567674684667457876977789897566969656959769756779955587897797656667759595665757998444564776864866544764753434674774653
465434747335645736344588767568458645768658786755798699576968787968676767788879776995795995566785889955978465876876586656777776447567537333452
242477446667634737654767875548767866457886665779867889589695985858886596759587756766995966566657765976488755866575564867676673677533437444466
436573643344744453775374566575466455666548667659975876867598796685957679886958578785759755889799855794675767455665668875654565737644747764653
364653345655334574355355486686557746857586796598667855997789689589659689798775578786785778996785968968574566688775876446863373434657536336722
432224353535466545676346847464474684887654845856596875766667866896557668587685678659698765676687694874888555474578657554564755337655736566425
466227343334436443543565686885785867745856467756587795659787757775766765958755766858768858789669966865858668475464658557763633575774375763564
525564345744353535555567785567757545886887877886757559675685855967669987576888565685885885757665685586465887587456646573346554334466735664223
322454443667644657466557545645764746786748468465555766997968786685999777878859877666868955797657458644667458875757555575563765656665563744423
526235554376335666336344466877478786845478668888848866879599958776678658899688756675589678968764877478747774888868565357767455474747666443242
344622625445755754663736444486456848574777557765744877889959576589877597556985968796558567686855454588885546545445545334436365757556635256645
222455464466463646535754446765768747674867876647556488676657757889995657595979795666655775558784876677788647744774473755454643364575576552266
243524626535645656667754347734464886885548747788856647886577967889856975567759587597874745864785668558758486686868334754654635765654765566323
524245646536573434557365534456854854446448447657875866878686665858596665668987587747654584884774744786467586886864634544567676666775765533443
655653456234744577677375445656784768584857778566776875458778767477456655748474456544658768744667745888787774664877354643566436634667432533634
423632226433677377477334757546653486644876847678764857846575768577587557684556848558585758454885756646767685573467433575674365453654242543522
352453666322373443653643544474457776748744755567574844555676554486754867488555755474464544578564478745487747745764456743563443333334443563445
522625526632547736434543367557657778764574766885656848488545656844445776467858787558546768655675756886847474743656664646733557637464342446332
225465653225326764555556636363474544454888665465766776478568756767645886586757678685554576678485657468767834445777653766636654347522266665663
466533445366426566654363356546345565355665786784747784647446685664864467465475776866847565548768676654878563757755547656433364353566434523343
535344665534355473346676753444444344554454658888484564878487478665446566866774875887547875675664787578474567333355567336363334532556325343445
534665425565233537643736375646455637454668486444787555866455444588744548767878846777687857647455576647657666373464677364567657646224433234442
552363644633464646533755334537576446547554765466476545456766457567748858786667865467675888444454658437344643437565657746673474242455336334452
654365255623562655465745753553437574354463365556666878584748554788547855858865865888656787646585855735773675445673674566544645265465643462655
543422325625426423426555477774575374437775673745757555787586845784768844447586686867756466844445736557635765457364567436677252642322445355532
246544563266333334544353464754575666676676377536736647787776577886784644546478558464765644475664663474747647553636334334335233265455643425353
554365425345425453436567443677534644465457366474766557478746757567775446674756588666766564457556565734446544676353633346735622245664422643256
326642456644426236642444754576366776567463337676475367647846747677456767865645787884448367364745773455334654334573335347543622454464666652464
343465234234554632656442655545546645554556466534655634677534858564878888654845854764743476563665366443755773564343465536363435556263562632324
332354642234543464356334424463334656467434334363566674447373375363356766533645566353777575344774453377435344577353564236536562364222625566452
511253623333566426644236326675745564475664657573356446435475336366346437456335767355744564745655766357753353374676772362362446436425453452244
444556335353542342235665243444456563655677574633463543366576467763543346747376754576734466553657463535773777343653444655626443565553636445415
322514556323234322626646226545544354343745777475554754453644357357745757735534365644437756773776477636357765673363523364434455526534533333331
143551153364623263526524353352435365467546445636757453634474677633575455733443765544444576337677733566373663477345233643566524322226565454334
524523513326646252552334624363523666537764777573475556434547544565643343753754735473337474444747563445535675534553433623464465625454353133423
524345215236452635534644535645353663745354663437465355646747334673655636566744464557645556465643553353756734566642645443422243322236651343245
421251533446326563335532353656352523276577565657664636377567467637453775654666633467544776363776576357347366362625243455353562555654212325112
424113122324552346435655266243442633224765636377545477665646434644455357573434437537656637355574635654562464445523566246426643522255552445212