Entry Summaries

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).
Thanks to all that responded!!!

               Yalta   370 ( 23/305/ 42)  275 22 22
Yalta submitted by P.Ouvarov F.van der Plancke at 

++ Please summarize the algorithm used by Yalta

The algo consists of the following phases:
(A)  produce a set of promising initial line patterns.
(B1) "quickly" tune each of these patterns a first time, to have a good
     idea of their potential
(B2) until timeout, re-tune more accurately the best patterns issued from 
     phase (B1) or from previous run of phase (B2).

A "pattern" is a set of lines, whose topology is fixed.
Tuning the pattern means repeatedly moving lines in such a way that the 
score of the system decreases, without breaking the topology.

Choosing the initial patterns.

  It is best to avoid triangles in the _interior_ of the square. So the
patterns we consider are N x M grids that may of may not cross the given line.
Not all grids are considered: if similar patterns A and B are such that
A is "obviously" worse than B then A is not considered.

For each pattern Yalta computes the best possible score allowed by the
pattern's topology (BPS), and the expected score (EXS: a crude estimate
actually, often really far from the actual outcome.)

Patterns are tested in phase (B) by order of increasing EXS, and discarded
when their BPS is worse than the current best score.

  An optimally distorted 5x5 grid that cuts the square in pieces of area
<= 277.951 is always tested, and will provide the solution for difficult
cases like (0,1)-(1,0). (For more details on this grid see Yalta's code)

Tuning the best pattern.
  The original idea for tuning was what we called thermoalgo. Its intention
was to put the same quantity of gas into each partition (that is, polygon) and
let the lines move according to the second law of thermodynamics (it states 
that the pressure of the gas with constant temperature in an isolated vessel 
is inverse propotional to its volume: P = k/V). 
  But then we decided to simplify the algo and implemented a variant of 
gradient descent. For the specified line we found the 8 most close
lines-candidates, and calculate the score of the system moving the line in
turn to each of its candidates. The candidate with best score was considered 
the best. After we had found the best candidates for each line in the
pattern, we made one step of tuning, moving the lines to these candidates. 
Further we discovered that it would be faster to choose the candidates 
randomly, check the score and if it decreased make a step. 
We call this method random_tune and it is now our main tuning method.
(Most of the time, tuning_main just calls random_tune).

Tuning: the scoring function.
  We quickly learnt that the MaxDiff function (so we call 
f:=(max_area-min_area)) is a bad function for tuning.

Why? The reason is that this function is very short-sighted, that is, it
just acts on min_area and max_area, but it doesn't try to modify areas 
_between_ maximum and minimum.

We understood that we must use the other function to minimize MaxDiff. The 
idea was to find a function that tries to make _all_ areas equal, and thus 
minimize MaxDiff as much as possible. And so we tried the root-mean-square 
function (without the square root which is useless for comparison): 
    SqDiff:=sum_i [(area_i - mean_area)^2], 
where area_i is the area of the i-th polygon. 

We later replaced 2 by an exponent k that increases while tuning 
a given pattern; and we replaced mean_area by 
    middle_area := (min_area + max_area)/2. 

So our last scoring function is:
    ExpDiff_k := sum_i [ |area_i - middle_area| ^ k ]

The trick is that when k increases, the optimum(s) for ExpDiff_k should 
approach the optimum(s) for MaxDiff.

[Frederic: I was not able to prove anything of the kind - any hints are welcome.
I haven't tried too hard so the problem may be easy.
The property is false if 'middle_area' is replaced by 'mean_area': at best,
the approached optima are those of max_i[ | area_i - mean_area | ].]

[note: in the program, k is represented by vmExp, with k = 2^vmExp]

Tuning: strategy against local minima

  In process of tuning the specified pattern with the specified 
scoring function, there is a moment when the system is stuck and 
doesn't want to be tuned any more. But this does not mean that Yalta 
optimised the scoring function. Yalta could be stuck in a local optimum,
that is, no move of the lines to close lines leads to a score 
improvement (or the program failed to find such a move).

To escape such minima Yalta "shakes" the pattern in the hope 
that further tuning will yield a better local minimum. 
"Shaking" is actually just moving the
lines randomly - but to farther lines than for ordinary tuning.
("Shaking" is done only in phase (B2).)

After a fixed number of "shakes", we replace k by 2*k it and re-tune 
the pattern for the new scoring function ExpDiff_2k. 
When k is high enough, ExpDiff_k is replaced by MaxDiff.

[Frederic] I hope this summary was not too long ;-)

++ If I had it to do all over - here's what I would try ....
We would never try to use long double ;-)
(Using long double made our program to be 100 times slower on Fred's machine
and it was a real headache for us to find out why...)

++ Please explain your program name: Yalta
	This name was suggested by Frederic. I can quote one of his 
	early mails to me: "I thought of a name for our entry. 
	I hope you don't mind the pun: "Yalta" ... where the 
	world was divided in "East" and "West" in 1945.

[Pavel]  I leave in Russia, in the science town Protvino near Moscow.
[Frederic] I live in Belgium (Brussels). 

+ Do for fun? [Pavel] Cinema. Politics. Also friends and beer :=)
[Frederic] Minesweeper (too much). Drawing. Programming.
   (talk of being funny ;-)

+ Do for work? 
   Programming on Unix systems (drivers, neural networks). But I
   began working only three months ago.
   Windows programming ... this team is mixing water and fire ;-)

+ Innermost secret? [Pavel] I'm a Martian. [Frederic] me too ;-)

+ POTM ideas? 
[Pavel] Why not provide photos of winners along with their codes?

[Frederic] "TRON"

              Mikado   383 ( 23/318/ 42)  287 18 22
Mikado submitted by K.VanBael W.Fransen at kris.vanbael@barco.com
++ Please summarize the algorithm used by Mikado

	[Van Bael, Kris]  Looking at the problem in floats, the total
searchspace has lots of discontinuities and local minima, so we divided it
in 'topologies'. What we call a topology is a single way of intersecting and
forming polygons without considering any coordinates. The first big part of
the work consisted in a backtracking topology-creator, returning billions of
valid topologies. For each topology we quickly (greedy) make an initial
instance. Then an iterator is executed, using 'forces' between the polygons.
Small polygons try to push its borders away, while big polygons try to
attract its borders. This is combined with a round-off routine, finding the
nearest integer solution for every line. Near the end of a good candidate,
we do some random kicking to find near-optimal float-solutions (with a
better score after integer-round-off).

	By looking at the returned solutions, we derived a set of heuristics
(in order to find a 10-line solution before the end of the world). One about
the number of polygons on each side of the given line was very succesfull.
The biggest boost however was achieved by limiting interiour polygons to

++ If I had it to do all over - here's what I would try ....

	[Van Bael, Kris]  After the heavy heuristics, the topology creator
seemed a bit too general. Next time we will try to invent a time traveling
machine and spy on VanderPlancke's entry ;-).

++ Please explain your program name: Mikado

	[Van Bael, Kris]  That one is pretty obvious, I suppose. It's a game
of skill with wooden sticks lying randomly on top of each other.

	[Van Bael, Kris]  We live in Belgium and eat chicken with Coca Cola
nevertheless, giving us 7 fingers on each hand.

              JigSaw   389 ( 24/323/ 42)  287 20 22
JigSaw submitted by Andrew Gauld at andrew.gauld@att.com
++ Please summarize the algorithm used by JigSaw

Try a collection of methods, and report the best answer found.  Methods are:
- Fixed 6x6 grid
- Fixed 5x5 grid
- Fixed 5x7 grid
- Dynamic 3x4 grid with diagonals
- Non-intersecting lines
- Line bisecting both original pieces and lines only intersecting bisection line
- Various dynamic grids based on successive approximation
- Horizontal line with divided top corner piece and vertical stripes
- Horizontal line with vertical stripes
All methods are applied after original line is rotated/mirrored to a "normal"
position (trying to get the smaller piece in the bottom left corner).

