QUILTS 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).


============== 1 ====================== GrannysGhost =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
      GrannysGhost    7.372881 26  870 118  594.64  c    Ben Nye
=================
GrannysGhost submitted by Ben Nye
=================
++ Please summarize the algorithm used by GrannysGhost
Depth first search with search path directed based on color frequencies
also a few "smart pruning" methods were used, so that if it was spending
a long time in one part of the search tree assume that it is stuck and
bump it loose.

general outline:
================
1. spend 1/2 time using this search to find largest square quilt that
  it can.
2. quickly check if a better score can be gotten using a narrower
  (but much longer) quilt.
3. whatever turned out best, try to lengthen it for most of the 
  remaining time.
4. I was going to use a edge color guided search to build a quilt of the
  same best dimensions found, and less edge colors, but ran out of time
  and energy to code it

data structures used:
=====================
When each square after the first is added to the quilt, it may need
to match up, left, or both. I created arrays for each need.
For example to handle both I created an array rot_list[26][26] so
that to find all rotated patches that have 'F' up and 'J' left
I simply look at array['F'-'A']['J'-'A'] and get a linked list of
all such pieces back. Since each piece could be present up to
4 times in each array, the rotated pieces have pointers back to
an array of non-rotated pieces, which keep the count of how many
times each piece has been used. These counters are also used to
handle duplicate pieces.

general search algo:
====================
My search routine takes the dimensions of a quilt as input,
and uses a depth first search starting at the upper left and working
top to bottom, left to right.
This search routine was used for 4 steps:
1. spend 1/2 time using this search to find largest square quilt that
  it can. Search for NxN till one is found, or out of time, then
  search for N+1 by N+1
2. briefly check if a better score can be gotten using a narrower
  (but much longer) quilt.
3. whatever turned out best, try to lengthen it for most of the
  remaining time. ie. if the best was a 30x29 found while searching for
  a 30x30 solution, search for a 29x31, then for a 29x32, etc
  If the best was a 20x39, search for a 20x40 and if found search
  for a 20x41, etc
4. I was going to use a edge color guided search to build a quilt of the
  same best dimensions found, and less edge colors, but ran out of time
  and energy to code it, instead just keep trying quilts of the best size
  found hoping one will improve the edge colors till out of time.

heuristic improvements to search:
=================================
1. Pieces are selected to use those pieces with a rare color facing
  to the right first. The general idea being that this will
  quickly bury such difficult to use colors and leave only easy to
  place pieces for the end when placement is the most difficult.
2. Each time that an attempt to place a piece below another in
  the quilt is made, if the attempt fails a counter(for the piece above)
  is incremented, and if it succeeds the counter is reset to 0.
  If the counter reaches a certain limit(I like 500) the piece above
  is marked as being a "trouble piece" and the search is backed up to
  that piece and it is replaced with the next piece in the list.
  This is most useful when the last piece of a certain color is placed
  facing down, but is also useful in more complex situations.
3. futility cutoffs. A count is kept of how many times the search
  moved back and forth below the same square, and if it passes a
  certain limit it was concluded that no progress was being made toward
  adding another layer on the existing layer, so the search was backed
  up one entire row. ie. from (5,25) back to (5,24)
4. probation squares. It was noted that if a piece is a trouble
  piece(see 2.) then it tended to be a problem at the same location
  repeatedly. I added a record in each piece of where(if at all) it
  had last been in trouble, and prevented it from being placed there
  again until it has been used in some other location.


