| 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
| |||||||||||
| 95 | 1 | ▶ | not @others or die "board has rows of different lengths"; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 96 | |||||||||||
| 97 | # check if callback is a coderef | ||||||||||
| 98 | 1 | ▶ | ref $print_solution eq 'CODE' or die "improper callback for solutions"; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 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
| |||||||||||
| 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
| |||||||||||
| 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
| |||||||||||
| 169 | |||||||||||
| 170 | # anything up to next free cell goes to "placed" | ||||||||||
| 171 | 17374 | ▶ | $board =~ s/^([^x]+)// and $placed .= $1; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 172 | |||||||||||
| 173 | 17374 | ▶ | if (!$board) { # no more free cells, so this is a solution | ||||||||
|
Branch: 1 branch
| |||||||||||
| 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
| |||||||||||
| 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
| |||||||||||
| 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__ | ||||||||||