Output a playable crossword grid

Question

Write a program to produce a file containing a crossword grid that the user can print out and work the puzzle on.

Input

A filename representing a crossword grid file and optionally a second filename representing a crossword numbering file. The input should be accepted by a conventional means for your programming environment: command line arguments, the standard input, web forms, etc..

You may assume that the crossword has been validated, and if using a numbering file that is corresponds to the grid provided.

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.

Numbering file format 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.

Output

The output will be a file that the user can print out and work a crossword on. ASCII, postscript, pdf, png, and any other reasonable format will be accepted, but all must abide by these rules:

1. There must be a rule around the entire puzzle and between every pair of squares.
2. Blocked squares must be filled in darkly.
3. In play square that represent the start of a numbered (across or down) clue must be provided with a number in the upper, left corner of the square, while leaving most of the square blank for the play to write in. Note that typical grid published in the papers will have many tens of clues and may have more than 100.

The output will be of the grid alone, without the list of clues.

Output should be sent to a conventional destination (a file whose name is derived from the input filename, produced as a web page, etc..)

Test case

Given a input of

5   5
#  ##
#    
  #  
    #
##  #

the starting corner of an acceptable ASCII output might look like this

+-----+-----+-----+---
|#####|1    |2    |###
|#####|     |     |###
|#####|     |     |###
+-----+-----+-----+---
|#####|3    |     |4  
|#####|     |     |   
|#####|     |     |   
+-----+-----+-----+---
|6    |     |#####|   
|     |     |#####|   

Those using graphical formats should take their inspiration from the usual printed sources.

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.
3. Numbers will be encountered in counting order by scanning from top row to the bottom taking each row from left to right.

Aside

This is the third 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.

Previous challenges in this series:

• Crossword numbering
• Crossword grid validation

Answer 1

Python, 379 characters

import sys
A=sys.argv
f=open(A[1])
V,H=map(int,f.readline().split())
M={}
if A[2:]:
 for r in open(A[2]).readlines():n,y,x=map(int,r.split());M[y*H+y+x]=n
R='+-----'*H+'+'
n,v,s='\n| '
x=y=z=''
p=V+1
for c in n+''.join(f):
 if c==n:print x+n+y+n+z+n+R;x=y=z=''
 elif'@'>c:x+=5*c;y+=5*c;z+=5*c
 else:x+=5*s;y+=s+s+c+s+s;z+=5*s
 if p in M:x=x[:-5]+"%-5d"%M[p]
 x+=v;y+=v;z+=v;p+=1

Answer 2

905 797 677 675 629 608 Postscript

