Thread Subject:

MATLAB Programming Contest: November 3-10, 2004

The next MATLAB Programming Contest will start tomorrow at 9 a.m. EST
and run through Wednesday, November 10 at 5 p.m. EST. Topics and
rules will be posted on the morning of the contest:

 <http://www.mathworks.com/contest/>

Due to popular demand, the format will be similar to the last contest
with darkness and twilight stages. During the darkness stage, code
and scores of submissions will not be visible to others, while in the
twilight stage, only the scores can be seen. We'll also be holding
several mid-contest prize giveaways of MATLAB T-shirts, jackets, and
other good stuff, so don't wait until the last minute to participate.


Please use this thread to talk about the contest, strategies, or to
ask related questions. If you have an "administrative" type of
question that you don't feel applies to anyone else, e-mail us at
contest@mathworks.com.

We look forward to seeing your entry. Good luck!

- The MATLAB Contest Team -

Min Poh wrote:

> During the darkness stage, code
> and scores of submissions will not be visible to others, ...

I forget. During the darkness stage, will the entries at least be
run so that we know if they pass the contest suite?

Good luck everyone. Min, please post the location of the ZIP file
containing the "runcontest" scoring function.

cyclist, in Darkness you don't receive any feedback from us at all,
not even pass/fail. In Twilight, you can see the scores but not the
entries. In Daylight, you can see everything.

Will the final solution always be attainable? For example, if the
room was only one unit high, it is impossible to switch the order of
any of the pieces of furniture.

Thanks,
 Mike

Yes, Mike, there will always be a solution.

Hey mathew can you post the location of the .Zip file thanks!!!!

I am getting "Page not found" errors when I try to download from the
File Exchange.

Anyone else having problems?

"Matthew Simoneau" <matthew@mathworks.com> wrote in news:eeefd44.4
@webx.raydaftYaTP:

> Yes, Mike, there will always be a solution.

I don't know about that. The common puzzle where you have 15 tiles and a
free space in a 4x4 grid, and have to translate one puzzle piece at a time
to the free space to reconstruct the picture does not seem to be solvable.
I base this on childhood efforts to break the puzzle apart, put it back
together, and try to reconstruct it. So, I'd guess that 15 pieces of
furniture in a 4x4 grid will not be solvable.

Scott

In the example provided, aren't you missing a duplicate [3 3 ] move ?

aInit = [ 4 0 0 3 ;
           0 0 0 0 ;
           0 0 0 0 ;
           1 2 0 0 ]

aFinal = [ 0 0 0 4 ;
           0 0 0 0 ;
           0 2 3 0 ;
           0 1 0 0 ]

wt = [ 5
       10
       20
        1 ];

One solution is
move = [ 3 4
         3 3
         4 2
         4 2
         4 2
         2 1
         1 2]

It took unexpectedly long for our clustered server environment to
mirror the file out to all locations, but it is all OK now. You can
find the download here:

 <http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6177>

Sorry about the confusion.

Scott Seidman wrote:
>
>
> "Matthew Simoneau" <matthew@mathworks.com> wrote in
news:eeefd44.4
> @webx.raydaftYaTP:
>
>> Yes, Mike, there will always be a solution.
>
> I don't know about that. The common puzzle where you have 15 tiles
> and a
> free space in a 4x4 grid, and have to translate one puzzle piece at
> a time
> to the free space to reconstruct the picture does not seem to be
> solvable.
> I base this on childhood efforts to break the puzzle apart, put it
> back
> together, and try to reconstruct it. So, I'd guess that 15 pieces
> of
> furniture in a 4x4 grid will not be solvable.

You are mistaken. The 15-tile puzzle is solvable UNLESS two tiles
are swapped, relative to the solved configuration.

is it legal to use embedded functions ?
because once it was not...

"the cyclist" <thecyclist@gmail.com> wrote in news:eeefd44.10
@webx.raydaftYaTP:

> You are mistaken. The 15-tile puzzle is solvable UNLESS two tiles
> are swapped, relative to the solved configuration.
>
>

That's what I mean. If you put the tiles in randomly to start, there are
configurations that are not reachable given an initial condition.

Scott

The MATLAB Contest Team:

a minor inconvenience: no link for contest ZIP-file:)

>
> That's what I mean. If you put the tiles in randomly to start,
> there are
> configurations that are not reachable given an initial condition.

The initial condition should have the same oddity of permutation to
make the puzzle solvable.

An initial solution can be the following:

-Fill the entire room with weights except one place both in the
initial and final rooms (These fillings should have the same oddity
as explained above).

-Create the solution mechanically for the puzzle.

-Remove the movements of the added weights (because these weights
simply not exist).

-Refine the path of each element by ordering and substituting the
movements.

Probably this can work.

Laszlo

Guy S wrote:
> In the example provided, aren't you missing a duplicate [3 3 ]
move?
>
> aInit = [ 4 0 0 3 ;
> 0 0 0 0 ;
> 0 0 0 0 ;
> 1 2 0 0 ]

Hello Guy:

You are correct. The matrices as shown in the illustration (3x4) did
not match the matrices shown in the text example (4x4). The text has
been corrected so that now the move list is accurate.

-Ned Gulley.
Contest Team
gulley@mathworks.com

Min Poh wrote:
>
> We look forward to seeing your entry. Good luck!
>
> - The MATLAB Contest Team -

I am running M5.3, looks like the matworks provided scripts don't
run. M5.3 Doesn't like || and && (so silly) nor "continue" (can fix
all of that), but then I get an error on line 57 in runcontest, the
line that reads "if any(round(mv...)); The error is "index exceeds
matrix dimentions", but I can't tell so quickly which index is
causing the problem.

Anyone experienced this?

GaRZoL, when you say "embedded functions", do you mean private or
nested functions? These are OK. We disallow function handles or the
use of FEVAL because of security reasons. Overall, the rules are
basically the same as past non-golf contests (MATLAB Golf is more
restrictive).

> I am running M5.3, looks like the matworks provided scripts don't
> run. M5.3 Doesn't like || and && (so silly) nor "continue" (can fix
> all of that), but then I get an error on line 57 in runcontest, the
> line that reads "if any(round(mv...)); The error is "index exceeds
> matrix dimentions", but I can't tell so quickly which index is
> causing the problem.
>
> Anyone experienced this?
I'm using Matlab5.2, and after replacing the && and || by & and | (in
runcontest.m and solver.m), it worked fine (but slow).

Stijn

Stijn Helsen wrote:
>
>
>> I am running M5.3, looks like the matworks provided scripts
don't
>> run. M5.3 Doesn't like || and && (so silly) nor "continue" (can
> fix
>> all of that), but then I get an error on line 57 in runcontest,
> the
>> line that reads "if any(round(mv...)); The error is "index
> exceeds
>> matrix dimentions", but I can't tell so quickly which index is
>> causing the problem.
>>
>> Anyone experienced this?
> I'm using Matlab5.2, and after replacing the && and || by & and |
> (in
> runcontest.m and solver.m), it worked fine (but slow).

I am in fact 5.2 as well, but what about "continue"? That is not part
of this version of Matlab, what did you do. Is it the reverse of
break? The cause of my error is that for the first sample the solver
with these fixes doesn't find a solution!
I changed the three cases with "continue" in solver.m to break, and
inverted the if statements that preceed it.

Will all entries begin as if from a "fresh" Matlab session?

Specifically, will the random number generator always start in state
0?

In the solver.m that was contained in the .zip files, the increment
tables are defined:
 
% Make increment tables
% N=1, E=2, S=3, W=4
I = [0 1 0 -1];
J = [1 0 -1 0];
 
If I is the row index, and J is the column index, then the tables
listed as shown above are somewhat confused. That is, according to
the table N=2, E=1, S=4, W=3. I realize that it doesn't really
matter how you define them, but I in case I'm missing something I
thought I'd ask.
 
thanks,
trevis

Leendert Combee wrote:

>>> I am running M5.3, looks like the matworks provided scripts
> don't
>>> run. M5.3 Doesn't like || and && (so silly) nor "continue"

Ok, fixed this now. it's working. Anyway, I can see this script is
not much use, waaaay too slow.

cyclist, we reset the random number generator before running each
entry so that re-running the same code gives the same answer. What
state specifically we set is a secret. It doesn't really matter,
however, since the test suite we use is not the same as the one we
distribute, so the result will be different anyway.

Trevis Crane wrote:
>
>
> In the solver.m that was contained in the .zip files, the increment
>
> tables are defined:
>
> % Make increment tables
> % N=1, E=2, S=3, W=4
> I = [0 1 0 -1];
> J = [1 0 -1 0];
>
> If I is the row index, and J is the column index, then the tables
> listed as shown above are somewhat confused. That is, according to
> the table N=2, E=1, S=4, W=3. I realize that it doesn't really
> matter how you define them, but I in case I'm missing something I
> thought I'd ask.
>
> thanks,
> trevis

I do think the the N E S W given are a little bit confusing.

If I am not wrong, tables should be:
I = [-1 0 1 0];
J = [0 1 0 -1];

