THE LOTTERY

The country of Elbonia runs a weekly lottery. To enter, you pick seven numbers. Then the King picks seven numbers out of a hat, if your ticket has three or more of the King's numbers on it - YOU WIN!! How many tickets do you have to fill out to guarantee a win?

I'll tell your program how many numbers are in the King's hat, and your program will "fill out" a bunch of lottery tickets. If your tickets guarantee a lottery win, and your program needs fewer tickets than anyone elses - you may win the next POTM!!!


Thanks for this idea go to Luc Kumps and Alfons Lievens from Belgium. By the way - if anyone can offer an equation and proof that derives the minimum number of tickets (given N, M, and K), Luc has offered a GIANT box of Belgian chocolates ... mail to me and I'll send it to Luc! (N, M, and K are defined in section II below)

Now on to the long rules. As always, the intent is to clarify the rules and to close any loopholes - generally the POTMs should be assumed to be fairly straightforward, but if you have any questions just send them to me and I'll answer them in the weekly FAQ ...


I.  THE ELBONIAN LOTTERY RULES AND REGULATIONS

	1) The King will place N balls in a "hat".  Each of the
	   balls will have a different number on it.  The numbers
	   will begin at ONE and run sequentially through to N.
	  
	2) To enter the lottery, you fill out a "ticket" on which
	   you select SEVEN different numbers, each of which may
	   range from ONE to N.  Your program will fill out your
	   tickets for you, and it may fill out as many tickets
	   as you wish.

	3) The tension mounts.  The King approaches the podium
	   and selects SEVEN balls (randomly) from the hat 
	   representing SEVEN different numbers.

	4) You WIN the LOTTERY if one of your tickets has THREE or more
	   of the King's numbers among the SEVEN on the ticket.  You
	   WIN the POTM if you filled out fewer tickets than anyone
	   else, but enough tickets to guarantee that you'd have at 
	   least one ticket with the winning three numbers on it!

II.  YOUR PROGRAM AND YOUR TASK

	1) M=7 is fixed.  This is the number of selections on each of
	   your entry "tickets" and the number of balls the King picks.
	2) K=3 is fixed.  This is the number of the King's numbers that
	   you must match on your ticket in order to "win" the lottery.
	3) N is the number of balls, each with a unique number on it,
	   that the King has in his hat.  The balls are numbered from
	   ONE up to (and including) N.  N will be provided to your
	   program at run time.  N will be greater than SEVEN and
	   less than or equal to TWO HUNDRED.  ( 8 <= N <= 200 )

	Your program must take a single argument of the value 
	defining N ... for example, I may execute:

		entryname 100

	if the king has 100 balls in his hat.  Your program must
	read this argument and then print out your ticket selections.

	1) Your program must print out your ticket selections with
	   one selection on each line - where a selection consists 
	   of a set of exactly SEVEN unique numbers.
	2) You may print out as many tickets as you wish, one per line.
	3) Each ticket (line) MUST contain seven DIFFERENT numbers.
	4) Your collection of tickets MUST guarantee a win for every
	   possible set of SEVEN numbers the King can pick.
	5) Each output line (or ticket) will contain SEVEN different
	   numbers separated by white space, for example, 2 tickets 
	   might be:

		7 24 92 16 1 88 100
		16 7 92 99 3 4 5

	6) Do not print out any blank lines or extra output besides
	   the collection of tickets - one per line!

III.  SOME RESTRICTIONS TO MAKE YOUR JOB HARDER

	1) You may NOT pre-compute solutions and simply print
	   them out ... not even for the system test problem!
	2) You must complete your task in less than ten minutes.*
	3) Your source code must be less than 25K bytes.*
	4) Your executable must be less than 1M bytes.*
	5) All tickets go to standard output ... nothing may
	   be printed to standard error.

	   *approximately ... I will be the sole judge.

IV.  THE FINALS AND THE SCORING

	For the finals, I'll pick a value of N <=200 and run all the
	programs.  I'll examine the ticket collection that each
	prints out to insure complete coverage of all possible
	drawings by the King.  If the entry exhibits complete coverage
	and completes within a reasonable approximation of ten
	minutes and is of the requisite size, it will be scored.

	** THE POTM WINNER will be the program that printed out
		the fewest number of tickets satisfying requirements.

	** In the event of a tie (two or more programs print out
		the smallest number of tickets), I'll add up all the
		numbers on all the tickets - the collection with the
		SMALLEST total will win the POTM.

	** If still tied, the FASTEST program will win - as measured
		by system+user time using the timex (times) command.

    Because of the difficulty involved with scoring large values of
    N, I have decided to conduct the finals in three rounds as follows:

    ROUND 1:  All programs will be run with a value of 2510 minutes are eliminated)
    ROUND 2:  All remaining programs will be run with a value of 5110 minutes are eliminated)
    ROUND 3:  All remaining programs will be run with a value of 101>>      IMPORTANT:  submit early so we can resolve any
>>>      portability problems!!!  (Particularly if you 
>>>      are working in a PC environment.

       NOTE: assembly code submissions are NOT acceptable.  I must be
       the one to compile your code so I can check for cheating!

    c) if you wish to submit a shell program, Bourne, Korn, and csh
         are available ... along with any bin or /usr/bin tools that
         are available as generic Unix tools - my judgement!!!
	 Also nawk, awk, dc, or whatever.
         (again - submit early in case there are version differences)

    d) Temporary files may be created in /tmp, but MUST be removed
         when you are done ... creation of files anywhere else is
         strictly prohibited.

    e) Maximum size of the source code is roughly 25K characters - 
         different rules may apply for specific POTMS, and 
         comments don't count against you.

    f) Maximum size of executable is 1 Megabyte ... please!!!!

    g) Maximum malloc'able space is a bit over 50 Meg ....

    h) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1

    i)	 a    = 0x80000000  = -2147483648
         a - 1 		    =  2147483647
         a + 1 		    = -2147483647
         {a} is true.	{a == 0} is false.

II.  The system testing ....
    
    a) mail me an entry as soon as possible - you can always submit
         another entry if you improve your solution .. but try and
         keep it down to one a week once the porting issues are 
	 resolved .... please!

    b) one entry per person (or team) please.  I associate each entry
         name with an email address and a person for communication
         purposes.  Communication is fine - and encouraged - but
         everyone's code should be their own unless there is a
         stated collaboration and a single team entry.  Honor system!

    c) on receipt of your entry, I'll run a system test to make sure
         your program works ... you'll receive the results and
         a weekly standing of how you fared against other entries.
         (I usually will get to new mail once a night but perhaps not!)

    d) please make sure your program works on the system test problem.

    e) your program must perform the task specified within 10 minutes
       sys+user time as measured by timex on MY execution system.
       Your time will be provided along with your system test run
       so you can see the differences in speed between yours and mine.
       All execution time measurements used for tiebreakers (if any)
       will be measured using  time via timex (similar to
       time command).  
       
       ===>	NOTE: A code fragment to measure elapsed time
       ===>	      is available from the POTM-master for the asking.

III.  SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!

   Please email (not uuto, no attachments) your source code to me at:

         enter@potm.ffast.att.com		(preferred)
         hicinbothem@att.com		 (use only as a last resort!)

    IMPORTANT:  Please use the following (or equivalent) lines at the
    front of the program you mail to me (this will help immeasurably!):

    /*  POTM ENTRY:  entryname (something clever please!)	*/
    /*  Your Name:   First Last					*/
    /*  Your email:  log@machine.att.com (or whatever)		*/
    /*  compile instructions (if other than "make entryname")	*/

    NOTE:  If you submit a shell program, please include these lines
    with a leading "#" and indicate which shell to run it under!  

    IMPORTANT:  ENTER EARLY - you will receive weekly standings and
    you will resolve any portability issues early.  You may improve
    your entry at any time by simply sending me another entry - so it
    pays to enter earlier!  (I process most everything in a day or so)

    IMPORTANT:  If you don't hear from me within a few days - it may
    mean that the mail got screwed up .... please follow up with an 
    inquiry to hicinbothem@att.com ....

Thanks!  If you have any questions, mail 'em to me - if I answer them
I'll include them in the Frequently Asked Questions (FAQ) list I 
circulate with the weekly standings!!!  Don't call me ... please!

WATCH THE FAQ - ESPECIALLY IN THE FIRST FEW WEEKS AS ALL THE STUPID
  ERRORS I MAKE IN THE PROBLEM STATEMENT TURN UP!!!!

Looking forward to your entry!	(remember:  enter@potm.ffast.att.com)
=Fred












Make your own free website on Tripod.com