Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

Sounds like a case for Branch and Bound.

I would partition the problem space by adding the next free category to either last used column or the next empty column. The root problem would be "category 1 in column 1", so the children would "category 2 in column 1" and "category 2 in column 2", etc. The low boundary for each solution is the height of the highest column, and the solution's high boundary is maximum(sum of heights of free categories, lower boundary). There is a constraint (free categories > empty columns) that has to be fulfilled to assure there will not be empty columns.

It's probably best to generate the solution tree breadth-first as you will descend far down the left side very quickly if the global lower and upper boundaries have not been narrowed down. Breadth-first would garantuee that you limit them soon. On the other hand, for larger problems the breadth-first approach will also require more memory to hold the solution tree.

I tried to write code yesterday but it was 3am and my mind wouldn't cooperate. Now I've just gotten up way waay too late into the day and it still doesn't. When I'm feeling a bit fresher I will update here with some code (or capitulation *g*). The tricky problem is coming up with a convenient data structure - I tried anonymous arrays for the columns, but it's inconvenient to have to deep copy to generate the child problems.

Update: sorry, would take too much time right now. :-( I will have a spare evening in a few days and may I'll get back to it then. Sigh..

Makeshifts last the longest.

In reply to Re: Puzzle: need a more general algorithm by Aristotle
in thread Puzzle: need a more general algorithm by Ovid

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    [erix]: Alvin Lee dead too -- we're stuck with Karl, I'm afraid :)
    [erix]: ok, one to remember Alvin Lee (Ten Years After - Help Me)
    stevieb has a significant craving to hear "My guitar gently weeps"...
    [Corion]: stonecolddevin: I think Jack White is highly regarded, but ...
    [Corion]: ... I'm not really knowledgeable about good guitar players
    [stonecolddevin]: I've been on a Stevie Ray Vaughan kick lately: https://www. v=wVjdMLAMbM0
    [stonecolddevin]: Corion I haven't heard much of his work to be honest.
    [erix]: here is a nice cover, stevieb
    [planetscape]: hello, Corion

    How do I use this? | Other CB clients
    Other Users?
    Others taking refuge in the Monastery: (9)
    As of 2017-06-22 21:26 GMT
    Find Nodes?
      Voting Booth?
      How many monitors do you use while coding?

      Results (531 votes). Check out past polls.