Greg Nice problem: I wasted my whole day on it :-)
I was explaining my plan for a solution to a colleague who is a computer scientist, he pointed out that I was trying to re-invent the wheel known as dynamic programming. here is my code, apparently it is called "bottom up dynamic programming". It runs pretty quickly, and returns (what I hope is :-) the optimal sum of squares and the cut-points. function(X=bom3$Verses,days=128){ # find optimal BOM reading schedule for Greg Snow # minimize variance of quantity to read per day over 128 days # N = length(X) Nm1 = N-1 SSQ<- matrix(NA,nrow=days,ncol=N) Cuts <- list() # # SSQ[i,j]: the ssqs about the overall mean for the optimal partition # for i days on the chapters 1 to j # M = sum(X)/days CS = cumsum(X) SSQ[1,]= (CS-M)^2 Cuts[[1]]= as.list(1:N) # for(m in 2:days){ Cuts[[m]]=list() #for(i in 1:(m-1)) Cuts[[m]][[i]] = Cuts[[m-1]][[i]] for(n in m:N){ CS = cumsum(X[n:1])[n:1] SSQ1 = (CS-M)^2 j = (m-1):(n-1) TS = SSQ[m-1,j]+(SSQ1[j+1]) SSQ[m,n] = min(TS) k = min(which((min(TS)== TS)))+m-1 Cuts[[m]][[n]] = c(Cuts[[m-1]][[k-1]],n) } } list(SSQ=SSQ[days,N],Cuts=Cuts[[days]][[N]]) } $SSQ [1] 11241.05 $Cuts [1] 2 4 7 9 11 13 15 16 17 19 21 23 25 27 30 31 34 37 [19] 39 41 44 46 48 50 53 56 59 60 62 64 66 68 70 73 75 77 [37] 78 80 82 84 86 88 89 91 92 94 95 96 97 99 100 103 105 106 [55] 108 110 112 113 115 117 119 121 124 125 126 127 129 131 132 135 137 138 [73] 140 141 142 144 145 146 148 150 151 152 154 156 157 160 162 163 164 166 [91] 167 169 171 173 175 177 179 181 183 185 186 188 190 192 193 194 196 199 [109] 201 204 205 207 209 211 213 214 215 217 220 222 223 225 226 228 234 236 [127] 238 239 On Tue, Jan 12, 2010 at 11:33:36AM -0700, Greg Snow wrote: > I have a challenge that I want to share with the group. > > This is not homework (but I may assign it as such if I teach the appropriate > class again) and I have found one solution, so don't need anything urgent. > This is more for fun to see if others can find a better solution than I did. > > The challenge: > > I want to read a book in a given number of days. I want to read an integer > number of chapters each day (there are more chapters than days), no stopping > part way through a chapter, and at least 1 chapter each day. The chapters > are very non uniform in length (some very short, a few very long, many in > between) so I would like to come up with a reading schedule that minimizes > the variance of the length of the days readings (read multiple short chapters > on the same day, long chapters are the only one read that day). I also want > to read through the book in order (no skipping ahead to combine short > chapters that are not naturally next to each other. > > My thought was that the optim function with method="SANN" would be an > appropriate approach, but my first couple of tries did not give very good > results. I have since come up with an optim with SANN solution that gives > what I consider good results (but I accept that better is possible). > > Below is a data frame with the lengths of the chapters for the book that > originally sparked the challenge for me (but the general idea should work for > any book). Each row represents a chapter (in order) with 3 different > measures of the length of the chapter. > > For this challenge I want to read the book in 128 days (there are 239 > chapters). > > I will post my solutions in a few days, but I want to wait so that my > direction does not influence people from trying other approaches (if there is > something better than optim, that is fine). > > Good luck for anyone interested in the challenge, > > The data frame: > > bom3 <- structure(list(Chapter = structure(1:239, .Label = c("1 Nephi 1", > "1 Nephi 2", "1 Nephi 3", "1 Nephi 4", "1 Nephi 5", "1 Nephi 6", > "1 Nephi 7", "1 Nephi 8", "1 Nephi 9", "1 Nephi 10", "1 Nephi 11", > "1 Nephi 12", "1 Nephi 13", "1 Nephi 14", "1 Nephi 15", "1 Nephi 16", > "1 Nephi 17", "1 Nephi 18", "1 Nephi 19", "1 Nephi 20", "1 Nephi 21", > "1 Nephi 22", "2 Nephi 1", "2 Nephi 2", "2 Nephi 3", "2 Nephi 4", > "2 Nephi 5", "2 Nephi 6", "2 Nephi 7", "2 Nephi 8", "2 Nephi 9", > "2 Nephi 10", "2 Nephi 11", "2 Nephi 12", "2 Nephi 13", "2 Nephi 14", > "2 Nephi 15", "2 Nephi 16", "2 Nephi 17", "2 Nephi 18", "2 Nephi 19", > "2 Nephi 20", "2 Nephi 21", "2 Nephi 22", "2 Nephi 23", "2 Nephi 24", > "2 Nephi 25", "2 Nephi 26", "2 Nephi 27", "2 Nephi 28", "2 Nephi 29", > "2 Nephi 30", "2 Nephi 31", "2 Nephi 32", "2 Nephi 33", "Jacob 1", > "Jacob 2", "Jacob 3", "Jacob 4", "Jacob 5", "Jacob 6", "Jacob 7", > "Enos 1", "Jarom 1", "Omni 1", "Words of Mormon 1", "Mosiah 1", > "Mosiah 2", "Mosiah 3", "Mosiah 4", "Mosiah 5", "Mosiah 6", "Mosiah 7", > "Mosiah 8", "Mosiah 9", "Mosiah 10", "Mosiah 11", "Mosiah 12", > "Mosiah 13", "Mosiah 14", "Mosiah 15", "Mosiah 16", "Mosiah 17", > "Mosiah 18", "Mosiah 19", "Mosiah 20", "Mosiah 21", "Mosiah 22", > "Mosiah 23", "Mosiah 24", "Mosiah 25", "Mosiah 26", "Mosiah 27", > "Mosiah 28", "Mosiah 29", "Alma 1", "Alma 2", "Alma 3", "Alma 4", > "Alma 5", "Alma 6", "Alma 7", "Alma 8", "Alma 9", "Alma 10", > "Alma 11", "Alma 12", "Alma 13", "Alma 14", "Alma 15", "Alma 16", > "Alma 17", "Alma 18", "Alma 19", "Alma 20", "Alma 21", "Alma 22", > "Alma 23", "Alma 24", "Alma 25", "Alma 26", "Alma 27", "Alma 28", > "Alma 29", "Alma 30", "Alma 31", "Alma 32", "Alma 33", "Alma 34", > "Alma 35", "Alma 36", "Alma 37", "Alma 38", "Alma 39", "Alma 40", > "Alma 41", "Alma 42", "Alma 43", "Alma 44", "Alma 45", "Alma 46", > "Alma 47", "Alma 48", "Alma 49", "Alma 50", "Alma 51", "Alma 52", > "Alma 53", "Alma 54", "Alma 55", "Alma 56", "Alma 57", "Alma 58", > "Alma 59", "Alma 60", "Alma 61", "Alma 62", "Alma 63", "Helaman 1", > "Helaman 2", "Helaman 3", "Helaman 4", "Helaman 5", "Helaman 6", > "Helaman 7", "Helaman 8", "Helaman 9", "Helaman 10", "Helaman 11", > "Helaman 12", "Helaman 13", "Helaman 14", "Helaman 15", "Helaman 16", > "3 Nephi 1", "3 Nephi 2", "3 Nephi 3", "3 Nephi 4", "3 Nephi 5", > "3 Nephi 6", "3 Nephi 7", "3 Nephi 8", "3 Nephi 9", "3 Nephi 10", > "3 Nephi 11", "3 Nephi 12", "3 Nephi 13", "3 Nephi 14", "3 Nephi 15", > "3 Nephi 16", "3 Nephi 17", "3 Nephi 18", "3 Nephi 19", "3 Nephi 20", > "3 Nephi 21", "3 Nephi 22", "3 Nephi 23", "3 Nephi 24", "3 Nephi 25", > "3 Nephi 26", "3 Nephi 27", "3 Nephi 28", "3 Nephi 29", "3 Nephi 30", > "4 Nephi 1", "Mormon 1", "Mormon 2", "Mormon 3", "Mormon 4", > "Mormon 5", "Mormon 6", "Mormon 7", "Mormon 8", "Mormon 9", "Ether 1", > "Ether 2", "Ether 3", "Ether 4", "Ether 5", "Ether 6", "Ether 7", > "Ether 8", "Ether 9", "Ether 10", "Ether 11", "Ether 12", "Ether 13", > "Ether 14", "Ether 15", "Moroni 1", "Moroni 2", "Moroni 3", "Moroni 4", > "Moroni 5", "Moroni 6", "Moroni 7", "Moroni 8", "Moroni 9", "Moroni 10" > ), class = "factor"), Words = c(908L, 879L, 1067L, 1262L, 761L, > 202L, 992L, 1221L, 259L, 924L, 1315L, 860L, 1899L, 1284L, 1488L, > 1618L, 2523L, 1217L, 1292L, 698L, 945L, 1506L, 1543L, 1460L, > 1170L, 1300L, 1169L, 895L, 405L, 812L, 2388L, 966L, 338L, 647L, > 587L, 203L, 857L, 370L, 687L, 570L, 587L, 928L, 520L, 134L, 587L, > 891L, 1699L, 1483L, 1461L, 1240L, 804L, 708L, 988L, 426L, 647L, > 719L, 1365L, 619L, 929L, 3758L, 511L, 1242L, 1160L, 734L, 1398L, > 857L, 966L, 2112L, 1117L, 1605L, 740L, 309L, 1555L, 938L, 864L, > 957L, 1271L, 1291L, 1073L, 391L, 1056L, 560L, 650L, 1382L, 978L, > 963L, 1328L, 620L, 1186L, 954L, 837L, 1200L, 1601L, 812L, 1879L, > 1496L, 1433L, 1016L, 1035L, 2787L, 390L, 1443L, 1231L, 1511L, > 1442L, 1466L, 1858L, 1347L, 1526L, 711L, 1010L, 1848L, 1623L, > 1701L, 1279L, 955L, 1871L, 764L, 1509L, 752L, 1665L, 1260L, 575L, > 708L, 2666L, 1478L, 1837L, 855L, 1576L, 699L, 1229L, 2027L, 651L, > 793L, 1153L, 701L, 1229L, 2221L, 1243L, 911L, 1809L, 1572L, 1073L, > 1345L, 1734L, 1682L, 1757L, 1085L, 988L, 1218L, 2177L, 1517L, > 1748L, 489L, 1777L, 854L, 2220L, 593L, 1418L, 599L, 1527L, 1076L, > 2084L, 1797L, 1142L, 1210L, 1480L, 720L, 1561L, 873L, 1855L, > 1241L, 824L, 1025L, 1340L, 769L, 1353L, 1518L, 931L, 1200L, 1132L, > 871L, 965L, 807L, 1434L, 1294L, 834L, 628L, 731L, 913L, 879L, > 1344L, 1233L, 1538L, 1155L, 507L, 415L, 620L, 183L, 793L, 1269L, > 1457L, 394L, 130L, 1949L, 706L, 1262L, 939L, 822L, 1067L, 914L, > 454L, 1710L, 1510L, 901L, 1370L, 1253L, 892L, 226L, 1048L, 899L, > 1231L, 1424L, 1415L, 762L, 1536L, 1219L, 1132L, 1314L, 147L, > 119L, 120L, 153L, 91L, 335L, 1929L, 1064L, 1012L, 1149L), Letters = c(3746L, > 3640L, 4295L, 4968L, 3202L, 777L, 3941L, 4769L, 1075L, 3829L, > 5159L, 3527L, 7874L, 5236L, 6149L, 6555L, 10180L, 4960L, 5399L, > 2767L, 3758L, 6275L, 6391L, 6151L, 4685L, 5267L, 4767L, 3780L, > 1574L, 3261L, 9985L, 4106L, 1332L, 2557L, 2454L, 810L, 3540L, > 1406L, 2668L, 2304L, 2474L, 3715L, 2090L, 533L, 2442L, 3587L, > 7294L, 6363L, 5809L, 4997L, 3197L, 2941L, 4065L, 1743L, 2539L, > 3149L, 5815L, 2765L, 4027L, 15366L, 2091L, 4988L, 4730L, 3149L, > 5906L, 3704L, 4188L, 8675L, 4771L, 6586L, 2965L, 1313L, 6326L, > 3948L, 3489L, 3942L, 5205L, 5309L, 4300L, 1574L, 4559L, 2393L, > 2655L, 5755L, 4070L, 4027L, 5649L, 2651L, 4978L, 3970L, 3610L, > 5112L, 6733L, 3513L, 7990L, 6356L, 6179L, 4340L, 4432L, 11260L, > 1657L, 5913L, 5033L, 6274L, 5835L, 5865L, 7802L, 5776L, 6295L, > 3034L, 4383L, 7842L, 6659L, 6905L, 5104L, 4162L, 7733L, 3321L, > 6241L, 3212L, 6840L, 5294L, 2471L, 2748L, 10762L, 6269L, 7479L, > 3416L, 6477L, 3043L, 4719L, 8764L, 2494L, 3168L, 4790L, 2983L, > 5129L, 9795L, 5043L, 3913L, 7635L, 6693L, 4669L, 5968L, 7508L, > 7271L, 7543L, 4730L, 4095L, 5152L, 9129L, 6395L, 7357L, 2166L, > 7512L, 3544L, 9554L, 2505L, 6171L, 2568L, 6542L, 4781L, 8655L, > 7721L, 4751L, 5134L, 6032L, 3013L, 6536L, 3504L, 7527L, 5106L, > 3607L, 4247L, 5524L, 3404L, 5947L, 6506L, 3891L, 5256L, 4944L, > 3700L, 4006L, 3392L, 5732L, 5185L, 3402L, 2451L, 2962L, 3679L, > 3550L, 5429L, 5083L, 6354L, 4659L, 2155L, 1754L, 2496L, 721L, > 3326L, 4917L, 5856L, 1589L, 564L, 8300L, 2987L, 5317L, 3820L, > 3595L, 4483L, 3664L, 1805L, 6931L, 6225L, 3508L, 5481L, 5007L, > 3623L, 891L, 4265L, 3746L, 5041L, 5823L, 5726L, 3238L, 6443L, > 5053L, 4664L, 5370L, 614L, 459L, 491L, 629L, 351L, 1457L, 7812L, > 4677L, 4305L, 4603L), Verses = c(20, 24, 31, 38, 22, 6, 22, 38, > 6, 22, 36, 23, 42, 30, 36, 39, 55, 25, 24, 22, 26, 31, 32, 30, > 25, 35, 34, 18, 11, 25, 54, 25, 8, 22, 26, 6, 30, 13, 25, 22, > 21, 34, 16, 6, 22, 32, 30, 33, 35, 32, 14, 18, 21, 9, 15, 19, > 35, 14, 18, 77, 13, 27, 27, 15, 30, 18, 18, 41, 27, 30, 15, 7, > 33, 21, 19, 22, 29, 37, 35, 12, 31, 15, 20, 35, 29, 26, 36, 16, > 39, 25, 24, 39, 37, 20, 47, 33, 38, 27, 20, 62, 8, 27, 32, 34, > 32, 46, 37, 31, 29, 19, 21, 39, 43, 36, 30, 23, 35, 18, 30, 17, > 37, 30, 14, 17, 60, 38, 43, 23, 41, 16, 30, 47, 15, 19, 26, 15, > 31, 54, 24, 24, 41, 36, 25, 30, 40, 37, 40, 23, 24, 35, 57, 36, > 41, 13, 36, 21, 52, 17, 34, 14, 37, 26, 52, 41, 29, 28, 41, 19, > 38, 26, 39, 31, 17, 25, 30, 19, 26, 33, 26, 30, 26, 25, 22, 19, > 41, 48, 34, 27, 24, 20, 25, 39, 36, 46, 29, 17, 14, 18, 6, 21, > 33, 39, 9, 2, 49, 19, 29, 22, 23, 24, 22, 10, 41, 37, 43, 25, > 28, 19, 6, 30, 27, 26, 35, 34, 23, 41, 31, 31, 34, 4, 3, 4, 3, > 2, 9, 48, 30, 26, 34)), .Names = c("Chapter", "Words", "Letters", > "Verses"), row.names = c(NA, -239L), class = "data.frame") > > > -- > Gregory (Greg) L. Snow Ph.D. > Statistical Data Center > Intermountain Healthcare > greg.s...@imail.org > 801.408.8111 > > ______________________________________________ > R-help@r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. > ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.