Crossword numbering

Question

Produce a program to correctly number a crossword grid.

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: A text file. 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 output will be a numbering file, and may be sent to the standard output, to a file whose name is derived from the input filename, to a user specified file, or to some other conventional destination.

Numbering file format A text file. Lines starting with '#' are ignored and may be used for comments. All other lines contain a tab separated triplet i, m, n where i represents a number to be printed on the grid, and m and n represent the row and column of the square where it should be printed. The number of both rows and columns starts at 1.

Numbering scheme

A correctly numbered grid has the following properties:

1. Numbering begins at 1.
2. No column or span of open squares is unnumbered. (You may assume that no single character answer will exist in the problem.)
3. Numbers will be encountered in counting order by scanning from top row to the bottom taking each row from left to right. (So, every horizontal span is numbered at its leftmost square, and every column is numbered at its topmost square.)

Test input and expected output

Input:

5   5
#  ##
#    
  #  
    #
##  #

Output (neglecting comment lines):

1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3

Aside

This is the first of what will hopefully be 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.

Answer 1

Ruby - 210 139 characters

o=0
(n=(/#/=~d=$<.read.gsub("
",S='#'))+1).upto(d.size-1){|i|d[i]!=S&&(i<n*2||d[i-1]==S||d[i-n]==S)&&print("%d\t%d\t%d
"%[o+=1,i/n,i%n+1])}

Tested with ruby 1.9.

Answer 2

Python, 194 177 176 172 characters

f=open(raw_input())
V,H=map(int,next(f).split())
p=W=H+2
h='#'
t=W*h+h
n=1
for c in h.join(f):
 t=t[1:]+c;p+=1
 if'# 'in(t[-2:],t[::W]):print"%d\t%d\t%d"%(n,p/W,p%W);n+=1

Answer 3

PHP - 175 characters

<?for($i=$n=strpos($d=strtr(`cat $argv[1]`,"\n",$_="#"),$_)+$o=1;isset($d[$i]);++$i)$d[$i]!=$_&($i<$n*2|$d[$i-1]==$_|$d[$i-$n]==$_)&&printf("%d\t%d\t%d\n",$o++,$i/$n,$i%$n+1);

Answer 4

C++ 270 264 260 256 253 char

#include<string>
#include<iostream>
#define X cin.getline(&l[1],C+2)
using namespace std;int main(){int r=0,c,R,C,a=0;cin>>R>>C;string l(C+2,35),o(l);X;for(;++r<=R;o=l)for(X,c=0;++c<=C;)if(l[c]!=35&&(l[c-1]==35||o[c]==35))printf("%d %d %d\n",++a,r,c);}

To use:

g++ cross.cpp -o cross
cat puzzle |  cross

Nicely formatted:

#include<string>
#include<iostream>
// using this #define saved 1 char
#define X cin.getline(&l[1],C+2)

using namespace std;

int main()
{
    int r=0,c,R,C,a=0;
    cin>>R>>C;
    string l(C+2,35),o(l);
    X;

    for(;++r<=R;o=l)
        for(X,c=0;++c<=C;)
            if(l[c]!=35&&(l[c-1]==35||o[c]==35))
                printf("%d %d %d\n",++a,r,c);
}

I tried reading the whole crossword in one go and using a single loop.
But the cost of compensating for the '\n character outweighed any gains:

#include <iostream>
#include <string>
#define M cin.getline(&l[C+1],R*C
using namespace std;

int main()
{
    int R,C,a=0,x=0;
    cin>>R>>C;
    string l(++R*++C,35);
    M);M,0);

    for(;++x<R*C;)
        if ((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))
            printf("%d %d %d\n",++a,x/C,x%C);
}

Compressed: 260 chars

#include<iostream>
#include<string>
#define M cin.getline(&l[C+1],R*C
using namespace std;int main(){int R,C,a=0,x=0;cin>>R>>C;string l(++R*++C,35);M);M,0);for(;++x<R*C;)if((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))printf("%d %d %d\n",++a,x/C,x%C);}

Answer 5

C, 184 189 chars

char*f,g[999],*r=g;i,j,n;main(w){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(r,99,f);++j)
for(i=0;i++<w;++r)
*r==35||j&&i>1&&r[-w]-35&&r[-1]-35||printf("%d\t%d\t%d\n",++n,j+1,i);}

Not much to say here; the logic is pretty basic. The program takes the filename on standard input at runtime. (It's so annoying that the program has to work with a filename, and can't just read the file contents directly from standard input. But the one who pays the piper calls the tune!)

The weird fscanf() pattern is my attempt to scan the full first line, including the newline but not including leading whitespace on the following line. There's a reason why nobody uses scanf().

Answer 6

Reference implementation:

c99 ungolfed and rather more than 2000 characters including various debugging frobs still in there.

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

void printgrid(int m, int n, char grid[m][n]){
  fprintf(stderr,"===\n");
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
      switch (grid[i][j]) {
      case '\t': fputc('t',stderr); break;
      case '\0': fputc('0',stderr); break;
      case '\n': fputc('n',stderr); break;
      default: fputc(grid[i][j],stderr); break;
      }
    }
    fputc('\n',stderr);
  }
  fprintf(stderr,"===\n");
}

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 main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the output
         filename */
    if (!(outf = fopen(argv[2],"w"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. 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: Number a crossword grid.\n\t%s <grid file> [<output file>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0;
  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]='#';
    }
  }

/*    printgrid(m,n,grid); */
  readgrid(inf,m,n,grid);
/*    printgrid(m,n,grid);  */

  /* loop through the grid  produce numbering output */
  fprintf(outf,"# Numbering for '%s'\n",infname);
  int num=1;
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
/*       fprintf(stderr,"\t\t\t (%d,%d): '%c' ['%c','%c']\n",i,j, */
/*        grid[i][j],grid[i-1][j],grid[i][j-1]); */
      if ( grid[i][j] != '#' &&
       ( (i == 0) || (j == 0) ||
         (grid[i-1][j] == '#') ||
         (grid[i][j-1] == '#') )
         ){
    fprintf(outf,"%d\t%d\t%d\n",num++,i+1,j+1);
      }
    }
  }
  fclose(outf);
  return 0;
}

