Skybuck's BoxifyMe Programming Contest

Last update: 16 may 2012 (Similarities section added)

Your mission is to "Boxify" the following picture with a minimum ammount of boxes (=rectangles):

In picture form:

In (PixelMap) text form:

PixelMapBoxifyMe1.txt

PixelMap text format is as follows:

Width,Height

X,Y

X,Y

X,Y

X,Y

Example (each x,y pair describes one pixel):

100,100
42,1
43,1
41,2
42,2
43,2
44,2
5,3
6,3
41,3
42,3

Etc

In (TextMap) text form:

TextMapBoxifyMe1.txt

TextMap text format is as follows:

A dot for an empty pixel.

An X for a full/taken pixel.

All of the red pixels must be described by boxes.

You should write a computer program which does this boring task for you ofcourse ! That's what lazy programmers are for !

To be able to verify the correctness of your algorithm/code you must provide me with the output of your algorithm.

For this purpose the following shall be used:

A textfile which describes the coordinates of each box on a seperate line as follows:

X1, Y1, X2, Y2

X1, Y1, X2, Y2

X1, Y1, X2, Y2

So a example:

10, 5, 20, 40

5, 3, 10, 9

40, 3, 50, 10

The picture itself is (left, top) to (right, bottom) which is  (0,0) to (99,99)

You can either submit your results to skybuck2000@hotmail.com

or simply post a message on the newsgroups where this contest was announced.

I shall write a little program which shall examine all the submitted results and rank them according to number of boxes used.

Least ammount of boxes wins.

Once I get some results from you guys I will put up a ranking page which will probably be updated as I receive more submissions.

You can either submit solutions only, or you can also choose to submit your algorithms and or code.

Good luck to you !

And may the boxforce be with the fokking you ! ;) =D LOL.

Oh yeah... ofcourse I will be contending the contest as well !

And I fully expect to win it ! ;) =D

But don't worry I will be fair.

So if you wanna try and piss me off... the best thing you can do is try and win it ! ;) =D

And then maybe I will be begging you on my kneeeeeesss if I could plssss have your algorithm and code ?! ;) :)

Wouldn't you absolutely like that ?! ;) =D

You may also choose if you want me to reveal or not reveal your algorithm if you do submit it to me.

Coding languages which are preferred: C, C++, Delphi, Free Basic.

Now download that picture, starting coding and BE GONE ! ;) =D

Let those brains of yours BURN CYCLES AND CONSUME ENERGON ! ;) =D

Also BE PREPARED for a new picture in the future !

Since I must verify your awesomeness !

You could just have gotten lucky with your algo...

So stay TUNED ! As always...

Be on your toes ! ;) =D

King of the Contest  (so far)

(Round 1):

Skybuck's BoxifyMe Entry1 (non-overlapping) (306):

This is my first entry for the contest:

In picture form:

In text form (306 lines/boxes):

BoxifyMe1SkybuckEntry1.txt

Now ask yourself one question punk: "Can I do better ?!" ;) =D

Skybuck's BoxifyMe Entry2 (non-overlapping) (305):

I was looking at the first picture/entry and something didn't seem quite right to me... I finally managed to find a small little odity in my code which was a left over from the bug hunt before it, I corrected the odity and now the algorithm is slightly better, so this will be my second entry:

In picture form:

In text form (305 lines/boxes):

BoxifyMe1SkybuckEntry2.txt

Skybuck's BoxifyMe Entry3 (non-overlapping) (285):

Hmm this time I try something else and surprise surprise it looks like it's worse but it's not:

In picture form:

In text form (285 lines/boxes):

BoxifyMe1SkybuckEntry3.txt

James Dow Allen's BoxifyMe Entry1 (overlapping) (234):

A person who apperently goes by the name of "James Dow Allen" has entered the contest and has provided me with a textfile as requested according to the rulez.

I have "rendered" his textfile to have a looksy at the picture which I will now share with you down below:

In picture form:

In text form (234 lines/boxes):

BoxifyMe1JamesDowAllenEntry1.txt

Only 234 boxes I was thinking to myself ?! WOW... How did you do it... I was thinking to myself at first glance...

Then after deeper inspection with a zooming program I discovered something odd about this picture, something mysterious... something fascinating.

Lol.. Apperently James Dow Allen has chosen to simply overlap the rectangles and therefore getting a smarter coverage and much less boxes ! ;) :)

This is an amazing solution which I didn't even think about yet... sigh.

Because my solutions have "non-overlapping" rectangles. Which means as much as: every pixel is part of a single rectangle. No pixels are shared.

So now this puts me a little bit of a dilemma.

Shall I allow this amazing discovery to enter the contest ?! ;) :)

It sure is intrigueing... and therefore... for now I shall and will allow it !

Because the rules where clear I thought... the rules are: minimum boxes.

I did not mention anything about "non overlapping boxes".

