Re^2: Wordfeud racks

[choroba]

Interestingly, it does not run much faster than a simple algorithm I wrote from scratch. For the rack size of 5, both run around 5m30sec on my box.

Update: The code is buggy. See Re^3: Wordfeud racks for a fix.

#!/usr/bin/perl
use warnings;
use strict;
use 5.010; # defined-or, say

my @tiles = (('_') x 2,  # 2 blank tiles (scoring 0 points)
             # 1 point
             ('E') x 12,
             qw(A I) x 9,
             ('O') x 8,
             qw(N R T) x 6,
             qw(L S U) x 4,
             # 2 points
             ('D') x 4,
             ('G') x 3,
             # 3 points
             qw(B C M P) x 2,
             # 4 points
             qw(F H V W Y) x 2,
             # 5 points
             ('K'),
             # 8 points
             qw(J X),
             # 10 points
             qw(Q Z));

my $rack_size = 5;

my %hash;
my @rack = 0 .. $rack_size - 1;
while ($rack[-1] != @tiles) {
    my $string = join q(), map $tiles[$_], @rack;
    $hash{$string}++;
    my $first_to_move = 0;
    $first_to_move++ while $rack[$first_to_move] + 1 == ($rack[$first_
+to_move + 1] // -1);
    $rack[$first_to_move]++;
    for my $i (0 .. $first_to_move - 1) {
        $rack[$i] = $i;
    }
}

my $combinations = keys %hash;

my $sum = 0;
$sum += $_ for values %hash;

print map "$_ => " . ($hash{$_} / $sum) . "\n", sort { $hash{$a} <=> $
+hash{$b} } keys %hash;
print "Combinations: $combinations, Count: $sum.\n";

With the module, the important part of the code simplifies to:

use Algorithm::Combinatorics qw(combinations);
my %hash;
my $iterator = combinations(\@tiles, $rack_size);
while (my $rack = $iterator->next) {
    $hash{ join q(), @$rack }++;
}

Update: I did some benchmarks. It seems the module would get faster than my code on racks greater than 5, but it will still run for days.

1 =================
         Rate module simple
module 2953/s     --   -24%
simple 3883/s    31%     --
2 =================
         Rate module simple
module 59.1/s     --   -13%
simple 67.9/s    15%     --
3 =================
         Rate module simple
module 1.65/s     --    -9%
simple 1.81/s    10%     --
4 =================
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
       s/iter module simple
module   15.5     --    -2%
simple   15.2     2%     --
5 =================
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
       s/iter module simple
module    328     --    -0%
simple    327     0%     --

Update 2: Fixed a bug in the code.

[Anonymous Monk]

performance tip, you could pre-size the hash, so there isn't need to grow it

[choroba]

I ran the code for rack size 7. It took 12 hours 6 mins 18 secs on a 4 core Xeon box with 8 GB memory, OS linux. I am not going to copy the whole output here, just a few first and last lines:

MMVFWXQ => 6.24704795748769e-11
__BPMKQ => 6.24704795748769e-11
BCBMYHV => 6.24704795748769e-11

...

EEAIOND => 3.56231662727778e-05
EEAIONU => 3.56231662727778e-05
EEAIONL => 3.56231662727778e-05
Combinations: 8275164, Count: 16007560800.

I probably have an error in the code :-)

Update: I see it now. The error was my effort to "DRY". The @tiles array must be defined as follows to make it work:

my @tiles = (('_') x 2,  # 2 blank tiles (scoring 0 points)
             # 1 point
             ('E') x 12,
             ('A') x 9, ('I') x 9,
             ('O') x 8,
             ('N') x 6, ('R') x 6, ('T') x 6,
             ('L') x 4, ('S') x 4, ('U') x 4,
             # 2 points
             ('D') x 4,
             ('G') x 3,
             # 3 points
             ('B') x 2, ('C') x 2, ('M') x 2, ('P') x 2,
             # 4 points
             ('F') x 2, ('H') x 2, ('V') x 2, ('W') x 2, ('Y') x 2,
             # 5 points
             ('K'),
             # 8 points
             qw(J X),
             # 10 points
             qw(Q Z));

Stay tuned, the next result is comming in 12 hours.

[choroba]

And here it is. 13 hours 16 mins 44 secs, 8 core Quad-Core AMD Opteron(tm) Processor 2387.

CCWWYYZ => 6.24704795748769e-11
HHYYJQZ => 6.24704795748769e-11
GGGWWKZ => 6.24704795748769e-11
...
EEAIONT => 9.61825489365001e-05
EEAIONR => 9.61825489365001e-05
EAIONRT => 0.000104926417021636
Combinations: 3199724, Count: 16007560800.