use strict;
our (@empty_square, @full_square);


sub layout_crossword {
  my @puzzle = @_;
  my $N = 1;
  my @result;
  my ($h, $w) = (scalar(@puzzle), length($puzzle[0]));
  for my $y (0 .. $h-1) {
    my @row;
    for my $x (0 .. $w-1) {
      my @square;
      my $blank = is_blank($x, $y, @puzzle);
      if ($blank) {
        @square = @empty_square;
        unless (is_blank($x-1, $y, @puzzle) && is_blank($x, $y-1, @puzzle)) {
          @square = add_numeral($N++, @square);
        }
      } else {
        @square = @full_square;
      }

      # Now trim off overlap with square above
      if ($y > 0) {
        shift @square;
      }
      # trim off overlap with square to left
      if ($x > 0) {
        s/^.// for @square;
      }

      # add square to output
      for (0 .. $#square) {
        $row[$_] .= $square[$_];
      }
    } 

    for (@row) {
      tr/./ /;
    }
    push @result, @row;
  }
  @result;
}

sub add_numeral {
  my ($n, @sq) = @_;
  my $space = '\.' x length($n);
  for (@sq) {
    return @sq if s/$space/$n/;
  }
  die "Square was too small for numeral $n\n";
}

# A numeral is placed in an empty square if the square above or the
# square to the left is full, or if the empty square is in the top row
# or the leftmost column.
#
# By adopting the convention that squares outside the diagram are
# considered full, we can simplify the logic for numbering squares: A
# square gets a numeral if the square above or to the left is full.
sub is_blank {
  my ($x, $y, @puzzle) = @_;
  return if $y < 0 || $x < 0 || $y >= @puzzle || $x > length($puzzle[0]);
  return substr($puzzle[$y], $x, 1) eq ".";
}