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.

=================================================================


  


The POTM is unsponsored and just for fun.       Monday 06:46:54 PM      Copyright © 2004-6 - Fred Hicinbothem