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.

• Keith Randall: Single-character spans are not numbered, right?
• dmckee --- ex-moderator kitten: @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.
• www0z0k: will input file be in txt?
• dmckee --- ex-moderator kitten: @www0z0k: Yes. The unix geek in me always defaults to text.
• dmckee --- ex-moderator kitten: @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.

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.

• dmckee --- ex-moderator kitten: I follow most of that. Not sure what s.shift.split.map does, but that must be forming the array from the input.
• dmckee --- ex-moderator kitten: 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).
• Arnaud Le Blanc: 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.

Answer 2

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

• dmckee --- ex-moderator kitten: I wondered when someone was going to do it in a 1d array.

Answer 3

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

• gnibbler: You should be able to use h.join(f) I think
• gnibbler: and next(f) instead of f.readline() if you are >=2.6 else f.next()
• dmckee --- ex-moderator kitten: 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.
• Keith Randall: @dmckee, yes I'm using extra #s to mark the edge. Can you post a test case where you think it fails?
• dmckee --- ex-moderator kitten: @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?

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);}

• dmckee --- ex-moderator kitten: Took me a few tries to invoke it right. Slick.

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

• ugoren: 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.
• breadbox: 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?
• ugoren: Any example where the rows and columns numbers are not equal.
• breadbox: 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)?
• ugoren: 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).

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

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

• Aman ZeeK Verma: 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 :)
• dmckee --- ex-moderator kitten: My /bin/sh complains about line 11. Could you say what shell you are using (including version number)?
• Aman ZeeK Verma: 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)
• Aman ZeeK Verma: try modifying #!bin/sh to #/!/bin/bash , It should work now!

Answer 10

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

• Jonathan Watmough: 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.