Code of the top five entries will be posted on the net sites shortly. If you need even more detail - contact the authors - not ME!!! =Fred -()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()- ============== 1 ====================== mudpack ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- mudpack 31 3704 .93 c Doug Jones (PLUS THE BEST SCORE ON ROUND 2!) ================= mudpack submitted by Doug Jones at daj@esun.ho.att.com ================= ++ Please summarize the algorithm used by mudpack The basic idea used by my algorithm is to partition the numbered balls into three disjoint sets and then generate tickets for each set so that all combinations of three numbers in a set are covered. This works because any combination of seven numbers the king selects must contain at least three numbers from one of my sets. I can't guarantee that this will give me the smallest solution, but making tickets for one of my partitions is slightly easier than making tickets for the original problem if only because I can check a solution in O(N^3) time instead of O(N^7) time. In order to determine the sizes of the partitions, I run ticket generator for all partition sizes from N/3-4 to N/3+4 and save the results. Then I loop over all combinations of 3 sizes that add up to N and pick the best combination. I then combine together the saved tickets and renumber them to minimize the tie break sum. The range N/3-4 to N/3+4 was determined by experiment. I ran my ticket generator for all sizes from 7 to 70 and then checked all combinations of 3 sizes for all N from 21 to 200 and found that the best combination was always in this range. I use a simple greedy method for generating tickets for a partition of a given size (M). I maintain a three dimensional array to record number triples that have been covered. I loop over all combinations of three numbers between 1 and M, and when I find a triple that hasn't been covered I make a new ticket. Three of the numbers on the ticket are the uncovered triple and the other four numbers are selected in pairs. First I loop over all possible fourth and fifth numbers and select the pair that covers the most new triples. Then I loop over all possible sixth and seventh numbers and select the pair of them that covers the most new triples. I found that I could sometimes get better answer for a given M by breaking ties during the pair selection based on the number of times a number had been used already. For M greater than 20 I always break times in favor of numbers than have already been used the most. For M <= 20, I run my ticket generator with three different tie breaking schemes, most used, least used and no tie break. I also found that I could sometimes get better answers by starting the ticket generator with tickets generated by another method. The basic idea for the starting algorithm is to group the numbers other than 1 into pairs and then make tickets involving 1 and three of the pairs such that no triple involving 1 has already been covered. I ended up using three different starting methods, two using this idea but with the pairs looked at in different orders and the other being no starting tickets. For one value of M (I think its 18) the best answer I got was from a version of the code that had a bug. I forgot to account for two of the triples that the ticket would cover. So I decided to use the buggy version also. I ended up with six different combinations of tie break, starting solution and bug that worked well but for different M. For M <= 20, I use all six and take the best answer. For M <= 40, I use three and otherwise I use only two. ++ Do you have any good references to recommend? No, but I did figure out a lower bound for the number of tickets required given partition size M. It is M*ceil((M-1)*(M-2)/30)/7 My algorithm is always within 170% of this lower bound and actually hits it for M=15 (and 7 which is trivial). However, I can't prove that partitioning the N numbers into three sets yields the optimal solution. So this lower bound doesn't say much about the original problem. ++ If I had it to do all over - here's what I would try .... I take advantage of the answer to FAQ 7 and make a table of the optimal partition sizes given N and another table with the best method given M. This would save alot of time. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I work for AT&T in Holmdel, NJ where I write software used to design data communication networks. ================================================================= ============== 2 ====================== ShowMeTheMoney ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- ShowMeTheMoney 31 3493 .38 gc H.Burch D.Sleator ================= ShowMeTheMoney submitted by H.Burch D.Sleator at hburch@cs.cmu.edu ================= ++ Please summarize the algorithm used by ShowMeTheMoney I used the technique that I'm guessing a majority of those who got 9 tickets used: split the set into 3 subsets and make sure that for every group of 3 from within ONE subset, you have a ticket that contains all three numbers. Note that since every ticket has 3 numbers from at least one group, this will satisfy the conditions. The question becomes then how to completely cover a set of numbers (well, that and how to split, but that's simply a dynamic programming problem if you know how many tickets it takes to cover each set size). I employ a greedy random ticket selector to do the covering. First, step through the triplets in canonical order, and for every triplet not covered yet, start a ticket with those three. Then, iteratively add a number to the ticket that covers the most number of triplets not covered thus far (randomly break ties). Once this has been done, generally you end up with too much coverage, and a reduction can be done. Note that testing for complete coverage is simple, as it's just making sure the number of triplets covered is equal to the total possible triplets (taking care of duplicate coverage, of course). Thus, we begin an elimination, reduction cycle that starts by going through each number on each ticket and seeing if zeroing that number out causes the completely coverage to fail. Try each number on a ticket, and if you don't eliminate at least 2, don't bother. Once this has been done, go through all the tickets and combine them if they can be (for example, 1 2 3 4 X X X and 2 4 5 9 13 X X can be combined into 1 2 3 4 5 9 13). ++ If I had it to do all over - here's what I would try .... Try to utilize some structure in the complete coverage stage. I tried splitting it into two, but I kept getting back to just a different way to do the thing I was doing in the first place. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a first-year Computer Science Ph.D. student at Carnegie Mellon University (Pittsburgh, PA) Danny Sleator is a professor of CS at CMU who discovered the splitting technique. ================================================================= ============== 3 ====================== shroud_of_Turan ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- shroud_of_Turan 31 3493 503.68 JAVA Ted Alper ================= shroud_of_Turan submitted by Ted Alper at alper@epgy.stanford.edu ================= ++ Please summarize the algorithm used by shroud_of_Turan first, the problem may be reduced to solving a bunch of coveing problems -- the original space of balls will be partitioned into 3 sets and I will create 3 collections of tickets so that every triple entirely in one set will occur in one of the tickets in the associated collection. so the problem is mostly reduced to finding good solutions to the C(x,7,3) problem -- finding the fewest tickets of size at most 7 the cover all the triples in a set of size x. do this for all x around N/3, then see how they can best be fit together. This is a well-known problem -- but I don't know much about how to solve it! So I just did something a lot like my boggle program, putting balls one by one onto tickets and trying to pick the "best" ball at each stage, i.e. one that maximizes some weighted function of the additional triples that would be covered by the ticket. Finding the right weights was an issue I never really addressed. Some weights work quite well for particular values. What I wanted to do was find a collection of reasonable weights, then have my program try them all in turn, as time permits, doing the weights that work best for large x first on the theory that that's all I'd have time for on those, but then working towards better weights for smaller x. I had intended to include some attempts with random initial tickets and such, but never got around to putting them in. I also never gor around to writing a program to search for reasonable weights. The program also runs through its best-achieved coverings to see if any can be improved based on results from its immediate predecessor or successors. Despite the program's name, it doesn't really use Turan theory, though Turan's work is certainly relevant to covering problems. ++ Do you have any good references to recommend? There's a nice web page -- "The La Jolla Covering Repository" that has some background information on the covering problem and samples of best-achieved valued for C(x,7,3) for x up to 32. In principle, these should give optimal or near optimal [possibly off by 1 due to some tickets not requiring all 7 balls in each problem -- and such tickets could be merged if identified] covering for values of N pretty close to 100.... but I'm not aware of ways to quickly compute those coverings (as opposed to simply quoting them). ++ If I had it to do all over - here's what I would try .... analyze the optimal or near-optimal coverings from the above web page to see if some useful patterns could be noted from them. Try to modify my program to make up random weights if it had run out of the early weights. Re-organize things a bit to eliminate redundancy. Experiment to find better weights. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Palo Alto, CA. Teach math, coach a math team, help create educational math software and supervise the students running it. Gack, we're always sick around the deadline time for these things! last time, my son had chicken pox -- this time we're all gacking up phlegm from some virus. Innermost secret -- NOBODY got my pun! Not my mom, not my wife -- *shroud* of Turan: a shroud is a covering! I thought it was such a good joke, too... ================================================================= ============== 4 ====================== DuckAndCover ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- DuckAndCover 31 4753 .10 c Happy Hacker ================= DuckAndCover submitted by Happy Hacker at guy@research.att.com ================= ++ Please summarize the algorithm used by DuckAndCover Gee; it's been a long time since I thought about this. First, I got a bunch of coverings from the La Jolla coverings repository. URL: http://sdcc12.ucsd.edu/~xm3dg/cover.html These are ways to cover *every* subset of size K with a ticket of T numbers chosen from 1..N. This doesn't quite solve *our* problem, but it's nonetheless useful. I got all the ones for K=3, T=7, N <= 32 (they only go up to 32). These coverings aren't necessarily optimal, but they're the best ones known--at least the best ones known in La Jolla. My program uses these canned coverings to compute a ticket set that must hit any other 7-number ticket in at least three numbers thusly: Break up the numbers from 1..N into three ranges: R1 = 1..v1, R2 = v1+1..v1+v2, R3 = v1+v2+1..N, and let v3 be defined as N-v1-v2. Now, from any set S of size seven chosen from 1..N, at least one of R1, R2, or R3 must intersect S in at least three numbers, by the pigeonhole principle. So therefore if we take the union of coverings for R1, R2, and R3, we are guaranteed to have some 7-set that intersects S in at least three numbers. My program simply tries all possible ways to break up N into v1, v2, and v3 st. N = v1 + v2 + v3, and picks the way that results in the smallest "union of coverings" size. Then it unions those coverings, shifting the second one ahead by v1 and the third one ahead by v1+v2. C'est ca. I did this all a long time ago and haven't had time to revisit it--didn't even bother to try to optimize the sum of the tickets at all. ++ Do you have any good references to recommend? There seems to be a lot of literature out there related to this. I actually read a couple of articles, but I can't seem to find them right now. If you look around on the Web starting from the La Jolla repository, you're bound to find the same stuff I did. ++ If I had it to do all over - here's what I would try .... If I had my life to live over, I'd live over a saloon. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? The Happy Hacker could tell you. But then he'd have to kill you ;-) ================================================================= ============== 5 ====================== ticketysplit ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- ticketysplit 35 4617 3.56 c Vincent Goffin ================= ticketysplit submitted by Vincent Goffin at vjg@research.att.com ================= ++ Please summarize the algorithm used by ticketysplit I first map the problem into a standard covering design problem. For this I divide the pool of N numbers into 3 smaller pools. Then I note that any ticket drawn by the King has to have a least one triple in one of three small pools. Therefore if I build 3 collections of tickets, one per pool, such that each collection covers all triples in its area, the combined collection is a good candidate for a minimal ticket list. The 3 smaller problems are standard covering design fare (as I learned!) and the exact solutions are known for only n <= 15. Since 3*15 < 50, it is possible that someone win in round 1! The solutions for n = 16, 17 look rock solid though, so the battle will probably be decided in round 2. Even knowing the best currently known solutions is no guarantee of being able to produce them, let alone under 10 mins! Half decent solutions can be generated by a greedy algorithm that simply collects tickets with the greatest possible number of new triples, while the tickets are generated in sorted order. The loop is repeated, decreasing the number of target new triples at each iteration until all triples have been covered. So ticketysplit has that. But we're talking about trying to win here! And that's much harder. With a respectful nod at the impenetrable combinatorics, I rejected a perturbative approach. This leaves explicit construction methods for each n. That takes us into the remarkable realm of finite fields, geometries over finite fields, Steiner systems and other algebraic beauties. That's where it lead, so that's where I went! Because of the need for explicit constructions, my program got larger and larger but I never looked back! ++ Do you have any good references to recommend? Yes! I owe whatever success this approach will generate to http://sdcc12.ucsd.edu/~xm3dg/cover.html, a reference I came across after much browsing based on a hunch that latin squares had something to do with the problem. I found some code to generate finite fields in netlib, by Art Owen, a package called oa (orthogonal arrays). ++ If I had it to do all over - here's what I would try .... I think I solved the problem to my satisfaction, and to the extent that it can be solved. Of course I could be surprised.... ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T Labs at Florham Park. My job is productizing research stuff, currently speech recognition software. The POTM is my idea of fun (I know, I know...) but I'm not sure how much of it I can take or how much more I can impose on family, friends, and just normal work schedules! Actually a while back I suggested sphere packing as a problem type, but this one came awfully close and I'm completely satiated... Maybe this problem was harder than expected, I'd like to read others' reaction to it. I'd also like to lead a round of applause for Fred for organizing this contest. I'm sure it provides memories, of both joy and struggle, for all participants. And finally I'd like to see Luc and Alfons be forced to eat their large box of chocolates in one afternoon session for suggesting there may be an exact formula! ================================================================= ============== 6 ====================== Prairie_Dog_Weiner ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Prairie_Dog_Weiner 32 3794 580.39 c Thad Smith ================= Prairie_Dog_Weiner submitted by Thad Smith at ThadSmith@acm.org ================= ++ Please summarize the algorithm used by Prairie_Dog_Weiner Values of N < 22 are handled as a special case (yes, I know it's not required, but I wanted my program to be complete) which can easily be worked out by hand. With larger values, the program examines 9 group sizes centered around N/3. For each group size, it strives to generate a minimum set of tickets which cover ALL the combinations of three in the group. Then the program joins three groups whose sizes total N and whose total number of tickets is the minimum, translating them to cover the full range of 1..N. For each group, I first select the ticket (1,2,3,4,5,6,7). The next ticket is either a random choice, or a ticket generated from a hint lookup table (derived from offline searches). For following tickets in the group, the program finds a triple not covered so far, places those balls as the first three, then chooses the remaining balls in the same ticket to minimize the overlap of triples. After all triples are covered in the group, the program optimizes the list by looking for balls in the list that can be eliminated without uncovering a triple. If 3 balls can be eliminated from one ticket and four balls can be eliminated from another, the tickets can be combined. Other combinations can be used to reduce the total number of tickets required to cover the group with triples. The general strategy of the program is to try as many random starts for each group size as possible, keeping the group ticket list that is the shortest. When time is almost up, the program takes the best combination of group coverages and renumbers the balls to do two things: 1) move the group to the selected sub-interval of 1..N, 2) reduce the sum of the balls. When combining the lists, it is possible to combine partial tickets from two different groups, thereby reducing the ticket count by one. All unneeded balls that were earlier removed from a ticket are replaced by the lowest possible values, usually 1, 2, etc. If the hint table is used (it was for the contest version), the initial effort for each group will be one found by trial to yield a low value. If not, the program uses the minimum found over the allowed running time. The program has a more extensive description in the initial comments. ++ If I had it to do all over - here's what I would try .... It would be much the same. I suppose I would further exploit the notions of precomputed hints. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I own my own company, T3 Systems, located in Boulder County, Colorado, USA, which develops software for embedded applications, such as wireless modems and roadside message signs. I like getting close to the metal, and sometimes design the digital hardware for projects. I enjoy combinatorial problems, such as the Elbonian Lottery. Otherwise, I play raquetball, run, and bike. I am a charter member of the Boulder Polar Bear Club, which rings in each new year with a dip in local reservoir. I live with my wife Mindy, son Joel, and daughter Alison. This year I will celebrate 50 years on Earth. ================================================================= ============== 7 ====================== El_Konyo ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- El_Konyo 34 3945 471.89 gc Yoichi Kono ================= El_Konyo submitted by Yoichi Kono at kono@ai.isl.secom.co.jp ================= ++ Please summarize the algorithm used by El_Konyo Just using the Hill Climbing method. (If I have to say more, I will!) ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? COMPANY: SECOM LOCATION: Tokyo,Japan JOB: Reseacher DO FOR FUN: Yes. ================================================================= ============== 8 ====================== tax_minimizer ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- tax_minimizer 35 4617 590.30 gc George Papoutsis ================= tax_minimizer submitted by George Papoutsis at Georgios.Papoutsis@nws.e-technik.tu-muenchen.de ================= ++ Please summarize the algorithm used by tax_minimizer First divide the numbers 1,2,...,N in three subsets with about N/3 elements each. At least three of the King's seven numbers will be in one of these subsets. For each of these subsets try to find as few tickets as possible, that contain all triplets of the subset. (For this last step, find a triplet that is not yet in the tickets, and based on that build a ticket, that contains as many new triplets (not yet contained in the other tickets) as possible; repeat this until all triplets of each subsets are in the tickets) ++ If I had it to do all over - here's what I would try .... Maybe try to find a general solution and get the chocolates ;-) ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I am from Greece and doing now my PhD in electrical engineering in Munich, Germany. For fun: computers, travelling, photography. Secret: # ######## ###'# #### ## #### ### ## #######. ================================================================= ============== 9 ====================== only_for_the_rich ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- only_for_the_rich 36 3936 449.99 c Franz Mauch ================= only_for_the_rich submitted by Franz Mauch at Franz.Mauch@uni-konstanz.de ================= ++ Please summarize the algorithm used by only_for_the_rich The algorithm uses recursion to smaller subproblems. Some of the subproblems are handled then explicit, some by greedy algorithms. ++ If I had it to do all over - here's what I would try .... I would refine the greedy algorithms. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Just finished my thesis and looking for a job. I like to solve such problems, so I participated in this competition. ================================================================= ============== 10 ====================== Russian_Roulette ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Russian_Roulette 37 4117 4.04 C Dmitry Potapov ================= Russian_Roulette submitted by Dmitry Potapov at DPOTAPOV@us.oracle.com ================= ++ Please summarize the algorithm used by Russian_Roulette Optimized greedy looking for an approximation. ++ If I had it to do all over - here's what I would try .... Will check what the POTM winners tried first :-) My entry doesn't solve the original problem, but I wouldn't do it differently unless rules are different. Maybe I would relax the greedy condition from "choose the best possible" to "choose all better than (the_best_possible - E)" Actually I tried to relax and there was an improvement but I'm too lazy (or busy). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Oracle Corporation, Redwood Shores, CA, Senior Software Engineer. POTM is fun! No POTM ideas or secrets to share. ================================================================= ============== 11 ====================== Renegade ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Renegade 38 4599 4.48 c John Engels ================= Renegade submitted by John Engels at jengels@att.com ================= ++ Please summarize the algorithm used by Renegade The problem decomposes into the three smaller problems of filling out enough tickets to guarantee that no matter what three (3) numbers the king picks from 1/3 of the balls in the hat, all three numbers are found on at least one ticket. This works because the king has to pick three (3) numbers from at least one of the three (3) subgroupings of ( M / 3) balls. (The actual formula for the size of the subgroupings is slightly more complicated than indicated here.) My final solution is really a combination of three (3) approaches. Algorithm 1 - First I generated every possible combination of three numbers based on the size of the subgrouping, and passed these "triads" into a function that built the tickets of seven (7) numbers. The "build_ticket" function selects a ticket to append the "triad" to by searching the existing ticket set for one where two of the three numbers already exist (and there is still room on the ticket). If no suitable match is found, then I add a new ticket with the three (3) numbers from the "triad". This results in some tickets containing less than seven (7) numbers, so I wrote an optomization function that would loop through the resultant ticket set and combine partially filled tickets. Then I call a function to fill up any still partially filled out tickets with the smallest number from 1 to 7 that is not already used on the ticket. Finally, I call a function to "shuffle" the numbers to ensure that larger numbers are used less frequently than small numbers, so that my total sum of numbers is as small as possible. This works OK, but . . . The resulting number of tickets is hightly dependent on the order in which the triads are passed into the "build_ticket" function. As much as I tested out different sort orders, I could not find one sort order that worked better than any other for all values between 25 and 200. Algorithm 2 - Next I tried an elimination technique. I chose the pair of numbers that were found more frequently than any other pair of numbers in the triads that were not yet part of a ticket. If more than one pair of numbers tied for most potiential matches, I chose the pair that was least frequently used. This pair was put on a ticket. Then, I chose the one number from the remaining numbers that would yield the most matches with the unused triad set when combined with the other numbers already on the ticket. This process is repeated until all seven numbers on the ticket are filled in. Repeat the process for the second ticket and continue until all triads are exhausted. This solution is better than the "sort_and_build" method for higher values of "M". For M < 50 the results were mixed. Algorithm 3 - Since "Algorithm 2", the "best_number" method was better than the "sort_and_build" method, why not try the "best_ticket" method. For this method, I generate every possible combination of seven (7) numbers, a full ticket, and pick the ticket that will eliminate the greatest number of unused "triads". Write this ticket out to the result set, mark any matched "triads" as used, and continue with the next ticket until all "triads" are exhausted. This solution was significantly better than both "sort_and_build" and "best_pair" for most values of M (about 5 or 6 values of M were still better with the "sort_and_build_ method) Also, it's as slow as some the contractors we have working here. The entry that I finally submitted is a combination of all three methods. For M < 50 , I produce the results using both Algorithm 3 and Algorithm 1, sorting the "triads" three (3) different ways for Algorithm 1. This gives four (4) different results. I choose the best result and print out my answer. Algorithm 3 is usually better, but like I said, there are about 5 values of M for which the "sort_and_build" technique works better. For values of M > 50, Algorithm 3 always gives the best answer, but it is too slow, so I use Algorithm 2, the "best_pair" technique. No matter what algorithm is used, the functions to "optomize_paritally_filled_tickets", "fill_up_partially_used_tickets", and "shuffle" numbers to get low sum totals, are always called before printing the results. ++ If I had it to do all over - here's what I would try ... Genetic Programming. Basically, the idea is to randomly generate a "population" of solutions represented as binary trees. This "population" can be bred into the next generation by swapping randomly selected subtrees from the solution or "parent". By selecting "fit" parents, that is parents whose subtrees contain characteristics that we want to breed into the next generation (ie: a minimal number of tickets), we can simulate survival of the fittest and evolve the "population" into better and better representations of the result we are trying to achive, that is, a minimal ticket set that matches at least three (3) of the kings numbers. I did get a version of this to work, but . . . Although successive generations of the "population" did yield valid solutions and become more "fit" over time, they never did evolve to a number of tickets that could beat the "traditional" programming of my submitted entry. I think that my B-Tree representation of the result was flawed, and that all I was really doing was getting a more evenly distributed randomness to my sorted "triads" before I passed them into a "build_ticket" function. Oh well, If I only had more time. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Company: AT&T Location: Piscataway, NJ Job: Programmer / Analyst (UNIX, PowerBuilder, "C", Oracle, Sybase, Informix) Do For Fun: Skateboarding, Snowboarding, WaterSkiing ,Woodworking, Gardening Innermost Secret: Well, there's this blonde . . . ================================================================= ============== 12 ====================== PackUpYourTriples ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- PackUpYourTriples 39 4547 .29 c John Linderman ================= PackUpYourTriples submitted by John Linderman at jpl@research.att.com ================= ++ Please summarize the algorithm used by PackUpYourTriples If you split N numbers into 3 piles, then, by a pigeon-hole principle argument, given any 7 of the numbers, 3 or more must come from the same pile. If you pack ALL triples from each pile into 7-tuples, then the collection of tuples, by the above argument, wins the lottery for any selection. What's more, omitting any triple from one pile yields a 7-tuple that isn't covered, by taking the missing triple and any 2 elements each from the other two piles. So if you go down the 3-disjoint-pile path, packing ALL triples in each pile is both necessary and sufficient. Whence the name for my program. So my approach rests on packing ALL triples for a collection of numbers into 7-tuples, which I have no reason to believe I do particularly well. With Fred's blessing, I precomputed the best way to split the original N numbers into the 3 piles whose triples are packed, given the number of tickets it takes for any given pile. For example, it takes me as many tickets (4) to cover 8 items as it does to cover 9. So, rather than treat 25 elements as two piles of 8 and one pile of 9, it's better to regard it as two piles of 9 and a pile of 7 (which can be covered with a single ticket). I collect the tickets instead of printing them immediately, so I can count how often each number occurs overall, and permute so that frequently occurring numbers are printed as lesser numbers, and infrequently occuring numbers as greater values (for the tiebreaker). Unlikely to matter much; I concur with Fred that packing into minimal 7-tuples for round 1 will be my downfall. ++ Do you have any good references to recommend? The Joy of Cooking has some great recipes. ++ If I had it to do all over - here's what I would try .... I'm pretty much tied to the 3-pile approach. I'll spend the last week looking for better ways to pack triples into 7-tuples. Although NP-hard in general, there may be some brute-force approaches for the smaller values of N, to keep me alive through the first round. (I suspect there may only BE one round). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T, Florham Park, NJ. Hacker (job AND fun). I've been XC-skiing a lot during this potm (obviously NOT in NJ). I'm devoid of secrets and potms. ================================================================= ============== 13 ====================== autolotto ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- autolotto 40 4546 .11 gc David Van_Brackle ================= autolotto submitted by David Van_Brackle at vanb@east.isx.com ================= ++ Please summarize the algorithm used by autolotto First, I divide the numbers 1-n into three equivalence classes (ECs). When the King selects 7 numbers at random, it's guaranteed that at least one of those three ECs will have at least three numbers from the King's seven. Then, I try to cover all possible selections of three from each of the ECs. Within an EC, I separate the numbers into consecutive groups of seven. I then handle each of these three cases: 1) Given one group A, all three are in A. 2) Given two groups A and B, either 2 are in A and 1 in B, or 1 in A and 2 in B. 3) Given three groups A, B and C, 1 is in A, 1 in B and 1 in C. In the code, you'll see three groups of loops - a for(a) loop, a for(a)for(b) construct, and a for(a)for(b)for(c) construct. It should be obvious which handles which case. For case 1 (for(a)), it's sufficient to just print the group as a single ticket. The size of an EC isn't usually divisible by 7. Thus, there's usually one group of numbers at the end which is <7. In case 1 (the for(a) loop) I ignore this - the extra group will be picked up in cases 2 and 3. In cases 2 and 3 (for(a)for(b) and for(a)for(b)for(c)) you'll notice a switch on the size of the last group, and in each case, a sequence of tickets to cover the case. Most of the work on this program went into handling each of these 14 cases with the minimum number of tickets. I then began to wonder if some of the tickets in case 2 were made unnecessary by the tickets in case 3. I found that, in the right circumstances, when the last group is of size 7, there were two tickets in case 2 that were unnecessary when case 3 tickets were considered. Of course, there is no case 3 with the last group of size seven unless the EC is bigger than 21. Now, how do you break the original 1-n into 3 ECs? I was stunned to learn early on that simply dividing into three equally-sized (or nearly so) ECs didn't always yield the minimum number of tickets. I wrote a program which #includes the lotto program, and goes through all n's from 25 to 200, and calculates the optimum split points. This must be done every time the case 2 and case 3 ticket combinations change! In the code, this is represented by the is and js arrays. Also in the code, you'll see some #ifndef COSTER stuff - this is to hide autolotto's main and other code from the coster. Next is the problem of minimizing the ticket number sums. The program runs very fast, so rather than trying to find some very clever way of ordering the numbers in the tickets, I simply run the algorithm twice. The first time, I build a histogram of the number of occurrences of each number. Then, I use quicksort, and build a translation table. The most frequently occurring number will be replaced by 1, the second most by 2, etc. This guarantees that for a given ticket combination, I will have the minimum sum. I wrote several programs for this project. Along with the main program submitted, I also wrote programs to determine the best split points for the ECs, count and sum up the tickets, display a histogram of the numbers, analyze if any of the case 2 tickets could be removed when case 3 was added, analyze my case 3 7x7x7 code, and to test my output. ++ Do you have any good references to recommend? Check out "Obfuscated C and Other Mysteries" by Don Libes. Look on page 257. ++ If I had it to do all over - here's what I would try .... I like my algorithm, and at the moment, can't think of a better one. My company sent me travelling for the three weeks prior to the contest deadline, so my only regret is that I didn't have more time at the end. I'm pretty sure I could come up with a better solution for case 3 with the last group having 5 tickets! ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? COMPANY: ISX Corporation LOCATION: Marietta, GA (just NW of Atlanta) JOB: Programming project technical lead DO FOR FUN: Ride roller coasters, travel, SCUBA dive, and write programs for fun. INNERMOST SECRET: None of your beeswax. POTM IDEAS: Dell Crossword magazines include a type of puzzle similar to a crossword, but using digits instead of letters. The across/down clues are the sums of the digits. The digit 0 is never used, and each "word" of digits cannot have any digit repeated. This is not a difficult problem to solve - but if you use CPU time as the measure of success, I think it becomes an interesting problem. In solving them by hand, I have built up some patterns in my mind that I look for. I would be interested to see the patterns and heuristics programmers come up with to solve such a problem in a minimum time. Unfortunately, choice of language may be too big of a factor in such a contest. Developing a game and having programmers to write code to play the game is always interesting. If you're interested, I have a game which is particularly well suited for the purpose. I used it for just such a contest at my school about 7 years ago. It is guaranteed to end after a certain number of moves, it is guaranteed to have a winner, and each move is complicated enough that competitors can't simply write a really deep minimax with a simple eval function. Nobody (but myself and the two competitors) will have ever seen it before, so no one would have an edge. I'd be more than happy to send you the details. vanb ================================================================= ============== 14 ====================== elboe ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- elboe 40 4627 .16 c Andrew Gauld ================= elboe submitted by Andrew Gauld at andrew.gauld@att.com ================= ++ Please summarize the algorithm used by elboe Divide range of numbers into rough thirds, and generate tickets using numbers from each third such that every tripple of numbers in a given third is found in at least one ticket. Subsequent optimizations re-number the tickets to minimize the total. Actually generates tickets for different size intervals around 1/3 of range, and picks the set of 3 intervals that minimizes the total number of tickets. Within an interval, numbers are assigned to tickets by 3 nested loops: First, loop runs across interval 3 numbers at a time and places the three numbers in a ticket. Second loop runs from end of first set of 3 to end of interval 2 numbers at a time and places 2 numbers in a ticket. Third loop runs from end of second to end of interval 2 at a time placing final 2 numbers in the ticket. Each ticket is checked to see that it is needed, and if it is not, it is omitted. If the final iteration of the 3rd loop only contains 1 number, then the 2nd loop is passed 3 tickets at a time to minimize the number of don't care ticket values (and the number of tickets). Special case for an interval of 8 numbers: need a ticket with the last 5 numbers in the interval and 2 don't cares. Could potentially improve by looking more for don't cares in generated tickets and trying to make use of them rather than looking for complete don't care tickets and rejecting them, but I don't have the time. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T Lincroft, NJ ================================================================= ============== 15 ====================== Lott-Er-Luck ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Lott-Er-Luck 40 4693 .09 c Paul Bunting ================= Lott-Er-Luck submitted by Paul Bunting at bunting@lucent.com ================= ++ Please summarize the algorithm used by Lott-Er-Luck 1) Break set of N numbers (1->N) into 3 sets. At least one of those sets has at least 3 of the King's 7 numbers. 2) Let S(I) = the number of sets of seven to completely cover all possible sets of 3 in the set of numbers 1, 2, 3, ..., I. 3) Find I1, I2 and I3 such that: a) S(I1)+S(I2)+S(I3) has the minimum value b) I1+I2+I3=N. 4) Best guess for S(I): a) Break I into sets of 3 and sets of 2. Assume x sets of 3 and y sets of 2. Then, 3*x + 2*y = I. For any 3 given numbers from 1 to I, they have to be contained in 3 sets of 3, 2 sets of 3 and 1 set of 2, 1 set of 3 and 2 sets of 2, or 3 sets of 2. b) Cover all cases: ( Note that at least two sets of 2 and 1 set of 3 must exist.) ( Note that C(x,n) is combination of x things taken n at a time.) 0) Special Case for Set of 8 - Set of 3 - A1, A2, A3 Set of 3 - B1, B2, B3 Set of 2 - C1, C2 Done in 4 - A1, A2, A3, B1, B2, B3, C1 A1, A2, A3, B1, B2, B3, C2 A1, A2, A3, B1, B2, C1, C2 A1, A2, A3, B1, B3, C1, C2 1) In 3 sets of 3 - C(x,3) * 3 (Ex: A, B, C are 3 sets of 3. A1, A2, A3, B1, B2, B3, C1 A1, A2, A3, B1, B2, B3, C2 A1, A2, A3, B1, B2, B3, C3) 2) In 2 sets of 3 and 1 set of 2 - C(x,2)*C(y,1)*2 (Ex: A, B sets of 3, C sets of 2. A1, A2, A3, B1, B2, B3, C1 A1, A2, A3, B1, B2, B3, C2) 3) In 1 set of 3, 2 sets of 2 - C(x,1)*C(y,2) 4) In 3 sets of 2 - a) for y=3 - done in one set of seven. b) odd number - treat like 2 sets of 3 + (y-3) sets of 2. = C(y-3-1,4)*2 + C(y-3,2)*2 + (C(y-3,1)*2 (Note y-3 is an even number) c) even number - C(y-1,4)*2 (Ex: A, B, C, D are sets of 2. A1, A2, B1, B2, C1, C2, D1 A1, A2, B1, B2, C1, C2, D2) 5) 2 in 1 set of 3, 1 in 1 set of 3 (see 2 sets 3 / 1 set of 2) 6) 2 in 1 set of 3, 1 in 1 set of 2 (see 1 set 3 / 2 sets of 2) 7) 2 in 1 set of 2, 1 in 1 set of 3 (see 1 set 3 / 2 sets of 2) 8) 2 in 1 set of 2, 1 in 1 set of 3 (see 1 set 3 / 2 sets of 2) 9) 3 in 1 set of 3 (see 1 set 3 / 2 sets of 2) c) Minimize sum of all cases where x>=1, y>=2 and 3*x +2*y = I: 1) Sum - C(x,3)*3 + C(x,2)*C(y,1)*2 + C(x,1)*C(y,2) + 1 if y is exactly 3 + C(y-1,4)*2 if y is even , >=4 + C(y-3-1,4)*2 + C(y-3,2)*2 + (C(y-3,1)*2 if y odd ++ If I had it to do all over - here's what I would try .... Basically, I would use same approach. I would have sent in more entries to better fine tune. I still see ways to improve: 1) Given a set of tickets that completely cover all sets of 3 for a given range of numbers, check that every pair of numbers (say p,q) in that set are such that if p= Count(q). If not, swap p with q in the set. This would produce a similiar result with a smaller sum. 2) If we are trying to cover 3 sets of 2, make sure 7th number is 1. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Lucent Technologies Warren, NJ USA Software Design/Development - METRICS Group Woodworking, Motorcycling, Photography ================================================================= ============== 16 ====================== Hole_Lotto_Love ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Hole_Lotto_Love 40 5017 9.13 PERL John Williams ================= Hole_Lotto_Love submitted by John Williams at jwill@chromatic.com ================= ++ Please summarize the algorithm used by Hole_Lotto_Love Basically I use a seive type approach, building larger solutions from smaller solutions. There are three basic algorithms I use: 1) Split the numbers into groups of three - each group is independently checked for the existence of three matching tickets. 2) Group numbers together in three groups to cycle through the possibilities. 3) A special case exists for 12 tickets that requires less tickets than the general case in (2). ++ Do you have any good references to recommend? Any perl manual, but especially the one written by Wall, Christiansen, and Schwartz. ++ If I had it to do all over - here's what I would try .... I decided to go with the perl entry, I could have made it faster by using C. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I work for Chromatic Research as a Hardware Verification Engineer. ================================================================= ============== 17 ====================== RockNRodl ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- RockNRodl 41 4775 2.43 PERL Matthew Mullin ================= RockNRodl submitted by Matthew Mullin at mdmullin@alumni.princeton.edu ================= ++ Please summarize the algorithm used by RockNRodl After thinking about it for a little while, I realized that to make winning lottery tickets for the 7,3 case, you could divide N into 3 approximately equal parts and make a 7,3 cover on each of those parts. Whatever the king's 7 numbers are, there has to be at least 1 parts that contains 3 of the king's numbers (pigeonhole principle). If we put a group of 7-sets on each of these 3 parts so that each 3-set in each part is contained by at least one 7-set, then at least one of these 7-sets will intersect with the king's 7 numbers in at least 3 points. After taking into account special cases for N<21 (when the parts will be smaller than 7), this appears to be basically the best way to do it. It is the method implied by a lower bound equation in [CRC]. So we now want to find good 7,3-coverings for the various N we want. There are many ways to build coverings; unfortunately, there is no single method that works well for all regions of N, and they are more ideal for finding good coverings using a lot of time, rather than finding a good covering in a limited amount of time. The main method I have used is a simple recursive method. Let the coverings we are looking for be (k,l,n) for a covering of n with sets of size k that cover all subsets of size l, and the size of a covering be C(k,l,n). Then the main equation is: C(k,l,n)<=C(k,l,n-m)+C(k-m,l-1,n-m) for m=1..min(k-l+1,n-k), plus boundary conditions: C(k,k,n)=binom(n,k) All k-subsets of 1..n C(k,1,n)=ceil(n/k) Subsets 1..k, k+1..2k, etc So the main procedure &cover uses the above equation recursively, finding the best value of m for each instance. The results of this are approximately N^3/80. After coverings were calculated, the actual &lottery routine was called. For small values of N, we check out not-quite-equal partition of N into 3 parts -- for the test case, N=25, an even division is 8,8,9, which gives a total of 12 tickets; an uneven divison of 7,9,9 gives 9 tickets (basically because the best covering for 8 is still inefficient). Running with this basic algorithm, we get an answer of 11088 for N=200. The improvements added for the final submission were: Using an affine geometry (15,7,3) for the covering for N=15 and using a projection of that (just dropping points 15 and 14) for N=13 and 14. We then run the &cover recursive algorithm from N=16 to N=25 to make use of these new improved estimates, which improves them by 13 (if I remember correctly) - the difference between the old and new values for C(7,3,15). For larger values of N (>25), we make use of an affine geometry AG(125,25,3), which has size 155. Then we 'induce' a covering for N by choosing a random set of N points from 1..125 and taking the intersection of this set with each set in AG(125,25,3). If the intersection is of size 2 or less, we discard it; if it is from 3 to 7 we stick it on a new list; and if it is 8 to 25 we put in a precomputing covering. Using these improvements, we get an answer of 7321 for N=200 (may vary since we are using random numbers). In all cases, after we make our coverings and combine them into a lottery solution, we relabel the points so that the most numerous is 1, the next is 2, etc... This way the sum of the numbers on the tickets will be minimized. While constructing the coverings with &cover, we keep track of elements that are 'garbage', i.e. unneccessary to actually cover anything. While finding what partition of N will give us the fewest tickets, we use the most garbage as a tiebreaker; the garbage elements are later set equal to 1, 2, etc in increasing order, to minimize their contribution to the total ticket sum. With these methods, we are able to match the best result for the test problem (9 tickets, ticket sum 669). NOTES: For 7,3 coverings such that we are interested in, the best general lower bound is given by Schonheim [SCH]: ceil(N/7*ceil((N-1)/6*ceil((N-2)/5))) For the N=200 case, using a partition of 66,66,67 we get a lower bound of 4029. For a general large N, we get asymptotically N^3/1890 for the lottery problem. Rodl [ROD] proved that for fixed k and l (7 and 3), the lower bound is approached asymptotically. Rodl's proof was non-constructive, but in [GKPS] there are given two methods that are asymptotically optimal. One is a variant on the lex code (order all the 7-sets and always pick the first one that covers the most new 3-sets), and one is the generalization of the 'induce' method that is used in my program. Allowed more time for the program to run, there are multiple other methods in [GKP]. ++ Do you have any good references to recommend? These are all references that I made some use of, either giving some method that I used, or letting me know I was on the right track. [CRC] CRC Handbook of Combinatorial Design. [SCH] J. Schonheim, "On Coverings", Pacific Journal of Mathematics, 14, 1964, pp 1405-1411. [ROD] V. Rodl, "On a Packing and Covering Problem", European Journal of Combinatorics, 5 (1) 1985, pp 69-78. [GKPS] D. Gordon, G. Kuperberg, O. Patashnik, J. Spencer, "Asymptotically Optimal Covering Designs", Journal of Combinatorial Theory, series A, 75 (2) 1996, pp 270-280 [GKP] D. Gordon, G. Kuperberg, O. Patashnik, "New Constructions for Covering Designs", http://sdcc12.ucsd.edu/~xm3dg/cover.ps also Journal of Combinatorial Design, vol. 3, pp 269-281. Plus many resources on combinatorics in general: The Handbook of Combinatorics, R. Graham, M Grotschel, L. Lovasz, ed. Introduction to Combinatorial Theory, R.C. Bose, B. Manvel A Course in Combinatorics, R.M. Wilson, J.H. Van Lint. The Electronic Journal of Combinatorics, http://www.combinatorics.org And in general, any books or articles dealing with combinatorics, graph and hypergraph theory, Turan numbers, design theory or finite geometry ++ If I had it to do all over - here's what I would try .... First I would find out about the contest sooner so as to not cram it into the last few weeks. There were multiple methods that could be used for different regions of N (and k and l) for coverings that I either didn't have enough time to implement, or make fast enough or make use reasonable space. The cases with k=3,4,5 and l=2 are nearly totally known and would improve the 7,3 case substantially. I might have tried to use C instead of Perl if I had had time to write some list manipulation routines. It seems that specially designed C should be faster than Perl, plus by the end of the contest, I was getting tired of $ and @ in Perl, and wrestling with when to use references and when to use real variables, [] vs \, etc. Plus I would have sent in my final submission before 11:55pm on the last day and would have carefully tested it before (hopefully it works as well as earlier submissions did). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? COMPANY: University of Detroit School of Dentistry, Materials Managemant FUN: Reading, games and puzzles of all sorts, sports (watching) SECRET: is a secret even from me :) POTM: More of the games (CHOMP,BOXING) or NP-complete problems in disguise (AIMLESS,KNIGHTCRAWLER). Basically things that you can get an idea on how to proceed, but not a simple, fast solution. ------------------ Link to code is at http://www.msen.com/~muffin ================================================================= ============== 18 ====================== who_needs_luck ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- who_needs_luck 43 5151 .13 gC Shawn Fox Sorry ... no description available for who_needs_luck ================================================================= ============== 19 ====================== LOTO_NHV ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LOTO_NHV 43 5395 .12 C Nguyen Viet Sorry ... no description available for LOTO_NHV ================================================================= ============== 20 ====================== LuckOut ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LuckOut 44 5171 .13 c Davor Slamnig ================= LuckOut submitted by Davor Slamnig at slamnig@fa2.so-net.or.jp ================= ++ Please summarize the algorithm used by LuckOut The set of possible ticket numbers is divided into three more or less equally sized subsets. Each possible ticket will contain at least three numbers from one of the subsets. The tickets are generated by enumerating the (hopefully) smallest number of seventh order combinations from each subset which guarantees that all third order combinations are covered. It was fast and slick, but it didn't do the trick. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I live in Zagreb, Croatia, and work on-line for TechnoCraft, Japan, making dictionary software. For fun I play the guitar (sometimes I do it for money, too). My innermost secret can only be revealed to a 5-dimensional observer who perceives my whole existence. POTM idea: Something I can win in. ================================================================= ============== 21 ====================== SWAG ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- SWAG 45 5280 .06 c Paul Banta ================= SWAG submitted by Paul Banta at pbanta@hotmail.com ================= ++ Please summarize the algorithm used by SWAG DIVIDE N INTO 3 (ROUGHLY) EQUAL SETS: For example, N=38 can be divided into 1-13, 14-26, and 27-38. Notice that the size of the first two sets is 13 and the size of the last set is 12. This is due to the fact that 32 is not evenly divisible by 3. KING FRED DRAWS BALLS: We're interested in counting how many balls fall in each of the 3 sets. After King Fred has drawn 6 balls, the worst-case scenario is that 2 balls have fallen into each of the 3 sets. Therefore, the 7th ball that King Fred draws will guarantee that at least 1 of the 3 sets will have at least 3 balls in it. The argument so far should prove that by dividing N into 3 sets, at least 1 set is guaranteed to contain at least 3 of the numbers drawn by King Fred. The problem is, however, that we don't know which set has the 3 balls. SOLVE 3 BALLS IN 1 SET: Treat each of the 3 sets as if IT is the one that contains 3 balls drawn by King Fred. The original problem has now been changed: Given a set of numbers, {a..b}, and only 3 balls drawn (between "a" and "b"), generate enough tickets (of 7 numbers between "a" and "b") to guarantee at least one ticket has all 3 balls on it. SUBDIVIDE SETS: We further divide each of our 3 sets into subsets. We'll turn our attention to only 1 of the 3 sets for now - we perform the same process on each of the 3 sets. Within a set, we create subsets such that the first subset is of size 3 and all other subsets are of size 2 (it is possible for the last subset to be of size 1). We're again interested in which subsets each of the 3 balls falls. In the worst-case scenario, each of the 3 balls falls into a different subset (no 2 balls fall into the same subset). We therefore have to generate all combinations of picking 3 subsets across all subsets. Notice that the size of the subsets allows us to combine any 3 subsets into a ticket of 7 numbers or less. EXAMPLE: Let's look at the set {1..13}. We divide it into subset of {1, 2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, and {12, 13}. We now have to generate all combinations of 3 subsets: 1 2 3 4 5 6 7 8 9 10 11 12 13 Generated Ticket +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | X | | | | 1 2 3 4 5 6 7 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | | X | | | 1 2 3 4 5 8 9 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | | | X | | 1 2 3 4 5 10 11 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | | | | X | 1 2 3 4 5 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | X | X | | | 1 2 3 6 7 8 9 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | X | | X | | 1 2 3 6 7 10 11 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | X | | | X | 1 2 3 6 7 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | | X | X | | 1 2 3 8 9 10 11 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | | X | | X | 1 2 3 8 9 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | | | X | X | 1 2 3 10 11 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ | | X | X | X | | | 4 5 6 7 8 9 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | X | X | | X | | 4 5 6 7 10 11 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | X | X | | | X | 4 5 6 7 12 13 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | X | | X | X | | 4 5 8 9 10 11 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | X | | X | | X | 4 5 8 9 12 13 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | X | | | X | X | 4 5 10 11 12 13 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | | X | X | X | | 6 7 8 9 10 11 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | | X | X | | X | 6 7 8 9 12 13 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | | X | | X | X | 6 7 10 11 12 13 ? | +-------+-----+-----+-----+-------+-------+---------------------+ | | | | X | X | X | 8 9 10 11 12 13 ? | +-------+-----+-----+-----+-------+-------+---------------------+ AN OPTIMIZATION: From the table above, notice that after we have generated all tickets that include the first subset, {1, 2, 3}, we can redefine our remaining subsets as {4, 5, 6}, {7, 8}, {9, 10}, {11, 12}, and {13}. In essence, after we've generated all tickets that include {1, 2, 3}, we turn our attention to the situation where no balls fall in the {1, 2, 3} subset. Another way of stating this is to say that we're concerning ourselves with the case where all three balls fall in {4..13}. So, why can't we treat {4..13} exactly the same as we treated {1..13}? We can! So, we break {4..13} into the following subsets: {4, 5, 6}, {7, 8}, {9, 10}, {11, 12}, and {13} and repeat the same process as we did for {1..13}. This yields the following, modified table of ticket generation: 1 2 3 4 5 6 7 8 9 10 11 12 13 Generated Ticket +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | X | | | | 1 2 3 4 5 6 7 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | | X | | | 1 2 3 4 5 8 9 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | | | X | | 1 2 3 4 5 10 11 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | X | | | | X | 1 2 3 4 5 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | X | X | | | 1 2 3 6 7 8 9 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | X | | X | | 1 2 3 6 7 10 11 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | X | | | X | 1 2 3 6 7 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | | X | X | | 1 2 3 8 9 10 11 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | | X | | X | 1 2 3 8 9 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ | X | | | | X | X | 1 2 3 10 11 12 13 | +-------+-----+-----+-----+-------+-------+---------------------+ (Redefine)4 5 6 7 8 9 10 11 12 13 (Subsets ) +--------+-----+------+-------+----+---------------------+ | X | X | X | | | 4 5 6 7 8 9 10 | +--------+-----+------+-------+----+---------------------+ | X | X | | X | | 4 5 6 7 8 11 12 | +--------+-----+------+-------+----+---------------------+ | X | X | | | X | 4 5 6 7 8 13 ? | +--------+-----+------+-------+----+---------------------+ | X | | X | X | | 4 5 6 9 10 11 12 | +--------+-----+------+-------+----+---------------------+ | X | | X | | X | 4 5 6 9 10 13 ? | +--------+-----+------+-------+----+---------------------+ | X | | | X | X | 4 5 6 11 12 13 ? | +--------+-----+------+-------+----+---------------------+ (Redefine) 7 8 9 10 11 12 13 (Subsets ) +--------+-------+-------+---------------------+ | X | X | X | 7 8 9 10 11 12 13 | +--------+-------+-------+---------------------+ Notice that we redefine subsets whenever we've exhausted all combinations that include the first subset (the first subset is always of size 3). Notice also, that by doing this we've reduced the total number of tickets generated. In our example, we've gone from 20 tickets down to 17 tickets. MINIMIZE SUM: Once the tickets have been generated, but before we print them, we look to see which number occurs most frequently across all tickets. Whatever number that is, we change it to the number "1". Then we look for the next most frequent number and change it to "2". This technique reduces the total sum to a minimal value. ++ Do you have any good references to recommend? No. Sorry. I pulled this algorithm out of thin air and a few late night white-board sessions with Rex-the-wonder-dog and straight-Shawn. ++ If I had it to do all over - here's what I would try .... nothing different. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I work as a software engineer for TRW (T R Wonderful) in Colorado Springs, Colorado, USA. We help protect the United States from those ever-so-common Inter-Continental Ballistic Missile attacks. I love to play volleyball. I also like fishing and backpacking. But above all else, I'm a POTM addict. My innermost secret is Bozo - but don't tell Tom; he's in the throes of an e-mail affair with Susan Adams. ================================================================= ============== 22 ====================== Bozo4_TM_So_Close ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Bozo4_TM_So_Close 45 5445 1.98 CSH Susan Adams ================= Bozo4_TM_So_Close submitted by Susan Adams at ButtGirl_69@yahoo.com ================= ++ Please summarize the algorithm used by Bozo4_TM_So_Close I don't know how this thing works. If anyone wants to look at it and finger it out for me, be my guest. I need all the help I can get - especially from men . . . like Fred (what a sweetie). I just sort of threw some ideas and lines of code together and it seemed to sort of work. Isn't that how life's supposed to be? I really just entered this contest because a friend of mine said it was a good place to meet decent men. ++ Do you have any good references to recommend? No. Sorry. ++ If I had it to do all over - here's what I would try .... I'd study Math and Science more - that's where the men are. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm just a simple country girl going to college in Wyoming. I like aerobics (can't live without aerobics), cross country skiing, camping, and dancing. ================================================================= ============== 23 ====================== HatTrick ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- HatTrick 50 5760 1.65 PERL D.Ross M.Hiller ================= HatTrick submitted by D.Ross M.Hiller at drdt@world.std.com ================= ++ Please summarize the algorithm used by HatTrick HatTrick was a three-stage program; each stage of which I thought was original and clever. I spent a fair amount of time working on the theory before I applied myself to the coding, and had actually worked out that there was a single best answer, everyone who had 9 tickets had that answer, and speed would be the crucial thing at the end. However, I was unable to find a mathematical proof for my theory (presumably because it was wrong). In the first stage, HatTrick splits the possible numbers into three ranges of optimal size. The reasoning behind this was that, with seven balls drawn, at least three of them would have to be in the same range together (if two of the ranges contained only two balls each, the third had to contain three balls). This way, as long as I covered every possible triplet in each of the ranges, I was guaranteed coverage of every possible ticket. I had done some math to figure out the minimum number of tickets my stage-II algorithm required to cover each range, and fudged the ranges so that they required the minimum combined tickets (an even-sized range requires just as many tickets as the next larger odd-sized range). The central algorithm (the second stage) was designed to guarantee coverage of all triplets within a range. Every ticket was composed of the numbers [A, B, C, D, T-C, T-B, T-A], where A45 in the given time limit. How does the "Branch & Bound" work? ----------------------------------- Luckyluke puts the king into the position of a player who tries to draw (at least) seven numbers without hitting any of the tickets from "GlobalTicketList" more than twice. Think of the algorithm as a binary decision tree. Each node of the tree is associated with a configuration, representing a partial drawing of the king, with the additional information that some of the not drawn numbers are "forbidden". The left and right branches are leading to new configurations where: - a number "n" is drawn by the king, or - the same number "n" is forbidden. The numbers not already drawn and not forbidden are stored in the configuration as "possible numbers". Numbers of tickets from the "GlobalTicketList" containing exactly two already drawn numbers are forbidden, too. It is not too difficult to get an upper bound for the number of possible drawings from the information of each configuration. Actually, "luckyluke" uses this uper bound to set up a priority queue of configurations, where the configuration with the biggest upper bound is at the top. Then it takes this configuration, choses one possible number "n", and constructs two new configurations, one where "n" is drawn by the king, and one where "n" is forbidden. Those configurations are inserted into the priority queue again. Luckyluke stops it search if it finds a configuration with 7 drawn numbers, or if the priority queue is empty. How does luckyluke chose the ticket "T" according to the drawing "D"? -------------------------------------------------------------------- Simple: just exchange one number of "D" for another for at maximum 4 times. Luckyluke tries to find numbers maximizing the number of drawings covered by "T", but not by any other of the tickets already in the ticket list. I could only calculate only a rough approximation for this number of drawings, using a formula to calculate the size of the intersection of the set of drawings covered by two tickets. Main problems I had to deal with: --------------------------------- - RUNNING TIME! I had to optimize the algorithm several times to get below the 10 minutes limit for N <= 50, and it does not look very good for N>50. - Finding "good" tickets! I believe that for finding good tickets, one has to change the tickets added to the list once before. Unfortunately, I found no algorithm that really would improve the list of tickets (within the time limit). I tried some evolutinary processes to change the list of tickets slightly, hoping that this would bring me better tickets, but it did not in general. For example, even for N=25 my best modification of the algorithm does not deliver a better solution than 17 ticket, but you know that there are solutions with 9 tickets possible. Other approaches I experimented with: ------------------------------------- - "Sieving" I tried to set up a boolean array with one entry for all of the C(N,7) ("binomial coefficient N over 7") possible drawings of the king and mark all entries as TRUE that are covered by the tickets of "GlobalTicketList". This way one can easily try to maximize the number of TRUE array entries by changing some of the tickets without changing the number of tickets. Unfortunately, C(N,7) gets rapidly very big: C(25,7)=480700 could be still managed, C(50,7) is about 100 millons, so the array won't fit into main memory, C(200,7) is out of question. - "OBBDs" An "Ordered Binary Decision Diagram" is a special data structure for representing boolean functions in an efficient manner. If you can construct an OBDD for a boolean function f, you can easily count the number of input vectors "x" where f(x)=1. To use OBDDs for the lottery, I encoded the tickets as a binary vectors x=(x_1, x_2, ...,x_N), where "x_i=1" means "ticket x contains number i". Then I looked at the binary functions N f(x)=1 <=> sum(x_i)=7 i=1 and for every ticket t=(t_1,...,t_N) of my "GlobalTicketList" N f_t(x) = 1 <=> sum(x_i * t_i) <=2 i=1 A valid drawing "d" of the king (without hitting any of the tickets from "GlobalTicketList" more than twice) must fulfill f(d)=1 AND f_t(d) for every t of "GlobalTicketList". It is easy to construct OBDDs for f(x) and f_t(x), and one can construct the OBDD for "f(x) && g(x)" if one knows the OBDD of f(x) and the OBDD of g(x). So I could construct the OBDD for "g(x)=f(x) && f_t_1(x) && f_t_2(x) && ... && f_t_k(x)", find a vector "x" with "g(x)=1" and use this vector as my next ticket "t_(k+1):=x". The only flaw here is that for N>30 the resulting OBDDs are becoming very large. Additionally, this approach does not support easily changing any of the previously constructed tickets. So at the end, I came back to my first Branch & Bound approach, which was the only one to handle the case N>=40 fast enough. ++ Do you have any good references to recommend? Sorry, I have no reference to english literature at hand. ++ If I had it to do all over - here's what I would try .... Read some books about combinatorial optimization. ================================================================= ============== 25 ====================== Slaughter-E ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Slaughter-E 60 7972 10.57 c Brace Stout Sorry ... no description available for Slaughter-E ================================================================= ============== 26 ====================== tripleg ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- tripleg 70 9390 120.13 c Ivan Velev ================= tripleg submitted by Ivan Velev at ivan.velev@tripleg.com ================= ++ Please summarize the algorithm used by tripleg 1. For 22 <= N < 35 Constructive algorithm based on a set of tickets 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 x x ? 1 2 3 4 5 x x 6 7 8 9 10 x x ? 6 7 8 9 10 x x 11 12 13 14 x x x ? 11 12 13 14 x x x x x x x x x x ... x x x x x x x where x's are between 22 and N 2. For 35 <= N < 70 Seven nested loops for generating all possible tickets. New ticket added to the set of already selected tickets if no ticket already selected has 3+ numbers in common with it. For better results - looping "tune up" (init value and increment) 3. For 70 <= N Three nested loops. Generates a group of tickets so that: for each set of three numbers x y z, there is at least one ticket containing that set. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? TripleG, Toronto Canada, Programmer ================================================================= ============== 27 ====================== EasyMoney ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- EasyMoney 77 9355 6.65 c Joe Vollbrecht Sorry ... no description available for EasyMoney ================================================================= ============== 28 ====================== cclljj ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- cclljj 77 9355 999.27 c Chen Ling-Jyh Sorry ... no description available for cclljj ================================================================= ============== 29 ====================== simple ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- simple 80 9779 1.09 c Alexey Zhelvis Sorry ... no description available for simple ================================================================= ============== 30 ====================== kentemp ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- kentemp 80 9779 1.29 gc Ken Bateman Sorry ... no description available for kentemp ================================================================= ============== 31 ====================== zakharov ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- zakharov 80 9779 1.56 c Alexei Zakharov ================= zakharov submitted by Alexei Zakharov at zakharov@baltics.ru ================= ++ Please summarize the algorithm used by zakharov 1. Generate a list of all triplets. 2. Look across the list of all septets if the current septet contains some striked out triplet. 2.a. If contains - look at next septet. 2.b. Else print the septet and strike out all triplets, contained within it. 3. If septets are over - exit. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Baltic Transport Systems Saint-Petersburg, Russua System Administrator ================================================================= ============== 32 ====================== loops ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- loops 80 9779 1.68 gc Bernard Hatt Sorry ... no description available for loops ================================================================= ============== 33 ====================== in2win ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- in2win 80 9779 67.87 gC Joseph Eccles Sorry ... no description available for in2win ================================================================= ============== 34 ====================== DumbAndSlow ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- DumbAndSlow 80 9779 117.83 C Colin Rafferty ================= DumbAndSlow submitted by Colin Rafferty at craffert@ml.com ================= ++ Please summarize the algorithm used by DumbAndSlow 1. Start with empty list of tickets. 2. For each legal ticket, if there is no ticket in my list that matches, add that ticket. 3. Dump resulting list of tickets. Of course, to make it not choose all 480700 tickets, I have made two simple efficiency optimizations: 1. As I loop through the possible tickets, I check truncated tickets for success. This means that if I match a ticket with only five entries, I can rule out the ~150 tickets that have those five entries. 2. When I add a ticket to my list, I immediately jump back to the third loop, so that I can easily disregard the ~6000 other entries that I know match. ++ Do you have any good references to recommend? No. If I did, I would have done it in with 9 tickets. :-) ++ If I had it to do all over - here's what I would try .... Write a program that exaustively calculates the optimum entries, and try to see if there is a pattern. In fact, I may still do this. Time is running out, but there's still a couple of days left. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I am a consultant doing C++ work for Merrill Lynch. For fun, I do development work for XEmacs. In fact, my exaustive search would best be run in Lisp rather than a procedural language. Hmmm..... ================================================================= ============== 35 ====================== CouldaBeen ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- CouldaBeen 80 10636 5314.66 gC Keith Jones ================= CouldaBeen submitted by Keith Jones at keith@streamdata.com ================= ++ Please summarize the algorithm used by CouldaBeen Depending on the number of balls, I would immediately choose 1-7, 8-14, 15-21, etc., as these always appeared to be good choices. I then looped, first looking for a set of 7 balls that my set of tickets didn't cover. Of the balls in this ticket, I'd pick one that was picked least often in my previous tickets, then I'd loop. Note: the function that checked for a set of 7 balls not covered by my tickets didn't care if a ticket wasn't complete. This looping would continue until I had a complete ticket at which point I'd continue on to the next ticket, picking one ball at a time. ++ Do you have any good references to recommend? None in particular. After finding that my algorithm wasn't even close, I looked through Donald Knuth for pigeon hole discussions but I couldn't find anything that lent itself to the problem. ++ If I had it to do all over - here's what I would try .... I would try to find a friendly neighbourhood Cray that I could work more on my brute force algorithm. The one that I had set my hopes on (so that I could perhaps see some sort of pattern in the 9 ticket solution) took four days to run on a Pentium Pro 200 and output more tickets than my existing algorithm. :) With a Cray, perhaps I may have been able to figure out what the problem was. I know for sure that my idea of an even distribution of ball selections isn't right but to traverse the entire problem space would probably mean I could get the optimum solution some time before the year 2000. Hopefully. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I work for Stream Data Systems Ltd., in Calgary, Alberta, Canada. My job title is Senior Systems Engineer but I think of myself simply as a programmer. Lately, what I do for fun is wrack my brains for a better ticket choosing algorithm. I thought I'd figure something out but nothing came. That's why my program was called CouldaBeen (AContender). I knew it wasn't up to snuff when I submitted it but I figured, "What the heck? You only live once. Maybe the next POTM will stump me even more." ================================================================= ============== 36 ====================== Lotta_rye ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Lotta_rye 82 10084 497.80 C A.S.Kiran Koushik ================= Lotta_rye submitted by A.S.Kiran Koushik at koushik@giasbga.vsnl.net.in ================= ++ Please summarize the algorithm used by Lotta_rye the algorithm is straight forward. first, i fill the two numbers in a ticket, then i use recursion to generate remaining digits in the ticket. after filling out a number(1= n, the existing set of tickets is sufficient. If m*l < n, we produce additional tickets to cover all possible combinations of k numbers out of (n-m*l). This step is done using a simple greedy algorithm. One thing worth mentioning about my solution is probably that the programming is quite general. The program should also work with (m,k) != (7,3). This hasn't been tested very much, though... ++ Do you have any good references to recommend? Nope. ++ If I had it to do all over - here's what I would try .... Try to find more time to think about the problem. My first version needed over 60 tickets for n=25. The second version with the above algorithm reduced the number of ticketes to 11, which is significant. I suppose further analysis could have brought me down to 9, but I have no time. Sigh. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? See below. Yes, I did it for fun. ================================================================= ============== 39 ====================== sevens ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- sevens 145 13686 10.63 c Aivars Zogla ================= sevens submitted by Aivars Zogla at fix.lv!uvsk@kcig2.att.att.com ================= ++ Please summarize the algorithm used by sevens As far as POTM is for fun it was interesting to build some funny algorithm as well. I simply try all triples possible with all numbers but last 14 which always make 2 tickets. After a bunch of tickets (no more then 1000 for N<=50) is selected, all these tickets are printed out (array is cleared) and selecting of triples continues from that point. Then I noticed oscillating nature of ticket count when using different volume of that bunch. So, program makes 3 runs with different volume of tickets' bunch: with differences 100, 10 and 1. Best interval (smallest total number of drawn tickets) selected is best and makes result. ++ Do you have any good references to recommend? Oh, yes! Debug window. ++ If I had it to do all over - here's what I would try .... Test everything again and again. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? For those, who have no references on this topic: Teacher of informatics at Ugale Secondary School. In fact, my subject is physics. I have switched for a while and I'm going to return to physics teaching. Ugale is where Sandis Prusis comes from :) Not a secret. They say, one man will easily give a drink for thousand of camels if they are thirsty, thousand men couldn't give a drop of water for one camel which doesn't want to drink. ================================================================= ============== 40 ====================== tix ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- tix 383 49765 10.96 c Eric Weeks ================= tix submitted by Eric Weeks at weeks@chaos.ph.utexas.edu ================= ++ Please summarize the algorithm used by tix I misread the question, and thought I had to have every possible triple appearing at least once in my tickets, rather than just a triple matching at least one triple in the King's ticket. I quickly realized my mistake (seeing entries with 9 tickets), but didn't have a chance to correct it as I got busy changing jobs and moving. ++ If I had it to do all over - here's what I would try .... It was a good problem, I wish I had had the time to try to solve the correct problem rather than the problem I tried to solve. Maybe the next POTM I'll have more time to work on it. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Now I'm at U Pennsylvania, working in a physics laboratory. Despite my pokey behavior on this POTM I do plan to enter future POTMs, time allowing! ================================================================= ============== 41 ====================== lottoluck ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- lottoluck 383 50166 2.57 c Edwin Berlin Sorry ... no description available for lottoluck ================================================================= ============== 42 ====================== TicketToElbonia ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- TicketToElbonia 512 69033 .35 c Sam Wilson Sorry ... no description available for TicketToElbonia ================================================================= ============== 43 ====================== triceratops ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- triceratops 632 83495 .66 c Earl Chew Sorry ... no description available for triceratops ================================================================= ============== 44 ====================== Olimpas ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Olimpas 809 95189 .25 c Mantas Puida Sorry ... no description available for Olimpas ================================================================= ============== 45 ====================== Bingo ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Bingo 1302 123396 .19 c Rags Viswanathan ================= Bingo submitted by Rags Viswanathan at ragsv@india.hp.com ================= ++ Please summarize the algorithm used by Bingo It is a simple Number Generator. Just crunches out all combinations. It picks the ones that are 'Mandatory' to "Cover" all the combos. ++ Do you have any good references to recommend? Yeah !. Sure. ragsv@india.hp.com. Just Kidding. I dont have any references. ++ If I had it to do all over - here's what I would try .... Take a Long Flight (say B'lore to NY) with a notebook , pencil and a print out of Fred's Mail on the rules and start attcking the real problem. I did "a solution" to be a 'Also Ran'. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Company=>Tata Consultancy Services. Location=>Bangalore,India. Job=>Software Engineer. Do for Fun=> For fun,I sing for My kid -Pranav. Inner most secret=> How much can you pay for it, Bud ???. Let's workout a deal and U will get it. ================================================================= ============== 46 ====================== Brute_Remorse ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Brute_Remorse 1302 222936 2.44 gC Chad Hurwitz Sorry ... no description available for Brute_Remorse ================================================================= ============== 47 ====================== frisbee ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- frisbee 1302 222936 3.29 PERL Andrew Schexnaydre ================= frisbee submitted by Andrew Schexnaydre at aschex@gsci.belvoir.army.mil ================= ++ Please summarize the algorithm used by frisbee The only thing I can say is that algorithm is probably not the best word to describe my program. look at it now and wonder what in the world was I thinking. ++ Do you have any good references to recommend? ++ If I had it to do all over - here's what I would try .... ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? ================================================================= ============== 48 ====================== Ticketmaster ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Ticketmaster 1302 222936 35.14 c Guy Oliver Sorry ... no description available for Ticketmaster ================================================================= ============== 49 ====================== NiceTry ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- NiceTry 1302 222936 80.44 gc Seth Rothenberg Sorry ... no description available for NiceTry ================================================================= ============== 50 ====================== something_clever ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- something_clever 5456 398288 .37 gc Don Dykes ================= something_clever submitted by Don Dykes at dykes@pobox.com ================= ++ Please summarize the algorithm used by something_clever Well, I misunderstood the problem, so the method wasn't very good. My best effort after that submission was a reduction to 9 tickets with a sum of 670. Since there were many 669 sums, and my nine ticket solution could not be renumbered down to 669, I didn't bother submitting the revision. The 9 tickets I got were 1 2 3 4 5 6 7 ; obvious first choice. but any first ticket is just as valid 8 9 10 11 12 13 14 ;building a "block" 15 16 17 18 19 20 21 ; only leaves 22-25 1 2 3 4 5 22 23 6 7 8 9 10 22 23 11 12 13 14 22 23 24 1 2 3 4 5 24 25 6 7 8 9 10 24 25 11 12 13 14 22 23 25 The last six "squeeze" the evil king (trying to pick one I don't have) by forcing him to pick no more than 2 from each of the first three, leaving him with the need to pick only one from the last 4 (22-25). There are several cases here. He can pick 1 from only one of the first three tickets and he must then pick 2 from the others and he must pick 2 from the 22-25 set. Or he can pick 2 from each of the first 3 tickets and then only pick one from the 22-25 set. Picking zero from any of the first three, or picking one from more than one would require him to pick more from the 22-25 set. Picking all 4 from 22-25 will get caught by tickets 6 or 9. If he picks 3 from the 22-25 set, he will be caught when he picks 1 from either of the first two tickets. If he picks any 2 from the 22-25 set he can pick 1 from the first three, but he must then pick 2 from each of the remaining tickets. Again, he will be caught since there isn't enough gap not to violate one of the tickets. The same is true for only one chosen from the 22-25 set. This pattern yields a sum of 768. However, each of the numbers is the same as any other, so replacing most frequently used with smaller numbers yields: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 19 20 21 22 23 24 25 1 2 3 4 5 6 7 1 2 8 9 10 11 12 1 2 13 14 15 16 17 3 4 5 6 7 17 18 8 9 10 11 12 17 18 1 2 13 14 15 16 18 which has a sum of 670. ++ Do you have any good references to recommend? I wish. ++ If I had it to do all over - here's what I would try .... I would start earlier on area mapping and building vast arrays of "covered" values. I haven't been able to think of a clever way to solve it, so I would probably resort to using many machines to attack the problem in a fairly brute force method. Constructing the 3 ball combinations I planned to win with, then creating tickets that had those combinations. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I live in Houston. I enjoy ham radio and shooting. This POTM was a very good puzzle and I look forward to hearing about other efforts. It would have been nice to have a shorter duration for the problem, since I haven't really worked on this for some time and became distracted with other things (work is like that). ================================================================= ============== 51 ====================== J3lottery ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- J3lottery 5456 398288 1.54 PERL Jason Nichols ================= J3lottery submitted by Jason Nichols at jcubed@jcubed.com ================= ++ Please summarize the algorithm used by J3lottery I kept the first 4 numbers static and ran through the other numbers having the first number(a) run from 1 to N, the second(b) run from a to N-1, and the third(c) run from b to N-2 ++ Do you have any good references to recommend? unfortunately, no. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I work for Lexmark International supporting their printers. I also moonlight as a web designer for my own company, J Cubed. I currently live in Richmond, KY. I have been in KY all of my life (22 yrs). I am married and have three children. Only one is mine, married into the other two. For fun, when I have time for it, I tinker with my computers. I have four computers operational in my apartment. My wife has one and won't let me touch it. Two of them are NT 4.0 servers and the other one is a Linux box. ================================================================= ============== 52 ====================== POTM_Emporer ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- POTM_Emporer 999999 0 gc John Guo Sorry ... no description available for POTM_Emporer ================================================================= ============== 53 ====================== LottoMan ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LottoMan 999999 0 .08 PAS Darren Davis ================= LottoMan submitted by Darren Davis at jpdavis@webspan.net ================= ++ Please summarize the algorithm used by LottoMan Believe it or not, after 4 months, I didn't have time to work on this problem. All I did (and finally in Pascal) was print out 10 random tickets. ++ Do you have any good references to recommend? No. ++ If I had it to do all over - here's what I would try .... Actually getting around to working on it. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a Junior at Marlboro High School in Marlboro, New Jersey. ================================================================= ============== 54 ====================== LuckAssure ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LuckAssure 999999 0 .08 c Vikram Sreeram Sorry ... no description available for LuckAssure ================================================================= ============== 55 ====================== MERLOT ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- MERLOT 999999 0 .09 c Elizabeth Ross Sorry ... no description available for MERLOT ================================================================= ============== 56 ====================== LOTO-OPTIMIST ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LOTO-OPTIMIST 999999 0 .09 c Le_Kim Quoc_Phong Sorry ... no description available for LOTO-OPTIMIST ================================================================= ============== 57 ====================== noentry ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- noentry 999999 0 .10 N Luc Kumps Sorry ... no description available for noentry ================================================================= ============== 58 ====================== The_Lucky_Draw ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- The_Lucky_Draw 999999 0 .11 gc S. Arun ================= The_Lucky_Draw submitted by S. Arun at ee96147@cycles.ee.iitm.ernet.in ================= ++ Please summarize the algorithm used by The_Lucky_Draw For 7<=N<12, only one ticket needs to be printed: 1 2 3 4 5 6 7 For N=12, the following additional ticket has to be printed: 8 9 10 11 12 1 2 for N=13, the following additional ticket has to be printed: 8 9 10 11 12 13 1 For 14<=N<17, only the following two tickets are required: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 For 17<=N<22, in addition to the above two tickets, fill out another ticket with numbers starting from 17 upto N and the remaining vacancies (if any) are to be filled with 1,2,.. Hence,for N=21, the tickets will be like the following 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 I use these three tickets ( or these 21 numbers ) as my basis for all other numbers. Taking N=22, if I printed just the above three tickets, I may lose as the 7th number chosen could be 22. Therefore, I fill out some more tickets such that if the king chooses 22, then it so happens that two other numbers in that ticket have already been chosen. So for N=22, the extra tickets printed will be 22 1 2 3 4 5 6 22 7 6 5 4 3 2 22 1 7 - - - - where - indicates any number will do. Continuing this process, for N=23, the extra tickets, besides the basis tickets mentioned at the top of this letter will be 22 23 1 2 3 4 5 22 23 7 6 5 4 3 22 23 1 2 6 7 - For N=24, the extra tickets will carry 22, 23, 24 as their first three entries and the remaining will be all possible 4-number combinations of 1,2,3,4,5,6,7. However, when it comes to N=25, for minimum number of tickets, the numbers 8-14 should also be considered. Now the extra tickets will be 22 23 1 2 3 4 5 22 23 7 6 5 4 3 22 23 1 2 6 7 - 24 25 8 9 10 11 12 24 25 14 13 12 11 10 24 25 8 9 13 14 - When N=26, it is treated as the same case as N=24. So tickets with 22, 23, 24 and 25, 26 are generated. When N=27, it is treated the same way as above and tickets with 22, 23, 24 and 25, 26, 27 are generated. When N=28, tickets with 22, 23, 24 are generated followed by tickets with 25, 26 and 27, 28 are generated. For tickets with 27 and 28 as their first two numbers, all possible 2-number combinations of 15-21 are used. For N=29, the tickets will be of the following form 22 23 24 * * * * 25 26 27 * * * * 28 29 * * * * * where * denotes all possible combinations of the numbers being used. For N=30, the tickets will be of the following form 22 23 24 * * * * 25 26 27 * * * * 28 29 30 * * * * For N=31, the tickets will be of the following form 22 23 24 25 * * * 26 27 28 * * * * 29 30 31 * * * * For N=32, the tickets will be of the following form 22 23 24 25 * * * 26 27 28 29 * * * 30 31 32 * * * * For N=33, the tickets will be of the following form 22 23 24 25 * * * 26 27 28 29 * * * 30 31 32 33 * * * For N=34, the tickets will be of the following form 22 23 24 25 26 * * 27 28 29 30 * * * 31 32 33 34 * * * For N=35, the tickets will be of the following form 22 23 24 25 26 * * 27 28 29 30 31 * * 32 33 34 35 * * * For N=36, the tickets will be of the following form 22 23 24 25 26 * * 27 28 29 30 31 * * 32 33 34 35 36 * * For N>36, the tickets will be of the following form 22 23 24 25 26 * * ( * * indicates all possible combinations of [1,7] ) 27 28 29 30 31 * * ( * * indicates all possible combinations of [8,14] ) # # * * * * * ( * * * * * indicates all possible combinations of [15,21]) where # # indicates all possible combinations of 32, 33 , 34 uptil N After generating all the tickets, the numbers are sorted so that the least sum is obtained. ----------------------------------------------------------------------------- ++ If I had it to do all over - here's what I would try .... ---- I have no more ideas! ++ COMPANY? ------ Not Applicable --------- LOCATION? ------ Bangalore, India. JOB? ------I am a second year B.Tech (Bachelor of Technology) student (Electrical Engineering) at the Indian Institute of Technology(IIT) Madras,Chennai DO FOR FUN? ------ Well, to some extent. ------ Participating in the POTM has improved my programming skills INNERMOST SECRET? ------ Nothing! If I had told it out, it would no longer be 'secret'! ================================================================= ============== 59 ====================== TroubleWithTriples ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- TroubleWithTriples 999999 0 .11 C R.Saint S.Weldon ================= TroubleWithTriples submitted by R.Saint S.Weldon at saint@phoenix.net ================= ++ Please summarize the algorithm used by TroubleWithTriples Scott's comments (this was mostly his algorithm) The number of Balls is divided into 3 subsets. Example for Number of Balls=25, the subsets could be 1-9,10-18, and 19-25. Of the seven balls drawn by the king, at least 3 must be in at least one of the subsets. For each subset, create tickets that include all possible combinations of 3 balls in that subset. If you do this, you are guaranteed a solution to the problem. Need to optimize the choice of the subsets, and how to generate tickets that cover all combinations of 3. One way is brute force. Look at all the possible combinations of 3, and create new tickets as needed. However, we found this task can be sped up by further subdividing the subset into 2 parts, A and B. Example, for the subset of numbers 1-9, let A be 1-5 and B be 6-9. Any combination of 3 balls must fall into one of 4 categories: i) 3 balls from A ii) 2 balls from A and 1 from B iii) 1 ball from A and 2 from B iv) 3 balls from B So if we generate tickets covering all 4 of these possibilities, we have also covered all to the subset. Example the two tickets: (1,2,3,4,5, 6,7) and (1,2,3,4,5, 8,9) satisfy all possibilities of case (ii). The two tickets (1,2,3, 6,7,8,9) and (4,5,x, 6,7,8,9) satisfy all possibilities of case (iii). In this case, because A and B are small, cases (i) and (iv) are also included in the above, so 4 tickets completely covers the subgroup of 9 balls. For larger A and B, the process can work by iteration to determine (i) and (iv). Similarly, to help determine all combinations of two balls, group A for case (ii) (or B for case iii) can be further subdivided into 'a' and 'b' and then we need to satisfy all possibilities of -) 2 balls from 'a' -) 1 ball from 'a' and 1 from 'b' -) 2 balls from 'b' Again, the first and third condition can be iterative until the case is small enough to be evident. The trick is determining what grouping of three subsets gives the best result, and how to divide into A and B and 'a' and 'b'. We generally determine this by trying all combinations and picking the best. Randy's Comments I decreased our ticket count by generating the ii) 2 balls from A and 1 from B, and iii) 1 ball from A and 2 from B first. Then, since some of those covered certain triples from i) 3 balls from A and iv) 3 balls from B, I was able to only use the necessary tickets to cover the rest of the triples. ++ Do you have any good references to recommend? How to write error free software? ++ If I had it to do all over - here's what I would try .... Randy's Comments: I would test the program completely, and remove all debug printf() statements! I made the fatal mistake of inadequate testing. For the solution for N=37, the program hits a line of code to print a debug statement. So the program failed in the first round. If I had commented that printf() out, then we would have gotten 41 tickets for N=37. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Scott Weldon is an actuary and international consultant for Watson Wyatt, and provides advice to multinational companies on pensions and employee benefits. He is a recent resident of Chicago, returning to the midwest after living and working in Paris France for eight years. For fun: plays games, and likes to dance. Randy Saint is a Software Manager at Lockheed Martin working for NASA at Johnson Space Center, Houston TX. They don't let me write any code at work, so this is my only "outlet." The name, TroubleWithTriples came out of a brainstorming session with my wife, Marianne. If you ask her, she came up with the idea. She's not even a Star Trek fan. ================================================================= ============== 60 ====================== Prince ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Prince 999999 0 .12 c Brandon Crosby Sorry ... no description available for Prince ================================================================= ============== 61 ====================== LuckyDip ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LuckyDip 999999 0 .12 c Roy Lett ================= LuckyDip submitted by Roy Lett ================= ++ Please summarize the algorithm used by LuckyDip Simplicity and luck. I just generated sets of random picks given the input. Fast but not very scientific/mathematical. My first POTM entry, I wanted something quick and dirty to start with to find compiler issues. Then, it went like what I guess is typical for many, planning to make further changes I just ran out of time (the day job!). ++ Do you have any good references to recommend? General mathematics texts. ++ If I had it to do all over - here's what I would try .... I'd get my mathematician pal involved and put in a joint entry. ++ COMPANY? Lucent Technologies LOCATION? Naperville, IL, USA JOB? Software development DO FOR FUN? Football (US=soccer), Laser racing (sailing), etc. INNERMOST SECRET? I'm a bit of a Nintendo 64 fan, I've found all 120 stars in Super Mario 64 and completed Goldeneye. ================================================================= ============== 62 ====================== IMayAlreadyBeAWinner ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- IMayAlreadyBeAWinner 999999 0 .13 c Phil Gregory ================= IMayAlreadyBeAWinner submitted by Phil Gregory at pgreg430@neors.cat.cc.md.us ================= ++ Please summarize the algorithm used by IMayAlreadyBeAWinner Bleah. I was using a straight combination algorithim. It basically took every possible three-number combination and made sure that that combination appeared on at least one card. ++ If I had it to do all over - here's what I would try .... If I had more time, I would have worked out the answers to greater numbers of numbers to see what the numbers of tickets were. There's probably a solution in there *somewhere*. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Delta Resources MD Program in SuperBase--ick. Program in C, read. If I told you, then it wouldn't be a secret, now would it? None. My mind isn't that devious. ================================================================= ============== 63 ====================== Two_Adder ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Two_Adder 999999 0 .23 PERL Nick Hildenbrandt Sorry ... no description available for Two_Adder ================================================================= ============== 64 ====================== LOTO_WINNER ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LOTO_WINNER 999999 0 .45 c Tong Nghia Sorry ... no description available for LOTO_WINNER ================================================================= ============== 65 ====================== lotto ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- lotto 999999 0 .48 c Jimmy Hu > ================= > lotto submitted by Jimmy Hu at njhua@silcom.com > ================= > ++ Please summarize the algorithm used by lotto First, split the numbers into 3 groups: this causes the king's ticket to contain at least 1 triple from one of the groups. Then try and cover all the triples in each group. It turns out that covering all the triples in a group containing N numbers with tickets holding 7 numbers is like covering a circle of radius N with circles of radius 7. (Try it, it's hard). It's probably one of those NP complete problems that take exponential time to figure out the best solution. So what I tried to do is to reduce the N numbers by 1,2, or 3. In order to do this, I set the last 1,2, or 3 numbers and then create all doubles with the remaining slots. For instance, if N = 10, I try this: X X X X X X 10, where in the X's I generate all doubles with the numbers 1-9. I also try: X X X X X 9 10, where in the X's I generate all doubles with the numbers 1-8, and: X X X X 8 9 10, where in the X's I generate all doubles with the numbers 1-7. Let's say N=30. I start by trying to find the best way to get to N=29. The only way is to take N=30 and eliminate one number (with X X X X X X 30). Then I look at N=28. To get here, I either start at N=30 and eliminate 2 numbers, or start at N=29 and eliminate 1 number. I continue down N=27 down to N=7. When only 7 numbers are left, I know that 1 2 3 4 5 6 7 will finish it off. I have a nice optimize stage at the end where I take the histogram of the usage of the numbers. Then I optimize the tickets so that the most used number gets 1, and the least used number gets N. This just insures that the sum of the numbers is as low as possible. But of course the tickets are another matter! > ++ Do you have any good references to recommend? No, I didn't use any references to do this problem. Maybe I should have! > ++ If I had it to do all over - here's what I would try .... I didn't have enough time to even complete my program! It didn't even work on N=37! So if I had more time I would make it work, then I would maybe try to think about how to do it better. My divide and conquer algorithm is fast, but it doesn't find good answers. For generating triples from 1-12, I myself found a 11 ticket answer whereas my program could only do 12 tickets! I could see where it was going wrong, but to do better seemed to require taking an unacceptable amount of time. > ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? It's interesting... I've done the inverse boggle program without ever hearing about it from the POTM. It was one of the ideas for my company's recruiting test. (My company likes to come up with difficult programming tests for recruits). I have several ideas that could be good POTM contests. Just as long as they are ruled out for my company first! ================================================================= ============== 66 ====================== LGVNWINH ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- LGVNWINH 999999 0 .66 PAS Tran Hoang Sorry ... no description available for LGVNWINH ================================================================= ============== 67 ====================== Lot_O_Tickets ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Lot_O_Tickets 999999 0 1.95 c Beth Wilson Sorry ... no description available for Lot_O_Tickets ================================================================= ============== 68 ====================== Indian_lottery ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Indian_lottery 999999 0 1.96 JAVA Raja Kannan ================ Indian_lottery submitted by Raja Kannan at karun@giasmd01.vsnl.net.in ================= ++ Please summarize the algorithm used by Indian_lottery The algorithm used by Indian_lottery is simple, but iam not sure whether it works until i recive the final standings. the logic behind that is i converted the given numbers into 3x7 matrix say for example 1,2,3,4,5,6,7 8,9,10,11,12,13,14 15,16,17,18,19,20,21 22,23,24,.... and so on. then i added the each row from next matrix to the all the matrix above it, see in that case; 22,2,3,4,5,6,7 23,9,10,11,12,13,14 24,16,17,18,19,20,21 and then transformed it two times, and the output is taken, like this 22,23,24,2,9,16,3 10,17,4,11,18,5,12 19,6,13,20,7,14,21 22,10,19,23,17,6,24 4,13,2,11,20,9,18 7,16,5,14,3,12,21 the final is output is taken frm the first row f the later matrix and all the rows from the sooner matrix. so the output is, 1,2,3,4,5,6,7 8,9,10,11,12,13,14 15,16,17,18,19,20,21 22,23,24,2,9,16,3 22,10,19,23,17,6,24 4,13,2,11,20,9,18 7,16,5,14,3,12,21 ++ Do you have any good references to recommend? Mr.Sundar Garg, president , SAlem Associates Inc, atlanta. ++ If I had it to do all over - here's what I would try a better way. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Salem Associates India Pvt Ltd chennai , India. software engineer no, actually i really get enthuiaistic when i get into contests like this, iam getting good logics and good programming style when i program these kinds of complex programs. my innermost secret is i can make logics faster and makes it work thru programming. iam innovative and can create new things, for example i wrote one of your contest problem (cross-word making) in my college days (4 years back) and luckily got a prize for that in a software presentaion contest. i found in one of the magazine saying about ur POTM and some of the problems you hosted. when i browsed ur pages i found one such problem has been hosted and iam unlucky that problem was over long back, otherwise i would have usd my old program for that. ================================================================= ============== 69 ====================== Rabbits ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- Rabbits 999999 0 5.83 c Victor Udovenko Sorry ... no description available for Rabbits ================================================================= ============== 70 ====================== copycat ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- copycat 999999 0 5.92 C Neal Palmer Sorry ... no description available for copycat ================================================================= ============== 71 ====================== shoe_in ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- shoe_in 999999 0 8.14 gC Andy Olsen ================= shoe_in submitted by Andy Olsen at aolsen@twisto.compaq.com ================= ++ Please summarize the algorithm used by shoe_in shoe_in would pick tickets one at a time, and pick numbers for that ticket one at a time. It used a very simple algorithm to decide which number to pick next, which tried to pick numbers that had been used least frequently, and tried not to put the same combination of numbers on more than one ticket. Here's a consoling thought to all those who didn't quite reach 9 tickets: I was frustrated one day and decided to try a new algorithm... totally random number picking. This approach failed to generate a solution in 30 tickets (I stopped the program after that). So take heart, you are smarter than a monkey picking randomly! ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? ================================================================= ============== 72 ====================== hatchance ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- hatchance 999999 0 30.22 JAVA George Adams ================= hatchance submitted by George Adams at GeorgeA@trellix.com ================= ++ Please summarize the algorithm used by hatchance If it makes any sense to talk of dividing algorithms into "discrete" and "statistical", of the many I tried, the best results I obtained were by a statistical approach. As 7-tuples were chosen from the N numbers, a set of use-counts were kept for the individual numbers, the pairs of numbers and the triplets of numbers. Among my many detours, I developed a compact, invertable enumeration of n-tuples drawn from N-combinatoric-n. This allowed me to do the use-count book keeping. I won't swell this e-mail with an attempt to show all the calculations but suffice it to say that. 1. when any 7-tuple is considered for purposes of this problem, it has a "shadow" of other 7-tuples that it covers in the sense that those others have at least one triplet contained in the chosen 7-tuple. 2. any two 7-tuples have some degree of overlap to their shadows, even disjoint subsets of the N numbers. The more numbers they have in common, the greater the overlap of their shadows. 3. The collected 7-tuples chosen up to some point may be said to have a collective shadow. 4. a weighted sumation of the single, pair and triplet use counts that would result if a given, potential, 7-tuple ticket were added to the collected set of tickets constitutes a score for that potential ticket. of all the 7tuples that could be formed, the one with the lowest score represents the choice that has the least overlap with the collective shadow. 5. With little more than an appeal to common sense to back up this assertion, I claim that the least amount of shadow overlap I can find means I have the most efficient coverage. But this is only a statistical argument, not one that leads to the construction of a set of tickets. 6. Exhaustive scoring of potential tickets , re-iterated after each choice is made and cut off when the use counts reach a predermined threshold is then the basic algorithm I use. It gives the result of 14 tickets for N=25 and takes a damn long time to compute. This is why I am not submitting a correction to my original, buggy submission. This algorithm's compute-time grows at an almost factorial fashion, another reason I'm not submitting it. On the other hand, I trust it to find a reasonably tight upper bound on what ever value would be the winning selection of tickets. ++ Do you have any good references to recommend? Lady Luck, an old Dover paper back, has some good sounding bibliographic suggestions, none of which I had time to look up and read. ++ If I had it to do all over - here's what I would try ....I would start earlier and I would have looked for a discrete approach...statisitical approaches can only approximate an optimum selection of tickets and cant give you any information that would drive a refinement of the set that is chosen. I knew all of my discrete algorithms were weak when I noticed that of 6 or 7 that I tried, each had some value of N where it out performed the others.... TRY THE WHOLE RANGE before you assume you have a winner! ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Trellix Corp. Waltham, MA. I write the HTML export and printer code for our nifty I mountain bike and write VB applications to unwind. Latest vb app is a data analysis utility that can plot and correlate multiple data sets and allow users to smooth the data, work with the differentials instead of the values and time shift the relation between the data sets. POTM ideas? light weight, "no-key" encryption filters for personal e-mail. Ever looked at "modulo-N Fibonacci series" and how it partitions N into disjoint subsets of cyclic sub-series? My innermost secret is no secret: life is incredibly short considering all that I could do and want to do. ================================================================= ============== 73 ====================== blotto ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- blotto 999999 0 stack c Warren Montgomery ================= blotto submitted by Warren Montgomery at warren@ans.ih.lucent.com ================= ++ Please summarize the algorithm used by blotto I'll be fascinated to see the other submissions here as I never discovered a 9 ticket solution to the 25 number lottery, let alone an algorithm that produces it. I found no easy way to deal with the partial match condition (i.e. the fact that the king draws 7 numbers, only 3 of which must match your ticket), and so took an approach that avoided it: Assume that a solution for 17 or more numbers must contain 2 non-overlapping tickets. (I believe this can be proven, but didn't go about doing it). Then if a draw by the king has no matches, it can contain at most 2 numbers from each of the two chosen non-overlapping tickets, and must therefore contain 3 numbers from the remaining N-14. Picking enough tickets to cover all 3 number combinations in the N-14 remaining numbers will therefore guarantee to cover all the king's tickets. The resulting algorithm is thus: For N>14 a) Create a bitmap (N-14)X(N-14)X(N-14) to track covered combinations, as well as counts to track for each i =4 even numbers, and those with >=4 odd numbers, and then cover the "even" tickets and the "odd" tickets separately. If the chosen N is even, then you can save some work by using symmetry. This was a very nice problem (simply stated but complex to solve). ++ Do you have any good references to recommend? I looked into computer science resources but ended up trying mostly ad-hoc approaches. ++ If I had it to do all over - here's what I would try .... Different kind of partitions of the ticket-set-space.. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Millsaps College/Jackson, Mississippi/Who has time for fun?/ Innermost secret: I had a closed-form solution for the minimum number of tickets for the general case, but Fred didn't provide enough room in this form to write it down. ================================================================= ============== 84 ====================== jabri_mamu ============= ================================================================= ENTRY SCORE SUM TIME Programmer - time (sec) ------------------ ----- ----- ---- ------------------------- jabri_mamu 999999 0 5332.02 gC Neelkanth Natu ================= jabri_mamu submitted by Neelkanth Natu at natu@cromp.ernet.in ================= ++ Please summarize the algorithm used by jabri_mamu Not a very sophisticated one. A real BRUTE force one.Thats why it took 200 odd seconds from the N=25 run. I just calculate all the Nc7 combinations that might be selected by the king (which takes a mammoth amount of time). Then I check if I have in my set of lottery tickets at least one 3 digits combination in the current Nc7 th combination. If YES then I just go over to the next one. If NO then I add the current Nc7 th combination to my list of selected tickets. After a few tries I found out that if the combinations 1234567, 8 9 10 11 12 13 14, etc were included in the set of tickets then the number of tickets is reduced drastically. I also tried my hand at a few theoretical formulae but none was satisfactory enough to earn me the box of chocalates. ++ If I had it to do all over - here's what I would try .... I'd make a beeline for the local Maths Guru. Thats what I would do. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? CG CoreEl Logic Systems Limited. 1181 Surya Bhavan, Fergusson College Road Pune 411005 INDIA Design Engineer in the systems hardware group. I did this because I love challenges and most of all C,C++ programming. Innermost Secret: I feel jealous of all those who have had the chance to work with Kernighan, Ritchie ,Thomson ,stroustrup and all those wonderful guys out there in the AT&T Bell Labs. =================================================================