import Ġjava . io . File Ċ Ċ /** Ċ Ġ* ĠA o C 2 0 1 6 ĠDay 2 4 a Ġmain Ġclass . Ċ Ġ* ĠDay Ġ 2 4 : ĠAir ĠD uct ĠSp el unk ing . Ċ Ġ* ĠThe Ġlab yr in th / graph Ġworks Ġexactly Ġlike Ġin ĠA o C 1 6 Ġday Ġ 1 3 . Ċ Ġ* Ċ Ġ* ĠRun Ġwith : Ġ` run b . sh `. Ċ Ġ*/ Ċ class ĠDay 2 4 a Ġ: ĠA oc Base () Ġ{ ĊĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠ Ġval ĠMAX RO UN DS _ LAB YR Ġ= Ġ 2 5 6 Ġ Ġ// Ġmax Ġcalc Ġrounds Ġfor Ġget t ng Ġshortest Ġpath Ġbetween Ġtwo Ġnodes Ġin Ġlab yr in th ĊĠĠĠ Ġval ĠMAX RO UN DS _ TR AV EL Ġ= Ġ 1 0 Ġ Ġ// Ġmax Ġh ops Ġfor Ġgetting Ġshortest Ġtr ave le Ġfor Ġall Ġpoints ĊĠĠĠ Ġval ĠMAX SOL UTION S Ġ= Ġ 1 0 2 4 ĊĠĠĠ Ġval ĠDOT EACH Ġ= Ġ 1 0 0 0 0 0 ĊĠĠĠ Ġvar Ġinput Title Ġ= Ġ"" ĊĊĠĠĠ Ġval ĠTEST STR Ġ= Ġ""" Ċ ######## ### Ċ # 0 . 1 ..... 2 # Ċ #. ####### .# Ċ # 4 ....... 3 # Ċ ######## ### ĊĠ Ġ""" . trim Indent () ĊĊĠĠĠ Ġfun Ġcreate (): ĠDay 2 4 a Ġ= ĠDay 2 4 a () ĊĊĠĠĠ Ġ@ Jvm Static Ġfun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠĠĠ Ġprintln (" Day Ġstarting ...") ĊĠĠĠĠĠ Ġval Ġo Ġ= Ġcreate () ĊĠĠĠĠĠ Ġinput Title Ġ= Ġ" test " ĊĠĠĠĠĠ Ġo . process ( TEST STR ) ĊĠĠĠĠĠ Ġprintln (" TEST Ġended , Ġproblem - solution Ġstarting ...") ĊĠĠĠĠĠ Ġ// o . process ( TEST STR ) ĊĠĠĠĠĠ Ġ// File (" some file . txt "). read Lines (). forEach Ġ{ ĊĠĠĠĠĠ Ġ//} ĊĠĠĠĠĠ Ġinput Title Ġ= Ġ" r he input " ĊĠĠĠĠĠ Ġval Ġdata str Ġ= ĠFile (" day 2 4 _ data . txt "). read Text () ĊĠĠĠĠĠ Ġo . process ( data str ) ĊĠĠĠĠĠ Ġprintln (" ... Day Ġends . !") ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġvar Ġstart tm Ġ= ĠSystem . currentTimeMillis () ĊĠ Ġvar Ġlast tt m Ġ= ĠSystem . currentTimeMillis () ĊĊĠ Ġprivate Ġfun Ġprocess ( repr 2 d : ĠString ) Ġ{ ĊĠĠĠ Ġtrace log (" found :\ n $ repr 2 d ") ĊĠĠĠ Ġstart tm Ġ= ĠSystem . currentTimeMillis () ĊĊĠĠĠ Ġval Ġworld Ġ= ĠWorld . create ( repr 2 d ) ĊĠĠĠ Ġworld . print grid () ĊĠĠĠ Ġval Ġpoint edges : ĠList < Point Edge > Ġ= Ġget Point Edges ( world ) ĊĠĠĠ Ġde blog (" edges : Ġ${ point edges }") ĊĠĠĠ Ġval Ġg Ġ= Ġbuild World Graph ( world ) ĊĠĠĠ Ġprintln (" graph : Ġ$ g ") ĊĠĠĠ Ġlast tt m Ġ= ĠSystem . currentTimeMillis () ĊĠĠĠ Ġinfo log (" world - building - TM =${ last tt m - start tm }") ĊĊĠĠĠ Ġpoint edges . forEach Ġ{ Ġpt sed ge Ġ-> ĊĠĠĠĠĠ Ġde blog (" calc Ġshortest Path Ġfor Ġpoint edge : Ġ$ pt sed ge ") ĊĠĠĠĠĠ Ġval Ġpts dist Ġ= Ġget Short est Path ( pt sed ge . node 1 , Ġpt sed ge . node 2 , Ġg ) ĊĠĠĠĠĠ Ġval Ġout str Ġ= Ġ"${ pt sed ge . getId String ()} =$ pts dist \ n " ĊĠĠĠĠĠ ĠFile (" day 2 4 _ paths _${ input Title }. txt "). append Text ( out str ) ĊĠĠĠĠĠ Ġval Ġtm Ġ= ĠSystem . currentTimeMillis () ĊĠĠĠĠĠ Ġinfo log (" Ġ Ġget Short est Path ĠTM =${ tm - last tt m }") ĊĠĠĠĠĠ Ġlast tt m Ġ= Ġtm ĊĠĠĠĠĠ Ġpt sed ge . dist Ġ= Ġpts dist ĊĠĠĠ Ġ} ĊĠĠĠ Ġpoint edges . forEach Ġ{ Ġpt sed ge Ġ-> ĊĠĠĠĠĠ Ġinfo log (" weighted Ġedge : Ġ$ pt sed ge ") ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġstart node Ġ= Ġworld . point nodes . filter Ġ{ Ġit . nod ename Ġ== Ġ" 0 " Ġ}. first () ĊĠĠĠ Ġinfo log (" start - node : Ġ$ start node ") ĊĠĠĠ Ġval Ġmin Travel Dist Ġ= Ġsolve Min Dist ( point edges , Ġstart node ) ĊĠĠĠ Ġinfo log (" travel Ġcomplete Ġwith Ġdist =$ min Travel Dist ") ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġsolve Min Dist ( point edges : ĠList < Point Edge >, Ġstart node : ĠPoint Node ): ĠInt Ġ{ ĊĠĠĠ Ġvar Ġbest dist Ġ= Ġ- 1 ĊĠĠĠ Ġvar Ġbest path Ġ= ĠPath ( Point Node (" 0 , 0 ", Ġ" undef ")) ĊĊĠĠĠ Ġde blog (" solve Min Dist , Ġnum - wt - edges =${ point edges . size }, Ġstart pt =$ start node ") ĊĊĠĠĠ Ġval Ġnode set Ġ= Ġmutable Set Of < String >() ĊĠĠĠ Ġpoint edges . forEach Ġ{ ĊĠĠĠĠĠ Ġnode set . add ( it . node 1 . nod ename ) ĊĠĠĠĠĠ Ġnode set . add ( it . node 2 . nod ename ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġfind size Ġ= Ġnode set . size ĊĠĠĠ Ġinfo log (" find - size =$ find size ; Ġfrom >> Ġ$ node set ") ĊĊĠĠĠ Ġval Ġal led ges Ġ= Ġmutable ListOf < Point Edge >() ĊĠĠĠ Ġpoint edges . forEach Ġ{ Ġp ted ge Ġ-> ĊĠĠĠĠĠ Ġal led ges . add ( pt edge ) ĊĠĠĠĠĠ Ġal led ges . add ( Point Edge ( pt edge . node 2 , Ġp ted ge . node 1 , Ġp ted ge . dist )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġsolutions Ġ= Ġmutable Set Of < Path >() ĊĊĠĠĠ Ġval Ġfirst Path Ġ= ĠPath ( start node ) ĊĠĠĠ Ġvar Ġround Ġ= Ġ 0 ĊĠĠĠ Ġval Ġcur Paths Ġ= Ġmutable ListOf < Path >() ĊĠĠĠ Ġcur Paths . clear () ĊĠĠĠ Ġcur Paths . add ( first Path ) ĊĠĠĠ Ġval Ġnext Paths Ġ= Ġmutable ListOf < Path >() ĊĠĠĠ Ġnext Paths . clear () ĊĠĠĠ Ġwhile Ġ( round Ġ< ĠMAX RO UN DS _ TR AV EL ) Ġ{ ĊĠĠĠĠĠ Ġround Ġ+= Ġ 1 ĊĠĠĠĠĠ Ġtrace log (" ROUND Ġ#$ round ") ĊĠĠĠĠĠ Ġnext Paths . forEach Ġ{ Ġcur Paths . add ( it ) Ġ} Ġ// Ġsome Ġdata struct Ġsh ifting ĊĠĠĠĠĠ Ġnext Paths . clear () Ġ// Ġclear Ġnext Ġpaths ĊĠĠĠĠĠ Ġcur Paths . forEach Ġ{ Ġcur Path Ġ-> ĊĠĠĠĠĠĠĠ Ġtrace log (" cur Path : Ġ${ cur Path . to Ext String () }") ĊĠĠĠĠĠĠĠ Ġval Ġcur Node Ġ= Ġcur Path . last node ĊĠĠĠĠĠĠĠ Ġal led ges . filter Ġ{ Ġit . node 1 . nod ename Ġ== Ġcur Node . nod ename Ġ}. forEach Ġ{ Ġedge Ġ-> ĊĠĠĠĠĠĠĠĠĠ Ġtrace log (" possible Ġnext Ġnode Ġ${ edge . node 2 }, Ġdist =${ edge . dist } Ġ< Ġedge =$ edge ") ĊĠĠĠĠĠĠĠĠĠ Ġval Ġnext Path Ġ= Ġcur Path . dup () Ġ// . copy ĊĠĠĠĠĠĠĠĠĠ Ġnext Path . add Edge ( edge ) ĊĠĠĠĠĠĠĠĠĠ Ġtrace log (" Ġ Ġadding Ġnext - path =${ next Path . to Ext String () }") ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( next Path . node set . size Ġ== Ġfind size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// throw ĠRuntimeException (" found Ġsolution Ġpath , Ġmin - dst =${ next Path . total dist }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// info log (" found Ġsolution Ġpath , Ġmin - dst =${ next Path . total dist }, Ġnodes =${ next Path . node set }, Ġedges =${ next Path . edges }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtrace log ( getPath Diag ( next Path )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsolutions . add ( next Path ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next Path . total dist Ġ< Ġbest dist Ġ|| Ġbest dist Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbest dist Ġ= Ġnext Path . total dist ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbest path Ġ= Ġnext Path ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġde blog (" new Ġbest Ġpath , Ġdist =${ next Path . total dist } Ġ>> " Ġ+ ĠgetPath Diag ( next Path )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( solutions . size Ġ>= ĠMAX SOL UTION S ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinfo log (" best Ġpath ĠI Ġof Ġ# ${ solutions . size } Ġ@ Ġround =$ round ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinfo log ( getPath Diag ( best path )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġbest path . total dist ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnext Paths . add ( next Path ) ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġcur Paths . clear () ĊĠĠĠĠĠ Ġde blog (" end - of - round Ġ#$ round Ġnext - paths - size =${ next Paths . size }") ĊĠĠĠ Ġ} ĊĠĠĠ Ġif Ġ( solutions . size Ġ> Ġ 0 Ġ) Ġ{ ĊĠĠĠĠĠ Ġinfo log (" best Ġpath ĠII Ġof Ġ# ${ solutions . size } Ġ@ Ġround =$ round ") ĊĠĠĠĠĠ Ġinfo log ( getPath Diag ( best path )) ĊĠĠĠĠĠ Ġreturn Ġbest path . total dist ĊĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠ Ġreturn Ġ- 1 ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun ĠgetPath Diag ( next Path : ĠPath ): ĠString Ġ{ ĊĠĠĠ Ġvar Ġos Ġ= Ġ"" ĊĠĠĠ Ġnext Path . edges . forEach Ġ{ ĊĠĠĠĠĠ Ġos Ġ+= Ġit . node 1 . nod ename ĊĠĠĠĠĠ Ġos Ġ+= Ġ" (${ it . dist })" ĊĠĠĠ Ġ} ĊĠĠĠ Ġos Ġ+= Ġnext Path . last node . nod ename ĊĠĠĠ Ġos Ġ= Ġ" FOUND ĠSol v Path Ġmin - dst =${ next Path . total dist }, Ġnodes =$ os " ĊĠĠĠ Ġreturn Ġos ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġget Short est Path ( pn 1 : ĠPoint Node , Ġpn 2 : ĠPoint Node , Ġgraph : ĠGraph Un dir Un w td ): ĠInt Ġ{ ĊĠĠĠ Ġde blog (" get Short est Path (${ pn 1 . nod ename }, Ġ${ pn 2 . nod ename }): Ġ${ pn 1 . node id } Ġ- Ġ${ pn 2 . node id }") ĊĊĠĠĠ Ġval Ġstart Node Ġ= ĠNode ( pn 1 . node id ) ĊĠĠĠ Ġval Ġend Node Ġ= ĠNode ( pn 2 . node id ) ĊĠĠĠ Ġval Ġpro ct m Ġ= ĠSystem . currentTimeMillis () ĊĊĠĠĠ Ġval Ġstart Node id Ġ= Ġstart Node . node id ĊĠĠĠ Ġval Ġend Node id Ġ= Ġend Node . node id ĊĠĠĠ Ġval Ġfirst nid Ġ= Ġstart Node id ĊĠĠĠ Ġval Ġfirst Path Ġ= ĠlistOf ( first nid ) ĊĠĠĠ Ġvar Ġround Ġ= Ġ 0 ĊĠĠĠ Ġval Ġcur Paths Ġ= Ġmutable ListOf ( listOf < String >()) ĊĠĠĠ Ġcur Paths . clear () ĊĠĠĠ Ġcur Paths . add ( first Path ) ĊĠĠĠ Ġ// assert msg ( first Path . size Ġ== Ġ 1 , Ġ" one Ġin ĠList Ġfirst path ") ĊĠĠĠ Ġ// assert msg ( cur Paths . size Ġ== Ġ 1 , Ġ" one Ġin ĠList Ġcur paths Ġ${ cur Paths . size }") ĊĠĠĠ Ġval Ġnext Paths Ġ= Ġmutable ListOf ( listOf < String >()) ĊĠĠĠ Ġnext Paths . clear () ĊĠĠĠ Ġval Ġseen Nodes Ġ= Ġmutable Set Of < String >() ĊĠĠĠ Ġseen Nodes . add ( start Node id ) ĊĠĠĠ Ġvar Ġla str dt m Ġ= ĠSystem . currentTimeMillis () ĊĠĠĠ Ġvar Ġrejected num Ġ= Ġ 0 ĊĠĠĠ Ġvar Ġaccepted num Ġ= Ġ 0 ĊĠĠĠ Ġwhile Ġ( round Ġ< ĠMAX RO UN DS _ LAB YR ) Ġ{ ĊĠĠĠĠĠ Ġround Ġ+= Ġ 1 ĊĠĠĠĠĠ Ġval Ġr dt m Ġ= ĠSystem . currentTimeMillis () ĊĠĠĠĠĠ Ġvar Ġs Ġ= Ġ"" ĊĠĠĠĠĠ Ġif Ġ( accepted num Ġ>= ĠDOT EACH ) Ġ{ ĊĠĠĠĠĠĠĠ Ġs Ġ+= Ġ"\ n ĠĠ Ġ" ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġde blog ("${ s } ROUND Ġ#$ round , Ġwatch - paths =${ next Paths . size }; Ġreject # =${ rejected num }. Ġd TM =${ ( r dt m - la str dt m )/ 1 0 0 0 . 0 }") ĊĠĠĠĠĠ Ġaccepted num Ġ= Ġ 0 ĊĠĠĠĠĠ Ġrejected num = 0 ĊĠĠĠĠĠ Ġla str dt m Ġ= Ġr dt m ĊĠĠĠĠĠ Ġnext Paths . forEach Ġ{ Ġcur Paths . add ( it ) Ġ} Ġ// Ġsome Ġdata struct Ġsh ifting ĊĠĠĠĠĠ Ġnext Paths . clear () Ġ// Ġclear Ġnext Ġpaths ĊĠĠĠĠĠ Ġcur Paths . forEach Ġ{ Ġcur Path Ġ-> ĊĠĠĠĠĠĠĠ Ġval Ġc urn id Ġ= Ġcur Path . last () ĊĠĠĠĠĠĠĠ Ġval Ġnext Nodes Ġ= Ġgraph . edges . filter Ġ{ Ġit . node id 1 Ġ== Ġc urn id Ġ}. map Ġ{ Ġit . node id 2 Ġ} ĊĠĠĠĠĠĠĠ Ġnext Nodes . forEach Ġ{ Ġstr Ġ-> ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( str Ġ== Ġend Node id ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! seen Nodes . contains ( str )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġseen Nodes . add ( str ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġde blog (" FOUND Ġshortest Ġpath Ġ${ pn 1 . nod ename }-${ pn 2 . nod ename }, Ġlen =${ cur Path . size }! Ġ${ cur Path } Ġ$ str . Ġseen - nodes - # =${ seen Nodes . size }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġde blog (" Ġ Ġproc - TM =${ ( System . currentTimeMillis () Ġ- Ġpro ct m )/ 1 0 0 0 . 0 }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// throw ĠRuntimeException (" found Ġat ĠRO UND Ġ#$ round ; Ġpath - len =${ cur Path . size }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcur Path . size ĊĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ(! cur Path . contains ( str )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnw Ġ= Ġmutable ListOf < String >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Path . forEach Ġ{ Ġnw . add ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnw . add ( str ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// trace log (" adding Ġnext Ġpath Ġ$ nw ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġaccepted num Ġ+= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnext Paths . add ( nw ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! seen Nodes . contains ( str )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġseen Nodes . add ( str ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( accepted num Ġ% ĠDOT EACH Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSystem . err . print (". ${ System . currentTimeMillis ()- la str dt m } Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSystem . err . flush () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmax set Ġ= Ġ 1 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( accepted num Ġ>= Ġmax set ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Paths Ġ= Ġnext Paths . sorted By Descending Ġ{ Ġpath cost ( pn 2 , Ġit ) Ġ}. take ( max set ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// trace log (" rejected Ġself - ref Ġpath Ġ${ cur Path } Ġ$ str ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrejected num Ġ+= Ġ 1 ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġcur Paths . clear () ĊĠĠĠ Ġ} ĊĠĠĠ Ġ// println (" ABORT Ġafter Ġround Ġ#$ round ; Ġseen - nodes - # =${ seen Nodes . size }") ĊĠĠĠ Ġthrow ĠRuntimeException (" ABORT Ġafter Ġround Ġ#$ round ; Ġseen - nodes - # =${ seen Nodes . size }") ĊĠĠĠ Ġ// return Ġ- 1 ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġpath cost ( target Point Node : ĠPoint Node , Ġit : ĠList < String >): ĠAny Ġ{ ĊĠĠĠ Ġthrow ĠUnsupportedOperationException (" not Ġimplemented ") Ġ// To Ġchange Ġbody Ġof Ġcreated Ġfunctions Ġuse ĠFile Ġ| ĠSettings Ġ| ĠFile ĠTemplates . ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġbuild World Graph ( world : ĠWorld ): ĠGraph Un dir Un w td Ġ{ ĊĠĠĠ Ġ// ** Ġbuild Ġworld Ġnodes Ġgraph ĊĠĠĠ Ġval Ġg Ġ= ĠGraph Un dir Un w td () ĊĠĠĠ Ġfor Ġ( y Ġin Ġ 0 .. world . dim y Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 .. world . dim x Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( world . grid [ y ][ x ] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġtrace log (" add Ġnode ($ x ,$ y )") ĊĠĠĠĠĠĠĠĠĠ Ġg . add Node ("$ x ,$ y ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġde blog (" build world graph : Ġnodes Ġ# :${ g . nodes . size }") ĊĊĠĠĠ Ġ// ** Ġbuild Ġworld Ġnodes - graph ĠEd ges ĊĠĠĠ Ġfor Ġ( y Ġin Ġ 0 .. world . dim y Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 .. world . dim x Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( world . grid [ y ][ x ] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġedges ĊĠĠĠĠĠĠĠĠĠ Ġvar Ġyy Ġ= Ġy Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( yy Ġ>= Ġ 0 Ġ&& Ġg . contains Node ("$ x ,$ yy ")) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" add Ġedge ($ x ,$ y < =>$ x ,$ yy )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġg . add Edge ("$ x ,$ y ", Ġ"$ x ,$ yy ") ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġyy Ġ= Ġy Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( yy Ġ< Ġworld . dim y Ġ&& Ġg . contains Node ("$ x ,$ yy ")) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" add Ġedge ($ x ,$ y < =>$ x ,$ yy )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġg . add Edge ("$ x ,$ y ", Ġ"$ x ,$ yy ") ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġvar Ġxx Ġ= Ġx Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( xx Ġ>= Ġ 0 Ġ&& Ġg . contains Node ("$ xx ,$ y ")) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" add Ġedge ($ x ,$ y < =>$ xx ,$ y )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġg . add Edge ("$ x ,$ y ", Ġ"$ xx ,$ y ") ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġxx Ġ= Ġx Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( xx Ġ< Ġworld . dim x Ġ&& Ġg . contains Node ("$ xx ,$ y ")) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" add Ġedge ($ x ,$ y < =>$ xx ,$ y )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġg . add Edge ("$ x ,$ y ", Ġ"$ xx ,$ y ") ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġde blog (" build world graph : Ġedges Ġ# :${ g . edges . size }") ĊĠĠĠ Ġreturn Ġg ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġget Point Edges ( world : ĠWorld ): ĠList < Point Edge > Ġ{ ĊĠĠĠ Ġval Ġpoint nodes Ġ= Ġworld . point nodes ĊĠĠĠ Ġval Ġpoint edges Ġ= Ġmutable ListOf < Point Edge >() ĊĠĠĠ Ġpoint nodes . forEach Ġ{ Ġpt node Ġ-> ĊĠĠĠĠĠ Ġpoint nodes . forEach Ġ{ Ġpt node 2 Ġ-> ĊĠĠĠĠĠĠĠ Ġif Ġ(!( pt node . nod ename Ġ== Ġpt node 2 . nod ename )) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġ// if Ġ(! point edges . contains ("${ pt node 2 . nod ename }-${ pt node . nod ename } ")) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġinfo log (" edge : Ġ${ pt node . nod ename } < => ${ pt node 2 . nod ename }; Ġ${ pt node . node id }-${ pt node 2 . node id }") ĊĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġpoint edges . add ("${ pt node . nod ename }-${ pt node 2 . nod ename }") ĊĠĠĠĠĠĠĠĠĠ Ġ//} ĊĠĠĠĠĠĠĠĠĠ Ġvar Ġseen Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠ Ġpoint edges . forEach Ġ{ Ġp ted ge Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( pt node . node id Ġ== Ġp ted ge . node 1 . node id Ġ&& Ġpt node 2 . node id Ġ== Ġp ted ge . node 2 . node id ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ|| Ġ( pt node . node id Ġ== Ġp ted ge . node 2 . node id Ġ&& Ġpt node 2 . node id Ġ== Ġp ted ge . node 1 . node id ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġseen Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ(! seen ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinfo log (" add ĠPoint edge Ġ$ pt node Ġto Ġ$ pt node 2 ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoint edges . add ( Point Edge ( pt node , Ġpt node 2 )) ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġpoint edges . sorted By Ġ{ Ġit . node 1 . nod ename Ġ+ Ġit . node 2 . nod ename Ġ}. toList () ĊĠ Ġ} Ċ } Ċ