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).
The attached is LONG mail. The profiles that were returned are
presented below .... in order of finish (so you can read the tidbits
before you get tired). If you sent in your form after 7:00 PM
on Wednesday - it wasn't included ... I apologize. A shar file
with the top ten C programs is on the way ... watch for it!
=Fred
********************************************************************
============================================================
=== 1=> ==== odomatic ==== Vincent Goffin ==== mozart!vjg =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
1=> odomatic 1000 0.89* 405 Oct 27 10:26 494*
===========================
PROGRAM: odomatic FROM: Vincent Goffin AT: mozart!vjg
APPROACH:
I went through 19 versions, and I started with a numerical approach that bumped
the odometer(s) just enough to remove the leading repeated digits. This
typically introduces new repeated digits somewhere else, and the process
continues until convergence (except for impossible cases).
Impossible cases had to be screened out by hand and that wasn't satisfying.
In the end, trying to speed up the numerical approach I found a hybrid method
where a symbolic "accelerator" routine took care of the last 4 digits AND
took care of the impossible cases. The speed jumped, the size fell and I
started counting my chicken.
WHAT DID YOU DO:
C's remarkable syntax can be packed tight; in addition, I converted all if
statements to ?: expressions, allowing them to be strung together with ',' and
avoiding braces. I also looked for ways around return and break statements.
Final touch: I delayed calculations to the point where it was clear that
they were needed, even if that meant doing them within the [] of an array indx.
COMMENTS, LESSONS?
It is a wonderful opportunity to focus on a small problem and try to reach
the bottom of it. You can't do that with real world problems and that's
what's frustrating. For unrepentant reductionists, the POTM is a break!
WHAT, WHERE, AND WHY ARE YOU?
I'm in the BL0591120 (Softw. Tech. Center), because that's where I ended up.
It's the 2nd time I joined the POTM and it's great fun each time
(and now I get to catch up on everything, which is an even more fun!).
============================================================
=== 2=> ==== palith ==== Palith Balakrishnabati ==== toucan!pb =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
2=> palith 1000 1.61 413 Nov 1 16:13 574
===========================
PROGRAM: palith FROM: Palith Balakrishnabati AT: toucan!pb
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
For each value of odo and tripodo, recursively generate the entire set
of pairs of four digit numbers (abcd, efgh) such that: 1) all the digits
a-h are distinct and 2) the differences abcd - efgh and odo - tripodo
are congruent mod 10,000. For each member of this set, use table
lookup to find the two unused digits (say i and j) and consider the two
six-digit numbers ijabcd and jiabcd. Keep track of the smallest of
numbers these encountered greater than odo, (mod a million); This will
be the answer we seek.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
To make it small, I used very ugly obfuscating techniques, such as
"#define _ define", making local vars into params so I don't have to
declare them, forcing bits of code to look similar for maximum macro
compression. Please do nottry this at home, kids.
LESSON: Very tough to speed-optimize for a particular machine type
when you don't have a one of the beasts on hand for testing.
WHAT, WHERE, AND WHY ARE YOU?
I am Palith Balakrishnabati, and my field is theoretical CAD/CAM.
I am 32 years old, unmarried and a Scorpio.
============================================================
=== 3=> ==== qcd ==== Julius Collins ==== esun!jpc =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
3=> qcd 1000 2.71 372* Oct 31 22:09 643
===========================
PROGRAM: qcd FROM: Julius Collins AT: esun!jpc
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
kind of a depth-first tree-search algorithm (but tree is not stored).
a potential 6-digit answer, say 145268, is a leaf, with
parents labeled 5268, then 268, 68, 8, and then the root.
if a node, say 268, causes any digit duplication, then its
children need not be examined.
search whole tree (except as above) and save best answer.
finds common no-solution cases (e.g. 123456, 9876) quickly --
only checks 10 nodes.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
small: tried every trick in the book; wrote some new chapters!
used horrid macros, ignored proper datatypes
COMMENTS, LESSONS?
dont you have a real job? i hope i still do!
really i appreciate you running these...
and hope i'm not so interested in the next one.
really amazed how much my first tiny program could be shrunk.
WHAT, WHERE, AND WHY ARE YOU?
julius collins, HO (NJ8460?) 1E-423, esun!jpc
math/comp.sci., software, puzzles, POTMs, no time for life anymore!
============================================================
=== 4=> ==== pumpkin ==== Steve Sommars ==== ihlpl!sesv =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
4=> pumpkin 1000 1.81 615 Oct 16 16:16 796
===========================
PROGRAM: pumpkin FROM: Steve Sommars AT: ihlpl!sesv
APPROACH:
General approach was to start at current odometer 10K-ade,
construct all solutions (if any) in that 10K-ade. Stop when
one is found, use smallest. The no-solution cases are all of the
form: (Here x=A-B%10,000, symmetric about x=5000.
x%10==0 || x < 25 || x%1000<3 || x%1000>997 ||abs(x-100)<3 ||abs(x-200)<2
(I kept hoping to find a shorter representation for this, but failed.)
****There should be a clever algoritm for this problem using
****perhaps combinatorics and number theory, couldn't find it though.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
The speed came naturally from the algorithm. Making it small
was a pain. Numerous ugly tricks were used. I suspect I had
a small advantage because my host here is an Amdahl.
The final code is fragile, non-portable.
COMMENTS, LESSONS?
Interesting problem. The size part was a pain though. I would
have preferred that the importance of size be decreased in overall score.
WHAT, WHERE, AND WHY ARE YOU?
Systems Engineering for NSD-5ESS applications.
============================================================
=== 5=> ==== igottagodad ==== Keith Vollherbst ==== mtqua!keithv =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
5=> igottagodad 1000 2.02 597 Oct 30 23:55 799
===========================
PROGRAM: igottagodad FROM: Keith Vollherbst AT: mtqua!keithv
APPROACH: First test difference between meters to see if a solution is possible.
If so, calculate a digit by digit difference between the last 4 digits
of the meters (e.g., readings 123456 6543 produce differences of 6,9,1,3
(123456-6543=116913)). Then, recursively build the final meter readings by
adding a digit at a time to a blank total odometer reading. Possible digits in
the trip reading are calculated from the digit diffs. If the possible digit
isn't already used, recursively add the next digit to the total reading;
otherwise try a different digit in the total reading or return a failure
indication if all have been tried.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Nothing fancy here -- mostly just trial and error.
COMMENTS, LESSONS? One lesson was that I may generally make too much of the
"you can always trade space for time" adage. I found my biggest improvements
came from eliminating unnecessary code -- thereby reducing both time and space!
I wonder how much waste is in our released products?
As usual -- THANKS FRED!
WHAT, WHERE, AND WHY ARE YOU? I think anybody who entered who doesn't respond
"Nerd" to this one is probably just kidding themselves! My job is Key/PBX
communication system software development for GBCS in Middletown.
============================================================
=== 6=> ==== rollon ==== Warren Montgomery ==== iexist!warren =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
6=> rollon 1000 2.92 547 Oct 29 17:30 839
===========================
PROGRAM: rollon FROM: Warren Montgomery AT: iexist!warren
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM? scan the first 10,000
cases starting with the given reading looking for cases where the last
4 digits of the odometer and trip-meter were all distinct. In
each case, report an immediate solution if the remaining digits match
the upper two digits of the odometer, else track the solution closest
to the original reading of the two possible. If no solution in
first 10K is found, the closest combination found during the
search is reported or -1 for no solution. Major insight was use of
bit code representation to represent numbers with unique
digits. (2^n set if digit n is present).
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST? Pre-computed tables
mapping 4 digits to a bit code and indicating which 4 digit combinations
were unique. Abusive use of the pre-processor, table talk, and
minimal declarations saved lots of space
COMMENTS, LESSONS? Nice problem. I was particularly impressed
that space and time were both significant, and nobody found a trivial
solution. Brought back memories of systems programming in BASIC and FORTRAN
WHAT, WHERE, AND WHY ARE YOU? Someone whose other interests and
job have little to do with programming!
============================================================
=== 7=> ==== bighorn ==== Dennis Sanger ==== bighorn!drs =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
7=> bighorn 1000 1.01 764 Oct 12 11:39 865
===========================
PROGRAM: bighorn FROM: Dennis Sanger AT: bighorn!drs
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
First, I tried the obvious approach, adding miles until I hit a solution.
Even with a few clever enhancements (e.g. incrementing by 9 miles at a
time), this approach wasn't nearly speedy enough. My final entry
constructs possible solutions (i.e. solutions with the appropriate
difference between the odometer and the trip odometer) digit by digit
until it manages to find one.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
I obviously didn't do enough to make it small. To make it fast, the key
is to be able to recognize problems with no solution rather than wasting
time searching for nonexistent solutions. Another time-saving hint:
if there exists no solution of the form "abxxxx", there won't be a solution
of the form "baxxxx" either.
COMMENTS, LESSONS?
What a great creative outlet for those of us working in software
sweatshops! :-)
WHAT, WHERE, AND WHY ARE YOU?
WHAT? Definity(TM) G3 switch product support WHERE? Bell Labs in Denver
WHY? ummmmm, I dunno....
============================================================
=== 8=> ==== odjjaz ==== Joost Zalmstra ==== intgp1!jzalmst =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
8=> odjjaz 1000 4.13 560 Oct 22 05:48 973
===========================
PROGRAM: odjjaz FROM: Joost Zalmstra AT: intgp1!jzalmst
There are two interesting points I found during developing this program.
At first I started going from 'right' to 'left', i.e., I first made the
4 least significant digits of the total counter together with the trip
counter unique. The top two digits of the total counter could then be
chosen freely. The problem is that when you find a solution you do not yet
know if it is the shortest. Therefore I would have to try 5000+ situations
to be sure I had the shortest solution. When I found then the fastest solution
to date was 20 times faster than my solution I knew I would have to go from
left to right, but I could not find a way how to do it. Then a colleague
hinted on the way he was working his solution I got a brain waive. Although
my final solution was quit different from what he did, just a small hint
triggered my imagination.
Another interesting point was compacting. My first version was 764 bytes. I
was convinced that I was close to optimum. In the end I got more then 200
bytes off!!. So never conclude too fast that something is optimal!!
============================================================
=== 9=> ==== dbk_odo ==== Donald Knudsen ==== sirius!dbk =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
9=> dbk_odo 1000 4.25 583 Oct 11 15:31 1008
===========================
PROGRAM: dbk_odo FROM: Donald Knudsen AT: sirius!dbk
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
First do straightforward brute force version, generate some
trusted answers plus time benchmark. Notice that 1) no solution
if last digits of both odometers match and 2) solution guaranteed
if last 8 digits all different. Used space for time trade-off,
i.e., precompute large array to avoid lots of computation in loops.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Tried to use only ints in inner loops. Precompute arrays of masks.
Eliminate boundary condition tests in loops by using double-length arrays.
Use registers for variables in loops.
COMMENTS, LESSONS?
C compilers tend to have bugs relating to register use. Using compiler
optimization can make a program not work!
WHAT, WHERE, AND WHY ARE YOU?
I'm at MH. Interested in puzzles (programming and other).
============================================================
=== 10> ==== osu_odo6 ==== David Jones ==== jonesd@kcgl1.eng.ohio-state.edu =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
10> osu_odo6 1000 1.03 957 Oct 11 08:11 1060
===========================
PROGRAM: osu_odo6 FROM: David Jones AT: jonesd@kcgl1.eng.ohio-state.edu
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
The general solution is to first find all offsets which when added to the
low 4 digits of each odometer result in 8 unique digits. For each of these
offsets, some multiple of 10,000 can be added to make the high 2 digits
in the odometer unqiue from the other 8. The answer is the lowest multiple
plus offset found. The trick to getting an answer fast is how fast you can
test the 10,000 base offsets. My algorithm incrementally builds a list of
valid offsets incorporating succeedingly higher powers of 10. This approach
optimizes the scan by eliminating checks for ranges of offsets that would
fail anyway (i.e. if digits 'nm' added to the low two digits of the odo-
meters do not result in four unique digits, 'xynm' fails for all xy).
COMMENTS, LESSONS?
I think the scoring system is way too skewed in favor of program size.
Until it's changed, every month's problem degrades to the same problem.
WHAT, WHERE, AND WHY ARE YOU?
I'm a systems programmer III at The Ohio State University. I support
networking and VMS systems for the college of Engineering.
============================================================
=== 11> ==== stab ==== Jim Porter ==== longs!jwp =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> stab 1000 4.23 866 Oct 28 15:43 1289
===========================
PROGRAM: stab FROM: Jim Porter AT: longs!jwp
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Initial approach was simple iteration of trip choosing top 2 digits of
odom when other 8 were unique. This gives a search with 10000 iterations
(not so good). Final solution involved determining the difference between
odom/trip digits and setting (recursively) the bottom 4 digit values of
odom from trip. The trip digits were chosen by a depth first recursive
search of possible digit values. The final 2 odom digits were still
determined when other were unique. This was 4* faster with 100 test data.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Sleepless nights ... pulled hair ... uh, wait really-->make all variables
and functions single character, #define common used terms, got rid of
all indenting and extra spaces, used 'c' default arg type of int.
COMMENTS, LESSONS?
I would have like to try search odom recursively. Search space is larger
but digit allocation and deterministic trip digit assignment might have
yielded a faster solution since a branch&bound could be used.
WHAT, WHERE, AND WHY ARE YOU?
Work in GBCS on a PBX adjunct called CMS (c++ appl. running on 486/UNIX).
I like puzzles. This one sounded fun (Thanks Fred). Also play racquetball.
============================================================
=== 12> ==== mile6 ==== Jim Hahn ==== cblph!jrh3 =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> mile6 1000 7.86 623 Oct 14 10:56 1409
===========================
PROGRAM: mile6 FROM: Jim Hahn AT: cblph!jrh3
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Note the digits working from left to right. When a duplicate appears, add
just enough to the current value to increment the duplicate digit. As for
no-solution cases, the only special case for which I checked was the same
right-most digit in the two readings. All other no-solution cases were
identified by two carries out of the left-most digit. To even get a program
into the top entries, it had to be small; this tended to eliminate any of
the algorithms I had in mind to pre-calculate stuff to speed it up. Instead
I had to focus on finding a simple algorithm.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
To make it small, I wrote a general purpose program, shrink, that shortens
variable names and replaces often used keywords with shorter #define symbols.
Thus I write & debug a legible program, but I submit a shrunken program.
COMMENTS, LESSONS?
I was amazed and impressed at the turn-around time when I submitted a new
version. Solving these problems can be addictive, but certainly spawns
creative thinking. Nevertheless, there came a point when I just had to stop!
WHAT, WHERE, AND WHY ARE YOU?
I'm in Columbus working on a product called StarRep(tm) PROES. My interests
include optimization problems; hence this POTM problems struck a chord.
============================================================
=== 13> ==== odm_potm ==== John Berry ==== cdsdb1!jlb =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odm_potm 1000 5.22 1041 Oct 31 00:11 1563
===========================
... No form returned
============================================================
=== 14> ==== odie ==== Brian Davies ==== ihlpl!bdavies =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odie 1000 4.31 1249 Oct 7 11:20 1680
===========================
... No form returned
============================================================
=== 15> ==== odor ==== David Roe ==== research!roe =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odor 1000 10.59 664 Oct 1 21:32 1723
===========================
... No form returned
============================================================
=== 16> ==== krrOD ==== Ken Rodemann ==== qsun!krr =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> krrOD 1000 2.43 1827 Sep 28 20:59 2070
===========================
... No form returned
============================================================
=== 17> ==== mr.bill ==== Scott Kennedy ==== homxb!tsk =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> mr.bill 1000 9.58 1212 Sep 28 14:26 2170
===========================
... No form returned
============================================================
=== 18> ==== odyssey ==== Debbie Brown ==== homxb!dwb =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odyssey 1000 20.50 733 Oct 7 16:01 2783
===========================
... No form returned
============================================================
=== 19> ==== hold_da_fort ==== Ken Haruta ==== mhcnet!kh =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> hold_da_fort 1000 13.78 1475 Oct 21 14:40 2853
===========================
PROGRAM: hold_da_fort FROM: Ken Haruta AT: mhcnet!kh
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
A. If the least significant digits of the OD (odometer) and TR (trip d)
are the same, there is no solution.
B. Stuff the last 4 digits of OD and TR starting from the top into n array
of 0 - 9 and if there is a duplication, bump n miles on OD and TR; n
depends on which digits are duplicated.
C. When the 8 digits are all different, see if the top 2 digits of D are
different from the 8 digits. If so, that's the solution. If not, hange
the top 2 till I find the
smallest N to satisfy the condition, store N, etc. and keep going.
After the sum of all N's >= 9999, the smallest M is the solution.
WHAT DID YOU DO TO MAKE THE THING SMALL?
Removed all the white spaces except in the statement number field.
COMMENTS, LESSONS?
I can't believe where you find time to run POTM, Fred. This is my first
entry, and had a lot of fun. Keep up the great job!
By the way, the weekly leaderboard is a must. Can't do without it.
WHAT, WHERE, AND WHY ARE YOU?
B.A. from Colby College, Waterville, ME, Ph.D. in physics from .I.T. ('63)
I'm crazy about tennis - but someone please tell me how to improve.
============================================================
=== 20> ==== bigrun ==== Dave Lynch ==== esun!dfl =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> bigrun 1000 23.91 849 Oct 29 14:25 3240
===========================
PROGRAM: bigrun FROM: Dave Lynch AT: esun!dfl
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
If the one's digits were the same, I printed -1. Otherwise, I rolled the two
odometers until all the digits were different. First, I would roll the
ten-thousands, then the thousands, then the hundreds, etc. For example, if
given 575213, 3456, my first step would be 576000, 4243. If I changed a column,
I would go back to the ten-thousands; otherwise I would move on to the next
column. If the odometer rolled over twice, I printed -1.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
The obvious. Nothing tricky.
COMMENTS, LESSONS?
Thanks for running the thing!
WHAT, WHERE, AND WHY ARE YOU?
Develop network design software.
============================================================
=== >20 ==== bmw ==== Doug Murphy ==== ios!djm3 =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> bmw 1000 23.49 1225 Sep 22 11:50 3574
===========================
PROGRAM: bmw FROM: Doug Murphy AT: ios!djm3
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
1) Eliminate all "no solution" cases (known algorithm)
2) Treat the number as an array of digits.
3) Compute plausible increment range for each decimal place.
4) From these ranges, compute the smallest possible solution.
5) From there, increment and check, subject to increment ranges.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
1) C++ inline functions
2) Used preprocessor macros as a source compression technique
3) Other usual hacks...
COMMENTS, LESSONS?
1) No matter how much I compressed it, Object-Oriented C++ code will
be bigger than C code. Information hiding in C++ is too verbose
if we're being measured on code size.
2) I need a better algorithm.
WHAT, WHERE, AND WHY ARE YOU?
Architect/Lead Developer
Operations Manager - Switch Provisioning
AT&T-BL, Holmdel, NJ
============================================================
=== >20 ==== leepfrog ==== David Stephenson ==== mlsma!dstephen =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> leepfrog 1000 17.91 1869 Oct 15 12:49 3660
===========================
PROGRAM: leepfrog FROM: David Stephenson AT: mlsma!dstephen
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
I started a the most significant end and worked towards the least
significant end, When I found a duplicate digit I called another function
which jumped forward enough miles so that the clock had changed the
duplicate digit.
Optomization took the form of working how far I could jump the clock.
But that only inproved the performance by about 50% not enough !!
the no-solution check was restricted to just checking that the two unit
digits were not the same.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Small, I just created a 'sed' script that went through and removed any
unneeded while space and swaped variable names for shorter ones.
DOES ANYONE HAVE A GOOD PROGRAM TO DO THIS ??????
COMMENTS, LESSONS?
I learnt from the last POTM that I entered that Algoritham optomization
must come before code optomization.
WHAT, WHERE, AND WHY ARE YOU?
I am a Software Engineer interested in Operating System Design and OOP.
============================================================
=== >20 ==== s5 ==== Ramachandran Subramanian ==== cblpe!subra =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> s5 1000 45.84 894 Oct 25 09:17 5478
===========================
PROGRAM: s5 FROM: Ramachandran Subramanian AT: cblpe!subra
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Compute a list of 4 digit numbers with 4 distinct digits; Assuming that the
odometer's last 4 digits are one of these numbers, compute the value of
trip meter. If the 8 digits (from the odometer and trip meter) are
distinct, prepend the remaining 2 digits to odometer value and compute
difference from the given pair of values. The pair with least difference is
the solution. If the difference is a multiple of 10 or is less than 25, no
solution. If there is no pair with 8 distinct digits, there is no solution.
The trade-off is run-time memory vs speed.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Use 1 char variable names, reduce number of variables, use smallest size
variables, eliminate unnecessary syntax, use the side-effect capability, use
register variables, optimize inner loop to reduce number of computations
COMMENTS, LESSONS?
It was addicting initially. After I saw the preliminary results, I
figured that I did not stand a chance of winning. But I still completed
to enter the contest.
WHAT, WHERE, AND WHY ARE YOU?
2STP Project Management in Columbus OH. Interests are too many ... music,
programming,PC,mathematics,stocks,simulation,travel,people etc.
============================================================
=== >20 ==== drex ==== David Magagnosc ==== dmagagno@mcs.drexel.edu =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> drex 1000 31.92 2362 Oct 29 20:40 5554
===========================
... No form returned
============================================================
=== >20 ==== meter1 ==== Yong Li ==== honet4!yong =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> meter1 1000 50.73 495 Oct 29 15:29 5568
===========================
... No form returned
============================================================
=== >20 ==== pz ==== Y.C. Tao ==== lzsc!tao =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> pz 1000 42.51 1594 Oct 21 15:57 5845
===========================
1.Program logic: (Answer is the answer, Initialze each time to High number)
First to find all 4-digit unique numbers (no two digits are same, e.g. 0123,
0124, ..., 9876) put into array of 10000. If number is not unique, the
value is of smallest number larger than the current one as pointer.
Check if both last 4-digit of 6-digit (Odom) number AND the 4-digit
Trip number are unique numbers. If yes, get first 2-digit (2-d)
of Odom number and Answer= 2-d*10000.
Loop to (find out both new 4-digit Odom number AND new 4-digit
Trip number are unique numbers by searching above 4-digit number array)
Get the Gap between 4-digit Current & Orig(inal) Odom number.
Add the Gap to Orig Trip number & get Current 4-digit Trip number.
IF Current Trip number is unique number then
Get smallest 2 digit number (2-d) > first 2-digit of Odom number from
the 2 remaining digits. Possible new-answer = 2-d*10000 + Gap
(Some instance may need adjustment because of Gap >9999)
Compare with the old Answer, if samller, Answer= new-answer.
Get the next unique of last 4-digit Odom number.
2. I do not think my program is either small nor fast.
3-4. This POTM is kind of fun. Personal stuff, couldn't give your answers.
============================================================
=== >20 ==== rams ==== Ram Ramachandran ==== iwtgo!rams =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> rams 1000 47.16 1718 Oct 15 13:55 6434
===========================
... No form returned
============================================================
=== >20 ==== hydra ==== Mike Gagle ==== inuxy!kessler =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> hydra 1000 65.91 929 Oct 20 15:05 7520
===========================
... No form returned
============================================================
=== >20 ==== potm2 ==== Bill Mielke ==== cbosgd!wfm =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> potm2 1000 53.30 2382 Oct 30 13:20 7712
===========================
... No form returned
============================================================
=== >20 ==== masses ==== Joe Miller ==== hogpa!jmil =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> masses 1000 18.81 6144 Oct 1 08:58 8025
===========================
... No form returned
============================================================
=== >20 ==== olds ==== Perin Jathavedam ==== mare!pnj =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> olds 1000 52.21 3681 Oct 31 10:25 8902
===========================
PROGRAM: olds FROM: Perin Jathavedam AT: mare!pnj
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
The overall approach was to move from the left to right (rather than
actual right to left operation of the odometer) so as to zero in on the
result quicker. Did not really care much about using ints vs chars.
The main idea in the left to right algorithm was to determine the valid
combinations that can occur in the corresponding digits of the odometer
and the trip meter at any instant. And used a recursive algorithm
to find the result. Once a cycle completes unsuccessfully for the
most significant digit in the odometer, then it means there is no answer.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
After timing my program run, it made more sense to reduce the size as much
as possible than try to make it run faster. Used one letter vars, no in-
dentations etc. and reduced the size to bare minimum.
COMMENTS, LESSONS?
This got me almost addicted to the POTM, though got frustrated sometimes
when things did not work as I expected. Thanks to you for running the tests
as quickly as you did.
WHAT, WHERE, AND WHY ARE YOU?
Background is Structural Engineer turned into Software Engineer. Interested
in problems involving innovative algorithms. Job - Software development.
============================================================
=== >20 ==== dds ==== Don Shugard ==== boole!dds =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> dds 1000 85.41 550 Sep 15 16:57 9091
===========================
PROGRAM: dds FROM: Don Shugard AT: boole!dds
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Brute force: I did a naive algorithm just to get into it with the
hope of refining the algorithm. A November 15 deadline shot any hopes
of achieving the final goal.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Lots of #defines
COMMENTS, LESSONS? Thanks for the puzzle. It lead to several enjoyable
lunch time discussions. It also gave me something to think about while
driving. Instead of source size use size of stripped executable. This
would be a better engineering constraint.
WHAT, WHERE, AND WHY ARE YOU? I've been doing VLIS design and hacking on
VLSI tools for the past eight years. I used to be in MH and now I reside
in HO 4G-526.
============================================================
=== >20 ==== mtrmaster ==== Frank Rahoi ==== nwsca!fer =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> mtrmaster 1000 72.64 2103 Oct 1 21:06 9367
===========================
PROGRAM: mtrmaster FROM: Frank Rahoi AT: nwsca!fer
APPROACH:
I got some code to work reasonablly well, and found all 'impossible' solutions
using this code and all combinations of the following: 000000 XXXX.
The last version of the code checked for impossible solutions quickly by
finding the miles for a 6 digit turnover (all 0's), adjusting the 4 digit
value accordingly, and checking against the (small) list of 'impossible'
numbers. To find the solution for solvable numbers, the algorithm found the
max of (minumum miles that would alter all but one of the duplicate digit (0-9))
and incremented until a solution was found.
Great Problem, waiting to see the other approaches especially those under
1s cpu. Felt a bit stupid on this one.
GRIPES: I made no attempt at decreasing the code size.
I thought this was a stupid criteria and hope it is never used again.
I also think that if 'nothing' can be discerned from the weekly leader board
that it should not be distributed ... more useless mail. I would like to
see the leader board given meaning, by using NEW random data to generate it
each week.
============================================================
=== >20 ==== rgk_odom ==== Bob Kramek ==== hotsb!rgk =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> rgk_odom 1000 73.28 2041 Oct 8 19:46 9369
===========================
... No form returned
============================================================
=== >20 ==== howd.i.do ==== Michael Bailey ==== mlsma!mbbailey =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> howd.i.do 1000 77.61 1619 Sep 29 21:36 9380
===========================
PROGRAM: howd.i.do FROM: Michael Bailey AT: mlsma!mbbailey
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Very simple, Just add 1 to the odometer and trip counter
and check each number against each other, if a
number was already present repeat the cycle.
I could not think of any clever ideas
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Remove charcaters
COMMENTS, LESSONS?
frustration
WHAT, WHERE, AND WHY ARE YOU?
New to the company at Network Systems UK (mlm)
ex Royal-Air-Force ( simulation engineer )
now software engineer ISUP
interests: basketball, software engineering ( what a mix ! )
============================================================
=== >20 ==== hcy ==== James Yang ==== cbncp51!hcy =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> hcy 1000 97.53 373 Sep 28 11:46 10126
===========================
... No form returned
============================================================
=== >20 ==== miles2go ==== Ravi Sharma ==== bhopal!sharma =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> miles2go 1000 100.91 795 Oct 26 10:45 10886
===========================
... No form returned
============================================================
=== >20 ==== racoco ==== Rich Coco ==== wibls!racoco =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> racoco 1000 75.73 3555 Sep 21 20:21 11128
===========================
PROGRAM: racoco FROM: Rich Coco AT: wibls!racoco
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
all possible odometer/tripometer pairs can be partitioned into equivalence
classes (EC) based on difference (mod 10) of low order digit. the EC cont-
aining 0 differences has no tuple whose digits are different. the 10!
tuples whose digits are all different are equally distributed among the
remaining 9 ECs. So, for each initial tuple read in, look at last digits
If difference is 0, no solution possible. I COULD NOT DERIVE AN ALGORITHM
WHICH GOT ME FROM THE INPUT TUPLE TO THE NEAREST SOLUTION TUPLE (other
than the obvious 'add 1' and check) - Waaaaaaaaa
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
since i felt that the real solution involved finding the algorithm
alluded to above, i didn't waste time find tuning what i had.
COMMENTS, LESSONS?
Travel and work prevented me from spending much time on this. i'm hoping
someone derived the EC algorithm i wasn't able to. I beieve the answer is
in Residue theory (number thy). PLEASE CONTACT ME IF YOU DID IT!
WHAT, WHERE, AND WHY ARE YOU?
rich coco racoco@wibls.att.com 508-960-4071
1600 Osgood St No Andover, Ma Rm 30-2B4 NB719AD00 Col A-16
============================================================
=== >20 ==== may.not.run ==== Raju Datar ==== hogpa!datar =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> may.not.run 1000 63.71 5009 Oct 31 19:13 11380
===========================
PROGRAM: may.not.run FROM: Raju Datar AT: hogpa!datar
Overall approach: find the duplicate numbers within tripmeter, odometer
and between trip and odometer. Increment the duplicate number by 1.
I used int to represent each digit. Converted each read char to int by
substracting char '0' from it and adding int 0.
Works for most cases but should check for digit 9 being multiple.
that should reduce the number of cases where my answer is not minimum.
Overall I really enjoyed this POTM acitvity. Wish I had more time to completely
debug the program. I am currently not getting right answers for about 13 cases.
(see above for what I think I would like to do).
============================================================
=== >20 ==== ads_potm ==== Al Schapira ==== mhcnet!ads =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> ads_potm 1000 77.83 3962 Oct 15 12:42 11745
===========================
PROGRAM: ads_potm FROM: Al Schapira AT: mhcnet!ads
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
I pre-generated the 151200 permuations of the 10 digits of length six,
recording which digits got used in each. For each 6-digit target, using
a binary search I found the smallest permutation greater than it,
and its index, and then tested each permutation onward
until one was found which yielded a solution, or wrapped around to the original
number. I also pre-built a table of the 10000 4-digit numbers
recording which digit each used so that the solution testing could
be done efficiently.
I tested separately for trivial solutions, and for no solution (F == J).
Aside form pruning the search to known permutations, I used brute force.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
I spent NO effort reducing program size. In fact, I put in extra
argument handling and extra debugging stuff to help me figure out what was
going on. I never took this stuff out.
For speed, I pruned the inner loops and got rid of scanf.
Using the same basic algorithm my times dropped like this
==> ads_potm 100 51.99 3657 Sep 30 13:28 55647
==> ads_potm 100 12.31 3610 Oct 1 11:12 15920
==> ads_potm 100 9.49 3931 Oct 4 13:43 13421
==> ads_potm 100 5.81 3791 Oct 12 13:11 9601
==> ads_potm 100 4.77 3962 Oct 15 12:42 8732
Replacing fread() with read() actually increased run time.
I suspect that one read of all 12000 inout characters, and a few pointer
operations would reduce the time slightly, but not significantly.
Since the fastest times were over an order of magnitude faster than mine,
I must have missed a better approach.
I found some optimizations which ran fine on my sparc1+ which
failed on your Amdahl.
COMMENTS, LESSONS?
get a life, addiction, frustration, amazement,
thank me for running the thing, FUN, etc.`
All of the above!
WHAT, WHERE, AND WHY ARE YOU?
538620000, CAD/CAE simulation tools for VLSI design and verification.
============================================================
=== >20 ==== holland ==== Warren Koontz ==== hvlpa!wlkoontz =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> holland 1000 102.09 1852 Oct 4 08:29 12061
===========================
PROGRAM: holland FROM: Warren Koontz AT: hvlpa!wlkoontz
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Observation: Last four digits of odometer "track" trip odometer.
Algorithm:
Note: "valid" means no repeated digits
best so far = 1000000
for all valid trip odometer values {
compute corresponding last four digits of odometer
if (trip odometer LFDO is valid) {
generate two candidates using last two digits
update "best so far" using elapsed miles criterion
}
}
print "best so far"
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Smallness: nothing explicit
Fastness:
- Used ugly nested for loops to enumerate valid trip
odometer values
- Combined some functions to avoid double work
- Used integer arithmetic rather than logic where
possible
COMMENTS, LESSONS?
Try to optimize in the mathematical, or other problem domain
before resorting to programming tricks.
WHAT, WHERE, AND WHY ARE YOU?
I took my first programming course in 1966 (MAD language)
and went through various phases involving FORTRAN, PL/I,
SIMSCRIPT and finally C. In the meantime, I joined the
management ranks and I haven't done any real programming for
many years. Still, I like to play every now and then and,
who knows, I may have to program for a living again some
day!
============================================================
=== >20 ==== milo ==== Dave Kristol ==== allegra!dmk =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> milo 1000 107.70 2426 Sep 30 11:32 13196
===========================
PROGRAM: milo FROM: Dave Kristol AT: allegra!dmk
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Let each digit, 0-9, be represented by a bit in a word 1 << digit.
If all 10 digits are present, 10 bits will be set. Now, how do we
cheaply tell what bits are present in the 6- and 4-digit numbers?
Two pre-computed tables contain those bits for 0-9999 and 0-999999.
Increment the 4- and 6-digit numbers, combine their table entries,
and stop when their logical OR has all 10 bits set.
There appear to be optimizations possible because there are long
sequences of numbers (for example, all numbers below 010000) that
have duplicate digits and therefore fail immediately. But I didn't
have time to explore these possibilities further.
I didn't make any attempt to minimize the size of my program,
because I didn't have time, and the improvements I could make were
unlikely to put me near the top of the standings anyway.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Nothing especially surprising.
COMMENTS, LESSONS?
Once again I find that it's not too hard to write a program that runs
within a factor of 10 of the leaders, but that I obviously fail to see
some clever trick that will yield the extra order of magnitude.
WHAT, WHERE, AND WHY ARE YOU?
David Kristol, Dept. 11382, Murray Hill, NJ
============================================================
=== >20 ==== are_we_there ==== Brian Urch ==== addams!bcu =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> are_we_there 1000 139.39 3857 Oct 1 15:09 17796
===========================
... No form returned
============================================================
=== >20 ==== odomEE ==== Ed Eng ==== cdsdb1!ed =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odomEE 1000 251.54 755 Sep 30 18:09 25909
===========================
... No form returned
============================================================
=== >20 ==== odo ==== Dave Dykstra ==== graceland!dwd =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odo 1000 342.62 1846 Sep 14 11:36 36108
===========================
PROGRAM: odo FROM: Dave Dykstra AT: graceland!dwd
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
First tried brute force to get something working. After that, I realized
that some numbers could be skipped and tried again to skip those with
repeated digits, starting from the most signficant digits down.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
As I said in the last question, I improved speed by skipping sets of
numbers where digits were repeated by higher signficant digits. I got
a factor of 10 improvement. Once I saw other people getting factors
of 10 better than mine (and later more factors of 10) with smaller code,
I decided I had spent enough time on it and didn't bother to make it small.
COMMENTS, LESSONS?
I wasted too much time on it.
WHAT, WHERE, AND WHY ARE YOU?
I'm a Resource Link associate in software development, most recently
working on layers and now working on the Broadband Switching System. I
have about 10 years professional experience in software development and
a CS Phd.
============================================================
=== >20 ==== odo_sent ==== Alan Javornik ==== mopar@dr.att.com =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odo_sent 1000 437.78 3747 Oct 27 12:34 47525
===========================
PROGRAM: odo_sent FROM: Alan Javornik AT: mopar@dr.att.com
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
The first decision was how to decide when all digits were distinct.
I used a unique bit position to represent each digit and xor'ed
them to determine uniqueness. One would think there would be
a mathematical solution rather than an iterative solution but I
haven't found one yet.
The second was how to determine when the problem was unsolvable (-1).
When the LSD's were the same was a simple case but there were
others that were not as obvious.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Took out the function calls after program was verified.
Used int rather than short for speed even though the space
wasn't fully needed.
COMMENTS, LESSONS?
WHAT, WHERE, AND WHY ARE YOU?
The thing about these kinds of problems is that I tend to think
about them until I come up with a solution, but, they are fun.
============================================================
=== >20 ==== gdo ==== Gary Oswald ==== ihlpm!gdo =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> gdo 1000 1091.16 732 Sep 30 15:08 109848
===========================
... No form returned
============================================================
=== >20 ==== focus ==== Steve Palmer ==== ho1focus!srp =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> focus 1000 1178.59 732 Sep 28 17:17 118591
===========================
PROGRAM: focus FROM: Steve Palmer AT: ho1focus!srp
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
don't check cases where least significant digit
is the same
otherwise, loop checking for all digits - if not,
bump up both counters and check again until
999999 loops are done or a match
used char strings for the counters to make the
all digits check
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
wrote a filter to take the long variables used in
the original program and make them smaller
COMMENTS, LESSONS?
thank you for running the thing, it is FUN
How 'bout that?
Actually, this is a great idea!!! Something to
do on those cold rainy weeknights.
WHAT, WHERE, AND WHY ARE YOU?
What's going on with the Redskins?
============================================================
=== >20 ==== open_road ==== Dom Gurrera ==== mtqua!dom =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> open_road 1000 1461.82 1898 Oct 27 16:10 148080
===========================
PROGRAM: open_road FROM: Dom Gurrera AT: mtqua!dom
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM
Ended up using arrays - did try to convert to a number
for incrementing, but that took longer.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Squeezed code into not so readable concoctions, no comments and
did not check for absencs of an input, also didn't close the file.
COMMENTS, LESSONS?
It was a fun problem. I did run my own speed runs before submitting.
Even looked for speed in using > instead of ==. Fun and educational.
WHAT, WHERE AND WHY ARE YOU?
Software developer in the PARTNER small business telephone
group in GBCS.
============================================================
=== >20 ==== steve ==== Steve Beckle ==== ihlpl!srbeckle =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> steve 1000 1487.24 3526 Oct 22 10:52 152250
===========================
PROGRAM: steve FROM: Steve Beckle AT: ihlpl!srbeckle
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
For each input pair, ran iterative algorithm until solution found or no
solution after 1 million miles. First, make all digits in main (odo1)
unique. For instance 434687. The 4 appears twice. Add 313 -> 435000.
then work on 435000 etc, until 435126. Now do the same for odo2.
Since moving odo2 changes odo1, must see if odo1 digs still all different.
If so, resolve any digits common to odo1 and odo2. Go back and test
for odo1 unique, repeat entire process as needed. All mileage
increments were based on determing what integer had to be added
to eliminate the rightmost "culprit" or duplicate digit, either
within the same odo or between the two. New tack:Tried to
generate all possible "winning" combinations then do lookup for each
input pair based on diff between odo1 and odo2, but insufficient
memory. Could have really gone fast after initial table was built!!
Ran several test pairs to identify instant losers based on diff btwn
odo1 and odo2. Put test for these diffs up front in program to save
time finding null solutions. Frustrations?? That I didn't figure out
the mathematical solution and had to use an iterative one.
Hey. This was fun!!! A chance to do real programming. A challenge!
Clever ideas?? How can I claim any when I'm not even close to
the best time? :-) This was the first POTM I participated in since
it didn't seem so bizarre/impossible/mind-bending.
============================================================
=== >20 ==== jfernan_odo ==== Jesus Fernandez ==== hzsbg01!jfernan =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> jfernan_odo 1000 1991.67 3410 Oct 8 19:47 202577
===========================
... No form returned
============================================================
=== >20 ==== jims_odo ==== James Stuhlmacher ==== intgp1!jims =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> jims_odo 1000 2146.12 2585 Sep 30 10:32 217197
===========================
... No form returned
============================================================
=== >20 ==== brute ==== Phil Gillis ==== whservh!pwg =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> brute 1000 2270.36 1684 Oct 25 12:41 228720
===========================
... No form returned
============================================================
=== >20 ==== contest64 ==== Joe Kruskal ==== research!kruskal =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> contest64 1000 2722.45 1762 Oct 10 23:41 274007
===========================
PROGRAM: contest64 FROM: Joe Kruskal AT: research!kruskal
I entered the contest as a way of learning to use Perl. I was successful
in learning about Perl, and my program worked, though not very fast.
The approach was to generate all 5040=10*9*8*7 4-digit numbers which
have no repeated digits, and to try each one as the final four digits
of the 6-digit odometer reading. Arithmetic then generates the 4-digit
odometer reading. A very simple hashing using powers of 6 and
guaranteed not to produce false agreements was applied to the eight
digits and looked up in an associative table with 45=10*9/2 entries.
If the hash code was not in the table, the 8 digits were not all
distinct, so the case was discarded. If the entry was found, it
yielded the two unused digits, which were tried in both orders. The
additional miles were calculated in each case, the minimum was found.
Since Perl is quasi-interpretive (source code is always parsed and
compiled at run time), the source code is the running code. No attempt
was made to reduce the size of the code.
-------------------------------------------------------------------
Joseph B. Kruskal 908-582-3853 mh 2c-281 Sent Tue Nov 2 10:15:11 EST 1993
============================================================
=== >20 ==== snail ==== Thierry Mataigne ==== hvlpa!tmataign =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> snail 1000 2767.71 2040 Oct 11 12:02 278811
===========================
... No form returned
============================================================
=== >20 ==== small ==== Narcus Hall ==== iwtlc!marcus =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> small 1000 2797.59 723 Sep 15 13:41 280482
===========================
... No form returned
============================================================
=== >20 ==== potm ==== Gregg Wonderly ==== intgp1!gregg =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> potm 1000 3017.36 1048 Sep 12 11:19 302784
===========================
PROGRAM: potm FROM: Gregg Wonderly AT: intgp1!gregg
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
I decided that I would just try exhaustive search by
simulating the wrap around of the TPO and ODO and then
looking for unique digits. An extremely inefficient
method, but to the best of my knowledge the program
worked the first time I ran it.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Nothing special...
COMMENTS, LESSONS?
I spent little time on a problem which obvious has some
very efficient answers that are orders of magnitude from
my solution, but I had other things to do...
WHAT, WHERE, AND WHY ARE YOU?
My background involves mostly just-do-it programming which
is the basis of my brute force solution. It is sometimes
easier to get the answer in 4 hours after working for 4 minutes
than to work for four hours to get the answer in 4 minutes!
============================================================
=== >20 ==== dlkmain ==== David Koeberle ==== vilya!djdlk =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> dlkmain 999 8.76 868 Oct 29 11:52 1744
===========================
... No form returned
============================================================
=== >20 ==== odoway ==== Bruce Brandon ==== esun!bgb =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odoway 999 31.21 990 Oct 22 12:41 4111
===========================
... No form returned
============================================================
=== >20 ==== dbb ==== Dave Brown ==== cbskat!dbb =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> dbb 999 199.91 1326 Oct 20 23:24 21317
===========================
... No form returned
============================================================
=== >20 ==== odoretentive ==== Tim Tjarks ==== iesde!tjarks =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odoretentive 997 2.74 589 Oct 31 11:01 863
===========================
PROGRAM: odoretentive FROM: Tim Tjarks AT: iesde!tjarks
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
My first approach was to recognize that (A-B) mod 10000 was constant as
you travelled, so I generated all values of A and B using digits only
once and built a table indexed by the difference. This proved to be
slow and use too much memory (exceeded brk ulimit on Amdahl, but it
did give me the pattern of which differences yielded no solution, so I
incorporated that into the next try. Next, I tried the brute force method
of incrementing and checking the digits. That wasn't so bad. I refined
it by a) figuring the next best guess for the increment rather than just
incrementing by one, and b) recursing so that previously checked digit
positions were not re-checked.
WHAT DID YOU DO TO MAKE THE THING SMALL?
Assume a 32-bit int, use one-character variables and only necessary
whitespace. Use ?: rather than if-else. #defines proved not worth the
effort, but I did use global variable for a couple constants. Declare
varaiable only if the default wouldn't work or didn't save space.
WHAT, WHERE, AND WHY ARE YOU?
Tim Tjarks, tjarks@iesde, IHP 2F-547
Switching Systems - Software Development Environment
============================================================
=== >20 ==== woody ==== Fred Hicinbothem ==== homxb!fah =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> woody 997 3.71 1251 Oct 11 16:48 1622
===========================
PROGRAM: woody FROM: Fred Hicinbothem AT: homxb!fah
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Nobody will read this far anyhow, so I need not be embarrassed.
* worked from left to right * no mod (%) or division (/)
* worked only with numbers <10 * didn't use int odo values
* keep a MASK with bits to indicate digits in current solution
* working from left to right, look for digits already used, if one
is found, then add enough to cause a carry into that position
and then repeat. Note: I added enough to make the last digits
something like 0123 as opposed to 0000 - a cycle here, a cycle there.
* problem issue was situations involving 9s that created unexpected
carrys into positions further left than I expected
* as for the quick-checks ... I checked only the units digits ... the other
checks took too many characters for "unlikely" payback.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Nothing you haven't read already. Speed was all algorithm since
I am a particularly rotten programmer.
COMMENTS, LESSONS?
If you are the one making up the final tests, your entry ought to
be able to pass them. Otherwise, a shitty programmer with a good
algorithm can be competitive with the converse.
WHAT, WHERE, AND WHY ARE YOU?
I am the POTM-master ... email is my life. I do have a REAL job
working for the Fast Features Adjunct Systems Technology (FFAST)
department - our products are better than our acronym!
============================================================
=== >20 ==== perma10t ==== Chip Webb ==== allegra!cwebb =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> perma10t 997 223.99 1095 Oct 9 18:00 23494
===========================
PROGRAM: perma10t FROM: Chip Webb AT: allegra!cwebb
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
build table of known possible 6-digit combinations.
numbers like xxxxxi and xxxi always fail.
building the table takes lotso time & fair amount of space
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
cpp (ugh, don't make us do this again, for your sake Fred!)
COMMENTS, LESSONS?
It is fun to work on a solution, but the weekly results can
be discouraging if you're behind by a factor of 100. :-)
Please keep doing the contest!
============================================================
=== >20 ==== mink ==== Harry Pilafis ==== mink!hbp =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> mink 995 417.44 818 Oct 11 11:57 42562
===========================
... No form returned
============================================================
=== >20 ==== simple_code ==== Richard Toeniskoetter ==== cblpe!rtoe =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> simple_code 995 2245.57 2361 Sep 28 14:35 226918
===========================
PROGRAM: simple_code FROM: Richard Toeniskoetter AT: cbskat!rtoe
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
My approach was to initially classify all 6 digit numbers with unique
digits into equivalence classes based on the 6 digits present, and do the
same with 4 digit numbers. Then given any 4 and 6 digit pair, increment
the 6 digit up to next number with all unique digits, add the same delta
to the 4 digit number, and check to see if the equivalence classes were
complements (indicating all 10 digits present). Submitted code used
prime number categorizations of the equivalence classes, had planned on
changing to bit masks for speed but didn't get that far.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Nothing was done since the original run was so far off of the leaders
that it was apparent the algorithm I was using was not competitive, no
matter what I did.
COMMENTS, LESSONS?
I was amazed at solutions that were 1000 times faster than mine,
and much shorter as well. So amazed that I gave up ...
Looking forward to the next problem.
WHAT, WHERE, AND WHY ARE YOU?
working in Bell Labs Columbus OH, primarily supporting Switching
projects with quality activities.
============================================================
=== >20 ==== odom ==== Kevin Ahrens ==== ihlpm!kea =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> odom 985 300.66 1439 Oct 29 09:30 31505
===========================
PROGRAM: odom FROM: Kevin Ahrens AT: ihlpm!kea
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
After receiving the original problem and thinking about what could be done
to solve the problem other than brute force, I came up with the following
reasoning:
The trip meter and the bottom 4 digits of the odometer are dependent on
each other. One can't be changed without affecting the other. It is only
necessary to check the first 10,000 "miles" for 8 unique characters between
the trip meter and the odometer. If 8 unique digits are found, the upper 2
digits of the odometer can be calculated to give the minimal distance. If
8 unique characters can't be found in 10,000 iterations, there is no solution.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Didn't concentrate much on fast. For small, I removed all
unnecessary spaces and renamed all variables, classes, etc,
to 1 character each. Removed comments.
WHAT, WHERE, AND WHY ARE YOU?
I'm just another programmer that likes to write programs to solve problems.
Also gives me an opportunity to play around with C++. Thanks to Fred for
running this thing. Looking forward to the next challenge.
============================================================
=== >20 ==== poot ==== Andrew Hume ==== research!andrew =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> poot KILLED 9999.99 2349 Sep 22 08:23
===========================
... No form returned
============================================================
=== >20 ==== oct93 ==== David Simen ==== uhura!dcs =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> oct93 KILLED 9999.99 1044 Oct 25 17:02
===========================
PROGRAM: oct93 FROM: David Simen AT: uhura!dcs
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Overall approach: determine "obvious" approach (simple algorithm) and lang.
(C), code it. Run >= 3 times for timing; also reduce size by eliminating
white space, using some #define macros. Then go in 2 directions in parallel:
(1) look for incremental improvements in algorithm or program (e.g.,
eliminate function calls; fiddle with algorithm.
(2) look at the mathematics for a "short-cut" idea.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
Speed: (1) algorithmic improvements (e.g., rather than go step by step, try
to increment the counter in larger increments by doing a little more analysis;
(2) speed-ups, e.g., eliminating function calls by putting code in-line.
COMMENTS, LESSONS?
Will probably participate again, but was disturbed at finding myself tweaking
msecs off run time vs. improving program organization, maintainability, etc.
WHAT, WHERE, AND WHY ARE YOU?
Object-oriented design/development for > 5 years, use C++. Lots of GUI work.
============================================================
=== >20 ==== short ==== Ajay Gupta ==== intgp1!ajgupta =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> short KILLED 9999.99 561 Oct 8 17:15
===========================
... No form returned
============================================================
=== >20 ==== initial ==== Steve Keefe ==== ihlpf!keefe =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> initial KILLED 9999.99 1337 Oct 22 14:31
===========================
PROGRAM: initial FROM: Steve Keefe AT: ihlpf!keefe
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
I was going to try several methods, unfortunately I only had time
for the the brute force method ... (ie. just add 1 to both numbers
until I either found the answer or the numbers wrapped back on themselves)
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
My approach is so slow that I didn't bother to make the program
small.
COMMENTS, LESSONS?
I wish I could remain anonymous since my program stinks so badly.
WHAT, WHERE, AND WHY ARE YOU?
I've been programming in some form or another for 14 years
for AT&T and I love a challenge. I think this is a great opportunity
for programmers to have some fun doing things they love to do.
============================================================
=== >20 ==== s.forward ==== Bruce Hartman ==== cbvox!bruce =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> s.forward KILLED 9999.99 608 Sep 23 20:19
===========================
... No form returned
============================================================
=== >20 ==== potm.bas ==== Greg Fiore ==== aluxpo!fiore =====
PROGRAM SCORE SYS+USR(sec) CHARS DATE RECEIVED TIEBREAKER
==> potm.bas NO RUN 0.00 2197 Oct 29 16:40
===========================
PROGRAM: potm.bas FROM: Greg Fiore AT: aluxpo!fiore
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
I incremented B until it differed from A, then used a simple
fast algorithm to go through combinations of the other letters.
WHAT DID YOU DO TO MAKE THE THING SMALL? OR FAST?
I tryed to minimize the steps, calculations and decision statements
nested inside the algorithm.
COMMENTS, LESSONS?
I realize that a more numerical approach is necessary to reduce time.
If I want my entries to be run I must use C!
WHAT, WHERE, AND WHY ARE YOU?
I work at Allentown and evaluate the reliability of I.C.'s. Most of
the equipment I use is old and runs on PC Basic.
============================================================