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

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

Nice challenge. I went for a particular brute force approach that requires 64bit perl with threads.
Runs for ~140 mins on my quad-core. Top results:

aeinprst: 346 aeilprst: 344 adeiprst: 332 aeimprst: 328

Filtering 2of12inf.txt gives 40933 words, 35893 of which incongruent.
Exhaustive search must cover 13884156 letter combinations, like e.g.:

use Algorithm::Combinatorics qw(:all); my $iter = combinations_with_repetition(\@{['a'..'z']}, 8);

Anyway, this is what I wrote:

#! /usr/bin/perl use threads; use threads::shared; use Thread::Semaphore; use integer; my $CORES = 8; my $TOTAL :shared = 0; my $TDONE :shared = 0; my $tresh = 0; my (%P, %N, @W, @N, %RES); sub wfilt { tr/a-z//cd; length() <= 8; } sub wval { my $x = 1; $x *= $P{$_} for split //; $x } @P{'a'..'z'} = grep {(1x$_)!~/^(11+)\1+$/} 2..101; open(WORDS, "words") or die; @W = grep wfilt, <WORDS>; $N{&wval}++ for @W; @N = keys %N; my $SEM = Thread::Semaphore->new($CORES); my @T = map threads->new(\&worker, $_), 'a'..'z'; report ((map {$_->join()} @T), 0); sub x2 { map { my $t = $_; map {$t.$_} @_ } @_ } sub worker { my ($pivot) = @_; # aaaPzzzz my (%A, %Z, @A, @Z, $a, $z); $A{&wval} //= $_ for grep s/.$/$pivot/, x2(x2('a'..$pivot)); $Z{&wval} //= $_ for x2(x2($pivot..'z')); @A = keys %A; @Z = keys %Z; report (-int(@A)*int(@Z)); for $a (@A) { $SEM->down(); my @R; for $z (@Z) { my ($v, $n) = ($a*$z, 0); $v % $_ or $n += $N{$_} for @N; # 99.99% push @R, ($A{$a}.$Z{$z} => $n) if ($n > $tresh); } report (@R, int(@Z)); $SEM->up(); } return (%RES); } sub report { if ((my $n = pop) < 0) { lock($TOTAL); $TOTAL -= $n; } else { lock($TDONE); $TDONE += $n; } return unless @_; %RES = (%RES, @_); my @top = sort { $RES{$b} <=> $RES{$a} } keys %RES; delete @RES{splice(@top, 20)} if @top > 20; print "$_: $RES{$_}\n" for @top; $tresh = $RES{pop @top}; no integer; printf "! progress %d/%d (% 3.1f%%)\n@{['-'x40]}\n", $TDONE, $TOTAL, 100.0*$TDONE/$TOTAL; }


In reply to Re: Challenge: 8 Letters, Most Words by oiskuu
in thread Challenge: 8 Letters, Most Words by Limbic~Region

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: (8)
    As of 2014-07-25 01:58 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My favorite superfluous repetitious redundant duplicative phrase is:









      Results (167 votes), past polls