that is,
if N, set row = row - 1 = row + I(1)
if E, set col = col + 1 = col + J(2)
if S, set row = row + 1 = row + I(3)
if W, set col = col - 1 = col + J(4)

not those given in sample
% N=1, E=2, S=3, W=4
I = [0 1 0 -1];
J = [1 0 -1 0];

it acutally defines
E=1,S=2,W=3,N=4

anyway, since the table in runcontest.m uses the above form, it will
not affect the result as long as we follow the implication,

but, for conveniences, the issue should be clarified.

> I am in fact 5.2 as well, but what about "continue"? That is not
> part
> of this version of Matlab, what did you do. Is it the reverse of
> break? The cause of my error is that for the first sample the
> solver
> with these fixes doesn't find a solution!
> I changed the three cases with "continue" in solver.m to break, and
> inverted the if statements that preceed it.
Yes, that's right. I didn't change it this way (because break
doesn't seem to be right), but I inverted the tests, and removed the
continue and end statements. The end's were then put at the end of
the loop.

Michael Kleder reported a bug in the error checking in runcontest.
Since "a" and "af" are matrices, line 88 of runcontest.m should be
"if any(a(:)~=af(:))". We updated the download and everyone should
update their local copies. Thanks Mike!

> % Make increment tables
> % N=1, E=2, S=3, W=4
> I = [0 1 0 -1];
> J = [1 0 -1 0];
>
> If I is the row index, and J is the column index, then the tables
> listed as shown above are somewhat confused. That is, according to
> the table N=2, E=1, S=4, W=3. I realize that it doesn't really
> matter how you define them, but I in case I'm missing something I
> thought I'd ask.
Especially by starting before having runcontest I had troubles with
this confusion too.

In the suite of test cases, scenarios # 7, 19 and 28 have objects
with negative weights.

Michael Kleder wrote:
>
>
> In the suite of test cases, scenarios # 7, 19 and 28 have objects
> with negative weights.

I sincerely hope that there are no negative-weight objects in the
actual contest suite. If so, the flavor of the problem changes
drastically. The solutions will not only have to have the correct
final position, but will also have to have a component which wiggles
one of the negative-weight objects as many times as possible in the
time alloted, to minimize the work units.

the cyclist wrote:
>
>
> Michael Kleder wrote:
>>
>>
>> In the suite of test cases, scenarios # 7, 19 and 28 have
objects
>> with negative weights.
>
> I sincerely hope that there are no negative-weight objects in the
> actual contest suite. If so, the flavor of the problem changes
> drastically. The solutions will not only have to have the correct
> final position, but will also have to have a component which
> wiggles
> one of the negative-weight objects as many times as possible in the
> time alloted, to minimize the work units.

It is an interesting finding, i actually submit a version called fun
to let negative blocks do back and forth up to many many times.
Finally I　achieve negative scores in local test suite.

anyway, this flaw is still fine for organizers, because we are at the
darkness stage. They can simply change the negative to positive, and
reevaluate all submissions.

cyclist, Michael, and wu,

The negative weights were unintentional. We don't have any in the
real test suite. We'll update the sample test suite to avoid
confusion. Thanks for pointing this out.

I'm just wondering if we can assume that the example solver.m
provided will work with test cases against which our programs will be
run.

Specifically I think if there was a densely populated room eg. 5x5
with 24 pieces of furniture the sample solver.m would probably time
out. Solutions for a densely populated room will probably be of a
different style than those for a sparsely populated one....

Randy Poe wrote:

> What this proves to me immediately is that so long as
> there is more than one empty space, a solution exists.

Nitpick (and silly) counterexample: The 1xN room.

Does it matter if my solver has an extra output? I'm using it for
diagnostic and recursive purposes, but it says in the rules that
there must be only one output. I'm wondering whether that is really
required, or whether it is just that the first output had better be a
move list.
Thanks,
  Mike

Mike Bindschadler wrote:
>
>
> Does it matter if my solver has an extra output? I'm using it for
> diagnostic and recursive purposes, but it says in the rules that
> there must be only one output. I'm wondering whether that is
> really
> required, or whether it is just that the first output had better be
> a
> move list.
> Thanks,
> Mike

I think you can put your recursion under the solver function

mv = solver(ai,af,w)

[a,b,c] = myf(.... )

function [a,b,c] = myf (... )

....

myf(....)

....

Klass, the real rest suite is similar in character to the one that we
distributed. Your entry's performance on it should roughly match the
sample. Know, however, that the scoring machine is only an 800Mhz
P3. Code runs roughly 3x slower on it than my 3GHz P4. The biggest
risk during darkness is that an entry may time out after the 2.5
minute limit.

Mike, I recommend stripping off the extra outputs before submitting
your code. It only takes a second. Even if it doesn't cause a
problem now, I haven't checked, it may make your code less robust to
future changes in the testing architecture.

Nice.

Randy Poe wrote:
> Proof:
> The reason is that in a fully-populated room (one
> empty space) you have a slider puzzle. All states of
> the same parity in a slider puzzle are reachable.
> If you have two empty spaces, then by treating one
> empty space as a tile E, you can change the parity
> by sliding any tile into that space. You've accomplished
> a swap of tile and E, i.e. a parity flip.
>
> - Randy
>
>

He, I see from the first table of scores that's coming up now that
CPU weight is very very low, in fact it doesn't really matter in the
final cpu time is as long as ones stays within limit. (well, until
entries start to become very very close as I expect during daylight
times).

Compare best entry sofar by Stijn vs Mike.....

What's the length column?

!!!A Big Confused Problem for me!!!

I find so called "increment tables" in the testsuite(smaple), are not
consistent with the explanation on the contest's homepage.
(but no body submit this problem?)
for instance, I run the following code(testsuit zip file is
Updated^_^):

ai = [ 4 0 0 3 ;...
           0 0 0 0 ;...
           1 2 0 0 ];
       
af = [ 0 0 0 4 ;...
           0 2 3 0 ;...
           0 1 0 0 ];
     
w = [ 5;10;20;1 ];

mv = solver(ai,af,w)

a result is:
mv =

     3 3
     3 1
     3 2
     2 4
     3 2
     3 3
     3 4
     1 1
     4 1
     4 1
     4 1

but in the hompage:
"
One solution is
move = [ 3 4
         3 3
         4 2
         4 2
         4 2
         2 1
         1 2]

"

see [2 4] vs [2 1]
block#2 shold go where?

In fact:
according to the homepage, the true "increment tables" is :
% N=1, E=2, S=3, W=4
% By Matrix Direction
I = [-1 0 1 0];
J = [0 1 0 -1];

not the testsuit solver's:
% N=1, E=2, S=3, W=4
I = [0 1 0 -1];
J = [1 0 -1 0];

Any Comments?
(The entry which comply with the homepage will not pass the testsuit
without modification)

The solver.m file that was supplied is completely random, so there's
no reason to expect it to pick out the "right" moves as they were
chosen on the rules page. Hence on average, that algorithm requires
more moves in order to arrange the furniture.

Concerning the increment tables -- what you call North, South, etc.
is completely irrelevant as long as you have a complete and
non-degenerate set. For ease of use in submission, just go with what
they supplied and then you won't have to worry about it.

trevis

Jin wrote:
>
>
> !!!A Big Confused Problem for me!!!
>
> I find so called "increment tables" in the testsuite(smaple), are
> not
> consistent with the explanation on the contest's homepage.
> (but no body submit this problem?)
> for instance, I run the following code(testsuit zip file is
> Updated^_^):
>
> ai = [ 4 0 0 3 ;...
> 0 0 0 0 ;...
> 1 2 0 0 ];
>
> af = [ 0 0 0 4 ;...
> 0 2 3 0 ;...
> 0 1 0 0 ];
>
> w = [ 5;10;20;1 ];
>
> mv = solver(ai,af,w)
>
> a result is:
> mv =
>
> 3 3
> 3 1
> 3 2
> 2 4
> 3 2
> 3 3
> 3 4
> 1 1
> 4 1
> 4 1
> 4 1
>
> but in the hompage:
> "
> One solution is
> move = [ 3 4
> 3 3
> 4 2
> 4 2
> 4 2
> 2 1
> 1 2]
>
> "
>
> see [2 4] vs [2 1]
> block#2 shold go where?
>
> In fact:
> according to the homepage, the true "increment tables" is :
> % N=1, E=2, S=3, W=4
> % By Matrix Direction
> I = [-1 0 1 0];
> J = [0 1 0 -1];
>
> not the testsuit solver's:
> % N=1, E=2, S=3, W=4
> I = [0 1 0 -1];
> J = [1 0 -1 0];
>
> Any Comments?
> (The entry which comply with the homepage will not pass the
> testsuit
> without modification)

Jin:

You are correct, when we were playing with our crappy solver at some
point we changed the tables but not the comments. You should follow
the explanation on the contest's homepage, or Travis post who pointed
this problem before.

Lucio Cetto
-Contest Team

Jin wrote:
>
>
> !!!A Big Confused Problem for me!!!
>
> I find so called "increment tables" in the testsuite(smaple), are
> not
> consistent with the explanation on the contest's homepage.
> (but no body submit this problem?)
> for instance, I run the following code(testsuit zip file is
> Updated^_^):
>
> ai = [ 4 0 0 3 ;...
> 0 0 0 0 ;...
> 1 2 0 0 ];
>
> af = [ 0 0 0 4 ;...
> 0 2 3 0 ;...
> 0 1 0 0 ];
>
> w = [ 5;10;20;1 ];
>
> mv = solver(ai,af,w)
>
> a result is:
> mv =
>
> 3 3
> 3 1
> 3 2
> 2 4
> 3 2
> 3 3
> 3 4
> 1 1
> 4 1
> 4 1
> 4 1
>
> but in the hompage:
> "
> One solution is
> move = [ 3 4
> 3 3
> 4 2
> 4 2
> 4 2
> 2 1
> 1 2]
>
> "
>
> see [2 4] vs [2 1]
> block#2 shold go where?
>
> In fact:
> according to the homepage, the true "increment tables" is :
> % N=1, E=2, S=3, W=4
> % By Matrix Direction
> I = [-1 0 1 0];
> J = [0 1 0 -1];
>
> not the testsuit solver's:
> % N=1, E=2, S=3, W=4
> I = [0 1 0 -1];
> J = [1 0 -1 0];
>
> Any Comments?
> (The entry which comply with the homepage will not pass the
> testsuit
> without modification)

Lucio Cetto:

Thanks for your reply and thanks for Trevis' reply. I debug my
algorithm, and find the failing of entry due to this problem. I think
I should modify some place. So, I post this problem into the thread.
I also sugguest the coherence should be kept no matter how simplest
it is if possible:)
Thanks again:)

