Crossword Compulsions!

Question

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

enter image description here

We will use the above image as a guide.

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.
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.
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!)
If there are no adjoining clues, he will go to the next available clue that's next in number (across or down)
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, Commented Feb 24, 2014 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... — Eliseo D'Annunzio, Commented Feb 24, 2014 at 1:25
@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... — Eliseo D'Annunzio, Commented Feb 24, 2014 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, Commented Feb 24, 2014 at 11:28
Hey @Jonah, to be honest, given this question is now some seven years old, I haven’t looked at it for some time... if there is a mistake, chances are I missed something in the proofing of this original post... possibly due to fatigue as I posted this somewhat late at night... I’ll have a look shortly... thanks for bringing this to my attention... — Eliseo D'Annunzio, Commented Feb 13, 2021 at 3:16

Community · Accepted Answer · 2020-06-17 09:04:33Z

6

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 24, 2014 at 11:33

Howard

23.6k2 gold badges44 silver badges83 bronze badges

\$\begingroup\$ +1 Remarkably succinct. How does it work? \$\endgroup\$
– DavidC
Commented Feb 24, 2014 at 12:12
\$\begingroup\$ 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++ \$\endgroup\$
– ChiefTwoPencils
Commented Feb 24, 2014 at 19:04
\$\begingroup\$ @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. \$\endgroup\$
– Eliseo D'Annunzio
Commented Feb 25, 2014 at 0:46
\$\begingroup\$ +1 here too... Probably one of the longer GolfScript entries I've seen... Nicely done. \$\endgroup\$
– Eliseo D'Annunzio
Commented Feb 25, 2014 at 1:09
1

\$\begingroup\$ @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. \$\endgroup\$
– Howard
Commented Feb 25, 2014 at 8:22

| Show 1 more comment

DavidC · Accepted Answer · 2014-02-24 15:19:43Z

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, Commented Feb 24, 2014 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, Commented Feb 24, 2014 at 12:18
But e.g. 5A has a clue and should therefore be favoured over 3A. — Howard, Commented Feb 24, 2014 at 12:32
Howard, Now I understand your point. Thanks. Will correct later. — DavidC, Commented Feb 24, 2014 at 15:19

Stack Exchange Network

Crossword Compulsions!

2 Answers 2

GolfScript, 154 characters

Mathematica 806 477

Golfed

Ungolfed

TestCases

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
crossword
or ask your own question.

Hot Network Questions

Crossword Compulsions!

2 Answers 2

GolfScript, 154 characters

Mathematica 806 477

Golfed

Ungolfed

TestCases

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfcrossword or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
crossword
or ask your own question.