#! /usr/bin/perl -wl
use strict;
use warnings;

my @names = qw(JOHN MARTY PAUL SHEILA SMACK SUZY ELSA);

for my $name (@names) {
  my @d = map {ord($_) - ord("A") + 1} split //, $name;
  my @solution = find_square(@d);
  if (@solution) {
    printf "%s:\n  %2d %2d %2d\n  %2d %2d %2d\n  %2d %2d %2d\n",
      $name, @solution;
    printf "\n  %s  %s  %s\n  %s  %s  %s\n  %s  %s  %s\n\n",
      map chr($_+ord("A")-1), @solution;
  }
  else {
    print "$name: no solution\n";
  }
}

# All solutions look like:
#
#    x+y    x-z  x-y+z
#   x-2y+z   x  x+2y-z
#   x+y-z   x+z  x-y
#
# Up to rotation and reflection we may insist that:
#
#   0 < z < y
#   z != y-z
#
# If 2z < y they are, in order:
#
#   x-2y+z, x-y, x-y+z, x-z, x, x+z, x+y-z, x+y, x+2y-z
#
# Otherwise if y < 2z they are:
#
#   x-2y+z, x-y, x-z, x-y+z, x, x+y-z, x+z x+y, x+2y-z
#
# This falls in the range 1..26 if 0 < x-2y+z and x+2y-z < 27.
#
# So 4y-2z < 25 with z < y means y < 13.
sub find_square {
  my @d = sort {$a <=> $b} @_;

  my $min_range = $d[-1] - $d[0];

  # As shown above, y < 13, but the lower limit is more complicated.
  # So work down from there.
  my $y = 13;
Y: while (1) {
    $y--;
    last Y if 4*$y-2 < $min_range;

    # y < z is trivial, but the lower limit is complicated.
    # Again we were down from the top.
    my $z = $y;
Z:  while (1) {
      $z--;
      next Y if 4*$y-2*$z > 25;
      next Y if $z < 1;

      my @in_order;
      if ($z+$z > $y) {
        @in_order = (
          -2*$y + $z,
          -$y,
          -$z,
          -$y + $z,
          0,
          $y - $z,
          $z,
          $y,
          2*$y - $z,
        );
      }
      elsif ($z+$z < $y) {
        @in_order = (
          -2*$y + $z,
          -$y,
          -$y + $z,
          -$z,
          0,
          $z,
          $y - $z,
          $y,
          2*$y - $z,
        );
      }
      else {
        next;
      }

      # Sanity check for our logic.  Can be removed.
      for (1..$#in_order) {
        if ($in_order[$_-1] >= $in_order[$_]) {
          print "y: $y, z:$z\n";
          die "Out of order: @in_order";
        }
      }

      # i is the index $d[0] matches at, which tells us $x.
I:    for my $i (0..$#in_order) {
        my $x = $d[0] - $in_order[$i];

        # Sanity check our number range.
        # If we're out of range and increasing $i will not help,
        # then move to a different ($x, $z), otherwise only
        # increment $i.
        next Z if $x + $in_order[0] < 1;
        next I if $x + $in_order[-1] > 26;
        next Z if $x + $in_order[-1] < $d[-1];

        # We match the lowest number, can we find the rest?
        # We search with "zipping" logic.
        my $p_d = my $p_o = 1;
        while ($p_d < @d) {
          if ($x + $in_order[$p_o] < $d[$p_d]) {
            # Perhaps the next number will match our digit?
            $p_o++;
          }
          elsif ($x + $in_order[$p_o] > $d[$p_d]) {
            # $d[$p_d] is not anywhere in our square.
            next I;
          }
          else {
            # One more digit matched.
            $p_o++;
            $p_d++;
          }
        }

        # If we got here we have a solution!  Return it in the
        # right order for a square.
        return (
          $x + $y,
          $x - $z,
          $x - $y + $z,
          $x - 2*$y + $z,
          $x,
          $x + 2*$y - $z,
          $x + $y - $z,
          $x + $z,
          $x - $y,
        );
      }
    }
  }

  return;
}

##</code><code>##

x11 x12 x13
x21 x22 x23
x31 x32 x33

##</code><code>##

S = 4*S - 3*S
  = (x21 + x22 + x23)
   +(x11 + x22 + x33)
   +(x12 + x22 + x32)
   +(x13 + x22 + x31)
   -(x11 + x12 + x13)
   -(x21 + x22 + x23)
   -(x31 + x32 + x33)
  = 3*x22

##</code><code>##

From choice of x, y, and z we have:
  x11 = x + y
  x12 = x - z
  x22 = x

We already showed that the sum of every column, row and diagonal is 3x

Finish the top row:
  3x = S
     = x11 + x12 + x13
     = (x + y) + (x - z) + x13
     = 2x + y - z + x13
  So
    x13 = x - y + z

Now let's do the bottom row:
  3x = S
     = x13 + x22 + x31
     = (x - y + z) + (x) + x31
  So
    x31 = x + y - z

  3x = S
     = x12 + x22 + x32
     = (x - z) + (x) + x32
     = 2x - z + x32
  So
    x32 = x + z

  3x = S
     = x11 + x22 + x33
     = (x + y) + (x) + x33
     =  2x + y
  So
    x33 = x - y

Now do the 2 sides

  3x = S
     = x11 + x21 + x31
     = (x + y) + x21 + (x + y - z)
     = 2x + 2y - z + x21
  So
     x21 = x - 2y + z

  3x = S
     = x13 + x23 + x33
     = (x - y + z) + x23 + (x - y)
     = 2x - 2y + z + x23
  So
    x23 = x + 2y - z

##</code><code>##

  x11 + x12 + x13
    = (x + y) + (x - z) + (x - y + z)
    = 3x

  x21 + x22 + x23
    = (x - 2y + z) + (x) + (x + 2y - z)
    = 3x

  x31 + x32 + x33
    = (x + y - z) + (x + z) + (x - y)
    = 3x

  x11 + x21 + x31
    = (x + y) + (x - 2y + z) + (x + y - z)
    = 3x

  x12 + x22 + x32
    = (x - z) + (x) + (x - z)
    = 3x

  x13 + x23 + x33
   = (x - y + z) + (x + 2y - z) + (x - y)
   = 3x

  x11 + x22 + x33
   = (x + y) + (x) + (x - y)
   = 3x

  x13 + x22 + x31
   = (x - y + z) + (x) + (x + y - z)
   = 3x