++ What did you do to make your code run faster?
stuck the word "register" in a couple of places.
removed the recursion(didn't pay off much)
kept several lists of the pieces pre-rotated and sorted.

++ If I had it to do all over - here's what I would try ....
skip removing the recursion, the recursive version was easier to
work on and roughly as fast.
I'm glad I waited till the last weekend to remove it.
Also skip a lot of other dead ends that didn't make it to the final prog.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Location: Missoula, MT (USA)
Job: programmer(C/Unix/X11)
Fun: write game playing programs, play Warcraft II, play suicide chess

=================================================================

============== 2 ====================== BuildSquareQuilts =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
 BuildSquareQuilts    7.355932 26  868 118 598.01   c Sergey Kondrashchenko
=================
BuildSquareQuilts submitted by Sergey Kondrashchenko 
	at iacgsz.pavlodar.kz!SKondras@mail.nursat.net
=================
++ Please summarize the algorithm used by BuildSquareQuilts

  The algorithm is based on recursive search of possible variants.
After choice initial quilt the construction begins as it is possible
of a more square blanket by construction of the completed parties from
a current rectangular with an opportunity of expansion in all parties.
Initial undertakes quilt with least weight.

++ What did you do to make your code run faster?

  For acceleration constructions of a blanket the connected lists quilts
on all possible combinations of corners (26*26), and also lists (26) for
being available quilts with availability of particular colour previously
are under construction. The lists are under construction sorted out in
ascending order of weight quilts. The weight quilts is calculated
depending on that, what colours it has and how many is present quilts
with presence of the given colour (with allowance for of that party, which
in near future will become boundary).

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

Company :  Service of employment
Location :  Republik of Kazakhstan
Job :  programmer
Do for fun :  programming
Innremost secret :  it's big secret

=================================================================

============== 3 ====================== brain =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
            brain     7.250000  24 841 116  540.63 gc Jaco Cronje

 =================
 brain submitted by Jaco Cronje at s9805027@student.up.ac.za
 =================
 ++ Please summarize the algorithm used by brain

DFS, with some optimizations like not searching the same things twice.
Heuristic was added so that the best branch will be searched first.
 
 ++ What did you do to make your code run faster?

Removing duplicate searches and just simple optimizations in 
some lines of code.  Programming in GCC instead of JAVA. 
There was a BIG difference in speed when
I switched to GCC. JAVA was realy very slow. 
It's just a pity that we couldn't use
compiler optimizations, the speed would double then.
 
 ++ If I had it to do all over - here's what I would try ...

Write a sort of genetic algorithm. Populations..... 

 ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

Student at the University of Pretoria in South-Africa ( RSA )
Going into my second year of study in February 1999.
Working as a researcher at the University.
Program some 3D stuff for fun, games, algorithms..  enjoy my girlfriend....
No Secrets..
LOTS of POTM ideas, this is the sort of thing that I want to start at our
University in South-Africa,
I've got a lot of programming problems that I have created. Mail me if you
want some ideas...
I took part in IOI 98, (International Olympiad in Informatics) in Portugal
and are planning to start
a olympiad based competition in our country between Universities maybe..


=================================================================

============== 4 ====================== monicas_dress =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
     monicas_dress    7.250000  25 841 116 553.13   c W.Neirinck W.Fransen
=================
monicas_dress submitted by W.Neirinck W.Fransen at
	wouter.neirinck@barco.com
=================
++ Please summarize the algorithm used by monicas_dress
[Neirinck, Wouter]  The basic work put into the algorithm is the
assignment of a 'quality' to certain generated line 
(row or column) of the quilt.
I will prefix all parametrizable elements of the algortihm with P_.
We basically have a simple but fast cell-level backtracker which 
searches a P_number of lines that match the 'current' quilt. 
This backtracker has a P_backtrackdistance which indicates 
how fast it goes back in one line when backtracking. 
We sort the generated lines in descending 'quality' and store a
P_number2 of these lines in a cache.
We also have a simple 'line-level' backtracker that uses the 
lines that were generated and put in a cache. When backtracking, 
it takes the next best line out of the cache and puts it in 
the quilt. It of course keeps track of the best quilt up to now.
There is also a 'restart', the algorithm restarts with a new
begin patch more often when the quilt is perceived to be 'hard'.
Quality is comprised out of a number of factors, each having a
P_weight. Of course these weights are dependent on where you 
are in the quilt.  Quality factors try to measure : - squareness 
of the generated quilt : always important, mostly in beginning
- the new lines 'uses' hard to lay patches : only uses for
'easy' quilts, where we try to lose the 'hard' patches in the beginning
- how easy can I lay a new line aside the current one
- how does this new line affect border colors (only important at the end)

We also start with a test-run of P_time1 to assess quilt
parameters like 'hardness'.
We end up with some end-run where we take the maximum quilt reached,
eliminate P_number rows of it and give it another try.

Shortcomings : we really perform no 'intelligent' operation
after we get our quilt selected by the 'best' quality 
(like swapping single cells in and out)
We also didn't have time enough to be able to remove rows and
cols randomly, so in our line-level backtracker we ALWAYS 
remove the same rows and cols we laid before. And we certainly 
didn't have enough time time to do major tuning.

Ah well, it was fun to work together on the project.
 
++ What did you do to make your code run faster?
[Neirinck, Wouter]  Some minor effort (5 hrs) was put into
profiling and adapting code. Al other stuff was written with 
speed in the back of our head. We only
'really' started working the last 2 weeks, so...   

++ If I had it to do all over - here's what I would try ....
[Neirinck, Wouter]  Start sooner, work harder, so we could
finish our initial ideas. 

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
[Neirinck, Wouter]  Barco Graphics, Ghent Belgium, Software
Engineering,
Innermost secret, That's what we do for fun, You're better at that.
=================================================================

============== 5 ====================== radek_family_quilt =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
radek_family_quilt       7.25  25  841 116 578.54  gC Kent Radek
=================
radek_family_quilt submitted by Kent Radek at kent_radek@itd.sterling.com
=================
++ Please summarize the algorithm used by radek_family_quilt

All available rotations of pieces are sorted so a binary search can easily
(and quickly) provide a list of all the ones matching a needed pattern.  A
heuristic evaluation provides 8 "good" starting tiles.  Recursively, sides
are added to the quilt, attempting to keep it square before expanding along
the larger dimension.  Each side is added by recursively adding tiles that
are selected based on a heuristic value which depends on how large the
quilt is so far.  Pieces with rarer colors are tried early on to build a
core quilt and leave more common colors for the later, difficult outer
sides.  Any time a side is completed, the current quilt is compared against
the "best so far" and saved if it is better.

This search is cut off after approximately 10n^2 nodes (max of 1000000) in
order to try other starting pieces and other cutoff points for determining
the heuristic value of pieces being added.  Once a maximum quilt is found
-- and it usually happens quickly -- the rest of the nodes searched are
usually fruitless, so this is why several starting points and a few varying
heuristic cutoffs are attempted.

++ What did you do to make your code run faster?

Underlying data structures are designed to allow operations like searching
for pieces or adding/removing sides of the quilt quickly.  While the code
recurses through attempts at completing all four sides, once a side is
completed, it is never tried again with different pieces.  Also, the
heuristic used to choose the next piece for completing a side takes only
the top 3 (or 5 or 7 depending on total number of tiles) choices so the
number of nodes searched to complete a side is no more than 3^length.

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

Hard to say...I got mixed results by allowing pieces blocking further
progress to be replaced by other available pieces with different outside
colors.  I would have liked to be able to use other outside pieces (not
just unused pieces), but my data structure wouldn't have supported this
without some modification, and I didn't have time.  I did the whole thing
in two weeks, and wish I'd had /lots/ more time to study the problem and
come up with alternate ideas.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

Sterling Software, Bellevue Nebraska.  Lead Software Engineer (and self-
proclaimed principle algorithm designer).  I run, bike, and sometimes
write programs for fun.  I have no secrets...that I can tell you.  I also
can't come up with a POTM idea in 15 seconds.
=================================================================

============== 6 ====================== Four_Corners =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
      Four_Corners      7.25   25  841 116 595.16   C Bill Wade
=================
Four_Corners submitted by Bill Wade at bill.wade@stoner.com
=================
++ Please summarize the algorithm used by Four_Corners

Exhaustive, depth first search, with time limits on branches.

++ What did you do to make your code run faster?

Reduce branching (number of choices at any move) by preferring to place
tiles in positions with two neighbors.

Reduce symmetries (this is another way to reduce branching) by:
o  recognizing duplicate tiles (including duplicates after rotation, such
as ABCD and BCDA)
o  recognizing tiles with special symmetry (AAAA, ABAB)
o  only search for quilts with at least as many rows as columns.

Used lookup tables to rapidly find all sides of a given color and all
corners with a given color pair.

Look for big quilts without regard to color, then start looking for better
color scores.

In some situations split available time between branches of the search
tree.  I found it was more important to spend some time on each branch near
the root than to exhaustively search each branch that happened to be
entered.

Used a Timeout() function that did a system call only once every several
thousand invocations.

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

Convince the POTM to use optimization when compiling.  Otherwise convert
small inline functions to #defines.

For large problems, split the available time among more initial guesses.

++ COMPANY? LOCATION? JOB?

Stoner Associates, Houston Texas, develop engineering software.

 DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

Square dance, not telling.

=================================================================

============== 7 ====================== scrabble_gambler =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
  scrabble_gambler    7.25    26   841 116 549.91  c Kris Kenis
=================
scrabble_gambler submitted by Kris Kenis at kris.kenis@barco.com
=================
++ Please summarize the algorithm used by scrabble_gambler

The winner of this POTM problem is not the one with the "best" program,
but the one who has the most luck! So, my program is a "lucky" program
with almost no intelligence etc.
Squares are placed on a pre-defined path, in that way I have only to
check the top and left sides of the squares. I am using the most stupid
back-tracking method. If a next square cannot be placed in the quilt, I
remove the previous square and try again with the next square in the
"square list". I notice that I can do a lot with this back-tracking in a
small time interval, but I couldn't find a better result after a few
seconds. So, after 100000 backtracks, I shuffle the square list and try
to place the squares in a new quilt.


++ What did you do to make your code run faster?

- Paths are place in a predefined path -> only check for top and left
borders to fit in quilt.
- Some use of inline-functions (#define)


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

- use of weight-factor (= quality) for each square.
- making use of 4 functions (AddNorthRow, AddWestRow, AddSouthRow,
AddEastRow) instead of using a pre-defined path --> random placing rows
or columns.


++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

- Barco Graphics, Belgium (Gent)
- R&D Engineer Packaging and Label
- renovate my new apartement, Waterpolo, Ski
=================================================================

============== 8 ====================== sewing_machine =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
    sewing_machine    7.241379 24  840 116 550.02  gc Michael Strauch
=================
sewing_machine submitted by Michael Strauch at michael.strauch@cityweb.de
=================
++ Please summarize the algorithm used by sewing_machine

Sewing machine constructs a quilt by trying to add incrementally edges
of squares to an existing quilt (the wider edge is preferred). If no
edge can be added any more, it removes a randomly chosen edge and tries
to add another one (with some randomness), until time is up.


++ What did you do to make your code run faster?

The main problem was to get the backtracking routine for adding an edge
fast enough. I solved this problem by using some dynamic programming
techniques. Before starting the backtracking search, sewing_machine
quickly calculates a set of possible squares for each position of the
edge, ignoring the fact that each of the available square could be only
used once on the edge. The second step is the backtracking, which uses
the calculated sets.


++ If I had it to do all over - here's what I would try ....
- Make a lot of more speed improvements
- Use a population of different quilts while doing the search, not only
one.
- Find different rules to modify the quilt


++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
michael.strauch@cityweb.de
=================================================================

============== 9 ====================== needle =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
            needle 7.172414    26   832   116 574.86     c Bernard Hatt
=================
needle submitted by Bernard Hatt at bmh@arkady.demon.co.uk
=================
++ Please summarize the algorithm used by needle

The basic algorithm is to try all the possible combinations (or
as many combinations that can be found in the time), and record the
best scoring quilt.

++ What did you do to make your code run faster?

As the pieces are read in lists of all the pieces which contain a
colour or pair of colours (on adjacent sides) are generated, hence for
any case of trying to add a square, it's just a simple (quick) question
of looking down the appropriate list. Rows and columns are added to the
initial square alternately in the order:

12468    If it's impossible to complete a row then just columns
33468    are added (and vice versa). Only one rotation of the 1st
55568    square is used to eliminate the duplicate solutions of
77778    the same quilt rotated.
99999

I also changed some functions into macros to try and get rid of the
calling overheads, which improved speed by about 10% on my machine,
and by ~1% on the POTM test machine :-(

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

The program could do better 'tree pruning', where it is not possible
to improve on the best score at a point, and could know that
if there is only one instance of a colour it must go on the edge etc.
Adding the rows/columns in a spiral pattern may be better, if a row
could not be added at the bottom, a row could be added at the top.

>From previous POTM experience it seems better not to attempt too many
last minute changes and tune ups, and stick with well tested robust
code.


++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

I currently work for Oracle, based in Hemel Hempstead (UK).
=================================================================

============== 10 ====================== Arlequin =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
          Arlequin 7.122807    23   812   114 590.00     C Kroum Savadjiev
=================
Arlequin submitted by Kroum Savadjiev at kroum@bigfoot.com
=================
++ Please summarize the algorithm used by Arlequin

I used very optimised brute force.

++ What did you do to make your code run faster?

I did all sort of optimisation, in improving my algorhytm, as well as
low-level optimisation.

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

There are many things that i can still do to improve my program, but i
don't have too much time...

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

I work as a developer for Purkinje Inc. in Montreal. 
I love programming, reading books,  walking, playing with my son...



=================================================================

============== 11 ====================== deCoubertin =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
       deCoubertin 7.122807    24   812   114 598.02     c Giorgio DiFalco
=================
deCoubertin submitted by Giorgio DiFalco at G.DiFalco@iseo.it
=================
++ Please summarize the algorithm used by deCoubertin
I used a very simple brute-force algorithm, that is starting from one
square and adding squares to the longest side of the rectangle buit up
to that moment. I then added a couple of IF statements to stop looping
after a fixed amount of attempts, so that the program can start again
with another square as first.

++ What did you do to make your code run faster?
Just created two arrays linking all squares containing a given color and
all squares containing a given adjacent couple of colors.

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

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
IS&O, Italy, Consultant, ...

=================================================================

============== 12 ====================== SQUILT =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
            SQUILT 7.122807    24   812   114 600.00    gc Mike Liddell
=================
SQUILT submitted by Mike Liddell at mike_liddell@hotmail.com
=================
++ Please summarize the algorithm used by SQUILT
DFS with dynamic heuristics
Heuristics simply list the order to try pieces
These lists are updated using a simulated annealing process
coded in C

++ What did you do to make your code run faster?
Hash tables for the available pieces meeting certain constraints
Hand coded dfs routine...explicit stack 

++ If I had it to do all over - here's what I would try ....
I think that the dumb-dfs system has almost reached its full
potential.  a Genetic Algorithms update engine would almost 
certainly be better than SA, but probably not enough to make a
significant difference...and there were technical problems. 

A more consise representation for the heuristics would help as
the current ones have redundancy which proves very troublesome

I would prefer to try and find one of the more direct methods...
probably still requiring some search, but with a much more guidance
to it.  I suspect that the highest placers are using things along
these lines.  

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Melbourne University---soon to be grad student
working for CSC in London at the moment.
for fun: playing piano, programming, computer games, travelling
inner-most secret: I play Ultima Online  (egad)  but I'll quit.
potm ideas: games...eg card games...removes the need for Fred to
think up test problems.  just make the rules and we can duke it out.

=================================================================

============== 13 ====================== cinderella =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
        cinderella 7.122807    24   812   114 600.00    gc Pavel Uvarov
=================
cinderella submitted by Pavel Uvarov at uvarov@mx.ihep.su
=================
++ Please summarize the algorithm used by cinderella
   The algorithm is very simple. First of all I sort the colors by their
"popularity". That is, the rarest color has the value of 0, the oftenest
has NCOLORS-1. (NCOLORS is the number of colors met in file). After that
I assign each square the value called weight:

/* Calculates weight for square n.
   square[n][j] - color of the j-side of the square n.
   odd[k]=1 if color k is met odd number of times, otherwise it is 0.
   MUL is a parameter.
   The function may be different in future versions.
*/
inline int Weight(int n)
{
  int j, result = 0;
  for (j = 0; j <= 3; j++)
    result += square[n][j] - MUL * odd[square[n][j]];
  return result;
}      

...and I sort the squares by their weights in increasing order.
Constructing a side means finding at least one combination of non-used
squares that fit the colorset on the previous (existing) side. 
Walking in closkwise direction I look for the suitable squares in increasing 
order of index in the sorted array (that is, I first take the square with 
the least weight). If I can't find a suitable square I go back and increase
the index in the sorted array for previous place (I use recursive algorithm, because it's very easy and not so much slow). If I can't construct the side I jump to another. If I can't construct any of the four sides I begin to delete
the last constructed side.
    The main problem of this algorithm is WHAT IS MUL??? I've tested 
cinderella with great number of files and each of them had its own optimal 
MUL. 
    So I decided to look through many MULs in one run. I go through STARTmul to
endMUL (they are somewhat about 0 and 32) for some time (not very large).
Then I take the best MULs (the exact number depends on KnMUL) and test them
for some more time. Then I take the best from them etc. Finally I have one MUL
which is considered to be the best. I run cinderella with this MUL until
time is over. 

++ What did you do to make your code run faster?
   First of all I made arrays meet[][] and meetcorner[][][] in order not to
go through ALL the squares each time. If I want to find a square that must
fit to other square with color k, I only look through those squares that
have that color k (the references to them I can find in meet[k][i], where
i runs 0 to nmeet[k]-1). The same is for corners.
   During making cinderella I tried to avoid the recurse, but I found
that it is much more complicated and not so much faster.
   Some functions I made inline. 

++ If I had it to do all over - here's what I would try ....
   I'd try to break the head of that guy who'd have deleted my cinderella
from the hard disk :)  

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
   I'm a student, leave in Russia in the best town of the world -- Protvino, 
teach physics in the school and sometimes write programs.
   I learned about POTM only 30th of November and as I don't have Internet 
at home I asked my father (who has Internet at his office) to bring me
the latest POTM task. 
   POTM ideas? Yes I have some. For example can anybody write a program
that will take the graphics file with a woman face and say whether it is 
pretty or not? The pretty (and not pretty) faces will determine some
number of men (the jury as you want).
=================================================================

============== 14 ====================== XL =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
                XL 7.122807    25   812   114 596.24     c Ivan Velev

	Sorry ... no description available for XL

=================================================================

============== 15 ====================== snowball =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
          snowball 7.122807    25   812   114 755.71     c Neil Weinstock

	Sorry ... no description available for snowball

=================================================================

============== 16 ====================== Carrion_Chameleon =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
 Carrion_Chameleon 7.122807    25   812   114 4278.26     C Boris Bulayev
=================
Carrion_Chameleon submitted by Boris Bulayev (X-???) at bbboris@rinet.ru
=================
++ Please summarize the algorithm used by Carrion_Chameleon

It took a long time io invent a easy data representation which allows to
quick program's work.

Two parts of my picture describe a quilt 3x3.
At first, I do a block 2x2. For example, I start with an "abcd" item.
Next I select compatible items. On the picture: capitals (B,C,E,F) mean
the letters which must match to the same letter above (B below b, etc).
The 4-th item was found by query "to find one when the 'e' is number N and
the 'f' is number N+3"
------------------------------------------
                   abcd                             a      c
                 caeB              this is        d   b  b   a
                     Cfab          equale to        c      e
                   EprF                             c      e
                                                  b   f  f   p
                                                    a      r
------------------------------------------
This is a block 2x2 items. Next I try to add the strings of items to the
sides of this block (see the continue of the same picture):
------------------------------------------
               klmA
                 MnoP
                       Aijn
                     RghI
                   OvnG
             xxkL
               KzwN
                 WycV
------------------------------------------
There are 3 ladders built by the same rule. Each left ladder adds a line of
items
to the right side of quilt, each right ladder - to the bottom of the quilt.
Analogically, to add a line to the top or left side, it must draw the same
ladders
above the first 2x2 block.
------------------------------------------

++ What did you do to make your code run faster?

1. I wrote each input item like "abcd" as "abcdabc" to make the seeking
easier.

2. I used two z-buffers which descrube the projection of letters array
to the x-axis.

3. I tried also to sort the input items by descending of frequency of
the letters and bigramms - both ideas weren't very effective.

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

I'd tried Pascal - it's quite good exactly for this problem (especially for
my approach to it),
because I can't work normally without "SET" datatype and "POS" function.
I "invented" 2 more approachs but didn't have a time to realize them:

1. direct trying of all variants - it's like grandmother's knitting.
2. twostep process: firstly to do the blocks 2x2 (as many as possible),
keeping in their edges only the "popular" colors and hiding "non-popular"
ones;
next to build a big quilt from these little blocks.

++ COMPANY? LOCATION? JOB? DO FOR FUN?
There is a financial crisis - I don't work now and write my dissertation.
INNERMOST SECRET?
To be like BG.
POTM IDEAS?
Both ideas I've described earlier (Wargame and "dotted" game)

=================================================================

============== 17 ====================== patchouli =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
         patchouli 7.122807    26   812   114 596.07     c Davor Slamnig
=================
patchouli submitted by Davor Slamnig at slamnig@sepia.ocn.ne.jp
=================

++ Please summarize the algorithm used by patchouli

Starting with one square, outer horizontal or vertical rows are repeatedly
added to the existing rectangle - while possible. 

While adding a row an exhaustive search is performed, but the backtracking
doesn't extend to previous rows (the existing rectangle isn't modified).

After each "run" (when no more rows can be added), the resulting rectangle
is evaluated and the best one is stored. 

Also, for each run the order of the squares is randomized. This order will
affect the way the rectangle is built.

The runs are repeated, each using a new starting square, until timeout.

++ What did you do to make your code run faster?

To find a square that fits, i.e. that has one or two consecutive colors
which correspond to the color(s) of adjacent square(s), I built a hash
table which significantly reduces the search time.

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

I'd try to do something a bit less montecarloish - although I've already
thought about this a lot and couldn't find anything more intelligent that
works better than the present version (although I did try a lot of
convoluted clever tricks which didn't). 

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

I work on-line (as a programmer) for TechnoCraft, a small Tokyo-based
company producing automated dictionary software for Windows. I live in
Zagreb, Croatia. Fun? What's fun? I've been building a house for the last 5
years and am planning to move in by Christmas... I've got a 3-year old son
and a wife working for MS-Europe... I'm probably having fun from time to
time but I'm too busy to notice. I play guitar (I'm a pro, but
unfortunately the money's in computers, not music), drink, smoke and solve
POTMs.
=================================================================

============== 18 ====================== PatchMaShirt =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
      PatchMaShirt 7.122807    26   812   114 600.11    gC Mike Goldshteyn

	Sorry ... no description available for PatchMaShirt

=================================================================

============== 19 ====================== SCISSORS =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
          SCISSORS 7.070176    23   806   114 595.47     c Joe Snyder
=================
SCISSORS submitted by Joe Snyder at jsnyder@voicenet.com
=================
++ Please summarize the algorithm used by SCISSORS
Add squares until no more fit, remove the last squares, and try again (brute
force). Try the highest scoring quilts first (for 36 squares, try 6x6 before
7x5).

++ What did you do to make your code run faster?
I built a link list of all C/D sides (for all rotations), so I wouldn't have
to search every square for a match. Duplicates were also handled in the link
list.

++ If I had it to do all over - here's what I would try ....
My program assumes that the first square added is in the bottom left of the
quilt.
I would change it to build in all directions from the first square.
Also I would try a simple breadth-first search.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Competitive Media Reporting
West Chester, PA


=================================================================

============== 20 ====================== The_Gult_Quilt =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
    The_Gult_Quilt 7.000000    23   784   112 525.40    gC Rahul Bhobe

	Sorry ... no description available for The_Gult_Quilt

=================================================================

============== 21 ====================== ColorMeQuilted =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
    ColorMeQuilted 7.000000    24   784   112 479.76     c T.Alexander Popiel
=================
ColorMeQuilted submitted by T.Alexander Popiel at popiel@snugharbor.com
=================
++ Please summarize the algorithm used by ColorMeQuilted

ColorMeQuilted is a basic guess-and-guess-again program.  It picks
a random square to start with, then repeatedly tries to grow the
quilt by adding a line of squares to one of the longest sides.
This growth process uses a brute-force (depth-first search) approach
to finding a line that fits.  When the quilt can no longer be grown,
it's checked against the best quilt made so far, and then the process
starts over.

When the program runs out of time, it just spits out the best quilt
it's made so far.

++ What did you do to make your code run faster?

Well, I played games with representation and memory use again;
instead of building a 2D array with the quilt in it, I just keep
track of the edges and the position/rotation of each square.
When outputting, I sort the squares by position/rotation to get
proper ordering.  This ends up saving a lot of memory, thus
keeping the resident set size low, and the code fast.

I also used linked lists of squares grouped by colors on one side
and colors on two adjoining sides.  This drastically improved
searching for squares that might fit in a growing line.

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

Some ideas that I had but never got around to implementing were
checking for raw square availability during growth, for faster
no-solution detection, and line growth starting from the hardest-
to-match squares, again for faster no-solution detection.  I had
absolutely no ideas on anything better than just repeatedly
growing quilts until something good popped out by chance.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

Company:  Pensare, Inc.  (http://www.pensare.com)
Location: Los Altos, CA, USA
Job:      Coder.  De-facto technical second.
Fun:      Random puzzles, board games, wearable computing.
Secret:   Velcro can be fun.
Ideas:    Uhh... something like sokoban?  Given a layout
          of boulders, a goal square, and a bunch of
          dynamite, how many boulders can you push to
          the goal, while blowing up as few as possible?

=================================================================

============== 22 ====================== Puzzler =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
           Puzzler 7.000000    25   784   112 51.83     c Arturs Zogla
=================
Puzzler submitted by Arturs Zogla at fix.lv!uvsk@kcig2.att.att.com
=================
++ Please summarize the algorithm used by Puzzler
Using a back-tracking algorithm my program tries to put every of the pieces
in the next possible place.

++ What did you do to make your code run faster?
To make my program run faster I didn't try to make every possible rectangle
m*n. The order which I used is:

1.  2.  5.  10. ....
4.  3.  6.  11. ....
9.  8.  7.  12. .....
16. 15. 14. 13. .....
....

This way my program can find only rectangles n*n or n*(n+1).

++ If I had it to do all over - here's what I would try ....
I don't think I would change much, because I haven't found any better
algorithm. One thing I maybe would do is to use all 10 minutes letting my
program find the best possible answer.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm still a 12. grade student of Ugale Secondary School. My best
achievements are produced in programming and that is actually the only thing
which I am developing. 



=================================================================

============== 23 ====================== cherry_baskets =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
    cherry_baskets 7.000000    25   784   112 82.00    gc Justin Legakis

	Sorry ... no description available for cherry_baskets

=================================================================

============== 24 ====================== Square_Quilt =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
      Square_Quilt 7.000000    25   784   112 499.59    gc Lourenco Arnasalon

	Sorry ... no description available for Square_Quilt

=================================================================

============== 25 ====================== Grannys_Cyber_Tailor =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
Grannys_Cyber_Tailor 6.991071    26   783   112 597.58     c Ramkumar Srinivasan
 =================
 Grannys_Cyber_Tailor submitted by Ramkumar Srinivasan 
	at ramkumar@giasbga.vsnl.net.in
 =================
 ++ Please summarize the algorithm used by Grannys_Cyber_Tailor

	Well...its called Brute force. You would have read a lot
	about it in the above writeups of other people. The program
	trys different combinations in the given time of 10 minutes
	& picks the best among them.
 
 ++ What did you do to make your code run faster?

	Ummm.... I dont think i did any thing worth mentioning. 
	Ah... using char variables instead of ints where ever 
	possible improved the speed a bit. Other than this nothing
	else i guess.
 
 ++ If I had it to do all over - here's what I would try ....
 
	Well i recently purchased a book on AI. If Fred gave me 
	a year or so...maybe i'll read the book & conjure up a
	new Algo.

 ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
 
	Iam 19 years old, Iam doing a bachelors engg in electronics.
	I live in Bangalore, India. For fun i sleep ... the dreams i
	get are more thrilling than a Blockbuster movie.
	Innermost secret : Freds my uncle & he send me all the source
	code for testing. :)  ----- iam Joking dudes.

	POTM ideas : A program which generates a new POTM idea every
	time you execute it... it will solve freds problems for ever.

	THANKS Fred for conducting this lovely contest.
	Merry Christmas & A very Happy New year to all !! 

=================================================================

============== 26 ====================== knit_1 =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
            knit_1 6.872727    25   756   110 77.06  PERL Rocco Caputo
=================
knit_1 submitted by Rocco Caputo at troc@netrus.net
=================
++ Please summarize the algorithm used by knit_1

Outer loop (build quilts):
* Build quilts, willy-nilly, discarding all but the best quilt.
* Quit if time runs out.
* Quit if a sufficient level of confidence has accumulated for the
best quilt found so far.

"Confidence" is defined in a few different ways:
* It is set to 0 when a new best quilt is found.
* It increases gradually with the number of subsequent inferior quilts.
* It increases by QUILT_AREA / TOTAL_INPUT_TILES as new quilts are
found that match the current best quilt's score.

"Sufficient" is defined as 1000 / TOTAL_INPUT_TILES.  This allows
the program to try more quilts for smaller input.  This is a win for
two reasons: it can create quilts faster with a small pool, and it
tends to do worse with fewer tiles to choose from.


Middle loop (build a quilt):
* Start with a "randomly" chosen seed square.
* Build new edges, preferring shorter sides to maintain squareness.
* Quit if no new edges can be found.


Inner loop (build an edge):
* Perform a depth-first search for a series of tiles that match the
edge we're looking for.
* Choose tiles with the most popular colors first, except when panicking
(see below).
* Short-circuit tile selection by performing a one-tile lookahead.
Don't choose tiles that will immediately lead to dead ends.
* Quit if confidence or time runs out.

"Confidence" here decreases as the number of permutations increases.
This prevents an infinite or overtime loop.

It is assumed at certain "milestone" levels of confidence that the
permuter is stuck, so the search depth is cut by a percentage that
increases per milestone.  So it's reduced by perhaps 1/10 at first,
increasing to 9/10ths near the end.

Right before the end, the permuter "panics" and assumes that an
orderly search isn't going to work.  It begins selecting tiles at
random instead of according to color popularity.


++ What did you do to make your code run faster?

The most important speed optimization was finding an time-efficient
way to store tiles.  Tiles are stored in hash buckets according to
two-edge runs.  The tile ABCD is stored in buckets AB, BC, CD and DA.

These runs correspond to the color of an existing quilt edge and the
edge of the previously placed tile.  Consider:

    A  C
   D BB D
    C  A
       A
      D B
       C

The next tile to place requires a CD run, and finding it is a single
hash lookup.  Keeping most of the work in the native-C runtime library
makes this a lot faster than doing it in bytecodes.

Secondly, because knit_1 takes a willy-nilly approach to building
tiles, knowing when to stop is a major win.  There are lots of little
bailout checks throughout.

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

... entering the contest earlier.  Then I could try more things and
tweak the bailouts to be more optimum over the range of possible input
types.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

Please upgrade POTM's Perl to version 5.004_04 or later.
 
=================================================================

============== 27 ====================== Stitch_n_Time =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
     Stitch_n_Time 6.872727    26   756   110 18.96     c Andrew Gauld

	Sorry ... no description available for Stitch_n_Time

=================================================================

============== 28 ====================== quilt_assembler =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
   quilt_assembler 6.872727    26   756   110 580.03    gc John FitzGerald

	Sorry ... no description available for quilt_assembler

=================================================================

============== 29 ====================== Quilt_Quest =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
       Quilt_Quest 6.763637    25   744   110 597.05     c Jan Doornaert
=================
Quilt_Quest submitted by Jan Doornaert at BlackAdder@cyberdude.com
=================
++ Please summarize the algorithm used by Quilt_Quest

    Very straightforward recursive algo. Just goes round and round
    a pseudo-randomly chosen quilt.

++ What did you do to make your code run faster?

    Nothing, really. Didn't have the time (or the knowledge :-).

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

    Make it work ?

    I still have a few unimplemented ideas to prune some more very
    obvious dead-end recursion paths (which could make the algo run
    a bit faster and/or enable it to check more (or more viable)
    configurations). Too bad I only joined a few weeks before the
    deadline...

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

    COMPANY ?

        Barco Graphics

        Tramstraat 69
        B-9052 Gent (Zwijnaarde)
        Belgium

    JOB ?

        Software Engineer

    FOR FUN ?

        Yes, my job *is* fun. Sometimes.

        Programming, reading books (SF, Fantasy).

    INNERMOST SECRET ?

        Still looking for it. It's hidden quite well.
        Not even sure there actually *is* one, to be honest.

    POTM IDEAS ?

        Contradictio in terminis ?

        I want to join as soon as there is a new contest. Hopefully,
        there will be one before the Xmas holiday starts, so I can
        start thinking/coding during the holidays...


=================================================================

============== 30 ====================== SaveNine =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
          SaveNine 6.740741    25   728   108 47.49    gC Joe Vollbrecht
=================
SaveNine submitted by Joe Vollbrecht at jvollbrecht@att.com
=================
++ Please summarize the algorithm used by SaveNine
start with a single square; add a column to the right, then a row to the
top, until no more can be added.
repeat using each square as a starting point.

++ What did you do to make your code run faster?
it's such a simple (and bad) algorithm that it didn't need tuning

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

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
=================================================================

============== 31 ====================== MatchAndPatch =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
     MatchAndPatch 6.622642    25   702   106 300.66    gc Corin Anderson
=================
MatchAndPatch submitted by Corin Anderson at corin@cs.washington.edu
=================
++ Please summarize the algorithm used by MatchAndPatch

Starting with an empty quilt, I iteratively try to extend the
quilt on a side selected at random.  If there's no permutation of
the tiles that will extend the quilt along that side, I chalk up
a failure.  I restart with a new, empty quilt after I've failed a
couple of times.  I wait for a few failures because the inability
to extend the quilt, say, North, doesn't imply the inability to
extended it East or South.  The psueudocode:

Iterate until out of time:
  Quilt <- empty
  Repeat until we "fail" a couple of times:
    Pick a side of the quilt
    Try adding a new line of tiles to that side.  If we can't
     add in tiles along the entire side, then "fail".  Else,
     continue
  If this quilt is better than what we used to have, save
   this quilt


++ What did you do to make your code run faster?

I actually didn't explicitly /do/ much to accelerate my code.  I
concentrated on keeping my code clean and simple.  I actually
have several places where I index into arrays or create 2D
arrays, which could have been replaced with faster counterparts.
But the faster counterparts would have obfuscated the code, and I
don't really think that I needed that much more speed.  It
appears that I usually find my best solution within about a
minute of two of running, if not well before then.


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

I would put more thought and code into a heuristic to suggest
which tile to use when.  In the current code, I'm happy when I
find a bunch of tiles that will extend my quilt.  But I'm
settling on the first set of legal tiles.  Might there be better
tile choices?  Perhaps tiles whose sides have colors in common
with many other tiles?  Or, if the side is on the edge of the
quilt, favor tiles that don't have many common colors with other
tiles (and thus don't interlock well).


++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

I'm a third year graduate student at the University of Washington
in Seattle, WA.  [Come visit my web page -- the URL should sound
familiar! 8) http://www.cs.washington.edu/homes/corin/] 

Being a grad student occupies most of my time, but I somehow also
squeeze in development work for XFree86, contract coding for NASA
Ames Research Center, and, of course, the POTM.  What I do for
fun is, for better or worse, the same list (XFree86, ...).  When
I do get torn away from the computer, I'm usually shooting arrows
at the archery range on UW campus, or perhaps running along the
Burke-Gilman trail in the University District.


=================================================================

============== 32 ====================== SearchAll =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
         SearchAll 6.433962    24   682   106 598.00     C Mathijs Vogelzang

	Sorry ... no description available for SearchAll

=================================================================

============== 33 ====================== bzzz =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
              bzzz 6.210000    26   621   100 590.20     c R. Ashenfelter
=================
bzzz submitted by R. Ashenfelter at ashe@submarinesystems.com
=================
++ Please summarize the algorithm used by bzzz

1.  Choose a random square and a random orientation to start.

2.  Try to add a new row at the bottom.  This involves searching
    the unused squares for one that can be matched to the bottom-
    left corner and then searching for one that fits next to this,
    etc. until you get to the right edge of the quilt.  If a square
    that fits can't be found, return all the squares in the new
    row to the unused list and either try again or continue...

3.  Rotate the quilt 90 degrees and go back to step 2.

4.  If all four sides have been tried and nothing has been added,
    give up and consider the quilt finished.

5.  Score the quilt and compare it to the best found so far.  If
    it scores higher (or the same and has fewer perimeter colors),
    save it as the best so far.

6.  Continue doing steps 1 to 5 until time runs out.

7.  Print out the best quilt and quit.

++ What did you do to make your code run faster?

1.  Don't count the perimeter colors unless necessary, i.e. the score
    is the same as the best previous.

2.  This algorithm has a tendency to construct long, skinny quilts
    in which it incorporates almost all the squares but gets a low
    score because the quilt is too nonsquare.  This is avoided by
    not adding to the short sides of a such a quilt.  This really
    saves a lot of wasted time.

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

    Not very much.  I tried taking the best quilt after most of the
    time was used up and trying to add to it alone for the rest of
    the time,  but I didn't get it debugged (made nice large quilts,
    but re-used squares) so I ripped it out.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

    Tyco Submarine Systems, Ltd.  (Was AT&T Submarine Systems, Inc.,
    but was sold by AT&T last year to Tyco International, Ltd.)

    Holmdel, N.J., but will move to Eatontown, N.J. early next year.
    (No change in e-mail address.)

    Electro-optical systems design (hardware, not software).

    Bicycling, grow orchids, travel.

    Hah!

    Nothing new...

=================================================================

============== 34 ====================== Quilt_by_Association =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
Quilt_by_Association 5.488636    26   483    88 570.06     c Randy Saint
=================
Quilt_by_Association submitted by Randy Saint at saint@phoenix.net
=================
++ Please summarize the algorithm used by Quilt_by_Association
Brute force.  It builds quilts until time runs out.
Conceptually, it starts with the middle piece and tries to build
onto each side.  It builds a side by finding the first piece that
fits along the side, then the first piece that matches the next 
spot on the side, and so on until the side is complete, or one 
spot can't be filled by any of the remaining pieces.  In this case, 
it marks the side as uncompletable.  When all 4 sides are 
uncompletable, it's done with that quilt.  Save it if it's the best 
so far.  Repeat until time runs out.

++ What did you do to make your code run faster?
Faster? Ha!  I didn't do any type of optimization.  I didn't really
see any opportunity, given the simpleness of the algorithm.

++ If I had it to do all over - here's what I would try ....
I would try to come up with some better algorithm.  I couldn't
come up with any measurement or heuristic that would tell me how
well the current quilt was coming along and/or expectations for
whether this quilt would maximize the ratio or minimize the colors.
Hence this brute-force, shotgun type approach.  
There's got to be a better way...

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lockheed Martin, Houston TX.
I'm the Unit Manager for the Planning Software for the International 
Space Station and Space Shuttle at NASA Johnson Space Center.
Fun? Programming Contests, of course!
Secret?  I'd like to know if anyone finds my Programming Contests
page useful.  http://www.c-com.net/~saint/contests/
Ideas? Turing Test.
=================================================================

============== 35 ====================== galois_fan =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
        galois_fan 5.372093    26   462    86 149.98    gC Emil Ong
=================
galois_fan submitted by Emil Ong at emilong@midway.uchicago.edu
=================
++ Please summarize the algorithm used by galois_fan
The quilt was constructed row, column, row, column, etc.
++ What did you do to make your code run faster?
Very little.
++ If I had it to do all over - here's what I would try ....
I would build a tree that mapped the possibilities for each square given and
return the best one found.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Nope.

=================================================================

============== 36 ====================== notQuilty =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
         notQuilty 5.238095    24   440    84 297.29     F Keith Blow
=================
notQuilty submitted by Keith Blow at keith.blow@bt-sys.bt.co.uk
=================
++ Please summarize the algorithm used by notQuilty
First I reordered the tiles so that the most common colours appear early
in the list. Then I start a quilt with each tile in each orientation. In
building a quilt I alternated between adding columns and rows.
I added a routine to reduce the number of colours on the edge by
swapping with the unused tiles but it rarely made any difference.

++ What did you do to make your code run faster?
Not really needed.

++ If I had it to do all over - here's what I would try ....
I should have allowed the search to go deeper than 'best first tile'.

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
BT Laboratories
Martlesham Heath, UK
Optical communications research
Just for fun but it helps to excercise my programming skills.

=================================================================

============== 37 ====================== Grannys_quilt =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
     Grannys_quilt 3.500000    18   196    56 .26     c Ajay Mulani

	Sorry ... no description available for Grannys_quilt

=================================================================

============== 38 ====================== ugleeee =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
           ugleeee 3.428571    21   192    56 200.26    SH Fred Hicinbothem
=================
ugleeee submitted by Fred Hicinbothem at potm@att.com
=================
++ Please summarize the algorithm used by ugleeee
An experiment in Korn shell programming.  Start at the center
and select a square - then spiral outward adding a row or a
column at a time.  Keep adding until you can't add any more
rows or columns.  The mystery is how to choose which square
to select when more than one can fit in a position - I tried 
various orderings of the squares having to do with the frequency
of the colors in the square (i.e. select the square with the most
common colors first was my final decision).

++ What did you do to make your code run faster?
When you're using greps and seds to do the work, there really
isn't much point ...

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

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T in beautiful Lincroft, New Jersey.  Ultima Online, the POTM,
and family occupy my spare time.  My secret:  I'm still trying to
figure out what the next POTM will be, so SEND IDEAS!!!

=================================================================

============== 39 ====================== Steppdecke =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
        Steppdecke 3.120000    17   156    50 1.68  JAVA Jim Rothenberger

	Sorry ... no description available for Steppdecke

=================================================================

============== 40 ====================== Clintons_shorts =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
   Clintons_shorts 0.250000     1     1     4 .02     c M.Huys F.Vernaillen

	Sorry ... no description available for Clintons_shorts

=================================================================

============== 41 ====================== singleton =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
         singleton 0.250000     3     1     4 .01     c Bruce Mycroft
=================
singleton submitted by Bruce Mycroft at bmycroft@acm.org
=================
++ Please summarize the algorithm used by singleton
Assume at least one square exists.  Use it.  Just the one, thank you.  Don't
bother rotating it. 

++ What did you do to make your code run faster?
Nothing.  I hoped it would be slow enough.

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

I would have added a delay to ensure I came in last (of the entries that
have valid scores).  (I knew I wouldn't have time to develop a program that
would rank first, so I was willing to settle for last.  There's only one
last place--much like there's only one first place.)

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

Montana.  Software Engineer.  Play with my children and read a lot.


=================================================================

============== 42 ====================== darn =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
              darn 0.250000     3     1     4 .02     C D. Wells

	Sorry ... no description available for darn

=================================================================

============== 43 ====================== warm_and_different =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
warm_and_different 0.000000     0     0     0 .33  JAVA Denis Konovalchik

	Sorry ... no description available for warm_and_different

=================================================================

============== 44 ====================== cranky =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
            cranky 0.000000     0     0     0 1.46  PERL Joshua Weinberg

	Sorry ... no description available for cranky

=================================================================

============== 45 ====================== Stranglehold =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
      Stranglehold 0.000000     0     0     0 11.24  PYTH Joseph DeVincentis
=================
Stranglehold submitted by Joseph DeVincentis at devjoe@wilma.che.utexas.edu
=================
++ Please summarize the algorithm used by Stranglehold

Very simple, I never really got time to complete it.  It weights the squares
by the total number of occurrences of each of their colors, uses the highest
weighted squares first, and spirals outward adding a row or column at each
pass, trying each side in order.  It's supposed to back up on some failures
to try and modify the previous row/column in order to try to find a match,
but I never finished that code.

++ What did you do to make your code run faster?

Never got to that point.

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

Not getting involved with so many other things that ate up the time I
might have otherwise spent on POTM.  Not trying to get a job and move
during the course of the problem. :-)

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?

In January I am starting a job with Aspen Technology in Boston.  Previously
I have been a graduate student at the University of Texas at Austin.  Hence,
I am moving in the interim.  
=================================================================

============== 46 ====================== hash-quilter =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
      hash-quilter 0.000000     0     0     0 543.16  PERL Tramm Hudson

	Sorry ... no description available for hash-quilter

=================================================================

============== 47 ====================== myTshirt =============

=================================================================

            ENTRY       RATIO COLS AR  PER  TIME  LANG    WHO
    ----------------    ----- ---- --- ---- ----  ----  -------------
          myTshirt 0.000000     0     0     0 580.35     C Trieu Nguyen
=================
myTshirt submitted by Trieu Nguyen at trieu@ix.netcom.com
=================
Sorry it's final time at my school. I just put some short answer.

++ Please summarize the algorithm used by myTshirt
    My program uses backtracking to find all possible combinations.

++ What did you do to make your code run faster?

   - The started square is very important. My programs run 10 times, each 1
	min, for 10 different squares, and choose the best.
  -  I only find the rectangle n x n or (n+1) x n to run faster.

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

++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
    Student. Senior level. UC Berkeley. Looking for a job for next year :-)
    Why dont we write some kind of game to compete with each other.

=================================================================












Make your own free website on Tripod.com