Anyway for now I will allow this but they will be specially marked as "overlapping solutions".

My entries 1,2,3 will be marked as "non-overlapping solutions".

Both are intrigueing and could be usefull so I hereby split this contest into two sections:

1. Non-overlapping solutions.

and

2. Overlapping solutions.

I am not yet sure which type of solutions I like best. This will depend on the engine called "box2d" which apperently likes to use a  lot of boxes ! ;) :)

So some day, some where in the future, which could actually be very soon... I will test both kinds of solutions to see which type of solutions

actually perform better with the favorite/popular engine box2d.

So stay tuned ! ;) =D

(I hereby like to thank the best man know as James Dow Allen for participating... perhaps he would like to let us know a little bit more about how he came to his solution... like what kind of programming language or tool was used ?! ;) :))

James Dow Allen's BoxifyMe Entry2 (overlapping) (226):

The "doctor" has complained of "foulplay" ;) :)

His complaints are as follows:

1. His "solutions" (output) is being made public. His complaint is that his algorithm produced this material...

and now the best man is afraid that others might copy it and cheat it and improve it slightly.

Alllll I can say about that is: Welcome to reality "doctor" !

This is the reality of EVOLUTION... yes it's all around us... take no prisoners... have no mercy.

If the people/contesters are smart enough (or dumb enough ?!?) to take your solutions and improve on it then I am in principle fine with that.

But all materials/contributions/entries will be examined on a case-to-case basis.

If I suspect "plagiarism" by simply copieing solutions and then making trivial adjustments, especially without any improvements then they will simply not be accepted.

I'll give one example of such a trivial trick: Simply swapping the lines in the file. Such "plagiarism" will not be accepted, nor will it be tolerated ! And it will be dealt with in harsh manners ! ;) :) =D

2. He wants the solutions to be taken down. What do you think this is "doctor" ? Some kind of patent office... where you will get the sole right of ownership or something... or where you get to deny the usage of all of this ?!? No doctor ! ;) :)  This is all about sharing... because sharing is careing ;) :)

This is all about searching the search space... who will find the best algorithm... that's what this is all about doctor... and for that a bit of openness is required.

People/contesters must know what the best solution is so far... so that they can try and improve theirs. So there is definetly a need for scores/openess at that front.

Furthermore analyzing the entries can give people knew idea's about how to proceed.

Perhaps even slight adjustments of current idea's.

I shall reveal a little bit about what you told me via e-mails... you mention.. "box reduction ?"

You my best "doctor" also made it sound like your algorithm spent a lot of time on trying to come up with a solution ? Is that perhaps why you seem to be discontent with the current situation ?!? I wonder...

I do wonder how much time your algorithm spents on finding a solution... My algorithms you best doctor complete very fast in under one second... probably mere milliseconds. So I would find it quite interesting

if you could tell us a little bit more about the executing speed of your algorithms... I have told you mine... well you tell me yours ? ;) :)

The best man has also let me know that he's apperently using the programming language known as "C" and that he is probably good at it. As I requested this information a little bit.

It pleases me "doctor" to see that you have improved your solution. It's quite impressive, down from my shitty 306 to 305 to 285 to 234 to 226. Pretty nice.

A verification program still has to be written for now I simply compared the pictures over each other to see if all pixels are used.

For now this method seems to be fine to verify entries. So perhaps a verification program isn't even necessary.

Why waste time on things which are not necessary, huh doctor ?! ;) :)

If people try to bullshit me then maybe the verification program will raise from it's ashes.

This competition will probably never end... unless somebody can prove that his algorithm is "optimal".

Thus "doctor" there is no real hurry... you may always submit more.

See you around doc ! ;) :)

In picture form:

In text form (226 lines/boxes) :

BoxifyMe1JamesDowAllenEntry2.txt

Skybuck's BoxifyMe Entry4 (non-overlapping, "boxy1") (327):

Skybuck's entry 4 is not really a though competitor unless maybe rules are changed... but for now it probably does resemble a little bit more my original idea... the title of this contest is after all called: "boxify" and not "rectanglefy". More original goal was to produce some kind of algorithm which produces more boxy like partitioning. The first three entries were not focused on this but merely on reducing the number of boxes/rectangles anyway possible... and the first tree version seem to produce somewhat flattened rectangles.

However this new version (internally version 0.05) seems to produce somewhat more boxy shapes followed by more many little boxes. The algorithm could probably still be refined further so this is a pre-liminary investigation of this new slightly changed algorithm.

This contest is not only about finding the optimal solution but it's also about finding interesting solutions.

So don't hesitate to enter interesting solutions as well ! ;) :) (Later on I will also try and attempt to develop an overlapped algorithm to compete with the other contender, so be on your toes ! ;) :) ).

I might also introduce a new section for "most boxy algorithm" The idea could be to include a "width/height ratio" measurement to see which algorithm is most boxy... but that's perhaps something for the future.

In picture form:

In text form (327 lines/boxes)

BoxifyMe1SkybuckEntry4BoxyV5.txt

Skybuck's BoxifyMe Entry5 (non-overlapping, "boxy2") (316):

Further improvements have been made to the "boxy" version of the non-overlapping version of the algorithm. Further improvements might be possible.

Number of boxes has been brought down some what, from 327 to 316.

(internally version 0.06)

In picture form:

In text form (316 lines/boxes)

BoxifyMe1SkybuckEntry5BoxyV6.txt

Skybuck's BoxifyMe Entry6 (non-overlapping, "edge") (276):

My non-overlapping algorithm has been improved. I am gonna give this improved algorithm a codename: "edge".

It's not a new category or anything like that. Therefore double apostrophes " " will be used to indicate it's just a codename ;) :)

The number of boxes has been brought down further from my previous record 285 to 276. That's a 9 box improvement... that's pretty good/significant... I am cool/happy with it ! ;) :)

(At least it wasn't a waste of time ! ;) :) That's always good/nice ! ;) =D though further testing will have to do be done with more pictures to be sure ! ;) :))

In picture form:

In text form (276 lines/boxes):

BoxifyMe1SkybuckEntry6EdgeV7.txt

Skybuck's BoxifyMe Entry7 (overlapping, "reduce") (277):

I wrote quite a lot of code (for the new overlapped version)...

I was kinda expecting to perform better than the other contester... but as I moved on and when I saw the debug output... I started to doubt... then I pretty much knew it was probably not gonna be better, but I finished up the job anyway ofcourse, curious as I was... the result: one box worse then my best non-overlapped algorithm but which did get more time and work done so far and more analysis.

So this is a bit of an anti-climax lol... for the day... but there will be more days, more days for analysis... more days for try outs... more days for algorithm refinements, tweaks or perhaps even new ones.

For now I must come to the conclusion that James Dow Allen's Kungfu is strong (at least for overlapped versions !;)) ! Apperently very strong... or perhaps my algorithm is doing something stupid somewhere...

Time will tell... for today I am probably done... or maybe not... perhaps I will give it a little bit more time and looksies... but don't expect anything great anymore for today...

(Today is 12 december 2010, contest was started on 11 december 2010) Well I must say for just two days of work we/I have done/accomplished a lot...

Quite amazing how much I did in just two days ! ;) :) but I am still yet not done...

Pretty darn fascinating ! ;) :)

I leave you now with the results for my 7th entry (internal version 0.07):

At least I had a lot of fun writing it... with all kinds of rock music on during the boring code writing sessions/sections oh yeah ! ;) =D and also to keep me going oh yeah ! ;) =D

Fun fun fun fun fun fun fun... days like these I like a lot ! ;) =D Yeah baby ! ;) =D

In picture form:

In text form (277 lines/boxes):

BoxifyMe1SkybuckEntry7OverlapV7.txt

Hmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

I just did some quick analysis and it seems my algorithm is doing something stupid... I kinda expected that... I kinda knew it was doing that... I saw it during the debug and such...

It appears it is outputting unnecessary boxes. It also seemed the solution was actually quite good except for the stupid bad boxes, I only looked half way, so still more analysis necessary.

I can now understand the other contester's fear about releasing a solution with stupid mistakes in it, which could/would then be spotted by another contester.

Another contester might be able to remove the stupid bugs/boxes from it and then represent it as an original solution... while it's not an original solution.

Such an contester might not even have an algorithm to produce a solution in the first place.

I also now understand where this fear is coming from. It's quite funny.

With my solutions I simply didn't have this fear... because my solutions were non-overlapping... so it was very clear to me that there weren't any stupid mistakes in it.

Hehehehehe and that's where the fun part begins.

Apperently James Dow Allen wasn't so confident about his solution because it was very messy ! because of all the overlap ! ;) =D

How funny is that ?! ;) :)

Because there are so many stupid and apperent bugs/boxes in it I have decided to remove my 7th entry for now... until I can have a look at it and hopefully/perhaps fix it.

Then it might become a very good solution.

This creates a bit of a dilemma for me... hihi.

James Dow Allen requested his entries to be removed until the contest is over and the final winner can be decided.

That's not how I envisioned this contest... I envisioned a non-overlapped contest where it wouldn't be such a big deal to share solutions as they come out.

But now I can see that with overlapped solutions this becomes a bit risky...

First of all I do not intend to "rob" other people of their solutions and secretly improve it or something like that. But do you trust me ? Ofcourse you don't trust me... you shouldn't trust me... and you shouldn't have to trust me. So ofcourse I am not going to be stupid and say something stupid like: "trust me" nooooooooooo.

I already see a much better solution to this problem than keeping things secret or granting removals noooooo that's all not necessary because all contesters are supposed to have their algorithms and code handy for when the next round begins ! Yes Ladies and Gentlemen ?! ;) :) You didn't really think that I would base a contest on one single picture did you ?! ;) =D

