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!!!
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 51 10 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