Perl Monk, Perl Meditation PerlMonks

### Re^2: Wordfeud racks

by choroba (Chancellor)
 on Jul 30, 2013 at 13:08 UTC ( #1047015=note: print w/replies, xml ) Need Help??

in reply to Re: Wordfeud racks
in thread Wordfeud racks

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.
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Replies are listed 'Best First'.
Re^3: Wordfeud racks
by Anonymous Monk on Jul 30, 2013 at 14:06 UTC
performance tip, you could pre-size the hash, so there isn't need to grow it
Re^3: Wordfeud racks
by choroba (Chancellor) on Aug 01, 2013 at 14:00 UTC
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.

لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
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.
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Create A New User
Node Status?
node history
Node Type: note [id://1047015]
help
Chatterbox?
 Eily used google. The lazy internet equivalent of grep [karlgoethebier]: He! [Eily]: Discipulus pretty much all oneliners are killing. Do you imagine how many people could be working if you asked them to do the same thing in C each time ? :P Eily is Listening to "Leave out all the rest" by Linkin Park

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (10)
As of 2017-07-21 09:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (320 votes). Check out past polls.