#!/usr/bin/perl

use strict;

##  0 1 2  <- Board     Compute forceable moves in tic-tac-toe
##  3 4 5  positions    Fred Curtis 2002-09-06
##  6 7 8               http://f2.org/maths/ttt.html

my @transforms;

##  Find closure of transform group
{
  my $sigs = { map((join('', @{$_}) => $_), 
    [ 2, 5, 8, 1, 4, 7, 0, 3, 6 ],  ##  90-deg CCW Rotation
    [ 2, 1, 0, 5, 4, 3, 8, 7, 6 ],  ##  Vertical Refelection
  ) };
  my $checked = { };
  do {
    @transforms = values %{$sigs};
    foreach my $s (@transforms) {
      $sigs->{join('', @{$_})} ||= $_
	foreach (map([@{$s}[@{$_}]], grep {$checked->{$s}{$_}++ == 0} @transforms));
    }
  } while (scalar(@transforms) != scalar(values %{$sigs}));
}

my $canonical_sig = { };
my $canonical_state = { };
my ($win_x, $win_o, $draw, $win_xd, $win_od, $win_xo) = map((1 << $_), 0..5);
my $outcome_bit = { 
  'WinX' => $win_x, 'WinX/Draw' => $win_xd, 'WinX/WinO' => $win_xo,
  'WinO' => $win_o, 'WinO/Draw' => $win_od, 'Draw' => $draw,
};
my $can_force_win_o = { map(($_ => $win_o | $win_od | $win_xo), 'x', 'o') };
my $can_force_win_x = { map(($_ => $win_x | $win_xd | $win_xo), 'x', 'o') };
my $can_force_draw  = { map(($_ => $draw  | $win_od | $win_xd), 'x', 'o') };

sub add_states {
  my($state, $depth) = @_;
  my $sig = join('', @{$state});

  if (!exists($canonical_sig->{$sig})) {
    $canonical_sig->{$_} = $sig   ## Make variant sig point to current sig
      foreach (map(join('', @{$state}[@{$_}]), @transforms));

    my $can_force;
    if ($sig =~ m{xxx......|...xxx...|......xxx|x..x..x..|.x..x..x.|..x..x..x|x...x...x|..x.x.x..}) {
      $can_force = $can_force_win_x;
    } elsif ($sig =~ m{ooo......|...ooo...|......ooo|o..o..o..|.o..o..o.|..o..o..o|o...o...o|..o.o.o..}) {
      $can_force = $can_force_win_o;
    } elsif ($depth == 9) {
      $can_force = $can_force_draw;
    } else {
      my ($player, $other) = ($depth % 2 == 0 ? ('x', 'o') : ('o', 'x'));
      $can_force = { $player => 0, $other => ~0 };
      foreach my $loc (grep {$state->[$_] eq '-'} 0..8) {
        $state->[$loc] = $player;
        my $child_outcome = add_states($state, $depth+1);
        $state->[$loc] = '-';

        $can_force->{$player} |= $child_outcome->{$player};
        $can_force->{$other}  &= $child_outcome->{$other};
      }
    }
    $canonical_state->{$sig} = $can_force;
  }
  return $canonical_state->{$canonical_sig->{$sig}}
}

add_states( [ '-', '-', '-', '-', '-', '-', '-', '-', '-' ], 0);

print "@{[scalar keys %{$canonical_state}]} canonical states\n";
foreach my $sig ('---------' , 'o-o-x-x--', '--oox-x--', 'x-oox-x--', '-oxooxxx-') {
  print sprintf("\n%s %s %s\n%s %s %s\n%s %s %s\n", split(//, $sig));
  my $csig = $canonical_sig->{$sig};
  if (!defined($csig)) {
    print "Not a valid game state\n";
  } else {
    print "Player '@{[scalar(grep { $_ eq '-' } split(//, $sig)) % 2 != 0 ? 'x' : 'o']}' to move\n";
    foreach my $player ('o', 'x') {
      my $can_force = $canonical_state->{$csig}{$player};
      print "   $player can force";
      print " @{[($can_force & $outcome_bit->{$_}) ? $_ : ' ' x length($_)]}"
	foreach (sort { $outcome_bit->{$a} <=> $outcome_bit->{$b} } keys %{$outcome_bit});
      print "\n";
    }
  }
}