Skip to content

Instantly share code, notes, and snippets.

@masak
Created August 11, 2011 11:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save masak/1139458 to your computer and use it in GitHub Desktop.
Save masak/1139458 to your computer and use it in GitHub Desktop.
Counting the number of ways a pentomino can be placed on an 8x8 board with a 2x2 hole in the middle
#! /usr/bin/perl
use 5.010;
use strict;
use warnings;
my $SIZE = 8;
my %pieces = (
'F1' => <<"EOP",
.XX
XX.
.X.
EOP
'F2' => <<"EOP",
XX.
.XX
.X.
EOP
'I' => <<"EOP",
X
X
X
X
X
EOP
'L1' => <<"EOP",
X.
X.
X.
XX
EOP
'L2' => <<"EOP",
.X
.X
.X
XX
EOP
'P1' => <<"EOP",
XX
XX
X.
EOP
'P2' => <<"EOP",
XX
XX
.X
EOP
'N1' => <<"EOP",
X..
XXX
..X
EOP
'N2' => <<"EOP",
..X
XXX
X..
EOP
'T' => <<"EOP",
XXX
.X.
.X.
EOP
'U' => <<"EOP",
X.X
XXX
EOP
'V' => <<"EOP",
X..
X..
XXX
EOP
'W' => <<"EOP",
X..
XX.
.XX
EOP
'X' => <<"EOP",
.X.
XXX
.X.
EOP
'Y1' => <<"EOP",
.X
XX
.X
.X
EOP
'Y2' => <<"EOP",
X.
XX
X.
X.
EOP
'Z1' => <<"EOP",
..XX
XXX.
EOP
'Z2' => <<"EOP",
XX..
.XXX
EOP
);
sub fits {
my ($piece, $sr, $sc) = @_;
my @rows = split /\n/, $piece;
my $width = length($rows[0]);
return if $sr + @rows - 1 > $SIZE - 1;
return if $sc + $width - 1 > $SIZE - 1;
for my $r (0..@rows-1) {
my $row = $rows[$r];
for my $c (0..$width-1) {
if (substr($row, $c, 1) eq "X") {
return if (3 == $sr + $r || 4 == $sr + $r)
&& (3 == $sc + $c || 4 == $sc + $c);
}
}
}
return 1;
}
sub rotate {
my ($piece, $rotations) = @_;
for (1..$rotations) {
my @rows = split /\n/, $piece;
my $width = length($rows[0]);
my @new_piece;
for my $c (reverse 0..$width-1) {
push @new_piece, join "", map { substr($_, $c, 1) } @rows;
}
$piece = join "\n", @new_piece;
}
return $piece;
}
my $rows;
for my $name (keys %pieces) {
my $piece = $pieces{$name};
chomp $piece;
my $rotations = 4;
$rotations = 2 if $name eq "I" || $name eq "N1" || $name eq "N2";
$rotations = 1 if $name eq "X";
for my $a (0..$rotations-1) {
my $rotated_piece = rotate($piece, $a);
for my $r (0..$SIZE-1) {
for my $c (0..$SIZE-1) {
if (fits($rotated_piece, $r, $c)) {
$rows++;
}
}
}
}
}
say $rows;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment