Programming Contest: BoxifyMe

S

Skybuck Flying

Skybuck's Boxify Me Programming Contest:

http://www.skybuck.org/BoxifyMe/

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

(See website for this text and the picture)

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 (e-mail address removed)

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

Bye,
Skybuck :) =D
 
S

Skybuck Flying

Ok,

I just finished programming my algorithm idea... so far it seems to be ok...
but I am not yet sure... tomorrow I will write a verification program to
make sure that everything is a.o.k.

For now I have added my first entry to the webpage... a colorized picture
showing all the boxes is included... (the colors were at random so maybe not
all boxes seperated correctly by a color but it gives some idea, I might
correct this later on with a more reliable colorization algorithm ;) :))
what matters mostly is the output in text form as described it's now
available too.

My algorithm produced: 306 lines that means 306 boxes where used !

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

(See bottom of page for update):

http://www.skybuck.org/BoxifyMe/

Bye,
Skybuck =D
 
S

Skybuck Flying

Hmm I just realized something... this could be interesting for some kind of
compression or something... but that's not what it was intended for...

Oh well.. maybe I look into that sometime...

Bye,
Skybuck.
 
S

Skybuck Flying

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 (305
lines/boxes).
(One box less ;) :))

See bottom of the page for second picture and textfile ! ;)

http://www.skybuck.org/BoxifyMe/

Looks much better to me ! ;) =D

Bye,
Skybuck.
 
S

Skybuck Flying

I have created a little animation of how the algorithm works... I am pretty
sure you can't actually tell the details from it ;) :)

So here it is for your and mine viewing pleasure... and gloating ofcourse !
LOL ;) :)

"Programming Contest: BoxifyMe, Skybuck's Entry 2 Animation 1"


Bye,
Skybuck ;) =D
 
S

Skybuck Flying

The contest has turned into an intrigueing development.

A contester has presented himself and stepped forward into the dragon's
layer !
;) =D

And what an unforgettable entry it was ! ;) =D

It was shocking at first and marvoulous at second glance.

It has provided a new insight into a possible direction of solutions.

Which type of solution is actually the most high performant with the
favorite/popular engine know as box2d remains to be seen... yes ladies and
gentlemen... that's what this contest is after all for, for my personal
purpose, ofcourse you may use it for whatever you like... for the contest it
doesn't matter because it's now split up into two sections:

1. Non-overlapping solutions.
2. Overlapping solutions.

For more details see the website which includes a picture of the second
contester ! ;) :)

And also his bloody bloody good textfile ! ;) =D

Perhaps I will also start to develop an algorithm for overlapping solutions
! ;) =D

Also overlapping solutions could be kinda nice for explosion effects... it's
not nice and clean... but a bit messy... could be gooood ! ;) =D

So both are interesting types of solutions ! ;) =D

The website had been updated:

http://www.skybuck.org/BoxifyMe/

Bye,
Skybuck.
 
L

Lew

Skybuck said:
The contest has turned into an intrigueing development.

A contester has presented himself and stepped forward into the dragon's
layer !
Click to expand...

A draconian layered architecture?! Are we talking about a module that needs
refactoring?

This is not one of the malapropisms on which I'd normally comment, but this
one is funnier than most.
 
J

James Dow Allen

A contester has presented himself and stepped forward into the dragon's
layer ! ;) =D
Click to expand...

Since I'm the "other contester," let me make some comments.
Skybuck: If any of these comments seem critical, please know
that I'm *not* annoyed. :) I have fun with the contest.
My comments are good-natured and intended only to be helpful.

(1) I'm curious how others interpreted the problem definition.
Pick one:
(a) overlapped boxes forbidden
(b) overlapped boxes allowed
(c) ambiguous; clarification required.
I thought it interesting that Skybuk assumed (a), James (b).
Given James' track-record in communication, I'm probably in the
minority. :)

(2) Skybuck: Publishing private e-mails without permission is
an etiquette No-no. (And perhaps even illegal in some cases!)
I'm happy, and grant permission to publish my e-mail to you.
But you may want to be more cautious in future.

(3) Most of the programming I do these days is purely
recreational, for the fun of writing the code. I had fun addressing
this puzzle, and that's my reward; Skybuck is free to use my
result as he wishes. At some point I'll be happy to mail him
my source code, if he wants it.

