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

Re^2: Wordfeud racks

by choroba (Canon)
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.
لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ


Comment on Re^2: Wordfeud racks
Select or Download Code
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 (Canon) 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.
      لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2015-07-03 18:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (55 votes), past polls