RESET Program entry descriptions
Beware of long mail .... but there ARE gems buried!
Even if you don't study the whole thing, you might
want to check out the first four or five writeups!
The attached mail is the collection of write-ups I received. As usual
they are mostly unedited (only personal POTM-master insults were removed).
Write-ups are provided in order of finish (more or less).
The web sites will have code listings of PegTheSnail, PickQuick, and whirligig.
If you need even more detail - contact the authors - not ME!!!
=Fred
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
============== 1 ====================== PegTheSnail =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
PegTheSnail 1768 1 734/1 506/0 528/0 c Gerhard Lutz
=================
PegTheSnail was submitted by Gerhard Lutz at glutz@hydra.informatik.uni-ulm.de
=================
++ Please summarize the algorithm used by PegTheSnail
Here are the most important ideas of my algorithm:
1) Calculation of several solutions till time limit is reached and
choose the best one
2) finding the best move in a tree search by valuating the board position
at a depth between 3 and 7
3) breadth first search for values of the fields on the boards
4) breadth first search to limit the environment of the farest peg from
center where the next move is made
5) maximum depth of tree search depends on the number of checked
positions of the last move
6) Number of moves to check is limited because of the local search for best
move
7) isolated pegs without neighbours and walks are valued with many
negative points
++ How did you choose this particular method over others you considered?
I knew that it must be a tree search in a local environment and it's
impossible to find the ultimatively best solution.
I got the further ideas from week to week and that's also the reason
why the program is very long and difficult to read
++ Was this POTM too difficult?
The problem was very hard but I love this kind of problem,
not that shit with the shortest code or something like that.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
University of Ulm, student of computer science with bad english knowledge,
done for fun, most on my own, but also discussed with my ACM programming
team members
And now I go to bed because it's 1:45 AM
=================================================================
============== 2 ====================== PickQuick =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
PickQuick 1835 1 784/1 516/0 535/0 gc Giorgio DiFalco
=================
PickQuick was submitted by Giorgio DiFalco at G.difalco@agora.stm.it
=================
++ Please summarize the algorithm used by PickQuick
The main idea in the algorithm is to progressively shrink the problem, by
first processing the farthest regions then the closer ones. For this reason,
a distance matrix is first computed, where each cell contains a number
representing the distance (number of actual walks) of the corresponding
board cell from the board center. This matrix is then used for delimiting
and marking the pegs to be processed at each step, so reducing the
number of processed pegs to something between 8 and 15 per step.
(This idea seems to work well if the board is quite large and the pegs
are not completely asymmetric with respects to the center).
After choosing such a limited zone, the possible move sequences (up to 9
moves deep) and the best sequence is chosen according to a special
evaluation function. The selected sequence is then partially applied
(at maximum 7 moves of 9 are done, before reevaluating the situation).
This basic idea is dressed with a lot of variations for trying to get the
double result of having all problems solved in less than 10 minutes and
approaching the best solution.
++ How did you choose this particular method over others you considered?
I tried literally hundreds of different algorithms, mainly changing the
evaluation functions that are used for judging a position and choosing the
best of two sequences.
The last submitted program suffers for the need of running in the max time
allowed and appears to be not bad on very large boards but quite bad on small
problems (it never finds the best solution in small problems).
The worst aspect of the solution, as any other I have tried before, is that
it is very unstable, that is it does not depend in a predictable way from
the parameters chosen. For example, if I make a deeper analysis of moves
(longer sequences) or I enlarge the region analysed the solution often worsen,
instead of improving as I would expect.
Therefore I am not very proud of the program submitted, that should be
largely tuned and improved; I simply chose one version that was good
enough, on average, on some large test boards I used for testing.
++ Was this POTM too difficult?
There is nothing too difficult to try one's best.
BUT: it was to laborious and tiring; I spent about 100 hours of my time
and my program can be still considered a draft. I think it was difficult
for most people to find that much spare time. Maybe next problems should
better be slimmer (but this one looked not so hard at the beginning).
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company: Bluesoft
Location: Rome, Italy
Job: Consultant in system architectures and system software engineer
Fun: Family, Ski, Programs, Reading
Secret: I am an alien
POTM: Poker card solitaire: the input is a pack of 32 play cards (card
from 7 to ace). Cards are drawn one by one (up to the 25th) and
they must be put in a 5 by 5 square, starting from any position
in the square but putting each card after the first in a position
such that it is 'close' to another card (i.e. touching another card
with a side or a corner). When 25 cards are arranged in the square,
a final score is computed, by adding up the line-scores of the
5 rows, 5 columns and two diagonals. Each line score is computed
by evaluating the 5 cards in the line as they were a poker hand:
for instance, 1 point for a pair, 3 points for two pairs, 5
for three of a kind and so on.
=================================================================
============== 3 ====================== whirligig =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
whirligig 1927 4 750/2 579/1 598/1 gc =Franz Korntner
=================
++ Please summarize the algorithm used by whirligig
=================
Whirligig takes the initial board and calculates for each hole the minimal
distance to the center hole. It then takes the starting board (with pegs)
and processes the pegs which are located the farest from the center hole.
Each selected peg is either jumped or moved, creating a new board. This
continues until N boards have been created.
Each board is assigned a score which is calculated by summing the square
of the distance of each peg to the center hole.
Next, M boards with the lowest score are taken, and the above process is
repeated until a final solutions is found.
Whirligig starts with N=15 and M=40. When 530 seconds have passed this
will change to N=8 and M=2, and after 580 seconds, whirligig will panic
and set N=1 and M=1 (which will not always find a solution!).
++ How did you choose this particular method over others you considered?
It is fast. The others I was thinking about were more 'intelligent', but
were more CPU demanding, and would therefore probably not make it in
the finals.
I did think of a totally different algorithm, but didn't have the time to
test it out. Maybe I'll save it for the next POTM.
++ Was this POTM too difficult?
No.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
- ICT (guess that doesn't ring a bell). It's a kind of contracting company
focused on Embedded Software with over 500 employees.
- Leiden, Netherlands
- I'm a contracter specialised in developing operating systems, drivers,
compilers, debuggers, developers software/tools, network protocols,
software ports...
- Think about POTM and nice cryptic entry names, play Mahjong (I'm an
official for the World Championship http://www.mahjong.conf.au/ )
- I'm not in for winning, I just try to prevent others from doing so...
- Fitting problems
=================================================================
============== 4 ====================== pegjumping =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
pegjumping 1933 2 821/0 570/0 542/2 C Paul Nelson
=================
pegjumping was submitted by Paul Nelson at pknelson@lucent.com
=================
++ Please summarize the algorithm used by pegjumping
I built a 2nd array for the board and I calculated the minimum
number of moves from each hole to the center of the board
(accounting for blocked areas containing '_'s).
Before each move, I always looked at the 'X' that was the most
number of moves from the center and ran a series of "Can this
'X' make a jump ???" tests. If the farthest 'X' failed all
tests then I moved to the 2nd farthest 'X', then the 3rd, and
so on.
The first jump-test that I evaluated looked for jumps that
moved the current 'X' FARTHER AWAY FROM THE CENTER OF THE
BOARD but left it in a position to be jumped by another 'X'.
After that I generally looked for jumps that moved me closer
to the center of the board but always tried to land somewhere
that left me in position for another jump. There were a lot of
special tests that looked at special combinations of 'X's and
'O's (like XOXX). I had some tests that looked at long strings
of 'X's (like XXXXXXXXO). Strings that were exactly three 'X's
long were handled differently from longer strings.
If none of the 'X's could make a 'good' jump, then I went back
to the farthest 'X' and ran simply ran some "Can this 'X' walk
???" tests. I only considered walks that moved the 'X' closer
to the center of the board . I gave preference to walks
that moved me closer to another 'X' and put me in position to
make a jump on the next move.
++ What kind of tricks did pegjumping use to minimize code length?
Since I was awarded the "YOU MEAN THERE WAS A SOURCE CODE
LIMIT?????" consolation award I'm not sure I used any tricks to
minimize code length. Actually, my final entry was "only" 31,300
bytes long but Fred gave me this award because an earlier entry
was 41 Kb long. I'm not sure I really deserved the award.
However, the version I sent in didn't contain any comments - the
commented version was 59 Kb long - so, on 2nd thought, I'm pretty
sure I deserved the award.
++ Here's what I hated (and loved) about this POTM's scoring:
I would have liked to seen Fred publish the execution times for
each entry. I'm interested how fast my entry was in comparison
to the others.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM
IDEAS?
COMPANY: Lucent (Santa Clara, CA)
JOB: MTS
=================================================================
============== 5 ====================== Solo =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Solo 2144 12 863/2 629/5 652/5 c Aivars Zogla
=================
Solo was submitted by Aivars Zogla at acad.latnet.lv!ugale@kcig2.att.att.com
=================
++ Please summarize the algorithm used by Solo
++ How did you choose this particular method over others you considered?
++ Was this POTM too difficult?
As somebody said: programs=data structures + algorithms.
So, first about data structures:
1) there are 3 arrays which stores:
a) allpegs - positions of all pegs on the board;
b) mas - board itself;
c) map - map of the board, t.i, distance from given position to the
center of the board. This map helps to be sure that all pegs will
move to some "center" and will "eat" each other until one SOLO peg
will stay. (Next time POTM will be anounced for PEGGED Fred will say
us, competitors, which peg must stay on the board at the end. ;) )
2) structure movetype is used to store possible move and bestmove in
current position and intermediate moves while evaluating.
Now, about algorithm:
1) some of competitors have faced a problem of time - 10 minutes for 25x45
board+sophisticated algorithm isn't too much. So, I didn't think much about
good algorithm, besides, it was VERY EXCITING to fight for time tiebreaker at
the first stages of PEGGED. Thanks Fred! Mostly I think about and search ways
how to beat time. What did I find?
a) every call to function takes time. I just copied code of some functions
into another, making program code as ugly as possible;
b) structure movetype contains more than necessary;
c) when I'm looking backwards, I'm considering possibility to copy recursive
function at the tail of itself some 2-3 times (instead of recursion).
Horrible!!! Good timing is well but in certain limits;
d) of course, sequence of using "if"s also is a difference.
2) to be sure that pegs will go through labirints of Fred's boards, I used map
of the board which was made twice:
at the start and after executing all possible jumps from start position
when, at some moment, only moves became available. Map is simply made by
assigning every position ('O' or 'X') a number of moves necessary to
reach the center of the board, which, in turn, is "center of gravity"
when map is preparing.
3) quality of the game depends on depth of recursion and number of analized
moves at current position (usually, with large boards there are more possible
moves than analized ones - time doesn't allow to look through more).
Depth of recursion matters with small boards, large ones doesn't allow depth
more than 2.
4) evaluation of intermediate position depends on:
a) number of pegs left on board (less - better);
b) number of "lonely" pegs (less - 3*better);
c) number of possible jumps at position (more - better);
Score at position is sum of "points" showed in map of the board. Not much, but
was enough.
Best score makes information about move which should be made at position.
5) there was no time check in my program because I hoped that timing of my own
tests showed me possible timing on Fred's computer and it will be under 10
minutes with every possible board. Nevertheless, when Fred made us 'friendly
POTM warning' I decrease number of possible jumps/walks looked through at
each move.
If after this long story somebody have any questions - email me, let's talk.
>++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Aivars Zogla (ugale@acad.latnet.lv)
I'm informatics teacher(fanatic) at Ugale Secondary School, Ventspils district,
LATVIA. (Guess, where it is.)
Previous POTMs were entered by Krists Boitmanis, 12th class student. This time
he was busy with other local competitions (gold everywhere, my pleasure). So, I
decided to try myself. Soon my eldest - Arturs (10th class) - will enter, I
hope.
You can easily guess what I'm doing for fun. But in summer I should take part
in my youngest son's Gatis fun - fishing. Absolute beginners level. Fortuntely,
my daughter Ilze doesn't ask me to share her hobby - knitting. On the other
hand, I couldn't say the same about my wife Aija. Sometimes I should do
something on the ground level - with spade and wheelbarrow. So, besides
programming, family is my fun as well.
The best POTM idea is POTM itself. I really appreciate what Fred is doing for
my(our) enjoyment. I'm glad to be in POTM's company. Best wishes to all!
=================================================================
============== 6 ====================== hiqqup =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
hiqqup 2252 3 873/1 720/1 659/1 c Warren Montgomery
=================
hiqqup was submitted by Warren Montgomery at wamontgomery@lucent.com
=================
++ Please summarize the algorithm used by hiqqup
Hiqqup computes the distance in moves from the center to each
square. If a jump is available, it will pick the jump that reduces
the total peg distance (sum of square distance for all squares
occupied by pegs) by the larges amount. If no jump is available,
it will make a move to reduce peg distance, with some attempt to
move pegs towards other pegs to create jump opportunities. It
picks a move or jump, makes it, then picks the next one with no
backtracking.
++ How did you choose this particular method over others you considered?
Peg distance minimization was an easy way to guaranatee that it
will make progress and keep the last pegs near the center.
Backtrack/search algorithms could clearly improve on this but I
never had time to implement one.
++ Was this POTM too difficult?
No, about right. I'd still like to see a simple problem with
limited time to work on it. Projects with 3 month deadlines are
too much like real work.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lucent, Naperville ILL
=================================================================
============== 7 ====================== PEGOUT =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
PEGOUT 2292 3 921/1 692/1 679/1 c Austin Green
=================
PEGOUT was submitted by Austin Green at austin@ww.co.nz
=================
++ Please summarize the algorithm used by PEGOUT
Stage 1: For each peg, find the number of steps to the central hole,
avoiding obstacles but ignoring other pegs.
Stage 2: For each peg, evaluate each possible move, classifying as a
walk or a jump and as 'improving' (reducing distance from central hole)
or 'non-improving'. Find the best move out of all the pegs, favouring
jumps over walks and improving moves over non-improving. Make the move
and output it.
Stage 3: Repeat stage 2 until there is only one peg left or no more
legal moves are possible.
++ How did you choose this particular method over others you considered?
It was the only one I could think of! The original version omitted
Stage 1, and so came to grief on the second system test board.
This was going to be the basis of an algorithm which performed the
processing described for numerous possible first moves, then selected
the best of those for evaluation of second moves, and so on until the
available time was used up. Unfortunately, I had very little spare
programming time to devote to this POTM, so the program remained at a
very basic level (only two entries submitted).
++ Was this POTM too difficult?
No, just about right for me.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
COMPANY: Self employed.
LOCATION: Auckland, New Zealand.
JOB: (1) Contract programmer/analyst. (2) Emu farmer.
DO FOR FUN: Programming, sailing, reading, cryptography,
net surfing, all sorts of stuff.
INNERMOST SECRET: Secretly, I would >really< like to win the POTM contest.
POTM IDEAS: Why not let ME specify the next POTM?
(See 'innermost secret'). :-)
Seriously: how about a maze-solver, input similar
to last POTM, output moves for shortest path from
start to finish; or, if that's too similar to the
last contest, perhaps something to do with fitting
shapes together, like pentominoes or jigsaw puzzles
or whatever you can imagine up.
=================================================================
============== 8 ====================== Pegasso =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Pegasso 2355 27 915/2 667/14 773/11 gc Misha Dynin
Sorry ... no description available for Pegasso
=================================================================
============== 9 ====================== WIN_A_PEG =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
WIN_A_PEG 2450 9 914/1 736/7 800/1 gC Derek Ross
=================
WIN_A_PEG was submitted by Derek Ross at d_ross@iders.mb.ca
=================
++ Please summarize the algorithm used by WIN_A_PEG
A tree-search looked forward one move and selected the "best" move. The
scoring function was:
Number of pegs * k1
+ Variance of the coordinates of the pegs * k2
+ Number of pegs touching an edge * k3
+ Number of pegs in a corner * k4
+ The sum of the manhattan distances between each peg and the center * k5
The constants were "determined" by setting them to random values and
running the test boards repeatedly, then recording the constants that
provided the best results.
I made an attempt to determine the constants by simulated annealing, but
it didn't seem to be working too well.
I also discarded some of the better evaluation functions, simply because
they took too long to evaluate.
++ How did you choose this particular method over others you considered?
As I began hacking away at the proto-program with no specific technique
in mind, the tree-search thing sort of rose up out of the chaos.
++ Was this POTM too difficult?
It was hard, but it wasn't impossible. (just don't re-do that old POTM
where you have to find very large prime numbers in a random matrix...
now THAT looks hard!). Plus it was interesting, which gave me a little
more motivation to actually do it.
COMPANY?
IDERS Inc.
LOCATION?
Winnipeg, Manitoba, Canada
JOB?
Electrical Engineer/Computer Programmer
DO FOR FUN?
I sit hunched over my keyboard for hours on end, trying to force a
random grid of 'X's and 'O's to sort itself in 86 moves instead of 87.
INNERMOST SECRET?
My unrequited love for Dot Matrix (from ReBoot).
POTM IDEAS?
Anything dynamic that you can watch on your monitor is good.
*** ed note: then you'll like the Java Applet for PEGGED on the web sites!
Something related to AI... How about a "grid world" where a single
celled "robot" has to push around blocks into a pre-determined position?
I also like that simulation "Wa-Torr" where sharks eat fish and
population fluctuations occur. I don't know how you'd base a contest on
that, but it sounds neat.
Or something like "Core Wars" would be interesting, where you have two
programs battling it out in a memory buffer.
=================================================================
============== 10 ====================== blip =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
blip 3141 3 1115/1 1140/1 886/1 c Derek Noonburg
=================
blip was submitted by Derek Noonburg at derekn@vw.ece.cmu.edu
=================
++ Please summarize the algorithm used by blip
Fairly standard recursive depth-first search.
The scoring heuristic includes the number of remaining pegs, the
number of walks, and the sum of the distances to the center for the
remaining pegs.
The search tree is pruned at each level to the best N moves.
++ How did you choose this particular method over others you considered?
Everything I tried was some sort of variation of the recursive search.
The main tricks were to optimize so that the search and scoring were
fast, and to tune the scoring heuristic so that it worked fairly well
for small boards and still finished in time for larger boards. All of
this was done by trial and error.
++ Was this POTM too difficult?
No.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
PhD student in Electrical & Computer Engineering at Carnegie Mellon
University.
=================================================================
============== 11 ====================== LegoMyPego =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
LegoMyPego 4266 6 1524/3 1381/1 1361/2 c Eric Sinzinger
=================
LegoMyPego was submitted by Eric Sinzinger at sinzinge@math.sc.edu
=================
++ Please summarize the algorithm used by LegoMyPego
Genetic algorithm with some initial planned runs
++ How did you choose this particular method over others you considered?
Easier to implement
++ Was this POTM too difficult?
No. But my solution started to be tedious.
=================================================================
============== 12 ====================== Pegbiter =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Pegbiter 14359 26 3593/14 4829/9 5937/3 C =Andre' Wilhelmus
=================
Pegbiter was submitted by Andre' Wilhelmus at wilhelmus@lucent.com
=================
++ Please summarize the algorithm used by Pegbiter
Pegbiter maintains a list of jumps and a list of walks.
It chooses random jumps until no more jumps are possible.
Then it chooses random walks until a jump is possible.
Multiple attempts are made to find a better solution until time runs out.
++ How did you choose this particular method over others you considered?
I did not have the time to find a better method which works.
++ Was this POTM too difficult?
This POTM was very difficult.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lucent Technologies, application programmer, ^_-, bishoujo senshi, nope.
=================================================================
============== 13 ====================== JPeg =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
JPeg 10001380 2 9999999/0 728/1 653/1 c P.Banta R.Jolliff
=================
JPeg was submitted by Paul Banta at Paul_Banta@notes.ymp.gov
and Rex Jolliff at Rex_Jolliff@notes.ymp.gov
=================
++ Please summarize the algorithm used by JPeg
JPeg is literally the combination of two algorithms, both suggested
by Rex Jolliff.
The first algorithm that runs is a Goal Oriented algorithm. It
repeatedly finds the worst peg on the board and then tries to find a
way to jump it over another peg. This may involve constructing a long
series of jumps and walks in order to get another peg next to the
worst peg. This algorithm has one major advantage - it's blazingly
fast. When we gave it to Fred to run on the second test board, it
found a solution in 0.15 seconds. Unfortunately, it also has one major
disadvantage - it only finds a single solution. Rex coded the Goal
Oriented algorithm.
The second algorithm that runs is a Depth First Search algorithm.
It looks at the current board, exhaustively finds all possible moves,
throws out all but the best 25 moves, and orders them from best to
worst. It then makes the best move and recursively calls itself. When
the recursive call returns, it undoes the best move, makes the second
best move, and again recursively calls itself. The Depth First Search
algorithm has one major advantage - it finds multiple solutions. Once
it finds a solution, it keeps looking for a better one. Unfortunately,
it also has one major disadvantage - on some boards it doesn't find a
better solution than the Goal Oriented algorithm no matter how long it
runs. Paul Banta coded the Depth First Search algorithm.
Rex and I worked on this problem together from the beginning. I
got the DFS code to work pretty quickly while Rex tried implementing a
number of exotic algorithms. Near the end of the competition, Rex got
the Goal Oriented code working. Each of our algorithms were coded as a
separate program. This brought us to a dilemma. The DFS gave a better
solution to the first test board. The Goal Oriented gave a better
solution to the second test board. So, which one should we submit for
the final three boards? The best idea that we had during this whole
process was to slap the two together into a single program. Run the
fast Goal Oriented program first, save the results, and then see if
the DFS can beat it during the balance of the 10 minutes. When we put
our two programs together into one, it exceeded the 25K size limit (it
was 37K). Not to worry - wherever more than one blank space occurred,
we changed it to exactly one blank space. This rendered our code
unreadable, but got us down to 23K.
++ How did you choose this particular method over others you considered?
The short answer is that it worked. Rex tried a few others, but
nothing worked as well as either the Goal Oriented or the Depth First
Search.
In particular, Rex spent considerable time on an A* (pronounced
A Star) algorithm. A* is supposed to give something in between Depth
First Search and Breadth First Search. Actually, I think it's called
a Best First Search. For this particular problem, we convinced
ourselves that it was much closer to Depth First Search.
Another reason why we went with the Depth First Search algorithm is
that in theory it was easy to modify. The basic algorithm could be
left alone while changes were made to the evaluation function. Given a
particular board, it looks at all possible moves and evaluate them.
That is, for each possible move, we actually make the move, call the
evaluate function which returns us back a number, and then UNmake the
move. In theory, all we need to do to improve our performance is to
come up with a better evaluate function. Coming up with such a function
proved elusive.
++ Was this POTM too difficult?
Rex and I are in strong agreement that this was NOT too difficult.
This was a GREAT problem. We both THOROUGHLY enjoyed it (Thank You
Fred). In looking at some of the past problems, I have one comment: If
the source-code size is one of the criteria for deciding a winner, the
problem is probably too easy.
On the other hand, a good mix of difficulties is good - some problems
should be harder, some should be easier.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Rex and I work for TRW (ever wondered what TRW stands for?) in Las
Vegas Nevada. We write administrative database software for the most
part (Ingres, BasisPlus, Visual Basic, C, FORTRAN, HTML, Java). For
fun I like to play Volleyball, Hike, Camp, and toy with a neural
network that beats the spread in football (did I mention that we're
in Las Vegas Nevada?). Our innermost secret is BOZO. The only POTM
idea that I have is something like CRobots - the game where you write
a program to control a tank/robot that does battle with up to three
other such programs. The only problem is that it only understands 1
language - a subset of C - this might be restricting to some.
As Paul said, we work at TRW in Las Vegas. We mainly use DEC
Alphas running VMS and PCs running WinNT or Win31. There are lots of
things I like to do for fun, some of which are even legal here,
among which are model rockets, astronomy and miniature wargames. I
can imagine that finding good ideas for the POTM is tremendously
difficult. Perhaps this is even more difficult than solving the
problems. I would first suggest a variation on Paul's idea, where
perhaps programs from contestants could compete against each other
in some kind of simple game. Perhaps there are some interesting
mathematical or computational geometry problems that can be posed?
=================================================================
============== 14 ====================== Darwin =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Darwin 10001418 2 9999999/0 722/1 697/1 gC Didier Barzin
=================
Darwin was submitted by Didier Barzin at dbarzin@ulb.ac.be
=================
++ Please summarize the algorithm used by Darwin
My program is based on a genetic algoritm. It choose a
population of species sort them by fitmess and create
new population by making evolutions on the previous
one. This till the end.
++ How did you choose this particular method over others you considered?
First I considered a stupid depth first method ... but after
an evolution, it seems that the fitness of Darwin was better. ;-)
++ Was this POTM too difficult?
Just good.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I am a student in computer sciences at the Free University of
Brussels. I am working on a native code generator for the YAFL
compiler.
Next POTM: A Sokoban solver.
=================================================================
============== 15 ====================== ePeg =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
ePeg 10001460 3 802/1 659/2 9999999/0 c Paul Leventis
=================
ePeg was submitted by Paul Leventis at leventi@ecf.utoronto.ca
=================
++ Please summarize the algorithm used by ePeg
ePeg was inspired by my Electricity and Magnetism mid-term -- we were asked
to calculate the energy in a three particle system. Basically, my
heuristic value is determined by calculating the total bond length of the
peg board... Connect all the pegs to each other by a line, then sum up the
squares of all those distances.
ePeg (though not yet complete) first runs a quick test with a 4 or 8 board
buffer. This takes a few seconds. From how "far" from the solution it is,
it decides how many boards to use in the "real" buffer -- usually around
256, but sometimes as low as 32. By limiting the number of boards
maintained between jumps/moves, this keeps the execution time to a
maximum/move, allowing prediction of the execution time after 5 moves have
been completed. The algorithm adjusts the size of the buffer at that time
to maximize the search space.
The heuristic is the key to ePeg; Though it doesn't directly map onto the
best move, it usually suggests a pretty close answer. It automatically
avoids repeat board situations (they would have the same energy, therefore
wouldn't be better than the parents), and places more weight on getting rid
of "orphanned" pegs as the game progresses... All with one calculation. To
keep this operation rather speedy, my program maintains the current total
X^2, X, Y^2, and Y distances for each board, so the "energy" calculation is
constant time... It's irrespective of the size of input board.
++ How did you choose this particular method over others you considered?
Basically, it was a lot less complicated. Prior algorithms had to consider
factors such as total number of moves possible from a given board
situation, number of orphaned pegs, distance from the center, etc.; this
algorithm is a single calculation, with no "weighting" between factors to
consider.
It was also really easy to code, and I was getting desperate :)
++ Was this POTM too difficult?
No. It was quite challenging to find a viable solution, but possible. It
was tough enough to keep "casual" entries out while easy enough that it
could be handled at the same time as a job or school.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a first year student at the University of Toronto in Engineering
Science. I'm planning on specializing (in third year) in both Computer and
Electrical Engineering. In the summer I'll be persuing research in either
compilers or FPGAs.
I love programming (obviously), as well as volleyball, table tennis, and
chess.
Ideas for the next potm: Any sort of two-player problem that will involve a
round-robin tournament between entries. Could make things kind of fun.
=================================================================
============== 16 ====================== dreadnaught =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
dreadnaught 10001512 15 9999999/0 700/13 813/2 C Stu Rowland
=================
dreadnaught was submitted by Stu Rowland at swr@mtatm.ho.lucent.com
=================
++ Please summarize the algorithm used by dreadnaught
dreadnaught randomly picked on of the possible jumps. If no jump was
available, it randomly picked one of the possible moves that moved a peg
toward the center of the board. It continued to do that until if found
a solution. Having found one solution, it repeated the process trying
to improve on the solution until the 10 minute timer expired.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lucent Technologies, Red Bank, NJ.
=================================================================
============== 17 ====================== Pegatory =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Pegatory 10001678 4 925/1 754/3 9999999/0 gC Jim Eadie
Sorry ... no description available for Pegatory
=================================================================
============== 18 ====================== JWPEG =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
JWPEG 10001782 55 9999999/0 900/27 883/28 c Lorenzo Arnasalon
Sorry ... no description available for JWPEG
=================================================================
============== 19 ====================== bmh_peg =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
bmh_peg 10001814 22 1016/7 799/15 9999999/0 gc Bernard Hatt
=================
bmh_peg was submitted by Bernard Hatt at bmh@arkady.demon.co.uk
=================
++ Please summarize the algorithm used by bmh_peg
The basic idea is to look at every possible move/combination of moves,
however this can take a little while, so the tree of possible moves
is pruned according to a number of criteria:
a) The board looks the same(*) as one that's been reached with a less
than or equal number of walks.
b) More moves have been used than are needed for a known solution.
c) Any walk move where any jump is possible.
d) More than one possible move on an even numbered move.
All possible moves are sorted by order of preference.
If more than 60sec has been spent examining a portion of the tree without
a solution being found, it gives up and examines a branch lower down the tree.
(*) A simple pair of checksums was used, the 1st to generate a 16 bit index
into an array and the 2nd a 32 bit value stored in the array. If the
index/array contents match the boards were considered the same, however
it was possible for false matches to be generated, given the arbitrary
nature of some of the pruning (ie.(d)), I didn't think it mattered.
++ How did you choose this particular method over others you considered?
The 'examine every possible move' algorithm seemed obvious, it was a
question of modifying it to run in a reasonable time and still produce
reasonable results.
I did have an idea for a better algorithm, to recurse a number of levels
to produce a more accurate value for each possible move, however this
didn't in practice produce better results :-(
++ Was this POTM too difficult?
Seemed about right to me, there was no obvious (to me!) method of producing
a perfect result for every possible board, so the challenge of the best
approximation in a limited time was quite interesting.
++ COMPANY?
<18th April - Uniplex Ltd.
>21st April - Transtech Parallel Systems
LOCATION?
Hemel Hempstead
JOB?
Computer programmer.
<18th April - Unix applications.
>21st April - Low level embedded.
DO FOR FUN?
Programming, Cooking, Gardening, Reading, Music.
INNERMOST SECRET?
POTM IDEAS?
I have heard of a game for many players where everyone picks a number
(positive integer), and the player with the lowest unique number wins,
though perhaps this is more of a psychological game than a computational one.
=================================================================
============== 20 ====================== SuperPeggy =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
SuperPeggy 20000686 1 9999999/0 688/1 9999999/0 gC Markus Sabadello
Sorry ... no description available for SuperPeggy
=================================================================
============== 21 ====================== centropic =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
centropic 20000763 2 9999999/0 765/2 9999999/0 C Davor Slamnig
=================
centropic was submitted by Davor Slamnig at slama@slama.pub.hr
=================
++ Please summarize the algorithm used by centropic
Ahh... It makes some random jumps, than checks whether the
new situation is better than the previous one. If it's worse,
it restores the previous situation and tries again. If it's better,
it makes some more random moves (if it can't jump, it walks)... And so
on until all the pegs but one are gone. Then it plays more games until
the time is up. Then it chooses the best game and writes it out.
++ How did you choose this particular method over others you considered?
Ahh... I didn't consider anything else, really.
++ Was this POTM too difficult?
No, it wasn't. This is the type of POTM I enjoy the most. The problem,
really, was something I anticipated when the PEG rules were released.
The contest became difficult because initially the focus was on
efficient jumping, and then it shifted to efficient walking (maze
solving). Most of my program deals with walking, really.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Self-employed programmer, writer, composer. What I do for fun is what I
do for money, mostly (and vice versa).
=================================================================
============== 22 ====================== I_too_ran =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
I_too_ran 20001079 2 1081/2 9999999/0 9999999/0 c Sagar Vinnakota
=================
I_too_ran was submitted by Sagar Vinnakota at vijaya@wipinfo.soft.net
=================
++ Please summarize the algorithm used by I_too_ran
Well, I_too_ran was designed to handle the problem based on the board size.
It didn't quite work out that way :((( The main reason was that tested it on
an SGI INDY (64 MB RAM) with its 'cc' compiler. I had been fully warned
of the p/f on which the final testing is going to be done, but inexperience
did me in. Just for the sake of a mention, I_too_ran solved all the three
final boards in under 10mins on my m/c :-) Some consolation...
Now for the algorithm:
0. If a single peg is remaining on the board, stop.
1. Look at the board for possible jumps.
2. Take all jumps one by one identified in step #1
3. If no jumps found in step #1 :
3.1 If board size (nrows*ncols) greater than 600 goto step #4
3.2 If board size greater than 300 goto step #5
3.3 goto step #6
4. This step takes a divide-&-conquer approach. Here the board is divided
into 4 equal quadrants and each quarter is solved independently using
steps #1, #2, and #6 (and #5 if necessary to break a deadlock).
goto step #7
5. This step tries to compact the board by bringing all the PEGs towards
the centre of the board as close to it as possible. Then it applies
the method in step #6.
goto step #7
6. This step applies a tinkered Dijkstra's shortest path algorithm to the
board (viewed as an undirected graph of PEGs and HOLs) to find the pair
of PEGs which have min dist in the board among all the pairs. One of
the two PEGs moves towards the other, leading to a possible jump.
goto step #7
7. goto step #0.
Nothing much. Yes, had I not put some effort, the size would well have
exceeded 50K and might have got disqualified. Lucky, I was able to
manage it in 35K (overshooting ofcourse.. :-) I started the coding 50hrs
before the deadline and had only 5hours of sleep from that time till the
deadline. Many a time I thought I'd stop there and send it off, but a
new idea/optimization would strike, and lo.. one more long session...
Misha Dynin's 'Pegasso' should have snatched the procrastinator's award
from me by only by a whisker ;-))
I couldn't believe it, when I saw the source code size of hiqqup.c by
Warren Montgomery. Cheers to him...
++ Here's what I hated (and loved) about this POTM's scoring:
Believe me, the POTM gave me some of the best times I ever had as
a programmer. Other than the initial confusion regarding scoring,
it was good. But, a small suggestion : May be the scoring can be a
weighted sum of speed, source code size and anything specific to the
problem
e.g., score == 0.5*(1/time) + 0.1*(1/codesize) + 0.4*(#moves - nPEGs)
The weights also can be problem specific.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I did my undergraduation in Comp.Sc last year. I'm working in WIPRO Ltd,
India's top IT organization, as a Software engineer. Happened to see POTM
site one night while browsing the web for programming contests. From then
t'was fun all the way. No secrets !-) What else.... waiting for the next
POTM to send my killer entry ;-)))))
=================================================================
============== 23 ====================== rodeo =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
rodeo 20001166 3 9999999/0 1168/3 9999999/0 AWK Ed Shipley
=================
rodeo was submitted by Ed Shipley at enshipley@attmail.att.com
=================
++ Please summarize the algorithm used by rodeo
The algorithm jumps wherever possible, and moves unjumpable pieces toward the
middle where they hopefully meet up with other pieces that need to be jumped.
++ How did you choose this particular method over others you considered?
Anything else was beyond the complexity I wished to implement
++ Was this POTM too difficult? Not really - I just didn't have enough time to
work on it. Actually, I wanted to get my teenager involved, and it may have
been too difficult for him, although I think the real reason is that he didn't
want to be dragged away from Diablo. The need to find a path to the middle
complicated things quite a bit, and I'm sorry your scoring algorithm didn't
include a non-infinite score if one didn't erase all but one token. A very
fast program that got almost all the tokens then would have had a chance.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T;Middletown;Global Systems Engineering;Did for fun;Don't get personal!
=================================================================
============== 24 ====================== Lookin_for_home =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Lookin_for_home 20001394 2 9999999/0 1396/2 9999999/0 gC Richard Taylor-Kenny
Sorry ... no description available for Lookin_for_home
=================================================================
============== 25 ====================== Silly_Pegs =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Silly_Pegs 20002605 0 9999999/0 2607/0 9999999/0 gc Greg Czajkowski
=================
Silly_Pegs was submitted by Greg Czajkowski at gczajkow@students.uiuc.edu
=================
++ Please summarize the algorithm used by Silly_Pegs
I didn't get a chance to spend much time on this and used and algorithm
which starts in the middle and starts making moves toward the center.
It will make as many jumps as possible before making any moves.
Then it will make a move toward the center and then trying jumping
again.
++ How did you choose this particular method over others you considered?
I tested several methods this seemed to work best for the first puzzle board.
++ Was this POTM too difficult?
It wasn't difficult but I didn't have time to figure out how to use
recursion or a backtracking algorithm
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
University of Illinois, Sophmore
=================================================================
============== 26 ====================== Bozo =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Bozo 29999997 0 9999999/0 9999999/0 9999999/0 c Scott McCord
=================
Bozo was submitted by Scott McCord at Scott_McCord@notes.ymp.gov
=================
++ Please summarize the algorithm used by Bozo
1) Bozo finds the spot on the board that is furthest (Manhattan
distance) from the center AND is NOT boxed in so much by no-play
areas that jumps are impossible. That is, it finds the furthest
spot from the center where jumps are POSSIBLE. We'll call this
spot "A".
2) Bozo moves all pegs as far away from "A" as possible using only
walks.
3) Bozo repeatedly finds the closest piece to "A" and walks it to
"A". When a piece gets next to "A", a jump may be possible. If
so, that jump is done. Whenever a piece gets to "A", Bozo finds
the next closest piece and walks it toward "A". This is done
over and over until one piece is left.
4) When one piece is left, it is first walked to the center and
then walked to the spot on the board that is the furthest
(Manhattan distance) from the center. We'll call this spot "B".
Note, "B" might be different than "A" - "A" requires jumps to be
possible, "B" does not.
5) Bozo waits for the 10 minutes to expire and exits.
++ How did you choose this particular method over others you considered?
I was just clowning around.
Actually, at first I thought there would be no board that Bozo
couldn't solve. I've since discovered that there are some that it
dies on. I hope Fred doesn't put any of those in the finals.
++ Was this POTM too difficult?
No.
COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for TRW in Las Vegas Nevada. I write business database
software. For fun I like to go anywhere that is not in Las Vegas. My
innermost secret is that I'm really a lesbian. Sorry, I don't have
any POTM ideas right now.
=================================================================
============== 27 ====================== Jumpy =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Jumpy 29999997 0 9999999/0 9999999/0 9999999/0 JAVA Oliver Enseling
Sorry ... no description available for Jumpy
=================================================================
============== 28 ====================== PEGGAB =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
PEGGAB 29999997 0 9999999/0 9999999/0 9999999/0 C Gabriel Gambetta
================
PEGGAB was submitted by Gabriel Gambetta at gabriel@thepentagon.com
================
++ Please summarize the algorithm used by PEGGAB
------------------------------------------------
I tried several algorithms, but no one worked in the test machine. They
worked fine in my machine.
The first algorithm I tried was quite simple : jump (to the center) this
way : XXO -> OOX. When no more jumps were possible, do ONE move and re-start
the process (jump again)
I solved the first problem in 49 steps. So I started optimizating what
I called double-jumps : XXOX -> OOXX -> OXOO. The program searched the
board for a XXOX and replaced it by a OXOO. (Of course, I tried all
rotations and mirrors) The problem was solved in 46 steps.
I realized that it was only a particular case; I could optimize this kind
of moves :=20
X X O
XXO -> OOX -> OOO
O O X
I wrote 6 "matrixes", as I called them, and my best solution was 41 steps.
Only 6 moves wasted.
I started thinking of considering each peg as and object, tracing its path
to the center and optimizing jumps, but I never coded this because my first
program (the "49") caused a core dump in the test machine, and simultaneously
I started my 5th grade of High School (16 years old), so I hadn't enough
time to continue.
++ How did you choose this particular method over others you considered?
I tried every method I could imagine.
++ Was this POTM too difficult?
No, I think I could solve it if I spent lots of time which I actually hadn't.
It's no excuse, the FACT is : I couldn't solve it
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company : BA Cient fico 2/1, Sagrado Coraz (My High School)
Location : Montevideo, Uruguay (Somewhere in South America)
Job : I work as a programmer in a company. Custom databases.
For fun : Reading (Mainly Asimov, Markstein), listening music (Ace of
Base, Alanis, Spice Girls, Backstreet Boys), playing soccer, paddle tennis,
PROGRAMMING, writing short tales (I've won all the contests in my high
school)
Secret : If I tell, it will not be a secret anymore! :)
Potm Ideas : Anything!
=================================================================
============== 29 ====================== pegpen =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
pegpen 29999997 0 9999999/0 9999999/0 9999999/0 gc John Williams
=================
pegpen was submitted by John Williams at jwill@chromatic.com
=================
++ Please summarize the algorithm used by pegpen
Pegpen used a simple level one lookahead to search for optimal moves. The
position evaluation was based on parity and distance from center. A fall
back mechanism was used to detect and correct any cases where pegs were
being separated from the group.
++ How did you choose this particular method over others you considered?
I actually didn't consider too many. I ran out of time to work on it.
++ Was this POTM too difficult?
I was happy to find a general solution. It was hard for me to find the time
or motivation beyond that
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for Chromatic Research as a verification engineer. My family keeps
me pretty occupied, otherwise.
=================================================================
============== 30 ====================== puzzle =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
puzzle 29999997 0 9999999/0 9999999/0 9999999/0 c Alexey Zhelvis
=================
puzzle was submitted by Alexey Zhelvis at lesha@mcs.spb.su
=================
++ Please summarize the algorithm used by puzzle
I tried to minimize the weight of position. I calculated weight based on 3
parameters: number of pegs (the most important), sum of all distancies from
the center of weight of all pegs and sum of distancies from the center of board.
I looked ahead for 1 movement and choose the movement with the lowest
weight that can be achieved on the following movement.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work in Marine Computer Systems, St.-Petersburg, Russia.
=================================================================
============== 31 ====================== PegHead =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
PegHead 29999997 0 9999999/0 9999999/0 9999999/0 C Michael Karczmarek
=================
PegHead was submitted by Michael Karczmarek at karczma@ecf.toronto.edu
=================
++ Please summarize the algorithm used by PegHead
Look at how a peg could be eliminated, and evaluate all posibilities.
Pick the one with highest score, and execute it.
++ Here's what I hated (and loved) about this POTM's scoring:
The scoring was good, but I think the time taken by each program should
also be taken into account, even before the position of the last peg.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Now studying at University of Toronto. This summer I'm gonna be an
intern at Microsoft.
=================================================================
============== 32 ====================== Pegasus =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Pegasus 29999997 0 9999999/0 9999999/0 9999999/0 c Ken Bateman
=================
Pegasus was submitted by Ken Bateman at kbateman@esinet.net
=================
++ Please summarize the algorithm used by Pegasus
Pegasus uses a genetic algorithm.
Basically, the gene determines the path of a 'focus' that wanders around
the board. The 'goodness' of any particular jump is determined by three
factors. For each possible jump, the best possible jump is picked based
on the following factors:
Will this be a jump, or just a plain old move?
Will this jump leave the peg closer to the center of the board?
Does this jump go towards the focus, or is it close to the focus?
The gene is a list of delta-x and delta-y movements for the focus, plus
some perturbation of some of the constants determining the relative
importance of the three factors listed above.
The genetic algorithm takes care of finding the solutions, but it's very
non-deterministic and tends to get stuck at local maxima.
There is a lot of room for speedup in the code, mainly in the parts that
find the best jump for a particular board and focus. I never got around
to improving those parts.
++ How did you choose this particular method over others you considered?
It seemed like a good choice for very large, degenerately complex
boards. I think I would have had a better chance of being near the top
if the boards were a couple orders of magnitude larger.
Now, judging from the system tests and the timings other people have
gotten on them, I think a more exhaustive approach does best on the more
reasonable boards.
++ Was this POTM too difficult?
Maybe. But then again, I wrote a program for the odometer problem, but
didn't submit it because it didn't seem worth it. I'd rather experiment
with algorithms and tinker with data structures than try to squeeze my
source code to be as small as possible.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I live in Charlottesville, VA. I'm a lonely batchelor engineer (bet you
couldn't see that coming) who works for a major Industrial PLC
manufacturer, who does things like this for fun.
POTM ideas:
Maybe something with Soma blocks? Soma puzzles are basically
three-dimensional tangrams. The program input would be a set of
available blocks and an 'outline', and the result would be the placement
and orientation of the blocks.
Programs that solve (or count solutions for) numeric puzzles like this:
SEND
+MORE
-----
MONEY
Solving these in an arbitrary base...hmm...
*** Ed note: check out the web pages during the summer of 1994!!!
You have various amounts of N elements. You have several recipes that
dictate how to combine elements together in various proportions into
result compounds. The resulting compounds have various selling
prices. The program should, given a set of initial amounts, a set of
recipes, and a set of selling prices, find what you should produce in
order to make the most money.
=================================================================
============== 33 ====================== jumpeg1 =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
jumpeg1 29999997 0 9999999/0 9999999/0 9999999/0 gc Byon Garrabrant
Sorry ... no description available for jumpeg1
=================================================================
============== 34 ====================== tppfkam =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
tppfkam 29999997 0 9999999/0 9999999/0 9999999/0 c Mark Huizer
Sorry ... no description available for tppfkam
=================================================================
============== 35 ====================== DePegger =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
DePegger 29999997 0 9999999/0 9999999/0 9999999/0 C Kevin Kennedy
Sorry ... no description available for DePegger
=================================================================
============== 36 ====================== Leapfrog =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Leapfrog 29999997 0 9999999/0 9999999/0 9999999/0 c Kroum Savadjiev
=================
Leapfrog was submitted by Kroum Savadjiev at kroum@consulan.com
=================
++ Please summarize the algorithm used by Leapfrog
I tried to make the computer do the work for me. My algorithm was to
evaluate each possible move from a given position, and to choose the "best".
The "criteria" is function of some parameters, and i assumed that the computer
will find the optimal strategy. Unfortunately, a strategy which is optimal
for a problem is not good for another one. I did'nt found a strategy which
is universal, optimal AND fast...
++ Here's what I hated (and loved) about this POTM's scoring:
This POTM was my preferred so far. I hope that my performance will improve
in the next.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work as a programmer in Montreal, Canada
=================================================================
============== 37 ====================== JustInTime =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
JustInTime 29999997 0 9999999/0 9999999/0 9999999/0 c V. Prabakar
=================
JustInTime was submitted by V. Prabakar at prabakar@wipinfo.soft.net
=================
++ Please summarize the algorithm used by JustInTime
What you are going to hear is really fundoo stuff :) First of all,
This is not a down-to-earth algo :) If not into fourth dimensions or
time-cones, it is definitely into the three dimensions you can visualise.
Pick the centre of the board, lift the board in the z-direction and you have
a mesh of pegs and holes interconnected. My aim shall be to make the pegs
move towards the top (here the centre of the board) clearing levels from
the leaf-node level, upwards. A peg shall move to a higher level only if
it has cleared the current level in which he is, or he *cannot* clear the
current level (like say, no more jumps or walks..)
Hey, are you with me.? Now, I view it as a undirected graph. Applying
the rules for jumps and walks, a peg with the least number of edges starts
its journey upwards, giving the chance to the guy who is a level above
him, whenever he finds he cannot continue his journey upwards, wholly
trusting recursion to get his chance again to look up with hope, after a
hole has been created on top.
While I started to code my 2090A.D. algo, I did not very much
concentrate on the management of "malloc-ed" memory, which, when I now
reflect upon my inward eye, find that one can behold as the greatest blunder
by any of the contemprory programmers. As the board size kept increasing,
the number of recursive calls increase, paving way for the
'dynamic-path-building' routine to swallow heap at a steadily increasing
pace...you know what happens when a process in *NIX tries to bring about a
revolution like this.
I should admit that my code was not complete in one more aspect.
Yes, this is regarding the illegal move that 'JustInTime' had committed
in one of the test boards. But, the mistake was not of having made an illegal
but that of having not printed a move ! If you still have the source code
of my entry, you can find that the functions "Jump(Node*,enum DIR)" and
"Commit_Walk()" are the only places where I am printing out the moves made.
But, as a handler for deadlock-situations, I have a "Can_anyone_Move()" and
"Move()" function-combination, of which, "Move()" *does make a walk*. I am
extremely sorry for having been so careless. I can understand that such
things are a real-pain-in-the-neck for organisers of such events !
Anyway, at least I learnt that 'tis me who looses !
I had lost time exploring ideas and optimizations, so much so that
I dared to send the entry without the memory-freeing code-strip also, for
final perusal !
++ Here's what I hated (and loved) about this POTM's scoring:
POTM was my maiden participation in a contest on the net. Truly,
my joy knew no bounds that working at office, I got an opportunity to
re-live my college-days, night-outs and all..!
I consider it worthwhile to mention that one of my colleagues here,
who also came up with an entry (I_too_ran), actually designed boards that
are potential situations that our code cannot handle. I feel, such
situations are where judging the program should be based on the time taken
by the code, lesser number of lines of code, and the effectiveness of
the code in leading to a better board-situation, all together and not
separately one at a time. Probably a weight-function of these parameters.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Finished my Computer Science Engineering degree from the Birla
Institute of Technology & Sciences, Pilani, India.
Working in Wipro Ltd, Infotech Group, Global R&D, Bangalore, India.
-Ran into POTM, had fun, thanks a lot. I am sure it is not so far..
the day JustInTime entries are going to reign the world :)
=================================================================
============== 38 ====================== eat_em_all =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
eat_em_all 29999997 0 9999999/0 9999999/0 9999999/0 JAVA Vishal Awasthi
Sorry ... no description available for eat_em_all
=================================================================
============== 39 ====================== IveBeenJumped =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
IveBeenJumped 29999997 0 9999999/0 9999999/0 9999999/0 gC Mike Goldshteyn
Sorry ... no description available for IveBeenJumped
=================================================================
============== 40 ====================== Peggy_Got_One =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Peggy_Got_One 29999997 0 9999999/0 9999999/0 9999999/0 c Tom Six
Sorry ... no description available for Peggy_Got_One
=================================================================
============== 41 ====================== Jump_Peggie!_Jump! =============
=================================================================
3 BOARDS smiley ruler killer
ENTRY MOVES DIST MOVE/DIS MOVE/DIS MOVE/DIS PROGRAMMER
Jump_Peggie!_Jump! 29999997 0 9999999/0 9999999/0 9999999/0 gc Patrick Frants
Sorry ... no description available for Jump_Peggie!_Jump!
=================================================================