package Ġcom . f eli pec sl Ċ Ċ import Ġcom . google . common . truth . Truth . assertThat Ċ import Ġorg . junit . Test Ċ Ċ class ĠOff line Bal anced Bin Pack ing Test Ġ{ ĊĠ Ġprivate Ġval Ġbin Pack ing Ġ= ĠOff line Bal anced Bin Pack ing () ĊĠ Ġprivate Ġval Ġitems Ġ= ĠlistOf ( ĊĠĠĠĠĠ Ġitem ( 5 2 2 ), Ġitem ( 7 6 5 ), Ġitem ( 2 8 8 ), Ġitem ( 1 3 1 ), ĊĠĠĠĠĠ Ġitem ( 9 8 3 ), Ġitem ( 2 3 ), Ġitem ( 9 8 7 ), Ġitem ( 3 6 1 ), ĊĠĠĠĠĠ Ġitem ( 1 2 7 ), Ġitem ( 2 9 6 ), Ġitem ( 5 2 3 ), Ġitem ( 3 6 3 ), ĊĠĠĠĠĠ Ġitem ( 8 9 9 ), Ġitem ( 9 7 7 ), Ġitem ( 7 2 0 ), Ġitem ( 8 9 6 ), ĊĠĠĠĠĠ Ġitem ( 8 3 8 ), Ġitem ( 8 6 ), Ġitem ( 7 3 6 ), Ġitem ( 4 9 6 ), ĊĠĠĠĠĠ Ġitem ( 8 5 4 ), Ġitem ( 3 5 5 ), Ġitem ( 3 1 1 ), Ġitem ( 4 9 2 ), ĊĠĠĠĠĠ Ġitem ( 9 2 ), Ġitem ( 5 3 5 ), Ġitem ( 8 4 2 ), Ġitem ( 5 7 4 ), ĊĠĠĠĠĠ Ġitem ( 9 4 9 ), Ġitem ( 4 9 3 ), Ġitem ( 9 3 8 ), Ġitem ( 9 4 2 ), ĊĠĠĠĠĠ Ġitem ( 9 6 4 ), Ġitem ( 9 3 2 ), Ġitem ( 9 5 0 ), Ġitem ( 1 1 9 ), ĊĠĠĠĠĠ Ġitem ( 5 9 9 ), Ġitem ( 6 0 4 ), Ġitem ( 8 3 8 ), Ġitem ( 7 6 7 ), ĊĠĠĠĠĠ Ġitem ( 6 6 9 ), Ġitem ( 6 8 7 ), Ġitem ( 6 8 1 ), Ġitem ( 4 6 2 ), ĊĠĠĠĠĠ Ġitem ( 4 8 6 ), Ġitem ( 6 0 5 ), Ġitem ( 6 1 ), Ġitem ( 2 1 4 ), ĊĠĠĠĠĠ Ġitem ( 6 4 3 ), Ġitem ( 9 2 2 ), Ġitem ( 5 3 7 ), Ġitem ( 6 9 2 ), ĊĠĠĠĠĠ Ġitem ( 7 0 7 ), Ġitem ( 1 4 0 ), Ġitem ( 4 3 7 ), Ġitem ( 4 8 9 ), ĊĠĠĠĠĠ Ġitem ( 9 9 8 ), Ġitem ( 1 2 2 ), Ġitem ( 2 2 2 ), Ġitem ( 5 2 9 ), ĊĠĠĠĠĠ Ġitem ( 6 8 ), Ġitem ( 6 1 3 ), Ġitem ( 7 7 4 ), Ġitem ( 6 4 2 ), ĊĠĠĠĠĠ Ġitem ( 4 4 3 ), Ġitem ( 8 3 1 ), Ġitem ( 2 8 ), Ġitem ( 6 3 9 ), ĊĠĠĠĠĠ Ġitem ( 7 0 1 ), Ġitem ( 3 4 9 ), Ġitem ( 5 3 4 ), Ġitem ( 7 6 2 ), ĊĠĠĠĠĠ Ġitem ( 9 6 5 ), Ġitem ( 6 1 4 ), Ġitem ( 6 7 7 ), Ġitem ( 1 8 7 ), ĊĠĠĠĠĠ Ġitem ( 4 6 0 ), Ġitem ( 2 2 3 ), Ġitem ( 4 9 3 ), Ġitem ( 4 0 1 ), ĊĠĠĠĠĠ Ġitem ( 8 5 8 ), Ġitem ( 7 5 7 ), Ġitem ( 2 4 0 ), Ġitem ( 6 5 6 ), ĊĠĠĠĠĠ Ġitem ( 7 7 5 ), Ġitem ( 3 5 9 ), Ġitem ( 1 4 1 ), Ġitem ( 3 6 0 ), ĊĠĠĠĠĠ Ġitem ( 8 9 3 ), Ġitem ( 4 2 1 ), Ġitem ( 1 5 ), Ġitem ( 2 3 0 ), ĊĠĠĠĠĠ Ġitem ( 9 1 4 ), Ġitem ( 7 4 1 ), Ġitem ( 8 2 1 ), Ġitem ( 2 8 9 ), ĊĠĠĠĠĠ Ġitem ( 7 1 3 ), Ġitem ( 2 3 6 ), Ġitem ( 4 9 5 ), Ġitem ( 2 5 4 ) ĊĠ Ġ) ĊĊĠ Ġ@ Test Ġfun Ġ` test Ġfirst Fit De creasing `() Ġ{ ĊĠĠĠ Ġval Ġresult Ġ= Ġbin Pack ing . first Fit De creasing ( items , Ġ 7 0 0 0 , Ġ 1 0 ) ĊĠĠĠ Ġval Ġlight est Bin Ġ= Ġresult . map ( Bin :: weight ). min () ĊĠĠĠ Ġval Ġheav iest Bin Ġ= Ġresult . map ( Bin :: weight ). max () ĊĠĠĠ Ġval Ġweights Ġ= Ġresult . map ( Bin :: weight ). sorted Descending () ĊĠĠĠ Ġval Ġcounts Ġ= Ġresult . map ( Bin :: size ). sorted Descending () ĊĠĠĠ ĠassertThat ( weights ). isEqualTo ( listOf ( 6 9 8 4 , Ġ 6 9 7 1 , Ġ 6 9 4 2 , Ġ 6 9 1 7 , Ġ 6 9 1 5 , Ġ 6 9 0 4 , Ġ 6 7 3 2 , Ġ 6 6 7 7 )) ĊĠĠĠ ĠassertThat ( counts ). isEqualTo ( listOf ( 2 3 , Ġ 1 5 , Ġ 1 4 , Ġ 1 1 , Ġ 1 0 , Ġ 9 , Ġ 9 , Ġ 9 )) ĊĠĠĠ ĠassertThat ( light est Bin ). isEqualTo ( 6 6 7 7 ) ĊĠĠĠ ĠassertThat ( he av iest Bin ). isEqualTo ( 6 9 8 4 ) ĊĠ Ġ} ĊĊĠ Ġ@ Test Ġfun Ġ` make Ġsure Ġthe Ġcomputation Ġfinishes `() Ġ{ ĊĠĠĠ Ġ// Ġall Ġitems Ġfit Ġperfectly Ġin Ġ 3 Ġbins Ġof Ġweight = 7 Ġeach ĊĠĠĠ Ġval Ġitems Ġ= ĠlistOf ( item ( 1 ), Ġitem ( 2 ), Ġitem ( 3 ), Ġitem ( 2 ), Ġitem ( 1 ), Ġitem ( 4 ), Ġitem ( 3 ), Ġitem ( 1 ), ĊĠĠĠĠĠĠĠ Ġitem ( 2 ), Ġitem ( 2 )) ĊĠĠĠ Ġval Ġresult Ġ= Ġbin Pack ing . first Fit De creasing ( items , Ġ 1 0 , Ġ 3 ) ĊĠĠĠ ĠassertThat ( result . size ). isEqualTo ( 3 ) ĊĠĠĠ ĠassertThat ( result ). contains Exactly ( ĊĠĠĠĠĠĠĠ ĠlistOf ( item ( 4 ), Ġitem ( 2 ), Ġitem ( 1 )), ĊĠĠĠĠĠĠĠ ĠlistOf ( item ( 3 ), Ġitem ( 3 ), Ġitem ( 1 )), ĊĠĠĠĠĠĠĠ ĠlistOf ( item ( 2 ), Ġitem ( 2 ), Ġitem ( 2 ), Ġitem ( 1 ))) ĊĠ Ġ} ĊĊĠ Ġ@ Test Ġfun Ġ` manual Ġtest `() Ġ{ ĊĠĠĠ Ġrun (" first Ġfit Ġ 1 0 0 ", Ġbin Pack ing :: first Fit De creasing ) Ċ // ĠĠĠ Ġrun (" best Ġfit Ġ 1 0 0 ", Ġbin Pack ing :: best Fit De creasing , Ġ 1 0 , Ġ 1 0 0 ) ĊĠ Ġ} ĊĊĠ Ġ@ Test Ġfun Ġ` test Ġbest Fit De creasing `() Ġ{ ĊĠĠĠ Ġval Ġresult Ġ= Ġbin Pack ing . best Fit De creasing ( items , Ġ 7 0 0 0 , Ġ 1 0 ) ĊĠĠĠ Ġval Ġlight est Bin Ġ= Ġresult . map Ġ{ Ġit . weight Ġ}. min () ĊĠĠĠ Ġval Ġheav iest Bin Ġ= Ġresult . map Ġ{ Ġit . weight Ġ}. max () ĊĠĠĠ Ġval Ġweights Ġ= Ġresult . map Ġ{ Ġit . weight Ġ}. sorted Descending () ĊĠĠĠ Ġval Ġcounts Ġ= Ġresult . map Ġ{ Ġit . size Ġ}. sorted Descending () ĊĠĠĠ ĠassertThat ( weights ). isEqualTo ( ĊĠĠĠĠĠĠĠ ĠlistOf ( 6 2 8 2 , Ġ 6 2 7 0 , Ġ 5 7 1 8 , Ġ 5 5 4 6 , Ġ 5 4 4 2 , Ġ 5 3 6 7 , Ġ 5 3 3 5 , Ġ 5 1 9 0 , Ġ 4 9 9 5 , Ġ 4 8 9 7 )) ĊĠĠĠ ĠassertThat ( counts ). isEqualTo ( listOf ( 1 1 , Ġ 1 1 , Ġ 1 1 , Ġ 1 1 , Ġ 1 0 , Ġ 1 0 , Ġ 9 , Ġ 9 , Ġ 9 , Ġ 9 )) ĊĠĠĠ ĠassertThat ( light est Bin ). isEqualTo ( 4 8 9 7 ) ĊĠĠĠ ĠassertThat ( he av iest Bin ). isEqualTo ( 6 2 8 2 ) ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġrun ( ĊĠĠĠĠĠ Ġlabel : ĠString , ĊĠĠĠĠĠ Ġfunc : Ġ( List < Item >, ĠInt , ĠInt ) Ġ-> ĠList < Bin >, ĊĠĠĠĠĠ Ġmax Bin Size : ĠInt Ġ= ĠInt . MAX _ VALUE , ĊĠĠĠĠĠ Ġmax Bins : ĠInt Ġ= ĠInt . MAX _ VALUE ĊĠ Ġ) Ġ{ ĊĠĠĠ Ġprintln (" ------------------ \ n $ label ") ĊĠĠĠ Ġval Ġresult Ġ= Ġfunc ( items , Ġmax Bin Size , Ġmax Bins ) ĊĠĠĠ Ġprint Groups ( result ) ĊĠĠĠ Ġval Ġmin Ġ= Ġresult . map Ġ{ Ġit . weight Ġ}. min () !! ĊĠĠĠ Ġval Ġmax Ġ= Ġresult . map Ġ{ Ġit . weight Ġ}. max () !! ĊĠĠĠ Ġprintln (" Light est Ġbin =$ min , ĠHe av iest Ġbin =$ max ") ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġprint Groups ( item Groups : ĠList < List < Item >>) Ġ{ ĊĠĠĠ Ġitem Groups . sorted By Descending Ġ{ Ġit . sum By ( Item :: weight ) Ġ}. forEach Indexed Ġ{ Ġi , Ġit Ġ-> ĊĠĠĠĠĠ Ġval Ġtotal Weight Ġ= Ġit . sum By ( Item :: weight ) ĊĠĠĠĠĠ Ġval Ġtotal Items Ġ= Ġit . size ĊĠĠĠĠĠ Ġval Ġweight Per Task Ġ= Ġif Ġ( total Items Ġ> Ġ 0 ) Ġtotal Weight Ġ/ Ġtotal Items Ġelse Ġ 0 ĊĠĠĠĠĠ Ġprintln ( ĊĠĠĠĠĠĠĠĠĠ Ġ" Bin =$ i , Ġtotal Ġweight =$ total Weight , Ġtotal Ġitems =$ total Items , Ġweight / item =$ weight Per Task ") ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġdata Ġclass ĠTest Item ( val Ġw : ĠInt ) Ġ: ĠItem Ġ{ ĊĠĠĠ Ġoverride Ġval Ġweight : ĠInt ĊĠĠĠĠĠ Ġget () Ġ= Ġw ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġitem ( weight : ĠInt ) Ġ= ĠTest Item ( weight ) Ċ } Ċ