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

Postscript 905 797 677 675 629 608 330 320 308

{G N}/Times-Roman .3 2 22 1 30/.{<920>dup 1 4 3 roll put cvx 
exec}def/${//. 73 .}def[/R{99<a51f3e7d75>$}/G{<1fab75>$ 
R(uN)${0 R{1(X)$ 0 1 -1 5 4 roll 35 eq{4<1980>$}if<81>$ 
1 add}(I)$(u)$ 0 -1<ad>$}<834d>$}/X{{exit}if}/N{-.9
.7<ad>${<1fab70>$ X}loop{{(>nk)$(  )<31a0>$}<a3>$
X}loop}>><0d38388b369bad8e3f>$

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

The new revision uses these two procedures to execute binary-encoded system names from strings.

/.{
    <920>  % two-byte binary-encoded name template with 0x92 prefix
    dup 1 4 3 roll put  % insert number into string
    cvx exec  % and execute it
}def
/${
    //.   %the /. procedure body defined above
    73 .  %"forall" (by code number)
}def

Indented and (somewhat) commented.

/Times-Roman .3 2 22 1 30
/.{<920>dup 1 4 3 roll put cvx exec}def/${//. 73 .}def
[
/R{99<a51f3e7d75>$}    %currentfile 99 string readline pop 
/G{<1fab75>$ %currentfile token pop 
    R (uN)$ %<754e>$ %pop gsave
    {   
        0 R { 
            1 (X)$ %index
            0 1 -1 5 4 roll
            35 eq{ 
                4<1980>$ %copy rectfill
            }if 
            <81>$ %rectstroke
            1 add 
        }(I)$
        (u)$ % 73 . %forall pop 
        0 -1<ad>$ %translate
    }<834d>$ %repeat grestore
}
/X{{exit}if}
/N{
    -.9 .7<ad>$ %translate
    %{ currentfile token not {exit} if } loop
    {<1fab70>$
        X %{exit}if
    }loop
    {   
        %dup type/integertype ne{exit}if
        {
            (>nk)$ %<3e6e6b>$ %exch neg moveto
            (  )<31a0>$ %cvs show
        }<a3>$ %stopped
        X %{exit}if
    }loop
}
>>
<0d38388b369bad8e>$
%begin dup dup scale div setlinewidth translate selectfont
{G N}exec

Data files.

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

It should look okay from a printer, but on-screen it needs a little help. This 19-char procedure and 9 chars to invoke it on all user-space points, helps make evenly-spaced lines look more even. So 308 + 19 + 9 = 337, used to generate this image.

/F{<ac893e893e5f>$} % transform round exch round exch itransform

Postscript 608

This earlier version (from revision 8) uses a completely different approach, reusing the main-line code as a "lexicon" from which longer tokens can be indexed using strings.

<<-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>*

It was written using this commented version which illustrates the encoding of the lexicon. The first token 30 is commented space therefore ( )* is a synonym for 30. Not very beneficial for 30, but for longer tokens this is(was) a big win (until deeper encoding possibilities are(were) discovered).

<<-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>*

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

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 6

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

Answer 7

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 8

Postscript, non-combatant.

Inspired (yet again) by your related question on SO, I've made a reference version in Postscript using file-IO. It also creates a derived fixed-width font so the grid data is simply passed to show. is an empty box and # is a filled box. Any other ascii character is drawn as a small Times-Roman glyph surrounded by a box.

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