(4) Still, this was billed as a "Contest" not as "Cooperative
Endeavor", so publishing submissions while the "Contest"
is in progress makes poor sense. I'd be happy if Skybuck
showed the best score *without* the boxes that produced that
score, but note that the highly respected Zimmerman Contest
doesn't even do that.

(5) On his page, Skybuck asked about my program's time.
I spent about 90 minutes altogether writing the code. I didn't
actually time its *execution*, but it was quite fast, perhaps
one second or less.

(6) I won't detail the algorithm except to note that it can
be described as 3 passes. The first pass solves a straightforward
problem, though somewhat tedious to implement.
It needed 6 for-loops.
The 2nd pass was
while (1) { qsort(...); ... }
The 3rd pass would have been most difficult of all, but on this
particular test image, the 2nd pass produced a solution with
a surprising property that avoided the need for any but a
trivial 3rd pass implementation. (So "surprising" to me,
that I double-checked. Perhaps I should now triple-check :)

(7) I may stop work on the problem. Not because I'm fully
satisfied, and certainly not due to any annoyance, but simply
because I have no inspiration for further progress. There
are straightforward ways to proceed; but they would be rather
tedious to code, and they might not save even a single box.

Best wishes to all, and I hope others participate too.
James Dow Allen
 
L

Lew

James said:
(2) Skybuck: Publishing private e-mails without permission is
an etiquette No-no. (And perhaps even illegal in some cases!)
Click to expand...

I doubt that it's illegal. Email is by definition not private. Given the
impossibility of expectation of privacy, you'd have a hard time establishing
any tort, much less crime. If the person had signed a non-disclosure
agreement with you you might establish a civil wrong, but they didn't, did they?

So publish away, other person.
I'm happy, and grant permission to publish my e-mail to you.
But you may want to be more cautious in future.
Click to expand...

Only for courtesy's sake, but then, did you ask them to keep the material
confidential? If not, then they were completely within their rights.

If you were to publish an email I sent you "privately", without a
non-disclosure agreement and absent my request to you to keep the contents
confidential, I would not even view that as an etiquette violation. I see
that you do, but you may want to be more cautious in the future about
representing your opinion as a universal truth.
 
A

Arved Sandstrom

Since I'm the "other contester," let me make some comments.
Skybuck: If any of these comments seem critical, please know
that I'm *not* annoyed. :) I have fun with the contest.
My comments are good-natured and intended only to be helpful.

(1) I'm curious how others interpreted the problem definition.
Pick one:
(a) overlapped boxes forbidden
(b) overlapped boxes allowed
(c) ambiguous; clarification required.
I thought it interesting that Skybuk assumed (a), James (b).
Given James' track-record in communication, I'm probably in the
minority. :)
Click to expand...

Me I assumed nothing, and so far I haven't detected any ambiguity
either. I'd consider the absence of (a) to strongly imply (b).

[ SNIP ]

I'm with you on the other points you make. Still, I detect no malice,
just enthusiasm, so I can live with the "contest" procedural warts. :)
(7) I may stop work on the problem. Not because I'm fully
satisfied, and certainly not due to any annoyance, but simply
because I have no inspiration for further progress. There
are straightforward ways to proceed; but they would be rather
tedious to code, and they might not save even a single box.

Best wishes to all, and I hope others participate too.
James Dow Allen
Click to expand...

I'm definitely playing with it, both from the standpoint of thinking
through the algorithms and also refreshing my knowledge of a rather
esoteric programming language. The problem itself has interesting
applications to image compression and recognition.