Nonononononononononononono.

The solution to the "stealing solutions/outputs" problem is very simple:

During another round, perhaps the second round of this contest a new picture will be generated (probably drawn by me by hand as I did the first one).

Actually I can already see another "attack vector" at my contest. People could accuse me of "generating favorable images for my algorithms" and thus I shall also already introduce a new rule to the contest:

You are allowed to send in your own pictures for "contesting". That could be a special round as well... Perhaps a sort of "combat" round... where people get to try and upset the algorithms of the opponents.

Very very very interesting idea ! ;) :)

Anyway the idea for the solution for the "stealing code/output" problem is the following:

During another round people will get to keep their solutions/outputs secret. This way it's garantueed that nobody gets to see the output.

The output is then encrypted by everybody... and it's send to me.

I will put all the outputs on the website in the encrypted form so that everybody can download it.

Nobody has the keys.

After the "period of entering submissions" is over no further solutions can be added.

After the submissions period is over everybody makes their key public and thus all can decrypt and see the results and verify them.

This way there can be no doubt about the results or the fairness of it.

Encryption methods will be up to the user to decide. I could recommend either AES but that might even be to weak for simple/little text files...

I could also recommend "The one time pad"... be sure to generate some good random numbers from hardware input or so... not just some rng ;) :)

Perhaps even a combination of AES and One time pad for maximum security... Maybe I will ask on sci.crypt if this indeed does provide more security, but don't bet on it, me asking that is, the one time pad

is probably the strongest encryption algorithm ever and it's very simple to implement. So it's the ideal contender for encryption during this contest... it will keep things nice and simple me thinks ! ;) :)

So for now I say to all the people/contesters that want to participate (especially with overlapped solutions):

Don't despair, don't worry, you will be treated more fairly in the next rounds.

Your complaints of "foulplay" have not fallen on deaf ears.

I now take your complaint more seriously and will act upon to take these doubts and fears away.

Such doubts and fairs will be taken away in next rounds.

So you will just have to sit tight, and sit this one out.

However my mistakes where so big and so great I still remove it :P* ;) :)

If you really believe your solutions are so bad and want them removed I will do so...

Just sent me e-mail if you really want them removed...

I would not like it... but I will obey any requests.

But I will leave the scores on the pages.

Also it doesn't make much sense to send me solutions and then to request to take them offline again.

I explicitly asked you to send me solutions and I also explicitly said that I would be entering the contest as well.

So apperently to a certain degree you will have to at least trust me with round one which makes round one weak.

Ofcourse I could also have done stupid things like claim your solutions to be mine... but that would be pretty dumb/stupid/weak since they nobody would enter anymore.

Such things have not happened. I have not taken credit for anybody else's solution nor have I used anybody else's solution.

However I did get inspired by the other contenders remarks in the e-mail.

The contender is now complaining about the privacy of his e-mail ?!? Why exactly ?

In short I can imagine a number possibilities:

1. Mentioning of C

2. Mentioning of reduce. (Everybody here to learn I hope.. ;) :))

3. Mentioning of patent office perhaps ?!? I don't know...

4. Just a warning... ok mister... you found me slightly annoying that's what I believe... it's ok... it was intended to annoy you a bit lol. Annoying opponents can also be a strategy ;) :)

As far as I can remember, I will check later, it was very clear about what would be private and what would be public.

I do not feel that I have revealed anything that could be considered "private information" except perhaps that he programs in "C". But is that so bad ?

I ask for that information and ofcourse I would share it with others... why would I keep that information to myself ? Doesn't seem to make much sense to me... and also doesn't seem fair to me.

Everybody that knows me a little bit from usenet knows that I program a lot in Delphi...

I just wanted to know if an external solver and/or language was being used or something more generic like C/Delphi/Pascal etc.

Contester has let known not to be offended, not to be annoyed at least not by e-mail leak. Ofcourse it was my pure intention to annoy him a little bit with this website... to make fun of him... to try and

embarash/humiliate him but in a fair way... the only way is the way to victory. Alas I have not achieved victory (yet?!). It was also ment to be a bit of fun...  calling him the "doctor" a secret referrel to
"The nazi doctor" of Call of Duty Black Ops ! ;) :) See it as a complement... the doctor is a lot of fun to play with and says: "Bow before the might of the Doctor !" when he blows away all the zombies ! ;) :)

Will The Great Skybuck fumble and BOW before the might of this nazi doctor ?!

Or will The Great Skybuck come out on top and PREVAIL ! =D And destroy and humilate the nazi doztor ?! =D

Hehehehehehehehe. Yes Ladies and Gentlemen... that's ofcourse what this contest is all about.

ONE SHALL STAND AND ONE SHALL FALL ! ;) =D

OR if multiple contesters take part:

ONE SHALL STAND AND THE REST SHALL FALL ! ;) =D

OR  even better:

ONE SHALL BECOME THE KING OF THE HILL ! ;) =D

Anyway I am not so sure about my claims anymore that there were indeed many dumb bugs in it... since they way it was quickly visualized was a bit deceptive... I will write a better analysis tool soon... to spot dumb bugs/inefficiency ;)

Meanwhile a new contester has entered the contest ! ;) :) See below ! ;) =D

Ok I have implemented a rectangle inside rectangle test and it seems I was wrong... there was no real bug inside my overlap algorithm... as I was afraid... the algorithm is probably just inefficient as it currently is :) :( :)

So I have restored it and my entry is now available ! ;) :)

Rob Pratt's BoxifyMe Entry1 (overlapping "SAS/OR" ) (217):

Quite an amazing entry this one ! It immediatly rises to the top of this contest.

It's of now the number one entry... with just 217 boxes ! ;) :)

Seems nice and clean algorithm too from viewing the output. I am starting to wonder if anybody is using a solver ;)

Perhaps Rob Pratt could let us also know what programming language he used ;)

I must give out a warning though, to people with slow algorithms which include myself as well potentially.

I will make sure that during a next round of the contest that many pictures will need to be processed by contesters to prove that they indeed

are in the possession of fast algorithms/code and not just a lucky run or a weakness in the picture. The round won't be so much about performance

though that plays a roll as well, but also about proving that it was done with computer code.

However I can already see a cheating possibility: using multiple computers or even whole clusters to do computations on solvers.

So I am afraid that this idea is no good... but I will do it anyway just to make sure that it was computerized ;) :)

Perhaps in the future there will be also be an open source round after the main winner has been decided to try and improve

on each other's code... for now the contest can remain half-open half-closed, meaning sharing of idea's ok... sharing of code not really.

After carefull analysis by mostly watching the new visualizations below I do suspect Rob Pratt of either:

1. Using the input from James Dow Allen to base his own entry/solution on.

or

2. Using the same kind of algorithm and/or software as James Dow Allen.

or

3. It's simply James Dow Allen pretending to be Rob Pratt.

It's very suspicious to say the least... you be the judge...

The coordinate map shows many similarities between the entry from Rob's and that of James'es.

Hmmm Rob has let us all know that he (probably) used a solver.

The solver goes by the name SAS/OR.

(Most interesting... I never heard of it ;) :))

This could mean that James is actually also using a solver lol ;) :)

Futher interesting details is that Rob claims that the solver claims that it's optimal at 217 cells... most interesting :)

The question is now:

How long did Rob take to solve the model ? If it was long then this could explain why James was worried about other's stealing his "solution".

Apperently James stopped the solver early on ?!?

However James has let me know from the start that he used something called "greedy".

Rob has said "set covering problem".

This leads me to the "greedy algorithm" which is apperently suited for "set covering problem".

The funny thing is I came really close to reinventing the "greedy" algorithm.

The only problem was with my heuristic... it probably wasn't the correct one... but it came close.

I shall now attempt to code the pretty easy "greedy" algorith.

I expected to get the same results as James... Unless ofcourse he made a bug... he did mention something about having some bugs and "requiring to much effort" to make it better hmmm ;) :)

Perhaps my newly-to-be-created implementation will do better than his... that would be amuzing ! ;) :)

Time will tell ! ;) :)

I am also starting to wonder if these guys can actually solve the "non-overlapping" problem ! ;) :)

So far I am the only "non-overlapping" contester ! ;) :)

In picture form:

In text form (217 lines/boxes):

BoxifyMe1RobPrattEntry1.txt

Skybuck's BoxifyMe Entry8 (non-overlapping, "greedy1") (328):

Ok I implemented the greedy algorithm exactly like I should according to the concept.

It's kinda amazing in two ways:

1. First of all it creates more boxes than my best non-overlapping algorithm.

2. Second of all it does seem to produce large boxes. So perhaps this algorithm create the most free space or so... not sure.

Perhaps it can be modified by changing the heuristics or so... currently there is just one heuristic:

"allocate largest/most free unused space first"

It's running time is not to bad... a few seconds or so... and this was with the array in wrong memory access order which is slow ;) :)

Correcting it and using a 1D array would probably speed it up quite a lot ;) :)

Though even a few seconds is still pretty bad if it's to be used for many pictures, so running time is definetly

something that needs to be look into and "contested" ;) :) for usuability's sake ! ;) :)

Anyway... James has let me know via e-mail that he has problems reaching this site... he suspects it's on his side... but it could also be because

I am updating a lot... I won't stop updating because I have a lot of stuff to say and analyze so I will continue... when stuff/I slow down it will stabilize ;) :)

(For example me go sleep or go ahead with other project ;) :))

Anyway I want to say some more words about this supposedly "greedy" algorithm.

