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).
They are provided in order of SPEED (more or less).
There are also other files available on request via email or uuto:
1. A cpio containing primeval.c, wookin_po_nubbas.c, and pringle.c
(these were the three fastest - their authors have been
kind enough to extensively comment their code for us all!)
2. A cpio with 160 squares I considered for the finals
3. The derivation of the digit rules for 7, 11, 13 (in MATH stuff)
4. Other entries are available, but I have not asked them to be
commented - some are/some are not - please request by name
(I won't just "ship them all"!)
This, together with the consolation prize mail, will be the last you hear
of prime numbers ... hope it was fun (complaints >/dev/null)! I'm off to
think up the NEXT one, coming within a few weeks with luck!
=Fred
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
======================================= primeval =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primeval 410 90 90 70 80 80
=================
primeval was submitted by Allan Wilks at allan@research.att.com
=================
HOW DID primeval CHOOSE CANDIDATES FROM THE SQUARE ?
o breadth-first search
o use bit-vectors to keep track of neighbors
o watch out for grids that are almost trivial (and hence deadly)
HOW DID primeval TEST A CANDIDATE FOR PRIMALITY ?
o trial division by small primes (40 of them)
o Miller tests to the bases 2 and 3
ANY OTHER COMMENTS, TRICKS, WHATEVER?
o many thanks to Jim Roche for a great collaboration on primality
testing
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
o statsitics research; specialty is statistical computing
ANY IDEAS FOR THE NEXT POTM?
o POTM should be short; about 2 or 3 weeks max I would say;
otherwise lots of time gets wasted and a lot of that is spent
pursuing tiny optimizations; also, in the real world no one
ever gets three months to work on such a well-defined, small
problem
=================================================================
======================================= =wookin_po_nubbas =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=wookin_po_nubbas 430 90 80 80 80 100
=================
wookin_po_nubbas was submitted by Jim Roche at roche@ccr-p.ida.org
=================
HOW DID wookin_po_nubbas CHOOSE CANDIDATES FROM THE SQUARE ?
Gradually built up each candidate from the highest order digit to
the lowest, searching first
over 9-digit numbers, then over 8-digit numbers, etc., all in
descending order. The most important thing to notice (as most people
probably did) is that in order to decide where to go to pick up the next
digit, you need only keep track of your current _state_, which consists
solely of the location of the last digit chosen. (If returns to the
same grid location had been disallowed, this trick would not have
worked, and the problem would probably have been much harder, at least
for the nastiest grids.)
In fact, in order to prevent an exponential explosion in the number
of paths searched for grids with lots of repeated digits, the thing to
do is to keep track of the SET of all grid locations that you can
occupy and have whatever part of the candidate you've constructed so far.
Thus we actually let our state consist of the part of the number we've
constructed so far, together with the set of all grid locations that
we could occupy at the moment (given the sequence of digits so far).
This state is also easy to update quickly, especially if one uses
bit maps. Thus we can search many paths simultaneously, and the total
time depends only on the number of candidates that we have to test for
primality (and upon the difficulty of testing them, of course). The
search phase takes very little time for most grids.
However, some grids have special properties modulo 2,3, and/or 5.
These grids can require tens of thousands of primality tests for the
unwary contestant, so we give the search routine enough intelligence
to recognize when it can lop of huge portions of the search tree
(before building up complete 9-digit numbers). It's also helpful
to use some simple tricks so that we never have to do a general
divisibility test on any number that's a multiple of 2,3, or 5.
HOW DID wookin_po_nubbas TEST A CANDIDATE FOR PRIMALITY ?
This is where the fun really begins. Allan Wilks and I worked
together on this aspect (but not on the search) and used every trick in
the book to speed things up. The basic idea was to quickly build
a small table containing the first 40 or 50 primes (up to
about 200) at the beginning of
the program, then use this table to do trial division of candidates.
Candidates that survived were subjected to a modified Miller test,
which is based on Fermat's Little Theorem. We found that because of
constraints imposed by the grid, many numbers would never be tested
for primality, because if one of these numbers appeared in the grid,
necessarily some larger prime (which we would have already found) would
also be in the grid. As a simple example, we would never have to test
17 for primality, because we would have already found the prime 71.
As a result, we found that the number of basic pseudoprime tests
we had to do could be reduced from 4 (as in the ordinary Miller test
for primality of numbers less than 10^9) to 2, because most of
the pseudoprimes would never be handed to our primality test in the
first place.
We wound up doing both the trial division and the Miller
tests using a combination of integer and floating point arithmetic.
These routines are probably the most cryptic, but perhaps the most
interesting, parts of the program (at least of _my_ program).
ANY OTHER COMMENTS, TRICKS, WHATEVER?
It's scary how much time has gone into this contest. As Fred
warned me after a previous contest, there's a real danger of winding up in
the Betty Ford Clinic after participating in a POTM.
The program name "wookin_po_nubbas" is a take-off on the song
"Wookin' po Nub," which was comedian Eddie Murphy's version of the
country-western song "Lookin' for Love (in all the wrong places)."
Murphy used to put on a huge unruly wig and speak
very indistinctly, pretending to be the character Buckwheat from the
Little Rascals. He made one phony commercial (much like the real
commercials that one sometimes sees on late-night TV) advertising a
record of Buckwheat's Greatest Hits, in which his Buckwheat character
was shown singing snippets of dozens of popular songs as the
phonetically spelled titles (e.g., "Wookin' po Nub") scrolled down the
screen.
My program name is admittedly a pretty bad (and obscure) pun, but
with the above paragraph as background, I imagine that it will be
easy enough to decipher. Maybe I should have chosen
"the_indivisible_man" as a program name instead.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Used to be a postdoc at Bell Labs in Murray Hill, which is where I
did my first POTM. Now I'm working at the Center or Communications
Research in Princeton.
Like to play volleyball, softball, and touch football (though
not simultaneously), juggle, read, sing, and do recreational math.
ANY IDEAS FOR THE NEXT POTM?
Probably only allow a month or so instead of three months. This
should allow enough time for people to write pretty good programs
without going off the deep end.
=================================================================
======================================= =pringle =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=pringle 370 70 90 70 60 80
=================
pringle was submitted by Palith Balakrishnabati at pb@toucan.att.com
=================
HOW DID pringle CHOOSE CANDIDATES FROM THE SQUARE ?
1) Search control via (nondeterministic) FSM simulation: build a
FSM that accepts strings of digits in the grid. Each state of
the FSM corresponds to one of the 25 grid positions; a set of
states can be stored in a 32-bit machine word. Thus, pringle
never has to muck around in the actual grid itself once the
FSM is built. (FSM==Finite State Machine)
HOW DID pringle TEST A CANDIDATE FOR PRIMALITY ?
2) Prime testing via:
a) checks for trivial factors (2,3,5) "built into" FSM traversal
b) checks for "small" factors (primes < 200) accomplished
in batches via GCD
c) checks for large factors by Miller-Rabin strong-psuedo prime
testing to bases 2, 3, and 7
3) Loop unrolling and other garden-variety eficiency hacks.
SIMPLIFIED SEARCH CONTROL OUTLINE:
==========================================================
read grid and build FSM /* map[i] = set of grid positions
containing the digit i *
for (n = 9; n > 0; --n) {
search (fullboard, 0, n) /* search for an n-digit prime in the grid * /
if found print and halt
}
search (states, number, depth) {
if (depth == 0) {
test number for primality; if prime, we're done
return
}
neighbors = bits adjacent to 1-bits in states /* easily found by
a little SHIFTing and ORing * /
for (i = 9; i >= 0; --i) {
newstates = neighbors & map[i];
if (newstates)
search (newstates, number * 10 + i, depth - 1)
}
==========================================================
This reduces search contol to a small percentage of the overall time.
Repeated paths in the grid that form the same number do not slow down
the search at all, and I visit candidate primes in strictly decreasing
orders, so I can stop when I find the first one.
PRIME TESTING
The search control is just a small fraction of the time, so I worked
at making the prime testing efficient.
I build an array mask[n][k] which gives the set of squares from which
there is an n-step path through the grid ending in a 1, 3, 7, or 9, with
residue -k mod 3. By keeping track of number mod 3 as I go and ANDing
in with the mask[][] values, I am assured that I am always going
to find at least one number not divisible by 2, 3, or 5 in the current
branch of the search tree, and that I never end up at number divisible
by 2, 3, or 5. This helps in tricky squares such as the "all 1, 4, 7".
To test for divisiblity by 5 > p > 200, I compute GCDs. On a SPARC,
where integer division is slow as dogmeat, a well-coded GCD (using, say,
the binary algorithm) is about as fast as one divide. But in a single
GCD, we can test for divisibility by many primes at once:
GCD (n, 7 * 11 * 13 * 17 * 23 * 29)
for example, will be 1 unless n is divisible by one of these primes.
By multiplying sets of primes less than 200, I can "pack" a set of test
integers and do a bunch of divisibility tests with a single GCD. The
value 200 was detemined empirically as a point where returns diminished.
This table of packed prime products is computed just once before the
search begins.
For large divisors, I use the probablistic strong pseudo-prime test.
Using bases 2, 3, and 7, there is only one SPP less than a billion, and
it cannot be the largest prime in the grid: this is because any grid
containing this number also contains a larger prime. For example,
the number 789201803 can never be the largest prime in the grid, because
any grid containing that number also contains the prime 989898989.
Almost all of the work is in multiplying x * y mod m. I use a simple
by-hand bit-at-a-time multiplication algorithm, with a fully unrolled
loop and a few tricks to make it efficient on a SPARC (e.g. testing
(x&512) is much cheaper than testing (x&1024).
That's about it. There's special-case code to take care of the "funny"
grids where all the digits have a common prime divisor. Unfortunately,
the version of pringle I submitted got the wrong answer on the test
"HOT DOG" because I bungled the code to make sure that I start from
only nonzero digits. Rats. This version has that bug fixed.
=================================================================
======================================= fermata =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
fermata 540 60 80 90 60 250
=================
fermata was submitted by Doug McIlroy at doug@research.att.com
=================
HOW DID fermata CHOOSE CANDIDATES FROM THE SQUARE ?
Paths of length 9 are enumerated recursively in lexicographically
decreasing order, then paths of length 8, and so on. No attempt is
made to learn anything about shorter paths during the search for
longer ones: that was deemed difficult and wasteful.
The input to each level of the recursion is a list of all prefixes
of a given length and value. Prefixes of the next longer length
are considered in decreasing order of their last digit. Prefixes of
equal value ending at the same cell are identified, so there cannot
be more than 25 prefixes alive at any stage of the recursion.
Preprocessing tricks allow paths to be pruned early:
(1) Since multidigit primes can't end in any of 0,2,4,5,6,8,
no cell needs to be considered from which one of 1,3,7,9
cannot be reached in the right number of steps. A simple
dynamic program is run initially to determine for every cell
which suffix lengths are possible. Paths are pruned according
to that criterion.
(2) Nine-digit numbers are divisible by 3 if every digit has
the same value mod 3. More generally a path can be pruned if
every valid suffix has the same value mod 3 and the prefix
has the complementary value mod 3. A simple dynamic program
determines what path lengths from each cell have single
values mod 3 and what those values are. In the most dramatic
instance that I have seen this reduces the number of candidates
from 13125 to 3.
If the gcd of all entries is not 1, then the problem has
a 1-digit answer, which condition is checked early.
HOW DID fermata TEST A CANDIDATE FOR PRIMALITY ?
First the candidate is tested for divisibility by 3,7,11
by looking up the value mod 3*7*11 in a precomputed characterisitic
table of multiples of 3,7,11. A division has to be done only
for the first of successive candidates that fall in
the same 3*7*11 range.
If a number survives this simple test,
Fermat's test (if p is prime, then a^(p-1) mod p = 1) is used
to cast out composite numbers. For a, I use 2, because the
high digits of the first few powers of 2 are 0, which speeds
the multiprecise calculation described in the next section.
Since the only square eoots of 1 mod p are 1 and p-1, we can first
cast out powers of 2 from p-1, sacrificing a tiny bit of discriminating
power for speed. Raising to the p'th power is done by the usual
log p algorithm. If a number is not identified as composite,
it could be a pseudoprime mod p, i.e. a composite that passes.
Try again using a different a; four random, pairwise relatively
prime, a's are deemed to give strong enough confidence. In fact no
pseudoprime candidates have arisen in any system test.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Quotients and remainders are computed in 53-bit floating point,
which is adequate to handle products of 30 bits (9 digits) times
15 bits, but not 30 bits times 30 bits. One operand of multiplications
is thus kept in two 15-bit parts. Even fixed-point mod is
calculated in floating point, because the sparc doesn't have
a machine divide. Fortunately we never have to find a more than
30-bit integer part of a floating-point number; conversion
to int and back is vastly faster than the floor() function.
To speed navigation, with each cell is kept lists of neighbor
cells classified by value. In one version of the program, "neighbor"
was taken to mean a canonical representative of the
neighbor cell's equivalence class under the symmetry of the pattern.
In the best case this can reduce the number of live prefixes
from 25 to 6. Nevertheless I decided to omit this feature
because the symmetry-preprocessing code was big (a 1/3 increase
in source) and hard to test thoroughly. Even the best-case
speedup was modest because the major time-eater -- prime testing --
was unaffected. If The contest features a lot of symmetric
problems and I lose by a few percent I'll be sorry.
The trick I didn't find was how to overcome the enormous
startup cost (about 70 ms) that Solaris apparently imposes on top
of the few milliseconds that my program actually takes on most
problems. Whoever knows such a trick will get the prize.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
1. I program interesting things. 2. I program interesting
things. (My interestingly programmed Christmas card is
available on request.) 3. I love to program interesting things.
ANY IDEAS FOR THE NEXT POTM?
crossword puzzles? in particular, word squares are a
nice challenge. various flavors: how quickly can you find
a square that can be made with a given vocabulary?
how many squares can you find in a given time?
perhaps with scrabble scoring. perhaps with holes,
prizes for minimizing the number of holes, or maximizing
lexicgraphically the list of distinct numbers of words
of each length.
=================================================================
======================================= totient =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
totient 550 100 140 90 110 110
=================
totient was submitted by Bob Hall at hall@research.att.com
=================
HOW DID totient CHOOSE CANDIDATES FROM THE SQUARE ?
It first exhaustively computed the set of all length 5 (or less) numbers
present in the square. It then iterated through them (greatest to least),
and for each, iterated through all those length-5 guys whose first digit
is the same as the last digit of the outer guy. For each of these,
it "pasted" them together, checked for primality and then finally
checked to see if the pasted number was actually in the grid.
Of course, for the inner iterations, we skip all 5-digit guys ending
in 0, 2, 4, 5, 6, 8, because these can't result in pasted primes.
HOW DID totient TEST A CANDIDATE FOR PRIMALITY ?
To test n for primality, it first divides it by all primes less than
257 (which it generates initially using the Sieve of Eratosthenes).
Since most ns are in the 9 digit range, we need to do more than this.
For all numbers surviving that test, totient then tested n for primality
by computing w=(2^(n-1) modulo n). If that is not 1, then n is not prime.
When a number passed that test (i.e. produced w=1), it computed
v=(3234^(n-1) modulo n). If v=1, then my program concluded that
n is prime. (This is a variantion on the Miller-Rabin primality test
(cf the writeup I submitted separately). You can also look it up in
the Cormen/Rivest/Leiserson algorithms book.) Note that in general, this
does not guarantee that n is prime, just pretty likely. In fact, I have
run some exhaustive searches to show that this is good enough (i.e. it
is a guarantee) for all cases that come up in this contest.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Of course, totient special-cases the grids having 2,3,5,7,or 11 as
their answer. I really wanted to special case the 9-8 and 9-7 grids
as well, but Fred disallowed that.
I also figured out a really fast way to test whether a number is divisible
by 7. It is way cool, running on the order of log log 2^32 ~ 5 operations,
compared to log 2^32 ~ 32 operations for actual division.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Software agent research (more generally, software engineering and
artificial intelligence research).
Innermost secret (shhh): AI is dead, long live software agents!
ANY IDEAS FOR THE NEXT POTM?
How about symbolic algebra? Solving for x, doing integrals, finding
closed forms for recurrences, roots of polynomials, stuff like that.
=================================================================
======================================= primetime =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primetime 560 80 130 90 110 150
=================
primetime was submitted by David Korn at dgk@research.att.com
=================
HOW DID primetime CHOOSE CANDIDATES FROM THE SQUARE ?
I did a depth first search to compute all 4-digit prefixes.
I kept track of paths that I had already computed and pruned.
I saved a bit map of for each four digit number indicating
which locations the paths terminated. I inverted these
4-digit numbers, and filtered numbers ending in 2,4,5,6,and 8
to get a list of all 4 digit suffixes that were possible.
Then I went down the prefixes in order, and found for each
digit that connected to a suffix, I tested for primes.
HOW DID primetime TEST A CANDIDATE FOR PRIMALITY ?
I handled 3's separately by keeping a suffix map.
I handled 7-31 by using a gcd algorithm.
I used Algorithm P on page 379 of Knuth volume 2 which uses
Fermats test to eliminate most other primes.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I looked at the input to eliminate boards that only had
single digit solutions. I handled the case that all
digits where of the form 1mod3 by starting my search
at 8 digit numbers.
Finally, it looked as if the largest amount of time for
most problems was for program invocation and termination.
I used system calls directly and called _exit() rather
than exit() to speed linking. I ran my ANSI-C program
through the program "proto" to get a C++ program since
tests indicated that it used cc rather than acc, and
my tests indicated about 5% less startup overhead.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Techncal Manager of a software reasearch group. Ever heard of ksh?
ANY IDEAS FOR THE NEXT POTM?
It would be good to find a problem whose solution might
be useful if embedded in a library. An example might
be something such as audio and/or video compression.
It might be useful to define a more complex metric
for best solution; for example something that takes
both speed and size into consideration.
=================================================================
======================================= =primanujan =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=primanujan 660 140 100 80 80 260
=================
primanujan was submitted by Vincent Goffin at vjg@mozart.att.com
=================
HOW DID primanujan CHOOSE CANDIDATES FROM THE SQUARE ?
It starts from 999,999,999 and checks all lesser odd numbers in turn.
It finds how many different sequences on the grid can represent
the current odd number. This is easier than it sounds because only the
end point of a sequence needs to be tracked (if two sequences cross,
they only count as one from then on). The end point is where the next
digit will attach and that's all we need to know.
For efficiency, the pattern of end points on the grid is represented
as a 25 bit pattern (stored as an int): each bit is a grid position and
a bit is lit if it is an end point, otherwise not.
As long as the pattern is > 0, there is at least one legal sequence that
generates the number -- and in the lowest level of looping can often be
done in a single bit-logical operation between ints.
The sequence grows using recursive calls so that if we hit a snag and
the end point pattern evaluates to zero, we simply pop one level of recursion
and continue from there.
For the last two digits the algorithm changes gear and uses a sieve to
skip multiples of 2, 3, 5, and 7. Matching the two gears is a bit tricky.
Once the last digit is reached, the number is odd, not a multiple of 3, 5 or 7,
is represented by a legal sequence (mostly unknown), and is the largest one
remaining. It then gets tested for primality.
HOW DID primanujan TEST A CANDIDATE FOR PRIMALITY ?
I started with the only method I knew: dividing by all primes less than
the square root of the number. Profiling (using quantify) the code showed
most time spent in remainder calculations. Even with clever short cuts this
remained the bottleneck. An inspired trip to Barnes & Noble got me a copy
of Neal Koblitz' "A Course in Number Theory and Cryptography" and I learned
that there are better ways to determine primality. I used his "strong
pseudo-prime algorithm".
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I learned more about arithmetic in a few weeks than I had in many years!
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I work in product support in the Software Technology Center (BL-5911).
For fun? but of course, the POTM!
ANY IDEAS FOR THE NEXT POTM?
How about packing same size spheres in a given volume of n-dimensional space?
It's a well known problem (Kepler problem in 3d) and unsolved for even
moderate n, I think.
The program with the most spheres, or the best packing ratio, wins.
It would print out the sphere center coordinates and a "verifier program"
could check that the spheres do not overlap.
=================================================================
======================================= =quickprime =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=quickprime 710 90 120 90 120 290
=================
quickprime was submitted by Bill Tanenbaum at tan@intgp1.att.com
=================
HOW DID quickprime CHOOSE CANDIDATES FROM THE SQUARE ?
Except for special cases, it simply chose all numbers, largest first,
except it demanded that they end in 1, 3, 7, or 9.
It was careful to focus on the numbers rather than the paths through
the grid to find them. By setting up all sorts of adjacency matrices,
I was able to loop through all possible numbers, largest first, rather quickly.
It took a LOT of work to set this up.
Special cases covered with special code:
All 0, 2, 4, 6, and 8, print 2
All 0, 2, 4, 6, 8, and 5, print 5
All 0 and 7, print 7
All 0, 3, 6, and 9, print 3
All 1's (prime test only 1111111, 11111, and 11)
Special cases covered with minor modifications to the general algorithm.
All 1, 4, and 7 : start with eight digits (no 9 digit solutions)
No 1's or 7's : (number must end in 3 or 9, (both 0 mod 3), so can determine
at second to last digit if candidates must be multiple of 3.
No 3's or 9's : (number must end in 1 or 7, (both 1 mod 3), so can determine
at second to last digit if candidates must be multiple of 3.
HOW DID quickprime TEST A CANDIDATE FOR PRIMALITY ?
Explicitly checked for divisibility by primes up to 120 (except 2 and 5)
(derived, of course). After that, used Fermat's theorem to base 2 only!
2^p == 2 mod p.
This is actually faster than just using Fermat's theorem directly, as you
find composites with small factors quickly.
A pseudoprime to base 2 without a prime factor of less than 120 would
have tripped me up! I deliberately took that risk to try to win!
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Too bad I missed getting 7 on this case:
04040
00000
00000
00000
70707
The bug was, that the general algorithm (excluding the
obvious special cases above) failed to search one digit candidates.
I did not realize this, and was surprised to discover this bug.
This was a bug, not a deliberate omission.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Write software, mostly.
=================================================================
======================================= vprime =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
vprime 940 80 100 140 90 530
=================
vprime was submitted by Phong Vo at kpv@research.att.com
=================
HOW DID vprime CHOOSE CANDIDATES FROM THE SQUARE ?
Vprime checks all possible values in a square starting from the largest
value. The basic strategy is to compute all values that can be prefices
of length 5, 4, 3, 2, 1 and where they end on the board. Similarly, compute
all values that can be suffices of length 4 and where they start.
Then values are generated by matching proper prefix and suffix values.
A (prefix,suffix) pair of values match if some ending digit of the prefix
value is adjacent to some starting digit of a suffix value. Due to
the small board size 5x5, a 32-bit mask is enough to keep track of all
ending (starting) positions for each prefix (suffix) value. Adjacency can
then be tested by an & operation. To focus the search, prefix values are
generated in groups where all members of a group share the same first two
digits. Two different strategies are used to generate suffix values.
If there are many repeated digits, then all suffices of length 4 are
generated at once. Otherwise, they are generated as needed.
HOW DID vprime TEST A CANDIDATE FOR PRIMALITY ?
Suffices divisible by 2 and 5 are rejected early.
Then values are rejected by divisibility by 3.
Divisibility by small primes in the range [7,29] is checked
using a binary GCD algorithm (Knuth Vol. 3). After that,
the Miller-Rabin probabilistic prime testing method with witnesses
3, 5 and 7 is used to test for compositeness (Intro to Algorithms
by Cormen, Leiserson and Rivest).
ANY OTHER COMMENTS, TRICKS, WHATEVER?
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I am in the Software Engineering Research department in MH.
Some of the popular software packages that I am either fully
or partially responsible for are the malloc and curses libraries
in System V, sfio, the Safe/Fast IO library to replace stdio,
IFS/Easel, a language for writing menu and form systems,
and DAG/DOT, a program to draw directed graphs.
For fun, I do landscaping, read science fictions,
and sometimes play around with algorithms and data structures,
ANY IDEAS FOR THE NEXT POTM?
Dave Korn and I talked a little about this.
It looks like potm is a good way to attract good programmers
to solve interesting problems but it's unfortunate that much of
this effort is not usable in any practical software. It would
be nice if you can find some problems that would result in
some interesting software that we can benefit from later.
Just so that this is not just a vacuous statement, the
sfio library has a pair of functions sfgetd/sfputd that read
and write double values in a (semi-)portable form. This is
important for applications that run on a network of heterogeneous
hardwares and need to communicate values across machines.
I wrote this based on the frexp/ldexp/modf routines but
I am unhappy because they are not quite portable (different mantissa
problems) and they can be slow. So a problem is to find a way to
encode/decode such double values using a minimal number of bytes
and such that the encoded bytes can be transported across machine
boundaries without loss of accuracy or minimal loss of accuracy
in the case when sizeof and mantissa are different. This problem
may be a little boring but it sure has great practical value for me.
Maybe you could also solicite similar practical problems on the net.
=================================================================
======================================= primal_scream =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primal_scream 1040 120 400 190 180 150
=================
primal_scream was submitted by David Roe at roe@hogpb.att.com
=================
HOW DID primal_scream CHOOSE CANDIDATES FROM THE SQUARE ?
1) Set up a table of pointers to adjacent cells in the square
2) Create a stack of partial integers of length up to 9,
starting from strings of length 1
3) Find the largest integer, regardless of primality, first.
Sort the stack by size of the partial integers
4) Add digits from adjacent cells to the end of the
largest integer on the stack
5) (speed) Trash the partial integer if it cannot get to 1, 3, 7, or 9
by the 9th digit.
6) (speed) Keep track of parity (mod 3). Trash the partial integer if parity
will be a problem, and it can't get to 1, 3, 7, or 9 with a change
in parity (mod 3) by the 9th digit.
HOW DID primal_scream TEST A CANDIDATE FOR PRIMALITY ?
1) sieve to find all primes less than 31623.
2) divide candidate primes by list of primes in the sieve.
It turns out not much CPU time was spent actually evaluating primes.
Repeatedly sorting the stack took more CPU time.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
By testing on many computer generated squares, I found some interesting
pathological cases. Then I tried to speed up those cases.
Tricks 5) and 6) above helped a lot.
Test for special cases by getting a histogram of digits present in
the square.
Re-writing the qsort() to find only instances of the largest integer
on the stack as needed, might have saved time, but I didn't do it.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Speech recognition.
ANY IDEAS FOR THE NEXT POTM?
Anything, as long as the tiebreaker is NOT the number of characters.
=================================================================
======================================= prime8 =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
prime8 1040 90 120 80 90 660
=================
prime8 was submitted by Stephan Zdancewic at sz24+@andrew.cmu.edu
=================
HOW DID prime8 CHOOSE CANDIDATES FROM THE SQUARE ?
prime8 generates numbers from the square starting with
the largest and counting backwards by maintaining a bit vector that
represents all of the possible neighbors from the current square(s).
It then ANDs this vector with the locations of the next largest digit
(calculated once at the beginning of the program) to determine the
next set of squares. This is done recursively, and the value of the
number currently being generated is kept. In this way, all possible
routes through the square that can form a number are checked simultaneosly.
HOW DID prime8 TEST A CANDIDATE FOR PRIMALITY ?
I used Fermat's little theorem with several bases to determine whether
a number was probably prime. Sufficient bases were used to make it
very unlikely that the number was a strong pseudoprime. No
deterministic prime test was done (ie prime8 will fail if a
pseudoprime is the largest number found)
ANY OTHER COMMENTS, TRICKS, WHATEVER?
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I'm a Junior at Carnegie Mellon University
=================================================================
======================================= ptime =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
ptime 1080 180 220 90 110 480
=================
ptime was submitted by Bob Ashenfelter at ash@hotlg.att.com
=================
HOW DID ptime CHOOSE CANDIDATES FROM THE SQUARE ?
Candidates are generated in decreasing order from the digits in the square.
To limit the number of bogus candidates, lists of all digits neighboring
each digit are generated beforehand. Lists of all digits neighboring pairs
of digits are generated as needed. The first and last digits are diff-
erent. The first can be any digit found in the square except 0. The last
can be only chosen from 1, 3, 7, 9 (if in the square); more lists of neigh-
bors are generated containing only these digits.
So, the procedure is as follows. The most significant digit is chosen
from all the digits in the square, largest first. For each most-signifi-
cant digit, the second digit is chosen from those that are neighbors of
the first somewhere in the square, again largest first. Each subsequent
digit is chosen similarly, but considering the previous two digits. The
least significant digit is chosen considering only one previous digit
using the special lists that exclude even digits and 5. If no 9-digit
candidate is accepted, then 8, 7, ..., 1-digit candidates are generated.
The candidates are generated using the digits in the square rather than
the positions in the square because there are fewer digits (<=10) than
positions (25) and this ratio is compounded by the number of significant
digits in the answer. However, depending on the square, it may generate
a lot of bogus candidates that are not actually in the square. Therefore
a second procedure is used to weed out the candidates that are not in the
square. This procedure generates lists of valid square positions for each
significant digit of the candidate. Starting with the most significant
digit, all positions which contain the correct digit and are neighbors of
a valid previous position are put in the valid list for the next most
significant digit. If at any level there are no valid positions then the
candidate is rejected.
The two procedures communicate with each other to avoid doing useless work.
For example, if the validity check fails after considering the three most
significant digits, the candidate generator is told to skip all remaining
candidates with these three significant digits. Likewise, if after a
candidate has been rejected, the next candidate shares some most signif-
cant digits with the previous one, the validity check jumps into the
middle knowing that the previous work still applies to the upper digits.
HOW DID ptime TEST A CANDIDATE FOR PRIMALITY ?
This is a multistep process. The first step is to avoid generating any
candidates which are divisible by 2 or 5. This is described above. The
second step is to make a "quickie" check between the candidate generator
and the validity checker. This tests only factors 3 and 7 and the next
several prime factors. (I think I left this at 12 more--the average run
time is extremely unsensitive to how many.) The quickie prime check weeds
out a lot of candidates. For the tougher squares there may be thousands
or tens of thousands of candidates larger than the true answer but only
a few hundred get by this step.
The final prime check is performed on those few (maybe a dozen) candidates
that get past both the quickie prime test and the square validity test.
It uses an array of 48 differences between numbers that are not divisible
by 2, 3, 5, or 7 to generate and test possible factors up to the square
root of the number being tested. This procedure was distilled from the
source code for the UNIX utility "factor". For a 9-digit number, about
half the possible factors are non-prime and thus superfluous, but the
cost to generate a more efficient list rapidly exceeds the benefit. In
fact, the full prime check is used so sparingly that all odd numbers up
to the square root could be used as possible factors (multiplying the
number of trial factors by another 2-1/2).
Of course, the array of 48 factor differences looks suspiciously like a
list of prime differences and thus can't be explicitly initialized as it
is in factor.c. I checked with the POTM-Meister and he disallowed it
even though it contains no entry greater than 10 and is based only on
primes less than 11: "Sounds like a weasel to me...". It's no big deal
to compute it.
The first candidate to get past the quickie prime test and the square
validity test and the final prime test is the answer.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Although the problem inherently involves only integers, numerical calc-
ulations (such as testing prime factors) should be done with double-
precision floating point numbers rather than integers. I was surprised
to find that floating point arithmetic executes twice as fast as integer
arithmetic! Of course, its all done in hardware.
It may seem that all squares have either a 9-digit answer or a 1-digit
answer (or the answer is 11, but this won't be used) and all the 1-digit
cases can be detected and treated separately so the main procedure needs
only to be capable of finding 9-digit answers. But how do you know that
there isn't some obscure square with a smaller answer? If our problem
had been to find the largest prime of no more than 7 digits, there are
squares with a 3-digit answer. Therefore it is important that the pro-
cedure be able to find answers of all lengths (including 1), and to check
that it does it should be tested with the special cases turned off. In
fact, there IS a square with a 1-digit answer which is not readily detect-
able as a special case. When I found it, just a few days before the
deadline, ptime put out an answer that was both not prime and not in the
square! I sent the square to Fred along with my corrected program and he
said that he "really" liked it...
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Circuit design.
Bicycling, grow orchids, travel.
Are you kidding??? That's an oxymoron! If I tell, it's not a secret.
ANY IDEAS FOR THE NEXT POTM?
Well, yes. Many years ago I came across a problem about putting pieces
on a chessboard which I couldn't solve so I wrote a computer program to
do it (there were lots of solutions!). Although the resulting program
was quite small, the logic was very tricky, or should I say sticky, and
the program took a couple of hours to execute (late at night on a VAX).
=================================================================
======================================= primary =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primary 1400 250 180 90 100 780
=================
primary was submitted by Warren Montgomery at warren@iwrmv1.ih.att.com
=================
HOW DID primary CHOOSE CANDIDATES FROM THE SQUARE: A recursive
search, looking for the biggest numbers first digit by digit.
Primary used a bitmap to represent all points in the square where
a sequence ending in the current digit could be found, and then
tried to find the next digit adjacent to each, thus finding each
candidate only once.
HOW DID primary TEST A CANDIDATE FOR PRIMALITY Built a table of
primes less than the square root of 999999999 using standard
methods and tested by exhaustive division (over 3000 candidates to
try).
ANY OTHER COMMENTS, TRICKS, WHATEVER? Other than the bitmap
strategy, which was my biggest breakthrough, being careful in
building the prime map (e.g. exploiting the fact that of each 6
integers, only 2 are potential primes), and realizing that Sparcs
don't have integer divide (so the prime test was done with floating
point divisions to avoid an expensive software emulation of the %
operator). I also test explicitly for cases where all digits are
even, all are multiples or 3, or all multiples of 5.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I'm a technical manager of a systems engineering group, for fun, I
get as far from technology as possible (ski slopes, coral reefs,
golf courses, back country travel, etc.
=================================================================
======================================= the_pump =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
the_pump 1430 230 360 110 140 590
=================
the_pump was submitted by Michael Chin at mchin@bubba.att.com
=================
HOW DID the_pump CHOOSE CANDIDATES FROM THE SQUARE ?
Candidates were chosen by making up a set of legal three digit numbers
and marking where their heads and tails were in bit fields. Making a
nine digit number was performed by concatenating the four three digit
numbers (they included three one-digit overlaps) whenever their heads
and tails matched. This generates additional cases where the entire
nine digit number is not reachable. After checking for primality, a
separate algorithm is used to determine whether the entire number was
reachable.
HOW DID the_pump TEST A CANDIDATE FOR PRIMALITY ?
Prime numbers were calculated using the sieve method. Additional
speed was obtained by noting the fact that prime numbers form rings as
long as the numbers are prime w.r.t each other (given true).
Therefore, I made a list of all the odd numbers, determined the prime
numbers in the first (3 * 5 * 7) odd numbers. I then memcopy'd that
initial pattern over all the prime number. All succeeding numbers
were then eliminated by taking the next prime and marking every
multiple of that prime starting from that prime squared.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
It was fun playing with operator overloading in C++. For me, it was
fun just to fool around with C++.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I spent way too much time on this.
ANY IDEAS FOR THE NEXT POTM?
MIT's Technology Review has a neat little puzzle every year.
(Actually every issue has a short puzzle section). Anyway, the
objective is to take the digits of the next year (i.e. 1995) and
generate all the nubmers from 1 to 100 from them using only the
operations (+, -, *, /, ^). Grouping is allowed (i.e. 99 - 15 is
legal). Parentheses are allowed. Additional points are awarded when
you get the digits in the right order (i.e. 1 + 9 + 9 + 5). Also
points are awarded for using the fewest number of operators.
=================================================================
======================================= squambulator =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
squambulator 1510 80 140 80 90 1120
=================
squambulator was submitted by Lew Mammel at lew@uscbu.ih.att.com
=================
HOW DID squambulator CHOOSE CANDIDATES FROM THE SQUARE ?
It used a bit mask to find all digits ( or positions ) which
could be the next digit of the largest untried number. This way
the possible numbers were tested in strictly descending order -
an optimal strategy.
HOW DID squambulator TEST A CANDIDATE FOR PRIMALITY ?
It used Fermat's "little theorem" I got the hint because someone
named their program "fermata", but I programed my test pretty much
from scratch. I did browse a little in the book store in some book
on algorithms to see if I was on the right track. I wrote my own
modular exponentiation routine, which looks like a kindergartner
wrote it.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
As usual, I dropped the ball. I was a few lines of code away from
picking up the diablolical "7" , but when I thought about these
possiblities I decided .... "Naaaaaaaaaaaahhhhhh".
I coulda been a contender.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I'll never tell how many hours I spent on this! ( I don't even
wnat to know myself. )
ANY IDEAS FOR THE NEXT POTM?
Half serious - same puzzle with 10 digits and 6 by 6.
=================================================================
======================================= primal_duck =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primal_duck 1700 300 330 100 150 820
=================
primal_duck was submitted by Mike Gagle at bl_indpls!gagle@inuxs.att.com
=================
HOW DID primal_duck CHOOSE CANDIDATES FROM THE SQUARE ?
For starters, I represented the square using a 10 element vector and a 9 by 25
element array. Elements of the vector corresponded to the digits 0 - 9 and each
element of the vector was a bitmap with a bit set for each cell in the original
square which contained that digit. The array contained bitmaps for each of the
25 cells in the square for each of the nine digits of the number being
generated. These bitmaps had bits set for each possible neighbor of that cell.
For the last digit generated, the 'neighbor' bit was only set for cells which
really were neighbors and which could be the last digit of a prime (1,3,7,9).
This information was then propogated into the neighbors list for the fourth-
through second-last digits of the number being generated to limit the trial
space (given the nature of the problem, the first five elements of the array
didn't vary and were initialized at compile time).
Given these data structure, the routine started with the bitmask corresponding
the all cells with 9s and examined all of their neighbors. All neighbors with
9s (then 8s, 7s ... 0s) were recursively examined. When a number of the correct
length had been generated it was tested to see if it was a prime.
HOW DID primal_duck TEST A CANDIDATE FOR PRIMALITY ?
Nothing very special here. I did a Seive of Erastothenes (sp?) to find the
primes less than 31622 (which is roughly the square root of 9,999,999).
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I created a bitmask of the input digits and checked for only even numbers, only
{0, 3, 6, 9} and only {0, 7} for fast tests of semi-degenerate squares. I
orginally had code to look for patterns of digits which couldn't be primes (such
as <0,x,y,x,y,x,y,x,y> or but it seemed like this violated
the Prime Directive on A-Priori Knowledge of primes greater than 11 so it took
it back out.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
To earn an income, I'm a contractor for the labs. I have worked on data
communications things like an ISDN home controller project and salvaging the
data comm part of the VideoPhone 2500 while at the Labs and have done database
and full text retrieval work when not working for AT&T.
=================================================================
======================================= enterprise =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
enterprise 1760 400 310 260 200 590
=================
enterprise was submitted by Marc Unangst Amy McGovern at mju+@cmu.edu
=================
HOW DID enterprise CHOOSE CANDIDATES FROM THE SQUARE ?
We used a fairly simple iterative algorithm. We first found the
largest number by finding the largest digit in the square, finding its
largest neighbor, etc., and storing the digits in an array. This
number was then tested for primality. If it wasn't prime, then our
algorithm backed off and found the next-largest digit for the
least-significant place. If it couldn't find a smaller number there,
it backed off another place and found the next-largest digit for that
place, followed by the largest neighbor in the next place, etc. This
algorithm continues, trying successively smaller numbers, until it
finds a prime.
There was also special-case code in the program that tested for a
square solely consisting of multiples of 2, multiples of 3, multiples
of 5, or multiples of 7, and immediately printed the correct result
for these squares.
HOW DID enterprise TEST A CANDIDATE FOR PRIMALITY ?
We used Miller's probabilistic test, with up to 10 randomly-generated
witness numbers. To ensure accurate results we probably should have
backed this up with a deterministic test if Miller's test indicated
that the number was probably prime, but we've yet to see a number
which passes our implementation of Miller's test but isn't actually
prime.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Not really. I think our program is faster than Daroohahaha, so even
if we don't win the contest I'll still feel good, since Daroohahaha
was written by our professor. :-)
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
For a living: I'm a sophomore ECE (electrical & computer engineering)
student at Carnegie Mellon, with a CS minor. My partner, Amy
McGovern, is a junior Math/CS major at Carnegie Mellon. I also work
part-time as a systems programmer for the School of Computer Science.
Amy works part-time as a programmer for a user-interface research
group at CMU, the Amulet Group.
For fun: Volleyball. Star Trek. (Yes, both of us.)
ANY IDEAS FOR THE NEXT POTM?
Optimal solutions for the Towers of Hanoi problem, with a number of
pegs greater than 3.
=================================================================
======================================= prime =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primeval 410 90 90 70 80 80
vprime 940 80 100 140 90 530
primer 3700 560 330 100 110 2600
potm_prime 15730 4110 1200 120 310 9990
goodprimes 70300 30710 17440 4150 7370 10630
primetime 560 80 130 90 110 150
=quickprime 710 90 120 90 120 290
prime8 1040 90 120 80 90 660
prime 1890 330 410 250 230 670
primeRib 20400 410 1470 1480 1600 15440
=usdaprime 22040 6690 240 150 190 14770
primecut 40200 14870 670 200 960 23500
gr_primes_id 51640 13050 8020 1110 800 28660
primevil 153230 140 810 40710 48740 62830
primesquare 412400 225780 230 19220 109210 57960
=================================================================
======================================= square-nt =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
square-nt 2000 110 100 170 150 1470
=================
square-nt was submitted by Brian Beuning at bgb@psp.att.com
=================
HOW DID square-nt CHOOSE CANDIDATES FROM THE SQUARE ?
It does a depth first search, selecting the largest digits first.
At the top level, it just does for( k = 9; k >= 1; k-- ) and finds
all squares with a value of 'k'. Then it does the depth first
search on that square, picking the largest neighbors of each square
first. To make it easier to find the largest neighor, square-nt
makes a data structure for each square that for each square includes
a list of neighbors sorted by value.
It also does a couple of types of pruning of the search. The simplest
is if we have found a prime, if we are looking down a leg of the search
tree that is less that the answer we found we don't need to search this
leg any more. It uses an array max_at_depth[10] which is subscripted
by the level of the search. This array starts out with 0, and is filled
in when we find an answer. Then the search checks the value for the
level the search is presently at to decide if this leg of the search
can not find an answer bigger that the answer we already have.
(This is one area I thought could be improved, if the code always only
looked at the biggest number possible first it wouldn't need to above
pruning and could not waste time looking down search legs that might
find an answer that is not the largest.)
The second type of pruning I called "been here before", consider this
partial input square
9 0 1
0 0 0
2 0 3
starting at the '9', there are two ways to get to 900, the first way is
by going right then down, the second way is by going down then right.
The depth first search by itself would blindly search both of these legs
even though they will find (or not find) all of the same results.
The "been here before" check looks for this case and prunes the search
to save this redundant work.
HOW DID square-nt TEST A CANDIDATE FOR PRIMALITY ?
The Sparc does not have a divide instruction, so square-nt goes
to great lengths to do very few divisions.
The tests for multiples of 2 and 5 are handled by checking the last
digit in the number. The test for multiples of 3 are handled by
keeping a sum of the digits, and check if this sum is a multiple of
three (by a simple table lookup).
For the numbers that are not multiples of 2, 3, 5, it does trial division
for the primes up to 50. This eliminates lots of numbers. If a number
passes all of these tests, then I use a "strong pseudo prime" test on
it. The strong pseudo prime test is very similar to the fermat test
which uses ( a^n % n == 1 ). The trick is that since 'n' is close to
being a 32 bit number, the intermediate results can overflow so it can
not use C operators.
It turns out that the same number can get tested for primality more than
once during a depth first search. So square-nt has a hash table to keep
track of what number have been tested for primality, and will only do
the above (expensive) test once for any given number.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
The tools on the sun for tuning performance are limited to the PC-smapling
type tools. Since the entries are ran pretty fast, PC-sampling isn't much
help for tuning. I ended up using a MIPS machine with its pixie tool for
some tuning. The pixie tool rewrites an object file after running this new
object file, it gives precise instruction counts for every block of code
(and function).
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
For a living, I work on the A-I-Net products. Mainly working with
making a programming language used by our customers to defined services
for running on the SCN and SCP.
For fun, I got a copy of Civilization as a present. It is lots of fun.
Also one of the reasons I jumped into this POTM, is I have done some fooling
around with finding factors of Mersenne primes.
ANY IDEAS FOR THE NEXT POTM?
How about something where the programs compete against each other.
One makes a move, an arbiter tells the first move to the second
contestant, it makes a reply, the arbiter tells the first program
the reply, and so on until a winner is found. Like corewars, or
there was something a while back about programs that showed that
cooperation was a winning strategy.
=================================================================
======================================= priem =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
priem 2110 90 340 360 130 1190
=================
priem was submitted by Stan Peijffers at hvgtw!hvssa01!speijffe@attmail.att.com
=================
HOW DID priem CHOOSE CANDIDATES FROM THE SQUARE ?
***************************************************************
The search algorithm is a recursive one by expanding a set of
square nodes. It generates the candidate primes
in decreasing order (highest first).
There is no sorting and expansions are only executed when needed.
This is how it works :
Before beginning the recursive expansion algorithm, the square
information is represented as a 2-dimensional array (10 x 10),
with the first dimension representing a "from" digit value and
the second dimension representing a "to" digit value.
Every element in this array contains a set of bitmap pairs (integers),
where each
bit represents a node in the square (nodes 1 to 25).
There is a set of bitmap pair for every digit in the square
(with a bitmap pair for every adjacent value) :
-the first bitmap contains one bit showing the node in the square
for this digit (with the "from" digit value).
-the second bitmap contains a set of bits, each bit showing the nodes
in the square for the "to" digit values.
The search algoritm starts off by constructing a bitmap representing
the nodes of the digits with the highest value digit.
This bitmap is fed to the recursive expansion algoritm.
Each expansion consists in accessing the above constructed array
with the value of the digit and successively map the current bitmap onto
the "first" bitmaps. When there is a match, the bits of the "second"
bitmap are retained in a newly constructed bitmap, which is
passed on to the next level of recursion.
The recursive function "expand" has the following parameters :
expand (level, bitmap, digit, val)
where
- level : the current level of recursion
- bitmap : the current bitmap showing all nodes
which are being expanded
- digit : the current digit value.
- val : the current value of the number.
HOW DID priem TEST A CANDIDATE FOR PRIMALITY ?
***************************************************************
- Execute the "mod" operation with all possible divisors up to
sqrt of the prime candidate, skipping all multiples of 2,3 and 5.
- The result of the mod operation (z = x % y) is marked in a large
array (or rather a set of arrays). Indeed, x-z is a multiple of
y, therefore it is not necessary to check a later candidate
prime with this value.
(Before invoking the prime testing algorithm this array is checked).
NOTE : I have considered marking all values x - z -n.y but this turned
out to be too much overhead.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
***************************************************************
I had what I believed to be a rather nice algoritm to perform the modulo
operation only with prime numbers. And this effectively increased
the speed of the algorithm with about 20-30% on my PC (where I
initially developed the algoritm). Unfortunately the same
"improvment" on the SUN slowed it down with about 20-30%.
So I left it out.
Anyway this was the algorithm :
An array should be maintained with an entry for each divisor (1 -> 32K).
A "0" entry means that this is a prime number. A non-zero entry means
that this is a non-prime number and the value is the value
of the lowest prime that divides this non-prime.
This array is constructed while looping thru the divisors and performing
the modulo operations. It makes use of an auxiliary array in which
for each prime 2 pieces of information are maintained : the next prime,
and the increment to reach the next prime.
As we loop thru the divisors (say "y") the following actions are performed :
- if y is a prime, then mark y*y as a non-prime in the array (with value y).
Update the entry in the auxiliary array for the previous prime (next and
increment to this new prime).
Perform the mod operation.
- if y is a non-prime (with value z which is a prime)
then get the increment to the next
prime from the auxiliary array (say value d), and mark y + z*d as a
non-prime. Update the auxiliary array to have the prime z now
point to the next higher prime in the chain (next and increment).
Do not perform the mod operation.
In doing so mod operations are only performed on primes.
A high-water mark on the y values covered so far should be maintained, because
clearly this should be done only once per y value.
=================================================================
======================================= symphony =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
symphony 2250 80 230 80 120 1740
=================
symphony was submitted by Gerie Alards at galards@intgp1.att.com
=================
HOW DID symphony CHOOSE CANDIDATES FROM THE SQUARE ?
HOW DID symphony TEST A CANDIDATE FOR PRIMALITY ?
Instead of using the expensive % operator the / operator was
used. Its 50% less expensive!
if (n % i == 0) { no prime }
can be replaced by:
m = (double) n;
if ((long) t == (t= (double) m / i)) { no prime }
(refer to symphony.c)
ANY OTHER COMMENTS, TRICKS, WHATEVER?
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I joined AT&T Network Systems Netherlands in '89 as software
engineer. My areas of interest are software development automation
and neural networks.
ANY IDEAS FOR THE NEXT POTM?
Neural networks can be a good next candidate.
=================================================================
======================================= =primate =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=primate 2520 130 330 110 130 1820
=================
primate was submitted by Debbie Brown at dwb@arch4.att.com
=================
HOW DID primate CHOOSE CANDIDATES FROM THE SQUARE ?
My original approach:
I had a data structure constructed at initialization time
that stored the "next moves" from each location in the square.
Each invocation of the procedure
is called with a value computed so far and a list of positions in the square
at which that val can terminate. At each call to the procedure,
I check each digit (in decreasing order from 9, ..., 0) to see if
that digit can be reached from any of the positions in my list. If so,
I add this digit to the right-hand side of the previous val, and recalculate
the list of positions. When I've generated a 9-digit value, I check
to see if it is prime. I repeat this procedure for 8-digits, 7-digits,
etc.
Unfortunately, instead of strictly sticking to this general approach,
I tried to put in some special cases - which did me in.
tried to take into account some special cases - which did me in
HOW DID primate TEST A CANDIDATE FOR PRIMALITY ?
At initialization, I used the sieve of Erasthothenes (is that how you
spell it), to generate all the primes less than or equal to
the square root of one billion. When I had a candidate from the square,
I kept checking to see if one it was divisible by one of the primes
I had generated.
=================================================================
======================================= odd =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
odd 3390 90 490 100 120 2590
=================================================================
======================================= primer =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primer 3700 560 330 100 110 2600
=================================================================
======================================= goldbach =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
goldbach 7320 1100 250 140 150 5680
=================
goldbach was submitted by Dave Lynch at dfl@esun.att.com
=================
HOW DID goldbach CHOOSE CANDIDATES FROM THE SQUARE ?
Created a matrix indicating which digits are adjacent to each digit.
Used this matrix to generate a decreasing list of possible candidates.
At each step, checked whether the candidate could actually be constructed
from the original 5x5 grid.
HOW DID goldbach TEST A CANDIDATE FOR PRIMALITY ?
Constructed a list of prime numbers <= sqrt(largest candidate), using
Sieve of Eratosthenes. Divided candidate by each prime and checked whether
the integer quotient equaled the floating point quotient.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Screened out trivial cases up front.
A conjecture concerning prime numbers was proposed by Christian Goldbach
during the 18th century and (as far as I know) still remains unsolved.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Develop private data network design software.
=================================================================
======================================= primoggle =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primoggle 7400 4210 470 250 780 1690
=================
primoggle was submitted by Ravi Sharma at sharma@mozart.att.com
=================
HOW DID primoggle CHOOSE CANDIDATES FROM THE SQUARE ?
primoggle built from the input matrix a scan-list for each (i,j) which
is a depth-first generation of numbers, but only 3-levels deep. After
sorting the scan-list (delayed sorting as much as possible), it
then performs a concatenation function by repeatedly joining numbers
from the scan-list to generate a 9-digit number which is tested
for primality. The tail section of the concatenation comes from
a separate scanned-list which is filtered for prime-digits in
the final position (i.e., only 1, 3, 7, 9 were allowed), so obvious
composites were eliminated (evens, and multiples of 5).
HOW DID primoggle TEST A CANDIDATE FOR PRIMALITY ?
A sieve algorithm was used to precompute primes up to 31623 (which
is sqrt(10^9)). The sieve only need to compute multiples of up to
177 (sqrt(31623)). The test for primality did the standard thing by
attempting to divide primes (less than the sqrt of the candidate)
into the candidate. A sqrt table was used to avoid making the
call to the sqrt function.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Attempted performance tweaks were to filter the scanned-list to
eliminate duplicates. Bit arrays were used to keep track of the
precomputed primes, duplicates in the scanned-list, and previously
tested candidates in primality testing.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
In my normal life, I work for the Software Technology Center in
building the SDE (Software Development Environment). As a current
life, I'm supporting the AT&T Network Notes project with some of
my Lotus Notes, development, and integration experience. For fun,
I enjoy time with my wife & two daughters -- enough to keep me
busy and sane away from the POTM. My innermost secret wouldn't
be one if I told you; besides I'd have to encode a way to eliminate
any reader of the secret and I'm not quite finished testing that
mechanism yet :-).
=================================================================
======================================= Labyrinth =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
Labyrinth 9200 1270 780 230 250 6670
=================================================================
======================================= srch4prm =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
srch4prm 11070 520 8820 130 120 1480
=================
srch4prm was submitted by Dale Harris at attbl!iesde!om7@att.com
=================
HOW DID srch4prm CHOOSE CANDIDATES FROM THE SQUARE ?
Rather than searching through the squares for candidate paths,
I rather searched through the possible values, from high to low.
I did a parallel search through all squares that gave a given value.
Thus:
search with all 1st sqaures with a value of (9,8,...)
search will all 2nd squares with a value of (9,8,...)
...
I used a bit map to indicate the set of squares I was on.
It was lucky that there 25 sqaures, ie less than 32,
so that a single unsigned long could represent the set of squares
that could give the accumulated value being examined so far.
I did use next square pointers to travers the square,
but I traversed all paths in parallel that had the highest value so far.
HOW DID srch4prm TEST A CANDIDATE FOR PRIMALITY ?
Basically by modular division of all primes in a list.
The list of primes stopped at the square root of the maximum value.
And I also stopped testing when the prime used was greated than
the sqaure root of the value being tested for being prime.
I may have saved some time by creating a composite of small primes,
the product of which is less than the square root of the maximum value.
The cost was calls to memcpy() and the savings was less mod divides.
This probable saved most when creating my list of test primes.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
The idea of searching for values, not paths, from high to low,
allowed me to stop the search as soon as I found a prime,
knowing that I had found the highest prime.
This thus saved many calls to "isprime", and thus many mod divides.
When constructing the list of test primes, I was able to save some
time by using a different algorithm for prime testing.
I created a list of primes in the range of the square root of
the square root of the maximum value.
I then took all odd multiplications of those primes to set
a "can't be prime" flag in an array the size of the square root of max value.
I could then go throgh that array and know that any odd index
which did NOT have a "can't be prime" flag set, MUST be prime.
Thus, I generated the prime test list via a series of adds,
rather than mod divides, which ended up costing less time.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
My job is C and C++ programming on some tools that compile
a high level language into database operations.
For fun, I play video games, I write letters and books,
and I go dancing at night clubs.
The writing is not so much "fun" as it is work.
In fact, the night club thing is also kindof work,
since it was research work for my second book.
I authored the book "The Quest for Love"
under the pen name of "Dave Erickson".
Its ISBN is 289-7059-02-8.
I am also involved in the men's movement and attend and speak
at conferences on gender issues. For example, in early Feb '95
I will be at the "International Men's Day" conference in Toronto
and speak on subjects related to my book.
( Organizer: Tom Oaster, PO Box 10033, Kansas City, MO 64171. )
=================================================================
======================================= potm_prime =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
potm_prime 15730 4110 1200 120 310 9990
=================================================================
======================================= primeRib =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primeRib 20400 410 1470 1480 1600 15440
=================
primeRib was submitted by Glenn Bradford at gmb@ams.hr.att.com
=================
HOW DID primeRib CHOOSE CANDIDATES FROM THE SQUARE ?
It did a recursive walk starting from the highest digits and worked
downward. First it checked for trick grids, then it searched for 9 digit
solutions, then 8, 7, ... Standard stuff.
HOW DID primeRib TEST A CANDIDATE FOR PRIMALITY ?
Very slowly by dividing all the prime factors up to the square root of
the candidate. If HOT DOG hadn't knocked me out, this would have.
I didn't realize this was my bottleneck until the 11th hour (literally).
Up until then I had been optimizing my program with better pruning techniques.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I recognized {1,4,7} and coded for it. I also kept track of partial paths
that had been searched already at every location on the grid for the first
6 steps so that I wouldn't needlessly search them again. I also kept track
of the top 10 composite numbers that kept popping up in the search, so I
wouldn't have to check them again for primality. I also had a fast way
to find solutions to grids composed of only 2 different digits, by
generating all their 9-digit permutations (in a pre-sorted fashion).
My program incorrectly calculated HOT DOG as 44404447. It did this during
the 9 digit search when the leading digit was 0, effectively turning it
into an 8 digit number. If I had coded it properly to prevent a leading zero,
the new answer would have been 47! This was due to a second bug
involving the arrays which stored the partial paths tried. I failed to
initialize this memory when starting to look for primes 8 digits long.
In the back of my mind I was aware of this latter problem, but
I never thought anyone would come up with an 8-digit grid outside of
{1,4,7} !! I should have known better!
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I'm a software developer in Network Systems. For fun I play racquetball
and putter around the house.
=================================================================
======================================= =usdaprime =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=usdaprime 22040 6690 240 150 190 14770
=================
usdaprime was submitted by Neil Weinstock at nsw@luna.att.com
=================
HOW DID usdaprime CHOOSE CANDIDATES FROM THE SQUARE ?
Simple (relatively) recursive search. At each node, I selected the next
node based on which would yield the highest possible 9-digit value, so
I would, at least roughly, search in order from highest to lowest.
HOW DID usdaprime TEST A CANDIDATE FOR PRIMALITY ?
I wish I knew of a better way to do this (is there one?), but all I did
was divide the number (call it N) by a list of primes from 3 to SQRT(N).
I did some other checks as well, to minimize the number of times I needed
to go through this time-consuming process:
1) If the last digit of the N wasn't 1,3,7, or 9, then it
couldn't be prime, so I skipped the checks.
2) If N was <= the largest prime I had found so far, then I again
skipped the check, since there was no point.
3) If I had already tried this value (see below), then I skipped
the check.
Oh, I generated the list of primes (potential factors) using a basic sieve.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I checked for all the obvious trick boards, i.e., all board entries multiples
of 2, 3, 5, or 7. In addition, I found one interesting and unobvious (to me
at least) trick board: when no digits on the board are either 1,3,7, or 9,
then the answer is the highest single-digit prime found on the board.
In my search, I kept track of all the values I'd seen before, plus the
positions in which I'd seen them. If I ever encountered a value I'd seen
before in the same position, then I terminated that branch of the search
immediately, since I'd already covered it. If I encountered a value I'd
seen before in a different position, then I at least avoided doing a
prime check on it.
I used a sorted list of "seen" values so I could do a quick search on it;
insertions unfortunately took a while.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
1) Hardware developer for BNS-2000
2) Volleyball, bowling, perl hacking
3) I am Elvis (please don't tell)
ANY IDEAS FOR THE NEXT POTM?
Not a specific idea, but a general one. How about some sort of task that
is like a game, in that you pit two programs against each other? You
give each program the current board and its current run time, and it returns
the new board. You then run a tournament to decide the winner.
I realize how difficult it would be (impossible?) to come up with a game that
would be suitable for such a contest, but it would make an interesting change
of pace. Code Size and run time limits would make the challenge. An ideal
game would be a new one for which no algorithms would already exist.
Ah, well. Just a thought...
=================================================================
======================================= BoggleYourMind =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
BoggleYourMind 24080 5510 330 590 800 16850
=================================================================
======================================= usda =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=usdaprime 22040 6690 240 150 190 14770
usda 24310 2310 420 170 210 21200
=================================================================
======================================= mintu =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
mintu 27900 2440 1000 3090 3800 17570
=================================================================
======================================= gridzip =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
gridzip 31260 7320 370 130 160 23280
=================
gridzip was submitted by Rana Dutt at rcd@mtqua.mt.att.com
=================
HOW DID gridzip CHOOSE CANDIDATES FROM THE SQUARE ?
Picked the largest digit(s) in the square with the largest
neighbor to start with. Kept a list of neighbors sorted by value
for each position. Walked the square recursively from
each starting digit. Picked next candidate from list of sorted
neighbors, going from largest to smallest.
HOW DID gridzip TEST A CANDIDATE FOR PRIMALITY ?
Kept a cache of the last 50 non-primes found during testing, and searched
the cache for a match first. Only if no match would I test using the more
time-consuming division-by-primes-less-than-square-root approach.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
The main optimization was to avoid traversing routes already visited.
Did this by keeping a list of n-digit numbers that had already been
generated/visited for each position, for n=1 to 9.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Design software for a WAN access system. Play tennis and racketball for fun.
=================================================================
======================================= primecut =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primecut 40200 14870 670 200 960 23500
=================
primecut was submitted by Joe Eccles at joe@mink.att.com
=================
HOW DID primecut CHOOSE CANDIDATES FROM THE SQUARE ?
Searching was done depth first, with candidate squares at each search level
ordered highest value first, and in the case of equal values, in order of the
highest value "neighbor" for that square.
HOW DID primecut TEST A CANDIDATE FOR PRIMALITY ?
Hard code results for 1 and 2, then simply check for zero remainder as the
number is is divided by sucessive odd numbers up the approximately the
square root of the number.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
- Never check a number for primality if it is smaller than the largest
prime found so far.
- If sqrt() is used, it becomes the most expensive component of the
program, so the upper limit is changed to be the minimum of the number
itself, or the sqrt of the number rounded up to the next largest power of
2. This estimate can be generated byusing a series of "and"s with fixed
bitmasks, and a couple of shift operations. The savings compared to the
use of sqrt() more than makes up for the extra remainders computed.
- If there is symmetry in the problem, make use of it.
- If row 5 is the same as row 1, and row 4 is the same as row 2,
eliminate rows 4 and 5. If in addition, rows 1 and 3 are the
same, also eliminate row 3.
- Do the same reduction for columns.
- Never reduce to less than 2 rows or columns.
- There were other problem reduction possibilities that were
not implemented due to lack of time. For example, if a corner
has the same value as two of its neighbors, never consider it.
(This is a small gain for most problems).
- Prune the search tree.
- At any search level, if a search starting at any candidate square
has already produced a prime number with 9 digits, discard all
other candidate squares whose value is smaller than that one.
- By saving a list is digits and matrix coordinates for the largest
prime found, never search a subtree whose digits so far match the
prime, and whose next square has the same coordinates as the next
coordinate for the known prime.
- If a 9 digit prime has been found on any search path, never consider
a candidate square whose value is less than that of the known prime
for the corresponding digit.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
- Software development.
- Golf, music, bridge.
- Sometimes programming can actually be fun.
=================================================================
======================================= gr_primes_id =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
gr_primes_id 51640 13050 8020 1110 800 28660
=================
gr_primes_id was submitted by Kenneth Smolik
=================
1. HOW DID gr_primes_id CHOOSE CANDIDATES FROM THE SQUARE?
First of all, the square is searched for the special one-digit-prime-number
cases. It is given that at least one prime number is in the grid, and the
grid does not have all of its digits as 1's.
Therefore, if all the digits are divisible by strictly one of any of the
one-digit prime numbers (2, 3, 5, or 7), then the one-digit prime itself must
appear at least once in the square and also be the largest prime in the square.
Otherwise, numbers in the grid less than 10^9 are sequently picked out largest
to smallest, to be tested for primality.
A for loop from 9 down to 1 executes, where the loop counter
represents the number of digits of the next number to be found.
Then a function is called recursively, where each recursion selects
a digit for the number in the order from leftmost to rightmost digits.
To select the largest numbers first, the gsort library function sorts all
the values in all possible grid positions for the current digit to be
selected from largest to smallest and then sequntially goes through the test.
For a given digit possibility, all possible grid positions for the next
digit are stored in another array, and this array is passed to the next
recursion of the function.
After all the digits are selected, the number is tested for primality.
If it is prime, the number is displayed as the program exits; otherwise
the recursion process is continued until a prime number is found in the grid.
HOW DID gr_primes_id TEST A CANDIDATE FOR PRIMALITY?
To test a given number for primality, the number2 and all
positive odd intergers other than 1 <= to the square root of the given number
are tested as factors of it.
The idea is to insure that at least all possible prime numbers are tested as
factors of the given number in the most systematic (and legal) but quickest
manner.
No even numbers besides 2 are prime and since all factors <= the square root
of a given number must have a corresponding factor >= the square root of the
given number, there is noo need to check tha above square root.
If no factors (besides 1 and itself) are found for a givennumber, then
it is prime.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
If there were many if not any possible grids that have largest primes with
between 2 and 8 digits inclusive, then if might save run-time to use a
temporary file to save all
9-digit numbers found, and then for numbers 8 or less digits, the right-hand
digit for a given d-digit number can be truncated to form a corresponding
(d-1)-digit number.
However, since all grids presented so farthat I've seen are either 1-digit
special cases or 9-digit prime number grids using a temporary file proobably
is a waste of time- both for the program author and its system run time.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Being a systems engineer, I did not have a clue about solving the POTM problem.
However, I did pass the "requirements" to my developer who is my son Andrew.
Andrew is a high school senior and is taking an AP CS course in Pascal.
He is also active in the Math Team, which took first in IL state competion.
During hisspare time, he designed the program using Microsoft Quick C.
(This program was his fun during XMAS break!)
Andrew will be entering UIUC in EE this fall and is looking for
a summer job in computer programming. If anyone has any leads, please contact
me at ihlpf!kfs.
ANY IDEAS FOR THE NEXT POTM?
Given some integer x between 1 and some other integer (depending on how
long the program would take to run- perhaps 100 to 1000) generate
a closed forula strictly in terms of n for the summation from
i=1 to n of i^n (in other words, 1^x + 2^x + 3^x + ... + n^x).
This formula should be in the form of a polynomial in terms of n.
The program should output the sum of the numerical coefficients of each
term; for example, in the polynomial a*n^4 + b*n^3 + d*n + e the program
should output whatever the value of the sum a+b+d+e is.
The sum should be rounded to a certain number of significant digits.
The formula and sum both must be generated; no sums, formulas, or
parts of the formulas for the summation may be in the source code.
=================================================================
======================================= EnQuest =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
EnQuest 59590 17730 2490 5040 6240 28090
=================
EnQuest was submitted by Frank Rehwinkel at fsr@kingfish.att.com
=================
HOW DID EnQuest CHOOSE CANDIDATES FROM THE SQUARE ?
Ordering the 25 cells so they'ld be looked at in descending order.
For each cell, created a descending ordering of the cells around it.
For each cell, kept a hash table that tracked which number had already
been tested for that cell. (This reduced a lot of excess searching
down branches that had effectively already been traversed.)
The cells were traversed in descending order, and once a 9 digit
prime was found, the search tree could be pruned whenever a cell was reached
that didn't have at least the value of the associated position in
the candidate prime.
HOW DID EnQuest TEST A CANDIDATE FOR PRIMALITY ?
I learned my lesson here. The library could probably have taught me much
about primes judging from the solutions the fastest programs used.
I created a list of primes, the hard way (using %), that would then be
used against any odd number that was larger than the largest prime found
so far. I even forgot about the trivial test for 5s and the easy test for 3s!
(So I guess it doesn't matter that I never heard of the test for 7s, 11s and
13s.)
ANY OTHER COMMENTS, TRICKS, WHATEVER?
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Design and develop software for ADSS (in Quest), a group specializing in
optimization software for the airline industry.
ANY IDEAS FOR THE NEXT POTM?
How about trying to solve one of the many NP-hard optimization problems
that we get from the airline industry (e.g. travelling salesman or bin-packing).
=================================================================
======================================= goodprimes =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
goodprimes 70300 30710 17440 4150 7370 10630
=================
goodprimes was submitted by David Good at dgood@iwcs.att.com
=================
HOW DID goodprimes CHOOSE CANDIDATES FROM THE SQUARE ?
All possible paths through the array were built up starting with the
low-order digit.
HOW DID goodprimes TEST A CANDIDATE FOR PRIMALITY ?
1) I ran the standard sieve to generate an array of all primes less than
sqrt(999999999) (there are 3400 of them).
2) For each path through the array, I checked the remainder of the
number against each of the primes in the prime array, starting with 7
(since filtering step 1 eliminated the need to check for 2 and 5, and
filtering step 3 eliminated the need to check for 3), until either the
prime array was exhausted, or the current prime was more than sqrt(num)
(so num had to be either prime, or a composite number whose smallest
factor was greater than sqrt(num) (!!) )
3) filtering: "for each path through the array" is not quite right.
1) if the starting cell (low order digit) is 0, 2, 4, 5, 6, or 8,
none of the paths can be prime, and are not even generated.
2) if the digit to be prepended to a number is == 0, there is no need
to check to see if it is a prime, since it will not be a largest prime.
3) if the current number modulo 3 == 0, it is divisible by three,
and is not a prime.
4) if the current number is less than the largest prime found so far,
there is no need to test it for primality.
5) if the current number matches any of the numbers previously found
to be not prime, it is not prime, and need not be checked.
(I kept an array of not_primes[], which eliminated a *lot* of the need
to do modulo math, which is apparently slow on System 3000's and SUNs
(involving a subroutine call?))
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I originally had a paths() subroutine that called itself recursively.
I wrote a program to generate 225 pathsLXY() routines, collapsing the
depth and the current position into the subroutine names, so all array
calculations involved constant subscripts, so addresses could be
calculated at compile time.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
For a living: I'm in the StarServer FT development and support group
at IW. For fun: I read a lot of science fiction.
=================================================================
======================================= primevil =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primevil 153230 140 810 40710 48740 62830
=================
primevil was submitted by Stuart Rowland at swr@mtatm.att.com
=================
HOW DID primevil CHOOSE CANDIDATES FROM THE SQUARE ?
Brute force
HOW DID 0ready4 TEST A CANDIDATE FOR PRIMALITY ?
Divided by all prime less than or equal to sqrt of number
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I was truly "not ready for prime time" - I wrote the simplest
program that would solve the problem since I did not have the
time required to work on a faster solution.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
ANY IDEAS FOR THE NEXT POTM?
=================================================================
======================================= spite =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
spite 231740 126560 720 10150 61510 32800
=================
spite was submitted by Gerald Williams at gsw@aloft.att.com
=================
> HOW DID spite CHOOSE CANDIDATES FROM THE SQUARE ?
This was the fast part--it first checked for degenerate cases (i.e.
all numbers in matrix divisible by 2,3,5,7) while generating a linked
list through the matrix in which the links are keyed on the following
digit. This can be thought of as a tree when it is expanded by
following the first 8 links. It recursively traversed the "tree" by
depth, starting with 9 digits, and by number, starting with 9.
> HOW DID spite TEST A CANDIDATE FOR PRIMALITY ?
This was the extremely slow part. Actually, the testing itself was
fast, but the setup was slow. It first generated enough primes to
factor the largest prime the square could produce, then used those to
try to factor candidate primes. The last few known non-primes were
kept track of to avoid checking them again, and some other tricks were
used to make the generation faster or not test numbers that can't be
prime.
The program was not supposed to work this way in its final form.
There are MUCH faster ways to test primality, although I did not
remember the algorithms at the time (I was surprised the entry did
as well as it did with this algorithm). I borrowed a book on primes
and primality testing, but did not have a chance to read it since I
was coordinating over a dozen software releases around Christmas (it
wasn't my idea!).
> WHAT DO YOU DO FOR A LIVING?
Spend too much time coordinating other people's efforts and not
enough doing REAL programming.
> FOR FUN?
Ski. Travel. Whatever else I can fit in between work, graduate
school, and working on our new house.
> INNERMOST SECRET?
It wouldn't be a secret then, would it?
=================================================================
======================================= prisq =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
prisq 307510 195860 1190 10510 74410 25540
=================================================================
======================================= voodoo =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
voodoo 359830 125700 1390 23300 107310 102130
=================
voodoo was submitted by Ram Ramachandran at rams@ihsdv1.att.com
=================
HOW DID voodoo CHOOSE CANDIDATES FROM THE SQUARE ?
Did some preliminary checking to eliminate the case of all numbers
divisible by 2, 3 and 5.
Then checked to see symmetric squares along the diagonals. If so eliminate
numbers above the diagonal and check if the resultant set of pattern is
symmetric across its "diagonal" and further eliminate numbers. Do this
till no more can be eliminated.
Sort the list in descending order.
Computed primes up to sqrt (999999999)
Starting with the highest number pick candidates moving from position to
its neighbour and keeping track of the highest computed prime.
HOW DID voodoo TEST A CANDIDATE FOR PRIMALITY ?
1) Test for multiple of 2, 3, 5.
2) If < sqrt(999999999) binary search to see if it is one of the primes
computed.
3) If > sqrt (999999999) see if divisible by one of the primes computed
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Looking for symmetric squares.
I think I was on a time "(de)warp". I thought the dead line was Monday
night. Over the weekend I found one major bug which causes it to code
dump in certain cases. I came all prepared to mail the POTM master my
final version just to find out that I was 8 hours (9 if dead line was
11:59 EST) too late...
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
I work for the Switched Digital Video project at Naperville, Illinois.
=================================================================
======================================= FIVE =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
FIVE 366240 270 980 28060 242350 94580
=================
FIVE was submitted by Mark Meyer at mdm@cbnscs.att.com
=================
HOW DID FIVE CHOOSE CANDIDATES FROM THE SQUARE ?
A simple recursive traversal of the grid, starting at a 9 (or highest non-zero
digit) and stepping to the highest of the (up to 8) next possible digits.
HOW DID FIVE TEST A CANDIDATE FOR PRIMALITY ?
The biggest time saver was to remember previous candidates in a
Digital Search Tree. It also checks the last digit (not even or 5),
and compares if longer and greater than current high prime.
The IsPrime function is rather simple and used only when necessary.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
It looks for those special grids (like all 3,6,9,0, all 1,4,7, etc...)
There must be a way to reduce the size of non-random grids (which I suspect
some others have done.) FIVE works well for random grids.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
- Systems Engineering, Software Development, System Testing, and Field support
for the Netminder Network Trouble Patterning team.
- Golf, Bowling, surf the internet, and enter the POTM.
- ...but then it would not be a secret ;-)
ANY IDEAS FOR THE NEXT POTM?
Whatever my next programming assignment is...
=================================================================
======================================= primesquare =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
primesquare 412400 225780 230 19220 109210 57960
=================================================================
======================================= Deion =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
Deion 525040 459510 1130 6290 26170 31940
=================
Deion was submitted by Dennis Sanger at drs@dr.att.com
=================
HOW DID Deion CHOOSE CANDIDATES FROM THE SQUARE ?
Just plain ol' depth-first, largest-first searching. After submitting a
working version in early November, I never got around to improving my entry.
I suppose I should be pleased that it actually got a perfect score, even
though it got stomped on the tie-breaker.
HOW DID Deion TEST A CANDIDATE FOR PRIMALITY ?
It's too embarrassing to talk about.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Living: software development for the Multimedia Call Server. Fun: Anything
else. Innermost secret: Aliens speak to me via transmitters implanted in
my molars.
=================================================================
======================================= poot =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
poot 619970 619020 530 140 140 140
=================================================================
======================================= yap =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
yap 953250 618690 1280 84050 162980 86250
=================================================================
======================================= Daroohahaha =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
Daroohahaha 1042940 606540 830 420 560 434590
=================================================================
======================================= =past_my_... =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
=past_my_... 1202330 200 340 614170 474730 112890
=================
past_my_... was submitted by Fred Hicinbothem at fah@ffast.ffast.att.com
=================
HOW DID past_my_... CHOOSE CANDIDATES FROM THE SQUARE ?
VERY UGLY ... prepared an ordered list of neighbors for each
of the 25 squares - largest neighbor first. Then, looked at
the biggest starting numbers and examined each neighbor in
turn until a nine digit string was found. Then test it - if
no good, move down the stack until all nine digit numbers
are tested. Then go to 8 digits ... etc.
HOW DID past_my_... TEST A CANDIDATE FOR PRIMALITY ?
Nothing too difficult - Sieve of Eratosthenes (easier to code
than to spell) to come up with a list of primes, and then
straight use of % ...
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Got rid of repeated candidates, divisible by 3 candidates, those
that end in 0,2,4,5,6,8, squares with all (7,4,1), all one
number squares, etc.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Systems Engineering and project management (whatever they are);
POTMs, games, and family (not necessarily in that order);
my secret? - I can't code worth a damn!
=================================================================
======================================= 2true =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
2true 1504710 610830 2370 27700 616780 247030
=================================================================
======================================= bodkin =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
bodkin 1653930 614920 1870 105580 619440 312120
=================
bodkin was submitted by Ton Kramer at ton.kramer@att.com
=================
HOW DID bodkin CHOOSE CANDIDATES FROM THE SQUARE ?
for startdig = 9 downto 1
do
step recursively through the square taking the heighest
neighbour as next digit
if it is a prime and larger than the one we have, mark it
if we have all numbers starting with startdig and prime is set
then print prime and exit
done
HOW DID bodkin TEST A CANDIDATE FOR PRIMALITY ?
test all even cases and then loop through 11 < sqrt(number)
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Due to my stupidity I lost the original code on my machine so
development stopped after the first entry.
I was designing a better way of selecting the correct branch but this
broke the original algorithm and I could not get the new algorithm to
work properly in the time I allowed myself to work on it.
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Living: I develop 5ESS ISDN features.
(Did develop Supervision Signaling features)
Fun: Drive my BMW R1100GS Motorcycle. Build Motorcycle models. Develop
tours for motorcyclists. Program C on my Amiga Home computer.
ANY IDEAS FOR THE NEXT POTM?
=================================================================
======================================= squaredance =============
=================================================================
Measured Time (milliseconds)
ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer
squaredance 1925820 612370 6080 616240 610890 80240
=================
squaredance was submitted by Graham McDermot at gmcdermo@ihlpo.att.com
=================
HOW DID squaredance CHOOSE CANDIDATES FROM THE SQUARE ?
A form of alpha-beta cutoff (or at least I think that was what
my lecturers at Uni called it.......dim distant past)
Judging by the performance of squaredance a very poor form of cutoff...
HOW DID squaredance TEST A CANDIDATE FOR PRIMALITY ?
I had originally planned to use the small array of numbers from the factor.c
code to generate all the prime numbers to test a candidate, however the
powers that be decided this was not allowed. I had no option then but to
hack in an odd number generator instead.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
These competitions are great fun, but like every other time I've entered
I get enough time to cobble together a first attempt, then only get an hour
or two every blue moon to update/change it........
WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET?
Field Support, ex-Development, now trying to get back into Development....
judging by my recent potm results I need the practice 8-)
ANY IDEAS FOR THE NEXT POTM?
1. How about a maze solving puzzle.....for example given a sample file
with an ascii representation of a maze, find your way from point A to point
B, program to output N,E,S,W as directions.
As an added twist find your way from A -> B then C.
Shortest direction, quickest time, smallest code decides or whatever.......
2. Magic puzzle solving.
All the numbers in an X by X square add up to the same in any direction
Solve the puzzle by using a set of numbers supplied.
Alternatively use the alphabet to represent the numbers in the same
way as the addition puzzle did but this time it has to solve a magic puzzle.
Shortest code, quickest time, highest numerical value of the digits or
subset of digits, etc.......
3. Finding the longest word acceptable to the system dictionary (if one exists)
from a set of letters passed to a program.
Multiple use of letters can be allowed or disallowed dependant upon the
whim of Mr POTM.
4. errm...thats all I can think of in 5 minutes.
=================================================================