#! /usr/local/gnu/bin/perl
 
###############################################################################
################################### SECRET ####################################
###############################################################################
use strict;

my $file1;

if (@ARGV != 1) {
  print("Usage: solve.pl <datafile>\n");
  print(" ie. solve.pl puz.dat\n");
  exit;
}


$file1 = $ARGV[0];

my @rows;
my @cols;
my $numRows;
my $numCols;
my $maxRow;
my $maxCol;

my @board;
my @board2;
my $ptr1;
my $ptr2;

($ptr1, $ptr2, $numRows, $numCols, $maxRow, $maxCol) = GetData($file1);
@rows = @$ptr1;
@cols = @$ptr2;

## init board to all unknown
for(my $i = 1;$i <= $numRows;$i++) {
  for(my $j = 1;$j <= $numCols;$j++) {
    $board[$i][$j] = 0;
  }
}

my $loop = 1;

while ($loop > 0) {
  PrintThisBoard(\@board);

  @board2 = CopyBoard(\@board);

  LayoutRows(\@board2);
  LayoutCols(\@board2);

  $loop = CheckDone(\@board, \@board2, $loop);

  @board = CopyBoard(\@board2);
}
PrintThisBoard(\@board);

###############################################################################
###############################################################################
###############################################################################

sub updateBlankArray {
  my $ptr = $_[0];
  my $num = $_[1];
  my @ba = @$ptr;

  $num = $num-1;

  if ($num > 0) {

    ## Try to shift one to the right
    for(my $slot = 0;$slot <= $num;$slot++) {
      my $to = $slot+1;
      if ($slot != 0) {
        if ($ba[$slot] > 1) {
          print("Take one from bucket $slot and add to $to\n");
          $ba[$to]++;
          $ba[$slot]--;
          $slot = $num+1;
        }
      } else {
        if ($ba[$slot] > 0) {
          print("Take one from end bucket $slot and add to $to\n");
          $ba[$to]++;
          $ba[$slot]--;
          $slot = $num+1;
        }
      }
    }
  }

  return \@ba;
}


###############################################################################
###############################################################################
###############################################################################

sub isColConsistant {
  my $ptr1 = $_[0];
  my $ptr2 = $_[1];
  my $row = $_[2];
  my @c = @$ptr1;
  my @b = @$ptr2;


  for(my $col = 1;$col <= $numCols; $col++) {
    print("    COL CONSIST $row, $col    $b[$row][$col]  $c[$col]\n");
    ## If the board has decided...
    if ($b[$row][$col] > 0) {
      if ($c[$col] != $b[$row][$col]) {
        print("       NOT CONSISTANT\n");
        return 0;
      }
    }
  }

  return 1;
}

###############################################################################
###############################################################################
###############################################################################

sub isRowConsistant {
  my $ptr1 = $_[0];
  my $ptr2 = $_[1];
  my $col = $_[2];
  my @c = @$ptr1;
  my @b = @$ptr2;


  for(my $row = 1;$row <= $numRows; $row++) {
    ## If the board has decided...
    print("    ROW CONSIST $row, $col    $b[$row][$col]  $c[$col]\n");

    if ($b[$row][$col] > 0) {
      if ($c[$row] != $b[$row][$col]) {
        print("       NO CONSISTANT\n");
        return 0;
      }
    }
  }

  return 1;
}

###############################################################################
###############################################################################
###############################################################################