One interesting follow-up is image reconstruction from the box
information. It's obviously trivial to draw each box with a known fill
colour, but what if it was desirable to draw the "real" boundary only,
with no artificial interior box boundaries? In that case I suspect (but
haven't tested) that a boxification solution based on (a) would be more
efficient.

AHS
 
B

BartC

Arved Sandstrom said:
Me I assumed nothing, and so far I haven't detected any ambiguity either.
I'd consider the absence of (a) to strongly imply (b).
Click to expand...

Although not stated, I assumed that a box cannot contain any black pixels,
otherwise the solution is trivial: one box the same size as the image.

At which point I gave up...
 
L

Lew

Arved Sandstrom wrote
Although not stated, I assumed that a box cannot contain any black
pixels, otherwise the solution is trivial: one box the same size as the
image.
Click to expand...

I keep thinking of calculus, topology and fractals as I read through this
discussion.

This contest / gedankenexperiment leads to a family of related puzzles.
Describe the minimum set of boxes that encompass the (specified set) with
error <= δ. Extend the problem to 3 (or more) dimensions. Apply to
linguistic data sets. Allow shapes other than boxes to approximate the set.
(Voronoi tessellations, here we come!)

<http://www.origamitessellations.com/2006/01/25/voronoi-tessellation-test-1-twisted/>
 
M

Mike Schilling

BartC said:
Although not stated, I assumed that a box cannot contain any black pixels,
otherwise the solution is trivial: one box the same size as the image.

At which point I gave up...
Click to expand...

I also got that far and declared the problem solved.
 
J

James Dow Allen

On Dec 12, 9:37 pm, Lew wrote:
(responding to the least interesting part of my post :-( )
I doubt that it's illegal....

If you were to publish an email I sent you "privately", without a
non-disclosure agreement and absent my request to you to keep the contents
confidential, I would not even view that as an etiquette violation.  I see
that you do, but you may want to be more cautious in the future about
representing your opinion as a universal truth.
Click to expand...

Lest gentle reader fear that Lew might be correct, you can read
http://arborlaw.biz/blog/2007/07/17/legal-issues-in-forwarding-email/
Or use Google to discover that myriads of people regard
publishing private e-mail, whether legal or not, as an etiquette
violation.

Skybuck intended no offense, and gave no offense, so my comment
was intended as a gentle warning for future reference. Not about me
(with few secrets, or at least few of a type I'd disclose to a
stranger!),
but that *SOME PEOPLE* feel strongly about this.

Perhaps it's a generational thing. How old are you, Lew?
I was born in the Truman Administration. (Gak!)
You yung'uns scribbling on each others' Facebook Walls may
have a completely different view on privacy than us old fogeys. :)

Best ever,
James
 
M

Mike Schilling

James Dow Allen said:
On Dec 12, 9:37 pm, Lew wrote:
(responding to the least interesting part of my post :-( )


Lest gentle reader fear that Lew might be correct, you can read
http://arborlaw.biz/blog/2007/07/17/legal-issues-in-forwarding-email/
Or use Google to discover that myriads of people regard
publishing private e-mail, whether legal or not, as an etiquette
violation.

Skybuck intended no offense, and gave no offense, so my comment
was intended as a gentle warning for future reference. Not about me
(with few secrets, or at least few of a type I'd disclose to a
stranger!),
but that *SOME PEOPLE* feel strongly about this.

Perhaps it's a generational thing. How old are you, Lew?
I was born in the Truman Administration. (Gak!)
You yung'uns scribbling on each others' Facebook Walls may
have a completely different view on privacy than us old fogeys. :)
Click to expand...

I don't know why e-mail and snail mail would be different. If I send you a
letter the old-fashioned way, you do not have the right to publish it
without my permission. You can see this in books where the author does
publish letters he's received. Lacking permission, he must disguise or only
summarize them.
 
L

Lew

On 12/12/2010 02:17 PM,
James Dow Allen wrote
Interesting article.

I see your point about the netiquette. His points about the legal issues
clear up my confusion as well. Thank you.

I'm a fuddy-duddy when it comes to Facebook,

Mike said:
I don't know why e-mail and snail mail would be different. If I send you
a letter the old-fashioned way, you do not have the right to publish it
without my permission. You can see this in books where the author does
publish letters he's received. Lacking permission, he must disguise or
only summarize them.
Click to expand...

Or cite excerpts under fair use doctrine.

--
Lew
Anyone who responds to one of my public posts, e.g., on a Usenet forum, via a
private email directly to me acknowledges that I intend to republish such
communication back to the public forum or forums from which the message arose,
and by dint of so responding to a public communication grants me the
non-revocable and non-transferable license to reproduce their communication at
my discretion, in full or in part, without further restriction and without
remuneration or compensation to the copyright owner, in perpetuity.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Programming Contest: ConvexifyMe 5
Shoelace Formula 5
Astronomy image processing contest 0
Java programming 1
How to save textBox values into a xml-file(with naming an choosing directory)? 1
I Need Help with making a function that draws in a canvas using location data. 1
Drawing missing in bitmap in a pure C win32 program 4
Remove Start Button from Clock 2

Members online

Total: 216 (members: 4, guests: 212)
Robots: 153

Forum statistics

Threads
474,262
Messages
2,571,044
Members
48,769
Latest member
Clifft

Latest Threads

Top