|
|
Entry Summaries
The attached mail is the collection of write-ups I received. As usual
they are mostly unedited (only personal POTM-master insults were removed).
Write-ups are provided in order of finish (more or less).
KING'S LOTTERY Program entry descriptions
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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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 -at- 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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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-at-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.
=================================================================
|