<<-1{{30 700 translate 0 0 moveto
currentfile 2{(@A1*)*}repeat exch string
3 2 roll{('BO1)*{( )(@#)*
4(,.N:;<%)*<<( ){p}/#{(1:;>%)*}0{(;,'.)*
6 -26(CE%)*}>>(IJ'B)* known not{p
0}if(LG #C)*}forall(#;*1 D%)*}repeat
p/Times-Roman 8 selectfont 99
string{('BO)*{(@)* length(#=)*{p}{(@#L)*
35(=)*{p}{cvx(GID ?'H*ID ?KHF%)*(   )cvs(E)*}e}e}{showpage
exit}e}loop exit{( @#M# FMF#M)*
closepath}currentpoint stroke eq fill
mul dup token copy rmoveto sub show
neg exec add 1 index 9 get rlineto
put readline}loop}0 1 index 0 get{1
index 1 add}forall pop/*{{32 sub load
exec}forall}/e{ifelse}/p{pop}>>begin(23,?4)*<1f>*

This program is written as a "protocol prolog" so you just cat it together with the grid and number files (in that order, separated by blank lines) and pipe the whole mess to ghostscript or Distiller or a PS printer. Appended to the reference version below is a NYT puzzle (From Nov. 5, 2011) with numbers and one answer I'm pretty sure of (Saturdays is hard!).

"Readable" version:

<<-1{{
%space  !    "         # $ %      &           '(        )     %*    +      , - .   %/
 30     700  translate 0 0 moveto currentfile 2{(@A1*)*}repeat exch string 3 2 roll
{('BO1)*{( )(@#)* 4(,.N:;<%)*<<( ){p}/#{(1:;>%)*}0{(;,'.)* 6 -26(CE%)*}>>(IJ'B)*
known not{p 0}if(LG #C)*}forall(#;*1 D%)*}
%0      1   2          3 4          5  6     7
 repeat p /Times-Roman 8 selectfont 99 string{('BO)*{(@)* length(#=)*{p}{
(@#L)* 35(=)*{p}{cvx(GID ?'H*ID ?KHF%)*(   )cvs(E)*}e}e}{showpage clear exit}e}
%8    9   :                         %;            <      =    >    ?
 loop exit{( @#M# FMF#M)* closepath} currentpoint stroke eq fill mul
%@   A     B    C       D   E    F   G    H   I J     K L   M       N   O
 dup token copy rmoveto sub show neg exec add 1 index 9 get rlineto put readline
}loop}0 1 index 0 get{1 index 1 add}forall
pop/*{{32 sub load exec}forall}/e{ifelse}/p{pop}>>begin(23,?4)*<1f>*

The key is the /* procedure which executes a string by subtracting 32 (so space becomes 0). The big procedure is defined with the key -1. It's wrapped in a loop so that after the exit, it can hold extra tokens (using the procedure array as storage). After the procedure, there's a little bit of code to spill the loop's tokens and add one to the key; so space means the first token in the loop, bang means the second token (when executing a string).

The few single-letter definitions are used for tokens that were not frequent enough to justify the ()* characters needed to invoke through the "lexicon" (the main procedure treated as a data bank). There's more in the clp thread linked in the comments.

The main procedure itself, being defined as the integer -1 is invoked by a string containing the character 31, which is not printable. So we use a hex string <1f>*. All of the procedure bodies (loops and selection blocks) were candidates for string-encoding but some were not profitable (and each token needed at least one real representation).

The definefont version in my other answer is smaller than the reference version here, but contains so many more distinct tokens that the lexicon approach would not reduce its size below the condensed result here.

"Reference" version:

%!
/dx 30 def
/dy 30 def
/Times-Roman 24 selectfont
/square{dx 0 rlineto 0 dy neg rlineto dx neg 0 rlineto closepath}def
{
    30 700 translate 0 0 moveto
    currentfile %F
    2{dup token pop exch}repeat %X Y F
    exch string %X F str
    3 2 roll %F str X
    { %F str
        2 copy readline pop %F str st
        { %F str ch
            ( ) dup 0 4 3 roll put
            square currentpoint stroke moveto %F str ch
            <<( ){pop}
               /#{pop square currentpoint fill moveto}
                0{currentpoint 3 2 roll 6 -26 rmoveto show moveto}
            >> 1 index 2 copy known not {pop 0} if %F str ch D key
            get exec %F str
            dx 0 rmoveto
        } forall
        0 currentpoint exch pop dy sub moveto
    } repeat pop %F
    /Times-Roman 8 selectfont
    99 string {
        2 copy readline {
            dup length 0 eq {pop} {
                dup 0 get 35 eq {pop} {
                    cvx exec
                    1 sub dx mul 2 add exch
                    1 sub dy mul 9 add neg moveto
                    (   ) cvs show
                } ifelse
            } ifelse
        } {showpage exit} ifelse
    } loop clear
} exec

15 15
     #   #


       #     ##
##   #   #
    #     #
   #    #
       #
      #    #
    #     #
    K#   #   ##
##  I  #
    L
    N
    S#   #

#i m n   figure(number), row, col
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
6 1 7
7 1 8
8 1 9
9 1 11
10 1 12
11 1 13
12 1 14
13 1 15
14 2 1
15 2 6
16 2 10
17 3 1
18 4 1
19 4 9
20 5 3
21 5 7
22 5 8
23 5 11
24 5 14
25 5 15
26 6 1
27 6 2
28 6 6
29 6 10
30 6 12
31 7 1
32 7 5
33 7 10
34 7 11
35 8 1
36 8 4
37 8 9
38 9 1
39 9 8
40 9 13
41 10 1
42 10 6
43 10 7
44 10 12
45 11 1
46 11 5
47 11 7
48 11 11
49 12 3
50 12 6
51 12 9
52 12 10
53 12 14
54 12 15
55 13 1
56 13 2
57 13 8
58 14 1
59 15 1
60 15 7
60 15 11

Answer 3

C (output to SVG), 553 chars

I know, the code is huge, but this problem is just crying out for an SVG answer.

char*f,b[99];h,w;main(i){fscanf(f=fopen(gets(b),"r"),"%d%d%*[\n]",&h,&w);for(
printf("<svg xmlns='http://www.w3.org/2000/svg' viewBox='.9 .9 %d.2 %d.2'><path d='M1 1",
i=w,h);i--;)printf("v%dv-%dh1",h,h);for(;h--;)printf("v1h-%dh%d",w,w);for(
puts("' style='fill:none;stroke:#000;stroke-width:.04'/><path d='");
fgets(b,99,f);++h)for(i=0;i<w;)b[i++]-35||printf("M%d %dh1v1h-1Z",i,h+2);puts("'/>");
for(f=fopen(gets(b),"r");fgets(b,99,f);)sscanf(b,"%d%d%d",&i,&h,&w)>2&&
printf("<text x='%d.1' y='%d.3' style='font-size:.3px'>%d</text>",w,h,i);puts("</svg>");}

When run it gets the two filenames on two separate lines of standard input; first the grid file, then the numbers file.

The logic in this one is actually quite simple. The format of the SVG allows it to create all the elements in any order (instead of going from top to bottom as with the ASCII output solution). The size is due almost entirely to SVG boilerplate.

But the resulting image looks great!

Edited to add: Here's a shorter version (517 chars) that output to a specific resolution. This allows the code to use more default settings, but at the (to my mind) prohibitive cost that the SVG no longer auto-resizes in your web browser.

char*f,b[99];h,w;main(i){fscanf(f=fopen(gets(b),"r"),"%d%d%*[\n]",&h,&w);for(
printf("<svg xmlns='http://www.w3.org/2000/svg'><path d='M1 1",i=w,h);i--;)
printf("v%d0v-%d0h50",h*5,h*5);for(;h--;)printf("v50h-%d0h%d0",w*5,w*5);for(
puts("' style='fill:none;stroke:#000'/><path d='");fgets(b,99,f);++h)
for(i=-1;++i<w;)b[i]-35||printf("M%d1 %d1h50v50h-50Z",i*5,h*5+5);puts("'/>");
for(f=fopen(gets(b),"r");fgets(b,99,f);)sscanf(b,"%d%d%d",&i,&h,&w)>2&&
printf("<text x='%d3' y='%d5'>%d</text>",w*5-5,h*5-4,i);puts("</svg>");}

Answer 4

Haskell, 328 characters

import System
main=do(g:d)<-mapM(fmap lines.readFile)=<<getArgs;mapM_ putStrLn$g% \i k->[t|x<-d,y@(c:_)<-x,c/='#',(t,q)<-lex y,w q==i,k<1]
(s:g)%n=[q|(i,x)<-e g,q<-b s:[c['|':f#n[i,j]k|(j,f)<-e x]++"|"|k<-[0..2]]]++[b s]
'#'#_="#####";_#n=take 5$c n++"     ";b n='+':([1..w n!!1]>>"-----+")
e=zip[1..];c=concat;w=map read.words

Answer 5

PostScript (435) (434)

[/r{currentfile 999 string readline pop}/p{pop}/x{exch}/T{translate}/S{scale}/G{gsave}/R{grestore}/_( )>>begin/Courier 1 selectfont 
20 20 S
.05 setlinewidth{r token
p x p
dup 3 x 3 add
T
G G{R
0 -1 T
G
_ 0
r{0 0 1 1
4 index 35 eq{rectfill p}{rectstroke
put
.3 .1 moveto
_ show}ifelse
1 0 T _ 0}forall}repeat
R R
1 -1 S -.9 -.7 T{{r
dup 0 get 35 ne{( )search
p 3 2 roll
cvx exec
G
x
T
.4 -.4 S
0 0 moveto show
p
R}if}loop}stopped}exec

Un-golfed with data:

%!
<<
  /r{currentfile 999 string readline pop}
  /p{pop}
  /x{exch}
  /T{translate}
  /S{scale}
  /G{gsave}
  /R{grestore}
  /_( )
>>begin
/Courier 1 selectfont
% In theory, 20 20 scale isn't needed, 
% but it would make the whole thing very tiny when printed
% (on screen it doesn't matter too much, it can be zoomed)
20 20 S
.05 setlinewidth
{ % exec
% Read number of lines
r token                          % restString numberOfLines true
% Discard rest of line (Contains number of columns.
% It becomes clear implicitly from number of letters in a line of grid definition)
p x p                            % numberOfLines
% Move to where the top line starts
dup 3 x 3 add                    % numberOfLines x y
T                                % numberOfLines
G G
{ %repeat
  R
  % Move to next line
  0 -1 T
  G
  _ 0
  r                              % ( ) 0 line
  { %forall                      % ( ) 0 char
    0 0 1 1                      % ( ) 0 char 0 0 x y
    % Check whether char is a hash
    4 index 35 eq{ %ifelse
      4 copy rectfill
    }if
    rectstroke                   % ( ) 0 char
    put                          % -/-
    .3 .1 moveto
    _ show
    1 0 T
    _ 0                          % ( ) 0
  }forall                        % 
}repeat
R R
% Now, render the numbers according to the numbering definitions
1 -1 S -.9 -.7 T
{{
  r
  %Check whether this is a comment
  dup 0 get 35 ne{               % line
    % Split at the first tab
    %TODO: Ust tab instead of space
    ( )search                    % (y x) tab number true
    p 3 2 roll                   % tab number (y x)
    cvx exec                     % tab number y x
    G
    x                            % tab number x y
    T                            % tab number
    .4 -.4 S
    0 0 moveto show              % tab
    % This pop can be eliminated in theory to save two characters,
    % but the operand stack will continue to grow
    p
    R
  }if
}loop}stopped
}exec
15 15
     #   #     


       #     ##
##   #   #     
    #     #    
   #    #      
       #       
      #    #   
    #     #    
    K#   #   ##
##  I  #       
    L          
    N          
    S#   #     
#i m n   figure(number), row, col
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
6 1 7
7 1 8
8 1 9
9 1 11
10 1 12
11 1 13
12 1 14
13 1 15
14 2 1
15 2 6
16 2 10
17 3 1
18 4 1
19 4 9
20 5 3
21 5 7
22 5 8
23 5 11
24 5 14
25 5 15
26 6 1
27 6 2
28 6 6
29 6 10
30 6 12
31 7 1
32 7 5
33 7 10
34 7 11
35 8 1
36 8 4
37 8 9
38 9 1
39 9 8
40 9 13
41 10 1
42 10 6
43 10 7
44 10 12
45 11 1
46 11 5
47 11 7
48 11 11
49 12 3
50 12 6
51 12 9
52 12 10
53 12 14
54 12 15
55 13 1
56 13 2
57 13 8
58 14 1
59 15 1
60 15 7
60 15 11

Answer 6

Postscript, non-combatant.

Inspired (yet again) by your related question on SO, I've made a reference version in Postscript using file-IO.

This program makes use of a ghostscript feature which may not be present in all Postscript interpreters. If ghostscript is invoked with the -- option, it passes command-line arguments to the postscript program in an array of strings named /ARGUMENTS. So you need to invoke the program like this gs -- xw-io.ps grid-file number-file.

%!

ARGUMENTS{}forall
/numfile exch (r) file def
/gridfile exch (r) file def

/q{0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath}def
/X<</FontType 3/FontBBox[0 0 1 1]/FontMatrix[1 0 0 1 0 0]
    /Encoding StandardEncoding
    /BuildChar{
        1 0 0 0 1 1 setcachedevice
        .001 setlinewidth
        q stroke
        dup 35 eq { pop
            q fill
        }{
            .3 .1 moveto
            .1 .1 scale
            /Times-Roman 8 selectfont
            (?)dup 0 4 3 roll put show
        }ifelse pop}
>>definefont pop /X 30 selectfont
40 700 moveto {
    gridfile 2{dup token pop exch}repeat pop pop
    {
        gridfile =string readline{
            dup length 0 ne{
                show currentpoint exch pop 30 sub 40 exch moveto
            }{clear exit}ifelse
        }{clear exit}ifelse
    }loop
    /Times-Roman 8 selectfont
    {
        40 700 moveto
        numfile =string readline{
            dup length 0 ne{
                dup 0 get 35 ne{
                    cvx exec
                    1 sub 30 mul 2 add exch
                    1 sub -30 mul 22 add rmoveto
                    (   )cvs show
                }{clear}ifelse
            }{clear}ifelse
        }{clear exit}ifelse
    }loop showpage
}exec

Answer 7

C, 375 chars

char b[99];g[999],*r=g,*f,i,j,w;main(n){
for(fscanf(f=fopen(gets(b),"r"),"%*d%d%*[\n]",&w);fgets(b,99,f);)
for(i=0;i<w;)*r++=-(b[i++]==35);
for(f=fopen(gets(b),"r");fgets(b,99,f);)
sscanf(b,"%d%d%d",&n,&j,&i)?g[j*w-w+i-1]=n:0;
for(f=g;f<=r;f+=w){for(i=w;i--;)printf(" ----");puts("");
if(f<r)for(j=3;j--;puts("|"))
for(i=0;i<w;printf(~n?n&&j>1?"|%-4d":"|    ":"|////",n))n=f[i++];}}

The two input filenames are entered on standard input, each on a separate line. The grid is rendered in ASCII on standard output. Yes, it's a lousy UI, but anything better cost characters. I took to invoking it like so:

printf "%s\n%s" grid.txt numbering.txt | ./crosswd-render > render.txt

The program should correctly handle things like commented lines in the numbering file.

Answer 8

Scala 463, output-format: html

object H extends App{val z=readLine.split("[ ]+")map(_.toInt-1)
val d="\t\t<td width='50' height='50'"
println("<html><table border='1'><tr>")
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(d+"valign='top'>"+c+"</td>")}
else println(d+{if(b(y)(x)!=' ')"bgcolor='#0'>"else">&nbsp;"}+"</td>")}
println("\t</tr>\n\t<tr>")}
println("</table></html>")
}

Sample output