8
\$\begingroup\$

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:

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

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)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – dmckee Feb 14 '11 at 20:26
  • \$\begingroup\$ 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! \$\endgroup\$ – Nas Banov Mar 5 '11 at 0:41
  • \$\begingroup\$ 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! \$\endgroup\$ – Nas Banov Mar 5 '11 at 1:07
  • \$\begingroup\$ 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. \$\endgroup\$ – Arnaud Le Blanc Mar 10 '11 at 9:12
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.