++ If I had it to do all over - here's what I would try ....

Don't know.  I did the best I could.

++ Please explain your program name: JigSaw

It slices a square into a lot of funny shaped pieces like a jigsaw puzzle


           Glamdring   441 ( 50/349/ 42)  286 12 11
Glamdring submitted by Michael Strauch at michael.strauch@cityweb.de
++ Please summarize the algorithm used by Glamdring

The two important parts of Glamdring are
  a) the scorer
  b) the optimizer.

a) The scorer uses a simple "divide-and-conquer" technique for finding all
polygons the square splits up to. It takes a polygon (at the beginning: the
complete square) together with a list of cutting lines, then splits the
polygon recursively into two new polygons p1 and p2 using the first cut and
decides for each of the remaining cuts whether it meets p1, p2 or both, so
adding the cut to the corresponding lists.

One of the main speed-ups for the scoring was to maintain the list of all
intersections of all cuts whenever a cut is added to or removed from the
square. Other speed improvements where made by using static memory
management whereever possible.

Thanks to George Papoutsis for his nice Postscript drawing program. In his
program comments was a very helpful hint to comp.graphics.algorithms.faq how
to calculate the area of a polygon from its vertice coordinates.

b) The optimizer consists of two parts, a "local optimizer" and a "global
optimizer". Both of them use a so-called "threshold accepting" algorithm (a
simplification of the better known "simulated annealing"). The general idea
(when you look for the smallest score) is:

  1. Choose a starting configuration C and a positive threshold T.
  2. Modify C randomly a little bit, giving a new configuration C'.
  3. If Score(C')<=Score(C) + T, set C:=C'.
  4. If there is no score improvement "for a long time", decrease T
  5. If T>0, goto step 2.

The "local optimizer" only changes the position of one randomly chosen cut
line slightly, without adding or removing a cut. The starting threshold and
the speed of decreasement are parametrized. In most cases, running the local
optimizer does not change the number of pieces.

The "global optimizer" adds, removes or changes one line completely
randomly, then it runs the local optimizer for a short while. The idea is,
that the global optimizer produces different topologies 
(thus different number of pieces) of the cutted square, whereas the 
local optimizer tries to find the best score for a given topology.

Putting it all together, the complete algorithm works as follows:
- Choose heuristically a starting configuration (Glamdring adds some
  parallels to Fred's first cut)
- run the global optimizer until 6 minutes are over (to use the time
  completely, Glamdring does not only decrease the threshold, but it increases
  it if there was no accepted modfication "for a long time" at all)
- use the remaining time to run the local optimizer on the best found
  configuration so far.

++ If I had it to do all over - here's what I would try ....
- Look for some better heuristics for choosing the initial cuts.
- Try to find a better heuristic to distribute the calculation time between
  the different parts of my algorithm
- Try to rewrite the complete scorer using a sweep line algorithm to see
  if this gets faster.

++ Please explain your program name: Glamdring
Glamdring is the name of Gandalf's sword in Tolkien's "Lord of the Rings".
Why do you need a powersaw if you have a magic sword :-)?

- Germany. POTM. Software Engineering.
  Well, it wouldn't be a secret any more ;-).
  No good ideas at hand, but if I have one, I will send it to the POTM master.

           SawOMatic   710 (101/573/ 36)  441 4 10
SawOMatic submitted by Dan Gehlhaar at gehlhaar@agouron.com

++ Please summarize the algorithm used by SawOMatic

  I used an evolutionary algorithm, starting with randomly placed
  lines, and using a mutation that moved, added, or deleted lines.  I
  made use of an excruciatingly simple, 1-D gradient search that was
  applied at strategic intervals.  Each run took on the order of 20-30
  seconds; I did as many runs as could fit in the allotted time.

  At a friend's suggestion, I used a different scoring function than
  the "official" one, for the search.  The official scoring function
  discards all of the information contained in all but the largest and
  smallest polygons.  He recommended that I try the sum-squared
  deviation from the theoretical average size (10000/N, for N
  polygons).  This has the same minimum, but a much better-defined

++ If I had it to do all over - here's what I would try ....

  1) Start earlier!!!  That scoring function was, er, "challenging",
     and didn't leave me much time for too much other experimentation.

  2) Take advantage of more "knowns", like that lines should probably
     tend to be parallel or perpendicular to the given line, and that
     they should be spread out.  Also, I'm sure that there are plenty
     of other heuristics that I ignored, due to lack of time.

  3) Search the space more uniformly.  I chose "random" starting lines
     based on just picking coordinate pairs.  This strongly biases 
     solutions towards the diagonals (by about a factor of two).

  4) Devise a better gradient search.  The one I used usually didn't
     do much.

++ Please explain your program name: SawOMatic

  I had to settle for "SawOMatic" because "Yalta" was already taken.


  I live in San Diego, CA, and work as a computational chemist for
  Agouron Pharmaceuticals.  For fun, I do karate, dancing, watersports,
  and various other diversions.  

  POTM ideas: I guess it's tough to get away from "optimization"-type
  problems, because you have to score the results.  I have a strong
  interest in adaptable systems, so I would be interested in controller-
  type problems.  I'll send you mail if I think of anything specific.

            iron_saw   801 ( 29/756/ 16)  712 12 22
iron_saw submitted by Ionel Santa at ionels@phobos.cs.unibuc.ro
++ Please summarize the algorithm used by iron_saw
My main idea was to create a mechanism that would make the cutting lines
arrange themselves. In order to do this, I have imagined the cut pieces
to be filled by gas which moved the cutting lines under its pressure. 
The force which acts upon a piece border was proportional with L/S, where:
L = the length of the border
S = the area of the cut piece
The lines, which are a sum of border segments, move acording to the 
resulting force and spinning moment. This is what I  will call a 
relaxing process.  Another idea was that, if I wanted to minimize the 
score and the first two
pieces have the areas S1 and S2, I must tend to cut these two pieces in
n1 and n2 parts, where abs(S1/n1 - S2/n2) is minimum.

The algorithm:
(1) I choose some initial cut designs, start the relaxing process and I
select the best resulting design, which is usually stable regarding the
relaxing process.
(2) From the cut design which results from (1), I obtain other stable
configurations by selecting a line L0, gradually spinning that line, and 
applying a relaxing process, but blocking L0 from spinning (the spinning 
moment has no effect on it). However the line  L0 is free to translate.
(3) I choose the best stable point from (2), and I try to improve the 
score with succesive random perturbations and improvements.

Remark : for the step (3) the improvements are made by trying to 
slightly move the line endings and see if there is any improvement 
or not. Also for steps (1) and (2) I work with lines of the 
form (a*X + b*Y = c, where a, b, c are real numbers), for the 
step (3) with lines of the form required by the final
solution (passing through two points of integer (between 0 and 100)

++ If I had it to do all over - here's what I would try ....
I would choose more carefully the first cut designs; it seems that a mistake
on this point made me score so lowly at the SLIVER-CUT test. However I think
that I could have done better at the other steps of my algorithm, too, but
the cruel Fate made me get a job just two weeks before the deadline and I
hadn't enough time to further improve my program. The good part was that I
got free access to the Internet again.

++ Please explain your program name: iron_saw
When I first named my program, I thought of a series of programs like
brass_saw, iron_saw, steel_saw, etc. Then, realizing I had no time to improve
the iron_saw program, I left it like this (also I realized that Iron_Saw
contains my initials and I thought this could bring me luck).

1) Bucharest, Romania.
2) Programming/mathematics, reading, hiking (unfortunately not too often).
3) Programming.
4) I don't know it myself.
5) A game called five in line: The players are trying to mark five
consecutive squares (in diagonal, vertical or horizontal) on a grid table.

          Bobbittize   891 (266/583/ 42)  287 4 41