1. First of all it's slow.

2. Second of all the whole problem is probably NP complete which sure shows when trying out that algorithm with overlapping. Granted memory access was implemented wrongly..

but still it's hellish slow.

3. James claims he used "greedy" algorithm as well.. I seriously starting to doubt that... since it requires a lot of pixel lookups. Or he has something special.

4. He also seems to have a weird computer situation... weird internet access, weird loading of this site... it all starts to make sense to me...

5. He probably using a solver that's what I am thinking... maybe a solver will somehow execute faster.

6. I am starting to get very curious about what code they are using... because I am not getting any where close to their outputs ! LOL.

But so are they... they are not getting anywhere close to my outputs when it comes to non-overlap ! LOL ;) :)

Man what a situation, kinda funny.

So conclusion: For now I think the greedy algorithm is not suited for this overlappig problem unless there is some kind of optimization or better heuristic.

Hmmm. If "we" contesters ever go open source it will be most interesting to see what everyboy made ;) :)

Perhaps it's time for me to move on with my own implementations and start working on the physics part.

I actually don't believe that the other two contesters have any fast algorithms at all... and I do need faster algorithms for the physics part.

Otherwise I would have to store all outputs in a database somewhere.. for the game... that's not cool.

Calculating it on the fly would be much better.

Perhaps it's time to call a winner, at least for the overlapping part of the contest.

I will give it some more time for others... and then when the physics stuff is done... it's time to look back at what they made.

But pointless really... the sas dude made it for sas lol...

So that leaves James... and he's doubtfull ;) :) I kinda believe his C stuff... but the pictures show otherwise hmmm ;) :)

Ofcourse as solutions get closer to the optimum they could start looking similair... hmmm.

Maybe I should give it some more thought how to optimize greedy a bit more... but even if it would run faster... it would probably not get close to the winning score so far...

So the greedy algorithm does not seem to become optimal for this problem ?!?

So last possibility to try is probably implement a solver manually... but can I implement the power of a SAS solver which has 30 years of experience ?

I doubt it... how much running time did Rob use ? These remain unanswered questions.

Without executables, without code, without more pictures this contest is starting to break down in a sort of "cheat" fest ;) :)

Use as much time as you want... surrrrreeeee.

Use as expensive software as you want to solve it... surrrreeeee.

Don't develop any algorithms yourself but use other's... surrreee LOL but ok this is less bad ;) :) Implementations count too ! ;) :)

I am starting to dislike this contest LOL it's a funny contest.. but shitty too LOL and it's all my doing ! LOL.

I need better contest rules next time ! LOL ;) :)

But at least this "openness" learned me some stuff from others and that's usefull too ! ;) :)

I really don't want to do heavy testing for this contest ?!? With a zillion of pictures ?!?

But yet I have to I guess, I most know what algorithm executes fastest.

So perhaps it's time I start asking for code to be able to test on my own system... because how could I ever trust their timings ?

And how could they trust mine ?

Then again I don't really wanna give away my code as well ;) :) It's too good ! LOL.

Nope definetly can't give away code LOL.

Ok that leaves one possibility:

EXECUTABLES ! ;) :)

But ofcourse I won't run them on my system.

And now comes the big problem.

I used Delphi 2010... which was nice... less crashable... I am pretty sure I can compile with Delphi 2007.

And the nice thing is then I can run my tests in Windows 95 in virtual machine.

But who has Windows 95 compatibility nowadays ?!? I guess nobody except me perhaps ;) :)

So there is one thing I can do about that... and that is install windows xp in vmware or so... or pocket pc... if that fails then this contest is over I guess.

Unless people wanna trust me with their code... and me do the timings.

I have this weird feeling that windows xp is not gonna work in vmware or pocket pc... it probably too complex.

Even if it did.. maybe it would run too slow.

For now there is only one real contester it seems... capable of producing an executable and that's James.

So I am going to ask James if he can produce a windows 95 compatible executable ?!?

If so they we can proceed with the contest.

If Rob can do it too then that would be great as well ofcourse ! ;) :)

Anyway here it is:

In picture form:

In text form (328 lines/boxes):

BoxifyMe1SkybuckEntry8GreedyV9.txt

David Eisenstat's BoxifyMe Entry1 (overlapping, "IBM ILOG CPLEX" ) (217):

A new contester has entered the contest, pretty much to verify the overlapping results of the solver (SAS/OR) used by Rob Pratt .

The solver used by David (IBM ILOG CPLEX) hereby confirms the optimal result of 217 boxes for the overlapping variation of this contest.

It's also interesting to see that apperently David Eisenstat's overlapping entry/solution is different than that of Rob Pratt's overlapping entry/solution.

This can be clearly seen from the heatmaps down below. So apperently multiple optimal solutions exist.

This can also be seen from the wiremaps down below.

Further differences can also be seen in the coordinate maps.

