# Crossword Compulsions!

Chris, a cryptic crosswords addict, has a set algorithm for the order in which he solves them.

We will use the above image as a guide.

1. Chris always starts off with the first across clue, in this case 1 Across. Chris is a capable crossword enthusiast, so it is assumed that he will always know the answer to the clue he is working on.
2. Once Chris completes a clue, he will check for all clues adjoining those he has completed (in the first case, 1 Down, 2 Down and 3 Down) and then complete the clue with the lowest number. If there are no adjoining clues, he would go to step 3.
3. If the clue is such that the next number (as described in Step 3) has both an across clue and a down clue, he will complete the across clue first (100% certainty, this borders on OCD!)
4. If there are no adjoining clues, he will go to the next available clue that's next in number (across or down)
5. Repeat from Step 2 until all clues are completed.

And this is where it comes down to you, dear coders. You have been tasked to create code that can, on being provided with a crossword template, provide output describing the order of clues based on Chris's algorithm for solving it.

The code will accept input of a crossword puzzle template, in the form of a . representing a white square and a # representing a black square.

Example:

.....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....


Input can be through: a) a file read of the representation of the crossword, or b) by line input of each line of the crossword, followed by \n, with a second \n indicating EOF.

And then it will determine the method by which Chris would solve it according to the above algorithm he has described.

Output must be in the format of a series of comma separated instructions in the form of n(A|D), where n is the clue number followed by A for across or D for down.

So in the example above (both from the image, and the example template, which are the one and the same), the output would be:

1A,1D,2D,3D,9A,10A,4D,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

Shortest code wins...

Testing

You must provide with your submission the code, a byte count, as well as one of the four test cases represented in the . and # format, as well as the output generated from this input. There are four test cases, the three below as well as the above example template.

Example test cases:

Test Case 1

.....#
.#.#.#
...#..
.#.#.#
.....#
##.#..


Output: 1A,1D,2D,3D,4A,5A,6A,7A

Test Case 2

.....#..
.#.##..#
.#....#.
...##.#.
.####...
......##


Output: 1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

Test Case 3

.........#
#.#.#.#.#.
....#...#.
#...#.#.#.
..###.#.#.
.#....#...
.#####...#
.....###..


Output: 1A,2D,3D,4D,5D,7A,8A,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

Test Case 4

.....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....


Output: 1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

Good luck!

• Just to be sure: In your example image, which number is the fifth clue to be compulsively filled? (after 1H, 1V, 2V, 3V) – Dr. belisarius Feb 24 '14 at 1:15
• @belisarius The image corresponds to the fourth test case. So the fifth clue to be filled would be 9 Across, or as you would put it, 9H :) As The only adjoining clues after the fourth clue is completed are 9 and 10 Across, Chris will be compelled to fill in the lowest clue first... – WallyWest Feb 24 '14 at 1:25
• Are the bytes considered only on the basis of the code that produces the correct output. IOW, are you penalized on includes, C# namespace + class + Main, and the like in order to have it compilable or is it reasonable to assume that if I write it in C#, or similar, that minimal amount of code would be required? – ChiefTwoPencils Feb 24 '14 at 8:13
• @BobbyDigital Well, this is code-golf... I would hope that if you did plan on writing it in C# you would try not to use too many externals... You'd have to count them I'm afraid... – WallyWest Feb 24 '14 at 9:35
• @WallyWest I thinkg your third example is omitting a 17A at the end. Also the fourth the 4A right after 4D. – Howard Feb 24 '14 at 11:28

### GolfScript, 154 characters

:^,,{.^=46<{;-1}*)}%[.^n?)/zip[0]*]{1,%{,1>},}%:H"AD"1/]zip{~{1$0=H{{0=}/}%.&$?)\+[\]}+/}%(2/\{0=)[\~\]}$+[]{1${1=1$&},.!{;1$1<}*1<:F~~@|@F-\1\$}do;;]','*


Input has to be provided on STDIN. The examples yield the following results (check online):

1A,1D,2D,3D,4A,5A,6A,7A

1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

1A,2D,3D,4D,5D,7A,8D,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