sub RowTryAllCombinations {
  my $row = $_[0];
  my $ptr = $_[1];
  my @orig = @$ptr;

  my $sum = 0;

  ## Do special case.. items fill whole thing
  for(my $i = 1;$i <= $rows[$row][0];$i++) {
#    print("Add up row $sum + $rows[$row][$i]\n");
    $sum = $sum + $rows[$row][$i];
  }

  my $numBlanks = $numCols - $sum;
  my $numBlankPosition = $rows[$row][0] + 1;
  print("Number of Blanks in row $row = $numBlanks\n");
#  print("Sum $sum   Num Blank(+1) $rows[$row][0]\n");

  my @copy = @orig;
  my @blankArray;
  my @changeArray;

  for(my $i = 1;$i <= $numCols;$i++) {
    $changeArray[$i] = -1;
    ## set to 1 for blank
    ## set to 2 for X
    ## reset to zero for inconsistants
  }

  for(my $i = 1;$i < $numBlankPosition-1;$i++) {
    $blankArray[$i] = 1;
  }
  $blankArray[$numBlankPosition-1] = 0;
  $blankArray[0] = $numBlanks - ($rows[$row][0] - 1);

  my $loopCount = 1;
  my $first = 1;
  my $done = 0;
  ##
  while ($done != 1) {

    ## Array is already set up for first time
    if ($first != 1) {
      my $temp;
      $temp = updateBlankArray(\@blankArray, $numBlankPosition);
      @blankArray = @$temp;
    } else {
      $first = 0;
    }
    print("ROW $row BA ");
    for(my $i = 0;$i < $numBlankPosition;$i++) {
      print("$blankArray[$i]");
    }
    print("\n");

    ## lay out data
    my $pos = 1;
    my @col;

    ## Do first blank
    for(my $i = 0;$i < $blankArray[0];$i++) {
      $col[$pos] = 1;
      $pos++;
    }

    ## Loop over X and blanks
    for(my $item = 1;$item <= $rows[$row][0];$item++) {
      ## Do X
      for(my $i = 0;$i < $rows[$row][$item];$i++) {
        $col[$pos] = 2;
        $pos++;
      }
      ## Do blank
      for(my $i = 0;$i < $blankArray[$item];$i++) {
        $col[$pos] = 1;
        $pos++;
      }
    }


    if (isColConsistant(\@col, $ptr, $row)) {

      print("CA ROW $row ");
      for(my $i = 1;$i <= $numCols;$i++) {
        print("$changeArray[$i]");
      }
      print("\n  ROW $row ");
      for(my $i = 1;$i <= $numCols;$i++) {
        print("$col[$i]");
      }
      print("\n");
      for(my $i = 1;$i <= $numCols;$i++) {
        if ($changeArray[$i] == -1) {
          $changeArray[$i] = $col[$i];
        } else {
          ## inconsistant
          if ($changeArray[$i] != $col[$i]) {
            $changeArray[$i] = 0;
          }
        }
      }
      $done = 1;
      for(my $i = 1;$i <= $numCols;$i++) {
        if ($changeArray[$i] != 0) {
          $done = 0;
        }
      }
      print("CA ROW $row ");
      for(my $i = 1;$i <= $numCols;$i++) {
        print("$changeArray[$i]");
      }
      print("\n");
    } else {
      print("Board not consistant with column\n");

      print("  ROW $row ");
      for(my $i = 1;$i <= $numCols;$i++) {
        print("$col[$i]");
      }
      print("\n");
      print("  BOARD $row ");
      for(my $i = 1;$i <= $numCols;$i++) {
        print("$orig[$row][$i]");
      }
      print("\n");
    }


    if ($blankArray[$numBlankPosition-1] == 
        ($numBlanks - ($rows[$row][0] - 1))) {
      $done = 1;
    }
    if ($loopCount > 5) {
      $done = 1;
    } else {
      $loopCount++;
    }

  }
  for(my $i = 1;$i <= $numCols;$i++) {
    if ($changeArray[$i] > 0) {
      print("SET BOARD $row,$i = $changeArray[$i]\n");
      $orig[$row][$i] = $changeArray[$i];
    }
  }

}


###############################################################################
###############################################################################
###############################################################################

