Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: Puzzle: need a more general algorithm

by zaimoni (Beadle)
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.


Comment on Re: Puzzle: need a more general algorithm
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://180438]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (8)
As of 2015-07-04 18:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (60 votes), past polls