Crossword Compulsions!

Question

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!

Answer 1

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

Answer 2

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"}