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
fvdp@decis.be,pavel@ontil.ihep.su
=================
++ Please summarize the algorithm used by Yalta
Algo
----
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
[Pavel]
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
[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?
[Pavel]
Programming on Unix systems (drivers, neural networks). But I
began working only three months ago.
[Frederic]
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
quadrangles.
++ 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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM
IDEAS?
[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
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
_________________________________________________________
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 :-)?
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
- 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
gradient.
++ 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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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)
coordinates.
++ 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).
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM
IDEAS?
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
history.
++ 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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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/
-Paul
_________________________________________________________
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 ...
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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".
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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
made.
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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
this:
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
perpendicular).
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!
4. WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM
IDEAS?
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
http://www.geocities.com/Athens/Atrium/6391/
_________________________________________________________
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:
#include
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
possible.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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
them.
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.
Else,
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).
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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.)
Hah!
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
WHERE DO YOU LIVE:
Heraklion, Crete, Greece.
DO FOR FUN:
SEX ;-)
DO FOR WORK:
Antonis: Working on my MSc in computer science.
Paul: PhD candidate in theoretical atomic physics
(defence scheduled for November 2).
INNERMOST SECRET:
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"
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM
IDEAS?
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...
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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
cool.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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.
algorithm
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? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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"
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
Idea: recognition of structure of 3d wired object using 3 descriptoin of its
2d-projections.
_________________________________________________________
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
lines).
++ 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++.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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
again.
++ 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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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:
Who_was_that_woman_I_sawed_you_with_last_night_
_That_was_no_woman_that_was_my_half_sister
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.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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!!"
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET? POTM IDEAS?
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.
++ WHERE DO YOU LIVE? DO FOR FUN? D$O FOR WORK? INNERMOST SECRET? POTM IDEAS?
--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)
line.
++ 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...
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
POTM IDEAS?
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
objective.
_________________________________________________________
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