package Ġus . j wf . a oc 2 0 1 5 Ċ Ċ import Ġjava . io . Reader Ċ import Ġjava . util . LinkedList Ċ import Ġkotlinx . coroutines . flow . map Ċ import Ġkotlinx . coroutines . flow . toList Ċ import Ġus . j wf . a oc . Day Ċ import Ġus . j wf . a oc . toInt Flow Ċ Ċ /** Ċ Ġ* ĠA o C Ġ 2 0 1 5 Ġ- ĠDay Ġ 2 4 Ċ Ġ*/ Ċ class ĠDay 2 4 Hang s InThe Balance Ġ: ĠDay < UL ong , ĠU Long > Ġ{ ĊĠ Ġoverride Ġsuspend Ġfun Ġexecute Part 1 ( input : ĠReader ): ĠU Long Ġ{ ĊĠĠĠ Ġval Ġweights Ġ= Ġinput . toInt Flow (). map Ġ{ Ġit . to UL ong () Ġ}. toList () ĊĠĠĠ Ġval Ġtotal Ġ= Ġweights . sum () ĊĠĠĠ Ġval Ġtarget Ġ= Ġtotal Ġ/ Ġ 3 u L ĊĊĠĠĠ Ġval Ġstart Ġ= ĠArrange ment ( other Group Members Ġ= Ġweights , Ġother Group Sum Ġ= Ġtotal ) ĊĊĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList < Arrange ment >(). apply Ġ{ Ġadd ( start ) Ġ} ĊĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of < Arrange ment >() ĊĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠ Ġval Ġnext Ġ= Ġqueue . poll () ĊĠĠĠĠĠ Ġif Ġ( next . is Done ( target )) Ġreturn Ġnext . group 1 Product ĊĊĠĠĠĠĠ Ġnext . next Options ( target ) ĊĠĠĠĠĠĠĠ Ġ. forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( it Ġin Ġvisited ) Ġreturn @ forEach ĊĠĠĠĠĠĠĠĠĠ Ġqueue . add ( it ) ĊĠĠĠĠĠĠĠĠĠ Ġvisited . add ( it ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġ 0 u L ĊĠ Ġ} ĊĊĠ Ġoverride Ġsuspend Ġfun Ġexecute Part 2 ( input : ĠReader ): ĠU Long Ġ{ ĊĠĠĠ Ġval Ġweights Ġ= Ġinput . toInt Flow (). map Ġ{ Ġit . to UL ong () Ġ}. toList () ĊĠĠĠ Ġval Ġtotal Ġ= Ġweights . sum () ĊĠĠĠ Ġval Ġtarget Ġ= Ġtotal Ġ/ Ġ 4 u L ĊĊĠĠĠ Ġval Ġstart Ġ= ĠArrange ment ( other Group Members Ġ= Ġweights , Ġother Group Sum Ġ= Ġtotal ) ĊĊĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList < Arrange ment >(). apply Ġ{ Ġadd ( start ) Ġ} ĊĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of < Arrange ment >() ĊĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠ Ġval Ġnext Ġ= Ġqueue . poll () ĊĠĠĠĠĠ Ġif Ġ( next . is Done Part 2 ( target )) Ġreturn Ġnext . group 1 Product ĊĊĠĠĠĠĠ Ġnext . next Options ( target ) ĊĠĠĠĠĠĠĠ Ġ. forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( it Ġin Ġvisited ) Ġreturn @ forEach ĊĠĠĠĠĠĠĠĠĠ Ġqueue . add ( it ) ĊĠĠĠĠĠĠĠĠĠ Ġvisited . add ( it ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġ 0 u L ĊĠ Ġ} ĊĊĠ Ġdata Ġclass ĠArrange ment ( ĊĠĠĠ Ġval Ġgroup 1 Sum : ĠU Long Ġ= Ġ 0 u L , ĊĠĠĠ Ġval Ġgroup 1 Product : ĠU Long Ġ= Ġ 1 u L , ĊĠĠĠ Ġval Ġother Group Members : ĠList < UL ong >, ĊĠĠĠ Ġval Ġother Group Sum : ĠU Long , ĊĠ Ġ) Ġ{ ĊĠĠĠ Ġfun Ġnext Options ( target : ĠU Long ): ĠList < Arrange ment > Ġ{ ĊĠĠĠĠĠ Ġreturn Ġother Group Members . map NotNull Ġ{ Ġmember Ġ-> ĊĠĠĠĠĠĠĠ Ġif Ġ( group 1 Sum Ġ+ Ġmember Ġ> Ġtarget ) Ġreturn @ map NotNull Ġnull ĊĠĠĠĠĠĠĠ ĠArrange ment ( ĊĠĠĠĠĠĠĠĠĠ Ġgroup 1 Sum Ġ+ Ġmember , ĊĠĠĠĠĠĠĠĠĠ Ġgroup 1 Product Ġ* Ġmember , ĊĠĠĠĠĠĠĠĠĠ Ġother Group Members Ġ- Ġmember , ĊĠĠĠĠĠĠĠĠĠ Ġother Group Sum Ġ- Ġmember ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġis Done ( group Size : ĠU Long ): ĠBoolean Ġ{ ĊĠĠĠĠĠ Ġif Ġ( group 1 Sum Ġ!= Ġgroup Size Ġ|| Ġother Group Members . sum () Ġ!= Ġgroup Size Ġ* Ġ 2 u L ) Ġreturn Ġfalse ĊĊĠĠĠĠĠ Ġ// ĠCheck Ġthat Ġother Group Members Ġcan Ġbe Ġsplit Ġinto Ġeven Ġweights . ĊĠĠĠĠĠ Ġfun Ġcan Split ( remaining Total : ĠU Long , Ġremaining Options : ĠSet < UL ong >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( remaining Total Ġ== Ġ 0 u L ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġval Ġpossible Options Ġ= Ġremaining Options . filter Ġ{ Ġit Ġ<= Ġremaining Total Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( possible Options . isEmpty ()) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġreturn Ġpossible Options . any Ġ{ Ġcan Split ( remaining Total Ġ- Ġit , Ġremaining Options Ġ- Ġit ) Ġ} ĊĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠ Ġ// Ġonly Ġworks Ġif Ġthey 're Ġall Ġdifferent , Ġif Ġthey Ġwere Ġthe Ġsame Ġwe 'd Ġneed Ġa Ġmap Ġof Ġcounts . ĊĠĠĠĠĠ Ġreturn Ġcan Split ( group Size , Ġother Group Members . toSet ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġis Done Part 2 ( group Size : ĠU Long ): ĠBoolean Ġ{ ĊĠĠĠĠĠ Ġif Ġ( group 1 Sum Ġ!= Ġgroup Size Ġ|| Ġother Group Members . sum () Ġ!= Ġgroup Size Ġ* Ġ 3 u L ) Ġreturn Ġfalse ĊĊĠĠĠĠĠ Ġ// ĠCheck Ġthat Ġother Group Members Ġcan Ġbe Ġsplit Ġinto Ġeven Ġweights . ĊĠĠĠĠĠ Ġval Ġcache Ġ= Ġmutable Map Of < Triple < UL ong , ĠU Long , ĠSet < UL ong >>, ĠBoolean >() ĊĠĠĠĠĠ Ġfun Ġcan Split ( remaining In A : ĠU Long , Ġremaining In B : ĠU Long , Ġremaining Options : ĠSet < UL ong >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġargs Ġ= ĠTrip le ( remaining In A , Ġremaining In B , Ġremaining Options ) ĊĠĠĠĠĠĠĠ Ġcache [ args ]?. let Ġ{ Ġreturn Ġit Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( remaining In A Ġ== Ġ 0 u L Ġ&& Ġremaining In B Ġ== Ġ 0 u L ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġval Ġpossible A Options Ġ= Ġremaining Options . filter Ġ{ Ġit Ġ<= Ġremaining In A Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġpossible B Options Ġ= Ġremaining Options . filter Ġ{ Ġit Ġ<= Ġremaining In B Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġ( possible A Options . any Ġ{ Ġcan Split ( remaining In A Ġ- Ġit , Ġremaining In B , Ġremaining Options Ġ- Ġit ) Ġ} Ġ|| ĊĠĠĠĠĠĠĠĠĠ Ġpossible B Options . any Ġ{ Ġcan Split ( remaining In A , Ġremaining In B Ġ- Ġit , Ġremaining Options Ġ- Ġit ) Ġ}) ĊĠĠĠĠĠĠĠĠĠ Ġ. also Ġ{ Ġcache [ args ] Ġ= Ġit Ġ} ĊĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠ Ġ// Ġonly Ġworks Ġif Ġthey 're Ġall Ġdifferent , Ġif Ġthey Ġwere Ġthe Ġsame Ġwe 'd Ġneed Ġa Ġmap Ġof Ġcounts . ĊĠĠĠĠĠ Ġreturn Ġcan Split ( group Size , Ġgroup Size , Ġother Group Members . toSet ()) ĊĠĠĠ Ġ} ĊĠ Ġ} Ċ } Ċ