Jin

Jin wrote:
>
>
> Lucio Cetto:
>
> Thanks for your reply and thanks for Trevis' reply. I debug my
> algorithm, and find the failing of entry due to this problem.

I just submitted solver.m unmodified. (I copied it directly from the
zip file.) It passed, which indicates that we should follow its
directional standard instead of what's on the Rules page. Would the
contest organizers agree?

Sean MacArthur

it shouldn't matter what standard you use. All that matters is the
moves are reported with the correct NSEW directions. . . or am i
misunderstanding the problem?

Are inline functions allowed?

Ed

Ed Manlove wrote:
>
>
> Are inline functions allowed?
>
> Ed

Is "Manlove" allowed?

Ed, INLINE is forbidden because of its EVAL-like behavior. I added
this to the rules page. Thanks.

It seems like i will eat my words from my prev post.

*Tries to bite screen* *Gets electric shock* *Screen Breaks* *Turns
to backup monitor*

Ok, now that is done. . . In the test suite. . an example room is
like this:
col 1 2 3 4 5 6 7 8
    0 0 0 3 0 0 0 5 row 1
    0 1 0 2 0 0 0 0 row 2
    0 0 0 0 0 0 7 0 row 3
    0 0 4 0 0 6 0 0 row 4

Now. . my understanding from the rules page is that:

N - direction from row 4 to row 3
S - direction from row 3 to row 4
E - direction from row 1 to row 2
W - direction from row 2 to row 1

Now, according to the provided test suite. . N-S are switched with
E-W. So, which way is correct?

wu zhili wrote:

>> Does it matter if my solver has an extra output? I'm using it
> for
>> diagnostic and recursive purposes, but it says in the rules
that
>> there must be only one output. I'm wondering whether that is
>> really
>> required, or whether it is just that the first output had
better
> be
>> a
>> move list.
>> Thanks,
>> Mike
>
> I think you can put your recursion under the solver function
>

Thanks Wu, that's what I ended up doing anyway.
-Mike Bindschadler

Another small typo in runcontest, on line 20,
moves = cell(n);
should be
moves = cell(n,1);
instead. Otherwise there is a nxn cell created. It doesn't cause a
problem, but it's not really correct.

I think it would be a really good idea if TMW offered some kind of
award to the educational establishment that provides the best
solution. It would much more interesting for the students than
regular homework assignments and might even create some friendly
inter-university rivalry.

Just a thought.

The constants for the scoring function

   score = k1 * result + k2 * exp(k3*runtime)

seem to be

   k1 = 1/1000
   k2 = 1/800
   k3 = 1/10

This means that for the maximum allowed time of 150 s
the runtime penalty is exp(15)/800 = 4086.

HTH, sTefan

zboot wrote:

> Now, according to the provided test suite. . N-S are switched with
> E-W. So, which way is correct?

If you are consistant with the provided solver.m you will be
consistant with the tests running on the server (whichever
prientation this implies).

my code would always timeout if that wasn't true.

> zboot wrote:
>
> Now, according to the provided test suite. . N-S are switched
> with E-W. So, which way is correct?

Several people have pointed out the problem with our move code. We
made a mistake when we created the direction tables.

In runcontest and our example solver we define the move code like
this.

% N=1, E=2, S=3, W=4
I = [0 1 0 -1];
J = [1 0 -1 0];

But later on in the same files we have code that looks like this.

direction = ceil(rand*4);
row = row + I(direction)
col = col + J(direction)

So in fact

direction=1 => col = col + 1 => move EAST
direction=2 => row = row + 1 => move SOUTH
direction=3 => col = col - 1 => move WEST
direction=4 => row = row - 1 => move NORTH

The comment in the code SHOULD have said

% E=1, S=2, W=3, N=4
I = [0 1 0 -1];
J = [1 0 -1 0];

Note that we are only updating the labels and not the code. The
scoring code will run as before. As long as the solver and the
grading routine are consistent with each other, a mistake with the
labels doesn't cause much trouble. Still, it was a mistake, and we
are changing the rules page to reflect this change. Sorry for the
confusion, and thanks to the people who helped set us straight.

-Ned Gulley.
Contest Team
The MathWorks, Inc.

For those of you not following the play-by-play, here's a summary of
the action so far.

Stijn Helsen won the darkness phase of the contest. He had to
develop his entry independently and without the benefit of any
feedback about the actual test suite. We'll send him a MATLAB
Toolkit for his efforts. The darkness phase also saw impressive
submissions from Mike Bindschadler, Roman Akulov, and Andy Mack, all
breaking 1000 points.

Mike Bindschadler won the twilight phase, developing without being
able to see anyone else's. Mike, a new inductee to the Hall of Fame,
will also receive a MATLAB Toolkit. Other contestants who were able
to break the 100-point barrier are Stijn Helsen, Timothy Alderson,
Leendert Combee, Tom Lemke, tuc, and Roman Akulov.

We'll award a daybreak prize of a of a MATLAB coffee mug for the best
entry submitted before 5PM EST today. Good luck!

no one wrote:
>
>
> Ed Manlove wrote:
>>
>>
>> Are inline functions allowed?
>>
>> Ed
>
> Is "Manlove" allowed?

Sorry!

Steve Amphlett, "Ed, Sorry about my recent CCSM post" #, 5 Nov 2004 1:36 pm </WebX?14@@.eef03d2>

It seems that now there is some tolerance in the scores(!). It is
very small, but I don't expect that. The codes for which I see this,
are not exactly the same, but only differs very small, and normally
nothing "really different". For example a code like
if 0&xxx
xxxx
end

The difference was only 0.0001, so nothing meaningfull. I've just
mensioned it.

(this is for example in "test mike&sti's great work__" and "test
mike&sti's great work". But I've seen it also a bit earlier.)

Stijn

Can I redraw my last comment???
I'm appearently too stressed to read the right columns.............

Sorry,
Stijn

Stijn Helsen wrote:
>
>
> Can I redraw my last comment???
> I'm appearently too stressed to read the right columns.............

Personally I thought the run up just before daylight was the most
interesting as we saw really some good progress on results for the
'few' competing algorithms. The kind of x-places behind the decimal
improvements of the rest of the day are really marginal and probably
irrelevant (imho...;-)

I hope someone can come up with a breakthrough in the further
development of the codes. Anyone dare to suggest where the limit will
be, who's the first who will go below 60? We will see.

Keep on working on it!,

I'm finding it really interesting watching this competition's
progress.

Imagine how good Stijn, Mike, the cyclist and all the other top guys
are feeling! But especially Stijn! An ~20% lead in the darkness
phase is something to write home about.

Murphy

Stijn Helsen wrote:
>
>
> Let me already start with asking for shorter contests. I can't
> stop,
> but I also don't want to work further. It's an interesting
> problem,
> but not for eight days.....