sub ColTryAllCombinations {
  my $col = $_[0];
  my $ptr = $_[1];
  my @orig = @$ptr;

  my $sum = 0;

  ## Do special case.. items fill whole thing
  for(my $i = 1;$i <= $cols[$col][0];$i++) {
    $sum = $sum + $cols[$col][$i];
  }

  my $numBlanks = $numRows - $sum;
  my $numBlankPosition = $cols[$col][0] + 1;
  print("Number of Blanks in col $col = $numBlanks\n");

  my @copy = @orig;
  my @blankArray;
  my @changeArray;

  for(my $i = 1;$i <= $numRows;$i++) {
    $changeArray[$i] = -1;
    ## set to 1 for blank
    ## set to 2 for X
    ## reset to zero for inconsistants
  }

  for(my $i = 1;$i < $numBlankPosition-1;$i++) {
    $blankArray[$i] = 1;
  }
  $blankArray[$numBlankPosition-1] = 0;
  $blankArray[0] = $numBlanks - ($cols[$col][0] - 1);

  my $loopCount = 1;
  my $first = 1;
  my $done = 0;
  ##
  while ($done != 1) {

    ## Array is already set up for first time
    if ($first != 1) {
      my $temp;
      $temp = updateBlankArray(\@blankArray, $numBlankPosition);
      @blankArray = @$temp;
    } else {
      $first = 0;
    }
    print("COL $col BA ");
    for(my $i = 0;$i < $numBlankPosition;$i++) {
      print("$blankArray[$i]");
    }
    print("\n");

    ## lay out data
    my $pos = 1;
    my @row;

    ## Do first blank
    for(my $i = 0;$i < $blankArray[0];$i++) {
      $row[$pos] = 1;
      $pos++;
    }

    ## Loop over X and blanks
    for(my $item = 1;$item <= $cols[$col][0];$item++) {
      ## Do X
      for(my $i = 0;$i < $cols[$col][$item];$i++) {
        $row[$pos] = 2;
        $pos++;
      }
      ## Do blank
      for(my $i = 0;$i < $blankArray[$item];$i++) {
        $row[$pos] = 1;
        $pos++;
      }
    }


    if (isRowConsistant(\@row, $ptr, $col)) {

      print("CA COL $col ");
      for(my $i = 1;$i <= $numRows;$i++) {
        print("$changeArray[$i]");
      }
      print("\n  COL $col ");
      for(my $i = 1;$i <= $numRows;$i++) {
        print("$row[$i]");
      }
      print("\n");
      for(my $i = 1;$i <= $numRows;$i++) {
        if ($changeArray[$i] == -1) {
          $changeArray[$i] = $row[$i];
        } else {
          ## inconsistant
          if ($changeArray[$i] != $row[$i]) {
            $changeArray[$i] = 0;
          }
        }
      }
      $done = 1;
      for(my $i = 1;$i <= $numRows;$i++) {
        if ($changeArray[$i] != 0) {
          $done = 0;
        }
      }
      print("CA COL $col ");
      for(my $i = 1;$i <= $numRows;$i++) {
        print("$changeArray[$i]");
      }
      print("\n");
    } else {
      print("Board not consistant with row\n");

      print("  COL $col ");
      for(my $i = 1;$i <= $numRows;$i++) {
        print("$row[$i]");
      }
      print("\n");
      print("  BOARD $col ");
      for(my $i = 1;$i <= $numRows;$i++) {
        print("$orig[$i][$col]");
      }
      print("\n");
    }


    if ($blankArray[$numBlankPosition-1] == 
        ($numBlanks - ($cols[$col][0] - 1))) {
      $done = 1;
    }
    if ($loopCount > 5) {
      $done = 1;
    } else {
      $loopCount++;
    }

  }
  for(my $i = 1;$i <= $numRows;$i++) {
    if ($changeArray[$i] > 0) {
      print("SET BOARD $i,$col = $changeArray[$i]\n");
      $orig[$i][$col] = $changeArray[$i];
    }
  }
}

###############################################################################
###############################################################################
###############################################################################

sub LayoutRows {

  my $ptr = $_[0];

  my @orig_board = @$ptr;

  for(my $i = 1;$i <= $numRows;$i++) {

    my $finished = 1;

    ## if row not finished
    for(my $j = 1;$j <= $numCols;$j++) {
      if ($orig_board[$i][$j] == 0) {
        $finished = 0;
        $j = $numCols;
      }
    }
    
    ## then

    if ($finished == 0) {
      RowTryAllCombinations($i, $ptr);
    }
  }
}


###############################################################################
###############################################################################
###############################################################################

sub LayoutCols {


  my $ptr = $_[0];

  my @orig_board = @$ptr;

  for(my $i = 1;$i <= $numCols;$i++) {

    my $finished = 1;

    ## if row not finished
    for(my $j = 1;$j <= $numRows;$j++) {
      if ($orig_board[$j][$i] == 0) {
        $finished = 0;
        $j = $numRows;
      }
    }
    
    ## then

    if ($finished == 0) {
      ColTryAllCombinations($i, $ptr);
    }
  }

}


###############################################################################
###############################################################################
###############################################################################

sub CopyBoard {

  my $ptr1 = $_[0];
  my @b1 = @$ptr1;
  my @b2;


  for(my $i = 1;$i <= $numRows;$i++) {

    for(my $j = 1;$j <= $numCols;$j++) {
      $b2[$i][$j] = $b1[$i][$j];
    }
  }
  return @b2;
}

###############################################################################
###############################################################################
###############################################################################

