import Ġjava . io . File Ċ Ċ data Ġclass ĠState ( val Ġflo ors : ĠArray < Mutable Set < String >>, Ġval Ġelev ator : ĠInt ) Ġ{ ĊĠĠĠ Ġvar Ġmoves : ĠInt Ġ= Ġ 0 ĊĊĠĠĠ Ġconstructor Ġ() Ġ: Ġthis ( Array ( 4 ) Ġ{ Ġmutable Set Of () Ġ}, Ġ 0 ) ĊĊĠĠĠ Ġfun Ġdeep Copy ( ĊĠĠĠĠĠĠĠ Ġflo ors : ĠArray < Mutable Set < String >> Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . flo ors . map Ġ{ Ġobjs Ġ-> Ġobjs . to Mutable Set () Ġ}. to Typed Array (), ĊĠĠĠĠĠĠĠ Ġelev ator : ĠInt Ġ= Ġthis . elev ator , ĊĠĠĠ Ġ) Ġ= ĠState ( flo ors , Ġelev ator ) ĊĊĠĠĠ Ġoverride Ġfun Ġequals ( other : ĠAny ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( this Ġ=== Ġother ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġif Ġ( other ?. java Class Ġ!= Ġjava Class ) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġother Ġas ĠState ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( f Ġin Ġ 0 .. flo ors . size Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( pairs At Floor ( f ) Ġ!= Ġother . pairs At Floor ( f ) Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġch ips At Floor ( f ) Ġ!= Ġother . ch ips At Floor ( f ) Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġg ens At Floor ( f ) Ġ!= Ġother . gens At Floor ( f ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġelev ator Ġ== Ġother . elev ator ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ= ĊĠĠĠĠĠĠĠ Ġelev ator Ġ* Ġ 3 1 Ġ+ Ġflo ors . with Index (). fold ( 1 ) Ġ{ Ġh , Ġ( i , Ġ_) Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ((( h Ġ* Ġ 3 1 Ġ+ Ġpairs At Floor ( i )) Ġ* Ġ 3 1 ) Ġ+ Ġch ips At Floor ( i )) Ġ* Ġ 3 1 Ġ+ Ġg ens At Floor ( i ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġchip ( obj : ĠString ): ĠBoolean Ġ= Ġobj [ 1 ] Ġ== Ġ' m ' ĊĠĠĠ Ġfun Ġgen ( obj : ĠString ): ĠBoolean Ġ= Ġobj [ 1 ] Ġ== Ġ' g ' ĊĊĠĠĠ Ġfun Ġpairs At Floor ( f : ĠInt ): ĠInt Ġ= ĊĠĠĠĠĠĠĠ Ġflo ors [ f ]. filter Ġ{ Ġc Ġ-> Ġchip ( c ) Ġ&& Ġflo ors [ f ]. any Ġ{ Ġg Ġ-> Ġgen ( g ) Ġ&& Ġc [ 0 ] Ġ== Ġg [ 0 ] Ġ} Ġ}. count () ĊĊĠĠĠ Ġfun Ġch ips At Floor ( f : ĠInt ): ĠInt Ġ= ĊĠĠĠĠĠĠĠ Ġflo ors [ f ]. filter Ġ{ Ġc Ġ-> Ġchip ( c ) Ġ&& Ġflo ors [ f ]. none Ġ{ Ġg Ġ-> Ġgen ( g ) Ġ&& Ġc [ 0 ] Ġ== Ġg [ 0 ] Ġ} Ġ}. count () ĊĊĠĠĠ Ġfun Ġg ens At Floor ( f : ĠInt ): ĠInt Ġ= ĊĠĠĠĠĠĠĠ Ġflo ors [ f ]. filter Ġ{ Ġg Ġ-> Ġgen ( g ) Ġ&& Ġflo ors [ f ]. none Ġ{ Ġc Ġ-> Ġchip ( c ) Ġ&& Ġc [ 0 ] Ġ== Ġg [ 0 ] Ġ} Ġ}. count () ĊĊĠĠĠ Ġfun Ġsafe () Ġ= ĊĠĠĠĠĠĠĠ Ġflo ors . none Ġ{ Ġf Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġf . any Ġ{ Ġc Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġchip ( c ) Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf . any Ġ{ Ġg Ġ-> Ġgen ( g ) Ġ&& Ġg [ 0 ] Ġ!= Ġc [ 0 ] Ġ} Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf . none Ġ{ Ġg Ġ-> Ġgen ( g ) Ġ&& Ġg [ 0 ] Ġ== Ġc [ 0 ] Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġup ( objs : ĠList < String >): ĠState ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( elev ator Ġ< Ġ 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewState Ġ= Ġdeep Copy ( elev ator Ġ= Ġthis . elev ator Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠnewState . flo ors [ elev ator ]. removeAll ( objs ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠnewState . flo ors [ elev ator Ġ+ Ġ 1 ]. addAll ( objs ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠnewState . moves Ġ= Ġmoves Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠnewState ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġdown ( objs : ĠList < String >): ĠState ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( elev ator Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewState Ġ= Ġdeep Copy ( elev ator Ġ= Ġthis . elev ator Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠnewState . flo ors [ elev ator ]. removeAll ( objs ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠnewState . flo ors [ elev ator Ġ- Ġ 1 ]. addAll ( objs ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠnewState . moves Ġ= Ġmoves Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠnewState ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġnext States (): ĠList < State > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġmutable ListOf < State >() ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( obj Ġin Ġflo ors [ elev ator ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġup ( listOf ( obj )) ?. let Ġ{ Ġresult . add ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdown ( listOf ( obj )) ?. let Ġ{ Ġresult . add ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġobj List Ġin Ġflo ors [ elev ator ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. flatMap Ġ{ Ġo 1 Ġ-> Ġflo ors [ elev ator ]. map Ġ{ Ġo 2 Ġ-> Ġ( o 1 Ġto Ġo 2 ) Ġ} Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġ( o 1 , Ġo 2 ) Ġ-> Ġo 1 Ġ!= Ġo 2 Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġ( o 1 , Ġo 2 ) Ġ-> ĠlistOf ( o 1 , Ġo 2 ) Ġ} ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġup ( obj List )?. let Ġ{ Ġresult . add ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdown ( obj List )?. let Ġ{ Ġresult . add ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġis Final (): ĠBoolean Ġ= ĊĠĠĠĠĠĠĠ Ġflo ors . take ( 3 ). all Ġ{ Ġit . none () Ġ} Ċ } Ċ Ċ fun Ġcompute Steps ( init State : ĠState ): ĠInt Ġ{ ĊĠĠĠ Ġval Ġtodo Ġ= Ġmutable ListOf ( init State . deep Copy ()) ĊĠĠĠ Ġval Ġseen Ġ= Ġmutable Set Of < State >() ĊĊĠĠĠ Ġwhile Ġ(! todo . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcurrent Ġ= Ġtodo . first () ĊĠĠĠĠĠĠĠ Ġtodo . remove First () ĊĊĠĠĠĠĠĠĠ Ġif Ġ( current . is Final ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcurrent . moves ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( next Ġin Ġcurrent . next States ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next . safe () Ġ&& Ġseen . none Ġ{ Ġit Ġ== Ġnext Ġ}) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtodo . add ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġseen . add ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġ 0 Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġlines Ġ= ĠFile (" input "). read Lines () ĊĊĠĠĠ Ġval Ġinit State Ġ= ĠState () ĊĠĠĠ Ġfor Ġ( f Ġin Ġ 0 .. lines . size Ġ- Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġline Ġ= Ġlines [ f ]. split (" Ġ"). drop ( 4 ). join ToString (" Ġ") ĊĠĠĠĠĠĠĠ Ġline ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. split (", Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġwords Ġ= Ġit . split (" Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠString ( listOf ( words [ words . size Ġ- Ġ 2 ][ 0 ], Ġwords [ words . size Ġ- Ġ 1 ][ 0 ]). toCharArray ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. forEach Ġ{ Ġinit State . flo ors [ f ]. add ( it ) Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprintln (" First : Ġ${ compute Steps ( init State )} ") ĊĊĠĠĠ Ġinit State . flo ors [ 0 ]. addAll ( listOf (" eg ", Ġ" em ", Ġ" dg ", Ġ" dm ")) ĊĠĠĠ Ġprintln (" Second : Ġ${ compute Steps ( init State )} ") Ċ } Ċ