import Ġpath utils . Pos Ċ import Ġpath utils . four Ne igh s Ċ import Ġpath utils . short est Ċ import Ġjava . io . File Ċ Ċ data Ġclass ĠNode ( val Ġsize : ĠInt , Ġval Ġused : ĠInt , Ġvar Ġtarget : ĠBoolean ) Ċ Ċ fun Ġparse Pos ( line : ĠString ): ĠPos Ġ= Ġwith ( line . split (" Ġ" )[ 0 ]. split ("- ")) Ġ{ ĊĠĠĠ ĠPos ( this [ 1 ]. drop ( 1 ). toInt (), Ġthis [ 2 ]. drop ( 1 ). toInt ()) Ċ } Ċ Ċ fun Ġparse Node ( line : ĠString ): ĠNode Ġ= Ġwith ( line . split ("\\ s +". to Regex ())) Ġ{ ĊĠĠĠ ĠNode ( this [ 1 ]. drop Last ( 1 ). toInt (), Ġthis [ 2 ]. drop Last ( 1 ). toInt (), Ġfalse ) Ċ } Ċ Ċ fun Ġfits ( n 1 : ĠNode , Ġn 2 : ĠNode ): ĠBoolean Ġ= ĊĠĠĠ Ġn 1 Ġ!== Ġn 2 Ġ&& Ġn 1 . used Ġ> Ġ 0 Ġ&& Ġn 1 . used Ġ<= Ġn 2 . size Ġ- Ġn 2 . used Ċ Ċ fun Ġinter change able ( n 1 : ĠNode , Ġn 2 : ĠNode ): ĠBoolean Ġ= ĊĠĠĠ Ġn 1 . size Ġ> Ġn 2 . used Ġ&& Ġn 2 . size Ġ> Ġn 1 . used Ġ&& Ġ! n 1 . target Ġ&& Ġ! n 2 . target Ċ Ċ fun Ġne igh s ( pos : ĠPos , Ġnodes : ĠMap < Pos , ĠNode >): ĠList < Pos > Ġ= ĊĠĠĠ Ġfour Ne igh s ( pos ). filter Ġ{ Ġnodes [ it ] Ġ!= Ġnull Ġ&& Ġinter change able ( nodes [ it ] !! , Ġnodes [ pos ] !! ) Ġ} Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġnodes Ġ= ĠFile (" input "). read Lines (). drop ( 2 ). map Ġ{ Ġparse Pos ( it ) Ġto Ġparse Node ( it ) Ġ}. toMap () ĊĊĠĠĠ Ġval Ġfirst Ġ= Ġnodes ĊĠĠĠĠĠĠĠ Ġ. flatMap Ġ{ Ġ(_, Ġn 1 ) Ġ-> Ġnodes . map Ġ{ Ġ(_, Ġn 2 ) Ġ-> Ġn 1 Ġto Ġn 2 Ġ} Ġ} ĊĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġ( n 1 , Ġn 2 ) Ġ-> Ġfits ( n 1 , Ġn 2 ) Ġ} ĊĠĠĠĠĠĠĠ Ġ. count () ĊĠĠĠ Ġprintln (" First : Ġ$ first ") ĊĊĠĠĠ Ġval Ġmain Path Ġ= Ġnodes . keys . filter Ġ{ Ġit . y Ġ== Ġ 0 Ġ}. sorted By Ġ{ Ġ- it . x Ġ}. to Mutable List () ĊĠĠĠ Ġvar Ġtarget Ġ= Ġmain Path . first () ĊĠĠĠ Ġmain Path . remove First () ĊĠĠĠ Ġnodes [ target ] !!. target Ġ= Ġtrue ĊĊĠĠĠ Ġvar Ġempty Ġ= Ġnodes . filter Values Ġ{ Ġit . used Ġ== Ġ 0 Ġ}. keys . first () ĊĠĠĠ Ġvar Ġtotal Len Ġ= Ġ 0 ĊĊĠĠĠ Ġwhile Ġ(! main Path . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnext Target Ġ= Ġmain Path . first () ĊĠĠĠĠĠĠĠ Ġmain Path . remove First () ĊĠĠĠĠĠĠĠ Ġtotal Len Ġ+= Ġshortest ( empty , Ġnext Target , Ġnodes , Ġ:: ne igh s ) !!. len () Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġnodes [ target ] !!. target Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġnodes [ next Target ] !!. target Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġempty Ġ= Ġtarget ĊĠĠĠĠĠĠĠ Ġtarget Ġ= Ġnext Target ĊĠĠĠ Ġ} ĊĠĠĠ Ġprintln (" Second : Ġ$ total Len ") Ċ } Ċ