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.
=================================================================