/* POTM ENTRY: DuckAndCover */ /* Your Name: The Happy Hacker */ /* Your email: guy@ulysses.att.com */ /* DuckAndCover.c The Happy Hacker, 12-97 I'd like to use the pseudonym "The Happy Hacker," if that's OK with you. Maybe later I'll change my mind. The data here was cribbed from the La Jolla covering repository (see URL http://sdcc12.ucsd.edu/~xm3dg/cover.html) I got every covering they have on file with v=8..32, k=7, t=3. and encoded them into rawblock, with counts in nblocks. These are the best known (according to the repository!) coverings of all triples from 1..v using sets of size seven. I've encoded these sets into the bits of unsigned longs in the obvious way to save a little space. Here's the basic idea for my program: divide the numbers from 1 through N into three disjoint ranges. Then any subset of seven numbers chosen from 1..N must contain at least three numbers from (at least) one of these ranges. I use canned coverings from the repository for each of the three ranges, assembling these together to arrive at a final ticket set. The program first computes the best way to divide N into three ranges by brute force (with the smallest total blocksize), then combines (by shifting numbers forward) three canned coverings into a ticket schedule. I'd like to argue, if I may, that even though I'm using some precomputed data, they are *not* data that represent, in themselves, solutions to the problem at hand, because a certain measure of insight (pat, pat) and a little bit of extra computation (cruch, crunch) is required to produce a winning ticket schedule. --Guy Jacobson */ #include #define INFINITY 1000000000 #define MINV 7 #define MAXV 32 int nblocks[] = { 0, 0, 0, 0, 0, 0, 0, 1, 4, 4, 6, 8, 11, 13, 15, 15, 25, 28, 33, 35, 45, 50, 62, 71, 82, 88, 109, 118, 138, 148, 155, 155, 186, 4, 4, 6, 8, 11, 13, 15, 15, 25, 28, 33, 35, 45, 50, 62, 71, 82, 88, 109, 118, 138, 148, 155, 155 }; unsigned long rawblock[] = { 127,127,191,223,239,127,415,487,505,127,911,1009,446,638,463,127,191, 319,575,1087,1987,1996,2032,127,3971,956,3292,1893,3386,2790,2905,1691, 1479,3493,1214,2428,4856,1521,3042,6084,3977,7954,7717,7243,6295,4399, 607,1335,2670,5340,10680,4980,9953,3538,7045,14090,11798,7721,14419, 14502,8527,671,1335,2670,5340,10680,21360,9953,19906,7045,14090,28180, 23593,14419,28838,24909,17051,4317,11418,30225,17336,30764,9588,11081, 19845,7904,19030,5902,17515,29122,8871,6451,32831,34753,63554,39308, 58892,57776,40496,34691,63491,32893,1335,2670,5340,10680,21360,9953, 19906,7045,14090,28180,23593,14419,28838,24909,17051,98901,100367, 101432,102146,102693,103620,108642,113160,115144,117408,118930,123156, 124033,248834,3719,86674,68212,157920,58420,29225,168026,201889,81999, 164770,55104,206360,3434,9681,4407,206148,154372,15634,110788,50317, 131516,90530,43788,176135,104545,9162,149785,72104,99097,108689,38444, 148057,278671,200979,11811,428099,33853,70221,141581,272593,22289, 148833,332961,426881,129025,69814,2902,177158,271642,397418,363018, 49586,91330,154242,483348,140004,284964,312900,101764,23640,198296, 182440,90920,45512,231536,307760,462144,73807,26887,136243,819843, 266781,524773,232453,274969,303401,535689,672905,55377,594321,346657, 176321,395073,525598,139926,538662,269446,320518,428058,21162,737362, 140178,102754,467106,69314,796994,133244,114844,20068,364644,885508, 938244,853048,279000,562760,682120,203528,26224,36272,633360,705312, 226560,1097782,795717,1070597,721066,1094786,168473,1663108,540793, 94282,594625,667670,516097,262870,66591,1736771,91696,1319065,935426, 364644,50888,1840168,1250384,1188576,413872,108880,565804,885904, 165029,274979,1458252,645376,27011,6556,7522,1409546,199430,1120545, 1576720,534828,1329476,167173,297888,788755,19273,1706432,150832, 408320,331144,1191176,1149194,795717,1097782,364644,1094786,721066, 1663108,413872,94282,168473,50888,540793,565804,262870,66591,516097, 594625,165029,1329476,1736771,1840168,935426,2140496,885904,2115971, 1319065,1188576,1070597,1409546,274979,667670,91696,1250384,158984, 2373889,645376,7522,2506828,6556,527177,76550,3180810,919826,2296256, 2427176,2395008,2116400,1186564,2263329,3149980,2631972,2133253, 2102882,3214353,3156384,2871296,2302470,3670601,2887040,3302408, 1115441,4063250,1576720,1097782,795717,1070597,721066,1094786,168473, 1663108,540793,94282,594625,667670,516097,262870,66591,1736771,91696, 1319065,935426,364644,50888,1840168,1250384,1188576,413872,108880, 565804,885904,165029,274979,1458252,645376,27011,6556,7522,1409546, 199430,1120545,1576720,534828,1329476,167173,297888,788755,19273, 1706432,150832,408320,331144,1191176,1149194,6373395,6455334,6619212, 6946968,7602480,6816353,7341250,6293893,6296330,6301204,6310952, 6330448,6369440,6447424,6603392,6915328,7539200,6689793,7088130, 7884804,7381001,267279,1066007,12587155,77923,527683,150147,10715139, 917533,2626085,8659141,86405,6391813,67241,4473129,2150473,9446921, 1215497,8431665,2163537,7471201,9994625,14685313,2241793,12879361, 3479553,13197313,155694,1638478,34150,3147942,12599878,1442566,84250, 264810,13140010,2228682,538762,2229810,3440722,39698,291346,627730, 1075522,2949762,2155650,13698306,14959106,12986370,3821570,35484, 14682380,12910644,2234452,6824212,430244,13239428,2174468,2934788, 13676548,12255236,3150136,12592216,1253528,13910152,2639624,2466056, 12784136,2638064,11542640,269712,12763408,14158352,12592032,9111840, 3260960,12606496,3941408,1070784,12683456,13373760,9085504,2573376, 229895,9445899,20975763,8667427,543811,31457411,9705475,155693, 20973837,9454613,2626085,8659141,9306137,8455337,2150473,8431665, 2163537,22151265,9994625,151169,2241793,21267969,3479553,21585921, 8655886,8921366,3147942,20988486,8472602,21528618,2228682,2229810, 3440722,8466530,2200098,2949762,2155650,8428290,22086914,21374978, 10113026,8422044,10027084,11141388,21299252,2234452,1442580,8422756, 8475012,21628036,31459588,2174468,2934788,22065156,3150136,20980824, 538776,8653416,31461416,22298760,2639624,2466056,21172744,3312648, 2638064,430256,265680,31465552,9642128,21152016,22546960,356880, 9016336,20980640,9111840,9552416,20995104,3941408,3151552,8416448, 21072064,1141056,21762368,9085504,2573376,31589888,33046528,31817728, 1066007,3146119,491527,1058315,37752979,282915,543811,25280515,33437, 37751053,2626085,794821,26223109,1966105,70825,2150473,25691273, 2140209,2163537,25432145,150161,38928481,25299233,1622401,2241793, 38045185,3479553,38363137,65077249,155694,398350,1581334,34150,3147942, 37765702,25692230,67898,38305834,2228682,26218762,3440722,25298450, 78434,25436322,1740866,2949762,2155650,47874,38864130,38152194, 65015810,31457308,60817436,1638508,86412,25624588,38076468,2234452, 25182612,1442596,25203748,38405252,2174468,2934788,38842372,2229816, 37758040,291352,25208856,264936,25182824,555144,39075976,2639624, 2466056,37949960,3312648,2638064,430256,26804272,269712,1269904, 37929232,39324176,1676304,37757856,2820384,1167904,65012256,37772320, 3941408,3151552,37849280,26378432,25240896,1141056,38539584,2794048, 2573376,65019968,65012096,25238144,25985792,26496000,65045504,65275904, 25849856,66076672,65667072,229895,9445899,20975763,8667427,543811, 31457411,9705475,155693,20973837,9454613,2626085,8659141,9306137, 8455337,2150473,8431665,2163537,22151265,9994625,151169,2241793, 21267969,3479553,21585921,8655886,8921366,3147942,20988486,8472602, 21528618,2228682,2229810,3440722,8466530,2200098,2949762,2155650, 8428290,22086914,21374978,10113026,8422044,10027084,11141388,21299252, 2234452,1442580,8422756,8475012,21628036,31459588,2174468,2934788, 22065156,3150136,20980824,538776,8653416,31461416,22298760,2639624, 2466056,21172744,3312648,2638064,430256,265680,31465552,9642128, 21152016,22546960,356880,9016336,20980640,9111840,9552416,20995104, 3941408,3151552,8416448,21072064,1141056,21762368,9085504,2573376, 31589888,33046528,31817728,117706817,102244482,102809860,104924680, 109185072,102900225,105136162,109577284,117475464,101781776,101745697, 102828098,104992900,109322504,117981712,100663327,100664288,100695040, 101679104,133169152,105384193,109089282,117514276,101859400,103023760, 109133953,117572866,101976580,103288872,104898640,229895,9445899, 20975763,8667427,543811,31457411,9705475,155693,20973837,9454613, 2626085,8659141,9306137,8455337,2150473,8431665,2163537,22151265, 9994625,151169,2241793,21267969,3479553,21585921,8655886,8921366, 3147942,20988486,8472602,21528618,2228682,2229810,3440722,8466530, 2200098,2949762,2155650,8428290,22086914,21374978,10113026,8422044, 10027084,11141388,21299252,2234452,1442580,8422756,8475012,21628036, 31459588,2174468,2934788,22065156,3150136,20980824,538776,8653416, 31461416,22298760,2639624,2466056,21172744,3312648,2638064,430256, 265680,31465552,9642128,21152016,22546960,356880,9016336,20980640, 9111840,9552416,20995104,3941408,3151552,8416448,21072064,1141056, 21762368,9085504,2573376,31589888,33046528,31817728,251724033, 235159684,235577344,247464196,237371424,239347712,234918146,235938080, 239616016,241177088,238075904,243482624,236980229,251920912,239109184, 235012676,236519428,235212864,251790344,234898184,244580354,234900482, 239140904,234955266,239206403,237044864,234889361,235668736,235409544, 234901537,251682880,235931720,243793985,234881054,254279682,243270704, 235014528,260052992,234981392,251691044,234894340,235175945,235407904, 256901248,243303040,234881250,245374984,235931137,236064784,236978512, 83886127,1927,30727,491527,7864327,310378579,134340611,41943157, 135790981,274727301,270009861,140510725,117440601,6553,26137,1671193, 6684697,427819033,25057,7777,6389857,1966177,503316577,25264513, 101056897,100763137,25560577,481281,402757633,26744833,106960897, 403070977,102260737,31481857,528482305,234881054,343933006,318767158, 159383654,134502406,268773382,268617734,10922,21802,2785322,5570602, 21202,11602,5406802,2949202,18153634,67731746,2166082,42107522, 84214402,405275266,139003010,84051202,42272002,407897346,306221570, 9638402,134395906,44574722,89139202,86528002,47206402,19660,13132, 5013580,3342412,309260,13492,19252,3440692,4915252,75793540,50529412, 50627332,75694852,80234500,53495812,402862084,55062532,78655492, 134598660,243269688,67707928,134284136,336200744,68233352,21244040, 143165576,304220296,72090376,69259528,17453320,143724808,306450696, 19957256,302555656,144843272,154206728,303121416,147080200,9474256, 37884112,136579408,34652752,12730960,151589008,337907856,152078608, 42535184,339872016,336151056,153371152,336634896,155329552,44311568, 278962336,168435872,79741088,19531040,281100576,169099552,21047840, 68430368,169904672,277482016,17355808,69358624,172037152,278139936, 287391936,202129600,269263168,289448256,44114240,202514752,203493952, 286003776,205556800,286395456,42732608,271583104,38945408,340348928, 2949202,546443840,444596306,540542465,80234500,100763137,153371152, 939524359,1927,12697792,855638092,3342412,279192592,26744833,5406802, 144843272,671262722,880803892,31481857,42272002,10559824,53495812, 281166352,286328968,408946177,336216352,402757633,203493952,337679392, 6389857,5570602,403070977,557883712,306221632,549536032,304155712, 34169872,152078608,205556800,26137,137366276,427819033,805613572, 101056897,676332802,4915252,168435872,604586512,67691528,30727, 277416208,285774088,302784832,555827392,545917472,18923809,172037152, 336863392,637542425,73535752,155329552,151655456,289677832,566231137, 143724808,34652752,11602,606343312,5013580,75793540,89139202,673710722, 605070352,37884560,608307472,169099552,86528002,21307552,551551361, 491527,546049088,536993795,202514752,273711746,106960897,25560577, 68231689,3440692,50627332,21802,50529412,547397792,71633032,84214402, 151589008,271060226,147080200,202129600,554439232,143165576,135579652, 572655752,78655492,268620802,75694852,36440336,1671193,554830912, 805521412,277909648,25057,13132,2785322,85199392,172491908,169904672, 808453252,303186112,19252,810025732,25264513,404226433,7777,268773394, 102260737,55062532,546575392,746586188,84051202,671436802,6684697, 503316577,339806752,10922,574886152,1966177,184549436,7864327, 754974802,352321834,19660,6553,136523780,13492,21202,125829127,127, 571556872,42107522,44574722,287458312,47206402,570991112,538318849, 713031722,2949202,1083314752,1384120402,1612187137,80234500,100763137, 153371152,2013265927,1927,1086374080,855638092,3342412,279192592, 26744833,5406802,144843272,671262722,880803892,31481857,42272002, 1084301632,53495812,281166352,286328968,408946177,336216352,402757633, 203493952,337679392,6389857,5570602,403070977,557883712,306221632, 549536032,304155712,1107895312,152078608,205556800,26137,1211106052, 427819033,805613572,101056897,676332802,4915252,168435872,604586512, 1141425160,30727,277416208,285774088,302784832,555827392,545917472, 1092665632,172037152,336863392,1711276057,1143083272,155329552, 1091179552,289677832,1635778657,143724808,1108394512,11602,606343312, 5013580,75793540,89139202,673710722,605070352,1111625872,608307472, 169099552,86528002,1094787232,1616904577,491527,1082920000,1610735617, 202514752,1347420802,106960897,25560577,1141973512,3440692,50627332, 21802,50529412,547397792,1145309320,84214402,151589008,1344800002, 147080200,202129600,554439232,143165576,1208272900,572655752,78655492, 1342361602,75694852,1109657872,1671193,554830912,805521412,277909648, 25057,13132,2785322,1091832352,1212679300,169904672,808453252, 303186112,19252,810025732,25264513,404226433,7777,1342515202,102260737, 55062532,546575392,1283457100,84051202,671436802,6684697,503316577, 339806752,10922,574886152,1966177,1258291252,7864327,754974802, 1426063402,19660,6553,1208168452,13492,21202,125829127,127,571556872, 42107522,44574722,287458312,47206402,570991112,1611012097,713031722, 43042832,1345332232,72646674,536937557,67645714,144704038,33701917, 1746403464,60096,268722697,4333184,35652686,1108347148,1275071108, 286262596,71348356,1078263920,1082467329,5771395,34740257,306840065, 639762497,143134794,25560448,1611466756,940606480,286146564,1083199497, 773064704,1157628466,303491,1082132533,11624960,1623720001,8526104, 688918593,345261056,684736514,419430933,26755264,33752195,1233125507, 295530,556144640,1091010562,551682816,539181062,1212174528,1241842048, 1419772417,53487680,402723152,136873000,536896290,69206167,1382023488, 140591392,805339969,1611146288,344010760,674373664,344588608,306253984, 9176164,360710308,537143393,1085717,268438179,8988752,41979948, 70529025,553654032,142811394,672203524,1140880896,539100312,822185988, 84428064,268446026,1073928196,478152722,138568196,58826880,5440034, 269555201,1361053702,184950785,654323744,3711120,151094529,168559116, 549719056,88178728,536887499,270140576,322969612,1344622592,155729929, 1124082946,307235842,549527588,1095761994,537136008,201472064, 269162498,4787233,403316760,1627934722,637599884,51497,35195520, 205573120,201918728,1142227464,918585344,1107317040,10753544, 1711801088,67305562,19515392,1077947460,1881833472,1074954296,85327968, 35733712,2920454,1208132736,68944260,69288969,134256196,1478492336, 1115848961,176456706,44597824,34084386,23072008,805347496,9584932, 50881040,220203041,17924688,73957633,440680464,7348486,21365272, 1145209408,268714464,637551634,566235272,170135648,4988949,805619714, 6558096,27265680,67257540,2685410336,2148061314,3355542592,2174418944, 2768257089,2149721217,3221374996,2225111076,2156146768,2160084232, 2147615586,2198078470,2421162180,2214922624,3508539648,2183661640, 3289391114,2168498688,2819105028,3226206241,3800040064,2298478776, 2285126144,2558527491,2690711570,2483553808,2953216008,2147553805, 2182119697,2386694144,2449563680,127,191,223,239,127,415,487,505,127, 911,1009,446,638,463,127,191,319,575,1087,1987,1996,2032,127,3971,956, 3292,1893,3386,2790,2905,1691,1479,3493,1214,2428,4856,1521,3042,6084, 3977,7954,7717,7243,6295,4399,607,1335,2670,5340,10680,4980,9953,3538, 7045,14090,11798,7721,14419,14502,8527,671,1335,2670,5340,10680,21360, 9953,19906,7045,14090,28180,23593,14419,28838,24909,17051,4317,11418, 30225,17336,30764,9588,11081,19845,7904,19030,5902,17515,29122,8871, 6451,32831,34753,63554,39308,58892,57776,40496,34691,63491,32893,1335, 2670,5340,10680,21360,9953,19906,7045,14090,28180,23593,14419,28838, 24909,17051,98901,100367,101432,102146,102693,103620,108642,113160, 115144,117408,118930,123156,124033,248834,3719,86674,68212,157920, 58420,29225,168026,201889,81999,164770,55104,206360,3434,9681,4407, 206148,154372,15634,110788,50317,131516,90530,43788,176135,104545,9162, 149785,72104,99097,108689,38444,148057,278671,200979,11811,428099, 33853,70221,141581,272593,22289,148833,332961,426881,129025,69814,2902, 177158,271642,397418,363018,49586,91330,154242,483348,140004,284964, 312900,101764,23640,198296,182440,90920,45512,231536,307760,462144, 73807,26887,136243,819843,266781,524773,232453,274969,303401,535689, 672905,55377,594321,346657,176321,395073,525598,139926,538662,269446, 320518,428058,21162,737362,140178,102754,467106,69314,796994,133244, 114844,20068,364644,885508,938244,853048,279000,562760,682120,203528, 26224,36272,633360,705312,226560,1097782,795717,1070597,721066,1094786, 168473,1663108,540793,94282,594625,667670,516097,262870,66591,1736771, 91696,1319065,935426,364644,50888,1840168,1250384,1188576,413872, 108880,565804,885904,165029,274979,1458252,645376,27011,6556,7522, 1409546,199430,1120545,1576720,534828,1329476,167173,297888,788755, 19273,1706432,150832,408320,331144,1191176,1149194,795717,1097782, 364644,1094786,721066,1663108,413872,94282,168473,50888,540793,565804, 262870,66591,516097,594625,165029,1329476,1736771,1840168,935426, 2140496,885904,2115971,1319065,1188576,1070597,1409546,274979,667670, 91696,1250384,158984,2373889,645376,7522,2506828,6556,527177,76550, 3180810,919826,2296256,2427176,2395008,2116400,1186564,2263329,3149980, 2631972,2133253,2102882,3214353,3156384,2871296,2302470,3670601, 2887040,3302408,1115441,4063250,1576720,1097782,795717,1070597,721066, 1094786,168473,1663108,540793,94282,594625,667670,516097,262870,66591, 1736771,91696,1319065,935426,364644,50888,1840168,1250384,1188576, 413872,108880,565804,885904,165029,274979,1458252,645376,27011,6556, 7522,1409546,199430,1120545,1576720,534828,1329476,167173,297888, 788755,19273,1706432,150832,408320,331144,1191176,1149194,6373395, 6455334,6619212,6946968,7602480,6816353,7341250,6293893,6296330, 6301204,6310952,6330448,6369440,6447424,6603392,6915328,7539200, 6689793,7088130,7884804,7381001,267279,1066007,12587155,77923,527683, 150147,10715139,917533,2626085,8659141,86405,6391813,67241,4473129, 2150473,9446921,1215497,8431665,2163537,7471201,9994625,14685313, 2241793,12879361,3479553,13197313,155694,1638478,34150,3147942, 12599878,1442566,84250,264810,13140010,2228682,538762,2229810,3440722, 39698,291346,627730,1075522,2949762,2155650,13698306,14959106,12986370, 3821570,35484,14682380,12910644,2234452,6824212,430244,13239428, 2174468,2934788,13676548,12255236,3150136,12592216,1253528,13910152, 2639624,2466056,12784136,2638064,11542640,269712,12763408,14158352, 12592032,9111840,3260960,12606496,3941408,1070784,12683456,13373760, 9085504,2573376}; unsigned long *block[MAXV + 1]; /* Program starts here :-) */ main (ac, av) int ac; char *av[]; { int num, i, j, k, sum; int opt[3]; int min = INFINITY; num = atoi(av[1]); if (num < 3 * MINV || num > 3 * MAXV) { printf ("Duh, I don't know how to solve a problem of that size!\n"); exit (1); } /* find the start of each block */ for (i = sum = 0; i <= MAXV; sum += nblocks[i++]) block[i] = rawblock + sum; /* dumb loop over all ways of breaking num into i + j + k = num */ for (i = MINV; i <= MAXV; i++) for (j = MINV; j <= MAXV; j++) { k = num - i - j; if (k >= MINV && k <= MAXV) { sum = nblocks[i] + nblocks[j] + nblocks[k]; if (sum < min) { min = sum; opt[0] = i; opt[1] = j; opt[2] = k; } } } /* combine three blocks into a ticket schedule */ for (k = sum = 0; k < 3; sum += opt[k++]) for (i = 0; i < nblocks[opt[k]]; i++) { for (j = 0; j < MAXV; j++) if (block[opt[k]][i] & (1 << j)) printf ("%3d", j + sum + 1); printf ("\n"); } }