package Ġcom . github . fer in agy . ad vent Of Code . a oc 2 0 1 5 Ċ Ċ import Ġjava . util .* Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġprintln (" Part 1 :") ĊĠĠĠ Ġprintln ( part 1 ( test Input 1 )) ĊĠĠĠ Ġprintln ( part 1 ( input )) ĊĊĠĠĠ Ġprintln () ĊĠĠĠ Ġprintln (" Part 2 :") ĊĠĠĠ Ġprintln ( part 2 ( test Input 1 )) ĊĠĠĠ Ġprintln ( part 2 ( input )) Ċ } Ċ Ċ private Ġfun Ġpart 1 ( input : ĠString ): ĠLong Ġ{ ĊĠĠĠ Ġreturn Ġsolve ( input , Ġ 3 ) Ċ } Ċ Ċ private Ġfun Ġpart 2 ( input : ĠString ): ĠLong Ġ{ ĊĠĠĠ Ġreturn Ġsolve ( input , Ġ 4 ) Ċ } Ċ Ċ private Ġfun Ġsolve ( input : ĠString , Ġgroup Count : ĠInt ): ĠLong Ġ{ ĊĠĠĠ Ġval Ġpackages Ġ= Ġinput . lines (). map Ġ{ Ġit . to Long () Ġ}. sorted Descending () ĊĠĠĠ Ġval Ġsum Ġ= Ġpackages . sum () ĊĠĠĠ Ġrequire ( sum Ġ% Ġgroup Count Ġ== Ġ 0 L ) ĊĠĠĠ Ġval Ġtarget Ġ= Ġsum Ġ/ Ġgroup Count ĊĊĠĠĠ Ġval Ġsequence Ġ= Ġpackages . groups With Sum ( target ) ĊĠĠĠ Ġval Ġfirst Valid Ġ= Ġsequence . first Ġ{ Ġit . isValid ( packages , Ġtarget ) Ġ} ĊĠĠĠ Ġval Ġall Candidates Ġ= Ġsequence . take While Ġ{ Ġit . size Ġ<= Ġfirst Valid . size Ġ}. drop While Ġ{ Ġit . size Ġ< Ġfirst Valid . size Ġ} ĊĊĠĠĠ Ġreturn Ġall Candidates . min Of Ġ{ Ġit . product () Ġ} Ċ } Ċ Ċ private Ġfun ĠList < Long >. product (): ĠLong Ġ= Ġreduce Ġ{ Ġacc , Ġl Ġ-> Ġacc Ġ* Ġl Ġ} Ċ Ċ @ Opt In ( Experimental Std lib Api :: class ) Ċ private Ġfun ĠList < Long >. groups With Sum ( target : ĠLong ): ĠSequence < List < Long >> Ġ= Ġsequence Ġ{ ĊĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList < Pair < List < Long >, ĠList < Long >> >() ĊĠĠĠ Ġqueue . add Last ( emptyList < Long >() Ġto Ġthis @ groups With Sum ) ĊĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġ( next , Ġremaining ) Ġ= Ġqueue . remove First () ĊĊĠĠĠĠĠĠĠ Ġval Ġsum Ġ= Ġnext . sum () ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġremaining . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( target Ġ< Ġsum Ġ+ Ġremaining [ i ]) Ġcontinue ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Ġ= Ġnext Ġ+ Ġremaining [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( target Ġ== Ġsum Ġ+ Ġremaining [ i ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġyield ( new ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġqueue Ġ+= Ġnew Ġto Ġremaining . sub List ( i Ġ+ Ġ 1 , Ġremaining . size ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġfun ĠList < Long >. isValid ( all : ĠList < Long >, Ġtarget : ĠLong ): ĠBoolean Ġ{ ĊĠĠĠ Ġval Ġrest Ġ= Ġall Ġ- Ġthis . toSet () ĊĠĠĠ Ġreturn Ġrest . groups With Sum ( target ). any () Ċ } Ċ Ċ private Ġval Ġtest Input 1 Ġ= Ġ""" 1 ĊĠĠĠ Ġ| 2 ĊĠĠĠ Ġ| 3 ĊĠĠĠ Ġ| 4 ĊĠĠĠ Ġ| 5 ĊĠĠĠ Ġ| 7 ĊĠĠĠ Ġ| 8 ĊĠĠĠ Ġ| 9 ĊĠĠĠ Ġ| 1 0 ĊĠĠĠ Ġ| 1 1 Ċ """. trim Margin () Ċ Ċ private Ġconst Ġval Ġinput Ġ= Ġ""" 1 Ċ 2 Ċ 3 Ċ 5 Ċ 7 Ċ 1 3 Ċ 1 7 Ċ 1 9 Ċ 2 3 Ċ 2 9 Ċ 3 1 Ċ 3 7 Ċ 4 1 Ċ 4 3 Ċ 5 3 Ċ 5 9 Ċ 6 1 Ċ 6 7 Ċ 7 1 Ċ 7 3 Ċ 7 9 Ċ 8 3 Ċ 8 9 Ċ 9 7 Ċ 1 0 1 Ċ 1 0 3 Ċ 1 0 7 Ċ 1 0 9 Ċ 1 1 3 """ Ċ