package Ġcom . github . cor ne il . a oc 2 0 1 9 . day 2 2 Ċ Ċ import Ġcom . github . cor ne il . a oc 2 0 1 9 . day 2 2 . Instruction . Cut Ċ import Ġcom . github . cor ne il . a oc 2 0 1 9 . day 2 2 . Instruction . Increment Ċ import Ġcom . github . cor ne il . a oc 2 0 1 9 . day 2 2 . Instruction . Reverse Ċ import Ġjava . io . File Ċ import Ġjava . math . BigInteger Ċ Ċ infix Ġfun ĠBigInteger .` %% `( b : ĠBigInteger ): ĠBigInteger Ġ{ ĊĠĠĠ Ġval Ġr Ġ= Ġthis Ġ% Ġb ĊĠĠĠ Ġreturn Ġif Ġ( r Ġ< ĠBigInteger . ZERO ) Ġr Ġ+ Ġb Ġelse Ġr Ċ } Ċ Ċ infix Ġfun ĠLong .` %% `( b : ĠLong ): ĠLong Ġ{ ĊĠĠĠ Ġreturn Ġ( this . to BigInteger () Ġ` %% ` Ġb . to BigInteger ()). to Long () Ċ } Ċ Ċ sealed Ġclass ĠInstruction Ġ{ ĊĠĠĠ Ġdata Ġclass ĠIncrement ( val Ġinc : ĠInt ) Ġ: ĠInstruction () ĊĠĠĠ Ġdata Ġclass ĠCut ( val Ġn : ĠInt ) Ġ: ĠInstruction () ĊĠĠĠ Ġobject ĠReverse Ġ: ĠInstruction () Ċ } Ċ Ċ fun Ġparse ( input : ĠString ): ĠInstruction Ġ{ ĊĠĠĠ Ġval Ġr Ġ= Ġmap Of < String , Ġ( Match Result ) Ġ-> ĠInstruction >( ĊĠĠĠĠĠĠĠ Ġ" deal Ġinto Ġnew Ġstack " Ġto Ġ{ Ġ_ Ġ-> ĠReverse Ġ}, ĊĠĠĠĠĠĠĠ Ġ" deal Ġwith Ġincrement Ġ( \\ d + )" Ġto Ġ{ Ġs Ġ-> ĠIncrement ( s . group Values . get ( 1 ). toInt ()) Ġ}, ĊĠĠĠĠĠĠĠ Ġ" cut Ġ(- ? \\ d + )" Ġto Ġ{ Ġs Ġ-> ĠCut ( s . group Values . get ( 1 ). toInt ()) Ġ} ĊĠĠĠ Ġ) ĊĠĠĠ Ġreturn Ġr . entries . find Ġ{ ĊĠĠĠĠĠĠĠ Ġit . key . to Regex (). matches ( input ) ĊĠĠĠ Ġ} ?. let Ġ{ ĊĠĠĠĠĠĠĠ Ġit . value ( it . key . to Regex (). match Ent ire ( input ) !! ) ĊĠĠĠ Ġ} Ġ?: Ġerror (" Could Ġnot Ġdetermine Ġ$ input ") Ċ } Ċ Ċ fun Ġreverse Index ( index : ĠLong , Ġdeck : ĠLong , Ġiterations : ĠLong Ġ= Ġ 1 L ): ĠLong Ġ{ ĊĠĠĠ Ġreturn Ġif Ġ( iterations Ġ% Ġ 2 L Ġ== Ġ 0 L ) ĊĠĠĠĠĠĠĠ Ġindex ĊĠĠĠ Ġelse ĊĠĠĠĠĠĠĠ Ġdeck Ġ- Ġ( index Ġ+ Ġ 1 ) Ċ } Ċ Ċ fun Ġreverse ( deck : ĠArray < Int >): ĠArray < Int > Ġ{ ĊĠĠĠ Ġprintln (" deal Ġinto Ġnew Ġstack ") ĊĠĠĠ Ġval Ġresult Ġ= ĠArray ( deck . size ) Ġ{ Ġ- 1 Ġ} ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġdeck . size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnew Index Ġ= Ġreverse Index ( i . to Long (), Ġdeck . size . to Long ()) ĊĠĠĠĠĠĠĠ Ġresult [ new Index . toInt ()] Ġ= Ġdeck [ i ] ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġresult Ċ Ċ } Ċ Ċ fun Ġcut Index ( index : ĠLong , Ġn : ĠInt , Ġdeck : ĠLong , Ġiterations : ĠLong Ġ= Ġ 1 L ): ĠLong Ġ{ ĊĠĠĠ Ġval Ġi Ġ= Ġindex . to BigInteger () ĊĠĠĠ Ġval Ġcn Ġ= Ġn . to BigInteger () ĊĠĠĠ Ġval Ġd Ġ= Ġdeck . to BigInteger () ĊĠĠĠ Ġval Ġn Ġ= Ġiterations . to BigInteger () ĊĠĠĠ Ġreturn Ġ(( n Ġ* Ġ( i Ġ- Ġcn )) Ġ` %% ` Ġd ). to Long () Ċ } Ċ Ċ fun Ġcut ( deck : ĠArray < Int >, Ġn : ĠInt ): ĠArray < Int > Ġ{ ĊĠĠĠ Ġprintln (" cut Ġ$ n ") ĊĠĠĠ Ġval Ġresult Ġ= ĠArray ( deck . size ) Ġ{ Ġ- 1 Ġ} ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġdeck . size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnew Index Ġ= Ġcut Index ( i . to Long (), Ġn , Ġdeck . size . to Long (), Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġresult [ new Index . toInt ()] Ġ= Ġdeck [ i ] ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġresult Ċ } Ċ Ċ fun Ġincrement Index ( index : ĠLong , Ġinc : ĠInt , Ġdeck : ĠLong , Ġiterations : ĠLong Ġ= Ġ 1 L ): ĠLong Ġ{ ĊĠĠĠ Ġif Ġ( index Ġ== Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ 0 L ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġn Ġ= Ġiterations . to BigInteger () ĊĠĠĠ Ġval Ġi Ġ= Ġindex . to BigInteger () ĊĠĠĠ Ġval Ġc Ġ= Ġinc . to BigInteger () ĊĠĠĠ Ġval Ġd Ġ= Ġdeck . to BigInteger () ĊĠĠĠ Ġreturn Ġ( n Ġ* Ġi Ġ* Ġc Ġ` %% ` Ġd ). to Long () Ċ } Ċ Ċ fun Ġincrement ( deck : ĠArray < Int >, Ġinc : ĠInt ): ĠArray < Int > Ġ{ ĊĠĠĠ Ġprintln (" deal Ġwith Ġincrement Ġ$ inc ") ĊĠĠĠ Ġval Ġresult Ġ= ĠArray ( deck . size ) Ġ{ Ġ- 1 Ġ} ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġdeck . size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnew Index Ġ= Ġincrement Index ( i . to Long (), Ġinc , Ġdeck . size . to Long ()) ĊĠĠĠĠĠĠĠ Ġresult [ new Index . toInt ()] Ġ= Ġdeck [ i ] ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġresult Ċ } Ċ Ċ fun Ġshuffle ( input : ĠString , Ġdeck : ĠArray < Int >): ĠArray < Int > Ġ{ ĊĠĠĠ Ġval Ġinstruction Ġ= Ġparse ( input ) ĊĠĠĠ Ġreturn Ġwhen Ġ( instruction ) Ġ{ ĊĠĠĠĠĠĠĠ Ġis ĠReverse ĠĠ Ġ-> Ġreverse ( deck ) ĊĠĠĠĠĠĠĠ Ġis ĠIncrement Ġ-> Ġincrement ( deck , Ġinstruction . inc ) ĊĠĠĠĠĠĠĠ Ġis ĠCut ĠĠĠĠĠĠ Ġ-> Ġcut ( deck , Ġinstruction . n ) ĊĠĠĠĠĠĠĠ Ġelse ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ-> Ġerror (" Unknown Ġinstruction Ġ$ instruction ") ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġshuffle From ( lines : ĠList < String >, Ġdeck : ĠArray < Int >, Ġprint Intermediate : ĠBoolean Ġ= Ġfalse ): ĠArray < Int > Ġ{ ĊĠĠĠ Ġvar Ġresult Ġ= Ġdeck ĊĠĠĠ Ġlines . forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġbefore Ġ= Ġresult . toList (). toSet () ĊĠĠĠĠĠĠĠ Ġresult Ġ= Ġshuffle ( it , Ġresult ) ĊĠĠĠĠĠĠĠ Ġif Ġ( print Intermediate ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( result . join ToString ("," )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġafter Ġ= Ġresult . toList (). toSet () ĊĠĠĠĠĠĠĠ Ġrequire ( before Ġ== Ġafter ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ" Cards Ġ Ġmissing Ġ$ before Ġ-> Ġ$ after " ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġresult Ċ } Ċ Ċ data Ġclass ĠOperation ( ĊĠĠĠ Ġval Ġdeck : ĠBigInteger , ĊĠĠĠ Ġval Ġincrement : ĠBigInteger Ġ= ĠBigInteger . ONE , ĊĠĠĠ Ġval Ġoffset : ĠBigInteger Ġ= ĠBigInteger . ZERO Ċ ) Ġ{ ĊĠĠĠ Ġconstructor ( ĊĠĠĠĠĠĠĠ Ġdeck : ĠLong , ĊĠĠĠĠĠĠĠ Ġincrement : ĠLong Ġ= Ġ 1 L , ĊĠĠĠĠĠĠĠ Ġoffset : ĠLong Ġ= Ġ 0 L ĊĠĠĠ Ġ) Ġ: Ġthis ( deck . to BigInteger (), Ġincrement . to BigInteger (), Ġoffset . to BigInteger ()) ĊĊĠĠĠ Ġoperator Ġfun Ġtimes ( right : ĠOperation ): ĠOperation Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġcopy ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġincrement Ġ= Ġincrement Ġ* Ġright . increment Ġ` %% ` Ġdeck , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ(( offset Ġ* Ġright . increment Ġ` %% ` Ġdeck ) Ġ+ Ġright . offset ) Ġ` %% ` Ġdeck ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġpow ( x : ĠLong ): ĠOperation Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire ( x Ġ>= Ġ 0 L ) ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ== Ġ 0 L ĠĠĠĠĠ Ġ-> ĠOperation ( this . deck ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ% Ġ 2 L Ġ== Ġ 0 L Ġ-> Ġ( this Ġ* Ġthis ). pow ( x Ġ/ Ġ 2 L ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse ĠĠĠĠĠĠĠĠ Ġ-> Ġthis Ġ* Ġpow ( x Ġ- Ġ 1 L ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġshuffle Operations ( ĊĠĠĠ Ġlines : ĠList < String >, ĊĠĠĠ Ġdeck : ĠLong Ċ ): ĠOperation Ġ{ ĊĠĠĠ Ġvar Ġr Ġ= ĠOperation ( deck ) ĊĠĠĠ Ġlines . forEach Ġ{ Ġline Ġ-> ĊĠĠĠĠĠĠĠ Ġprintln (" Re ver sing Ġ$ line ") ĊĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġparse ( line ) ĊĠĠĠĠĠĠĠ Ġr Ġ= Ġwhen Ġ( s ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠReverse ĠĠ Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr . copy ( increment Ġ= Ġ- r . increment Ġ` %% ` Ġr . deck , Ġoffset Ġ= Ġ(- r . offset Ġ- ĠBigInteger . ONE ) Ġ` %% ` Ġr . deck ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠCut ĠĠĠĠĠĠ Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġs . n . to BigInteger () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr . copy ( offset Ġ= Ġ( r . offset Ġ- Ġn ) Ġ` %% ` Ġr . deck ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠIncrement Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġinc Ġ= Ġs . inc . to BigInteger () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr . copy ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoffset Ġ= Ġr . offset Ġ* Ġinc Ġ` %% ` Ġr . deck , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġincrement Ġ= Ġr . increment Ġ* Ġinc Ġ` %% ` Ġr . deck ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġr Ċ } Ċ Ċ fun Ġget Index ( s : ĠOperation , Ġindex : ĠLong ): ĠLong Ġ{ ĊĠĠĠ Ġval Ġx Ġ= Ġindex . to BigInteger () ĊĠĠĠ Ġreturn Ġ((( s . increment Ġ* Ġx Ġ` %% ` Ġs . deck ) Ġ+ Ġs . offset ) Ġ` %% ` Ġs . deck ). to Long () Ċ } Ċ Ċ fun Ġget Reverse Index ( s : ĠOperation , Ġindex : ĠLong ): ĠLong Ġ{ ĊĠĠĠ Ġrequire ( s . deck . is Prob able Prime ( 1 0 )) ĊĠĠĠ Ġreturn Ġget Index ( s . pow ( s . deck . to Long () Ġ- Ġ 2 L ), Ġindex ) Ċ } Ċ Ċ fun Ġapply Shuffle Reverse ( lines : ĠList < String >, Ġindex : ĠList < Long >, Ġdeck : ĠLong , Ġiterations : ĠLong Ġ= Ġ 1 L ): ĠList < Long > Ġ{ ĊĠĠĠ Ġrequire ( deck Ġ> Ġ 0 L ) Ġ{ Ġ" Deck Ġmust Ġhave Ġa Ġpositive Ġlength Ġnot Ġ$ deck " Ġ} ĊĠĠĠ Ġrequire ( iterations Ġ> Ġ 0 L ) Ġ{ Ġ" Iteration Ġmust Ġbe Ġpositive Ġnot Ġ$ iterations " Ġ} ĊĠĠĠ Ġrequire ( index . all Ġ{ Ġit Ġ>= Ġ 0 L Ġ}) Ġ{ Ġ" Index Ġmust Ġbe Ġ 0 Ġor Ġgreater Ġnot Ġ$ index " Ġ} ĊĊĠĠĠ Ġval Ġs Ġ= Ġshuffle Operations ( lines , Ġdeck ) ĊĠĠĠ Ġval Ġx Ġ= Ġs . pow ( iterations ) ĊĊĠĠĠ Ġreturn Ġindex . map Ġ{ ĊĠĠĠĠĠĠĠ Ġget Reverse Index ( x , Ġit ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġapply Shuffle ( lines : ĠList < String >, Ġindex : ĠList < Long >, Ġdeck : ĠLong , Ġiterations : ĠLong Ġ= Ġ 1 L ): ĠList < Long > Ġ{ ĊĠĠĠ Ġrequire ( deck Ġ> Ġ 0 L ) Ġ{ Ġ" Deck Ġmust Ġhave Ġa Ġpositive Ġlength Ġnot Ġ$ deck " Ġ} ĊĠĠĠ Ġrequire ( iterations Ġ> Ġ 0 L ) Ġ{ Ġ" Iteration Ġmust Ġbe Ġpositive Ġnot Ġ$ iterations " Ġ} ĊĠĠĠ Ġrequire ( index . all Ġ{ Ġit Ġ>= Ġ 0 L Ġ}) Ġ{ Ġ" Index Ġmust Ġbe Ġ 0 Ġor Ġgreater Ġnot Ġ$ index " Ġ} ĊĊĠĠĠ Ġval Ġs Ġ= Ġshuffle Operations ( lines , Ġdeck ) ĊĊĠĠĠ Ġreturn Ġindex . map Ġ{ ĊĠĠĠĠĠĠĠ Ġget Index ( s , Ġit ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġinput Ġ= ĠFile (" input . txt "). read Lines (). map Ġ{ Ġit . trim () Ġ}. filter Ġ{ Ġit . length Ġ> Ġ 0 Ġ} ĊĠĠĠ Ġrequire ( input . size Ġ== Ġ 1 0 0 ) Ġ{ Ġ" Expected Ġ 1 0 0 Ġlines Ġnot Ġ${ input . size }" Ġ} ĊĠĠĠ Ġval Ġdeck Ġ= Ġ( 0 Ġuntil Ġ 1 0 0 0 7 ). toList (). to Typed Array () ĊĠĠĠ Ġrequire ( deck . indexOf ( 2 0 1 9 ) Ġ== Ġ 2 0 1 9 ) ĊĠĠĠ Ġval Ġresult Ġ= Ġshuffle From ( input , Ġdeck ) ĊĠĠĠ Ġval Ġindex Ġ= Ġresult . indexOf ( 2 0 1 9 ) ĊĠĠĠ Ġval Ġindex 2 Ġ= Ġresult . indexOf ( 2 0 2 0 ) ĊĠĠĠ Ġprintln (" Result [ 2 0 1 9 ] Ġ= Ġ$ index , ĠResult [ 2 0 2 0 ] Ġ= Ġ$ index 2 ") ĊĠĠĠ Ġrequire ( index Ġ== Ġ 7 5 4 5 ) ĊĠĠĠ Ġrequire ( index 2 Ġ== Ġ 5 0 7 8 ) ĊĠĠĠ Ġ// ĠTesting Ġindex Ġcalculations Ġon Ġsame Ġdata ĊĠĠĠ Ġval Ġindex 3 Ġ= Ġapply Shuffle ( input , ĠlistOf ( 2 0 1 9 L , Ġ 2 0 2 0 L ), Ġdeck . size . to Long (), Ġ 1 L ) ĊĠĠĠ Ġrequire ( index 3 [ 0 ] Ġ== Ġ 7 5 4 5 L ) Ġ{ Ġ" Expected Ġ${ index 3 [ 0 ]} Ġto Ġbe Ġ 7 5 4 5 " Ġ} ĊĠĠĠ Ġrequire ( index 3 [ 1 ] Ġ== Ġ 5 0 7 8 L ) Ġ{ Ġ" Expected Ġ${ index 3 [ 1 ]} Ġto Ġbe Ġ 5 0 7 8 " Ġ} ĊĠĠĠ Ġ// ĠTesting Ġreverse Ġon Ġsame Ġdata ĊĠĠĠ Ġval Ġreverse Ġ= Ġapply Shuffle Reverse ( input , ĠlistOf ( 7 5 4 5 L , Ġ 5 0 7 8 ), Ġdeck . size . to Long (), Ġ 1 L ) ĊĠĠĠ Ġval Ġreverse Value Ġ= Ġdeck [ reverse [ 0 ]. toInt ()] ĊĠĠĠ Ġval Ġreverse Value 2 Ġ= Ġdeck [ reverse [ 1 ]. toInt ()] ĊĠĠĠ Ġrequire ( reverse . first () Ġ== Ġ 2 0 1 9 L ) Ġ{ Ġ" Expected Ġ${ reverse . first ()} Ġto Ġbe Ġ 2 0 1 9 " Ġ} ĊĊĠĠĠ Ġ// ĠLarge Ġinputs ĊĠĠĠ Ġval Ġlarge Deck Ġ= Ġ 1 1 9 _ 3 1 5 _ 7 1 7 _ 5 1 4 _ 0 4 7 L ĊĠĠĠ Ġval Ġiterations Ġ= Ġ 1 0 1 _ 7 4 1 _ 5 8 2 _ 0 7 6 _ 6 6 1 L ĊĠĠĠ Ġval Ġlarge Index Ġ= Ġapply Shuffle Reverse ( input , ĠlistOf ( 2 0 2 0 L ), Ġlarge Deck , Ġiterations ) ĊĠĠĠ Ġprintln (" Large ĠNumber Ġ= Ġ${ large Index . first () }") ĊĠĠĠ Ġrequire ( large Index . first () Ġ== Ġ 1 2 _ 7 0 6 _ 6 9 2 _ 3 7 5 _ 1 4 4 L ) Ċ } ĊĊ