perlquestion
sflitman
Greetings and felicitations! I have been cracking my head on [http://www.newscientist.com/article/mg20127001.000-enigma-number-1537.html|this problem from New Scientist] all day. Here is my code.
<c>
#!/usr/bin/perl
# SSF 040409 - New Scientist Enigma 1537 - 21 March 2009
# borrows heavily from Juerd's Math::MagicSquare::Generator
use strict;
my @names=qw(JOHN MARTY PAUL SHEILA SMACK SUZY ELSA);
my ($text,%squares);
generate_magic_squares(\%squares);
print "Magic squares:\n";
map { print "$_\n" } sort keys %squares;
print "Names in squares:\n";
map { print "$_: $text\n" if match_squares(\%squares,\$text,$_) } @names;
exit;
sub generate_magic_squares { # generate 3x3 squares
my ($lst)=@_;
my ($square,$start,$step);
for $step (1..10) {
for $start (1..26) {
$square=generate_magic_square($start,$step);
print as_string($square);
if (check($square)) {
print "---PASS\n";
$lst->{ as_letters($square) }++;
} else {
print "---FAIL\n";
}
}
}
}
sub as_letters {
my ($self)=@_;
return join('',map { join('',map { chr(64+$_) } @$_) } @$self);
}
sub as_string {
my ($self) = @_;
return map { join(' ', map { chr($_+64) } @$_) . "\n" } @$self;
}
sub _sum {
my $sum = 0;
$sum += $_ for @_;
return $sum
}
sub check {
my ($self) = @_;
my $sum = _sum( @{ $self->[0] } );
# Horizontals
for (@$self[1..$#$self]) {
return undef if @$_ > @$self; # undef if not square
return undef if _sum(@$_) != $sum;
}
# Verticals
for my $x (0..$#$self) {
return undef if _sum(map $self->[$_][$x], 0..$#$self) != $sum;
}
# Diagonals
return undef if _sum(map $self->[$_][$_], 0..$#$self) != $sum;
return undef if _sum(map $self->[$#$self - $_][$_], 0..$#$self) != $sum;
# Duplicates
my %seen;
$seen{$_}++ for map @$_, @$self;
return undef if _sum(values %seen) != keys %seen;
# Passed all tests!
return $sum;
}
sub generate_magic_square { # 3x3, taken from Math::MagicSquare::Generator
my ($start,$step)=@_;
my $self = [
map {
[ (undef) x 3 ]
} 1..3
];
my $value = $start;
my $halv = int(@$self / 2);
for my $start_x (-$halv..$halv) {
my $x = $start_x - 1;
my $y = $x + @$self + 1;
for (1 .. @$self) {
$x = $x - @$self if ++$x > $#$self;
$y = $y - @$self if --$y > $#$self;
$self->[$y][$x] = $value;
$value += $step;
if ($value>26) { $value-=26; }
}
}
$self;
}
sub match_squares { # are there keys which contain letters of names
my ($lst,$text,$name)=@_;
my @lst=keys %$lst;
for my $letter (split(//,$name)) {
@lst=grep { index($_,$letter)>-1 } @lst;
}
$$text=join(' ',@lst);
@lst ? 1 : 0;
}
</c>
I only get the following output:
<c>
JOHN: HMLOKGJIN INMPLHKJO
MARTY: RATOMKFYH
SMACK: MASQKECUI
SUZY: SXWZVRUTY
</c>
So I know the solution is PAUL, SHEILA, or ELSA. What am I missing? I think it could be that Juerd's algorithm (which actually dates back to the 17th century and probably long before, called the
[http://en.wikipedia.org/wiki/Magic_square#A_method_for_constructing_a_magic_square_of_odd_order|Siamese method]) does not generate all possible 3 x 3 magic squares with the numbers 1..26, but I'm not sure how to code other methods.
<p>
Any comments appreciated!
<p>
SSF