9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Single-character spans are not numbered, right? \$\endgroup\$ – Keith Randall Feb 1 '11 at 4:17
  • \$\begingroup\$ @Kieth: I prefer the rule where there are no such spans, but I haven't specified it here because validating the grid is planned as another problem. I suppose which you use is a matter of taste. \$\endgroup\$ – dmckee Feb 1 '11 at 4:30
  • \$\begingroup\$ will input file be in txt? \$\endgroup\$ – www0z0k Feb 5 '11 at 0:19
  • \$\begingroup\$ @www0z0k: Yes. The unix geek in me always defaults to text. \$\endgroup\$ – dmckee Feb 5 '11 at 0:25
  • 1
    \$\begingroup\$ @www0z0k: Line breaks are whatever is native on your platform. That's ASCII decimal 20 on mine and represented as '\n' in c on all platforms. The assumption is that the input file was produced on the same system that will process it, so this issue should be transparent. A general note about code-golf: if you're working in a strange language or on a strange platform simple make a note of anything that might surprise the reader. People will make allowance for that in judging your submission. \$\endgroup\$ – dmckee Feb 5 '11 at 0:57

10 Answers 10

4
+50
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I follow most of that. Not sure what s.shift.split.map does, but that must be forming the array from the input. \$\endgroup\$ – dmckee Feb 4 '11 at 19:09
  • \$\begingroup\$ BTW-- How should I invoke it at a unix command line. I tried giving it a shebang appropriate to my system, but it complains ./temp.ruby:4: wrong argument type Symbol (expected Proc) (TypeError). \$\endgroup\$ – dmckee Feb 4 '11 at 19:20
  • \$\begingroup\$ s.shift takes the first line, split returns ["m", "n"], map returns [m, n]. I'm running it with ruby1.9 like this: ruby1.9 test.rb. \$\endgroup\$ – Arnaud Le Blanc Feb 4 '11 at 20:03
3
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ I wondered when someone was going to do it in a 1d array. \$\endgroup\$ – dmckee Feb 5 '11 at 18:46
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You should be able to use h.join(f) I think \$\endgroup\$ – gnibbler Feb 1 '11 at 7:23
  • \$\begingroup\$ and next(f) instead of f.readline() if you are >=2.6 else f.next() \$\endgroup\$ – gnibbler Feb 1 '11 at 7:24
  • \$\begingroup\$ My python was never very good, but it looks like you're using extra '#'s to handle the edge cases, no? However, I'm getting some odd output on the test data, including extra numbers. \$\endgroup\$ – dmckee Feb 1 '11 at 12:54
  • \$\begingroup\$ @dmckee, yes I'm using extra #s to mark the edge. Can you post a test case where you think it fails? \$\endgroup\$ – Keith Randall Feb 1 '11 at 17:12
  • \$\begingroup\$ @Kieth: For the test case above I'm getting 12 output lines (and the first 10 don't match). Using python2.6 or 2.7 on my Mac. Running it with echo test_input_file_name | python golf.py, is that wrong? \$\endgroup\$ – dmckee Feb 1 '11 at 17:18
2
\$\begingroup\$

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);}
\$\endgroup\$
  • \$\begingroup\$ Took me a few tries to invoke it right. Slick. \$\endgroup\$ – dmckee Feb 5 '11 at 7:51
2
\$\begingroup\$

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().

\$\endgroup\$
  • \$\begingroup\$ I think you reverse the rows and columns number. If I understand correctly, the first number is the number of rows, but you treat it as the number of columns. \$\endgroup\$ – ugoren May 21 '12 at 8:31
  • \$\begingroup\$ From what I can tell, the output of my program matches the example given in the description, and the output from the reference implementation. Can you give me a specific example of what you're referring to? \$\endgroup\$ – breadbox May 21 '12 at 8:51
  • \$\begingroup\$ Any example where the rows and columns numbers are not equal. \$\endgroup\$ – ugoren May 21 '12 at 12:41
  • \$\begingroup\$ Okay, but let's get specific please. When given the example grid provided in description, my program outputs (1,2) for the number 1. Are you saying that my program ought to output (2,1)? \$\endgroup\$ – breadbox May 21 '12 at 17:30
  • \$\begingroup\$ I'm talking about input, not output. When the first line is 5 5, you take the first 5 as the width, when you should have taken the second (which doesn't matter, of course, in this example). \$\endgroup\$ – ugoren May 21 '12 at 18:57
1
\$\begingroup\$

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

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

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I might have not understood the requirements fully, as I just tried to understand from provided I/O, please forgive if the solution is just a workaround for given particular case :) \$\endgroup\$ – Aman ZeeK Verma Feb 10 '11 at 6:32
  • \$\begingroup\$ My /bin/sh complains about line 11. Could you say what shell you are using (including version number)? \$\endgroup\$ – dmckee Feb 10 '11 at 7:16
  • \$\begingroup\$ Line 8 seems to be similar to line 11.. isn't? $bash --version GNU bash, version 3.1.17(1)-release (x86_64-suse-linux) \$\endgroup\$ – Aman ZeeK Verma Feb 10 '11 at 7:22
  • \$\begingroup\$ try modifying #!bin/sh to #/!/bin/bash , It should work now! \$\endgroup\$ – Aman ZeeK Verma Feb 10 '11 at 8:55
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This code correctly handles #_# vertical and horizontal single space gaps, which although they may not occur as a single unconnected space, appear to be allowed, e.g. as the last letter of a, say, horizontal word. \$\endgroup\$ – Jonathan Watmough Apr 22 '11 at 1:19

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.