Positions 41-80
Note - program listings may not print correctly due to HTML conflicts.
RESET Program entry descriptions (continued) positions 41-80
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
=================================================================
============== 41 ====================== best_name =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
best_name 1879997 738 615 123 97 David Roe
=================
best_name was submitted by David Roe at roe@research.att.com
=================
++ Please summarize the algorithm used by best_name
Step one is quick routine for finding the odometer setting that was
at least as large as the current setting, but that uses all different
digits. Then I arranged the remaining four digits and subtracted
to see if this was consistent with the initial odometer setting.
If not a solution, the program incremented the current setting
and went back to step 1.
Speed tricks: by looking at the results on all 1000000 initial odometer
readings, I found that the final digit of the solution was never 0 or 1.
And there was another trick if the result of the subtraction was too
far below the initial odometer.
++ What kind of tricks did best_name use to minimize code length?
Nothing enlightened: Short variable names, a couple of macros, and #ifdefs for
expunging all the debugging code. I found it useful to automate
all the code shortening stuff in a batch file that used lex so
that I could shorten succesive version of the "real" code without having
to do it by hand multiple times.
++ Here's what I hated (and loved) about this POTM's scoring:
Last time Fred pulled this "minimum progam length" stunt I swore
I'd never do it again. Well, what can I say? This time I mean it, I'll
really truly never do it again.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T Labs - Research, speech recognition. I love to fool around programming.
=================================================================
============== 42 ====================== Jack =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Jack 1879997 789 477 312 118 Justin Legakis
=================
Jack was submitted by Justin Legakis at legakis@graphics.lcs.mit.edu
=================
++ Please summarize the algorithm used by Jack
Of the 10! combinations, only 42171 are "interesting" -- that is,
you can always find the best answer by only considering those 42171
final positions. Jack first makes an array of these solutions.
Then, for each input miliage, Jack finds the solution with a binary
search through the array.
Jack actually stores pairs of values, the final odometer value, and
the greatest odomeder value at which the trip odometer can be reset
to arrive at the final value with all 10 digits different. The search
is simply looking for the smallest starting value greater than the
input. (This algorithm is correct only after selecting the 42171
"interesting" solutions. It would fail if Jack did not weed out the
others.)
++ What kind of tricks did Jack use to minimize code length?
minimizing and reusing variables, ?: operator, #defines, nothing too
fancy. Wished I could find alternatives to using fopen(), scanf(),
and printf(). Here's my binary search, with logic to handle wrap-
around:
for(l=0,i*=p>*S&p<=S[i=n-1];i-l>1;p>S[t=(i+l)/2]?l=t:i=t);
++ Here's what I hated (and loved) about this POTM's scoring:
I like POTM's that are determined by the first score, not the
tiebreaker...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Graduate student at MIT.
=================================================================
============== 43 ====================== kindly.accept =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
kindly.accept 1879997 795 639 156 108 P.Harode P.Patwardhan
=================
kindly.accept was submitted by P.Harode P.Patwardhan at pnh@ee.iitb.ernet.in
=================
++ Please summarize the algorithm used by kindly.accept
/* Program */
#include
main(int argc, char *argv[])
{
char num[12], not_used[11],*c;
register i,j,k,l;
FILE *fp;
fp=fopen(argv[1],"r"); /*Open datafile*/
while(fscanf(fp,"%s",c=num+5)!=EOF) { /*Loop until EOF*/
while(strlen(c)<6)
*--c='0'; /*Add leading zeros*/
k=atoi(c);
for(i=0;i<10;)
not_used[i++]=1;
for(i=0;i<6 && not_used[j=c[i]-'0'];i++) /* get repeat digit loc. */
not_used[j]=0;
do {
if(i>5) {
i=5; /* all digits different */
not_used[j=c[i]-'0']=1;
}
while(i>=0) {
for(;++j<10;)
if(not_used[j]) {
c[i]='0'+j; /* next highest not used digit */
not_used[j]=0;
break;
}
if(j>9) {
i--; /* no higher digit is free */
not_used[j=c[i]-'0']=1;
continue;
}
else {
for(j=0;j<10&&i<5;j++)
if(not_used[j]) {
c[++i]='0'+j;
not_used[j]=0;
}
break;
}
}
if(i<0)
for(i=0;i<6;) {
c[i]='0'+i;
not_used[i++]=0;
}
for(l=0,j=9,i=1; j>0;j--)
if(not_used[j]) {
l += i*j; /* ascii to int */
i *= 10;
}
i=atoi(c);
j=i-k;
if(j<0)
j+=1E6;
}while(j201345). Store result in p[].
}
r(){
return the next permutation p[]. (e.g. 201345 -> 201346)
}
main(){
Parse the original number into digits and store in array o[].
FOR (g();;r()){
construct n-the smallest number possible from digits not used in p[].
IF (n <= current - start)
print solution
}
}
++ What kind of tricks did R use to minimize code length?
Not too many.
1. pack as many operations in one statement as possible.
2. #define for repeated code
3. Relied on global vars being initialised to zero when first used in
calculation
4. pack for loop statements in head to avoid curly brackets (i.e for
(;;a=3,b=4,s+=a);)
5. using recursive procedures
6. use puts instead of printf where possible
7. no variable type declaration, all vars are int
8. global variables
9. variables reused to serve different purpose, and current value of the
variable in
its new role reused if possible
10. relying on int being size 4 (code is not portable)
11. pointers are the same size as integers
12. incrementing loop in the body where appropriate (i.e. for(;;)
b[n=o[i++]];)
13. some redundant operations are added to the code to be able to reuse
#defines
14. when algorithm was testing for var>=0 it was modified to test for var>0
(e.g. if(m>=0) -> if(m)
++ Here's what I hated (and loved) about this POTM's scoring:
The ratio of source code to execution time doesn't look fair before seeing
other people's entries. Speed and elegance of the algorithm are more
important than the size of the program. I'm not much into cryptic
programming. I believe the reasons for
limiting the source code size is to prevent hardcoding of results, but could
have been achieved in a better way. In the end I had great fun doing what I
don't normally do: making my program unreadable.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Telstra (tele-communications)
Melbourne
Computer Consulting
POTM
Too many to mention
=================================================================
============== 46 ====================== shlem =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
shlem 1879997 829 257 572 90 Leonid Shikhmatov
Sorry ... no description available for shlem
=================================================================
============== 47 ====================== bitdrive =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
bitdrive 1879997 857 476 381 67 Russ Cox
===================
bitdrive was submitted by Russ Cox at rsc@research.att.com
===================
++ Please summarize the algorithm used by bitdrive
Basically, generate a list of all the possible permutations of
the mileage, using a convoluted nested for using #define's.
As you generate the list, generate the smallest trip odometer
mileages and save them. (Its easy - just concatenate the
unused digits).
For each number fed in, binary search for it in the list and
then just search up until you find a mileage such that
( mileage - trip > current mileage ) modulo 1e6.
++ What kind of tricks did bitdrive use to minimize code length?
I had a giant sed script that removed unnecessary white space,
renamed variables using defines, etc. It also removed the error
checking parts of the code that were marked as expendable.
++ Here's what I hated and loved about this POTM's scoring:
We didn't get to see everyone else's scores.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
School. Delbarton School, Morristown NJ.
I enter or help run other programming contests.
Deep down inside, I understand Windows 95 networking completely.
I just can't verbalize it. That's it...
I'd like to see some more interactive programs like CHOMP.
=================================================================
============== 48 ====================== Seed_Racer =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Seed_Racer 1879997 898 297 601 50 =Chad Hurritz
=================
Seed_Racer was submitted by Chad Hurritz at churritz@king.cts.com
=================
++ Please summarize the algorithm used by Seed_Racer
your basic find the next uniquely 6 digited number and print out the results.
I wish i coulda found a monotonic funciton that does it (which i'm sure someone
found.)
++ What kind of tricks did Seed_Racer use to minimize code length?
not many extravigancies like some others have sure to have done. you gotta
pat those ones on the back who get it small AND keep/make it faster.
++ Here's what I hated (and loved) about this POTM's scoring:
Only knowing where you stand doesn't "strive" people to do better since they
don't know how much they need to work in order to move up a step...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
where's RANK? where's RANK? I want to be asked "RANK?"!
company vaxa, location usa, job company, fun mountain, secret yes, potm yay.
=================================================================
============== 49 ====================== cruzin2 =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
cruzin2 1879997 934 687 247 113 Don Shugard
=================
cruzin2 was submitted by Don Shugard at dshugard@lucent.com
=================
++ Please summarize the algorithm used by cruzin2
Used chars to represent the digits of the odometer. Kept a table of
the used digits. Worked the odometer digits from left to right
checking to make sure it was unique. If not took the next available
small number to find the next unique odometer reading. Once I had
a unique number I made the smallest possible number for the trip
indicator if the math was right this was the answer. If not kept on
going... Interesting problems involving 9's and rollovers.
++ What kind of tricks did cruzin2 use to minimize code length?
Substituted single letters for variable names. One big #define that
was used in several places.
++ Here's what I hated (and loved) about this POTM's scoring:
Loved the problem easy to understand and create test cases for.
Using the size of the source code is a horrible metric.
++ COMPANY? Lucent Technologies
LOCATION? Holmdel NJ
JOB? MTS
DO FOR FUN? Fly and Build Model Airplanes
INNERMOST SECRET? Constants aren't, variables won't.
POTM IDEAS? I have shared a few with you previously.
=================================================================
============== 50 ====================== grumble =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
grumble 1879997 938 701 237 14 Robert Bonomi
=================
grumble was submitted by Robert Bonomi at bonomi@delta.ece.nwu.edu
=================
++ Please summarize the algorithm used by grumble
analysis showed that for any 'unique' odometer reading, there
was precisely -one- 'push-the-button' point that gave a "best"
result.
Thus one could 'pre-compute' a table of possibilities.
And do a simple table-lookup to solve any particular case.
(this methodology is optimized for "production" use, solving a
large number of cases -- elementary analysis indicated that
this would be a faster solution on the 1000-value 'final';
although probably *significantly* slower on the 100-number
test set)
++ What kind of tricks did grumble use to minimize code length?
conventional 'bad C coding practices'
short variable names,
no whitespace, except where *absolutely* necessary
multiple statements per line
'type abuse' of passed parameters
overlaying distinct data into different parts of a single array
CSE, into temporaries and/or as pre-processor macroes
Did -not- spend a lot of effort on size reduction, as a little preliminary
calculation/research showed -time- reduction to be _dramatically_ more sig-
nificant to a good score.
++ Here's what I hated (and loved) about this POTM's scoring:
I thought the 'space vs. time' trade-off was a neat idea.
I didn't think the factor was reasonable. life would have been a -lot-
more 'interesting' if the source-size had counted approx 10x higher than
it did. (would have made the space/time balancing question *much* more
difficult to resolve. :)
=================================================================
============== 51 ====================== Mach5 =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Mach5 1879997 942 564 378 101 Carleton Garrison
=================
Mach5 was submitted by Carleton Garrison at cgarriso@dulles.dcn.att.com
=================
++ Please summarize the algorithm used by Mach5
1. Save original odometer reading.
2. Parse odometer reading into 7 individual digits (integers) (7th is used
to denote odometer rollover).
3. Looking at digits from left to right, find the first digit that
duplicates a prior digit.
4. If duplicate found
4a. Add one to digit (nine become zero).
4b. Increment each digit to left as necessary.
4c. Initialize digits to right to be zero.
4d. Set odometer to reflect newly defined digits.
4e. Go to step 3.
5. Construct smallest number using remaining four digits.
6. If the current odometer minus the original odometer is greater than the
four digit "trip" number
6a. Set digit pointer to right most digit.
6b. Go to step 4a.
7. Print results.
++ What kind of tricks did Mach5 use to minimize code length?
Single character variable names.
Remove all unnecessary blankspace.
Multiple instructions per line of code to 80 char limit.
Macro substitution for any code fragment, when beneficial.
++ Here's what I hated (and loved) about this POTM's scoring:
I hate single run scoring - three runs are necessary at mininum. The first
run should be thrown away - the score includes the overhead of loading the
executable into cache which is contrary to the contest premise of program
execution (this is significant on the machines I've worked on). Continue
executions/runs (should require two) until consistent results are observed
eliminating the possiblity that some fluke system lock may have tied up a
resource and skewed the first [second] outcome.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Consultant/Independent C/UNIX/DBA working for AT&T in Northern Virginia.
=================================================================
============== 52 ====================== Underworld =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Underworld 1879997 943 463 480 33 Douglas Zongker
Sorry ... no description available for Underworld
=================================================================
============== 53 ====================== odomagic =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
odomagic 1879997 952 685 267 54 Kevin Ryan
=================
odomagic was submitted by Kevin Ryan at kryan@aoc.nrao.edu
=================
++ Please summarize the algorithm used by odomagic
It read each number in one at a time and parsed the digits starting
from the MSD until a duplicate was found. It bumped the duplicate
digit to the next highest available one (from an array-based digit
pool) and then filled in the rest of the number and tripmeter from
the remaining digits in the pool. This number (which was the lowest
one that contained unique digits) was tested to ensure that it minus
the orginal mileage would be greater than the tripmeter's. If not,
the next higher unique-digit mileage was found and tested until it
statisfied the condition.
++ What kind of tricks did odomagic use to minimize code length?
Obviously not very good ones :) Odomagic used a few while() statements
so a '#define W while' was used to save some chars. Nothing much else
outside of using single char variable names and removing all white space.
++ Here's what I hated (and loved) about this POTM's scoring:
If I must complain, I guess I would say that probably too much weight
went to program size. This is not to say there shouldn't be *some*
size weighting to keep everyone from just using a giant lookup table.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a programmer for the National Radio Astronomy Observatory in Socorro,
New Mexico. Ideas? Has POTM done anything along the lines of finding
prime numbers or PI out to a zillion places in base-3? I'll share my
innermost secret only if the internet promises not to tell anybody.
=================================================================
============== 54 ====================== counterSTEER =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
counterSTEER 1879997 958 377 581 15 Brace Stout
=================
counterSTEER was submitted by Brace Stout at brace@stoutware.com
=================
++ Please summarize the algorithm used by counterSTEER
counterSTEER originally used recursive algorithms for practically
everything, since they typically use less code. I opted for an
iterative algorithm when I saw how much time was being spent in
recursion.
I would imagine I took pretty much the same approach as most people,
filling in an array with digits, using a bit mask to keep track of
which digits were used, checking the resulting values to see if the
reset would need to occur before the initial value, and if so,
incrementing a particular digit and trying again.
I realized late in the game that I could have used an array instead
of a bit mask to save time and code length, but I didn't have time
to pursue it.
I also didn't get around to removing the call to printf, which I'm
sure ate a significant amount of CPU time.
++ What kind of tricks did counterSTEER use to minimize code length?
To minimize code length, I did the standard stuff: one-character variable
names, ternary operators instead of if statements, squeezing as much use
out of the for(;;) loop as I could, using the implicit short-circuit
of the logical && and || operators, using a single macro to declare
parameters and variables for all functions, making maximum use of the
lexical separation caused by the required carriage returns.
++ Here's what I hated (and loved) about this POTM's scoring:
The code-length attribute of the scoring was a killer for me, since it
goes against everything I strive for in my job as a software engineer.
My code was unreadable, unmaintainable, took advantage of little-known
compiler features, didn't use parentheses to make order of evaluation
clear, used implicit type casts between pointers and integers, read
characters into integer storage, etc., etc. Felt like washing my hands
every time I compressed it for entry.
However, I understand the need for the code-length to be factored into
the scoring. With such a straightforward problem, it would have been
easy to decrease execution time at the expense of increased code size.
The extreme example would be a simple array lookup for each of the
possible 1,000,000 odometer values (not that such a large program
would be allowed).
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
StoutWare Software Engineering does software and systems engineering in
the metro Phoenix area. Software is primarily Ada, C++, and 'C' in
embedded and UNIX environments.
My latest hobby is R/C truck building and racing.
I'd like to see A POTM where entrant's programs interact with each other.
I know this has been done in the past, but has not been done recently.
Maybe something similar to RISK? Or populations competing for resources
in a digital world? Another (pretty dry) possibility: I've occasionally
wondered if one could come up with a minimum number of rectangular
operations (set, clear, toggle) to generate a given pattern. I haven't
looked at it, so son't know if it is a trivial problem or not.
=================================================================
============== 55 ====================== blush =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
blush 1879997 967 850 117 71 Hans vanderWal
Sorry ... no description available for blush
=================================================================
============== 56 ====================== ken =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
ken 1879997 973 617 356 59 Ken Thompson
Sorry ... no description available for ken
=================================================================
============== 57 ====================== LongStrangeTrip =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
LongStrangeTrip 1879997 979 474 505 34 Jeff Stone
Sorry ... no description available for LongStrangeTrip
=================================================================
============== 58 ====================== AllClear =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
AllClear 1879997 1016 344 672 2 Byon Garrabrant
Sorry ... no description available for AllClear
=================================================================
============== 59 ====================== jura =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
jura 1879997 1034 637 397 94 George Choolinin
Sorry ... no description available for jura
=================================================================
============== 60 ====================== Beethoven =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Beethoven 1879997 1081 590 491 31 Stu Rowland
=================
Beethoven was submitted by Stu Rowland at swr@mtatm.ho.lucent.com
=================
++ Please summarize the algorithm used by Beethoven
Beethoven used a brute force approach. It started at the current
odometer reading and proceeded to generate the next value that did not
contain duplicate digits. It then generated the trip odometer reading
from the remaining 4 digits using them in increasing order. If the
difference between the generated value and the trip value was less than
the starting value, the process was repeated with the next nonduplicate
value until one was found where the difference was greater than or
equal to the starting value.
In order to avoid testing for the rollover condition, if the starting
value was greater than 987654-0123 = 987531 (the last reset point
before rolling over to 000000), the starting point was set to 0.
A bit mask was used to keep track of the digits used when generating
the nonduplicate values.
++ What kind of tricks did Beethoven use to minimize code length?
The program was first written in an understandable manner. Its length
was then reduced by folding in those subroutines that were called only
once, replacing all variables with single letter identifiers, and
removing all unnecessary white space without exceeding the 80
characters per line restriction.
++ Here's what I hated (and loved) about this POTM's scoring:
Minimizing code size means unreadable code. I suspect that the winner
will actually be one of the larger programs because the final run of
1000 values will overwhelm small differences in code size.
=================================================================
============== 61 ====================== odofuscato =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
odofuscato 1879997 1164 536 628 7 Andreas Eisele
Sorry ... no description available for odofuscato
=================================================================
============== 62 ====================== roll-em =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
roll-em 1879997 1171 517 654 4 Martin Kealey
=================
roll-em was submitted by Martin Kealey at martin@kurahaupo.gen.nz
=================
++ Please summarize the algorithm used by roll-em
Generate-and-test; generate the next permutation after a given
starting point and see if it answers the constraint about when
to hit the reset button.
I think I had my generator running pretty well, but it could have
done with more smarts for choosing starting points, especially
when it's just failed the previous test; just too many iterations
it seems.
++ What kind of tricks did roll-em use to minimize code length?
All normal obfusticated C stuff really:
Inlining function which are only called once (only main() left)
Common subexpression ellimination
Single letter identifiers
Removal of whitespace
Removing (on the POTM master's advice) some #includes
++ Here's what I hated (and loved) about this POTM's scoring:
Hated: nothing
Disliked: I didn't win :-)
I suggest that any POTM where code space counts towards the
result should count tokens, so that long identifiers,
whitespace and comments wouldn't penalize an entry -- so you
wouldn't need a separate version "for show". If you like I
have a program that will do this for C & C++ programs.
Liked:
I didn't have to spend ages working on my entry, and this time
I didn't get the booby prize for the last submission.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company:
Nobody wants my company, that's why I'm all alone at my keyboard.
Actually, I'm self-employed, and people never leave me alone to
get on with things.
Location: 36.88888=B0S, 174.72116=B0E.
=================================================================
============== 63 ====================== dawn =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
dawn 1879997 1208 643 565 127 Kim-hang Chung
=================
dawn was submitted by Kim-hang Chung at khchung@cs.ust.hk
=================
++ Please summarize the algorithm used by dawn
Pseudo code below:
Let M = odometer that records the miles travelled by the car
since it was born
N = trip odometer that measures the miles travelled by
the car since it was last reset
Input: M
Find the smallest number T such that the 6 digits of (M+T)
are all different.
Determine N' which is the smallest number formed by the rest
4 digits.
While (T < N') Do
Find the next smallest T such that the 6 digits of
(M+T) are all different
Determine N' which is the smallest number formed by the
rest 4 digits.
End While
Print (M+T-N') and (M+T)
++ What kind of tricks did dawn use to minimize code length?
Change some of the "if" statements to triary operations.
Store large constants (e.g. 1000000) in variables.
++ Here's what I hated (and loved) about this POTM's scoring:
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Hong Kong University of Science and Technology. Hong Kong.
WWW : http://www.cs.ust.hk/~khchung/
Computer Science Department, HKUST, Hong Kong
=================================================================
============== 64 ====================== Odie_the_wonder_button =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Odie_the_wonder_button 1879997 1256 794 462 80 Glenn Larratt
=====================
Odie_the_wonder_button submitted by Glenn Larratt at glratt@rice.edu
=====================
++ Please summarize the algorithm used by Odie_the_wonder_button
Traverse the given odometer reading left to right, checking off each digit
in a table as it's used, incrementing where necessary, backing up to the
right on rollover. Once this process is complete, you have an odometer
reading with 6 unique digits: create the smallest number consisting of the
unused four digits, and determine if that number is smaller than the number
of miles travelled. If so, you're done; if not, advance to the next unique
six-digit reading and try again.
++ What kind of tricks did Odie_the_wonder_button use to minimize code length?
#define'd a macro or two
typedef unsigned u; for the number of times I needed to declare u's
stuck to primitive manipulations (no mult/div) for speed
did the arithmetic in bcd, so used "%x" for i/o
++ Here's what I hated (and loved) about this POTM's scoring:
Liked that getting a solution was fairly easy to do, so lots of competition
for efficient code.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Rice University
Houston, TX USA
"LAN Specialist"
Dance, sing, eat
...is my outermost joy: my wife Elizabeth
traffic modelling? something with a potentially real application...or
alternatively, something absurdly whimsical (cf. Lemmings)
=================================================================
============== 65 ====================== Excuse_Me! =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Excuse_Me! 1879997 1281 1019 262 78 Krishna Tripathi
===============
Excuse_Me! was submitted by Krishna Tripathi at kct@hotmail.com
===============
++ The algorithm used by Excuse_Me!
1. Read the Numer ( Reading of Meter A )
** say 037368 ( = I )
2. Add the smallest four digit number possible to make by excluding
two most significant digits.
** 037368 + 1245 = 038613
3. Store the digits in an array of integers starting from left , till any
repeated digit is found.
** |0|3|8|6|1|*|*|*|*|*|
4. Fill this array by the remaining digits in increasing order.
** |0|3|8|6|1|2|4|5|7|9|
5. Now the first six will be the reading of meter A and last four will be
reading of meter B when it is possible to have an event of our desire.
** meter A |0|3|8|6|1|2|
meter B |4|5|7|9|
6 If A-I is less than B then do the following till A-I becomes either
greater or equal to B,
1. take the sixth (say CurrentLocation) element in the array ( =2)
2. swap it with the digit which is smallest of the digits that are
# in the right side of this digit ( from location 7 to 10 )
# and larger than this digit ( =2), 4 in this case.
** meter A |0|3|8|6|1|4|
meter B |2|5|7|9|
3. If none of the digits satisfy these conditions then decrease
CurrentLocation (make fifth) and do the same.
as it can happen in this case :
meter A |0|3|8|6|1|9|
meter B |2|4|5|7|
||
\/ *
meter A |0|3|8|6|2|9|
meter B |1|4|5|7|
4. After swapping sort the section of the array that is right of
the CurrentLocation.
meter A |0|3|8|6|2|1|
meter B |4|5|7|9|
++ What kind of tricks did Excuse_Me! use to minimize code length?
No special trcicks than to keep variable names of one character and
declaring global variables so that they can be used by all functions and
need not be passed.
++ Here's what I hated (and loved) about this POTM's scoring:
* You enjoy too much of power . The system system should be more
democratic . We shold have full right to know the strength and weakness of
the people with whome we are competing( I mean strength and weakness of
their programms ). But I enjoyed the frustration arising out of putting my
all efforts but program not moving upward , as if gravity has increased !
( don't you think enjoying frustration is a weird thing !, a new
philosophy in itself ! )
++ COMPANY? Tata Unisys Ltd.
LOCATION? Bombay.
JOB? Analyst/Programmer/Peon/Manager as the need arises.
DO FOR FUN? Travel and sleep during travel.
INNERMOST SECRET? Let it remain innermost.
POTM IDEAS? I won't give beacuse I want to participate.
=================================================================
============== 66 ====================== tono =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
tono 1879997 1302 307 995 9 Antonio Esguevillas
Sorry ... no description available for tono
=================================================================
============== 67 ====================== delphi.guys =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
delphi.guys 1879997 1307 750 557 122 K.Symeonidis J.Tsoukalidis
=================
delphi.guys was submitted by K.Symeonidis and J.Tsoukalidis at
ksymeon@hypernet.hyper.gr
=================
++ Please summarize the algorithm used by delphi.guys
The algorithm delphi.guys used is rather simple. It passed through thorough
examination and is like this :
1- at first we take the odometer mileage. (START)
2- Then we try to find the first mileage that has all the six digits
different. (CURRENT)
3- The remaining four digits form a number. (REMAIN)
(note that the order we get the digits from the smallest to the largest, thus
producing numbers like 2456 etc)
4- if the CURRENT-START >= REMAIN then we can produce this situation by pressing
the reset button at CURRENT-REMAIN mileage
else
we goto step 2, where another mileage with 6 different digits will be
computed.
Explanation of STEP 2. How to find a six-diff-digit mileage.
We have a number, we break it into 6 digits like : 355344
we try to find if digit M is same with digit L (M 356000 (because digit 2= digit 3)
Iteration 2=> 356010
Iteration 3=> 356011
Iteration 4=> 356012 which is the first mileage after 355344 with six
different digits.
Explanation of STEP 3.
For the example above we get the REMAIN = 4789.
Of course 356012-355344 < 4789, so we can't possibly form the 4789 in the
small odometer, and we go to STEP 2 again.
we find 356014 and 2789 still not good, then
we find 356017 and 2489 still not good, then
........
++ What kind of tricks did delphi.guys use to minimize code length?
We didn't do any special tricks, other than using small variable names,
using less variables, less functions and combining assignments and
conditionals in the same sentence like :
if (d >= (f=a+b+c+d))
We find ourselves puzzled though with the problem to produce faster code. We
constantly changed a bit of our code, and went out to OS, and timed the
program (with a special "home-made" millisecond resolution timer).
We started at 13000 ms (or 13seconds), went lower to 7000ms, to 1000ms, to
510ms for 1000 numbers in our machine of course.
++ Here's what I hated (and loved) about this POTM's scoring:
What I loved? The continuous quest for faster code. I have written a
decreasing list with my millisecond
scores :-) Wanna see it? :
13271
12567
7902
7710
7478
7397
7396 -> our first entry went to position 94.
5312 (major breakthrough :-))
5237
1428 (something good in mind!)
1087 (no we get closer to 1000ms for 1000 numbers, yeah!)
1084 -> our second entry, went to position 84. Why? :-(
1067
1057
1016
1014 (Is this getting somewhere? :-)
995 --------------!!!!! BROKE THE 1000ms barrier!! Great hopes arise!
577 (Am I blind, I didn't see that thing?)
544
540
527
515
512
511
510.69milliseconds (LAST ENTRY. Haven't got any results yet!)
Awaiting for the jury's decision!!! :-)
What I hated? That I had to minimize code length with small variables,
unstructured code, and that when
I finished a version of the program, I had to concatenate lines and delete
indentation spaces to produce a smaller source file.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
NAME: Kostas Symeonidis, 27
COMPANY: ArtLogic
LOCATION: Thessaloniki, GREECE
JOB: Computer Programmer, Teacher in Informatics
HOBBIES: Ski, Inline Skates, Swimming, Sports of all kind generally... :-)
This was my first POTM, I'm a rookie. I wrote this program with my student
and friend, John Tsoukalidis, who I train for the national informatics
contest. I usually search the Internet to find computer exercises and
often I give him some problems to solve. So some day we started working
on this POTM in Delphi. We discussed it, solve it, and then the idea to
compete came, so I translated it to C++. (Of course I had to explain C
to John, 'cause we use Pascal for the moment. No problem. He's so smart,
he learned the basics in 5 minutes). When we found our program a bit slow,
we started thinking about how to make it faster. It was a great exercise,
I can tell. Thanks POTM Master!
=================================================================
============== 68 ====================== hope.it.works =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
hope.it.works 1879997 1328 703 625 51 John_Zer0 InfraRED
=================
hope.it.works was submitted by John Zer0 and InfraRED at john@graphisoft.hu
=================
++ Please summarize the algorithm used by hope.it.works
The algorithm increases the counter, and then tries to get the start mileage
setting, a kind of reverse-thinking.
++ What kind of tricks did hope.it.works use to minimize code length?
Everithing we could think of.
First of all, all variables are 1 char long (like 'a' to 'z'). Some #defines
used also, we even defined 'a[i' (to char z), so 'a[i]+=b' looks like
'z]+=b;' after the conversion. Very funny ;)
Note that k(;;) (k defined as 'for') is 3 chars shorter than while(1) !
++ Here's what I hated (and loved) about this POTM's scoring:
I think it was pretty interesting. Though we didn't know how much time the
program takes to load/initialise on your computer (this info could've be
used on the 100 items -> 1000 items time estimation).
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
University, Technical. Pretty cool, but only 1/2 month util the exams! ;)
Borland C++ was used to write the code, in ANSI mode...
Oh, and concernig the timings, it seems as our lame PC (AMD PR100) was much
faster than your Sun. But I really don't believe this...
=================================================================
============== 69 ====================== aleph =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
aleph 1879997 1353 919 434 130 Arie Tzvieli
=================
aleph was submitted by Arie Tzvieli at atzvieli@lehman.com
=================
++ Please summarize the algorithm used by aleph
PHASE 1 - PREPARE
1. Generate in ascending lexicographic order all 6 digits numbers having
all digits different
2. For each number, check if it is eligible
(if X denotes the numbers generated in Step 1, and Y are the corresponding
MINIMAL 4 digits number such that XY has 10 different digits, and
Z={x-y|x in X, y in Y, and y corresponds to x} then a is ELIGIBLE if there
exists a number d for which z,a is the BEST solution.
This is easy to implement by comparing the z value corresponding to the
current x number with the z value of the last eligible number - the
new z value has to be the greater of the two.
Retain all eligible numbers in an array.
PHASE 2 - SOLVE
3. For each given number find the best solution in the array generated in
Step 2 using binary search. The solution is the first number in the
array greater or equal to the given number.
++ What kind of tricks did aleph use to minimize code length?
One character names for all variable, #define C continue, squeeze multiple
instructions into one row
++ Here's what I hated (and loved) about this POTM's scoring:
I liked the minumum mile criteria.
I hated the length criterion, encouraging me to write ineligible code
that was hard to debug.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
COMPANY - ProLogica Inc.
Job: Consulting at Lehman Brothers.
Do for fun: meditation.
=================================================================
============== 70 ====================== another =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
another 1879997 1422 609 813 24 Mark Huizer
=================
another was submitted by Mark Huizer at xaa@xaa.stack.urc.tue.nl
=================
++ Please summarize the algorithm used by another
Hmm...
* find the first permutation below the start number
* while not possible
- see if next permutation is possible from start point
++ What kind of tricks did another use to minimize code length?
Ha ha!
* beer, much beer!
* funny modes
* an evening with my neighbor behind a computer
* 3 hours of laughing for every 10 bytes gain on the code
++ Here's what I hated (and loved) about this POTM's scoring:
hated: finally writing down some permutation creating code
loved: finally writing down some permutation creating code
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
fun, fun, fun
=================================================================
============== 71 ====================== matzke =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
matzke 1879997 1473 641 832 104 Robb Matzke
=================
matzke was submitted by Robb Matzke at matzke@llnl.gov
=================
++ Please summarize the algorithm used by matzke
1: Based on the current odometer reading, choose the next larger
odometer value with unique digits, mod 1000000
2: Choose the smallest possible trip meter value from the remaining
four digits.
3: If odometer-trip (mod 1000000) is smaller than the initial odometer
reading then go back to step 1. It typically takes about 80
iterations to find a solution.
The smallest possible final trip meter reading is `0123', so we can
travel 123 miles before we even start considering solutions.
The function to return the next larger number with N unique digits
worked from left to right always choosing the smallest available digit
not smaller than the digit currently at that position (modulus
10). When a digit changed then all remaining digits were reset to zero
before the process continued. When the digit wrapped from 9 to 0 then
the left digits were increased by one (the carry from 9 to 0) and new
left digits were generated recursively before continuing.
++ What kind of tricks did matzke use to minimize code length?
One-letter variable names, no indentation, about 80 characters per
line, spaces only where necessary. I also did `#define int I'.
++ Here's what I hated (and loved) about this POTM's scoring:
I found out about the POTM contest two days before I left for
Thanksgiving vacation so it was nice being able to see within 24 hours
that my program compiled and ran correctly. However, since I only had
one evening to program, it would have been nice to see the execution
time and length of other entries to have a goal to shoot for and to
help decide what speed/size tradeoffs to make.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a computer scientist for the Scientific Computing Applications
Division of Lawrence Livermore National Laboratory in Livermore, CA.
I work on various physics support codes including the publicly
released MeshTV used for viewing scientific mesh data.
For fun I bicycle (road), hike, watch birds and take pictures.
=================================================================
============== 72 ====================== road_warrior =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
road_warrior 1879997 1503 888 615 42 Jim Curran
Sorry ... no description available for road_warrior
=================================================================
============== 73 ====================== Kicks_On_66 =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
Kicks_On_66 1879997 1530 882 648 18 Scott Everett
=================
Kicks_On_66 was submitted by Scott Everett at severett@gvmail.ih.lucent.com
=================
++ Please summarize the algorithm used by Kicks_On_66
1. If the starting mileage of odometer A was higher than 987654 or lower
than 12345 then I automatically rolled it up to 12345. That is because
there are no unique answers in that range for the A odometer, so there
could be no unique answer overall.
2. B can not be unique for at least 123 miles, since 0123 is the lowest
unique value. Therefore, odometer A is always advanced by at least this
much at the start to save checking those first combinations.
3. Once the initial value of A had been modified by the first two steps
above, I advanced the A odometer until all 6 digits were unique. This was
not done by adding one to the mileage and re-checking, instead I looked for
the first decimal location that duplicated an earlier digit and then I
advanced that digit by one. The digits after that were then selected to be the
lowest value for each digit that was unused from the digits already in use for
the A odometer.
4. Finally, I selected potential odometer B values by using an array of 10
digits and marking off those that were used for the mileage on A. I then
created a value for B by choosing those digits that were unused in A and
arranging them lowest to highest.
5. It was essential to account for wrap-around of both the A and B odometers,
but because of the method I used to generate B values I was able to ignore
that case.
++ What kind of tricks did Kicks_On_66 use to minimize code length?
Used single character variables, stripped out all comments, and put
multiple statements on a single line (up to 80 char max) to minimize the
number of carriage returns. Also, stripped out all unnecessary spaces.
++ Here's what I hated (and loved) about this POTM's scoring:
I did not like having to strip out the comments and use single character
variables to minimize the size of my entry. This meant each time I sent
in a new entry I had to strip it down. I would prefer that the object
size be used instead of the raw size of the file, it saves time and energy.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lucent Technologies in Lisle, IL. I am a 5ESS Product Manager.
=================================================================
============== 74 ====================== ugly =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
ugly 1879997 1549 1141 408 103 Paul Nelson
Sorry ... no description available for ugly
=================================================================
============== 75 ====================== razorback =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
razorback 1879997 1670 591 1079 22 Mike Wilder
Sorry ... no description available for razorback
=================================================================
============== 76 ====================== watsoncolin =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
watsoncolin 1879997 1698 1005 693 106 Colin Watson
Sorry ... no description available for watsoncolin
=================================================================
============== 77 ====================== slow_but_long =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
slow_but_long 1879997 1865 336 1529 40 Steven vanEnk
=================
slow_but_long was submitted by Steven vanEnk at vanenk@mpq.mpg.de
=================
++ Please summarize the algorithm used by slow_but_long
Add 123, find next smallest 6-digit number A with different digits,
construct smallest 4-digit number of remaining digits, and check if
this is solution: if not add 1 to A, and repeat.
++ What kind of tricks did slow_but_long use to minimize code length?
Not many, after submission of my first try I had no time to
improve....
++ Here's what I hated (and loved) about this POTM's scoring:
It's nice to have an easy problem, except that since it's easy for
everyone, it's difficult to win
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
University of Innsbruck, Austria, physicist.
Participated to learn C. This could be a joke.
=================================================================
============== 78 ====================== yuguang =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
yuguang 1879997 1989 1505 484 39 Yuguang Wu
Sorry ... no description available for yuguang
=================================================================
============== 79 ====================== DashBored-Lite =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
DashBored-Lite 1879997 2198 728 1470 85 John McMillan
=================
DashBored-Lite was submitted by John McMillan at jcm@pegasus.att.com
=================
++ Please summarize the algorithm used by DashBored-Lite
Algorithm? Watts an Algorithm?
First hack just searched for the next "digit-unique" ODOMETER
(6 digit) number at least 123 miles (minimum trip-meter amount)
beyond the start-odometer setting. Once that 6-digit number
was chosen, the minimum trip-meter setting was obvious and was
tested for feasibility. (A trivial incrementation scheme was
used any time a digit was found to duplicate an earlier (higher)
digit.
Further hacks used various algorithm speedups, such as tables of
masks rather than bit-shifts. Alas, the TIMEX variability
of all these speed-ups was so great on my home system that I
couldn't identify which changes reduced times, so why bother
Fred with'em?! %^)
++ What kind of tricks did DashBored-Lite use to minimize code length?
'Just wrote bad code -- shades of the original BASIC compilers using
single letter names! If it boils down to a byte war, I lose as
I failed to "#define R register". %^)
++ Here's what I hated (and loved) about this POTM's scoring:
How could one hate anything Fred thought up? (Are there extra
Brownie points?)
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Actually, on-the-beach (by own choice) these days. Hmmm... should
face "reality" (yuck) and interview, shouldn't I?
=================================================================
============== 80 ====================== odoracle =============
=================================================================
ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS
odoracle 1879997 2233 1184 1049 92 Ljupco Taseski
=================
odoracle was submitted by Ljupco Taseski at cu151@fim.uni-erlangen.de
=================
++ Please summarize the algorithm used by odoracle
Odoracle algorithm is really simple. The first step is to build list of
all numbers between 0 and 999999 with all different digits. Then for every
input line the program tries to find the smallest possible entry from the
lookup list.
++ What kind of tricks did odoracle use to minimize code length?
Mainly C shortcuts, one-letter variables and minimum blanks. In C is possible
to write quite condensed statements. It's really amazing how many
(unnecessary) spaces are there :))
++ Here's what I hated (and loved) about this POTM's scoring:
I cant's say I hated, but rather I didn't like the rule about code length.
If you plan some other POTMs with the same rule, please tell us now - to start
writing some script for "code compacting".
Paradoxically, one of the things I liked was the same rule about code length.
It reminded me of the past days and my (at the time) new HP41CV. It has a
little more than 2KB memory, and every program was tightened to the maximum.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm starting (with two partners) a new company.
Fun? Everything which is not part of the job. Even programming, like POTM :)
Secrets are mine and only mine :)
Ljupco Taseski Trilus d.o.o., Ljubljana SI-1000, Slovenija
=================================================================