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

Re^2: Wordfeud racks

by choroba (Abbot)
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 (Abbot) 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 studying the Monastery: (10)
As of 2014-12-18 22:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (67 votes), past polls