Positions 14-40
Note - program listings may not print correctly due to HTML conflicts.
RESET Program entry descriptions (continued) positions 14-40
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
============== 14 ====================== QuaSimOdo =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
QuaSimOdo 1879997 389 358 31 75 Chris Hendrie
=================
QuaSimOdo was submitted by Chris Hendrie at cihendri@uwaterloo.ca
=================
++ Please summarize the algorithm used by QuaSimOdo
QuaSimOdo first computes for each subset of {0,...,9} the latest offset to
the necessary reset point, given only those digits for the trip-meter and
odometer suffix (hard to explain). This takes 1024 x 10 steps, but is
relatively quick. For each input number, it can then simply pick odometer
digits from left to right, verifying that the latest possible reset point
comes after the given input. This takes at most 6 x 10 steps, and so is very
fast.
++ What kind of tricks did QuaSimOdo use to minimize code length?
Everything I could think of. One #define, argc (aka. 'm') as a variable, ?:
wherever possible, etc. etc.
++ Here's what I hated (and loved) about this POTM's scoring:
I liked the combo of run time and code length. Looks to me like code-length
was the dominant factor, which I find a tad disappointing. I would perhaps
have made run time twice or three times as important.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a 3rd-year Computer Science undergraduate at the University of Waterloo.
I haven't found an interesting job yet. For fun, I juggle. Innermost secret:
I'm an arrogant young-un who chafes at losing to more experienced hackers.
How about a game-playing POTM?
=================================================================
============== 15 ====================== TheFinger =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
TheFinger 1879997 402 314 88 84 =Neil Weinstock
=================
TheFinger was submitted by Neil Weinstock at nsw@ariel.com
=================
++ Please summarize the algorithm used by TheFinger
First, if the input number was >= 987532, I set it to 0, because it would
roll over, so same difference.
For each number fetched, I called a recursive function that worked one
digit at a time, from left to right. For each digit, I do this:
if (this digit is not "used")
if (this is the rightmost (ones) digit)
figure out trip odometer value from available digits
if this solution works, print and return all the way up
else
recurse, next digit to the right
increment digit
That's basically it. There's plenty of optimization, naturally.
++ What kind of tricks did TheFinger use to minimize code length?
Much was algorithmic. Other than that, my favorite little tricks were:
1) Where possible, embed assignments into other statements, to
avoid the need for brackets. My favorite spot was at the end
of an arg list for a function call.
Example: printf("%d %d\n",v-t,v,h=0);
2) Perl-like constructs to eliminate an if().
Example: v-t= t, then it is possible to find a solution (in particular,
press reset at p - t) using the value under consideration for p[j],
and p[j] is fixed at its current value. If not, other values of p[j]
are considered until one is found for which a solution exists.
When values for all six digits of p have been found, the answer is
displayed: Reset is hit at p - t (where t is the smallest number made
from the digits not in p).
++ What kind of tricks did reset use to minimize code length?
Short variable names.
Maintained bit map of used digits instead of using an array of flags
and thus used less code for setting bits and initializing the list.
Removed all excess blanks, tabs, and newlines.
++ Here's what I hated (and loved) about this POTM's scoring:
I didn't like not knowing what the tiebreaker scores were.
I hated the "smallest source code size" scoring.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lucent; Holmdel; Currently working on a storage technology product;
Sing, act, play chess, etc.; That's for me to know...; None at the
moment.
=================================================================
============== 17 ====================== brauciens =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
brauciens 1879997 412 344 68 47 Krists Boitmanis
=================
brauciens was submitted by Krists Boitmanis at
acad.latnet.lv!ugale@kcig2.att.att.com
=================
++ Please summarize the algorithm used by brauciens
Array as follows:
[1|2|3|4|5|6!7|8|9|10]
First 6 - main odometer (D)
Last 4 - RESET odometer with digits in reverse oder (R)
Start at S[10]={9,8,7,6,5,4,3,2,1,0}
After some rotations of digits:
for (i=0;i<6;i++) {
k=S[9];
for (j=9;j>i;j--) S[j]=S[j-1];
S[i]=k;
for (j=9;j>i;j--)
/# making of D and R out of array #/
if (D-R>[given number of miles]) break;
else {k=S[j];S[j]=S[i];S[i]=k}
}
everything is ready for output.
++ What kind of tricks did brauciens use to minimize code length?
Efficiency of algorithm allways does the job.
++ Here's what I hated (and loved) about this POTM's scoring:
Lots of thanks to Fred for this overcrowded POTM! Everything was great!
More people, more enjoyment.
Congratulations to WINNERS!!!
++ COMPANY? LOCATION? DO FOR FUN?
Last year at Ugale Secondary School (high school).
Ugale is 40km from port Ventspils in LATVIA.
Programming, basketball.
=================================================================
============== 18 ====================== too_many_miles =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
too_many_miles 1879997 413 324 89 112 Kurt VandenBranden
=================
too_many_miles was submitted by Kurt VandenBranden at
KVD2@bipsy.se.bel.alcatel.be
=================
++ Please summarize the algorithm used by too_many_miles
combinatorial (sorry, but I can't explain any
better, it would take a few pages)
++ What kind of tricks did too_many_miles use to minimize code length?
Read every line of code 20 times, and check if it can't be skipped or
included in another statement.
Use the same variable if possible for different purposes.
++ Here's what I hated (and loved) about this POTM's scoring:
It's fun for once, but I wouldn't like to do this another time.
I worked a few hours on the base algorithm, and then the following weeks,
I was busy making it smaller and smaller and smaller and smaller...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a software engineer at Alcatel Bell in Belgium.
I read SF, I juggle, I compete in POTM.
I would like a POTM that doesn't depend on the speed of the language
you are using. The last 2 POTM's were very much about speed. It would be
nice to have a POTM that depends on the algorithm you write, where it
doesn't make a difference if you implement it in C, PERL, JAVA or even shel.
(But I don't have any ideas for such a POTM)
=================================================================
============== 19 ====================== odomontade =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
odomontade 1879997 421 300 121 65 D.McIlroy S.Dorward
=================
odomontade was submitted by D.McIlroy S.Dorward at doug@research.bell-labs.com
=================
/* Odomontade, by Doug McIlroy and Sean Dorward - programmers for fun
and profit in computer science research, Bell Labs, Murray Hill, NJ.
300 bytes when reduced to blank-free 80-character lines */
int f=1023, l, m, x[1024], t[90000];
main(i, j, k)
{
g(4,0,0,0);
g(6,f=0,0,0);
for(f = fopen(1[(int*)j], "r");
i = fscanf(f, "%d", &l) > 0;
vprintf("%d %d\n", t+j%m))
for(j=m; i t[k = i+j>>2<<1]?
i = k+2
:(j = k);
}
g(n, v, z, d){
if(n)
for( ; d<10; d++)
z&1< l?
t[m++] = l = n,
t[m++] = v
:0
;
}
/*
The method is to generate all possible answers - a table of final
odometer readings and reset values - then look up the answers by
binary search on reset value.
Why precompute answers for 10!/4!=151,200 different mileages, when we
will only be asked 1000? Because we don't know a good way to find the
next achievable final odometer reading. The odometer may have to pass
as many as 246 all-digits-different mileages before reaching an
achievable one. (Only 42171 are achievable.) Thus a fiendish potm
master could set 1000 problems that caused us to consider 247,000
different mileages. Betting that the potm master is not benevolent,
we arranged for our run time not to depend on his problems. (This was
a delicious speculation - how many other entries would take several
times as long per problem for 10 times as many problems in the finals
vs the preliminaries, while our time scarcely increased?)
g(n,v,z,d) generates in lexicographic order permutations of digits
0..9 taken n at a time.
d is a candidate for leading digit.
v is numeric value of string of decimal digits.
z is a bit mask giving the set of digits in v.
The loop in g tries digits in increasing order, checks (by testing
z&1< l) {
t[m++]=l=n;
t[m++]=v;
}
m is the table index.
v is the final mileage.
l is the previous final mileage.
n is the reset mileage.
LOW CUNNING TO SAVE CODE
Table-update code is executed in g at all recursion levels, not just
the final level where it's needed. In the first phase, this makes
entries in table cells that will never be used. In the second phase,
the code to guard against unreachable final mileages happens also to
guard against updates at other levels of recursion.
Vprintf is supposed to be used in connection with va_args to index
arguments one at a time in a printf-style argument list. The
misuse here to print two values from only one printf argument
happens to work on Suns. That argument, t+j%m, also handles
odometer wraparound.
Tricks to save or shorten declarations
omit header files
use old-style function definitions
reuse variables
eschew non-int variables; mistype non-int as int
use parameters, not local variables
Because table t has two-word entries, the binary search indexes the
low and high pointers, i and j, by two. i is initialized not to 0
but to 1 (the return from an unrelated test!), but this off-by-one
error washes out when i+j is divided by 4 in the binary search.
Savor the benefits of addressing argv[1] thus: 1[(int*)j].
Also the multiple uses of f
flag to distinguish first from second phase (f?)
mask for doing set complement (x[z^f])
test-free way to set argument of g conditionally (f&d)
stdio file handle (f=fopen(...))
Plus all the usual coding tricks:
embedding assignments in funny places, like argument lists,
subscripts, and for statements, sometimes to avoid
semicolons, sometimes to grab available values.
using comma expressions to avoid {} brackets.
using conditional expressions instead of if: || for 1-way;
?: for 2-way. For example, binary search becomes a
"one-liner":
for(j=m; i t[k = i+j>>2<<1]?
i = k+2
:(j = k);
*/
=================================================================
============== 20 ====================== The_first_try =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
The_first_try 1879997 438 394 44 125 Rolandas Gricius
=================
The_first_try was submitted by Rolandas Gricius at
lanteka.lt!rolandas@caig1.att.att.com
=================
++ Please summarize the algorithm used by The_first_try
That's simple: take as basis miles entered, then calculate miles at
the end, and then - miles travelled, increasing every digit while - <= .
++ What kind of tricks did The_first_try use to minimize code length?
Almost none. Standard ones are - one letter variable names, no
variable types in function declarations, freopen(..., stdin), you know,
they are standard ones.
++ Here's what I hated (and loved) about this POTM's scoring:
Very difficult to predict impact of speed differences between my and
test machines, complicated by different test (100 entries) and actual
(1000 entries) runs. (I hated it, of course).
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
UAB "Lanteka", Klaipeda, Lithuania. We are running three person ISP,
I'm the main UNIX administrator, programmer, consultant for leased lines
installation, etc. Secret? I almost hate computers sometimes. POTM
ideas? I have some. But not now :)
=================================================================
============== 21 ====================== eyes-on-the-road =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
eyes-on-the-road 1879997 443 331 112 87 Clive Dawson
=================
eyes-on-the-road was submitted by Clive Dawson at Clive.Dawson@amd.com
=================
++ Please summarize the algorithm used by eyes-on-the-road
The basic algorithm was simple:
Using the starting mileage (m), compute the next possible mileage
that consists of unique digits (x). Use the 4 leftover digits for
the trip odometer (t). Now check whether x-t >= m. If so,
this is a valid solution. Otherwise, go back and compute the
next higher value of x.
I used a refinement to this algorithm which speeded it up considerably:
Solve the problem by assuming that the rightmost n digits of both
odometers don't exist, for n decreasing from 3 to 0. This allows
the more significant digits to be determined more quickly, cutting
down on the number of times we need to iterate in the basic loop.
Another significant speedup was obtained by using a precomputed
array of powers of 10. This allowed much faster extraction of
individual digits. The alternate approach of working with
individual digits to begin with seemed to be a losing proposition,
since you would then have to worry about doing your own arithmetic.
(But given the vastly better performance of the winners, I'm
beginning to have second thoughts about this!)
Finally, I'm guessing that most everybody realized that you didn't
have to worry about wrap-around on the odometer. This was taken
care of by just making sure that your answer was printed modulo
1000000.
++ What kind of tricks did eyes-on-the-road use to minimize code length?
Nothing particularly spectacular. It was just a matter of trying
various styles of loops and if statements to see which would be
shorter. Of course you want to take maximum advantage of compound
statements, and creative use of the initialization, test, and
increment portions of 'for' loops.
At one point I switched to gcc, since it allows end of line
characters in literal strings. I tried to make the ends of
lines coincide with the places where a blank was required.
++ Here's what I hated (and loved) about this POTM's scoring:
I didn't like the fact that we were left in the dark regarding
specific scores. Certainly knowing that somebody had succeeded
in one third the time, or had a program which was half as long
would have motivated me to try harder. I think knowing more about
what we were up against would have contributed to an overall
improvement in the quality of the submissions.
Another interesting aspect was that the tradeoffs made between
execution time and program length depended on the speed of your
computer, not mine. This wasn't bad or good; just interesting.
One last bothersome aspect of this POTM was that since we didn't
know the contents of the input file or how it was generated,
it was hard to tune the algorithm. If you had told us that the
test file would consist of 1000 random numbers between 0 and
999999, my program might have been very different from one designed
to perform best on the "worst cases" which might have been
specially chosen.
=================================================================
============== 22 ====================== tracks =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
tracks 1879997 454 372 82 131 =Franz Korntner
=================
tracks was submitted by Franz Korntner at korntner@xs4all.nl
=================
++ Please summarize the algorithm used by tracks
The algorithm is generally described as:
Calculate an array containing 4 digit numbers where the digits are in
ascending order. The array in indexed by bitmapping ie. the number 2456
has an index of 1<<2|1<<4|1<<5|1<<6.
Then for all 1 million 6 digit numbers, calculate the bitmap (as
described above) and find the matching 4 digit number in such a way that
the OR'ing of both bitmasks result in all 10 bit positions being set. If
a number combination has been found, then the 6 digit number will
represent the final milage and subtracting the 4 digit number from the 6
digit number will represent the starting milage.
Given a certain starting milage, it is sometimes wiser to wait a bit
longer before pressing the reset to get a better end position. To catch
this, the found starting milages must be in ascending order for them to
be accepted/processed.
This operation will create a list of starting positions and 'trip
lengths' where the starting positions are in ascending order. The list
will be 42171 combinations long.
Finally for each number in the input list will be searched using a
binary search method, displaying the milage when the reset button should
be pressed, and the milage to wait before the result is achieved.
++ What kind of tricks did tracks use to minimize code length?
Put all variables in registers for speed, and use a macro for the 10
used for loops.
++ Here's what I hated (and loved) about this POTM's scoring:
I hated not knowing the scores of the other contestants, because it
gives no indication on how well the entry actually is, it just tells you
that all solutions are correct, nothing else. If I knew that first place
was an entry 140 characters smaller than my 372 character entry, I would
have taken a very different approach and not concentrate on speed
issues.
++ COMPANY? ICT Netherlands. (www.ict.nl) which is a dutch contracting company
LOCATION? Holland
JOB? Contractor, specialized in low-level concepts ie. OS, compiler,
debugger, library, encryption, compression, TCP/IP, device drivers,
parallel processors.
DO FOR FUN? POTM
INNERMOST SECRET? Well, actually I --CENSORED-- about it.
=================================================================
============== 23 ====================== JustOnce =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
JustOnce 1879997 475 439 36 23 Bob Lied
=================
JustOnce was submitted by Bob Lied at lied@lucent.com
=================
++ Please summarize the algorithm used by JustOnce
Choose digits beginning from the most significant. As each
digit is chosen, form the largest possible number that will
complete the odometer, and the smallest possible number that
will fill the trip meter. Then check that the constraint that
the chosen digit will create an odometer reading in range:
InitValue + TripMeter < Odometer + BiggestPossible
Continue to choose the next smallest available digit until
the constraint is satisfied.
The weak part of this algorithm appears to be forming the smallest
and largest numbers, which were the most expensive parts both in
program size and execution speed.
++ What kind of tricks did JustOnce use to minimize code length?
Unreadability -- no white space, single-character variables,
reuse of variables, no functions
Side effects -- ++/--, comma operator, embedded assignment,
coincidental calculation of values needed later
Control flow -- only while loops, goto
Correctness proof -- no bounds checking on loops because they were
known to terminate, elimination of special cases
++ Here's what I hated (and loved) about this POTM's scoring:
Never quite knowing whether speed or size could make a difference.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
COMPANY: Lucent Technologies
LOCATION: Naperville, Illinois, USA
JOB: software dilettante
FUN: basketball, classical guitar
SECRET: haven't produced a line of production code in three years
=================================================================
============== 24 ====================== rollback =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
rollback 1879997 475 325 150 114 Warren Montgomery
=================
rollback was submitted by Warren Montgomery at warren@psp.ih.lucent.com
=================
++ Please summarize the algorithm used by rollback
Brute force, try each odometer reading starting with the given
mileage looking for a solution and stopping at the first one. 3
tables were built in advance to speed things up: A mapping from 3
digits to a bit code (sum of 2^digit for each digit present) for
each 3 digit number with unique digits, an inverse mapping from bit
codes to lowest 4 digit number with remaining 4 digits for all bit
codes with 6 bits on, and a table giving the next higher 3 digit
number with unique digits for each one, allowing many impossible
numbers to be skipped.
++ What kind of tricks did rollback use to minimize code length?
Abusive (typeless) programming, comma expressions, ? expressions,
and a #define for a repeated loop.
++ Here's what I hated (and loved) about this POTM's scoring:
Combination of time and size was nice. Standings should have either
given both time and size, or been based on the same number of
numbers as the finals. The quirks of the POTM test machine
(e.g. lack of hardware multiply/divide, odd cache effects, no
optimization) make it very difficult to predict the space/time
tradeoff without seeing it perform under actual conditions.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for Lucent/Bell-Labs in Naperville Illinois on Intelligent
Network Architecture. I enjoy puzzles, and POTM is a pretty good one.
=================================================================
============== 25 ====================== odododo =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
odododo 1879997 501 412 89 86 Bob Ashenfelter
odododo was submitted by Bob Ashenfelter at ash@att.com
=================
++ Please summarize the algorithm used by odododo
The digits of the final odometer reading are computed one at a time
starting with the most significant which is initially set to the
corresponding digit of the starting odometer reading. The remaining
digits are sorted into the remaining odometer digits, highest to the
left, and the last four smallest digits are sorted into the trip
odometer, highest to the right. The result is the final readings
when the reset is pushed at the very latest point that leaves the
initial value in the most significant digit. Compute the mileage
at reset by subtracting the trip odometer from the total odometer.
If this is at or beyond the starting value, go on to the next digit.
If not then the initial digit cannot possibly be right. Increment
it (mod 10) and try again.
Subsequent digits are initialized to either the corresponding digit
of the starting odometer reading or, if it had been necessary to
increment ANY previous digit, to 0. (It is easier to just set all
subsequent digits to 0, but the cost in extra execution time is more
than the savings of 8 characters.) Then the remaining digits are
sorted and the reset is tested as above. This continues until all
six odometer digits are determined and then the answer is printed.
++ What kind of tricks did odododo use to minimize code length?
These are all pretty obvious:
* Use one-character variable names.
* Use as few variables as possible, reusing them wherever possible.
* Use pointer notation instead of array notation wherever it is
more concise.
* Use "," to terminate statements (except the last) in a block
instead of ";" and then remove the "{}".
* Move statements from the body of "for" loops into unused control
expressions and save the ";"s.
* Remove all extraneous white space.
* Use "#define" for repeated character sequences. (I could only use
it once, for "for (", and it saved only a couple of characters.)
* Use a new-line for unavoidable white space if it keeps line lengths
within the 80-character limit.
Perhaps my most creative trick was to use a single array for both the
final odometer digits and the trip odometer digits with the trip odometer
digits reversed so only a single sort was needed for both. And then I
padded the array with two additional digits which were never changed
from their default initializations of 0. These extended the trip odometer
to six digits and simplified the subtraction to obtain the reset mileage.
Another cute trick was to reuse the "argc" and "argv" arguments of main().
Of course I called them "c" and "v". Even though the initial value of "c"
was not used and it was not declared, it defaults to "int" and was sub-
sequently used as such. When I reused "v" as a pointer to an array of
integers, the compiler complained bitterly. So I lied to the compiler
and declared it "int*v;" instead of "char**v;". Not only was the compiler
deceived (not even a whimper), but I shortened the code by two characters
as well!
++ Here's what I hated (and loved) about this POTM's scoring:
If you, or anyone else, expect me to complain about the encouragement
of bad programming style, sorry..., I have no problem with that.
The following is neither love nor hate--just a comment. The score for
time was too small in comparison with the score for size. At the time
this was determined you probably expected them to be comparable, but you
really had no idea how efficient the best programs would be. Perhaps
you should have left this to be determined later, say by increasing the
number of input values until the winning program scored equally for both
time and size.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T ... until they sell us out--I'm in Submarine Systems.
Holmdel, N.J., U.S.A.
Circuit design.
Bicycling, sailing, grow orchids, travel.
No way...
You could publish the winning entry of this POTM as the problem for the
next POTM. First one to figure out what it does is the winner.
=================================================================
============== 26 ====================== outofgas =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
outofgas 1879997 508 331 177 41 Matthias Ruhl
=================
outofgas was submitted by Matthias Ruhl at ruhl@informatik.uni-freiburg.de
=================
++ Please summarize the algorithm used by outofgas
The program starts with the current meter and iteratevly computes the next
meter setting with 6 different digits. If the smallest number that can be
built from the four remaining digits is smaller than the difference of the
this and the original meter setting, we are done. Otherwise continue.
The tricky part is obviously to determine the next meter setting where all six
digits are different. This is done by going from the highest value position to
lowest value position and checking each time whether the digit at that position
already occurred (to the left of it). If it has, then
a) zero all digits to its right
b) repeatedly increase the digit by one until it
1. hasn't occurred before. Then we continue with the next position.
2. it is increased to 10. In this case, the overflow must be propagated
to the next higher position, where the loop begins again.
To avoid handling the special case where the meter turns from 999999 to 000000,
all meter settings greater than 987531 (=987654-123) are mapped to 000000 at
the beginning of the program.
++ What kind of tricks did outofgas use to minimize code length?
Only 'garden variety' C-code shrinking (reusing variables, shortening
expressions, etc.) - nothing really problem specific. And not a single
'#define' :)
++ Here's what I hated (and loved) about this POTM's scoring:
The scoring system itself (length+time) was, well, interesting :)
But I think it would have been even more fun if the actual scores had been
distributed with the ranklist.
The scoring method may also put people who have access to a Sparcstation at a
slight advantage, since the tradeoffs between speed and (code) length are
often quite counter-intuitive and also very machine-dependent.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm an undergraduate student majoring in Maths and CS at the University
of Freiburg, Germany, and will be graduating in summer 1997.
So hopefully I'll then have some more time to spend on a future POTM :)
=================================================================
============== 27 ====================== dodo =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
dodo 1879997 556 510 46 93 Jeroen Moelands
=================
dodo was submitted by Jeroen Moelands at moelands@nlr.nl
=================
++ Please summarize the algorithm used by dodo
I use arrays of 10 bits that tells which digits are already used
as integer indices to two arrays. One array contains the trip odometer
standing, which consists of the four lowest digits that are not used yet,
lowest digit first. The other one contains the highest possible value that can
be made with the unused digits. These arrays are filled first.
To avoid the wrap-around stuff, if the odometer has a value
higher than a certain maximum, I print the lowest milage possible.
For other odometer standings, a simple backtracking algorithm is used that
finds the minimal odometer value without much backtracking, using the two
arrays. The algorithm creates the odometer number from left to right. If the
entire number is found, it is printed. Otherwise, the lowest possible digit
is 'added' to the odometer number "head"; if the resulting number 'plus' the
highest possible "tail" to form 6 digits is greater than or equal to the given
odometer standing 'plus' the lowest possible trip odometer standing, try to
'add' the next digit (the highest standing possible to create with the given
"head" must be at least as high as the given standing plus the lowest possible
trip). If no digits are possible, backtrack. In this way the odometer standing
is found without much backtracking.
++ What kind of tricks did dodo use to minimize code length?
Tricks? Just spent a *lot* of time.
++ Here's what I hated (and loved) about this POTM's scoring:
Creating a fast program is a lot more fun than creating a small one.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work as a Software Engineer at the National Aerospace Laboratory (NLR) in
Amsterdam, Holland.
=================================================================
============== 28 ====================== Close_Enough =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Close_Enough 1879997 557 354 203 53 Vance Heron
Sorry ... no description available for Close_Enough
=================================================================
============== 29 ====================== Hoovey =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Hoovey 1879997 562 312 250 128 A.Halverson J.Halverson
=================
Hoovey was submitted by A.Halverson J.Halverson at alanh@microsoft.com
=================
++ Please summarize the algorithm used by Hoovey
We used a 6-element array of integers to represent the digits of the
odometer. To determine uniqueness, we employed a bit-field in which
bits were set if a digit was used in the main odometer. We proceeded
left to right (most significant to least significant digit). By
right-shifting 1 "current digit" times, we arrived at a unique bit in
the bit field. If the bit was already set, increment the current digit
and zero out all less sig digits. As soon as you found a digit not
already set in the bitfield, set it and move on to the next digit. If
you roll a digit (9 -> 0), you have to remove the previous digit's bit
from the bitfield and increment it. Once all six digits were found to
be unique, it was trivial to construct the trip odometer by testing bits
in the bitfield, LSB to MSB. If bit j wasn't set, multiply the trip
odometer by 10 and add j. This method guaranteed the smallest possible
trip odometer. Finally, just subtract main odometer from trip odometer
and test against input odometer reading, looping back if the test
failed.
++ What kind of tricks did Hoovey use to minimize code length?
We used "#define W while(" - every loop in our program was a variant of
the while loop. Also, the comma sequencing operator came in very handy
("f=x,y=j;" instead of "{f=x;y=j;}"). Another good one - define argv as
int*argv instead of char**argv. This works because
sizeof(int)==sizeof(char*). No #include files. No functions other than
main(). Of course, getting rid of that pesky whitespace helped as well
... %^)
++ Here's what I hated (and loved) about this POTM's scoring:
Having code size share importance with speed of execution is a bummer.
Maybe if speed was worth 2/3 and code size 1/3 in the second tiebreaker.
Maybe I'm just complaining because I don't have enough experience
writing unreadable C code ...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM
IDEAS?
Company: Microsoft Corporation
Location: Redmond, WA
Job: Quality assurance for a "popular database product"
Fun: Music - play, sing, listen
Secrets: You can't have any when you're married ... %^)
=================================================================
============== 30 ====================== gdrula =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
gdrula 1879997 597 471 126 124 Catalin Drula
=================
gdrula was submitted by Catalin Drula at gdrula@pcnet.pcnet.ro
=================
++ Please summarize the algorithm used by gdrula
If "a" is the initial number, I considered all the numbers starting
with "a" that have all the digits different.
With the left 4 digits I formed the smallest number "c".
If the difference between the current number and the initial number
is less or equal than c, than the current number is the number
we're looking for.
That's all.
++ What kind of tricks did gdrula use to minimize code length?
Not many.The usual C syntax + flags...
++ Here's what I hated (and loved) about this POTM's scoring:
I think the code length has too much importance in the score:
Wouldn't something like: 5*time+length have been better?
I like that you send the weekly status and nobody knew the other
contestants scores.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I learn at Bucharest High School of Computer Science.
I live in Romania and I'm 15.
Yes, I do it for fun.
In future I think you should give more difficult problems.
The algorithm should count more than some tricks to make the source
shorter.
If possible don't use the source length in the score.
Thanks for what you do,
=================================================================
============== 31 ====================== shortcut =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
shortcut 1879997 614 327 287 58 Jan Venema
=================
shortcut was submitted by Jan Venema at jvenema@lucent.com
=================
++ Please summarize the algorithm used by shortcut
For each A1 on input:
a) Start with A2 = A1.
b) Check if all 6 digits in A2 are different.
c) If different, then calculate B2 by using the remaining 4 digits.
Check if B2 <= A2-A1 then print A2-B2, A2 and continue with next A1 input.
d) Else, increment A2 with 10^n (depending on digits used) and restart at b).
++ What kind of tricks did shortcut use to minimize code length?
- Roll over is prevented by starting A2 as 0 when A1 > 987531.
- Use gcc compiler since it is forgiving and makes correct assumptions when
C input is incomplete (e.g.: no #includes used, direct parameter access from
main(), no 'int' declarations needed, any pointer can be used for fopen() and
fscanf() file parameter).
- Use a recursive algorithm: 6 deep recursion level, one for each digit in A2.
- Take advantage of priority ordering where possible, so fewer '()'
- I used a small program to reduce variable name length, remove spaces etc.
++ Here's what I hated (and loved) about this POTM's scoring:
To solve the POTM it was inevitable to write a second program that ensures
smallest possible code size.
Some hacking was required: how are parameters passed to main() program, and
to what extend can one fool passing of parameters to library functions.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Systems Engineering, Lucent Technologies in Huizen, the Netherlands.
jvenema@lucent.com
=================================================================
============== 32 ====================== turtle =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
turtle 1879997 659 392 267 38 Didier Barzin
Sorry ... no description available for turtle
=================================================================
============== 33 ====================== odor =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
odor 1879997 667 313 354 98 Edwin Berlin
Sorry ... no description available for odor
=================================================================
============== 34 ====================== What_A_Trip =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
What_A_Trip 1879997 668 429 239 25 Robert Morrison
Sorry ... no description available for What_A_Trip
=================================================================
============== 35 ====================== bitsrock =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
bitsrock 1879997 669 551 118 116 Pete Demoreuille
=================
bitsrock was submitted by Pete Demoreuille at pbd@gate.cybernex.net
=================
++ Please summarize the algorithm used by bitsrock
precalculate all valid 6 digit numbers and the digits used by
them. also precalculate the all the lowest 4 digit numbers and
the digits that they do not use. then do a binary seach in the
6 digit numbers for the first number greater than the given.
while the differnece of the original number and the 6 digit number
in the refrence place of the 4 digit number that does not use the
digits in the 6 is less than the number of miles moved, try again.
else print the proper numbers.
++ What kind of tricks did bitsrock use to minimize code length?
efficiency, no redundancy by way of #defines when it would help...
++ Here's what I hated (and loved) about this POTM's scoring.
nothing. it was pretty fair for the problem.
=================================================================
============== 36 ====================== Porsche =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Porsche 1879997 677 576 101 49 Michael Strauch
=================
Porsche was submitted by Michael Strauch at strauch@metronet.de
=================
++ Please summarize the algorithm used by Porsche
For every starting point [A], Porsche does the following:
a) Increase [A] until you find a point where all 6 digits are different.
Lets call this number [A2].
b) Let [B] be the smallest number containing the 4 remaining digits.
c) If ([A2]-[A]) MOD 10^6 >= [B], [A2] is the earliest point at which
ten different digits appear on the odometers, and ([A2]-[B]) MOD 10^6 is
the point where to press the reset button.
d) If ([A2]-[A]) MOD 10^6 < [B], replace [A] by [A2] and go back to step a).
How I tried to get the program fast
-----------------------------------
I used a lot of small tricks to increase the speed of the program. Here
are the main ideas:
- "Porsche" stores the mileages [A] as a vector of 6 Digits "int Dig[6]";
when I need the mileages value, I use the expression
(((((Dig[5]*10+Dig[4])*10+Dig[3])*10+Dig[2])*10+Dig[1])*10+Dig[0])
- Increasing of [A] is not done "one by one"; instead, "Porsche" increases
the leftmost digit appearing twice first.
- Porsche adds "123" to the starting point before running the main
calculation loop, because [B] cannot be smaller than that.
- Some "register" variables are declared (GCC then does some register
optimization, even if the optimizer is not used)
I made a second implementation of Porsche, storing [A] as an "int", which
was more than 100 bytes shorter than my entry, but it needed approx. 4 seconds
more for 1000 numbers.
++ What kind of tricks did Porsche use to minimize code length?
I used an awk script to "compress" my program to a real short one:
- all comments, every empty line and all unneccessary whitespaces are stripped
out of the text
- the lines are concatenated if they don't exceed 80 characters
- the variable and function names are replaced by short names of one letter
++ Here's what I hated (and loved) about this POTM's scoring:
- I think "code length" is overweighted by this POTM's scoring; letting
the speed score be "seconds*1000" instead of "seconds*100" would
be a much more interesting challenge (in my opinion), because you have
much more room for inventing a real good algorithm.
- On the other hand, I never saw as many programmers as ever here at
this contest - the problem makes it very easy to build a correct entry with
less than 1000 bytes, and the scoring gives them all a chance to win the
contest not by inventing a complicated mathematical solution, but by
optimizing the code for shortness. I think, this is a very good point
for this kind of scoring.
=================================================================
============== 37 ====================== vanb =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
vanb 1879997 678 384 294 13 David Van_Brackle
Sorry ... no description available for vanb
=================================================================
============== 38 ====================== thewinner =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
thewinner 1879997 694 403 291 70 Ravi Nemlekar
=================
thewinner was submitted by Ravi Nemlekar at ravindra@airmail.hobl.lucent.com
=================
++ Please summarize the algorithm used by thewinner
Read the input number. Keep incrementing the number till all the
digits in it were unique. The 4 digits not in the number are the
"trip" miles. If the number - trip < input, goto incrementing.
++ What kind of tricks did thewinner use to minimize code length?
1. Removed unrequired code (like error checks, redundant code)
2. Improved the algorithm.
++ Here's what I hated (and loved) about this POTM's scoring:
Loved: Making the code faster
Hated: Making the code smaller.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company: Lucent Technologies, Holmdel, New Jersey
Do for fun: Meet people, action Movies, music.
Innermost secret: Motivated to do something.
POTM ideas: Thinking...
=================================================================
============== 39 ====================== 1000000 =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
1000000 1879997 727 561 166 105 David Wales
=================
1000000 was submitted by David Wales at david.wales@waii.com
=================
++ Please summarize the algorithm used by 1000000
In a loop : read the number in, setting up a lookup of integers used,
then, in an inner loop, check that we have a solution, else,
recursively, keep incrementing the rightmost number, doing sensible
things with the loookup on the way, until the next candidate is found
with non repeated integers. Checking for a solution is to use the
remaining four numbers in the lookup, in order.
++ What kind of tricks did 1000000 use to minimize code length?
Replace common code with function calls so long as run time didn't
increase too much. Replace code with macros, remove all blank space (
except end of lines ). Reuse variables, make all variables global, use
function parameters defaulting to int. Lots of pointer stuff.
> ++ Here's what I hated (and loved) about this POTM's scoring:
This became an obfuscated C contest. On my machine run time, for 1000
problems, is far less than code length so squashing code became a
priority. Maybe should have deducted points based on some measure of
unreadability? Alternatively could have issued a beautifier through
which all code would be crunched and do an ls -l on its result. Maybe,
if it's to be an obfuscated c contest, add a score measuring the
number of unique symbols in the code - the more the worse!?
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Western Geophysical, Bedford UK. Software bloke.
=================================================================
============== 40 ====================== trees =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
trees 1879997 730 436 294 37 Dave Lynch
=================
trees was submitted by Dave Lynch at dflynch@att.com
=================
++ Please summarize the algorithm used by trees
Increment the odometer until all digits are different.
Permute the remaining 4 digits to get the trip odometer.
If I haven't traveled this far, go another mile and repeat.
++ What kind of tricks did trees use to minimize code length?
Just the obvious.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T
Holmdel, NJ
Write software to design data networks.
Stay away from work.
Secret.