Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Couldn't think how to do this yesterday, but it came to me this morning. Generate a regex for the whole thing at once, with the insurance that there be no two-in-a-row. The code actually gets simpler and faster, but on some very long random layouts, it does get hung up (meaning it's doing a lot of backtracking and probably not going to find a solution).

Update: The reason it's prone not to find a solution is that the no-two-in-a-row check is more strict than it needs to be. It will not allow 'pl' to be used if the next two chars are 'pl', even if you have a 'pll' layout available. The fix for this is to use an assertion ((??{ })) to generate each match as "any available pattern except the previous match". The 2nd code block below implements that.

my $desired_page_count = 10; # Structure holding all the different page layouts. ('l' = Landscape, +'p' = Portrait) my $pages = { ll => '01', pp => '02', lp => '03', pl => '04', lpp => '05', pll => '06', plp => '07', lpl => '08', lll => '09', ppp => '10', ppl => '11', llp => '12', ppll => '13', llpp => '14', }; my $photos = "llppllpplpppllplpplpplpllplpll"; # Make a really long layout -- at much over 100, it tends to hang up $photos .= substr 'lp', rand 2 for 1..100; $desired_page_count = int( length($photos)/ 2.7 ); my $page_regex = join '|', keys %$pages; my $regex = "($page_regex)"; $regex .= "(?!\\$_)($page_regex)" for 1..($desired_page_count - 1); print "\$regex is $regex\n"; if (my @pages = $photos =~ /^$regex$/) { # Added the anchors as per S +mugX's reply print "$pages->{$_}\n" for @pages; } else { print "Could not come up with no-repeat layout in $desired_page_cou +nt pages\n"; }
use warnings; use strict; my $desired_page_count = 10; # Structure holding all the different page layouts. ('l' = Landscape, +'p' = Portrait) my $pages = { ll => '01', pp => '02', lp => '03', pl => '04', lpp => '05', pll => '06', plp => '07', lpl => '08', lll => '09', ppp => '10', ppl => '11', llp => '12', ppll => '13', llpp => '14', }; # Construct a hash of regexen: each value is all the patterns except f +or the # key. This way, they don't need to be constructed repeatedly during t +he matching my @patterns = keys %$pages; my %all_except = map {my $k=$_; ($k => join '|', grep {$_ ne $k} @patt +erns)} @patterns; my $photos = "llppllpplpppllplpplpplpllplpll"; # Make a really long layout $photos .= substr 'lp', rand 2 for 1..100; $desired_page_count = int( length($photos)/ 2.7 ); my $page_regex = join '|', @patterns; my $regex = "($page_regex)"; $regex .= "((??{\$all_except{\$$_}}))" for 1..($desired_page_count - 1 +); print "\$regex is $regex\n"; use re 'eval'; if (my @pages = $photos =~ /$regex/) { print "$pages->{$_}\n" for @pages; } else { print "Could not come up with no-repeat layout in $desired_page_cou +nt pages\n"; }

Caution: Contents may have been coded under pressure.

In reply to Re^3: Algorithm to fit photos into spaces on pages by Roy Johnson
in thread Algorithm to fit photos into spaces on pages by SmugX

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!
  • 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
  • Outside of code tags, you may need to use entities for some characters:
            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?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chilling in the Monastery: (4)
    As of 2014-11-23 13:52 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My preferred Perl binaries come from:














      Results (132 votes), past polls