Bobbittize submitted by Randy Saint at saint@phoenix.net
++ Please summarize the algorithm used by Bobbittize
The heart of the algorithm is a Genetic Algorithm (GA) that tunes a set
(population) of solutions to incrementally improve the best solution.  Each
generation, half the population is destroyed and new ones are created by
"breeding" a pseudo-randomly selected pair of the remaining members
(favoring the better members).
I found that this was quite susceptible to getting trapped in local minima.
I tried different forms of "nudging" or cross breeding with randomly
generated initial members to try and get it out of the rut and more towards
the global minima.  Nothing worked.  So I settled on cycling through as many
runs of the GA as possible and hoping that eventually I would find a "pretty
good" local minima.
The change that improved my algorithm the most was seeding the initial
population with better members.  I generate one member that tries to draw
somewhat parallel lines to the original in order to create the even-area
cuts.  This was done by comparing the areas created by the initial line with
even areas of dividing the square by 3, 4, 5, ..., 12.  Then I would know
how many lines to draw, and on which side of the original line.  The GA
usually takes this member and tweaks it until it is improved and stabilized.
This usually produces the best answer, except for slivers and tiny initial
cuts.  I also generate another member that has a 6x6 square grid.  This
usually comes up with an answer around 275 to 288 for initial cuts that are
slivers or tiny areas.  I also tried a few other "patterns", one of which I
left in.
On the 3rd Final board (950) the 6x6 grid "took over" the population so the
solution came out as 266, even though the "parallel lines" method was
tweakable down into the 60-70 range.
My area evaluation routine creates polygons somewhat recursively.  I add new
lines to a board one at a time.  Each line is passed to each polygon.  If
the line intersects the polygon, (thus creating two polygons) it updates
itself with one of the new polygons and returns the other, which is added to
the list of polygons.  After all lines are added, then the board is done and
we calculate the max and min areas for the polygons.  This method does not
lend itself to changing the lines after they've been created, so each time I
wanted to update a line I would generate a whole new board.  This was not
ideal, but it seemed fast enough for my purposes.

++ If I had it to do all over - here's what I would try ....
I wanted to figure out some GA evaluation function (instead of Max - Min)
that would be smoother and less susceptible to the local minima problem.
This would allow the GA to find the global minima easier.  Unfortunately, I
couldn't find one.
Another step would be to only seed each population with one type of seed.
This way each seed would have its chance to be "tweaked" to its best
possible solution.  (If I had done this I would have been 5th.)

++ Please explain your program name: Bobbittize

This comes from one of the most infamous instances of "cutting" in recent

++ WHERE DO YOU LIVE?  Houston TX,
DO FOR FUN? Programming Contests, Reinstall Linux (~8 times until I figured
out I had a bad IDE controller),
DO FOR WORK? Develop software at NASA-JSC for planning Space Shuttle and
International Space Station flights.
INNERMOST SECRET? Some POTM I hope to submit an entry that doesn't have to
take the whole 10 minutes to try to find an answer.
POTM IDEAS?  We haven't had a Head-to-Head type POTM in a while.

Hofstadter's Law: It always takes longer than you expect, even when you take
into account Hofstadter's Law.

            Messer37   986 (263/683/ 40)  285 40 40
Messer37 was submitted by Paul Grayson at pdg@mit.edu

++ Please summarize the algorithm used by Messer37

Basically, my strategy is to start with a (hopefully) good guess
and anneal it towards a good score.  This program can calculate it's
own score, using a very fast scorer --- under gcc without optimization
flags on a P166 it scores a random 10-cut board in 2.5ms / 240k boards
per 10-minute game (if compiled with -DPRINTFINALSCORE it will brag
about its speed at the very end).  It also occasionally tries to
maximize the size of the smallest polygon, to get out of some common
bad configurations.

++ If I had it to do all over - here's what I would try ....

...making the code less messy so I could implement some more beautiful
optimization algorithm!  ...One thing that I thought about for a while
was trying to make three lines intersect in a single point.  The
ability to eliminate those annoying tiny triangles would've really
helped me out, but I didn't have time to think it through.

++ Please explain your program name: Messer37

Messer = knife in German, and the algorithm is pretty messy...see
http://www.mit.edu/afs/athena.mit.edu/activity/d/dom/www/37/ for some
more of my inspiration.


I'm a student at MIT, studying physics + math, live in the Russian
house, a truly wonderful product of MIT's excellent housing system...
I have a homepage: http://baa.mit.edu/


          LumberJack  1024 (151/841/ 32)  571 12 10
