package Ġcom . s 1 3 g . a oc . a oc 2 0 2 1 Ċ Ċ import Ġcom . s 1 3 g . a oc . Result Ċ import Ġcom . s 1 3 g . a oc . Solver Ċ Ċ /** Ċ Ġ* Ġ--- ĠDay Ġ 1 5 : ĠCh iton Ġ--- Ċ Ġ* Ġhttps :// ad vent of code . com / 2 0 2 1 / day / 1 5 Ċ Ġ*/ Ċ class ĠDay 1 5 Ġ: ĠSolver Ġ{ ĊĠ Ġoverride Ġfun Ġsolve ( lines : ĠList < String >): ĠResult Ġ{ ĊĠĠĠ Ġval Ġwidth Ġ= Ġlines [ 0 ]. length ĊĠĠĠ Ġval Ġheight Ġ= Ġlines . size ĊĠĠĠ Ġval Ġdata Ġ= ĠInt Array ( lines . size Ġ* Ġlines [ 0 ]. length ) ĊĊĠĠĠ Ġfor Ġ( y Ġin Ġlines . indices ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( x Ġin Ġlines [ y ]. indices ) Ġ{ ĊĠĠĠĠĠĠĠ Ġdata [ width Ġ* Ġy Ġ+ Ġx ] Ġ= Ġlines [ y ][ x ]. toString (). toInt () ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġpart A Ġ= ĠBoard ( data , Ġwidth , Ġheight ). calc () ĊĠĠĠ Ġval Ġpart B Ġ= ĠBoard ( expand For Part B ( data , Ġwidth , Ġheight ), Ġwidth Ġ* Ġ 5 , Ġheight Ġ* Ġ 5 ). calc () ĊĠĠĠ Ġreturn ĠResult ("$ part A ", Ġ"$ part B ") ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġexpand For Part B ( data : ĠInt Array , Ġwidth : ĠInt , Ġheight : ĠInt ): ĠInt Array Ġ{ ĊĠĠĠ Ġval ĠnewData Ġ= ĠInt Array ( width Ġ* Ġheight Ġ* Ġ 5 Ġ* Ġ 5 ) ĊĠĠĠ Ġvar Ġidx Ġ= Ġ 0 ĊĊĠĠĠ Ġfor Ġ( y Ġin Ġ 0 Ġuntil Ġheight ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. 4 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 Ġuntil Ġwidth ) ĠnewData [ idx ++] Ġ= Ġround It ( data [ y Ġ* Ġwidth Ġ+ Ġx ] Ġ+ Ġi ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġnew Width Ġ= Ġwidth Ġ* Ġ 5 ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. 4 ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( y Ġin Ġ 0 Ġuntil Ġheight ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 Ġuntil Ġnew Width ) ĠnewData [ idx ++] Ġ= Ġround It ( new Data [ y Ġ* Ġnew Width Ġ+ Ġx ] Ġ+ Ġi ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn ĠnewData ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġround It ( num : ĠInt ) Ġ= Ġif Ġ( num Ġ>= Ġ 1 0 ) Ġnum Ġ- Ġ 9 Ġelse Ġnum ĊĊĠ Ġprivate Ġclass ĠBoard ( val Ġdata : ĠInt Array , Ġval Ġwidth : ĠInt , Ġval Ġheight : ĠInt ) Ġ{ ĊĠĠĠ Ġ// ĠIndex Ġ( width / height ) Ġand Ġche ape st Ġcost . ĊĠĠĠ Ġval Ġvisited Ġ= Ġmutable Map Of < Int , ĠInt >() ĊĠĠĠ Ġvar Ġactive Routes Ġ= Ġmutable Set Of < Route >() ĊĠĠĠ Ġval Ġgoal Ġ= Ġidx At ( width Ġ- Ġ 1 , Ġheight Ġ- Ġ 1 ) ĊĊĠĠĠ Ġfun Ġcalc (): ĠInt Ġ{ ĊĠĠĠĠĠ Ġactive Routes . add ( Route ( 0 , Ġ 0 )) ĊĠĠĠĠĠ Ġvisited [ 0 ] Ġ= Ġ 0 ĊĊĠĠĠĠĠ Ġwhile Ġ( active Routes . count Ġ{ Ġit . last Idx Ġ!= Ġgoal Ġ} Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( route Ġin Ġactive Routes . toList ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( route . last Idx Ġ== Ġgoal ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠ Ġactive Routes . remove ( route ) ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( cost At ( route . last Idx ) Ġ< Ġroute . cost ) Ġcontinue ĊĊĠĠĠĠĠĠĠĠĠ Ġval Ġend Ġ= Ġroute . last Idx ĊĠĠĠĠĠĠĠĠĠ Ġval Ġoptions Ġ= Ġfind Next Options ( end ) ĊĠĠĠĠĠĠĠĠĠ Ġfor Ġ( opt Ġin Ġoptions ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtotal Cost Ġ= Ġdata [ opt ] Ġ+ Ġroute . cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cost At ( opt ) Ġ> Ġtotal Cost ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġactive Routes . add ( Route ( opt , Ġtotal Cost )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvisited [ opt ] Ġ= Ġtotal Cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġreturn Ġactive Routes . sorted By Ġ{ Ġit . cost Ġ}. first (). cost ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcost At ( pos : ĠInt ) Ġ= Ġif Ġ( visited . containsKey ( pos )) Ġvisited [ pos ] !! Ġelse ĠInt . MAX _ VALUE ĊĊĠĠĠ Ġfun Ġidx At ( x : ĠInt , Ġy : ĠInt ) Ġ= Ġy Ġ* Ġwidth Ġ+ Ġx ĊĊĠĠĠ Ġfun Ġfind Next Options ( pos : ĠInt ): ĠSet < Int > Ġ{ ĊĠĠĠĠĠ Ġval Ġx Ġ= Ġpos Ġ% Ġwidth ĊĠĠĠĠĠ Ġval Ġy Ġ= Ġpos Ġ/ Ġwidth ĊĊĠĠĠĠĠ Ġval Ġresult Ġ= Ġmutable Set Of < Int >() ĊĠĠĠĠĠ Ġif Ġ( x Ġ> Ġ 0 ) Ġresult . add ( idx At ( x Ġ- Ġ 1 , Ġy )) ĊĠĠĠĠĠ Ġif Ġ( x Ġ< Ġwidth Ġ- Ġ 1 ) Ġresult . add ( idx At ( x Ġ+ Ġ 1 , Ġy )) ĊĠĠĠĠĠ Ġif Ġ( y Ġ> Ġ 0 ) Ġresult . add ( idx At ( x , Ġy Ġ- Ġ 1 )) ĊĠĠĠĠĠ Ġif Ġ( y Ġ< Ġheight Ġ- Ġ 1 ) Ġresult . add ( idx At ( x , Ġy Ġ+ Ġ 1 )) ĊĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠ Ġ} ĊĊĠ Ġprivate Ġdata Ġclass ĠRoute ( val Ġlast Idx : ĠInt , Ġval Ġcost : ĠInt ); Ċ }