sub CheckDone {

  my $ptr1 = $_[0];
  my $ptr2 = $_[1];
  my $loop = $_[2];

  my @b1 = @$ptr1;
  my @b2 = @$ptr2;


  for(my $i = 1;$i <= $numRows;$i++) {

    for(my $j = 1;$j <= $numCols;$j++) {
      if ($b1[$i][$j] != $b2[$i][$j]) {
        $loop++;
        return $loop;
      }
    }
  }

  $loop = -1;

  return $loop;
}
###############################################################################
###############################################################################
###############################################################################

sub PrintThisBoard {

  my $ptr = $_[0];
  
  PrintColHeader();
  for(my $i = 1;$i <= $numRows;$i++) {
    PrintRow($i);
    for(my $j = 1;$j <= $numCols;$j++) {
      PrintBoard($i, $j, $ptr);
    }
    print("\n");
  }
  print("\n\n");
}

###############################################################################
###############################################################################
###############################################################################

sub PrintData {
  my $data = $_[0]; 

  if ($data < 0) {
    print("   ");
  } else {
    if ($data < 10) {
      print("  ");
    }
    print("$data");
  }
}

###############################################################################
###############################################################################
###############################################################################

sub PrintRow {
    
  my $row = $_[0];   

  if ($rows[$row][0] > 0) {
    
    PrintData($rows[$row][1]);

    for(my $i = 2;$i <= $rows[$row][0];$i++) {
      PrintData($rows[$row][$i]);
    }
    for(my $i = $rows[$row][0]+1;$i <= $maxRow;$i++) {
      PrintData(-1);
    }
  }
}

###############################################################################
###############################################################################
###############################################################################

sub PrintColHeader {
  for(my $j = 1;$j <= $maxCol;$j++) {
    ## white space
    for(my $i = 0;$i < $maxRow;$i++) {
      PrintData(-1);
    }
    for(my $k = 1;$k <= $numCols;$k++) {
      if ($cols[$k][0] >= $j) {
        PrintData($cols[$k][$j]);
      } else {
        PrintData(-1);
      }
    }
    print("\n");
  }
}

###############################################################################
###############################################################################
###############################################################################

sub PrintBoard {
    
  my $row = $_[0];
  my $col = $_[1];
  my $ptr = $_[2];
  my @b = @$ptr;

  if ($b[$row][$col] == 0) {
    print(" ??");
  }

  if ($b[$row][$col] == 1) {
    print("   ");
  }

  if ($b[$row][$col] == 2) {
    print(" XX");
  }
}

###############################################################################
###############################################################################
###############################################################################

sub GetData {

  my $datFile = $_[0];
  my $line;
  my @fields;

  my $numRows;
  my $numCols;
  my $maxRows;
  my $maxCols;
  my @rows;
  my @cols;
  
  open(DATFILE, $datFile);
  while ($line = <DATFILE>) {
    chomp($line);
    @fields = split(/ +/, $line);

    if ($fields[0] eq "NUMROWS") {
      $numRows = $fields[1];
      for(my $i = 1;$i <= $numRows;$i++) {
        $rows[$i][0] = 0;
      }
    }

    if ($fields[0] eq "NUMCOLS") {
      $numCols = $fields[1];
      for(my $i = 1;$i <= $numCols;$i++) {
        $cols[$i][0] = 0;
      }
    }


    if ($fields[0] eq "ROW") {
      if ($fields[1] > $numRows) {
        print("Specified row($fields[1]) is greater than max($numRows)\n");
        exit;
      }
      $rows[$fields[1]][0] = $fields[2];
      if ($fields[2] > $maxRow) {
        $maxRow = $fields[2];
      }
      for(my $i = 1;$i <= $fields[2];$i++) {
#        print("Fill in row [$fields[1]] [$i]\n");
        $rows[$fields[1]][$i] = $fields[$i + 2];
      }
    }


    if ($fields[0] eq "COL") {
      if ($fields[1] > $numCols) {
        print("Specified column($fields[1]) is greater than max($numCols)\n");
        exit;
      }
      $cols[$fields[1]][0] = $fields[2];
      if ($fields[2] > $maxCol) {
        $maxCol = $fields[2];
      }
      for(my $i = 1;$i <= $fields[2];$i++) {
#        print("Fill in col [$fields[1]] [$i]\n");
        $cols[$fields[1]][$i] = $fields[$i + 2];
      }
    }
  }

  return \@rows, \@cols, $numRows, $numCols, $maxRow, $maxCol;
}