Answer 7

PerlTeX: 1143 chars (but I haven't golfed it yet)

\documentclass{article}

\usepackage{perltex}
\usepackage{tikz}

\perlnewcommand{\readfile}[1]{
  open my $fh, '<', shift;
  ($rm,$cm) = split /\s+/, scalar <$fh>;
  @m = map { chomp; [ map { /\s/ ? 1 : 0 } split // ] } <$fh>;
  return "";
}

\perldo{
  $n=1;
  sub num {
    my ($r,$c) = @_;
    if ($r == 0) {
      return $n++;
    }
    if ($c == 0) {
      return $n++;
    }
    unless ($m[$r][$c-1] and $m[$r-1][$c]) {
      return $n++;
    }
    return;
  }
}

\perlnewcommand{\makegrid}[0]{
  my $scale = 1;
  my $return;
  my ($x,$y) = (0,$r*$scale);
  my ($ri,$ci) = (0,0);
  for my $r (@m) {
    for my $open (@$r) {
      my $f = $open ? '' : '[fill]';
      my $xx = $x + $scale;
      my $yy = $y + $scale;
      $return .= "\\draw $f ($x,$y) rectangle ($xx,$yy);\n";

      my $num = $open ? num($ri,$ci) : 0;
      if ( $num ) {
        $return .= "\\node [below right] at ($x, $yy) {$num};";
      }

      $x += $scale;
      $ci++;
    }
    $ci = 0;
    $x = 0;
    $ri++;
    $y -= $scale;
  }
  return $return;
}

\begin{document}
\readfile{grid.txt}

\begin{tikzpicture}
  \makegrid
\end{tikzpicture}

\end{document}

It needs a file called grid.txt with the spec, then compile with

perltex --nosafe --latex=pdflatex grid.tex

Answer 8

Scala 252:

object c extends App{val z=readLine.split("[ ]+")map(_.toInt-1)
val b=(0 to z(0)).map{r=>readLine}
var c=0
(0 to z(0)).map{y=>(0 to z(1)).map{x=>if(b(y)(x)==' '&&((x==0||b(y)(x-1)==35)||(y==0||b(y-1)(x)==35))){c+=1
println(c+"\t"+(y+1)+"\t"+(x+1))}}
}}

compilation and invocation:

scalac cg-318-crossword.scala && cat cg-318-crossword | scala c

Answer 9

ANSI C 694 chars

This is a C version that looks for horizontal or vertical runs of two spaces that are either butted up against the edge, or against a '#' character.

Input file is taken from stdin and must be:

<rows count> <cols count><newline>
<cols characters><newline> x rows
...

Any tips for compacting this will be gratefully received.

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

#define H '#'

char *p,*g;
int m=0,d=0,r=0,c=0,R=0,C=0;
void n() {
    while(!isdigit(d=getchar()));
    m=d-'0';
    while(isdigit(d=getchar()))
        m=m*10+d-'0';
}

int t() {
    return (((c<1||*(p-1)==H)&&c<C-1&&*p!=H&&p[1]!=H)||
            ((r<1||*(p-C-1)==H)&&r<R-1&&*p!=H&&p[C+1]!=H));
}

int main (int argc, const char * argv[]) 
{
    n();R=m;m=0;n();C=m;
    p=g=malloc(R*C+R+1);
    while((d=getchar())!=EOF) {
        *p++=d;
    }
    int *a,*b;
    b=a=malloc(sizeof(int)*R*C+R+1);
    p=g;m=0;
    while(*p) {
        if(t()) {
            *a++=++m;
            *a++=r+1;
            *a++=c+1;
        }
        if(++c/C) r++,p++;
        c-=c/C*c;
        p++;
    }
    while(*b) {
        printf("%d\t%d\t%d\n",*b,b[1],b[2]);
        b+=3;
    }
}

Output for the Example Provided

1   1   2
2   1   3
3   2   2
4   2   4
5   2   5
6   3   1
7   3   4
8   4   1
9   4   3
10  5   3

Answer 10

SHELL SCRIPT

#!/bin/sh
crossWordFile=$1

totLines=`head -1 $crossWordFile | cut -d" " -f1`
totChars=`head -1 $crossWordFile | awk -F' ' '{printf $2}'`

NEXT_NUM=1
for ((ROW=2; ROW<=(${totLines}+1); ROW++))
do
   LINE=`sed -n ${ROW}p $crossWordFile`
   for ((COUNT=0; COUNT<${totChars}; COUNT++))
   do
      lineNumber=`expr $ROW - 1`
      columnNumber=`expr $COUNT + 1`
      TOKEN=${LINE:$COUNT:1}
      if [ "${TOKEN}" != "#" ]; then
      if [ ${lineNumber} -eq 1 ] || [ ${columnNumber} -eq 1 ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
      elif [ "${TOKEN}" != "#" ] ; then
          upGrid=`sed -n ${lineNumber}p $crossWordFile | cut -c"${columnNumber}"`
          leftGrid=`sed -n ${ROW}p $crossWordFile | cut -c${COUNT}`
          if [ "${leftGrid}" = "#" ] || [ "${upGrid}" = "#" ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
          fi
      fi
      fi
   done
done

sample I/O:

./numberCrossWord.sh crosswordGrid.txt

1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3