# Crossword grid verification

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
#  ##
#
#
#
##  #


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:

• Does the symetry requirement also apply to the grid's known contents, or only to the structure (# or not #)? – J B Feb 12 '11 at 10:50
• Only to the structure of blocked and in-play squares. – dmckee --- ex-moderator kitten Feb 12 '11 at 15:50
• Oh, this one already had a bounty. Bummer. Still, I think two answers are a bit few. – Joey Feb 27 '11 at 11:15
• Center symmetry and 180°-rotation are the same thing - aren't they? But I don't see vertical, nor horizontal symmetry. But 90°-rotation. – user unknown May 26 '12 at 14:11

# 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)

• Would you care to explain a little for those of us who don't speak ruby? I can see how you've removed any non-blacks from in-play squares, and how the answer length checking works (nice, BTW), but I'm not quite getting the symmetry check. – dmckee --- ex-moderator kitten Feb 14 '11 at 20:26
• I see a problem here of how the width of the grid is determined - by taking the length of the 1st line. That is incorrect, it will only work on the example where that line is "5---5" (three spaces in the middle). If it was "5 5" it wont work! – Nas Banov Mar 5 '11 at 0:41
• Also i think there is a problem with "veritcal wrap-around", when going over the 1st row and looking one row down (+n) and one row up (-n) - the latter will look in the last row and may mistakenly pick-up space from there! – Nas Banov Mar 5 '11 at 1:07
• Well you are right for the width of the grid; I assumed that on the first line, the second number is always aligned to the end of the line. – Arnaud Le Blanc Mar 10 '11 at 9:12

## 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
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]='#';
}
}

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) {
return 8;
}
return 0;
}


## 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

## 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.