Programming Contest: BoxifyMe

Discussion in 'C Programming' started by Skybuck Flying, Dec 11, 2010.

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

    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
     
    Skybuck Flying, Dec 11, 2010
    #1
    1. Advertising

  2. 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
     
    Skybuck Flying, Dec 11, 2010
    #2
    1. Advertising

  3. 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.
     
    Skybuck Flying, Dec 11, 2010
    #3
  4. 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.
     
    Skybuck Flying, Dec 11, 2010
    #4
  5. 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"

    http://www.youtube.com/watch?v=C1EJ7eO96AE

    Bye,
    Skybuck ;) =D
     
    Skybuck Flying, Dec 11, 2010
    #5
  6. Skybuck Flying, Dec 11, 2010
    #6
  7. 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.
     
    Skybuck Flying, Dec 11, 2010
    #7
  8. Skybuck Flying

    Peter Webb Guest

    Peter Webb, Dec 11, 2010
    #8
  9. Skybuck Flying

    Lew Guest

    Skybuck Flying wrote:
    > The contest has turned into an intrigueing development.
    >
    > A contester has presented himself and stepped forward into the dragon's
    > layer !


    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.

    --
    Lew
     
    Lew, Dec 11, 2010
    #9
  10. "Peter Webb" <> wrote in message
    news:4d037837$0$17760$...
    >
    > "Skybuck Flying" <> wrote in message
    > news:9d3af$4d035d47$54190f09$1.nb.home.nl...
    >> It seems like I'm making rapid progress:
    >>
    >> Already entry 3 from me:
    >>
    >> "Programming Contest: BoxifyMe, Skybuck's Entry 3 Animation 1"
    >>
    >> Number of boxes down from 305 to 285
    >>
    >> http://www.youtube.com/watch?v=uzjodCJUpAw
    >>
    >> Website updated too:
    >>
    >> http://www.skybuck.org/BoxifyMe/
    >>
    >> Bye,
    >> Skybuck.
    >>
    >>

    >
    > http://en.wikipedia.org/wiki/Karnaugh_map


    The description says it's ment for aiding humans and their pattern detection
    capabilities.

    Question is: Could it also be used to do massive calculations/solutions by a
    computer program ?

    I have seen some things that might suggest so... but I am not sure...

    Bye,
    Skybuck.
     
    Skybuck Flying, Dec 12, 2010
    #10
  11. Skybuck Flying

    John Metcalf Guest

    Hi Skybuck,

    I didn't see a deadline mentioned. Is there any chance you can make
    it after the deadline for the International Corewar Programming
    Contest?

    http://www.corewar.info/tournament/icpc1

    Thanks,

    John


    On Dec 11, 5:00 am, "Skybuck Flying" <>
    wrote:
    > 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).
     
    John Metcalf, Dec 12, 2010
    #11
  12. On Dec 11, 8:07 pm, "Skybuck Flying" <>
    wrote:
    > A contester has presented himself and stepped forward into the dragon's
    > layer ! ;) =D


    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
     
    James Dow Allen, Dec 12, 2010
    #12
  13. Skybuck Flying

    Lew Guest

    James Dow Allen wrote:
    > (2) Skybuck: Publishing private e-mails without permission is
    > an etiquette No-no. (And perhaps even illegal in some cases!)


    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.


    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.

    --
    Lew
     
    Lew, Dec 12, 2010
    #13
  14. On 10-12-12 05:55 AM, James Dow Allen wrote:
    > On Dec 11, 8:07 pm, "Skybuck Flying"<>
    > wrote:
    >> A contester has presented himself and stepped forward into the dragon's
    >> layer ! ;) =D

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


    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


    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
     
    Arved Sandstrom, Dec 12, 2010
    #14
  15. Skybuck Flying

    BartC Guest

    "Arved Sandstrom" <> wrote in message
    news:Qr6No.10081$...
    > On 10-12-12 05:55 AM, James Dow Allen wrote:
    >> On Dec 11, 8:07 pm, "Skybuck Flying"<>
    >> wrote:
    >>> A contester has presented himself and stepped forward into the dragon's
    >>> layer ! ;) =D

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

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


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

    --
    Bartc
     
    BartC, Dec 12, 2010
    #15
  16. Skybuck Flying

    Lew Guest

    James Dow Allen wrote:
    >>> (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. :)


    Arved Sandstrom wrote
    >> 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).


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


    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/>

    --
    Lew
     
    Lew, Dec 12, 2010
    #16
  17. "BartC" <> wrote in message
    news:ie2uek$4pn$-september.org...
    >
    > 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...


    I also got that far and declared the problem solved.
     
    Mike Schilling, Dec 12, 2010
    #17
  18. On Dec 12, 9:37 pm, Lew wrote:
    (responding to the least interesting part of my post :-( )

    > James Dow Allen wrote:
    > > (2) Skybuck:  Publishing private e-mails without permission is
    > > an etiquette No-no.  (And perhaps even illegal in some cases!)

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


    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
     
    James Dow Allen, Dec 12, 2010
    #18
  19. "James Dow Allen" <> wrote in message
    news:...
    > On Dec 12, 9:37 pm, Lew wrote:
    > (responding to the least interesting part of my post :-( )
    >
    >> James Dow Allen wrote:
    >> > (2) Skybuck: Publishing private e-mails without permission is
    >> > an etiquette No-no. (And perhaps even illegal in some cases!)

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

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


    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.
     
    Mike Schilling, Dec 12, 2010
    #19
  20. Skybuck Flying

    Lew Guest

    On 12/12/2010 02:17 PM,
    James Dow Allen wrote
    >> Lest gentle reader fear that Lew might be correct, you can read
    >> http://arborlaw.biz/blog/2007/07/17/legal-issues-in-forwarding-email/


    Interesting article.

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

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


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

    Mike Schilling wrote:
    > 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.


    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.
     
    Lew, Dec 12, 2010
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Robby Findler

    2005 ICFP Programming Contest

    Robby Findler, May 29, 2005, in forum: Java
    Replies:
    0
    Views:
    380
    Robby Findler
    May 29, 2005
  2. Thaddeus L Olczyk

    Programming Contest--ICFP

    Thaddeus L Olczyk, Jun 23, 2003, in forum: C++
    Replies:
    0
    Views:
    1,292
    Thaddeus L Olczyk
    Jun 23, 2003
  3. Replies:
    0
    Views:
    350
  4. Catherine Chronaki
    Replies:
    0
    Views:
    348
    Catherine Chronaki
    Jan 2, 2004
  5. Skybuck Flying

    Programming Contest: BoxifyMe

    Skybuck Flying, Dec 11, 2010, in forum: Java
    Replies:
    33
    Views:
    879
    Skybuck Flying
    Dec 15, 2010
Loading...

Share This Page