blib/lib/Games/Pentominos.pm

filter: Statementstmt 98.5% 68 / 69 Branchbran 70.0% 14 / 20 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 7 / 7 Podpod 100% 1 / 1 totaltotal 92.7% 90 / 97 CC 14 SCAR 16.4
CC
14
Cov
92%
_place_pentomino
8.1
solve
5.2
_compile_substitutions
3.0
CRAP 5.2
↑ Summary
1 #======================================================================
2 package Games::Pentominos; # see doc at end of file
3 #======================================================================
4 2 our $VERSION = "1.0";
5 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
6 2 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
7 2 ▶use Time::HiRes qw/time/;
Subroutine BEGIN: called CC=1 SCAR=0.0
8 2 ▶use List::MoreUtils qw/uniq/;
Subroutine BEGIN: called CC=1 SCAR=0.0
9  
10 # work mostly with global vars because this is fastest than parameter-passing
11 our # because accessed from eval
12 2 $board; # cells remaining to be filled
13 2 my $placed; # cells filled so far
14 my $print_solution; # callback for printing a solution
15 2 my ($t_ini, $t_tot); # times in milliseconds
16 2 my $n_solutions; # how many solutions found
17 2 my %substitutions; # a coderef for each pentomino/permutation
18  
19 # description of the 12 pentominos. Each of them has a labelling letter,
20 # a number of permutations, and for each permutation a rectangle describing
21 # the pentomino shape. Occupied cells are shown with an 'x', untouched cells
22 # with a '.' (this character explicitly chosen so that in regexes it will
23 # match anything except a newline character).
24  
25 2 my %pentominos = (
26 F => [8, qw/.xx xx. x.. ..x .x. .x. .x. .x.
27 xx. .xx xxx xxx xxx xxx xx. .xx
28 .x. .x. .x. .x. x.. ..x .xx xx./],
29  
30 I => [2, qw/xxxxx x
31 ..... x
32 ..... x
33 ..... x
34 ..... x/],
35  
36 L => [4, qw/xxxx xxxx x. .x
37 x... ...x x. .x
38 .... .... x. .x
39 .... .... xx xx/],
40  
41 P => [8, qw/xx xx xxx xxx x. .x xx. .xx
42 xx xx xx. .xx xx xx xxx xxx
43 x. .x ... ... xx xx ... .../],
44  
45 S => [8, qw/xx.. ..xx xxx. .xxx x. .x x. .x
46 .xxx xxx. ..xx xx.. xx xx x. .x
47 .... .... .... .... .x x. xx xx
48 .... .... .... .... .x x. .x x./],
49  
50 T => [4, qw/xxx .x. x.. ..x
51 .x. .x. xxx xxx
52 .x. xxx x.. ..x/],
53  
54 U => [4, qw/xxx x.x xx xx
55 x.x xxx x. .x
56 ... ... xx xx/],
57  
58 V => [4, qw/xxx xxx x.. ..x
59 x.. ..x x.. ..x
60 x.. ..x xxx xxx/],
61  
62 W => [4, qw/xx. .xx x.. ..x
63 .xx xx. xx. .xx
64 ..x x.. .xx xx./],
65  
66 X => [1, qw/.x.
67 xxx
68 .x./],
69  
70 Y => [8, qw/.x x. .x x. xxxx xxxx ..x. .x..
71 xx xx .x x. .x.. ..x. xxxx xxxx
72 .x x. xx xx .... .... .... ....
73 .x x. .x x. .... .... .... ..../],
74  
75 Z => [4, qw/xx. .xx x.. ..x
76 .x. .x. xxx xxx
77 .xx xx. ..x x../],
78 );
79  
80  
81  
82 #----------------------------------------------------------------------
83 1 ▶sub solve {
Subroutine solve: called CC=5 SCAR=16.4
Pod documented
84 #----------------------------------------------------------------------
85 1 my ($self, $submitted_board, $submitted_callback) = @_;
86  
87 # initialize globals
88 1 ($board, $placed) = ($submitted_board, "");
89 1 $print_solution = $submitted_callback;
90  
91 # check if $board meets requirements
92 1 my $n_cells = ($board =~ tr/x//);
93 1 my ($board_n_cols, @others) = uniq map length, ($board =~ m/.+/g);
94 1 ▶ $n_cells == 60 or die "board does not have 60 empty cells noted as 'x'";
Branch: 1 branch
BranchTrueFalseTotal
$n_cells == 60 or die "board does not have 60 empty cells noted as 'x'" 1 0 1
95 1 ▶ not @others or die "board has rows of different lengths";
Branch: 1 branch
BranchTrueFalseTotal
@others and die "board has rows of different lengths" 0 1 1
96  
97 # check if callback is a coderef
98 1 ▶ ref $print_solution eq 'CODE' or die "improper callback for solutions";
Branch: 1 branch
BranchTrueFalseTotal
ref $print_solution eq "CODE" or die "improper callback for solutions" 1 0 1
99  
100 # compile the substitution subroutines
101 1 _compile_substitutions($board_n_cols);
102  
103 # anything up to first free cell goes to "placed"
104 1 ▶ $board =~ s/^([^x]+)// and $placed .= $1;
Branch: 1 branch
BranchTrueFalseTotal
$Games::Pentominos::board =~ s/^([^x]+)// and $placed .= $1 1 0 1
105  
106 # start computing solutions
107 1 $t_ini = time;
108 1 $t_tot = 0;
109 1 $n_solutions = 0;
110 1 _place_pentomino(keys %pentominos);
111 }
112  
113  
114  
115 #----------------------------------------------------------------------
116 1 ▶sub _compile_substitutions {
Subroutine _compile_substitutions: called CC=3 SCAR=11.0
117 #----------------------------------------------------------------------
118 1 my ($board_n_cols) = @_; # how many columns in each row
119  
120 1 %substitutions = ();
121 1 ▶ while (my ($letter, $array_ref) = each %pentominos) {
Branch: 1 branch
BranchTrueFalseTotal
if (() = each %pentominos) 12 1 13
122  
123 12 my $n_permutations = $array_ref->[0]; # how many possible layouts
124 12 my $n_rows = (@$array_ref-1) / $n_permutations;
125  
126 12 for my $perm_id (0 .. $n_permutations-1) {
127  
128 # gather data rows for that permutation
129 59 my @rows = map {$array_ref->[$_ * $n_permutations + $perm_id + 1]}
130 (0..$n_rows-1);
131 59 my $n_cols = length ($rows[0]);
132  
133 # construct regex to match that permutation
134 # NOTE: \D below is just a convenience for char class [FILPSTUVWXYZx.\n]
135 59 my $skip_to_next_row = sprintf "\\D{%d}", $board_n_cols + 1 - $n_cols;
136 59 my $regex = join $skip_to_next_row, @rows;
137  
138 # remove everything before or after the touched cells
139 59 $regex =~ s/^[^x]+//;
140 59 $regex =~ s/[^x]+$//;
141  
142 # add capture brackets in regex
143 59 $regex =~ s/([^x]+)/($1)/g;
144  
145 # substitution string : replace 'x' by letter
146 # and brackets by captured groups
147 59 (my $subst = $regex) =~ s/x/$letter/g;
148 59 my $num_paren = 1;
149 59 $subst =~ s/\(.*?\)/'$'.$num_paren++/eg;
150  
151 # compile a sub performing the substitution
152 59 push @{$substitutions{$letter}},
153 eval qq{sub {\$board =~ s/^$regex/$subst/}};
154 }
155 }
156 }
157  
158  
159 #----------------------------------------------------------------------
160 17374 ▶sub _place_pentomino { # the recursive algorithm
Subroutine _place_pentomino: called CC=8 SCAR=20.9
161 #----------------------------------------------------------------------
162 # my @letters = @_; # commented out for speed (avoiding copy)
163  
164 17374 my ($board_ini, $placed_ini) = ($board, $placed);
165  
166 17374 foreach my $letter (@_) {
167 52912 foreach my $substitution (@{$substitutions{$letter}}) {
168 195821 ▶ if ($substitution->()) { # try to apply this pentomino to $board
Branch: 1 branch
BranchTrueFalseTotal
if (&$substitution()) 17374 178447 195821
169  
170 # anything up to next free cell goes to "placed"
171 17374 ▶ $board =~ s/^([^x]+)// and $placed .= $1;
Branch: 1 branch
BranchTrueFalseTotal
$Games::Pentominos::board =~ s/^([^x]+)// and $placed .= $1 17374 0 17374
172  
173 17374 ▶ if (!$board) { # no more free cells, so this is a solution
Branch: 1 branch
BranchTrueFalseTotal
if (not $Games::Pentominos::board) { } 1 17373 17374
174 1 my $t_solution = time - $t_ini;
175 1 $t_tot += $t_solution;
176 1 $n_solutions += 1;
177 1 ▶ $print_solution->($placed, $n_solutions, $t_solution, $t_tot)
Branch: 1 branch
BranchTrueFalseTotal
&$print_solution($placed, $n_solutions, $t_solution, $t_tot) or return 0 1 1
178 or return; # stop searching if callback did not return true
179 0 $t_ini = time;
180 }
181 else {
182 17373 ▶ _place_pentomino(grep {$_ ne $letter} @_)
Branch: 1 branch
BranchTrueFalseTotal
_place_pentomino(grep({$_ ne $letter;} @_)) or return 17362 11 17373
183 or return;
184 }
185  
186 # restore to previous state (remove pentomino from board)
187 17362 ($board, $placed) = ($board_ini, $placed_ini);
188 }
189 }
190 }
191 17362 return 1; # continue searching
192 }
193  
194  
195 __END__
↑ Summary