Furthermore it seems David Eisenstat's solution contains less overlapping, which I find a bit interesting.

I would consider his solution a better solution than that of Rob Pratt. So perhaps Rob Pratt can still do better ?! ;) :)

However the new sorted area map has revealed something interesting about David's solution.

David's solution has a few single pixel boxes here and there and I would consider that less good for physics.

So Rob Pratt's solution is probably a bit more robust/stable, but also perhaps a bit slower because of the heat.

It's too close to call which one is better, and for now it doesn't matter that much.

But for me robustness probably goes before speed.

So all in all I would think Rob's is slightly better than David's.

So I stand corrected by the new visualizations ! ;) :)

However if the physics engine has no problem with a single box next to other boxes then it wouldn't be a problem and then it comes down to speed.

For now my bet is on David's solution to be a bit faster physics wise then Rob's...

Only time/a physics test can tell which one will be faster ;) :)

Here it is:

In picture form:

In text form:

BoxifyMe1DavidEisenstatEntry2NonOverlapping.txt

David Eisenstat's BoxifyMe Entry1 (non-verlapping, "IBM ILOG CPLEX" ) (264):

And now for the most spectacular entry in this contest. The first secondary contester in this contest for the non-overlapping variation of this contest.

And what an entry it is ! Not only is it the best non-overlapping entry so far but David also claims that his solver claims that it's optimal !

And now only that... but this makes David the new and possibly final King of the Contest of this round of the contest !

Unless somebody else can prove that there is actually a better solution for either overlapping or non overlapping then he has won this round of the contest !

My congratulations go to David Eisenstat for beating everybody else to it !

Also my thanks go to him for providing the optimal solution for the non-overlapping variation.

It's also quite amazing and interesting to see that it's quite higher than the optimal overlapping solution.

Furthermore my/Skybuck's non-overlapping entry 6 codenamed "edge" is very close to the optimal result, only 10 boxes difference.

That's pretty nice.

James performance/algorithm for the overlapping variation was still better than my non-overlapping performance/algorithm.

He was 9 boxes away from the optimal result, and is possibly also a more difficult problem to solve.

So for now this will probably but James at third place.

And that means I am last LOL :((( boooeehoeee LOL.

I am happy about that. It's lonely in the top ! =D At least now I have some people to lookup too and hold me company and give me some nice warmth ;) :)

But ! The contest is not over yet. Because let's consider this round to "theoretical" round.

This round apperently has proven that it is possible to solve this problem with solvers within reasonable time.

This contest has only been rounding for about 3 days. I have no idea how much time their solvers spent on calculation these solutions.

But we will find out soon enough... because I am already thinking about and planning round 2 ! Yes ladies and gentlemen there will be a round 2 !

And it's going to be spectacular. At least I think so...

It's also going to be a lot of fun to look at I promise ! ;) :)

Especially if you are able to run windows executables.

(In case any of the contesters is running another operating system, let me know and I will see if I can generate an executable for that as well).

This round will remain open to for two reasons:

1. Additional solver confirmations.

2. Additional algorithm entries which will play a role in the next round.

Here it is:

In picture form:

In text form:

BoxifyMe1DavidEisenstatEntry2NonOverlapping.txt

Skybuck's BoxifyMe Entry9 (non-overlapping, "greedy2") (279):

I decided and wanted to give the greedy algorithm one more try... but this time... instead of selecting the largest rectangle and sticking with that... the smallest rectangle of the largest is now

selected first... and disabled... and then it repeats. This has indeed improved the non-overlapping result for the greedy algorithm. However my own non-overlapping algorithm seems to perform slightly better and probably a whole lot faster too.

Perhaps one last idea to try for an algorithm is multiple passes, try it first, then try to improve on it by selecting edge/single pixels first. If this would actually work and be any good remains to be seen ;) :)

Anyway I thought it was kinda interesting and was easy to implement/make some changes, so here you go... some more nice visualizations to look at... At least now I don't have to keep wondering about it ;) :)

I am not completely statisfied yet... I still have to come up with a good overlapping algorithm... hmm.

Here is is:

In picture form:

In text form:

BoxifyMe1SkybuckEntry9GreedyNonOverlapV12.txt

Comparison section:

I have re-generated all pictures from textfiles. During my development I think my program overwrote some pictures. I noticed

some pictures looked too samiliar so I regenerated them and uploaded them... I think it's ok now ;) :)

Also I think Delphi's 2010 randseed is initialized differently by it... I have now set a fixed randseed so pictures will look the same from now on ;)

I also think there was an imposter on the thrown ! LOL.. The imposter has been thrown into prison lol.

And the rightfull picture is now on the thrown !  ;) :)

(Zoom factor has been reduced a bit from 600x600 to 500x500)

A new section has been added called "Free Inner Area".

I was kinda interested and wondering for a while which algorithm/entry was most efficient for the inner regions.

This could be interesting for compression purposes or so.

