package Ġorg . example . e 3 fx g aming . wort problem Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġfile Content Ġ= ĠInput Reader :: class . java . getResource ("/ input Ch om sky NF . txt ") ?. read Text () Ġ?: Ġthrow ĠException (" No Ġrules Ġfound ") ĊĊĠĠĠ Ġval Ġinput Reader Ġ= ĠInput Reader ( file Content ) ĊĊĠĠĠ Ġval Ġfirst Test Word Ġ= Ġ" aba aba " ĊĠĠĠ Ġval Ġsecond Test Word Ġ= Ġ" ab bb ba " ĊĠĠĠ Ġval Ġthird Test Word Ġ= Ġ" bb abb ba ab ba ab bb abb " ĊĠĠĠ Ġval Ġfalse Word Ġ= Ġ" aa ab bbb " ĊĊĠĠĠ Ġval Ġsolver Ġ= ĠSolver ( input Reader ) ĊĠĠĠ Ġprintln ("$ first Test Word : Ġ${ solver . solve ( first Test Word )} ") ĊĠĠĠ Ġprintln ("$ second Test Word : Ġ${ solver . solve ( second Test Word )} ") ĊĠĠĠ Ġprintln ("$ third Test Word : Ġ${ solver . solve ( third Test Word )} ") ĊĠĠĠ Ġprintln ("$ false Word : Ġ${ solver . solve ( false Word )} ") ĊĊĠĠĠ Ġprintln ( input Reader ) Ċ } Ċ Ċ /** Ċ Ġ* ĠClass Ġfor Ġreading Ġthe ĠCh om sky ĠNF Ġinput . ĠAlso Ġholds Ġthe Ġcache . Ċ Ġ*/ Ċ class ĠInput Reader ( file Content : ĠString ) Ġ{ ĊĠĠĠ Ġ// Maps Ġsecond Ġpart Ġof Ġrule Ġto Ġall Ġpossible Ġfirst Ġparts ĊĠĠĠ Ġprivate Ġval Ġrules Ġ= Ġfile Content . split ( System . getProperty (" line . separator ")) ĊĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġit . split (" -> ") Ġ} ĊĠĠĠĠĠĠĠ Ġ. map Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠRule ( it [ 0 ], Ġit [ 1 ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġreversed Rules Ġ= Ġrules . groupBy Ġ{ ĊĠĠĠĠĠĠĠ Ġit . production Output ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// caching Ġrule Ġwrappers Ġto Ġspeed Ġup Ġsubsequent Ġsame - word - evalu ations ĊĠĠĠ Ġval Ġcache : ĠMutable Map < String , ĠDer ivation Wrapper > Ġ= Ġmutable Map Of () ĊĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ" Read Ġ${ rules . size Ġ} Ġrules . ĠCurrent Ġcache Ġsize : Ġ${ cache . size } Ġentries ." ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠAn Ġelement Ġof Ġthe Ġproduction Ġsystem , Ġthat Ġcan Ġtransform Ġa Ġ[ variable ] Ġinto Ġa Ġ[ production Output ] Ċ Ġ*/ Ċ data Ġclass ĠRule ( val Ġvariable : ĠString , Ġval Ġproduction Output : ĠString ) Ġ{ ĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ"$ variable ->$ production Output " ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠSince Ġthe Ġsame Ġ[ word ] Ġmay Ġbe Ġderived Ġin Ġmultiple Ġways , Ġthis ĠDer ivation Wrapper Ġbundles Ġthe Ġpossible Ġ[ deriv ations ]. Ċ Ġ* ĠAlso Ġstores Ġinformation Ġabout Ġits Ġdirect Ġ[ left ] Ġand Ġ[ right ] ĠDer ivation Wrapper Ġdesc endants . Ċ Ġ* Ċ Ġ*/ Ċ data Ġclass ĠDer ivation Wrapper ( val Ġword : ĠString , Ġval Ġderiv ations : ĠList < Der ivation Operation >, Ġval Ġleft : ĠDer ivation Wrapper ?, Ġval Ġright : ĠDer ivation Wrapper ?) Ġ{ ĊĠĠĠ Ġfun Ġget Child ( child Selector : Ġ( Der ivation Wrapper ) Ġ-> ĠDer ivation Wrapper ?, Ġcollection List : ĠMutable List < Der ivation Wrapper >): ĠList < Der ivation Wrapper > Ġ{ ĊĠĠĠĠĠĠĠ Ġcollection List . add ( this ) ĊĠĠĠĠĠĠĠ Ġchild Selector ( this )?. getChild ( child Selector , Ġcollection List ) ĊĠĠĠĠĠĠĠ Ġreturn Ġcollection List ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġderiv ations . join ToString ("\ n ") ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠRepresents Ġa Ġsingle Ġder ivation ĠA Ġ-> ĠA ĠB Ġwith Ġ[ rule ], Ġwhere ĠA Ġends Ġat Ġ[ first Segment End s AtIndex ]. Ċ Ġ*/ Ċ data Ġclass ĠDer ivation Operation ( val Ġrule : ĠRule , Ġval Ġfirst Segment End s AtIndex : ĠInt ) Ġ{ ĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ"$ rule Ġ($ first Segment End s AtIndex )" ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠWrapper Ġclass Ġfor Ġsolving Ġword Ġproblems . Ċ Ġ* Ġ[ input Reader ] Ġprovides Ġthe Ġgrammar Ġinformation . Ċ Ġ*/ Ċ class ĠSolver ( private Ġval Ġinput Reader : ĠInput Reader ) Ġ{ ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠTests Ġwhether Ġa Ġ[ word ] Ġstring Ġbelongs Ġto Ġthe Ġlanguage Ġof Ġthe Ġprovided Ġgrammar . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsolve ( word : ĠString ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsolution Py ramid : ĠMutable List < List < Der ivation Wrapper >> Ġ= Ġmutable ListOf () ĊĊĠĠĠĠĠĠĠ Ġ// create Ġfoundation Ġrow Ġof Ġsolution Py ramid ĊĠĠĠĠĠĠĠ Ġword . map Ġ{ Ġword Char Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsubstring Ġ= Ġword Char . toString () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġinput Reader . cache [ substring ]?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn @ map Ġit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġderiv ations Ġ= Ġinput Reader . reversed Rules [ substring ]?. map Ġ{ Ġrule Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠDer ivation Operation ( rule , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}. or Empty () ĊĊĠĠĠĠĠĠĠĠĠĠĠ ĠDer ivation Wrapper ( substring , Ġderiv ations , Ġnull , Ġnull ). also Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinput Reader . cache [ it . word ] Ġ= Ġit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ}. let Ġ{ Ġfirst Row Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsolution Py ramid . add ( first Row ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĊĠĠĠĠĠĠĠ Ġ// create Ġtop Ġrows Ġof Ġsolution Py ramid ĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlast Row Ġ= Ġsolution Py ramid . last () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcombination Pairs Ġ= Ġ( 0 Ġuntil Ġlast Row . last Index ). map Ġ{ Ġindex First Element Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Der ivation Wrapper Ġ= Ġlast Row [ index First Element ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Der ivation Wrapper Ġ= Ġlast Row [ index First Element Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsubstring Ġ= Ġword . substring ( index First Element , Ġindex First Element Ġ+ Ġsolution Py ramid . size Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcombine Pairs ( left Der ivation Wrapper , Ġright Der ivation Wrapper , Ġsubstring ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsolution Py ramid . add ( combin ation Pairs ) ĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( solution Py ramid . last (). size Ġ!= Ġ 1 ) ĊĊĠĠĠĠĠĠĠ Ġreturn Ġsolution Py ramid . last (). first (). deriv ations . any Ġ{ Ġit . rule . variable Ġ== Ġ" S " Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCombin es Ġa Ġ[ left Der ivation Wrapper ] Ġand Ġ[ right Der ivation Wrapper ] Ġinto Ġa Ġsuperior Ġ[ Der ivation Wrapper ] Ġfor Ġa Ġgiven Ġ[ word ] ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġcombine Pairs ( left Der ivation Wrapper : ĠDer ivation Wrapper , Ġright Der ivation Wrapper : ĠDer ivation Wrapper , Ġword : ĠString ): ĠDer ivation Wrapper Ġ{ ĊĠĠĠĠĠĠĠ Ġinput Reader . cache [ word ]?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġit ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġleft Der ivation Wrappers Ġ= Ġleft Der ivation Wrapper . getChild ({ it . left }, Ġmutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġval Ġright Der ivation Wrappers Ġ= Ġright Der ivation Wrapper . getChild ({ it . right }, Ġmutable ListOf ()) ĊĊĠĠĠĠĠĠĠ Ġif ( left Der ivation Wrappers . size Ġ!= Ġright Der ivation Wrappers . size ) Ġthrow ĠException (" Der ivation Wrapper Ġnot Ġbal anced ") ĊĊĠĠĠĠĠĠĠ Ġval Ġpairs Ġ= Ġleft Der ivation Wrappers . zip ( right Der ivation Wrappers . reversed ()). filter Not Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . first . deriv ations . isEmpty () Ġ|| Ġit . second . deriv ations . isEmpty () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġder ivation Operations Ġ= Ġpairs . map Ġ{ Ġder ivation Wrappers Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfirst Production Inputs Ġ= Ġder ivation Wrappers . first . deriv ations . map Ġ{ Ġit . rule . variable Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsecond Production Inputs Ġ= Ġder ivation Wrappers . second . deriv ations . map Ġ{ Ġit . rule . variable Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġproduction Pairs Ġ= Ġfirst Production Inputs . to Pair List ( second Production Inputs ). map Ġ{ Ġit . join ToString (" Ġ") Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġapplicable Rules Ġ= Ġproduction Pairs . map NotNull Ġ{ Ġproduction Pair Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinput Reader . reversed Rules [ production Pair ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}. flatten () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġapplicable Rules . map Ġ{ ĠDer ivation Operation ( it , Ġder ivation Wrappers . first . word . length ) Ġ} ĊĠĠĠĠĠĠĠ Ġ}. flatten () ĊĊĠĠĠĠĠĠĠ Ġreturn ĠDer ivation Wrapper ( word , Ġder ivation Operations , Ġleft Der ivation Wrapper , Ġright Der ivation Wrapper ). also Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinput Reader . cache [ it . word ] Ġ= Ġit ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠCreates Ġthe ĠCart esian Ġproduct Ġof Ġthe Ġelements Ġof Ġthis ĠList Ġand Ġa Ġdifferent Ġ[ other List ] ĠList . Ċ Ġ*/ Ċ private Ġfun ĠList < String >. to Pair List ( other List : ĠList < String >) Ġ= Ġflat Map Ġ{ Ġa Item Ġ-> ĊĠĠĠ Ġother List . map Ġ{ Ġb Item Ġ-> ĊĠĠĠĠĠĠĠ ĠlistOf ( a Item , Ġb Item ) Ġ} Ċ }