#!/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;
}

##</code><code>##

JOHN: HMLOKGJIN INMPLHKJO
MARTY: RATOMKFYH
SMACK: MASQKECUI
SUZY: SXWZVRUTY