Actually, I totally agree... It's great that the darkness and
twilight phases are only a day, and because of that, I can stay up to
4am two nights in a row or take a little bit of time out of my work,
but now that twilight is over, I think I'm going to mostly just watch
(I'm not much of a tweaker anyway). It takes the most effort to stay
in front during daylight, and I can't imagine keeping that effort up
for an extended period of time.

Stijn Helsen wrote:
>
>
> Hello,
>
> Until now I was convinced of the good timing-quality. But now the
> "test-computer" seems to be tired. I saw tolerances of 0.8 s
> (itShouldBeFaster_01cor - itShouldBeFaster_01cor_test). Maybe a
> restart of the computer?
>
> Stijn

I noticed that with itShouldBeFaster_01cor_cy1, which was unmodified.

/Christian

server seems down,

including the mathworks website, except the news group..

maybe, the problem is too computationally intensive, and the machine,
and the network are not so powerful

wu, the website has been down for a little bit. Our web team is in
the process of upgrading the machines in our web cluster. This has
nothing to do with our contest. The entries are run serially on an
independent, dedicated machine. They didn't expect any interruption
in service, but you know how these things go. They assure me it will
be back up soon.

My script has reached a maximum recursion limit. I was wondering if
it is allowed to use the following command to increase the limit:
set(0,'RecursionLimit',N)?

I've just invented some new optimization algorithm which cleans
unnecessary moves from the movelist. It can possibly improve any
other entry. Check out "Strange Solver v2.0" (which contains only my
code) and "wannabe1stplace" (which is based on current top-entry).

Has anyone else noticed that the "score" given to entries seems to be
approximately inversely proportional to the length of the submission?
 It seems that the less clever ML you use, the better your score.

The whole point of using ML in my (limited - only 14 years)
experience is that you can prototype algorithms with the minimal
amount of code and then, when really happy, implement them
efficiently in a real language (i.e. one that's compiled).

The current competition isn't really suited to ML. It's suited to
lower level languages. Admittedly, you can write low-level code in
ML, but why bother? GCC is free; ML isn't!

IMHO, encoraging people to use ML like C or FORTRAN is wrong. I
think there should be a serious size element to the scoring.

- Steve

Steve Amphlett wrote:
>
>
> Has anyone else noticed that the "score" given to entries seems to
> be
> approximately inversely proportional to the length of the
> submission?
> It seems that the less clever ML you use, the better your score.
>
I think that this (and earlier) contests show something about
difficulty of telling which algorithm is best. For many kind of
algorithms, different problems need different algorithms (look also
to "the best data-compressing program). Some algorithms are
sometimes better "most of the time". But for some specific problems
the algorithm can be much worse.
That's why in contests like these, trying different algorithms, and
choosing the best, is giving good results (as long as there is enough
time).
(another example is sorting - if you often sort already sorted lists,
bubble sort can seem the best algorithm!!)

Stijn

Steve Amphlett wrote:
> The whole point of using ML in my (limited - only 14 years)
> experience is that you can prototype algorithms with the minimal
> amount of code and then, when really happy, implement them
> efficiently in a real language (i.e. one that's compiled).
> The current competition isn't really suited to ML. It's suited to
> lower level languages. Admittedly, you can write low-level code in
> ML, but why bother? GCC is free; ML isn't!
>
> IMHO, encoraging people to use ML like C or FORTRAN is wrong. I
> think there should be a serious size element to the scoring.
> - Steve

Hi Steve.
Sounds reasonable.
The best entry has about 2150 command lines! It's not a game any
more!

I do not have enough forces to participate in this game. The problem
seems to be very similar to a simple version of chess. Therefore,
minimization of the number of moves inevitably includes several
levels of analizable positions (after 1-st, second etc. moves).

I think, a smart solution should not calculate all possible versions,
but try to reduce the problem consecutively by finding and realizing
those new positions which do not influence subsequent analysis and
which allow for a shortest (optimal) trajectory to them. To find
such "points of immediate action", one can try first optimal moves of
those objects, which represent obstacles, therefore one has to
classify the optimal trajectories in terms of number of obstacles.
Additional problem is that there are many optimal trajectories within
a rectangle between start and finish, so that real skill is to write
a clever function to check whether there is a free (no obstacles)
optimal trajectory between given start and finish.

   However, already formalization of the concept "not participate in
subsequent analysis" needs some experience, which is, perhaps,
trivial for those, who did write chess-similar programs earlier, but
not to a routined user.

In any case, those who find their own working algorithm, will surely
prove that they are well above middle level programmers. I am
interested, how many people presented working wersions during dark
phase.

Steve Amphlett wrote:
>
>
> Has anyone else noticed that the "score" given to entries seems to
> be
> approximately inversely proportional to the length of the
> submission?
> It seems that the less clever ML you use, the better your score.

I disagree with the idea that shortness=cleverness. For me,
cleverness is really about the underlying ideas about how to approach
the problem, which has little to do with how much code it takes to
implement those ideas. I agree that, with a given underlying idea,
shorter code is often more elegant, and for that reason I don't think
it would be unreasonable to add a minor code length penalty to the
scoring (like the time penalty), but I think the primary ruler for
measurement needs to be how well the algorithm accomplishes the task
(i.e., in this case, units of effort). If the code length penalty
was comparable to the time penalty, then the tweaking which happens
all the time to cut down the time would now have to be weighed
against increasing the length of the code, which is an interesting
idea.

Vassili wrote:

> I do not have enough forces to participate in this game. The
> problem
> seems to be very similar to a simple version of chess. Therefore,
> minimization of the number of moves inevitably includes several
> levels of analizable positions (after 1-st, second etc. moves).
>
> I think, a smart solution should not calculate all possible
> versions,
> but try to reduce the problem consecutively by finding and
> realizing
> those new positions which do not influence subsequent analysis and
> which allow for a shortest (optimal) trajectory to them. To find
> such "points of immediate action", one can try first optimal moves
> of
> those objects, which represent obstacles, therefore one has to
> classify the optimal trajectories in terms of number of obstacles.
> Additional problem is that there are many optimal trajectories
> within
> a rectangle between start and finish, so that real skill is to
> write
> a clever function to check whether there is a free (no obstacles)
> optimal trajectory between given start and finish.

Vassili,
  A good entry doesn't need to be quite that complicated. My first
algorithm doesn't look very far ahead at all, and it performed pretty
well (not good enough to be competitive now, but good enough to win
the twilight phase). Instead, a box is chosen and it's desired
location is determined. Usually this defines a rectange of some
height and width through which the box needs to move to get to the
goal. As you point out there are several optimal paths to get there
if there are no obstacles, but in every move you can make sure you're
following one of them by choosing one of the two directions which is
towards your goal. As long as there are no obstacles, it makes sense
to move along the longer direction first (this maximizes the number
of remaining minimal paths at each step). If there is a single
obstacle, adjacent to the moving box, then it can just move in the
other minimal path direction and remain unhindered. The real
question is what to do when the box comes against two boxes which
block both minimal path directions. My solution is that you tell one
of those boxes to get out of the way. If that box is not surrounded,
it can do this in one step, and then our original box can move again.
 If that box is surrounded, it tells one of those boxes to get out of
the way, and the process is repeated. The only thing you really need
to keep track of is what boxes are waiting to move, because you are
never allowed to tell a box which is already in the queue to get out
of the way of a box later in the queue. Occasionally, this method
runs into a dead end, it may need to be tried a few times, but there
is always a solution, so you don't have to worry too much. As soon
as one box can actually get out of the way, all the others in the
queue move in turn and the original box can continue along it's
minimal path. So, almost all my algorithm does is do this procedure
for each box in turn. Every box takes a minimal path to it's goal
and the only extra cost comes from moving boxes out of the way.
   As a general rule you aren't done after one pass through because
you may have displaced earlier boxes from their final locations
because they had to get out of the way of later boxes. Often though,
starting the procedure again with the final position of the first run
as the starting position of the last run fixes this. If not, you can
always do it again.
  There are a few cases, however, where this is never going to work.
Consider a case like this:
Initial Final
[ 0 0 0 0 ] [ 0 0 0 0 ]
[ 1 3 0 0 ] [ 2 3 0 0 ]
[ 2 4 0 0 ] [ 1 4 0 0 ]
[ 0 0 0 0 ] [ 0 0 0 0 ]

When it is box 1's turn, box 2 is told to get out of the way and
obliges by moving down, then, when it is box 2's turn, it tells box 1
to get out of the way, which obliges by moving up, and then box 3 and
4 don't move because they are already at their goals. This situation
is taken care of by randomly moving the goals for any unhappy boxes
somewhere else in the room for one pass through the main procedure,
then using the real final matrix again. This makes it unlikely that
they will find themselves in the same relative arrangement again.
And, of course, if they do, you can just try this again.
   So, while this whole method is not entirely simple, it is not
nearly as complex as the chess-type program you suggest. No box ever
"sees" more than their four neigboring locations, and no single box
ever considers the effects of moving more than one unit (i.e. the
move after this one is never planned for the current box).

Mike Bindschadler wrote:
>
>
> I disagree with the idea that shortness=cleverness. For me,
> cleverness is really about the underlying ideas about how to
> approach
> the problem, which has little to do with how much code it takes to
> implement those ideas.

Mike,

I'm not degrading your work in any way. From your email address, you
must be some kind of student and as such, using a student ML license.
 If that's the case, spending hours and hours pursuing this challenge
is far better than any other kind of coursework I can think of. And
you seem to be doing really well at it! If I were a student again,
I'd be up all night trying to win too. Unfortunately, my ML license
is at work and when I'm there, I've got other things to do.

My point was that I'd probably not choose ML for this problem. I
might use it to test some ideas, but if my code ran to thousands of
ML lines, I'd use a more suitable language.

ML does some things really well (matrix and vector algebra, pattern
recognition, frequency analysis, etc). But not grunt work like this
particular problem demands.

Mike Bindschadler wrote:
>
>
> Vassili wrote:
> Vassili,
> A good entry doesn't need to be quite that complicated. My first
> algorithm doesn't look very far ahead at all, and it performed
> pretty
> well (not good enough to be competitive now, but good enough to win
> the twilight phase). Instead, a box is chosen and it's desired
> location is determined. Usually this defines a rectange of some
> height and width through which the box needs to move to get to the
> goal. As you point out there are several optimal paths to get
> there
> if there are no obstacles, but in every move you can make sure
> you're
> following one of them by choosing one of the two directions which
> is
> towards your goal. As long as there are no obstacles, it makes
> sense
> to move along the longer direction first (this maximizes the number
> of remaining minimal paths at each step). If there is a single
> obstacle, adjacent to the moving box, then it can just move in the
> other minimal path direction and remain unhindered. The real
> question is what to do when the box comes against two boxes which
> block both minimal path directions. My solution is that you tell
> one
> of those boxes to get out of the way. If that box is not
> surrounded,
> it can do this in one step, and then our original box can move
> again.
> If that box is surrounded, it tells one of those boxes to get out
> of
> the way, and the process is repeated. The only thing you really
> need
> to keep track of is what boxes are waiting to move, because you are
> never allowed to tell a box which is already in the queue to get
> out
> of the way of a box later in the queue. Occasionally, this method
> runs into a dead end, it may need to be tried a few times, but
> there
> is always a solution, so you don't have to worry too much. As soon
> as one box can actually get out of the way, all the others in the
> queue move in turn and the original box can continue along it's
> minimal path. So, almost all my algorithm does is do this
> procedure
> for each box in turn. Every box takes a minimal path to it's goal
> and the only extra cost comes from moving boxes out of the way.
> As a general rule you aren't done after one pass through because
> you may have displaced earlier boxes from their final locations
> because they had to get out of the way of later boxes. Often
> though,
> starting the procedure again with the final position of the first
> run
> as the starting position of the last run fixes this. If not, you
> can
> always do it again.
> There are a few cases, however, where this is never going to
> work.
> Consider a case like this:
> Initial Final
> [ 0 0 0 0 ] [ 0 0 0 0 ]
> [ 1 3 0 0 ] [ 2 3 0 0 ]
> [ 2 4 0 0 ] [ 1 4 0 0 ]
> [ 0 0 0 0 ] [ 0 0 0 0 ]
>
> When it is box 1's turn, box 2 is told to get out of the way and
> obliges by moving down, then, when it is box 2's turn, it tells box
> 1
> to get out of the way, which obliges by moving up, and then box 3
> and
> 4 don't move because they are already at their goals. This
> situation
> is taken care of by randomly moving the goals for any unhappy boxes
> somewhere else in the room for one pass through the main procedure,
> then using the real final matrix again. This makes it unlikely
> that
> they will find themselves in the same relative arrangement again.
> And, of course, if they do, you can just try this again.
> So, while this whole method is not entirely simple, it is not
> nearly as complex as the chess-type program you suggest. No box
> ever
> "sees" more than their four neigboring locations, and no single box
> ever considers the effects of moving more than one unit (i.e. the
> move after this one is never planned for the current box).

Hi Mike! Thanks for explanations. I Thought that he number of chairs
and the room size are relatively big numbers, and then (similar to
chess) you would need weight functions to estimate attractivity of
different moves, based on transmutation length.

Your example, as I see, needs 8 moves. It needs to move aside both
obstacles (3 and 4) temporarily, in order to transmutate positions
1 and 2. In my terminology, you would need 2-levels algorithm, in
order to find this solution, in comparison to 10 moves, which you get
in zero-level algorithm.

I have nothing against code length, if there are no other ways.
However, I am quite sure, that for the problems suggested as contest
topic, the nesessary code length should not exceed several dozens of
commands, otherwise you get a hard work instead of a pleasant play.

I wish you all success!

Steve Amphlett wrote:
> I'm not degrading your work in any way. From your email address,
> you
> must be some kind of student and as such, using a student ML
> license.
> If that's the case, spending hours and hours pursuing this
> challenge
> is far better than any other kind of coursework I can think of.
> And
> you seem to be doing really well at it! If I were a student again,
> I'd be up all night trying to win too. Unfortunately, my ML
> license
> is at work and when I'm there, I've got other things to do.
>
> My point was that I'd probably not choose ML for this problem. I
> might use it to test some ideas, but if my code ran to thousands of
> ML lines, I'd use a more suitable language.
>
> ML does some things really well (matrix and vector algebra, pattern
> recognition, frequency analysis, etc). But not grunt work like
> this
> particular problem demands.

Steve,
  I wasn't taking it personally, but thanks for the concern. MATLAB
is the only programming language I know well, so I can't really say
anything about whether the problem would be more suitably addressed
with another one. But one of the great advantages of the types of
problems the MathWorks has chosen for it's contests is that the
problem is easy to state and hard to solve. Any programmer who reads
the description knows immediately exactly what the goals are and has
a first idea about how to get there, and, in the process of trying to
implement that idea starts to think about problems with it, and ways
around those problems. Lots of programming fun ensues. A linear
algebra problem which takes advantage of MATLAB's particular
strengths (and isn't trivial either) is going to take much more
effort just to understand, and be less playful than imagining moving
furniture around a room.

z wrote:
>
>
> The newsgroup thread link from the search entries page points to
> the
> april contest
That's only for the links from the view-/edit-submission pages. From
the others it is alright.

Stijn

Min Poh wrote:
>
>
> The next MATLAB Programming Contest ...

One perhaps prize-worthy accomplishment for the contest is being the
entrant who spends the most cumulative time as leader. This could be
over the duration of the whole contest, or maybe just for one day of
it (like the Sunday Push).

Mike Bindschadler wrote:
>
> Vassili,
> A good entry doesn't need to be quite that complicated. My first
> algorithm doesn't look very far ahead at all, and it performed
> pretty
> well (not good enough to be competitive now, but good enough to win
> the twilight phase).

Mike,

Good job you did explaining your twilight phase winning algorithm to
all of us here. Although I am sure most of the participants here
already were aware of it. I am not a participant (yet) in this
contest, but I find it very interesting to watch and learn from.
I think this is the aim of having such a mental competition;
watching, learning, and of course thinking.
My suggestion for all of the programmers enjoying this contest, and
who invented different algorithms, is to do just as Mike did: let
this message thread be your documentation. This will open different
discussions and will be a great help for others (like those who enjoy
watching).
A code can be clearly read only if it is extremely showered with
comments, if you really wanted to explain your idea. This is mostly
not the case.

Finally I support the long-running contest idea, it leaves
opportunity to participate for every one especially those who have
jobs. I disagree with those who say the opposite, winning this
contest is not only when you have the best score just before closing,
its more when you construct an algorithm that will be the base of the
winning entry (with few modifications). This usually requires less
time-consuming coding and refining efforts.

We'll award the Tuesday Leap prize to the contestant who makes the
biggest single improvement in score. The winning entry must be
submitted on Tuesday and beat the previous leader by the largest
margin. The prize is a MathWorks calculator and a MATLAB lunch bag.
Good luck!

Matthew Simoneau wrote:
>
>
> We'll award the Tuesday Leap prize to the contestant who makes the
> biggest single improvement in score. The winning entry must be
> submitted on Tuesday and beat the previous leader by the largest
> margin. The prize is a MathWorks calculator and a MATLAB lunch
> bag.
> Good luck!

doh!

I should have waited until tomorrow with the bisection idea!

Roman Akulov wrote:
>
>
> I would like to thank Mike for the explanation of his algorithm and
> I
> would like to follow his example....
(I came here to write about possible further improvements, because
now I can't stop thinking about it, while I should do other things.
Therefore I wanted to write it down. But after reading Roman's
request for explanation of other parts, I do mine.
The main start of solver2 (the winning code of the darkness period)
works by searching for paths from points to its final position. It
does this by for each point "deleting" "dead points" from the "room".
 Dead points are points from where a block can't move straight to its
final position without moving another block. After that, a path is
searched. This is done in an easy way, without trying different
routes. If the block can't go further (blocked by a block or a "dead
point"), it is stopped.
Then the different paths are combined, and looked if any path is
blocked by a final position of the other paths. The paths that don't
block others, are done. Full paths (paths to the final position) are
preferred over non-full paths. That's the main idea. (There are
some other things like when there are only partial paths, some
further tests are done to choose "the best partial path".)
Today I added a test (which was also partly in the code in the
beginning of the contest (MoreFullLines4_)) to see if there are
blocks which can not be moved directly to its final position, using
only a room with only the blocks which are in the final position. If
such blocks exist, "Dperfect" is increased by two (because that's the
minimal additional path). (This is giving now the same results,
while it could lead to worse results, because then the same
path-length can lead to different results (moving heavier blocks then
necessary). But it worked.)
Except increasing Dperfect, solver2 is stopped, because in that
situation, this method often leads to partial solutions which are
more difficult to solve further then the original.

Then a further solution is found by Faster10IntReps2 (originally it
was the "Mathworks example solver").

I think about the following further improvements:
- The solution of the partial solution could be done with other
existing solvers.
- Now the main part of solver2 does not try to split paths, so that
it makes place by moving from the original position without (at
first) blocking paths by the final position. I think trying to use
splitting paths could give better results.
- The first reason to look for "impossible blocks" was to find
optimal was for solving this (moving around or moving a blocking
block). That is still something to investigate.

Stijn

Chris Johnson wrote:
>
> I was also toying around early on with the idea of defining the
> complexity to be the average number of nearest neighbors of all
> final
> furniture pieces. I don't think this is a good criteria, as the
> average number of nearest neighbors of all the initial furniture
> pieces is important.

Chris, I did some analysis on this, comparing/plotting the geometry
complexity as defined by #of_blocks/#room_size vs. the median weight
of the blocks. I used the testsuite to analyse the performance of an
algorithm on each each subcase. You will see that it breaks
approximately in three cases:

- complexity < 30% : all testsuite samples have blocks with very
low weight, typically values less than 10 (do not recall the average
weight for all of these cases). These are the majority of cases and
although they are easy to solve they do not contribute "much" to the
final score.
- complexity > 30% : these are the tough ones that can take a
longer time to solve, especially to get the best solution.
This groups breaks down, into two further sets: median(w) ~< 50
and > 50. The last ones are the nasty ones because they are
difficult to solve and contribute a lot the final score.

So it could well that some algorithm solutions can take benefit from
tuning depending on these parameters.

Another interesting point is the following: given that now everyone
is building upon limited set of previous algorithm, have we reach a
local minimum wrt to results or is this the best we get (42315)? Time
will tell.

I think the beauty of this problem is it simplicity of the problem
statement. Personally I would have liked to see more emphasis on
finding the solution with lowest result factor instead of weight on
CPU. It's like chess, a longer game is often more interesting! And it
may become more creative.

Unfortunately I had to drop out from the contest after the twilight
zone because I have a real job as well :-(

> I think the beauty of this problem is it simplicity of the problem
> statement. Personally I would have liked to see more emphasis on
> finding the solution with lowest result factor instead of weight on
> CPU. It's like chess, a longer game is often more interesting! And
> it
> may become more creative.
The CPU time is also partly to make it practical. There were other
Matlab contests where CPU time was less critical. There was only a
time limit (of 300 s). Then submissions were tuned so that they used
the full 300 s. That made it impossible to handle. It think
something as now, where at low CPU loads the CPU-cost is low is
good....

Ok, here's the description of the basic ideas behind My Sunday Push
entry.

The main idea is to solve the problem recursively, such that if the
full problem does not seem to have obvious solution, drop out some of
the lighter objects and try to solve the simpler problem. Once enough
objects are removed, the problem has an "optimal" solution, and after
that we start to add the removed objects back, heviest first. If the
re-adding fails, revert back to the recursion, again removing some
randomly selected heavy objects. This is all done in the subfunction
mainsolver.

The re-addition is done with a full shortest path search (subfunction
dijkstra). This was a fun part to tweak since it initially could
handle only couple of hundred nodes within reasonable time, and now
runs over 10000 nodes in a flash.

Moreover, the subfunction easysolver tries to find an optimal
solution by first putting the necessary moves after one another and
then trying every permutation of them. This isn't of course practical
so there is some "global" and "local" fiddling to find an order with
no conflicts.

This was actually the very first approach that came to mind, it only
took good four days until I got it to work fast enough. :)
As a peculiarity, my solver uses a slightly different coding for the
moves matrix. It contains one column for each object and the moves
are given as the changes of vectorized array indexes. This allows
fast computing of all positions given initial positions and moves.
This way it is also easy to drop some objects away.

My solver managed to shave couple of thousand points off from some
test cases but failed miserably on others, so I combined it with the
leader at the time. This was worth 0.3 points. The other 0.7 points
came from the idea of using my slow solver only if the faster one
could not get within 1.1 times the optimum move length.

zboot wrote:
>
>
> I've noticed that when i run my code using the provided
> runcontest.m
> file, my score is significantly better on faster machines than
> slower
> ones. This has been pretty consistent trials on various laptops
> and
> PC's with differing amounts of CPU speed and RAM. I knew that the
> execution time would be longer on the slower machines. .but I
> expected the score to be roughly the same. Anyone else notice this
> phenomena?

zboot,
  I think this must be a coincidence. Try setting the random number
generator to the same state before calling your solver on each
machine. You can do this with
 rand('state',0);
Your program should run exactly the same way on different computers,
just faster or slower.
  -Mike

I find my code after about the 2096 line will be truncated......

There does appear to be a maximum code length of 65535 characters.
This is why I have been deleting the good comments from the code.

k1 = 1/1000
k2 = 1/800
k3 = 1/10

FWIW.
Ken

Leendert Combee wrote

> I think the beauty of this problem is it simplicity of the problem
> statement. Personally I would have liked to see more emphasis on
> finding the solution with lowest result factor instead of weight on
> CPU. It's like chess, a longer game is often more interesting! And it
> may become more creative.

I spent some hours on looking up literature
about this problem. You find lots of information
on shortest path searches in books about artificial
intelligence. The algorithms in there are pretty
general and deal with the problems only in an
abstract graph representation: Arrangements are nodes
in the graph, connected by edges (moves). The length
of an edge is given by the weight of the piece shifted.
Of course, this graph is tremendously complicated even
for small rooms and few pieces of furniture. I found out
that the average branching factor in such graphs is between
15 and 40 in the test suite. That puts the problem on
par with chess.

Now, given a start node and an end node, the problem is
to find the shortest path, i.e. the path that minimizes
the sum over the edges travelled. There are based - again on
a rather abstract level - on different approaches:
(1) Breath-first search (BFS):
    Search all paths with 1 move, search all path with 2 moves,
    etc. until you find a solution. This minimizes the number
    of moves, though, and not the total work.
(2) Depth-first search (DFS):
    Take the starting node, generate a list of all possible
    moves, and take the first move. Then generate a list of
    moves for the new node etc. and take the first one. This
    continues until the end node has been found or all "child"
    nodes have been visited. In the latter case, take one move
    back and take the second move from that node. etc. Of course,
    one must label nodes that have been visited in order not to loop.
    Again, this only finds a path, not the shortest.
These two methods search the entire tree, which is impractical.
For a room with N fields and P pieces of furniture, the number
of nodes is N!/P!, which is astronomical for the samples in the
test suite. For the famous 8-puzzle (3x3 squares, 8 pieces), it's
9! = 362880.

Now, one of the algorithms that is guaranteed to find the
shortest path is

    IDA*: Iterative Deepening A* (depth-first)

(see Korf, Artifical Intelligence 27 (1985) 97-109).

It goes like this. For each node N, we define a cost function f = g+h. g is
the cost of reaching N from the start node, and g is an estimation
of the cost necessary to reach the end node. g must not overestimate
the costs, and in the contest problem it can simply be taken as
the weighted sum of the Manhattan distances between current position
and goal of the pieces. For the start node, f = h, since g is 0.
The idea is now to search the graph with a budget (initially
just h of the start node) which is spent along the way. If the estimated
total cost exceeds the budged, the search is stopped and continued elsewhere
in the tree. If for the given budget, the end node cannot be found, increase the
budget by the amount needed to reach at least one more node, and
start all over again with the new and larger budget. In crude pseudocode:

  function ida-star
  budget = h(start->goal)
  while not solved
     budget = depthfirstsearch(start,goal,budget)
  end

  function newbudget = depthfirstsearch(node,goal,budget)
  if f(node,goal)>budget
    newbudget = f(node,goal)
    return
  end
  if h(node->goal)==0
    solved!!
    return
  end
  generate all moves for the node
  loop over all moves m
    newnode = node.move(m)
    budget(m)= depthfirstsearch(newnode,goal,budget)
  end
  return min(budget)

This algorithm will always find the cheapest path, but not
in reasonable time. The ordering of the moves is absolutely
crucial. I wrote an IDA* solver and experimented with various
orderings, but since it takes ages for some configurations, I
randomized the order and restarted the algorithm after a certain
time. However, if the the cost of the shortest path is much
larger than the minimal cost (sum over weights*Manhattan distance
from goal), the algorithm performs badly: it has to make dozens
of budget increases before having enough to reach the end node.

Of course, all this stuff is impractical. But quit
interesting, IMO. I had a great time - even if I didn't submit
solvers to the contest! Combinatorial optimization is fun!

The following site about computer chess contains stuff
that is relevant to the one-agent game of shifting furniture:
http://www.seanet.com/~brucemo/topics/topics.htm
The Dictionary of Algorithms and Datastructures is useful, too:
http://www.nist.gov/dads/

Good luck for the final hours of the contest!
sTefan

Stefan Stoll wrote


> For a room with N fields and P pieces of furniture, the number
> of nodes is N!/P!, which is astronomical for the samples in the
> test suite. For the famous 8-puzzle (3x3 squares, 8 pieces), it's
> 9! = 362880.

Uups! Of course the formula should read N!/(N-P)!

sTefan

I don't think that the path-searching is the most difficult part in
this problem. Especially because the the cost for one path (move of
one block) is simply the distance. The problem is more the
combination of the paths of all the blocks that is giving the biggest
complexity.
For many situation the path for some blocks is from point A to point
A, just to make room for other blocks. And then which block has to
go away when during the paths of the other blocks.
So, the theory given here is nice, but is only a small part of it.

Stijn

Stijn Helsen wrote

> For many situation the path for some blocks is from point A to point
> A, just to make room for other blocks. And then which block has to
> go away when during the paths of the other blocks.
> So, the theory given here is nice, but is only a small part of it.

Right. As I said, these shortest-path search algorithms are just
a more general point of view. Impractical and rather useless, but
a pleasure to ponder for a contest kibitz like me.

sTefan

I have Matlab 6.5, too, and they work perfectly with it.

Stijn Helsen wrote:
>
>
> I've asked it already. But does the submissions of the latest
> day(s)
> work with the testsuite?
> With the latest I always get an error of "??? Index exceeds matrix
> dimensions.", in line "if parent(d)~=0" from the dijkstra-function.
>
> Since I don't want to submit anything anymore, it's not such a
> problem, but I just want to look to current results for some
> problems. I don't want to spend too much time in not working
> programs.
> Has it to do with the matlab-version. (Now I'm using 6.5.)
> Stijn

> With 7.0.1, the latest leading entry st3 hangs
> with test 19 (8x4 room, 8 blocks). Don't know why.
> My IDA* solver found a 384-move (!!) solution with minimal
> cost. Very difficult configuration, it seems.
An older entry (one of early yesterday) gave a solution in 30 moves!
A solver of the first day did it in 34 moves (depending on the
random-state).)

Stijn
(the solution :
     6 1
     2 2
     2 2
     6 3
     2 2
     1 1
     8 4
     2 2
     5 2
     8 4
     8 4
     5 3
     3 1
     4 1
     5 2
     5 3
     8 4
     4 1
     4 2
     8 4
     8 4
     4 2
     3 1
     6 4
     4 2
     8 4
     4 1
     8 3
     6 3
     2 3
)

Roman Akulov wrote:
> I have Matlab 6.5, too, and they work perfectly with it.
That makes me curious. Is it on MS-platform? (To be exact, I have
MATLAB Version 6.5.0.180913a (R13), on MS Win'98)
Stijn

The way how to participate has changed over different contests. The
first time I've participated I started with ideas. Ideas grow, and
most of the time I was not submitting code with "my newest ideas".
So I kept something for later. I looked to what was going on, but
most of the time I worked on my own. (It was also with
phone-connection, so connection time was a bit important.)
In that contest it worked too. In some other contests I wanted to do
it the same way, but actively participating became more important
than preparing for the last moment. The ideas that I had also didn't
work as well.
Now, maybe partly because of the darkness period and that I had time
the first day (later I didn't have so much time), I worked something
out. I had some ideas, but didn't find the time and motivation to
work on it. So, from the moment the contest was fully open, I
checked now and then what was sent. (Now and then was in some
periods maybe often (every 5 - 10 minutes or more).)

When the winning entries didn't work anymore here, I didn't look as
much anymore, but I also didn't work on programs anymore. I looked
to older codes, and looked how they worked for different problems.

My unsubmitted program gives another solution. Both have the minimum
score 48 and 40 moves. (The solution is:
     4 2
     1 1
     6 1
     8 4
     2 2
     4 2
     6 4
     8 4
     3 1
     8 4
     6 3
     8 4
     4 2
     8 4
     4 1
     3 1
     5 3
     8 4
     2 2
     8 4
     4 1
     5 2
     2 2
     4 1
     5 2
     5 3
     2 2
     2 3
     6 3
     8 3
)
Stijn Helsen wrote:
>
>
>> With 7.0.1, the latest leading entry st3 hangs
>> with test 19 (8x4 room, 8 blocks). Don't know why.
>> My IDA* solver found a 384-move (!!) solution with minimal
>> cost. Very difficult configuration, it seems.
> An older entry (one of early yesterday) gave a solution in 30
> moves!
> A solver of the first day did it in 34 moves (depending on the
> random-state).)
>
> Stijn
> (the solution :
> 6 1
> 2 2
> 2 2
> 6 3
> 2 2
> 1 1
> 8 4
> 2 2
> 5 2
> 8 4
> 8 4
> 5 3
> 3 1
> 4 1
> 5 2
> 5 3
> 8 4
> 4 1
> 4 2
> 8 4
> 8 4
> 4 2
> 3 1
> 6 4
> 4 2
> 8 4
> 4 1
> 8 3
> 6 3
> 2 3
> )

Niilo Sirola wrote:

I just want to say that I like all Niilo's ideas. I think he's right
that the milestone prizes get new ideas into the open before the last
minute, and that's a good thing.

Niilo Sirola wrote:
>
> I actually went through the trouble of extracting the five
> "elementary solvers" from the leading entry (there were
> additionally
> several "meta-solvers" that used one or more elementary solvers
> with
> different parameters and random seeds) and running some benchmarks
> with individual solvers to find the optimal performance/time
> balance
> for different-sized problems, but I did not have much time to put
> in
> it and this approach sadly did not survive the competition however
> nicely ir was structured.

I had a similar idea, but never got to even attempting it. I'm sorry
to hear it didn't work out!
   My contest strategy was to try to get a working entry done in
Darkness, then see at the beginning of twilight how it compared to
other entries. This time, it was tantalizingly close to the the
leader, and this provided tremendous motivation for me to find ways
to make it better. I was able to do this, and won the twilight
phase. My first contest was the Gerrymandering contest, and I
learned in that one that once Daylight hits, the contest changes
dramatically, and the identity of the leader changes often as people
make incremental improvements on the current leading entry. I knew
that I wasn't going to have time to stay competitive after twilight,
so I figured that part of my contribution to the contest would be to
make my code reasonably intelligible so that people modifying it had
a chance of understanding the overall plan. For the rest of the
contest I have watched with interest and tried (mostly
unsuccessfully) to understand the pieces of the leading entries. If
I had had a compelling new idea about how to approach the problem
differently, I would have tried to develop it into a new entry, but I
didn't, and just watched.
 I'd also like to say that I really appreciated the descriptions
people posted of their algorithms. I found them very interesting, and
something I found it impossible to extract from the entries
themselves.
Thanks for a great contest!
-Mike

Ned Gulley wrote:
>
>
> As the contest is winding down, I wanted to ask people what
> strategies they use as they play. Many of you have participated in
> several contests and have developed some sophisticated strategies.
> Here are a few questions that might get the discussion rolling...
>
> * How often do you check for changes in the current leader as you
> work on your own entry?
>
this game is so absorbing, i cannot stop thinking of it all day and
night.... by continuously checking the winning entry, and to
prototyping my own idea, to see there is added-value to the current
best...

> * Do you have a "watch list" of people whose algorithms you make
> sure
> to look at?
>
sure, like stij, mike, cao yi, ..... but eventually i see some
brilliant ideas from some new comers. And generally, several top
entries are checked....

> * Do you save up changes for submitting at the last minute just
> before the contest ends?
>
no, at least for this game. And actually I am sleeping when the game
enters into the final day..

> * Are you an "active lurker" in the sense that you don't enter the
> contest, but you work hard to understand what's going on?
>
no, I think i am an active participant

> * Do you ignore the competitive aspect of the contest and just try
> to
> add value?
>

not fully ignore, some midstage prizes are certainly incentives for
me to develop/watch continuously. But most of time, I think I am
motivated by how can I further push the limit...

> * Do you think the contest has a good balance between competition
> and
> cooperation?
>

I don't know, I think I learn much from the game, and learn how
competitive some top matlabers are ....

The overall winner asdf1 loops infinitely for
problem 19 of the test suite. Now I see why:
The problem is that one of the weights is negative!
Maybe this traps some of the algorithms developed,
since cost functions don't behave properly: Move
the negative-weight block around a couple of times,
and your cost is down to 0! My IDA* solver fails
miserably.

Other problems in the test suite with negative
weights are 7 and 28. 56 has a zero-weight block
(I wish I had such furniture...)

Have these negative weights been included on
purpose?

sTefan

Yi Cao wrote

> My unsubmitted program gives another solution. Both have the minimum
> score 48 and 40 moves. (The solution is:
> 4 2
> 1 1
> 6 1
> 8 4
> 2 2
> 4 2
> 6 4
> 8 4
> 3 1
> 8 4
> 6 3
> 8 4
> 4 2
> 8 4
> 4 1
> 3 1
> 5 3
> 8 4
> 2 2
> 8 4
> 4 1
> 5 2
> 2 2
> 4 1
> 5 2
> 5 3
> 2 2
> 2 3
> 6 3
> 8 3
> )
> Stijn Helsen wrote:
>>
>>
>>> With 7.0.1, the latest leading entry st3 hangs
>>> with test 19 (8x4 room, 8 blocks). Don't know why.
>>> My IDA* solver found a 384-move (!!) solution with minimal
>>> cost. Very difficult configuration, it seems.
>> An older entry (one of early yesterday) gave a solution in 30
>> moves!
>> A solver of the first day did it in 34 moves (depending on the
>> random-state).)
>>
>> Stijn
>> (the solution :
>> 6 1
>> 2 2
>> 2 2
>> 6 3
>> 2 2
>> 1 1
>> 8 4
>> 2 2
>> 5 2
>> 8 4
>> 8 4
>> 5 3
>> 3 1
>> 4 1
>> 5 2
>> 5 3
>> 8 4
>> 4 1
>> 4 2
>> 8 4
>> 8 4
>> 4 2
>> 3 1
>> 6 4
>> 4 2
>> 8 4
>> 4 1
>> 8 3
>> 6 3
>> 2 3
>> )

Ned Gulley, Mike and everyone who participated in the contest:

    I think the seven days of the contest are impressive and helpful
for me. I touched ML contest from Molecule Contest. First, in the
Molecule Contest, I just watch and don't enter it. In recent several
contests, I try to develope my codes to take part in this mental
play. My major is the Applied Superconductivity, which almost has
nothing with computer science. So I have no practice in complex
algorithm. I just employ my thinking way to try to solve those funny
problem proposed by the ML Contest Team. I must say, I have learned
many many many from the course of contest. And I would like to try to
learn more (only if I have enough time^_^).
    I also have some ideas about the contest.
1. balance between competition and cooperation
  This is hard to be evaluated. A contest always need the
competition:) However, I think more considerations could be given to
the cooperation (or to the fun^_^). Contest Team could provide a
special zone for the running contest, which can include a instant
chatroom, a related algorithm area and more interesting about the
contest(such as the news about the crash of server^_^) . The
participants, not only the matlaber, but also the newcomer, can get
more beyond the contest itself!^_^

2. the prize
  Push and leap prizes are good. However, the grand prize should be
left to the man who has the most leader records. He is the most
diligent and the most clever participant(Such as Stijn, Mike, Timothy
and...). Winning the prizes is not everything for our contest:)

    Oh, I need a sleep now. Good night everyone:)

Jin

This contest was a little different for me since I did not have
Matlab available. This resulted in mostly tweaking of other peoples
code. Usually I try to develope my own algorithms and then try to
introduce them when I feel that they can give a boost to the top
score. Unfortunately I missed a large part of the beginning in this
contest, this lead to even less development of my own code.

What I did (partly instead of Matlab programming) was to write a
script that automatically downloaded and compared two entries agains
eachother using diff. I did not use it more than a couple of times
but it was quite fun to see which variables that where subjected to
tweaking.

As to my own algorithms I had an idea of using Zobrist hashing to
keep track of the "board" position, score, route etc. and then use
Dynamic programming to find the best solution. I did not get very
far however, my best entry was the basic solver where each position
was stored in a hashtable. They where then compared and any
repetitions were removed (much like in the function checksummer).

As mentioned earlier I think revarding the person who spends most
total time in the lead is a good idea.

I would also like to see the twilight zone last 3-4 days to give more
time for individual effords.

If the extreme overfitting to the contest suite could be avoided that
would be great but I can't see how that should be done.

As usually I had great fun.
See you all sometime around April -05

/Christian

Ned Gulley wrote:
>
>
> As the contest is winding down, I wanted to ask people what
> strategies they use as they play. Many of you have participated in
> several contests and have developed some sophisticated strategies.
> Here are a few questions that might get the discussion rolling...
>
> * How often do you check for changes in the current leader as you
> work on your own entry?
>
At least twice a day.

> * Do you have a "watch list" of people whose algorithms you make
> sure
> to look at?
>
Yes, sure. Also because this, I have to use anonymous submission to
test my code before I am sure it works.

> * Do you save up changes for submitting at the last minute just
> before the contest ends?
>
Not really. I was not ready to submit my code at the end.

> * Are you an "active lurker" in the sense that you don't enter the
> contest, but you work hard to understand what's going on?
>
No. I worked hard to develop my own code but was not satisfied with
it at the end.

> * Do you ignore the competitive aspect of the contest and just try
> to
> add value?
>
Not this time. In most previous contests, I did.

> * Do you think the contest has a good balance between competition
> and
> cooperation?
>
I don't think so. Competition is always overweighted, particularly at
the last minute. Cooperation is very trivial. I also do not see any
cooperation channel practically operable. Maybe, some discussions in
the News Group can be counted as this, but most of them are about
past not future. Originally, I think big push prize may motivate
cooperation. But, it did not happen.

> As always, thanks for playing.
>
> -Ned Gulley.
> Contest Team
> The MathWorks, Inc.

Stijn Helsen wrote:
>
>
> I've asked it already. But does the submissions of the latest
> day(s)
> work with the testsuite?
I did now some further investigation. It is very strange (as far as
I see it now). The problem is in the input of the dijkstra-routine.
The first argument should be the number of elements in "R", which is
"slices" in imoves. Sometimes that number appears to be faulty. It
added a check at the top of that function (if n~=numel(R)). That
appeared to be true, sometimes. The, and it gets more "interesting",
I added two tests before the call of the dijkstra-function :
  nnnn=numel(slices);
  if nnnn~=numel(slices)
error xxxxxxx
  end
  if nnnn~=prod(size(slices))
error yyyy
  end
The result was error-yyyy!
Am I really the only one who is getting this strange behaviour?
Stijn

In this contest I was not an active participant, not even an active
lurker. Yet I managed to finish in second place by speeding up some
code I didn't have time to understand... This is what makes the last
day so unfair and at the same time so exciting. Competition and
fairness are antonyms. You can not have both. But things can be
improved somewhat by implementing some of the suggestions that have
been made in this newsgroup. Here are my two suggestions:
1. Remove the time portion of the score in the last 5 hours. Or at
least decrease the sensitivity of the score to time so that a .1
seconds improvement will score the same as the original, but maybe
> 1 second improvement will do better. You can call this the
"sunset" phase of the competition. This would be an incentive to
improve the results, not just the time.
2. Name the overall winner to whoever improves the score the most.
Ideally this would be the sum of all the improvements throughout the
competition but this has its drawbacks as the first ones to
participate or the ones that submit the most have a better chance of
winning. So maybe a compromise would be to add just the best 3
improvements in the last 3 days. Or have a "last push" similar to
the "Sunday push" where the biggest cumulative score over the last
two days wins it all.

But then again, you can leave the contest the way it is: A great,
fun, and _exciting_ contest!

-Paulo

Jin wrote:
>
>
> Leendert:
> Three segment model has been proved as a nice model. To give the
> twlight segement a more day is a piece of advice which worth
> consideration, I think:). This give more time to the participants
> who have not much time(and newcomers):)
>
> and Mike:
>
> Yes! I also believe, the additional prize is the biggest prize:)
> And
> he deserves the award!
>
> Jin

> nnnn=numel(slices);
> if nnnn~=numel(slices)
> error xxxxxxx
> end
> if nnnn~=prod(size(slices))
> error yyyy
> end
> The result was error-yyyy!

I can confirm this. Additionally:

K>> nnnn
nnnn =
    48
K>> numel(slices)
ans =
   480
K>> prod(size(slices))
ans =
   480

Veeeery strange. It seems either nnnn or slices changes
spontaniously. This is on ML 6.5, using the winner entry.

Stijn Helsen wrote:
>
>
> Stijn Helsen wrote:
>>
>>
>> I've asked it already. But does the submissions of the latest
>> day(s)
>> work with the testsuite?
> I did now some further investigation. It is very strange (as far
> as
> I see it now). The problem is in the input of the
> dijkstra-routine.
> The first argument should be the number of elements in "R", which
> is
> "slices" in imoves. Sometimes that number appears to be faulty.
> It
> added a check at the top of that function (if n~=numel(R)). That
> appeared to be true, sometimes. The, and it gets more
> "interesting",
> I added two tests before the call of the dijkstra-function :
> nnnn=numel(slices);
> if nnnn~=numel(slices)
> error xxxxxxx
> end
> if nnnn~=prod(size(slices))
> error yyyy
> end
> The result was error-yyyy!
> Am I really the only one who is getting this strange behaviour?
> Stijn

I did not get this behavior with Version 7.0.

I just noticed in the File Exchange the actual test suit has been
added to the zip file. However, after download it, I found the zip
file is still old one. There is no actual test suit in it.

The Furniture contest final analysis, contest evolution, and winners
page are now available from our contest page.

Final Analysis:
 <http://www.mathworks.com/contest/furniture/analysis.html>

Contest Evolution:
 <http://www.mathworks.com/contest/furniture/evolution.html>

Winners Page:
 <http://www.mathworks.com/contest/furniture/winners.html>

Thanks to all our participants and spectators for making this contest
a success.

- The MATLAB Contest Team -