Crossword grid verification

Question

Validate a proposed crossword grid.

Entries should be full programs that simply test a proposed grid to determine if it meets a set of conditions for making crossword solvers happy.

Input

The input will be the name of a file representing the crossword grid. The input filename may be passed as an argument, on the standard input, or by other conventional means other than hardcoding.

Grid file format: The first line consists of two white-space separated integer constants M and N. Following that line are M lines each consisting of N characters (plus a new line) selected from [#A-Z ]. These characters are interpreted such that '#' indicates a blocked square, ' ' a open square in the puzzle with no known contents and any letter an open square whose containing that letter.

Output

The program should produce no output on valid grids and exit with normal termination state. If the proposed grid fails, the program should produce a diagnostic error message and exit with a abnormal termination state (i.e. not 0 on unix) if this is supported by your execution environment. The error message should indicate both which condition for validity is violated and the location of the offending square; you are free to chose the means of conveying these facts.

Conditions for validity

Valid grids will have no answers (across or down) that are only 1 character long (extra credit for making the minimum length a input parameter), and will exhibit the usual symmetry. The usual symmetry means the crossword remains the same after (three equivalent descriptions of the same operation):

• reflection through it's own center
• reflection both vertically and horizontally
• 180 degree rotation

Test input and expected output

Passes:

5   5
#  ##
#    
  #  
    #
##  #

Fails on short answer:

5   5
## ##
#    
  #  
    #
## ##

Fails on symmetry:

5   5
#  ##
#    
  #  
#   #
##  #

Aside

This is the second of several crossword related challenges. I plan to use a consistent set of file-formats throughout and to build up a respectable suite of crossword related utilities in the process. For instance a subsequent puzzle will call for printing a ASCII version of the crossword based on the input and output of this puzzle.

Previous challenges in this series:

• Crossword numbering

Answer 1

Ruby - 215 207

t,*d=$<.map &:chop;n,d,e=t.size+1,(d*S=?#).gsub(/[^#]/,W=" "),->c,i{puts [c,i/n+1,i%n+1]*" ";exit 1}
0.upto(d.size-1){|i|d[i]==d[-i-1]||e[?R,i];d[i]==W&&(d[i-1]!=W&&d[i+1]!=W||d[i-n]!=W&&d[i+n]!=W)&&e[?L,i]}

Ungolfed:

h, *g = $<.map &:chop
w = h.size+1
g = (g*?#).gsub(/[^#]/," ")
error = ->c,i{ puts [c,i/w+1,i% w+1]*" "; exit 1 }
0.upto(size-1) { |i|
        error[?R, i] if g[i] != g[-i-1]
        error[?L,i] if g[i]==" " && (g[i-1]!=" " && g[i+1]!=" " || g[i-w]!=" " && g[i+w] != " ")
}

.

h, *g = $<.map &:chop

This basically removes the last char (line break) of each input line by calling the chop method on them, and returning an array of the results.

h takes the first element of this array and *g takes the rest. So we end up with the first line in h and the crossword grid lines in g.

g = (g*?#).gsub(/[^#]/," ")

g*?# joins (*) the array g with the "#" (?# is a character literal). This is the same as g.*("#"), or g.join("#"). Then every non # is replaced by a space.

For the symmetry check we just have to check if the char at every index is equals to the char at the opposite index in the string:

0.upto(g.size-1) { |i| if g[i] != g[g.size - i - 1]; error() }

In Ruby we can index strings from the end using negative indexes (starting from -1 instead of 0), so that g[-i-1] is the opposite of g[i] in the string. This saves a few chars:

0.upto(g.size-1) { |i| if g[i] != g[-i-1]; error() }

We can save a ; by using a conditional statement:

0.upto(g.size-1) { |i| error() if g[i] != g[-i-1] }

In the golfed version we can save a few more chars:

0.upto(g.size-1){|i|g[i]==g[-i-1]||error()}

In a previous version I used recursion for iterating over the string:

(f=->i{g[i]&&f[i+1]&&g[i]!=g[-i-1]&&error()})[0]

An out of bound access to g returns nil, so once g[i] returns nil, this stops the iteration.

Output format:

{ L | R } line-number column-number

L for length errors, and R for rotation error (so L 1 2 means length error at line 1, column 2)

Answer 2

APL (115)

{∨/,k←⍵≠⌽⊖⍵:'⍉',(,k×⍳⍴k)~⊂2/0⋄×⍴d←(,⊃,/(g(⍉g←⍳⍴⍵))×{k↑1⌽1⊖0 1 0⍷¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵}¨⍵(⍉⍵))~⊂2/0:'∘',d}d↑↑{'#'≠⍞}¨⍳⊃d←⎕

If the grid is not symmetrical, it outputs ⍉ followed by the coordinates, i.e. for the example it gives

⍉ 2 5  4 1

If the grid has short answers, it outputs ∘ followed by the coordinates, i.e. for the example it gives

∘ 1 2  5 2

Explanation:

• d↑↑{'#'≠⍞}¨⍳⊃d←⎕: read the first line as a list of numbers and store in d, then read as many lines as the first number, and reshape as a matrix of size d. 'Closed' squares are stored as 0 and 'open' squares as 1.
• ∨/,k←⍵≠⌽⊖⍵: store in k the places where the grid is asymmetrical. If there is such a place...
• '⍉',(,k×⍳⍴k)~⊂2/0: output a ⍉ followed by the offending coordinates
• ⋄: otherwise...
• ~⊂2/0: remove the zero coordinates from the following list:
• ¨⍵(⍉⍵): for both the grid and its transpose...
• ¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵: surround the grid with zeros (i.e. closed squares)
• 0 1 0⍷: see where it contains an 'open' square enclosed by two 'closed' squares (= too short)
• k↑1⌽1⊖: remove the ring of extra zeros again
• ,⊃,/(g(⍉g←⍳⍴⍵))×: multiply by coordinates and transposed coordinates, and join together, to form a list of offending coordinates (and a lot of zeros which we remove).
• ×⍴d←: store the offending coordinates in d, and if there are any...
• :'∘',d: output a ∘ followed by the coordinates.

Answer 3

C, 278 chars

char*f,g[999],*r=g;i,j,h,w;main(e){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(g+h*w,99,f);++h);
for(;j++<h;)for(i=0;i++<w;++r)if(e=*r==35^g[g+w*h-r-1]==35?83:
*r==35||i>1&r[-1]!=35|i<w&r[1]!=35&&j>1&r[-w]!=35|j<h&r[w]!=35?0:76)
exit(printf("%d%c%d\n",j,e,i));exit(0);}

As you might expect, the error messages have themselves been golfed. They take the following form:

11L8 - indicates a length error at row 11 column 8

4S10 - indicates a symmetry error at row 4 column 10

Answer 4

Reference implementation

c99

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void readgrid(FILE *f, int m, int n, char grid[m][n]){
  int i = 0;
  int j = 0;
  int c = 0;
  while ( (c = fgetc(f)) != EOF) {
    if (c == '\n') {
      if (j != n) fprintf(stderr,"Short input line (%d)\n",i);
      i++;
      j=0;
    } else {
      grid[i][j++] = c;
    }
  }
}

int isSymmetric(int m, int n, char g[m][n]){
  for (int i=0; i<m; ++i)
    for (int j=0; j<n; ++j)
      if ( (g[i][j]=='#') != (g[m-i-1][n-j-1]=='#') )
    return j*m+i;
  return -1;
}

int isLongEnough(int m, int n, char g[m][n], int min){
  /* Check the rows */
  for (int i=0; i<m; ++i) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int j=0; j<n; ++j) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == j-1) && (j-lb <= min+1) ) return lo*m+i;
    lb=j;
      } else {
    /* In-play square */
    lo=j;
      }
    }
  }

  /* Check the columns */
  for (int j=0; j<n; ++j) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int i=0; i<m; ++i) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == i-1) && (i-lb <= min+1) ) return lo*m+i;
    lb=i;
      } else {
    /* In-play square */
    lo=i;
      }
    }
  }

  /* Passed */
  return -1;
}

int main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;
  int min=1;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the minium
         answer length */
    if ( (min=atoi(argv[2]))<1 ) {
      fprintf(stderr,"%s: Minimum length '%s' too short. Exiting.",
          argv[0],argv[2]);
      return 2;
    }
    /* FALLTHROUGH */
  case 2: /* exactly one argument */
    infname = argv[1];
    if (!(inf = fopen(infname,"r"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[1]);
      return 1;
    };
    break;
  default:
    printf("%s: Verify crossword grid.\n\t%s <grid file> [<minimum length>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0,e=-1;
  char lbuf[81];
  fgets(lbuf,81,inf);
  sscanf(lbuf,"%d %d",&m,&n);

  /* Intialize the grid */
  char grid[m][n];
  for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
      grid[i][j]='#';
    }
  }

  readgrid(inf,m,n,grid);

  if ((e=isSymmetric(m,n,grid))>=0) {
    fprintf(stderr,"Symmetry violation at %d,%d.\n",e/m+1,e%m+1);
    return 4;
  } else if ((e=isLongEnough(m,n,grid,min))>=0) {
    fprintf(stderr,"Short answer at %d,%d.\n",e/m+1,e%m+1);
    return 8;
  }
  return 0;
}