LumberJack submitted by David Mishelashvili at Dati@altavista.net
++ Please summarize the algorithm used by LumberJack

   Scoring system: is based on the polygons calculation that uses 
 some techniques from Algebra - Geometry (such as vectoral multiplication).

   Optimisation Method: each cut is presented by two points that 
 besides on the rectangle [0, 0, 100, 100] (so one of the coordinates,
 X or Y is 0 or 100, and another is >=0 and <= 100).

     1. We have some fixed cuts and have also the cut that we want to 
	optimise. this cut has two points, we can move each point in 
	three direction (-, 0, +   ==  move against clock arrow, 
	don't move, move according clock arrow) by some step 
	(for wxapmle 1 or 0.01), of course (0, 0) is the same position;
	then we try to do all moves and choose the one that improves 
	the score in the best way. we repeate this action until 
	dead point, which is local minimum.

     2. We have several cuts on the board and we want to optimise 
	all of them. To do this, for each cut (and making all other fixed)
	we repeate (1) again and again until the system comes to the 
	dead point, in other words after this procedure there 
	must not be any cut that we can optimise.

   Generating starting cuts: (that we optimise using algorith 
described abow, and choose the best one) the first cut divides the 
sides in 6 logical pieces (if first cut touches points [0, 0] 
[0, 100] [100, 0] [100, 100] then number of pieces is less than 6, 
but we can to move this cut a little, that doesn't reflects 
much on the score), we choose some sencetive compinations of 
them and make various number cuts from one piece to another.

++ If I had it to do all over - here's what I would try ....

   Good converot from float cuts to integer. (Actually this was my 
first contest, the problm was enaugh solid (but not interesting 
from algorithmical point) and the only goal of mine was to get 
some practice in POTM and to be somewhere up on the leader board)
++ Please explain your program name: LumberJack

   Name for my entry was suggested by Paul Banta, so ask him to explain ...


   I Live in Georgia (not USA!); I'm a student of computer 
science department at the Tbilisi State University; 
My age is 20; My goal of life is (from the time when I write my 
first program for MK-52) to became The Best Programmer Of The Planet,
and I think that POTM is good starting place for it...

              planit  1062 ( 74/976/ 12)  857 12 11
planit submitted by David Lynch at dflynch@att.com
++ Please summarize the algorithm used by planit

Calculate the area to the left and/or under the initial cut, determine the
percentage of the total area, and convert this area into the closest
fraction with a denominator no larger than 12.  Using the denominator (D) to
determine the number of cuts, make additional cuts parallel to the initial
cut such that each section has approximately 1/D of the total area.

This approach breaks down when the area under the first cut is significantly
less than 1/12 of the total area (e.g., "sliver").

++ If I had it to do all over - here's what I would try ....

Ideally, I would consider a variety of cutting strategies and choose the one
that produced the best score.  But that would require more time to develop ...

++ Please explain your program name: planit

planit is a contraction of "plan it", meaning to plan before you cut.  It
also looks like the woodworking term "plane" and sounds like the word "planet".


I live in Freehold, New Jersey, where I enjoy music, reading, running,
sailing, and woodworking.  Right now I'm coaching a 4'th grade boys'
recreational soccer team.  When I have time, I work on network design
projects for AT&T Labs.

Has anyone ever revealed an "innermost secret"?

      Texas_Chainsaw  1135 (269/824/ 42)  287 44 41
Texas_Chainsaw submitted by Davor Slamnig at slamnig@sepia.ocn.ne.jp
++ Please summarize the algorithm used by Texas_Chainsaw

Writing the scorer used up most of my POTM-energy; the actual cutting algo
just divides the board into 36 rectangular pieces (plus any pieces that
result from the initial cut). Then the cuts are wiggled around randomly as
long as the time limit allows - the scorer decides when an improvement is

Still, I seem to have made top ten, although other people evidently used
much more intelligent approaches. This probably just proves how difficult
this POTM was.

++ If I had it to do all over - here's what I would try ....

Something much more intelligent.

++ Please explain your program name: Texas_Chainsaw

There is a movie, "Texas Chainsaw Massacre", presumably about people
cutting up each other with chainsaws in Texas. I've never seen it, though.
Probably wouldn't want to see it.


Zagreb, Croatia - Drink and/or play guitar - Program for a small Japanese
company - ... - ...

        SocialistSaw  1145 ( 50/1073/ 22)  989 4 11
	Sorry ... No questionairre was returned for SocialistSaw

          LatticeSaw  1163 (275/846/ 42)  285 45 41
LatticeSaw submitted by Franz Mauch at Franz.Mauch@t-online.de
++ Please summarize the algorithm used by LatticeSaw
It's a static solution, almost a lattice, twisted a little against
the square, to give more equally distributed areas.

++ If I had it to do all over - here's what I would try ....
The same. 

++ Please explain your program name: LatticeSaw
See above. 


Germany. I find it really challenging to solve problems and competing
in this. 
Franz Mauch    http://www.mathe.uni-konstanz.de/~mauch/

        Black+Decker  1173 (278/853/ 42)  287 45 41
Black+Decker submitted by Vasudev Seeram at cavalier@tstt.net.tt
++ Please summarize the algorithm used by Black+Decker

1. Summary of algorithm:
The program that I submitted just drew five horizontal and five vertical
lines across the square, thus dividing the square into 25 (or more parts). 
for (i = 1; i <= 5; i++) {
    j = i * 100 / 6;
    drawLine (0, j, 100, j);
    drawLine (j, 0, j, 100);

++ If I had it to do all over - here's what I would try ....

HOWEVER, that wasn't the real program I was working on. I just sent in that
program to enter the contest. Trouble is, I never actually finished the
real program, so I never sent it in. Anyway, it was going something like
1. Determine the size of both partitions (P1 & P2) that are created when
the input line is read. To do this, determine the points of intersection of
all lines. Determine which points are adjacent to which on the lines.
Isolate the points that form an enclosed polygon. Get area of this polygon.
2. Reduce ratio of partitions to integrals (P1 : P2 :: R1 : R2)
3. Determine required number of polygons to give the best answer.
4. Draw lines across the square (some of the lines are parallel, some
5. Get the score from this arrangement.
6. Rotate and move lines until best score is found.

I finished up to the scoring, but not drawing the new output lines. Was fun
though, felt like I was researching for a Ph.D. (BTW, I currently have only
my BSc).

a. Finish the program and submit it on time.
b. Use a neural net. Beats me how that will help. But I figure that the way
of getting the 'best' answer is not a straight forward step-by-step
algorithm. Something fuzzy could be used.

++ Please explain your program name: Black+Decker

I could understand the first question. I could understand the second
question. This one is a toughie. I guess the name is funny. Probably kinda
macho. It's like, we have problem to cut up a piece of wood, and I'm
Black&Decker baby! More like a wannabe carpenter. I was looking for a
really really funny name, not some goo goo gaa name. I submitted the stub
program to just reserve the name, I had started to worry that someone would
take the name!


Now THIS is a tough one. The fun part, that is, I know where I live. I live
in Trinidad (as in Trinidad and Tobago, not as in Felix Trinidad). We
hosted the Miss Universe either this year or last year (I wasn't paying
attention). Life is pretty ok, no real complaints. No really mortal danger
(like Serbia etc.) A really homey place.

What do I do for fun? This is really hard, like the question 'What was the
happiest moment of my life?' These days I am working overtime: get up, go
to work, come home, sleep, ad infinitum. However, I do like (when I get the
time) to read, cook, play computer, entering programming contests (p.s. I
am male). I have to start exercising, my lack of exercise is beginning to
show (around my belly). The company has a small pool, I will join the club
and start going there lunch times. My boss might get a little pooped, and
wonder if I am happy or something.

I am a programmer analyst, working on an IBM ES/9000 mainframe. We are
currently working on our Y2K project (get this: Sept 1999 and we are
working on this god-forsaken project). IBM said that the mainframe is
running on borrowed time (and our department manager asked, "What does that
mean?") We are struggling to get all of the data off before next year
(when, we assume, the mainframe will really stop). Last week, we had a
meeting for the contingency plan. Well, to make a long story short, they
will be doing the payroll for 10,000 employees manually. I think I am going
to switch careers to dentistry come Dec, 31st, 1999. On the bright side,
though, we might get to write our own cheques next year. Wuppee doo.

In addition, my mother wants to take a trip next year. Me? I'm gonna learn
how to use a fire extinguisher and keep it in the car. Besides that, I'm
not worried: the bomb shelter is already stocked with food and I have all
the old reruns of Happy Days (ok ok, everything that I just said that was a
joke was a lie, big deal).

Innermost secret?
Now why would you wanna know my innermost secret? I don't know what that
could be, my innermost secret that is. Maybe that romantic love is a lie,
is a lie, is a goddamn lie! 'Love' is a genetically programmed lie that
ensures the continuation of the species by tricking us into marriage. Yeah
yeah, she liked someone else, the guy was a moron, man!
  But it's still a lie. How many romantic relationships really last? The
passion dries up like flower in summer heat. And then once more, we are
left all alone, wondering what happened, and why it happened.
  Traitors. Treacherous traitors. I will never trust a pretty face. Maybe I
should marry someone ugly. Maybe I shouldn't even marry; maybe I should
just become a playboy. Then why do I walk this path, the straight path,
'the road less traveled'? The path of pleasure is a dark and dangerous
path. But it is a seductive path, where many are lured, but none have
returned. I walk the razor's edge between good and evil.
  There is an eternal battle in my soul: The Man vs. The Beast. The face of
Man is scarred and covered with blood. The face of the Beast is that of a
maiden. The Man must not fall. But the Beast cannot die, cannot be killed.
The Man lives in my head, the Beast in my heart. And as long as I continue
to feel, the Beast will persist.
  I wonder what it would be like to have my brain wired with NAND gates?
Computers cannot feel, and will never feel in the true sense of feel. Not
merely responding to input like programs, but genuinely feel. They cannot. 
  I wish someday I will meet someone who will prove me wrong. Maybe
reprogram me. Purge this faulty logic. Prove me wrong that women can be
trusted, and that there are more than two kinds of women (the frigid moral
kind and the passionate boorish kind).

  I don't know if I will ever trust.

Until then, I walk alone. Cold, calculated and emotionally distant. Bond.
James Bond.

POTM Ideas
Well, no ideas now, but have you ever checked out Dr. Dobbs Journal? There
is a column about some Dr. Ecco guy who solves programming programs. Most
of the problems (that I have seen) involve some sort of topological sort,
sorting by all sorts of precedence rules. It may give you some ideas,
though topological sort is much easier in comparison to Powersaw.

Well, laters then, Fred my Freudian Friend, (<- hey, that rhymes!)

Vasudev Seeram

            SawItOut  1173 (278/853/ 42)  287 45 41
SawItOut  was submitted by Denis Konovalchik at denisk@compassplus.ru
> ++ Please summarize the algorithm used by SawItOut

Maybe, the listing of my program will do it better:

const int delta[] = {17, 17, 16, 16, 17};
void main() {
   int offset = 0;
   for(int i=0; i<5; i++) {
      offset += delta[i];
      cout << offset << ' ' << 0 << ' ' << offset << ' ' << 100 << endl;
      cout << 0 << ' ' << offset << ' ' << 100 << ' ' << offset << endl;

Really, it's the shortest program I ever sent anywhere. I wonder the great
place it won at this time. Maybe, the concentration of mind in every line of
my code at this time was high as never before ;)

++ Please explain your program name: SawItOut
My best willing after reading the task was to saw it out as quick as


I live in the Magnitogorsk city, Russia. My job is C++ programming in the
Compass-Plus firm (www.compassplus.ru), specializing in the electronic pay
systems and e-commerce.
I also like to publish different papers about computers in the "Computerra"
magazine (www.computerra.ru, sorry! it's in Russian only). Sometimes I
compose humouristic poems and publish it via Internet.
I would like to find some friends abroad and to exchange e-letters with

Thank you for great problem and thank the winners for the showing the way
how to solve it. I appreciate the internetional team as the greatest idea of
all POTM history ;)

                bzzz  1173 (278/853/ 42)  287 45 41
bzzz submitted by Bob Ashenfelter at RAshenfelter@submarinesystems.com
++ Please summarize the algorithm used by bzzz

	If initial cut comes within one unit of the center,
		output initial line rotated 90 degrees.
		output a 5x5 grid of horizontal and vertical lines.

   This program was submitted in the first week to get on the list.  It
   was not intended to be my final entry but it was (see below).  The fact
   that such a trivial program managed a three-way tie for 12th out of 44
   entries says more about the problem than my solution.  This was one of
   the hardest POTMs ever and there were very few serious entries.  It was
   also a very good POTM problem in that no specialized knowledge was
   needed beyond the ability to program and the ability to think clearly.

   Even this little program contains a bug!  For "midway", it was supposed
   to output  20 1 80 98  with a score of 61 (7th place) instead of the
   grid with a score of 288.  (Inadvertantly used integer arithmetic to
   calculate the slope...)
++ If I had it to do all over - here's what I would try ....

   If I had it to do over again, I would not wait until the last month!!!

   Early on I realized that the choice of how to represent lines would
   make important differences later on.  After thinking it out, I decided
   to use the good old standard slope and intercept:  y = m*x + b.  The
   main reason was that I wanted to be able to move lines around in
   arbitrarily small increments with an optimization routine and that
   would be difficult using integer coordinates on the square.  The
   disadvantage is that you have to be careful not to divide by zero
   when computing slopes and use an arbitrarily large value to represent
   vertical lines.  (I used values as low as 1000, usually one or two
   orders of magnetude higher.)

   However, I was rather intimidated by the scoring routine.  After a
   couple of months of only occasionally thinking about it, I realized
   around September 1st that it is really rather straightforward:  First
   compute all the vertices (i.e. intersections, including the boundaries)
   keeping only those on the square.  Then make some sorted lists of them
   for each line (again, including the boundaries).  You also need some
   flags to indicate when a line segment has been used, but only one per
   segment even though most line segments are traversed twice.  Now you
   are set to traverse each polygon, adding up the area as you go and 
   checking off the flags if you go in the right direction (but not if
   the left direction ).  The only hitch is deciding which way
   to go as you get to each intersection but that turned out to be easy
   after carefully thinking it out.

   Well, there was another hitch, what to do about three or more lines
   meeting at a point?  I had hoped I could just ignore them and throw
   out any very small areas.  But it turned out that the lines had better
   be separated enough that round-off error doesn't corrupt the lists by
   getting the vertices sorted inconsistently.  If that happens you will
   wander haphazardly around, usually off the end of a list (coredump),
   but sometimes in an infinite loop (if it doesn't include the starting
   vertex).  So I had to nudge the lines a little bit and I also included
   tests to abort the score if necessary instead of letting it crash.  Even
   so, lots of lines meeting at a common point turned out to be a challenge.

   By Labor Day I had an acceptable scoring routine--in QBASIC on a PC
   using single precision!  But I had less than two weeks left to do all
   the rest.  Here is what the final program attempted to do:

   First it rotated and reflected the initial line so that the slope was
   positive and less than unity.  This simplified the computation of some
   kinds of solutions.  At the end, the output points were unrotated just
   before they were output.

   Then there was a series of canned solutions, including the 5x5 grid
   (which is, after all, the optimum solution for some small nibbles).
   Some of these contained as many as 11 lines in the hope (not very 
   realistic) that one of them could be replaced by the the input line.

   Next there were several computed solutions.  One was the "Pizza Pie",
   a series of lines all meeting in the center in case the input line should
   go there (again, not very realistic, although one came close).  A much
   more important one was "Slats", a series of nonintersecting lines on
   either side of the initial line, this being computed for various total
   number of lines from 5 to 10.  Even better would have been "Bisected
   Slats" with a single line crossing all the rest, but I didn't have time
   to figure out how to compute this.  Still others should have been
   developed, each designed for special cases.  One of the more challenging
   ones would have been for the original system test.  But I didn't have
   time to do any of these.

   Each potential solution was scored and, if not too bad, was sent to a
   home-brewed optimization routine which tried to improve it by moving lines
   around.  The best of these was saved and then the optimizer tried it even
   longer.  The optimizer needed further tweaking as it tended to get caught
   in local minima (so, what else is new?).  Surprisingly, execution time
   was not a problem; the scorer could do thousands in only a few seconds,
   even with an interpreted program on the PC.  I was going to be in the
   unusual position of not knowing what to do with my 10 minutes if I couldn't
   get any better solutions after only a few seconds!

   So I translated the whole program to C and I had less than a day to debug
   it.  I didn't make it.  The reams of compiler errors I got rid of, but the
   C program never consistently put out the right answer so I didn't submit it.
   Only after I got the final results from my initial entry, did I find the
   bug mentioned above, now also duplicated elsewhere in the program.  I'm
   sure there were others also.

   Another refinement occured to me while writing this up.  I had originally
   hoped that I could do my special cases ("Slats", et.al.) by sloppily placing
   lines in the desired configuration and then letting the optimizer move them
   to right places.  This didn't work and I had to compute the positions rather
   closely and then the optimizer would fine tune them.  The reason is that
   when far from the optimum a quick improvement can often be obtained by
   throwing out a line or two.  Once a line moves off the square the penalty
   as it moves back will prevent the optimizer from ever putting it back.
   (Of course I had to purge such lines to get a legal output.)  This was the
   source of false optimums which gave my optimizer so much trouble and tweaking
   it is not going to work.  The solution is to add to the score a steep penalty
   for a line getting close to the edge and to optimize this.  Probably other
   such refinements to the opimization function would be needed to keep the
   lines from getting tangled before they got close to the optimum. 

   How might I have done?  The PC program would have scored 285 + 12 + 53 = 350
   which would have put me in 5th place.  That's only two places higher than
   my trivial program would have scored if it weren't for its bug, but now we're
   talking about the serious entries.  With some better computed configurations
   and maybe some better optimization it might have gotten second or third, but
   probably no better.  Oh well, there's always nest time...

   Question for Fred:  Could you take a program in BASIC or QBASIC?  I don't
   know how to read command line parameters, but perhaps some shell thing could
   be cooked up that would convert the parameters to standard input.  Then I
   would use that command line as the name of my program!

++ Please explain your program name: bzzz

   Now that's rather obvious:  the sound of a power saw.

   Actually, it's a recycled name.  I previously used it for the QUILTS POTM
   (the sound of a bee).


   Highlands, New Jersey, U.S.A.

   Bicycling, sailing, grow orchids, travel.

   Electro-optical systems design (hardware, not software) for Tyco Submarine
   Systems, Ltd.  (Previously AT&T Submarine Systems, Inc., but sold a couple
   of years ago.)


   Nothing new...

              griddo  1173 (278/853/ 42)  287 45 41
griddo submitted by P.Maragakis A.Danalis at plm@mpq.mpg.de
++ Please summarize the algorithm used by griddo

We construct an initial grid and then perform a Monte-Carlo.  The
random moves are controlled by two criteria.  First by optimizing with
respect to the sixth moment of the area distribution.  This tries to
remove high assymetries of the distribution.  Second we optimize with
respect to the score (as defined by the POTM rules).  The final
version uses the simplest initial grid (5x5).

We have created a good infrastructure with classes about polygons,
polygon-grids, and most utilities needed for real work on the
problem.  Unfortunately we had no time available after June ;-(

++ If I had it to do all over - here's what I would try ....

We would rework initial conditions, and try purely topological
attempts.  We have tried an adoptive grid method, that tried to add
lines sequentially and could come up with quite good solutions in some
cases.  Large scale simulations on the first test grid using this
method came up with two interesting topologies and with a good score.
Unfortunately we did not include this in the final run.  We have
thought about using trying initial conditions based on the fraction of
the initial area, and also about trying all (!?) possible topologies.
We also considered algorithms on optimizing an already good
solution.  Too many to list ;-)

++ Please explain your program name: griddo

It comes from the initial condition we used: a 5x5 rectangular grid.



Heraklion, Crete, Greece.


SEX ;-)


Antonis:  Working on my MSc in computer science.

Paul:     PhD candidate in theoretical atomic physics 
(defence scheduled for November 2).


Antonis: Once I worked with Windows95.

Paul:    None, like an open book...

                vidi  1173 (278/853/ 42)  287 45 41
	Sorry ... No questionairre was returned for vidi

             packpou  1175 (279/854/ 42)  287 45 41
	Sorry ... No questionairre was returned for packpou

            Saw_Dust  1181 (282/857/ 42)  287 45 41
Saw_Dust submitted by Rajgopal Nayak at rajgopalnayak@hotmail.com
++ Please summarize the algorithm used by Saw_Dust

    The algorithim simply cut up the board into symmetrical pieces using 5 
horizontal and 5 vertical  lines. That way you are assured that the largest 
piece will be of size approximately 281. This is trivial solution aimed more 
at hedging the score rather that acutaly attacking the problem.

++ If I had it to do all over - here's what I would try ....

    Would scratch my brains a bit more, I guess :-)

++ Please explain your program name: Saw_Dust

    "Saw Dust"


     I live in India. I like to read a lot and play football and badminton. 
Am a MBA student right now.

        Icame_Isawed  1190 (288/860/ 42)  287 45 42
Icame_Isawed submitted by Ted Alper at alper@turing.stanford.edu
++ Please summarize the algorithm used by Icame_Isawed
sorry, didn't get around to writing a real program! I liked
the name and wanted to get it into the contest before someone
else used anything similar. I hoped to get around to writing
a program, but our new baby has filled what little free time I had...

++ If I had it to do all over - here's what I would try ....
I'd try writing a program!

++ Please explain your program name: Icame_Isawed
reference to the famous quote of Julius Caesar. I certainly
didn't conquer, though! maybe, I came, I saw, I stayed up
all night changing diaper after diaper...

palo alto; coach high school math teams; teach math over the internet;
sleep deprivation has caused me to forget my secrets;
potm idea: how about something like a game where you take turns
planting flags on a map... at the end our score is the area of
all the regions closest to your flags. You might need to play
the game twice, though, and average the scores.
to avoid first turn advantage... for
a large enough number of turns this shouldn't matter too much.
You could also soup it up by making the board an irregular shape,
or with holes, or  make some portions of the area count for more
than others. 
this idea comes from something in the Dr. Ecco column of Dr. Dobb's
journal about a year ago.

   GettinJigsawWitIt  1380 (313/1036/ 31)  462 16 18
GettinJigsawWitIt submitted by Donald Pratt at don.pratt@flashmail.com
++ Please summarize the algorithm used by GettinJigsawWitIt

I used evolutionary programming for GettinJigsawWitIt.  This technique
is loosely related to genetic algorithms.  With EP, you start with a
set of possible solutions to the problem.  Each solution is scored and
compared with the others.  The bottom 50% are thrown out and the top
50% are used to generate new solutions.  Unlike genetic algorithms,
EP uses just mutation to generate new solutions.  Each of the "surviving"
solutions is copied and then mutated to create the new solutions.  This
cycle is repeated until time runs out, or a maximum number of generations
is completed.

++ If I had it to do all over - here's what I would try ....

Well, I'd be sure to test for cases where the initial cut more or less
cuts the board in half.  I thought that might be a likely scenario,
but never got around to adding code to handle it.  Actually, adding
any heuristics probably would have been a good idea.  Too much work
though.  Random number based solutions (like EP, genetic algorithms,
or simulated annealing - I tried all three) and just so easy to code
up ;)

++ Please explain your program name: GettinJigsawWitIt

It's a play on the song title "Gettin' Jiggy Wit It" by Will Smith.
I've never actually heard the song, but always thought the name was


I live in Ramona, CA (in the mountains north-east of San Diego).  For
work, I'm the programming department for a small engineering consulting
company.  For fun, I read Dr. Dobb's Journal and Embedded Systems
Programming (can you say "geek").  Oh well, maybe one of these days
I'll strike it rich and buy myself a life.

            paparaki  1459 (252/1185/ 22)  645 16 17
paparaki submitted by P.Tsantoulis V.Vasaitis at vvas@egnatia.ee.auth.gr
++ Please summarize the algorithm used by paparaki

  paparaki used a genetic algorithm to evolve a good solution.
Essentially it consisted of two parts: the geometric algorithms (line
intersection, polygon splitting, etc.), made primarily by me (Vasilis),
and the genetic algorithm, made primarily by Petros. The geometric
algorithms were optimized to a large extent, and the genetic algorithm
used special techniques (guessing, hill climbing) to evolve faster.
Still, we both knew that paparaki didn't become fast enough for the
contest, and of course it generally could not produce optimal solutions.

++ If I had it to do all over - here's what I would try ....

  The most attractive solution that I had in mind (and couldn't get down
to code) was to use parallel lines, together with lines that cross them
at equal intervals. This way you can have perfectly equal polygons
without much hassle, and you only need to figure out what to do with a
small portion of the initial square.

++ Please explain your program name: paparaki

  paparaki in Greek means `little cock.' It's hardly insulting, and it's
rather cute. Petros chose it (I don't know the rationale), and lacking a
better name (and a better algorithm) I agreed.


  I live in Thessaloniki, the second biggest city in Greece. I'm a
student in the Computer Science Department of the Aristoteleian
University of Thessaloniki. I love coding in many different programming
areas, and with many different programming languages. I listen to a lot
of music (mostly modern rock and electronica), and go to the cinema as
often as I can.

  Petros lives in Athens, the capital of Greece. He's a student in the
Medical School of the University of Athens. When he's not studying for
University, Petros likes to code, listen to music or make some with his
piano, and do some karate training.

          BoredBoard  1627 (394/1191/ 42)  398 46 41
	Sorry ... No questionairre was returned for BoredBoard

           renaisSAW  1907 (505/1357/ 45)  433 44 49
renaisSAW submitted by Ranjeet Bhatia at ranjeet@psu.edu
++ Please summarize the algorithm used by renaisSAW

The overall structre of the algorithm what I thought should be a something
which can calculate score and an optimization scheme. I got nothing to say
about the optimization scheme as I couldnt get time to implement it.For
calculation of the score, the trivial tasks of finding which line intersects
what other lines and thier cordinates of intersection were calculated.
For the scorer I looked at the problem as polygons attached to a line. say if
we take one line then there will be polygons on its right side and on its left
side and for all of these polygons this line will be an edge. So if we look
through all the lines on the board we can get all the polygons.

1 say the line we are looking is line1
2 find the line at which line1 intersects the corner lines 
	of the board call it line0
3 find the next line with which line 1 intesects call  it line2
4 now we move our attention to line 2 and find a line which intersects with
	line2 such that there is no other line in between.. call it line3.
	(here we can find two line 3 , one if we want the anticlockwise 
	polygon another if we want the clockwise polygon, we will 
	choose according to the direction we are finding the polygon 
	(right or left)
5 set line0=line1; line1=line2 and line2=line3 and again find line3
6 go on repeating the above procedure till we get line 3 =line1.
	which implies that we have a closed polygon. for calculating 
	the area we dont need to store all the lines the polygon is 
	formed of triangle subtended by the intersection of line0 and line1.
	so if we know line0 line 1 line 2 and line3 we have a triangle. 
	calculate the area and keep adding all the triangles.

 the above algorithm can be very neatly coded for RECURSIVELY but i 
	didnt tried (I suffer from  recursion debugging phobia. which 
	keeps on recurring whenever i think of implementing recursion.)

optimization: dont ask me...

++ If I had it to do all over - here's what I would try ....

I would implement a good optimization scheme and a good intial solution
technique (sensitive to the intial cut)

++ Please explain your program name: renaisSAW

it comes from renaissance....


WHERE DO YOU LIVE?  state college, PA  USA.
DO FOR FUN?  squash, tennis and a bit of programming...
DO FOR WORK?  currently doing MS in mechanical engg from 
		penn state univ.(dont know why???)
INNERMOST SECRET?  still searching..

         Saw_It_Easy  1997 (467/1504/ 26)  499 28 25
Saw_It_Easy submitted by Aivars Zogla at uvsk@fix.lv
++ Please summarize the algorithm used by Saw_It_Easy
September rush, when school year begins, took me apart from algorithm
developments. On the other hand summer is summer.
So, I decided to go for certain score, wich will give me (if no problems) <1500.
I'm taking 10 cuts, which cross in the center of board and divide it into 20
equal pieces (Fred's one not taken in account). One and only care - i'm
checking weather Fred's cut isn't one of mine. And only one improvement -
very close Fred's cut to mine can eliminate latest.

++ If I had it to do all over - here's what I would try ....
Allways possible to do better until ultimate zero for all three tests. I
wouldn't try to take POTM apart from fun and enjoyment, anyway.

"PS I'm idiot because 'optimisation' I've made was just stupid mistake,
which led no to gaining points, but to loss. Not much and not to be a
winner, but small mistakes are most painful."

++ Please explain your program name: Saw_It_Easy
I hope, it's self-explaining.

Ugale, Latvia, teacher.
I'm not doing any particular activities for fun. If I feel - it will give me
fun - I'm simply go for it.
I have idea about participating in POTMs, but I'll ask Fred later, is it
possible. Then you'll see.
Regards to POTM company! It's real fun to be with you.

         PizzaSlicer  2385 (617/1718/ 50)  613 49 46
	Sorry ... No questionairre was returned for PizzaSlicer

               Image  2905 (550/2343/ 12)  1732 2 11
	Sorry ... No questionairre was returned for Image

           Rusty_saw  3848 (928/2853/ 67)  907 29 55
	Sorry ... No questionairre was returned for Rusty_saw

           first_cut  4172 (1023/3127/ 22)  995 15 13
	Sorry ... No questionairre was returned for first_cut

            puddytat  5659 (1606/3999/ 54)  1201 43 42
puddytat submitted by Mr. POTM-Master at fah
++ Please summarize the algorithm used by puddytat
	Just drew 10 random lines ... hey - I'm the POTM-Master
	and I can do what I want.

++ If I had it to do all over - here's what I would try ....
	An easier contest ... this one was TOUGH!

++ Please explain your program name: puddytat
	"I tought I taw a puddytat ... I did! I did!"
						= Tweety

	Marlboro, New Jersey
	I run the POTM for fun, RPG games, Mets fan, oh yeah - Family stuff
	www.catalog.att.com and www.e-care.att.com ... buy something!
	After 32 years, I still enjoy going to work in the morning ...

15MenOnTheDeadMansChest  9170 (2277/6881/ 12)  949 8 10
15MenOnTheDeadMansChest submitted by Boris Bulayev at bbboris@rinet.ru
++ Please summarize the algorithm used by 15MenOnTheDeadMansChest

No algorithm. It didn't even undetstand your coommand line parameters.

++ If I had it to do all over - here's what I would try ....

No idea

++ Please explain your program name: 15MenOnTheDeadMansChest

See "Treasure Island"


Idea: recognition of structure of 3d wired object using 3 descriptoin of its

                cSaw  10417 ( 45/10330/ 42)  286 99 11
cSaw submitted by Doug Jones at douglasjones@att.com
++ Please summarize the algorithm used by cSaw

The basic idea is local search from a huge number of intelligently selected
starting points.

  + First the coordinate system is translated, rotated and mirrored, so that
    the starting line is where the rest of the code expects it.  Before
    printing the final results, this transformation is undone.  Unfortunately,
    my code that mirrored about the y==50 axis contained an obvious bug (the
    50s should be changed to 100s) that caused cSaw to fail on the 1 80 98 20
    final problem.  With this code fixed, cSaw gets a score of 10 (by my
    scoring code) and would of otherwise finished fourth, oh well.

  + A starting solution is created by generating a simple grid of 5
    horizontal and 5 vertical lines.  This solution is used if a better
    one isn't found within the time limit.

  + Three different methods are used to generate starting solutions.  I call
    them: Divide Largest, Divide Each and Divide Both.

      - Divide Largest tries to divide the larger initial piece using a
        grid of n "horizontal" and m "vertical" lines.

      - Divide Each tries to evenly divide each initial piece using lines
	lines "parallel" to the initial line.  n lines are used to divide the 
        smaller piece and m lines are used to divide the larger.

      - Divide Both is like Divide Each but it uses an additional k lines
	"perpendicular" to the starting line to divide both initial pieces.

    Lines are place given a slope and area (on the 0,0 side) or by giving 
    two areas and a crossing line.  First a real valued equation for the line
    is found and then the integer points are found by searching combinations
    close to the line and saving the pair that best fits the area(s).

  + For each of the three starting methods, the ten possible lines are
    allocated to all combinations of n, m and k.  A lower bound is
    calculated for each combination and the methods are tried in
    increasing lower bound order.

  + Two different local search methods are used.  The first accepts the each
    change as soon as an improvement is found.  The second is a variable
    depth search that tries to make changes to all lines at once.  Both use
    the same neighborhood, which consist of small changes to one or both 
    points of a line.  Divide Largest only uses the first local search
    since its fast and Divide Largest is very slow (it tries a lot of starting

++ If I had it to do all over - here's what I would try ....

  I should have made my scoring code handle real value points, it would
  have allowed me to try things that I otherwise couldn't.

  I also should have been more careful about what I tested.  I spent most
  of July and August trying out "improvements" to the basic algorithm,
  none of which seems to work.  On Sep 1 I found a bug that was causing
  flaky answers.  Once this was fixed everything worked better, but I'll
  never know of any of those "improvements" would work.  And, I didn't
  find that bug in the initial coordinate translation until too late.

++ Please explain your program name: cSaw

  Combination of the language name and Saw that sounds like an unrelated word.
  Actually, my code is written in C++, but I didn't like c++Saw or cSaw++.


  I live in New Jersey and work for AT&T where I write software used to route
  PVCs in the Frame Relay network.  I ride bicycles, both on and off road.
  Your POTM ideas always seem to be better than mine, but I'll let you know
  if I get a good one.

          MadHackSaw  10482 (10435/  2/ 45)  9899 47 0
MadHackSaw submitted by Peter Szkiela at petszk@crossecom.com.au
++ Please summarize the algorithm used by MadHackSaw
Simply find the 2 largest pieces on the board, find the central point of each, and run a line through both. Then start the process

++ If I had it to do all over - here's what I would try ....
..try to get more time to work on the program

++ Please explain your program name: MadHackSaw
Hmmm...I had visions of the program madly hacking pieces apart.

Live: Western Australia
Fun: I seem to have a new hobby every week, but some of the long 
	standing ones are Soccer, Basketball and 4 Wheel Driving
Innermost Secret: It wouldn't be a secret then, would it? ;)
POTM Ideas: How about Take 5? Sorry, I probably infringed copyright 
	with the name, but the general concept is you take a 12 x 12 (or
	whatever size) grid, and opponents take turns placing a 
	peg on the board. The winner is the first player to get 5 
	in a row. A draw happens (rarely) if the board is filled 
	without either player getting 5 in a row.

             HackSaw  10698 (275/10324/ 99)  9999 12 41
HackSaw submitted by Paul "Bozo" Banta at pbanta@yahoo.com

++ Please summarize the algorithm used by HackSaw

HackSaw finds a good way to slice the two different pieces that result
from Fred's cut. It compares this with what would result from slicing
the board into a 6 X 6 grid. Which ever one has a better score is
printed out as an answer.

++ If I had it to do all over - here's what I would try ....

I'd do two things different. I'd test more. Something's hosed
somewhere (hosed = yes), and that cost me a 7th place finish. Also,
I'd put comments in as I coded. Java has a nifty comment extracting
tool that would have been great if I had put comments in.

++ Please explain your program name: HackSaw

I think it's self explanatory. Code is often "Hack"ed . . . The
problem was to "Saw" some wood . . . HackSaw. Personally, I liked the
name "cSaw" the best.


I live in Colorado Springs, Colorado, USA. The funnest thing I do is
compete in these contests. I also like hiking, fishing, backpacking,
camping, volleyball, and breaking perfectly good automobiles under the
guise of "fixing". I am a software engineer working in Java. My
innermost secret is "Bozo". I don't have any new POTM ideas.

  Who_was_that_woman  10839 (233/10567/ 39)  335 99 13
Who_was_that_woman submitted by Kevin Williams at lorikevn@aol.com
++ Please summarize the algorithm used by Who_was_that_woman

Find a pattern of horizontal and vertical cuts that appear to yield the most
promise, then spend the rest of the time jiggling those cuts 
(three at a time) to reduce the score.

++ If I had it to do all over - here's what I would try ....

Fix the one-line problem that prevented me from producing a result for the
second problem, and thereby reduce my score from 10,567 to 801.

++ Please explain your program name:

It's a tribute to Walt Kelley, who drew the old Pogo comic strip.  
"One magician says to the other, 'Who was that woman I sawed 
you with last night?'  'That was no woman; that was my half-sister.'"  
If you've never read Pogo, think of Doonesbury with animals set in 
Okefenokee Swamp.  If you have read Pogo, you probably miss it as much as I do.


I now live in Longmont, CO.  I enjoy bicycling, bowling, and volleyball.  
I am a contract MVS and OS/390 systems programmer, currently 
billing IBM for my time.
Still trying to port my POTM program to my Digi-Comp 1.  
None at the moment, but I really enjoy participating.

            slycndyc  11227 (301/10875/ 51)  575 99 22
slycndyc submitted by David Harris at dpharris@megsinet.net
++ Please summarize the algorithm used by slycndyc

Two primary geometric properties, area and center of gravity, were used to
construct several slicing strategies. After prelimary cut placement, the program
twiddles with the end points, looking for improvements in area difference.
Finally, a pass is made through the solution, looking for an intermediate
solution having fewer cuts.

++ If I had it to do all over - here's what I would try ....

I would have spent more time on minimum cut solutions rather than shooting for
maximum counts.

++ Please explain your program name: slycndyc

It's a phonetic representation of 'Slice and Dice', which draws on the old TV
commercials where the announcer always said, "It slices, it dices!!"


I'm in Richardson, TX, a 12-year survivor of a 'temporary' migration from
Virginia and points North. To beat the heat and fire ants, I've forsaken all
outdoor activities and simply tinker and read. I'm an independent, currently
working as a software development manager for a medium-size ISV.

This is the first time I've participated in the competition. I've known about it
for years, but never jumped in. For this problem, I was able to draw on some
work I did back in the Supercollider days when we were computing mineral rights
on the purchased properties (the ring was so large that the slope towards the
Gulf of Mexico caused the projections to deviate from the vertical.)

               singh  13931 (237/13595/ 99)  9999 14 11
singh submitted by Shailender Singh at shsingh@hss.hns.com
++ Please summarize the algorithm used by singh

The steps are :

1) calculate the two areas given by the first line.

2) find the points P1 P2 where the line cuts board into two parts lets say
A and B. fix one of cutting points and and calculate the no. of lines
need on each of the parts to devide them into some smaller equal parts
such that the diffrence of areas of smaller parts is minimum.   

3) Find such lines by fixing one point P1 of all of the lines. (This part
had some implementation errors).

4) Now search for a random line s/t it would minimise the score (the set
points for the construction of such  lines is approximated to be on the
edges of the original board, such lines 60000).

5) repeat 4) till no new lines could be found. 

This program theoritically should give scores as <= 60 for any board. But
there were some implemetation flaws.

++ If I had it to do all over - here's what I would try ....

Try to find a new scoring scheme for board (for the internal
implementation) s/t it converges to your scoring sheme for the last line
to drawn (minimise the actual score at the last line) and this score
should be s/t that if you minimise it for the given board position you
should be able to leave the board s/t the overall score minimises <10 at
the last line drawn. 

++ Please explain your program name: singh

No program name given.


--My address is : 16, Samaj Kalyan Apt., Vikaspuri, New Delhi, India

--I normally do abstract thinking (reallity etc.), solve mathematical
	problems/ play table tennis, cricket for fun.

--I am a software engineer at Hughes Software Systems, New Delhi.

--I want to be know as a great thinker.

--This problem really required a lot of implementation coding( and for
which working people like us don't have time). Can be more on algorithm
and experimentation side.

     No_Lost_Fingers  26160 (8099/18059/  2)  9899 2 2
No_Lost_Fingers submitted by Ray Stephenson at ray@FisherTowne.com
++ Please summarize the algorithm used by No_Lost_Fingers

Unfortunately, the algorithm was fairly unintelligent.  I simply reversed
the given coordinates to create a line that bisected the existing (first)

++ If I had it to do all over - here's what I would try ....

I would have spent more time and done what I actually wanted to do which was
to use a ratio-based approach where I could create lines parallel to the
original line and try to find the lowest ratio of area that I could create
on one side versus the other.  However, I never did get around to working on
the program more than just entering.

++ Please explain your program name: No_Lost_Fingers

Always a concern when using sharp objects...

Buffalo, NY
Volleyball, Reading, cooking
Build Internet commerce applications using SQL Server and ColdFusion
If I revealed that, it would no longer be a secret...

I really liked the idea of a 'competitive' contest where submitted programs
must compete with one another through a series of playoffs to win.  The one
you had a while back where each program started from one corner and could
either shoot, build a wall, or move was very interesting.  Something along
those lines, but maybe with a different twist.  Maybe 3D with a certain
number of walls randomly placed in the matrix, and a capture the flag type

     WoodyWoodCutter  30196 (9999/20098/ 99)  9999 4 99
	Sorry ... No questionairre was returned for WoodyWoodCutter

              my_day  33084 (9029/23989/ 66)  9930 57 57
	Sorry ... No questionairre was returned for my_day

             Dice_It  34910 (9999/24898/ 13)  4900 99 99
	Sorry ... No questionairre was returned for Dice_It

              cut-em  40095 (9999/29997/ 99)  9999 99 99
	Sorry ... No questionairre was returned for cut-em

Make your own free website on Tripod.com