To me it looked like "greedy1" was the most greedy in this regard... and yup.. this has been confirmed by the new visualization.

Now ofcourse the other contesters did not design their entries for such a situation, but it's still kinda interesting.

"Greedy1" completely smashes all others with a whoping 1806 free inner pixels ! ;) :)

Followed by the runner up; "boxy1" with 1386 free inner pixels.

See pictures down below.

Similarity section:

Today 16 may 2012 I decided to investigate into the claims that some contenders/contesters might have used solutions from others (as James claimed or feared) to cut some corners and save some work/processing.

It's an interesting claim/strategy for others to continue work on solutions of others which were found by/via solvers.

Today I came up with an easy visualization idea which simply compares a solution to all other solutions except itself ofcourse.

Each solution is given a unique color which is indicated in the border lines of the picture.

Then if a solution contains rectangles which are exactly the same as in another solution, then this rectangle is drawn into the picture with the color of the other solution.

If multiple other solutions have the same rectangle then the colors are averaged.

This should give some kind of idea what's going on... so let's examine the pictures waaaayyy down below ;) :)

There could be some thruth in James's claims... Rob Pratt's solution seems somewhat similar to James's solution.

A closer inspection of Rob Pratt's solution does show a striking similarity with James's solutions, it seems

lots of boxes where copied by Rob Pratt, another explanation could be the solver found a similar solution.

(Rob and James's solution have about 130 similar rectangles, that's a bit too much to be a coincidence ? ;))

For now this will have to do, because comparing each solution to each other on a 1 by 1 basis would generate too many pictures.

Perhaps in the future I might post that but for now those pictures shall remain on my drive ;) :) I did take a look at it though kinda interesting :)

(There is lots of green in Rob Pratt's visualization which comes from James solution).

The colors could be better chosen though, a bit too much green and david's is too dark.

Perhaps I will re-do the colors for the similarity section in the future, but for now this will have to do ;) :)

Color-map:

Heat-map:

Wire-map:

Coordinate-map:

Sorted area-map (from largest area(darkest) to smallest area(lightest)):

Free Inner Area (Second number represents free inner pixels):

Similarities (Second number represents similar rectangles in other solutions):

Tessellation by OpenGL's Utility Library (Also known as GLU (not to be confused with GLUT ;))):

(Bitmap/image converted to polygons and then tessellated by GLU)

GLU Tessellation 1 on inefficient polygons (many redundant verteces on edges/straight lines) (1682 triangles):

(Wired lines are +1 pixel on right side and +1 pixel on bottom, I didn't correct this because I don't mind, it looks good enough,

 this makes it appear as if a pixel is missing near top right corners, but this is not a problem, the colorized images down below prove that it's ok when drawing filled polygons/triangles/primitives.)

GLU Tessellation 1 (colorized):

GLU Tessellation 1 (randomly shaded, mostly for fun, a bit crowded):

GLU Tessellation 2 on efficient polygons (redundant verteces removed on edges/straight lines) (826 triangles):

GLU Tessellation 2 (colorized):

GLU Tessellation 2 (randomly shaded mostly for fun, looks nice):

Better but still quite inefficient. By comparision: Best non-overlapped version would have 2 x 264 = 528 triangles.

Best overlapped version would have 2 x 217 = 434 triangles.

Conclusion:

Best non-overlapped version would have 4 x 264 = 1056 edges.

Best overlapped version would have 4 x 217 = 868 edges.

Triangulated version would have 3 x 826 = 2478 edges.

Possible applications which come to mind for non-overlapping:

1. Non-colliding/non-penetrating physics.

2. Compression. (Could be combined with bin-packing)

3. Memory efficient texture maps for transparent images. (Could be combined with bin-packing)

Possible applications which come to mind for overlapping:

1. Colliding/penetrating tolerant physics. (Extra redundancy could help prevent fall throughs, less boxes->so less collision/edge checks so perhaps more performance.)

2. Compression. (Perhaps for color/bit planes)

Further idea's for implementations (from newsgroup contributions):

1.1 Area-based growth decision moment. (Calculate area of potential rectangles and select largest one)

(Honorable mention, idea came from: "Jongware" modified a little bit by me ;):) he said smallest, I say biggest ;))

(my modification has been tried in "greedy1" didn't do to well)

1.2 Perhaps try the original idea from jongware with "smallest rectangle" first. (This will probably get rid of those pesky little pixels ;))

(This has been tried in "greedy2" and does indeed perform better for non-overlapped version, overlapped version not tried yet)

2. "Perfect" triangles. When pixels/rectangles/boxes have the form 3x3 or 4x4 or 5x5 or 6x6 with a perfect diagonal.

(Honorable mention, idea came from: "Brett Davis")

I might allow triangles in future extension of this contest, so contesters would be wise to start thinking about

such implementations ;)

Bye,

Skybuck ! ;) :) =D