package Ġw tf . log . x mas 2 0 2 1 . day . day 1 2 Ċ Ċ import Ġw tf . log . x mas 2 0 2 1 . Day Ċ import Ġjava . io . BufferedReader Ċ Ċ object ĠDay 1 2 Ġ: ĠDay < C ave System , ĠInt , ĠInt > Ġ{ ĊĊĠĠĠ Ġoverride Ġfun Ġparse Input ( reader : ĠBufferedReader ): ĠC ave System Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠC ave System . parse ( reader . line Sequence (). as Iterable ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġpart 1 ( input : ĠC ave System ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġfun ĠfindAll Paths ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinput : ĠC ave System , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput : ĠMutable Set < List < C ave >>, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath : ĠList < C ave >, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent C ave : ĠC ave , ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( current C ave Ġ== ĠC ave . END ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput Ġ+= Ġpath ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( adjacent C ave Ġin Ġinput [ current C ave ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( adjacent C ave . type Ġ== ĠC ave . Type . LARGE Ġ|| Ġadjacent C ave Ġ! in Ġpath ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠfindAll Paths ( input , Ġoutput , Ġpath Ġ+ Ġadjacent C ave , Ġadjacent C ave ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġoutput Ġ= Ġmutable Set Of < List < C ave >>() ĊĠĠĠĠĠĠĠ ĠfindAll Paths ( input , Ġoutput , ĠlistOf ( C ave . START ), ĠC ave . START ) ĊĠĠĠĠĠĠĠ Ġreturn Ġoutput . size ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġpart 2 ( input : ĠC ave System ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġfun ĠfindAll Paths ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinput : ĠC ave System , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput : ĠMutable Set < List < C ave >>, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath : ĠList < C ave >, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent C ave : ĠC ave , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhave Selected L uck y C ave : ĠBoolean , ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( current C ave Ġ== ĠC ave . END ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput Ġ+= Ġpath ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( adjacent C ave Ġin Ġinput [ current C ave ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( adjacent C ave . type Ġ== ĠC ave . Type . LARGE Ġ|| Ġadjacent C ave Ġ! in Ġpath ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠfindAll Paths ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinput Ġ= Ġinput , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput Ġ= Ġoutput , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath Ġ= Ġpath Ġ+ Ġadjacent C ave , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent C ave Ġ= Ġadjacent C ave , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhave Selected L uck y C ave Ġ= Ġhave Selected L uck y C ave , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ(! have Selected L uck y C ave Ġ&& Ġadjacent C ave Ġ!= ĠC ave . START Ġ&& Ġadjacent C ave Ġ!= ĠC ave . END ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠfindAll Paths ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinput Ġ= Ġinput , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput Ġ= Ġoutput , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath Ġ= Ġpath Ġ+ Ġadjacent C ave , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent C ave Ġ= Ġadjacent C ave , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhave Selected L uck y C ave Ġ= Ġtrue , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġoutput Ġ= Ġmutable Set Of < List < C ave >>() ĊĠĠĠĠĠĠĠ ĠfindAll Paths ( input , Ġoutput , ĠlistOf ( C ave . START ), ĠC ave . START , Ġfalse ) ĊĠĠĠĠĠĠĠ Ġreturn Ġoutput . size ĊĠĠĠ Ġ} Ċ } Ċ Ċ class ĠC ave System Ġprivate Ġconstructor ( ĊĠĠĠ Ġprivate Ġval Ġedges : ĠMap < C ave , ĠSet < C ave >>, Ċ ) Ġ{ ĊĊĠĠĠ Ġoperator Ġfun Ġget ( c ave : ĠC ave ): ĠSet < C ave > Ġ= Ġedges [ c ave ]. or Empty () ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĊĠĠĠĠĠĠĠ Ġfun Ġparse ( lines : ĠIterable < String >): ĠC ave System Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġedges Ġ= Ġmutable Map Of < C ave , ĠMutable Set < C ave >>() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( line Ġin Ġlines ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsplit Ġ= Ġline . split ('- ') ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrequire ( split . size Ġ== Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Ġ= ĠC ave . parse ( split [ 0 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Ġ= ĠC ave . parse ( split [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Edges Ġ= Ġedges . get Or Put ( left , Ġ:: mutable Set Of ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Edges Ġ= Ġedges . get Or Put ( right , Ġ:: mutable Set Of ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Edges Ġ+= Ġright ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Edges Ġ+= Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠC ave System ( edges ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ Ċ } Ċ Ċ data Ġclass ĠC ave ( ĊĠĠĠ Ġval Ġtype : ĠType , ĊĠĠĠ Ġval Ġsymbol : ĠString , Ċ ) Ġ{ ĊĊĠĠĠ Ġenum Ġclass ĠType Ġ{ ĊĠĠĠĠĠĠĠ ĠSMALL , ĠL ARGE , ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval ĠSTART Ġ= ĠC ave ( Type . SMALL , Ġ" start ") ĊĠĠĠĠĠĠĠ Ġval ĠEND Ġ= ĠC ave ( Type . SMALL , Ġ" end ") ĊĊĠĠĠĠĠĠĠ Ġfun Ġparse ( text : ĠString ): ĠC ave Ġ= ĠC ave ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtype Ġ= Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext . isEmpty () Ġ-> Ġerror (" C ave Ġname Ġmust Ġnot Ġbe Ġempty ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext . all Ġ{ Ġit . is UpperCase () Ġ} Ġ-> ĠType . LARGE ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext . all Ġ{ Ġit . is LowerCase () Ġ} Ġ-> ĠType . SMALL ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġerror (" Unsupported Ġcave Ġname : Ġ$ text ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsymbol Ġ= Ġtext , ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} Ċ } Ċ