The lava starts flowing rapidly once the Lava Production Facility is operational. As you leave, the reindeer offers you a parachute, allowing you to quickly reach Gear Island.
As you descend, your bird’s-eye view of Gear Island reveals why you had trouble finding anyone on your way up: half of Gear Island is empty, but the half below you is a giant factory city!
You land near the gradually-filling pool of lava at the base of your new lavafall. Lavaducts will eventually carry the lava throughout the city, but to make use of it immediately, Elves are loading it into large crucibles on wheels.
The crucibles are top-heavy and pushed by hand. Unfortunately, the crucibles become very difficult to steer at high speeds, and so it can be hard to go in a straight line for very long.
To get Desert Island the machine parts it needs as soon as possible, you’ll need to find the best way to get the crucible from the lava pool to the machine parts factory. To do this, you need to minimize heat loss while choosing a route that doesn’t require the crucible to go in a straight line for too long.
Fortunately, the Elves here have a map (your puzzle input) that uses traffic patterns, ambient temperature, and hundreds of other parameters to calculate exactly how much heat loss can be expected for a crucible entering any particular city block.
For example:
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
Each city block is marked by a single digit that represents the amount of heat loss if the crucible enters that block. The starting point, the lava pool, is the top-left city block; the destination, the machine parts factory, is the bottom-right city block. (Because you already start in the top-left block, you don’t incur that block’s heat loss unless you leave that block and then return to it.)
Because it is difficult to keep the top-heavy crucible going in a straight line for very long, it can move at most three blocks in a single direction before it must turn 90 degrees left or right. The crucible also can’t reverse direction; after entering each city block, it may only turn left, continue straight, or turn right.
One way to minimize heat loss is this path:
2>>34^>>>1323
32v>>>35v5623
32552456v>>54
3446585845v52
4546657867v>6
14385987984v4
44578769877v6
36378779796v>
465496798688v
456467998645v
12246868655<v
25465488877v5
43226746555v>
This path never moves more than three consecutive blocks in the same direction and incurs a heat loss of only 102.
Directing the crucible from the lava pool to the machine parts factory, but not moving more than three consecutive blocks in the same direction, what is the least heat loss it can incur?
type Point struct {
x, y int
}
type State struct {
pos Point
dir Point
straight int
heat int
}
type PriorityQueue []State
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].heat < pq[j].heat }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(State)) }
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func main() {
content, err := os.ReadFile("input.txt")
if err != nil {
fmt.Println(err.Error())
os.Exit(1)
}
lines := strings.Split(strings.TrimSpace(string(content)), "\n")
grid := make([][]int, len(lines))
for i, line := range lines {
grid[i] = make([]int, len(line))
for j, c := range line {
grid[i][j] = int(c - '0')
}
}
dirs := []Point{
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
}
rows, cols := len(grid), len(grid[0])
visited := make(map[string]bool)
pq := &PriorityQueue{}
heap.Init(pq)
heap.Push(pq, State{Point{0, 0}, Point{0, 1}, 0, 0})
heap.Push(pq, State{Point{0, 0}, Point{1, 0}, 0, 0})
for pq.Len() > 0 {
current := heap.Pop(pq).(State)
if current.pos.x == rows-1 && current.pos.y == cols-1 {
fmt.Println(current.heat)
break
}
key := fmt.Sprintf("%d,%d,%d,%d,%d",
current.pos.x, current.pos.y, current.dir.x, current.dir.y, current.straight)
if visited[key] {
continue
}
visited[key] = true
for _, newDir := range dirs {
if newDir.x == -current.dir.x && newDir.y == -current.dir.y {
continue
}
newStraight := 1
if newDir == current.dir {
newStraight = current.straight + 1
if newStraight > 3 {
continue
}
}
newPos := Point{
current.pos.x + newDir.x,
current.pos.y + newDir.y,
}
if newPos.x < 0 || newPos.x >= rows || newPos.y < 0 || newPos.y >= cols {
continue
}
heap.Push(pq, State{
pos: newPos,
dir: newDir,
straight: newStraight,
heat: current.heat + grid[newPos.x][newPos.y],
})
}
}
}
The crucibles of lava simply aren’t large enough to provide an adequate supply of lava to the machine parts factory. Instead, the Elves are going to upgrade to ultra crucibles.
Ultra crucibles are even more difficult to steer than normal crucibles. Not only do they have trouble going in a straight line, but they also have trouble turning!
Once an ultra crucible starts moving in a direction, it needs to move a minimum of four blocks in that direction before it can turn (or even before it can stop at the end). However, it will eventually start to get wobbly: an ultra crucible can move a maximum of ten consecutive blocks without turning.
In the above example, an ultra crucible could follow this path to minimize heat loss:
2>>>>>>>>1323
32154535v5623
32552456v4254
34465858v5452
45466578v>>>>
143859879845v
445787698776v
363787797965v
465496798688v
456467998645v
122468686556v
254654888773v
432267465553v
In the above example, an ultra crucible would incur the minimum possible heat loss of 94.
Here’s another example:
111111111111
999999999991
999999999991
999999999991
999999999991
Sadly, an ultra crucible would need to take an unfortunate path like this one:
1>>>>>>>1111
9999999v9991
9999999v9991
9999999v9991
9999999v>>>>
This route causes the ultra crucible to incur the minimum possible heat loss of 71.
Directing the ultra crucible from the lava pool to the machine parts factory, what is the least heat loss it can incur?
type Point struct {
x, y int
}
type State struct {
pos Point
dir Point
straight int
heat int
}
type PriorityQueue []State
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].heat < pq[j].heat }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(State)) }
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func main() {
content, err := os.ReadFile("input.txt")
if err != nil {
fmt.Println(err.Error())
os.Exit(1)
}
lines := strings.Split(strings.TrimSpace(string(content)), "\n")
grid := make([][]int, len(lines))
for i, line := range lines {
grid[i] = make([]int, len(line))
for j, c := range line {
grid[i][j] = int(c - '0')
}
}
dirs := []Point{
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
}
rows, cols := len(grid), len(grid[0])
visited := make(map[string]bool)
pq := &PriorityQueue{}
heap.Init(pq)
heap.Push(pq, State{Point{0, 0}, Point{0, 1}, 0, 0})
heap.Push(pq, State{Point{0, 0}, Point{1, 0}, 0, 0})
for pq.Len() > 0 {
current := heap.Pop(pq).(State)
if current.pos.x == rows-1 && current.pos.y == cols-1 && current.straight >= 4 {
fmt.Println(current.heat)
break
}
key := fmt.Sprintf("%d,%d,%d,%d,%d",
current.pos.x, current.pos.y, current.dir.x, current.dir.y, current.straight)
if visited[key] {
continue
}
visited[key] = true
for _, newDir := range dirs {
if newDir.x == -current.dir.x && newDir.y == -current.dir.y {
continue
}
if current.straight < 4 && newDir != current.dir &&
(current.dir.x != 0 || current.dir.y != 0) {
continue
}
if newDir == current.dir && current.straight >= 10 {
continue
}
newStraight := 1
if newDir == current.dir {
newStraight = current.straight + 1
}
newPos := Point{
current.pos.x + newDir.x,
current.pos.y + newDir.y,
}
if newPos.x < 0 || newPos.x >= rows || newPos.y < 0 || newPos.y >= cols {
continue
}
isEnd := newPos.x == rows-1 && newPos.y == cols-1
if isEnd && newStraight < 4 {
continue
}
heap.Push(pq, State{
pos: newPos,
dir: newDir,
straight: newStraight,
heat: current.heat + grid[newPos.x][newPos.y],
})
}
}
}
Links
Click to show the input
316646223234254241766272522447716451422437887735473441275458343631253685757784667161381656818354324872173427676551465144527436464352322335312 461225152511525234443631713464165117155535145824451414271252656342566823552615211451756848336121533775462254654464332616611565134614542233565 264316613265132517712173465115411554335328564342215668765886254383758664164513845558466565787675827341371467443513774221232541527456345362464 244624443421554654462361663326575165328258467566222413176712474544618873535724328824823813178211485627174434731455736743135421346512433456334 552636621336263761233375544215134433251145686655463856841147276145268656341341311346867863815761884674271288531311174335417164117671564243435 264531324527725673427134515534223228641378313421415883412455776731647378668437684774187826531384233435644615335152723216745253167157661156331 612462324171361617646121271417445646455773851616277858354772212766866343848473716248651532883656158243283461851213736663746244535473464446661 522415161554246376361577656566514574835147375523826672412771215783134635798152337732776765343585578723365454125715566657631255252625666615112 646561227441743655433633645522644158723812688561826518243327741929281373897536939287222252753687673443335254628741234525334754665346667632215 544446577653411176334624556482865146635711382844831273727654592471852229896584491725318526438818638553415474286353137644664772515734627241616 556513636746646557116117273543625414282737756638163484471224384134247854386851363129717523515476127866114253223421257711624122775353663644551 264523365775435311146158866675627728328834287428341355681247373566537149712947876438277761648645214678368676512775373135317631731467142747461 642537554354535547346136186844356628185333317638914248234315134187334152219926231859652885524762716244173575866471814186417512557672153523235 323733674435612767467561387511383647614528279284319971975589695228279569599789984643725973847956851133323477174577734682857642473746641711553 216416467436562436547288312355261123753711772949452575928341748867394651647339733946686619753123721954367441125786228574574663237271514636653 166613245153675331587173585655376753156223641296426757361445287114418469649946149547311959692788953191588334254467187817554731253542721242332 547523514312366135513641323634262873865957492672786191863176499369112115786438224515825359769927747762347462164282631346423683337577322251335 166523326326354244541816258648568514371873681695918311777532288693464837792476735719327889839128236582765871853242423747827142611534677453543 731777134255237425784115136288678756264332987364721128471587795581413219454217344433111643979161448889753391147416753723221771626662664326516 545364745414254311778542823568482683754977448898758188356762159555911742266835983225262147948564322875218297861217466655164342343122436514225 127135645457317831133486341851327498295576216451189188573274743387954427323746234812319497327164985462554882343184112747738163137246521643153 211153612135472514674741555132369488265831257468191956858527364452392644294543293265362271841523489742625255953588881835432857714653426213134 354544277155137577214555483186962361741463593253492246483584864338356867253634634258835885973689454565143178471278872131887477461586175767521 473667741727572148337466618125686361281474531964163215957472927724789742689572428842448487622825132212365752632759863334358232183743441742556 642774465578517447717266128471475953169516318878422877869935879725966436349468587332435948383438188872716877888168321666145277176646543334242 657623443132127347262222581836498295686314223124842638323643228546467792868583954448285565444456161386338571312842827322653737436832561611516 173521137325741652885781667454937538193886838243756466236485234754993997492253327874278968377787544559958256157811168233681151247333552221361 324164361771678485438422773825881396364235291942632787585548697789232437543892854359227696942974326521755896246238675543587852138355475415773 263244128121481357761742123314921625516488653832795334849558834685854928966583348562723958343244379258885777367734461446578256354734584233127 224751457643558813775355783387613266129416687464234728922548892642266978448489822963296756539532758863681836196797631725721531556465335371744 573632625387815863778295536691412465492186293244566845722394829742272852939475498686545446239559923364395498476745898732127773255273756711675 125551765638781115387986553476978447743693686482955975553523287268832824723434276975496797237495497828375379813551247331415236627588227351216 712147252846438855726197369256887531275773962959243436746382734336534765886599775347387395392537962865924647863987422217871755141142875832125 462527672636852847112846149284137924877263969624788244938336279734544994666347869279653553652974447529533829656812882891385183868328787268334 541566836283368443622443169196926737587688777275398385238335555648453445885497744475545422939979275582927627796941546554676988316223525512773 433661616633748867542111454978328889456294367725654568597883697634354959848866945377942552549973348989532744393169819115515917446327833173525 373663343715877151561563878969491438439548284256869497374437595786387887767696436667399478437943727694684865672997988639926468886477235841344 261837376854538112239814241429998442795584389662354892399555953475665557769858445999776344955535283268458937334459367213499729462332658664326 173327446714457477674828422722315224445397646689872735746867884856689379946385398834698657347336745246885324566835798818837485753376284618616 267548657686342818283789488594478546327879263899289876375653997375589659638483987855699436857899348989274675664874894963818794425146424366847 121524576744887533233715141989673446723979565973666343498734663487779365758986345937845675479549555553532379944292942128945758338182111641686 225245423631651272863717349136262455442944524558935655638784363784935486783849385346585953597365737286566472774881946932827923553513131578873 756354258865873997512986498159828289899368433278788646996547846785436636846444638475765798889343983353758449464563927999681381291367217713534 825454353753167727854943295237838564294363255773483539737474749374866768833546698544737498465433862474276266348479646835835224698625715367841 818855485116468759958737311377337869245564849575545858467433467888457885888844349368998367895864398689737996236578859434355191234921413847684 181232471254771947916384175827644989396474877988956453488678899577633684884577396949346649953358975564356396234539927612249868822846724272863 816611727125334628223532937844687323783554587939735936885984377569556874968696348744633696673547748393733739766556783257773377474884663743742 247752842117428874837675362393668888674229494499356639389396398885557854558468447483796835465344953487566973544226532886417333584466816325276 844886164774788663862632853646458549992354689338638778943974749855896474585477454443997744633737964488322464549728596552464833235868164134117 167882665678168191882622284258972524747369388456459744859854458999596959456944554568779868556446994659976544392224723652128579957776525352234 827875757553134631339199257673258427832747495846493384633464886884986799486785999484897969363343837338533223477444772853264881542549215386362 481562732186252323621578694833656248349635878884556879994474694448897679494684768455954987657978943944652438653256977729738538621259426525331 125113761666244677595437795272873942367576638399763584477675569777698444567876855677977767755587699587444469227955845462624939369699136234543 365374664616313368337696987867825344824466547998874894994545756875554544647759676869866787799695758864459569397256684798252125982422556233267 252255787157798433557144775972955278759334569565346964866765865878679454547988599548758855983379486576794822279734334984451225875357555114452 511255732959735161822145298278465429758776647686448955878449746667567869767547654966699744579799849949435985378788673552237279229184294112531 263675713738794587574516948365657844688697774337934856577447866586884465898479975669546795556968945877593888543224857692556138665721811556278 744188416233859144159267548873856479686853497335367455449484745547776694445776946984689898475358349363946567525576623788811465569752737513221 544145425238268231945787493495297865649386977976686555885648457455544459565688555986479897797779886635565844384546932255972398875393577726425 178283442285833883216897646434754934548474493594999574657945876574758875797997884669797447847788577733897499657634882378789365448711812473263 444251722133684812898638479228799554968487399676799656754785787997998868676598448694965748844899467993459353938488846295588363538882566411428 481788521892572859891647294248683246963357435436644495576949756588957989677788689778897988884649436586368565599469949739464697761145588288544 434643353793585533618348626499792447966477548363548694677795558856769855879598875695885859689453975848483933778876266974495354657954847825882 833515751761379661273678336339357279346787873685986866698456998868559575968588876769857798497954378336395568866735767859344798914842191185613 588486772848315924158579747986364583593584986986957769689767855969887777567796576776587666464649657466787549578497254579728979652132143371734 863561461292225879874557322676659673886589548468765754579969669768757695779979689956899868487586648389793749548587439338527632631578433225313 654787251151873615928537234274669466745398354354984575556747657797787889667799758556896478688598843447874895574788354225355685187569513722117 884716687789261851894988957655569975836893347688558756958888977896885785888558975595959644998578883665466636782567883234499137231748796713884 248788767415453381766448778644239567754385378996845845976976577589768775989655659596559766948899738446594936972694957837864549367289584672465 754714587666735184447576268285433466693665944678788567459988959556997687958667586969959988644695439599949395885644284623966284617696383318257 867228461533925441422557299286424645537956657887556979659467595566855669879987965996998479477757656863364895676285897248975828996437483577821 456865585395473485649288758247323549858543693467756589786477755579679569886997899997764566688565796879976598359767296756526763115932229883381 362214463661525876982796297348627744435748745399999988458955858568555685986757585886499959888958738688698599497844253358629392673182181786613 547431318339685516263837546367367985789575867955588659475457788665768788975756778555598847588864686878478337788865697394577376192271122218225 516677187682333782795343676727949375945764763656974947555965688689758695767998575577855875697997688464857893549244749478962116253829526416733 575331237426769928476229642947467534333369779498956758697786759675966997569979669788748566898966946543646859357523224244837736993192373612215 883642111646486752113842865678793843633683594446445574665977795775696755996599779957574796554848468563553895648838869942689353529879864635432 321816569948234769913623962627298236754363558899954587954599597987778768988767965796587979746668739965363778973852943974354746813732543684881 664676358357263525396256293497389266457967635336698674865684958689596856556699976788767888777697667644356455735553265998672519722145839412382 734154413442818938218532332486585969557586339598767759559576799885555887865867565968966869568945885444566658967872758956746339372171831552536 525844633288654233189725934669663435445754744396597974689854498588666575668696767668485979589778785539975876555996874352533671526849855668683 157184741329187365244744789987882673786439965598857946668847445799796655665759755598889576777968593363898737334684943326241182264214413565684 423155447752119996472234676694482424865947754353998897794999898959755897688556857574777575974443755546888766325922442849752451145488121638636 465842331252255184266383642496386695949675446888868584598565778576957695558556794848474664687453386995395598423329875799572138112561225668515 718124155449431572288995469846693377959438778669698858564797458497667944857464765888989488989849994854974639288824284224798355858947541754747 744181827464311239958487423532294377335596743899647664548764665988576964587596847689758787548494839936549792564534283433991229351977473627438 786842555499235316447793843897923692877968646533537495978776946845699844585999645874558646473894993383856482436643783565348776686871131372575 422463438285152758521526444882392596297856346878499985588665867575694475857547469874947995464365973447965582896528798692941891437424663862552 135242576224993616615559252965837959233566966853343857598888546954997567586894698578465988853663775986557532352633245446256927734447416557544 333248182466928295412372443684776693267335636657664858857958878457446657558445667748547656963333846844496736589528574956328423266866721488217 628825144145866533234938692556353538839769674767536434988889956969496954884774994689699866989598688789855422358778382426676144443556614224523 655355445787228821123333823285488297397487939799998478474899485894997859659759459647856577347663576845883763487525297992464385221585832884233 453882677143166361745876899553587395377856437984478975854588895985479789879967754756794434354358948994597258983886774973154865771867273333655 676541547741912631661914142692786299642288586448437738866585599647997564955494789545664445398353349975962344395534577253145998785891663685748 163832237338225133763172959255455382535824558987556354497459968565445474965559766478848468343487977737228697469872683327676983768165818273173 683366468373762115954262825888897745696559876836899463946347543798876859487657755873748989795765887955673467629947733454352163968336586238262 667848858753833484261131239668754958779852476945533343763448579697765559564973634843436633587558387844685558595449633745952447272512718864168 616741875212121115468159973556272993234577548869494947868669454485893644385569496895953777638583955549529964549276376724951818682366111624213 727142562575629554557667699996356333324755265749364788476463336457948496933753497378666367974338793485388626662337478985273189517513523817241 611336345235854485582778637536775699648244834633944735458955644768934756663937999437693849438598945549488582945272783833722398324211744743845 677646574861272846221786596947887847533863342367596993369693975965379867734686733785444696375439899727876725344786537577887424879388747777272 347847186422641364745675246749962424678667884343637699489995668885485869969578788398693867359939339642685296996322689759611887798133562648766 623815317842838967555757266728246594777588483373967764365963494353889677683875368798853435379549688648269389766624237925844328272461113857352 575287234312736285922133619831767749325693967322423464643547476489989743533948546958933598966384466946945492638228711339326242716237253378211 766362383142533628958485524473222695463785488529963693837567744656985449577554966566999688668554782298496669294645452539925888176444113545228 671272557123387637855524761618534272682887973794746567844833643748494657834637785457955443864969854876877356863787425589247522184584831383551 322247757673331343539718916192516367627894669786433228348657988859987475837768598399957786743576658222248555521729611317298364654451112874462 751513173456881857322413312482228169563332882259556667459646949949646669933869934356397297523726446223344337745891427397859247551156824675733 333451276622428866518852962162377362598226765833527576829254887957785638795786789378979739323554633372343246693683733554159974313441275454211 222737362547752458718422927996721829786382748692374995669576426366934489434545573797464888987773953492366872281432236848677418333716287663737 754214626251846723864945447598375373756539345225936973662486435947854349577996522572378984296829679342495611118315561359735636268348356655472 452142133683781524142584136137519148673979233895498783883546543235275487767245453733488226452874352473989927653947358415445675555243388483337 642776682861217864887526557348474827733354897285778273786974438856375863586526836388949638767438328956656341395765232274533122715726426146353 624454114556177481832585799166979719352965687867933622988433249449356565892797386328728749592393376972928215665988743834371613356711157324477 733514343215785537714865329327289574459718174654889585793983849928939262984694935937568556342727285672269426294273111587178253313614727462625 262561125757681288464417288721127557435311754445974662268447836232395684249844788639892627977437692245257434524553671761628418785858814437143 143322452535142163877638521126514937759135919929499975296582349654977843765783425828552929837334796185934688229969519766312266762132246771632 147165731755148351817838226627987488419341591982978843573267875873969687686756227884897697449696738891225269195288511666647436454567472373621 146635612757287347568612146733782293188293923996933659286794949983523953369938626495662435224289661384953274781936658778851122682513533576335 446572467262727876145261255579453516533325357477854174367238472454829997277352528547834459999948755779674725633395848888316154537288166636262 533222152224548413821144126771519987477631299237557119467673223898548475556423232597482736564689973551598516573675513877122456336344673462353 563365342442321261865187682768894954112616478988273662788578426569977626374254236468785575449935537343772475493912714714625144126425362521164 175374643722516166747174682755821594124654138788316283145276913446658964957635377756461696616637155597575526944737423145277173681614171625315 277166152166523632288625268734571612154894157962679363788756465812126244118736691424849886155895594351152359438745322383443568231246541711327 351423121224415364158535431883481117915195786922752966715583135426337159962793641782889797222224161324121971114421127573872178327464633475174 144312421466516248486877675138245666384661583521927651955363541493399726821976812185267452173373593224265743571246787835781173573327744362747 263655412135555435211885223774847686362578936832224825875648316642532823715343725317646372971111287189984545272488285133141482713453671156142 534241374251266444488245737352541561755854915642216937954672226445483115298427597361317189538799149461271438148244864418114231213616647777117 267772554652746524272848213738865646724485426152831393475776998866388699658982954953475791889148676978617671877471476255877751754124735154212 312565674577673645653163685642542475885855883435746415448972183914262641911947621293838273774863524288412738825826477811142775572153137644371 161256132353313266663253314838717875736116655685989999856742443256833587177246685617228334399444633382673744565185165265462351452262673437215 111453672743655176736611562433753744424345863865793182872657725971982133359532788135213914316713411651582746444277782348137162131634322164636 121323426223515575631175572468565175443116584824548727644265469739389299733814691568222177558555875678858383458834234676623366526435765143165 122563522125142426414133765112881614715612222822328375495526841123759981881287611714765377643577776787156847836524155342167126367674151216422 266121613314656423374543172321623148874862455277641521264653699771443157453293236547874813416782461643167271682686137527567735672452126362511 243554212367336141457115354563843481124881345144264236582528482616118156885826643556333656643138244725166713783242562446223166372556431633654 465462313675523115237235251261651652516721733363246235378264563876328133517342336345544781435747862462737735342245667351661453611436561652666 421626651414121133314211733566274631878615655662216835252752815376572733143467218324344567388415858437848617857375613144456436562411111665254 425115654363736342411364541277644763165463456712358276224353557135221448336762158225233514488784354647477537355222717164562664214345333356624 615232131126262567147475255553121431434128363882846713888532886153252867864754733364265261528383815153341782714236567727141354424442623441664 342135233661433243612575426726374652414862847217714224848378881365578183673443452142761371821575774855821166126333577276221264656244454215531