• +1 Remarkably succinct. How does it work? – DavidC Feb 24 '14 at 12:12
• Wow, thanks for making it clear that I should not even waste my time. Clearly going to have to get on top of a more appropriate language. votes++ – ChiefTwoPencils Feb 24 '14 at 19:04
• @BobbyDigital I meant no disrespect. C# is a very verbose language... it's probably not the best for code golf. Code-bowling or for popularity contests on here... but Code Golf is a whole new kettle of fish. – WallyWest Feb 25 '14 at 0:46
• +1 here too... Probably one of the longer GolfScript entries I've seen... Nicely done. – WallyWest Feb 25 '14 at 1:09
• @BobbyDigital: The task itself is quite interesting. Give it a try in a language you are familiar with. I think you'll enjoy the puzzle as much as I did - investigate all the different approaches to tackle the puzzle. It is fun by itself even if you don't reach a character count as low as this answer. – Howard Feb 25 '14 at 8:22

# Mathematica 806 477

(There appears to be a glitch in the ordering of the solution steps. I am looking into this.)

## Golfed

The function q finds the order of the crossword solutions.

i = Dimensions; v = MemberQ; u = Position; y = ToString; k = Select;
q@t_ :=
(g@p_ := Characters@StringSplit[p, "\n"];
w = g@t;
a[{r_, c_}, z_] := (c != i[z][[2]]) \[And]
v[u[z, "."], {r, c + 1}] \[And] ((c == 1) \[Or]
v[u[z, "#"], {r, c - 1}]);
b@z_ := k[u[z, "."], a[#, z] &];
d[{r_, c_}, z_] := (r != i[z][[2]]) \[And]
v[u[z, "."], {r + 1, c}] \[And] ((r == 1) \[Or]
v[u[z, "#"], {r - 1, c}]);
e@z_ := k[u[z, "."], d[#, z] &];
Cases[Flatten[{
If[v[b[w], #[[1]]], y[#[[2]]] <> "A"],
If[v[e[w], #[[1]]], y[#[[2]]] <> "D"]} & /@ (MapIndexed[List,
b[w] \[Union] e[w]] /. {{r_, c_}, {i_}} :> ({r, c} -> i))],
Except[Null]])


## Ungolfed

q[t7_]:=
Module[{d,acrossSquareQ,acrossSquares,downSquareQ,downSquares,m,numberedCells},
(*w=g[t7];*)
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[t7];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Cases[Flatten[{
If[MemberQ[acrossSquares[w],#[[1]]],ToString[#[[2]]]<>"A"],
If[MemberQ[downSquares[w],#[[1]]],ToString[#[[2]]]<>"D"]}&/@m],Except[Null]]]


board displays the crossword puzzle. The code is not included in the character count. Several sub functions from q are borrowed here.

board[p_]:=
Module[{q,g,w,downSquareQ,downSquares,acrossSquareQ,acrossSquares,numberedCells,m},
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[p];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Grid[ReplacePart[w,m],Dividers->All,Background->{None,None,(#-> Black)&/@Position[w,"#"]}]]


## TestCases

1

t1=".....#
.#.#.#
...#..
.#.#.#
.....#
##.#..";
board[t1]
q[t1]


{"1A", "1D", "2D", "3D", "4A", "5A", "6A", "7A"}

2

t2=".....#..
.#.##..#
.#....#.
...##.#.
.####...
......##";

board[t2]
q[t2]


{"1A", "1D", "2D", "3A", "3D", "4A", "4D", "5A", "6D", "7A", "8A", "9A"}

3

t3=".........#
#.#.#.#.#.
....#...#.
#...#.#.#.
..###.#.#.
.#....#...
.#####...#
.....###..";

board[t3]

q[t3]


{"1A", "2D", "3D", "4D", "5D", "6D", "7A", "8D", "9A", "10A", "11A", "11D", "12A", "13A", "14D", "15A", "16A", "17A"}

4

t4=".....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....";

board[t4]

q[t4]


{"1A", "1D", "2D", "3D", "4A", "4D", "5D", "6D", "7D", "8D", "9A", "10A", "11A", "12A", "13A", "14D", "15A", "15D", "16A", "17A", "18D", "19D", "20A", "21D", "22D", "23A", "24A", "25D", "26D", "27A", "28A", "29A", "30A", "31A"}

• I think you have an issue with your code. E.g. in example 2 the 3A should no be right after the 2D because there is no clue yet. Also the other solutions show this effect. – Howard Feb 24 '14 at 11:39
• Howard, I am not understanding your point. From "4. If there are no adjoining clues, he will go to the next available clue that's next in number (across or down)", it appears that 3A may be after 2D. – DavidC Feb 24 '14 at 12:18
• But e.g. 5A has a clue and should therefore be favoured over 3A. – Howard Feb 24 '14 at 12:32
• You've defined a shorthand for ToString` twice – Dr. belisarius Feb 24 '14 at 14:33
• Howard, Now I understand your point. Thanks. Will correct later. – DavidC Feb 24 '14 at 15:19