Compulsions de mots croisés!

14

Chris, un addict cryptique des mots croisés, a un algorithme défini pour l'ordre dans lequel il les résout.

entrez la description de l'image ici

Nous utiliserons l'image ci-dessus comme guide.

  1. Chris commence toujours par le premier indice transversal, dans ce cas 1 Across. Chris est un passionné de mots croisés, donc on suppose qu'il connaîtra toujours la réponse à l'indice sur lequel il travaille.
  2. Une fois que Chris aura terminé un indice, il vérifiera tous les indices adjacents à ceux qu'il a complétés (dans le premier cas, 1 Down, 2 Down et 3 Down) puis complétera l'indice avec le nombre le plus bas. S'il n'y a pas d'indices adjacents, il passerait à l'étape 3.
  3. Si l'indice est tel que le numéro suivant (comme décrit à l'étape 3) a à la fois un indice transversal et un indice négatif, il remplira d'abord l'indice transversal (100% de certitude, cela frise le TOC!)
  4. S'il n'y a pas d'indices adjacents, il ira au prochain indice disponible qui est le suivant en nombre (en travers ou en bas)
  5. Répétez à partir de l'étape 2 jusqu'à ce que tous les indices soient terminés.

Et c'est là que cela vous revient, chers codeurs. Vous avez été chargé de créer du code qui peut, après avoir été fourni avec un modèle de mots croisés, fournir une sortie décrivant l'ordre des indices basé sur l'algorithme de Chris pour le résoudre.

Le code acceptera la saisie d'un modèle de mots croisés, sous la forme d'un .représentant un carré blanc et d'un #représentant un carré noir.

Exemple :

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

L'entrée peut se faire par: a) une lecture de fichier de la représentation du mot croisé, ou b) par l'entrée ligne de chaque ligne du mot croisé, suivie par \n, avec une seconde \nindiquant EOF.

Et puis il déterminera la méthode par laquelle Chris le résoudrait selon l'algorithme ci-dessus qu'il a décrit.

La sortie doit être au format d'une série d'instructions séparées par des virgules sous la forme de n(A|D), où nest le nombre d'indices suivi de Apour à travers ou Dà bas.

Ainsi, dans l'exemple ci-dessus (à la fois de l'image et de l'exemple de modèle, qui sont les mêmes), la sortie serait:

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

Le code le plus court gagne ...

Essai

Vous devez fournir avec votre soumission le code, un nombre d'octets, ainsi que l'un des quatre cas de test représentés dans le format .et #, ainsi que la sortie générée à partir de cette entrée. Il existe quatre cas de test, les trois ci-dessous ainsi que l'exemple de modèle ci-dessus.

Exemples de cas de test:

Cas de test 1

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

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

Cas de test 2

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

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

Cas de test 3

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

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

Cas de test 4

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

Production: 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

Bonne chance!

WallyWest
la source
Juste pour être sûr: dans votre exemple d'image, quel numéro est le cinquième indice à remplir compulsivement? (après 1H, 1V, 2V, 3V)
Dr belisarius
@belisarius L'image correspond au quatrième cas de test. Donc, le cinquième indice à remplir serait 9 Across, ou comme vous le dites, 9H :) Comme les seuls indices adjacents après que le quatrième indice est terminé sont 9 et 10 Across, Chris sera obligé de remplir l'indice le plus bas en premier ...
WallyWest
Les octets ne sont-ils considérés que sur la base du code qui produit la sortie correcte. IOW, êtes-vous pénalisé sur les inclusions, l'espace de noms C # + classe + Main, etc. pour le rendre compilable ou est-il raisonnable de supposer que si je l'écris en C #, ou similaire, une quantité minimale de code serait requise?
ChiefTwoPencils
1
@BobbyDigital Eh bien, c'est du code-golf ... J'espère que si vous prévoyez de l'écrire en C #, vous essayerez de ne pas utiliser trop d'externes ... Vous devrez les compter, je le crains .. .
Wally West
1
@WallyWest Je pense que votre troisième exemple omet un 17Aà la fin. Aussi le quatrième 4Ajuste après 4D.
Howard

Réponses:

5

GolfScript, 154 caractères

:^,,{.^=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;;]','*

L'entrée doit être fournie sur STDIN. Les exemples donnent les résultats suivants (vérifiez en ligne ):

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
Howard
la source
+1 Remarquablement succinct. Comment ça marche?
DavidC
Wow, merci d'avoir dit clairement que je ne devrais même pas perdre mon temps. Il va clairement falloir se familiariser avec une langue plus appropriée. votes++
ChiefTwoPencils
@BobbyDigital, je ne voulais pas manquer de respect. C # est un langage très verbeux ... ce n'est probablement pas le meilleur pour le golf de code. Code-bowling ou concours de popularité ici ... mais Code Golf est une toute nouvelle marmite de poisson.
WallyWest
+1 ici aussi ... Probablement l'une des entrées GolfScript les plus longues que j'ai vues ... Bien joué.
WallyWest
1
@BobbyDigital: La tâche elle-même est assez intéressante. Essayez-le dans une langue que vous connaissez. Je pense que vous apprécierez le puzzle autant que moi - explorez toutes les différentes approches pour résoudre le puzzle. C'est amusant en soi même si vous n'atteignez pas un nombre de caractères aussi bas que cette réponse.
Howard
3

Mathematica 806 477

(Il semble y avoir un problème dans l'ordre des étapes de la solution. J'examine la question.)

Golfé

La fonction qtrouve l'ordre des solutions de mots croisés.

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]])

Non golfé

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

boardaffiche le jeu de mots croisés. Le code n'est pas inclus dans le nombre de caractères. Plusieurs sous-fonctions de qsont empruntées ici.

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]

t1

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


2

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

board[t2]
q[t2]

t2

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


3

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

board[t3]

q[t3]

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]

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

DavidC
la source
Je pense que vous avez un problème avec votre code. Par exemple, dans l'exemple 2, le 3Ane devrait pas être juste après le 2Dcar il n'y a pas encore d'indice. Les autres solutions montrent également cet effet.
Howard
Howard, je ne comprends pas votre point. De "4. S'il n'y a pas d'indices adjacents, il ira au prochain indice disponible qui est le suivant en nombre (en travers ou en bas)", il semble que 3A puisse être après 2D.
DavidC
Mais par exemple 5Aa un indice et devrait donc être privilégié 3A.
Howard
Vous avez défini un raccourci pour ToStringdeux fois
Dr. belisarius
Howard, maintenant je comprends votre point. Merci. Corrigera plus tard.
DavidC