Positions 1-13
Note - program listings may not print correctly due to HTML conflicts.
86 of 131 entries returned program summaries ... THANKS!
Hope to see you all in the NEXT POTM!!!
I've divided the program summaries into four pieces of mail ...
covering the top 13 finishers, then 14-40, 41-80, and 81-131.
The mirror sites should be updated shortly ...
*** http://www.cs.washington.edu/homes/corin/POTM.PAGES/
*** http://potm.ffast.att.com/ INSIDE AT&T only
*** http://icds.micro.lucent.com/POTM INSIDE Lucent only
Thanks for participating!
=Fred
====================================================================
RESET Program entry descriptions
Beware of long mail .... but there ARE gems buried!
Even if you don't study the whole thing, you might
want to check out the first four or five writeups!
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).
There are also Code listings available on request.
If you need even more detail - contact the authors - not ME!!!
=Fred
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
============== 1 ====================== driveL =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
driveL 1879997 274 232 42 102 W.Burley A.Goldstein
=================
driveL was submitted by William Burley and Arthur Goldstein at
jolt!wburley@ffast.ffast.att.com and jolt!arthur@ffast.ffast.att.com
=================
Here is the entire program ... an annotated version is available on
the POTM web sites (or request one by mail if you don't have web access)
d,r,i,v,e,L;*_;main(a,b){for(L=fopen((_=b)[1],"r");*_=fscanf(L,"%d",&v,e=1e6
)>0;printf("%d %d\n",r,r+d))for(memcpy(b+4,b,d=123),v*=v<=(r=987531);e;_=(a=
r-(e-i)*_[*_])= 342243 holds)
swap 8 and 7: 347986 0125 (347986-0125 >= 342243 holds)
swap 7 and 6: 346987 0125 (346987-0125 >= 342243 holds)
swap 6 and 5: 345987 0126 (345987-0126 >= 342243 holds)
swap 5 and 2: 342987 0156 (342987-0156 >= 342243 holds)
The next swap would be between the 2 and 1, but we don't do this swap
because it would violate the invariant. Thus, we have determined that the
next digit is 2. Note that, as stated above, the remaining available digits,
9, 8, 7, 6, 5, 1, and 0, are in decreasing order from left to right in the
odometer followed by right to left in the trip odometer.
Our implementation of this algorithm does not keep track of the odometer,
but only the trip odometer and the reset mileage.
We use an array to keep track of available digits. We actually keep the
differences between available digits, with the first entry of the array
used as a pointer to the beginning of the list. Initially the array is
{1,1,1,1,1,1,1,1,1,1,1}, which corresponds to the list 9,8,7,6,5,4,3,2,1,0.
To delete an element from the list, we change the value of its predecessor
to skip over it (or change array element 0 to skip over the first part of
the list). Thus, if the array is {3,_,_,2,_,1,1,2,_,1,1} (where "_" means
the value doesn't matter), then the list of available digits is 7,5,4,3,1,0.
Keeping the list of available digits in this manner has the advantage that
when we swap two digits, the difference between the new reset mileage and
the old reset mileage depends on the difference between the digits - the
actual values of the digits doesn't matter.
For each position in the odometer and trip odometer, there is a value
that we call the "difference amount" for that position. The difference
amount of a position tells how much the reset mileage changes when the
digit in that position is increased by 1. The difference amounts for the
positions are as follows:
odometer: 100000 10000 1000 100 10 1
------ ------ ------ ------ ------ ------
trip odometer: -1000 -100 -10 -1
------ ------ ------ ------
When two digits are swapped, call the position of the first digit in the
odometer the "current position" (this is the position whose digit we are
trying to determine) and the position of the other digit the "swap position".
Thus, in the following two examples, "a" is the current position and "b"
is in the swap position.
_ _ a _ _ _ a _ _ b _ _
_ _ b _ _ _ _ _
When two digits are swapped, it is easy to compute the new reset mileage
as follows:
let e = difference amount for the current position
i = difference amount for the swap position
X = difference between the two digits
then
new reset mileage = old reset mileage - (e - i) * X
If the swap position is in the trip odometer, then the new trip odometer
is computed as follows:
new trip odometer = old trip odometer - i * X
--------------------------------------------------------------------------------
Here is the final version of the program:
--------------------------------------------------------------------------------
d,r,i,v,e,L;*_;main(a,b){for(L=fopen((_=b)[1],"r");*_=fscanf(L,"%d",&v,e=1e6
)>0;printf("%d %d\n",r,r+d))for(memcpy(b+4,b,d=123),v*=v<=(r=987531);e;_=(a=
r-(e-i)*_[*_])0;
printf("%d %d\n",r,r+d))for(memcpy(b+4,b,d=123),r=987531,v*=v<=r,e=1e6;e;a=r-
(e-i)*p[*p],p=a0; /* putting *p here sets b[0] to 1 if */
/* there's more input */
printf("%d %d\n",r,r+d)
)
for ( memcpy(b+4,b,d=123), /* initialize list of available digits */
/* (this copies b[0] into b[1],b[2],..., */
/* setting b[11],...,b[123] unnecessarily, */
/* but it saves characters) */
r=987531, /* = 987654-0123 */
v*=v<=r, /* set v=0 if it's too large */
e=1e6; /* really should be i=e=1e5 here. This */
/* just happens to work - the first time */
/* through the loop is wasted (and b[] */
/* becomes {2,_,1,1,1,1,1,1,1,1,1,1}, so */
/* the previous description of b[] is a */
/* bit of a lie.) */
e;
a=r-(e-i)*p[*p], /* compute new reset mileage for this swap */
p= as+4;i=a-l<
b?*p:memcpy(q=s,s+1,--p-s),*p=*q,*q++=i)for(*s=b=i=a=0;a=a*10+s[10-i],i<5;b=b*
10+s[i++]);}}
=================
++ Please summarize the algorithm used by POTM9609
To explain what the algorithm does, let us suppose that it has already
found the first two digits of the ending value for the large odometer
and it is searching for the third one:
problem start value = 100109
large odometer 10xxxx
small odometer xxxx
The smallest available digit is put in the third position:
large odometer 102xxx
then, the algorithm check whether it is high enough, by composing the
highest value with those three initial digits and subtract the lowest
possible value for the small odometer:
large odometer 102987
small odometer 3456
The difference is 99531, that is less than the starting value: this
means that the mileage is not enough to allow the small odometer to
get to the wanted number (that is the minimum with the chosen initial
digits). Therefore, the program exchange the chosen third digit (2)
with the one immediately greater, among those not already used (3).
large odometer 103987
small odometer 2456
Now the difference is 101531, that is greater than the starting number:
this means that there is enough mileage to let the small odometer get to
the wanted number, i.e. 3 is the mimimal acceptable digit in that
position. Now the program shift to the next position, repeating the
process:
large odometer 103298
small odometer 3456
etc.etc. In the submitted program, this algorithm is implemented by
putting all digits as 1-byte binary numbers in an array and initializing
it to the value {0,1,2,3,4,5,6,7,8,9}, where the initial value for
the large odometer is 987654 and for the small odometer is 123. The
algorithm just described is then executed by swapping and shifting elements
in that array.
++ What kind of tricks did POTM9609 use to minimize code length?
1) exploiting the weaknesses and tolerance of the C compiler (no
header files, default types=int, int* to int assignment, etc.)
2) , (comma) operator whenever useful, for putting more instructions
in a line and avoiding parenthesis; comma-separated are also
used in the second operand of conditional assignments (xxx?a,b,c:d)
3) careful usage of initial and final value of variables in 'for' loops
4) obviously, use of ++/-- operators.
++ Here's what I hated (and loved) about this POTM's scoring:
Not knowing the score got me nervous, but it compelled me not to give up.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
COMPANY: I work as a partner in two companies: BLUESOFT and I.S.& O., the
first one making (mainly) PC-based software, the second one system
integration and engineering for large accounts.
LOCATION: ROMA, ITALY
JOB: System architect / engineer, consultant.
DO FOR FUN: Reading, skiing, caring of my daughters and... programming.
INNERMOST SECRET: Obstinacy.
=================================================================
============== 3 ====================== Spinner =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Spinner 1879997 309 268 41 82 Alex Popiel
=================
Spinner was submitted by Alex Popiel at popiel@rintintin.Colorado.EDU
=================
Note - expanded code is available on the web sites. Alex's entry was:
main(a,v,b,c,i,z)int*v;{for(i=fopen(v[1],"r");~fscanf(i,"%d",&a);printf("%d %d
",b,c)){char*k,*p=v+3,*r;for(c=10;*--p=--c;);for(a*=a<987532;k=p++,p-9p+3;b=b*10+*r);}}
=================
++ Please summarize the algorithm used by Spinner
In the course of the contest, I used three different algorithms
for Spinner. In the beginning, I started with a simple counter
that ran through the successive odometer readings, looking for
ones that had all digits different and had a valid trip-odometer
value. My second algorithm used ordered permutations to find
only mileages with all digits different, and again these were
successively tested until a valid solution was found.
My final algorithm was much different from the above. Instead of
testing multiple mileages for appropriateness, my final algorithm
builds a single mileage digit by digit such that it is guaranteed
to be a valid solution. This is rather faster than the successive
testings.
Spinner starts by adjusting the input number to prevent odometer
overflow. It next initializes a sorted pool of all available
numerals (initially all of 0 through 9 inclusive). For each digit
in the destination mileage (working left to right), the lowest
value numeral which can produce a valid solution is picked. The
validity is checked by building the highest value odometer reading
possible with that numeral in place, and subtracting off the
lowest value trip-odometer reading built from the remaining four
numerals; if the resulting number is not less than the input number,
then the numeral picked for the digit in question is valid. Each
digit of the destination mileage is filled in this way, until a
complete solution is found. (As a note: having a sorted pool of
available numerals makes building the highest possible odometer
reading and the lowest possible trip-odometer reading _much_
easier; just read an appropriate number of numerals off each
end of the pool.)
++ What kind of tricks did Spinner use to minimize code length?
Spinner uses many tricks to minimize code length:
1) Use K&R-style function declaration to avoid specifying the
return type of main(), and the type of its parameters.
2) Put all int variables in the parameter list for main(), so
their type does not have to be explicitly specified. (Note:
this will cause some implementations to core dump through
trashing the stack. In that case, put the int declarations
in global scope, still leaving off the 'int' keyword.)
3) Use the comma operator to avoid need for compound blocks.
4) Use the memory space guaranteed available in argv instead
of declaring an array.
5) Use for loops instead of while loops, and pack stuff into
the expression_1 and expression_3 sections of the for loop
instead of having compound blocks within the loop.
6) Use side effects in the expression_2 part of the for loops.
7) Don't #include anything.
8) Use operator precedence to eliminate parentheses.
9) Use pointer arithmetic on pointers to different size types,
knowing the sizes of the various types, to reduce offsets
of 12 to offsets of 3.
10) Use only implicit type conversions.
11) Don't initialize variables if their values don't matter.
++ Here's what I hated (and loved) about this POTM's scoring:
I would have liked to see the full scores of everyone in the
weekly updates. (I just had to say it...)
I would have preferred a token-counting size measurement instead
of the character counting measurement. (Problem: what constitutes
a token in a perl/sed/awk regex?)
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
In order: No. SF Bay Area. Consultant for hire. Think, code,
play games. I'm not real. Interference pattern simulators.
=================================================================
============== 4 ====================== potm_miles =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
potm_miles 1879997 312 263 49 109 Alexey Zhelvis
=================
potm_miles was submitted by Alexey Zhelvis at lesha@mcs.spb.su
=================
i=0,A,s,f,b,j;F(I,N){N=1<999?I>2e4?s=0:F(I*10),
A+=N=1,-I*9:I,~A&N||f0){
A=2;f=9999;F(1);printf("%i %i\n",f-b,f);}}
=================
++ Please summarize the algorithm used by potm_miles
I am constructing 6-digits numbers with all different digits,
then I calculate the lowest possible value of the second
odometer, and then I compare start value + value of the
second odometer with the 6-digits number I have constructed.
When this number is greater, I stop and print result.
In order to search faster, on first steps I am changing
the highest digits, assuming the lowest are all 9.
++ What kind of tricks did potm_miles use to minimize code length?
I replaced some "if" statements with ? : operator, some "if" statements I
replaced with || operator in order to execute second expression with
side-effects only if the first expression is false.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I am working as a programmer in Marine Computer Systems,
Jont British-Russian venture, located in Saint-Petersburg, Russia.
=================================================================
============== 5 ====================== alphabet_soup =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
alphabet_soup 1879997 316 240 76 46 =Andre' Wilhelmus
=================
alphabet_soup was submitted by Andre' Wilhelmus at wilhelmus@lucent.com
=================
Here is the entire program ... an annotated version is available on
the POTM web sites (or request one by mail if you don't have web access)
b;e;m;r;u;main(s,v)int*v;{for(v=fopen(v[1],"r");u=~fscanf(v,"%d",&s);m=!printf(
"%d %d\n",e-r,e))for(s*=s<987532;u--&7;m=--m*10)for(b=4;b+=b;b&u?n(u^=b,9),n(4,
r^=e=r),u^=b*=e-r>13|1)u>>d&8?r=r*10+d,--c:0;}
=================
++ Please summarize the algorithm used by alphabet_soup
The summary is longer than the whole program. ^_^
If the start mileage causes the meter to go through zero then
the start mileage is bumped to zero.
A bit field of unused digits is maintained.
The end mileage is assembled digit by digit from left to right
with increasing digit values until 'end - reset >= start' is true.
The end mileage is completed with unused digits from left to
right and high to low.
The reset counter is assembled with unused digits from left to
right and low to high.
++ What kind of tricks did alphabet_soup use to minimize code length?
Well, I wanted to rename alphabet_soup to "%d% d\n" to save
7 characters but the POTM master does not like spaces,
let alone a real linefeed. ^_^
Break all the portability rules.
Collapse two variables into one twice.
Use a bit field instead of an array.
Keep the for(;;) expressions filled.
Avoid commas in for(;;) expressions.
Avoid if.
Use a function.
++ Here's what I hated (and loved) about this POTM's scoring:
I hate not seeing my and the other scores.
++ COMPANY? Lucent Technologies.
++ LOCATION? Hilversum, The Netherlands.
++ JOB? Application programmer.
++ DO FOR FUN? Trying to learn Japanese.
++ INNERMOST SECRET? I feel obfuscated. ^_^
++ POTM IDEAS? Something simpler next time, please. ^_^
=================================================================
============== 6 ====================== Mercedes =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Mercedes 1879997 330 261 69 62 Harm Jetten
=================
Mercedes was submitted by Harm Jetten at hjetten@lucent.com
=================
a[10],s,t,m;g(n,i){for(t=m=i=0;i<6;i++)t=10*t+a[in==t-m0;printf("%d %d\n",l-s-c[m],l-s))for(m=0,l=s*=s<987532,g=1000000;g/=
10;s-=x,m=n)for(v=s>0?s/g:0;m==(n=m|1<0;printf("%d %d\n",l-s-c[m],l-s))
// go through each odometer digit starting with the most significant
// shortcut wrap around large readings
for(m=0,l=s*=s<987532,g=1000000;g/=10;s-=x,m=n)
// shortcut first guess if s is positive
// incrementally guess until a large enough number is found
for(v=s>0?s/g:0;m==(n=m|1<= [A1] ==> [A2]=2..... is o.k.
Second digit of [A2]:
[A2]=21....(*) worst case: [A2]=219876
[B2]= .... [B2]= 0345
[C]=219531 >= [A1] ==> [A2]=21.... is o.k.
The same is repeated then for the third digit: [A2]=213... is o.k.
Fourth digit: [A2]=2130.. rejected because [C]=208531<[A1];
[A2]=2134.. o.k.
Fifth digit: [A2]=21340. rejected, [A2]=21345. o.k.
Sixth digit: [A2]=213450 rejected, [A2]=213456 o.k. with
[B2]= 0789, [C]=212667>=[A1]
(*) Here note, that I begin with [A2]=21.... instead of [A2]=20.... as
in the description above. That is becase 20....<212000 despite
the yet unknown digits, and not testing such cases extra made
the program some hundredths of seconds faster (about 0.20 secs
on average for the 1000 numbers on Fred's machine) by making the
code about 15 chars larger.
++ What kind of tricks did forD use to minimize code length?
Huh! Too man too small tricks to tell about every one of
them, or to call one or the other more important than
the others. In general, I mostly tried not to compute
something two times (in my first version I had to compute
even [B2] twice, which saved me over 40 chars after changing
it), to use as few parentheses and keywords as possible
(by putting once two 'for'-loops together I had both of them:
I saved the one 'for', the parentheses, and also the brackets
for another for, making the code again about 7 bytes smaller...
from that comes also the name 'forD' as I could 'D'elete one
'for')...
++ Here's what I hated (and loved) about this POTM's scoring:
In the beginning I actually didn't like that there were so
few input-lines, so that the code length was very important.
But with time I liked it, being happy for just one or two
bytes I could save here or there.
But I still think it would be better, if you would show in
the system-tests also the code-length and times of the
other programs, as one would try harder having a 'target'
instead of 'just do the best you can and see if you move
up the list next week!' (not complaining, just an opinion ;-) )
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I am from Greece (the best greek entry if you didn't notice; two
greek entries in the top-ten !!! :-) ) and making now my PhD
in electrical engineering (neural networks) in the Technical
University Munich (Germany).
For fun I like computers (programming, linux, internet),
travelling, taking photos (the last two can easily be combined :-) )
and developing photos (black and white... just started with that
one... still a beginner).
Innermost secret ????? I thougt it was secret... It is so
secret, that I even don't know myself.
I would also like to thank you, Fred, for the nice contest
you organize, and I am looking forward for the next problem.
=================================================================
============== 10 ====================== 14theRd =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
14theRd 1879997 349 291 58 27 Happy Hacker
Sorry ... no description available for 14theRd
=================================================================
============== 11 ====================== metritis =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
metritis 1879997 349 304 45 129 Apostolis Dimitromanolakis
=================
metritis was submitted by Apostolis Dimitromanolakis at apdim@hol.gr
=================
++ Please summarize the algorithm used by metritis
The algorithm proceeds from the left to the right guessing each digit correctly
for the 6-digit odometer. We always start with 987531. After each step we
subtract 10^(digit-place-1) and a value choosen from the set
{-10000,-1000,-100,-10,-1,1,10,100,1000,10000} (starting with the first number
and proceeding to the right after each step). Note that this value does not
change for used digits but it IS subtracted. The rest is a bit complicated...
++ What kind of tricks did metritis use to minimize code length?
Many, but the most important are one-digit variables and common expression
elimination. (well I'm not a C expert, I learned C a few months ago)
++ Here's what I hated (and loved) about this POTM's scoring:
It was fun trying to make a small unreadable program, but the execution machice
was SLOW ( same speed as my old 386DX/40 ).
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Greetings from Chania a small town at the island of Crete in Greece. I think
that I'm too young to have a real job but I take care of a unix server for an
ISP. What I enjoy to do is: electronics in general, microcontroller
programming, C/C++ and Linux (over all)...
=================================================================
============== 12 ====================== big-n-slow =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
big-n-slow 1879997 362 287 75 95 Vladimir Schipunov
=================
big-n-slow was submitted by Vladimir Schipunov at
vschipun@cammail1.attmail.com
=================
++ Please summarize the algorithm used by big-n-slow
Recursion to iterate numbers with different digits. Precalculation
of often used numbers (values of small odometer). Plus magic with
digit 0 when it is on the first or second position of the input
number. Following statement is true:
If N=_abcdef_ is input number, A=_ijklmn_ is value of big odometer
and B=_xyzt_ is value of small odometer, where i,...,t are different,
then none of a or b equals to x,y,z,t.
It means that if on the first or second position of N there is 0,
then A >= N+1234, otherwise A >= N+123. This saves up to 50% of time
for simple recursion.
++ What kind of tricks did big-n-slow use to minimize code length?
Reused code and variables
Implicit declarations
"a || b", "a ? b : c" instead of if/else
Merging two cycles in one
"," instead of ";" to eliminate "{}"
++ Here's what I hated (and loved) about this POTM's scoring:
Scoring was OK. The combination of algorithm and programming
techniques determined the winners. There were a plenty of
available algorithms and the problem was to pick up the right one.
However, I don't think it's a good idea to write in POTM_09_96
manner more than one program in a year - it's spoiling style.
I did not like much the problem itself, but the competition was
really interesting.
COMPANY? Velankani Information Systems, consultant in AT&T
LOCATION? Holmdel, NJ, USA
JOB? C++ in client/server project (PricerX)
DO FOR FUN? TV, PC, etc.
INNERMOST SECRET? Not at this time
POTM IDEAS? What about short-term problems? Or several at once?
=================================================================
============== 13 ====================== fourfor =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
fourfor 1879997 378 264 114 12 =Julius Collins
=================
fourfor was submitted by Julius Collins at jpc@esun.ho.att.com
=================
++ Please summarize the algorithm used by fourfor
initialization:
precompute "minimum 4-digit values of unused digits" array
e.g. m4dvud[{0,2,6,7,9}] is 1345.
in the code, this is more like m[(1<<0)+(1<<2)+(1<<6)+(1<<7)+(1<<9)] = 1345.
/* the following ignores wraparound from 999999 to 000000 but easy to handle */
for each input:
set g /* current guess */ = input
for(k=1;k<=6;++k) /* actually implemented by (d=100000;d;d/=10) */{
if(k'th digit of g matches an earlier digit
|| (input + m4dvud[first k digits of g])
> (largest number matching g in first k digits) ) {
reset g = 1 + (largest number matching g in first k digits)
restart k loop
}
if((input + m4dvud[first k digits of g]) > g)
reset g = input + m4dvud[first k digits of g])
}
print g - m4dvud[6 digits of g], g
++ What kind of tricks did fourfor use to minimize code length?
scratch and claw, lie about data types, avoid FILE*'s completely.
++ Here's what I hated (and loved) about this POTM's scoring:
didn't like the order-of-entry tiebreaker (but it turned out not to matter!)
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T HO(for now) 1E-423, software tools development/analysis.
=================================================================