laziness, impatience, and hubris PerlMonks

Comment on

 Need Help??
Thinking vaguely...

Notation:

• Columns: N
• Category count: Q

Assuming the problem makes sense (Q>N), yet another way to think about the problem space is to enumerate the cells like this:

1 3 5 7
2 4 6 8

Then, if we index the categories by 0...Q-1 (fine because the category order must be preserved), we can consider the location of a category to be L(category index). The nature of this location is yet to be determined. I see that the categories always fill up from the top down.

Now, implementation details are critical...so I may be off on a wild goose chase. I'm envisioning this target (X)HTML table as a single row with a single cell for each column. Then the top-down ordering is automatic, and we're just calculating where to put the table cell delimiters. In this case, the location L corresponds simply to the column, and I can forget about rows entirely for the analysis. Then

L(0)<=L(1)<=...<=L(Q-2)<=L(Q-1)

In particular, L(0)=1 and L(Q-1)=N. In some way, we need to track the mininum category index for each column 2...N.

Merlyn pointed out the above, in his comment about binary representation.

Untested pseudo-code follows:

```my \$ColumnCount = 4; # or whatever we need it to be
my \$CategoryCount = 6; # or whatever we need it to be

my %Weight = ();
# TODO: initialize %Weight hash with values from 0 to Q-1
my %WeightCache = (); # to be filled with weights
# TODO: initialize weight cache to handle references to
# hashes with indexes 1..Q-1

# brute-force would iterate across combinations of 1...Q-1;
# for 6 categories and 4 columns, this is 5 choose 3 i.e. 10

sub WeightSpan
{
my (\$LowBound,\$HighBound) = @_;
my \$WeightSum = 0;
\$WeightSum += \$Weight{\$LowBound++}
while \$LowBound<\$HighBound;
return \$WeightSum;
}

sub IncrementCombination
{
my (\$LowBound,\$HighBound,@Combination) = @_;
my \$Idx = 0;
while(\$Combination[\$Idx-1]=\$HighBound-\$Idx)
{
return () if 1==\$Idx+scalar @Combination;
\$Idx--;
};
\$Combination[\$Idx-1]++;
\$Combination[++\$Idx -1]++ while \$Idx;
return @Combination;
}

sub MaximumHeight
{
my (\$LowBound,\$HighBound,@Combination) = @_;
my @IndexSpan = ();
# TODO: auto-init @IndexSpan: 0...scalar @Combination-1
return max(map
{\$WeightCache{\$Combination[\$_]}{\$Combination[\$_+1]}
||= &WeightSpan(\$Combination[\$_],\$Combination[\$_+1])}
@IndexSpan);
}

sub CrunchBestCombination
{
my (\$LowBound,\$HighBound,\$N) = @_;
my @Combination = ();
# TODO: auto-init: fill @Combination with 1...\$N-1
my @BestCombination = @LowestBounds;
my \$BestHeight =  &MaximumHeight(\$LowBound, \$HighBound,
@Combination);
&IncrementCombination(\$LowBound, \$HighBound,
@Combination);

while(@Combination)
{
my \$CurrentMaxHeight =
&MaximumHeight(\$LowBound,\$HighBound,@Combination);
if (\$CurrentMaxHeight<\$BestHeight)
{
\$BestHeight = \$CurrentMaxHeight;
@BestCombination = @Combination;
}
@Combination =  &IncrementCombination(\$LowBound,
\$HighBound, @Combination);
}
return (\$BestHeight,@BestCombination);
}

my @TargetCombination = &CrunchBestCombination(1,
\$ColumnCount-1, \$CategoryCount);
my \$BestHeight = shift(@TargetCombination);

# TODO: translate @TargetCombination into </td><td>
# cell breaks

Obviously, all TODO comments should be implemented before the code has any chance of working. Also, a number of the example functions can be made more succinct.

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

Title:
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.
• 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: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (9)
As of 2017-06-28 09:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (631 votes). Check out past polls.