### Re: Puzzle: need a more general algorithm

 on Jul 09, 2002 at 09:55 UTC ( #180438=note: print w/replies, xml ) Need Help??

in reply to Puzzle: need a more general algorithm

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.

Create A New User
Node Status?
node history
Node Type: note [id://180438]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (14)
As of 2018-03-19 11:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (239 votes). Check out past polls.

Notices?