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

Re: Puzzle: need a more general algorithm

by Abigail-II (Bishop)
on Jul 09, 2002 at 16:25 UTC ( #180533=note: print w/ replies, xml ) Need Help??

in reply to Puzzle: need a more general algorithm

The problem smells badly to being an NP-complete problem. And those are believed that they cannot be done efficiently. Hence, we might as well backtrack. And which mechanism in Perl is good at backtracking? Right, regular expressions.

Therefore, I present a solution that will use a regular expression to do the hard work. It will report the minimum height that is needed. Calculating the actual partition is left as an exercise for the reader.


#!/usr/bin/perl use strict; use warnings 'all'; sub partition ($$); my $columns = 4; my @sizes = qw /10 15 25 30 10 13/; sub partition ($$) { my ($b, $h) = @_; return [(0) x $h] unless $b; return [$b] if $h < 2; map {my $__ = $_; map {[$__ => @$_]} partition $b - $__, $h - 1} 0 + .. $b; } my @r = partition @sizes, $columns; my @regex; foreach my $r (@r) { my $c = 0; push @regex => join ":" => map { $c += my $__ = $_; join ("" => map {"-" x $_} @sizes [$c - $__ .. $c - 1]) . "-*" +} @$r; } my $regex = join "|" => map {"(?:$_)"} @regex; my $try = 1; { exit !print "Minimum required height: $try\n" if join (":" => map {"-" x $try} 1 .. $columns) =~ /$regex/; $try ++; redo; }

Comment on Re: Puzzle: need a more general algorithm
Download Code
Replies are listed 'Best First'.
Re(2): Puzzle: need a more general algorithm
by FoxtrotUniform (Prior) on Jul 09, 2002 at 16:39 UTC


    Once you have the minimum height, calculating the actual partition is equivalent to the text justification problem, with each category being a word, its length being the word's length, and the minimum height being the line length. This has been done before.

    The hell with paco, vote for Erudil!

      Actually, once you know the height that will work, a simple greedy algorithm will do (stuff as much as you can in the first column, then the next, and the next, etc). After all, it was given that any solution would do, not the prettiest or something like that.


Log In?

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

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2015-11-25 19:25 GMT
Find Nodes?
    Voting Booth?

    What would be the most significant thing to happen if a rope (or wire) tied the Earth and the Moon together?

    Results (686 votes), past polls