package Ġd 1 2 _ Pass age Path ing Ċ Ċ import Ġutil . Input Ċ import Ġutil . Output Ċ Ċ val Ġupper Alpha Ġ= Ġ" A " .." Z " Ċ val Ġlower Alpha Ġ= Ġ" a " .." z " Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ ĠOutput . day ( 1 2 , Ġ" Pass age ĠPath ing ") ĊĠĠĠ Ġval ĠstartTime Ġ= ĠOutput . startTime () ĊĊĠĠĠ Ġval Ġinput Ġ= ĠInput . parse To 2 d List < String >( filename Ġ= Ġ"/ input / d 1 2 _ path _ map . txt ", Ġdelimiter Ġ= Ġ"- ") ĊĊĠĠĠ Ġval Ġcave Graph Ġ= Ġmutable Map Of < String , ĠList < String >>() ĊĠĠĠ Ġinput . forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( it [ 1 ] Ġ!= Ġ" start ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcave Graph . merge ( it [ 0 ], ĠlistOf ( it [ 1 ])) Ġ{ Ġa , Ġb Ġ-> Ġa Ġ+ Ġb Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( it [ 0 ] Ġ!= Ġ" start ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcave Graph . merge ( it [ 1 ], ĠlistOf ( it [ 0 ])) Ġ{ Ġa , Ġb Ġ-> Ġa Ġ+ Ġb Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġcave Graph [" end "] Ġ= ĠlistOf () ĊĊĠĠĠ Ġvar Ġcomplete Paths Ġ= Ġ 0 ĊĠĠĠ Ġvar Ġcomplete Paths No Repeat Ġ= Ġ 0 ĊĠĠĠ Ġval Ġcur Path Ġ= Ġmutable ListOf < String >() ĊĊĠĠĠ Ġval Ġto Do Q Ġ= Ġmutable ListOf ( Pair (" start ", Ġ 0 )) ĊĠĠĠ Ġlateinit Ġvar Ġcur Node : ĠPair < String , ĠInt > ĊĠĠĠ Ġvar Ġjust Pop ped Ġ= Ġfalse ĊĊĠĠĠ Ġwhile Ġ( to Do Q . size Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġset Ġcurrent Ġnode Ġto Ġend Ġof Ġqueue ĊĠĠĠĠĠĠĠ Ġcur Node Ġ= Ġto Do Q . last () ĊĊĠĠĠĠĠĠĠ Ġ// Ġadd Ġcurrent Ġnode Ġto Ġtracked Ġpath Ġif Ġhaven 't Ġjust Ġpop ped Ġon Ġoff ĊĠĠĠĠĠĠĠ Ġif Ġ(! just Pop ped ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Path . add ( cur Node . first ) ĊĠĠĠĠĠĠĠ Ġelse Ġjust Pop ped Ġ= Ġfalse ĊĊĠĠĠĠĠĠĠ Ġ// Ġ--- Ġfind Ġneighbors ĊĠĠĠĠĠĠĠ Ġval Ġneighbors Ġ= Ġcave Graph [ cur Node . first ] !! ĊĊĠĠĠĠĠĠĠ Ġ// Ġstart Ġat Ġcurrent Ġnode 's Ġstored Ġindex Ġto Ġavoid Ġpreviously Ġvisited Ġneighbors ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġa Ġneighbor Ġis Ġlowercase Ġand Ġin Ġthe Ġtracked Ġpath , Ġskip Ġto Ġnext ĊĠĠĠĠĠĠĠ Ġ// Ġalso Ġskip Ġto Ġnext Ġif Ġthere 's Ġnot Ġroom Ġfor Ġanother Ġsmall Ġcave ĊĠĠĠĠĠĠĠ Ġvar Ġnext Index Ġ= Ġcur Node . second ĊĠĠĠĠĠĠĠ Ġwhile Ġ( next Index Ġ< Ġneighbors . size Ġ&& Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( neighbors [ next Index ] Ġ! in Ġupper Alpha Ġ&& Ġneighbors [ next Index ] Ġin Ġcur Path Ġ&& Ġ! cur Path . room For One More ())) ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnext Index ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġif Ġat Ġ' end ' Ġor Ġno Ġneighbors Ġleft , Ġthen Ġsave , Ġpop , Ġand Ġcontinue ĊĠĠĠĠĠĠĠ Ġif Ġ( cur Node . first Ġ== Ġ" end " Ġ|| Ġnext Index Ġ>= Ġcave Graph [ cur Node . first ] !!. size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Node . first Ġ== Ġ" end ") Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcomplete Paths ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Path . room For One More ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcomplete Paths No Repeat ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Path . remove Last () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Do Q . remove Last () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġjust Pop ped Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Do Q [ to Do Q . size Ġ- Ġ 1 ] Ġ= ĠPair ( cur Node . first , Ġnext Index Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Do Q . add ( Pair ( neighbors [ next Index ], Ġ 0 )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ ĠOutput . part ( 1 , Ġ" Number Ġof ĠPaths ", Ġcomplete Paths No Repeat ) ĊĠĠĠ ĠOutput . part ( 2 , Ġ" Number Ġof ĠLong er ĠPaths ", Ġcomplete Paths ) Ċ Ċ // ĠĠĠ Ġrecursive Ġsolution Ċ // ĠĠĠ ĠOutput . part ( 1 , Ġ" Number Ġof ĠPaths ", ĠfindAll Paths ( c ave Graph , Ġ" start "). size ) Ċ // ĠĠĠ ĠOutput . part ( 2 , Ġ" Number Ġof ĠLong er ĠPaths ", ĠfindAll Paths ( c ave Graph , Ġ" start ", Ġsmall C ave Max Ġ= Ġ 2 ). size ) ĊĠĠĠ ĠOutput . execution Time ( startTime ) Ċ } Ċ Ċ fun ĠMutable List < String >. room For One More (): ĠBoolean Ġ{ ĊĠĠĠ Ġval Ġsmall s Ġ= Ġthis . filter Ġ{ Ġit Ġin Ġlower Alpha Ġ} ĊĠĠĠ Ġreturn Ġsmall s Ġ== Ġsmall s . distinct () Ċ } Ċ Ċ // Ġrecursive Ġsolution Ċ // fun ĠfindAll Paths ( Ċ // ĠĠĠ Ġgraph : ĠMap < String , ĠList < String >>, Ċ // ĠĠĠ Ġnode : ĠString , Ċ // ĠĠĠ Ġcur Path : ĠMutable List < String > Ġ= Ġmutable ListOf (), Ċ // ĠĠĠ Ġsmall C ave Max : ĠInt Ġ= Ġ 1 Ċ // ): ĠList < List < String >> Ġ{ Ċ // ĠĠĠ Ġ// Ġfor Ġreturning Ġpaths Ġin Ġa Ġlist Ġof Ġpath Ġlists Ġ- Ġy ay Ġrecursion ! Ċ // ĠĠĠ Ġval Ġsuccess Paths Ġ= Ġmutable ListOf < List < String >>() Ċ // Ċ // ĠĠĠ Ġ// Ġadd Ġnode Ġto Ġpath Ġimmediately Ġon Ġtraversal Ċ // ĠĠĠ Ġcur Path . add ( node ) Ċ // Ċ // ĠĠĠ Ġ// Ġif Ġat Ġ' end ', Ġreturn Ġthe Ġcurrent Ġtracked Ġpath Ċ // ĠĠĠ Ġif Ġ( node Ġ== Ġ" end ") Ġ{ Ċ // ĠĠĠĠĠĠĠ Ġsuccess Paths . add ( cur Path ) Ċ // ĠĠĠĠĠĠĠ Ġreturn Ġsuccess Paths Ċ // ĠĠĠ Ġ} Ġelse Ġ{ Ċ // ĠĠĠĠĠĠĠ Ġ// Ġonly Ġtraverse Ġthrough ĠLarge Ġnodes Ġor Ġnot - tra versed Ġsmall Ġnodes Ċ // ĠĠĠĠĠĠĠ Ġgraph [ node ] !!. filter Ġ{ Ċ // ĠĠĠĠĠĠĠĠĠĠĠ Ġit Ġin Ġupper Alpha Ġ|| Ġit Ġ! in Ġcur Path Ġ|| Ċ // ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( it Ġin Ġlower Alpha Ġ&& Ġsmall C ave Max Ġ> Ġ 1 Ġ&& Ġcur Path . room For One More ()) Ċ // ĠĠĠĠĠĠĠ Ġ}. forEach Ġ{ Ċ // ĠĠĠĠĠĠĠĠĠĠĠ Ġsuccess Paths . addAll ( findAll Paths ( graph , Ġit , Ġcur Path . to Mutable List (), Ġsmall C ave Max )) Ċ // ĠĠĠĠĠĠĠ Ġ} Ċ // ĠĠĠ Ġ} Ċ // Ċ // ĠĠĠ Ġ// Ġnothing Ġleft Ġto Ġtraverse , Ġdon 't Ġreturn Ġpath Ġbecause Ġnot Ġat Ġ' end ' Ċ // ĠĠĠ Ġreturn Ġsuccess Paths Ċ //} Ċ