Überprüfung des Kreuzworträtsels

8

Überprüfen Sie ein vorgeschlagenes Kreuzworträtsel.

Einträge sollten vollständige Programme sein, die einfach ein vorgeschlagenes Raster testen, um festzustellen, ob es eine Reihe von Bedingungen erfüllt, um Kreuzworträtsellöser glücklich zu machen.

Eingang

Die Eingabe ist der Name einer Datei, die das Kreuzworträtsel darstellt. Der Eingabedateiname kann als Argument, für die Standardeingabe oder auf andere herkömmliche Weise als durch Hardcodierung übergeben werden.

Rasterdateiformat: Die erste Zeile besteht aus zwei durch Leerzeichen getrennten Ganzzahlkonstanten M und N. Nach dieser Zeile befinden sich M Zeilen, die jeweils aus N Zeichen (plus einer neuen Zeile) bestehen [#A-Z ]. Diese Zeichen werden so interpretiert, dass sie '#' ein blockiertes Quadrat, ' 'ein offenes Quadrat im Puzzle ohne bekannten Inhalt und einen Buchstaben ein offenes Quadrat anzeigen, das diesen Buchstaben enthält.

Ausgabe

Das Programm sollte keine Ausgabe in gültigen Gittern erzeugen und mit normalem Beendigungszustand beenden. Wenn das vorgeschlagene Raster ausfällt, sollte das Programm eine Diagnosefehlermeldung ausgeben und mit einem abnormalen Beendigungsstatus (dh nicht 0 unter Unix) beenden, wenn dies von Ihrer Ausführungsumgebung unterstützt wird. Die Fehlermeldung sollte sowohl angeben, welche Bedingung für die Gültigkeit verletzt wurde, als auch die Position des fehlerhaften Quadrats. Es steht Ihnen frei, die Mittel zur Übermittlung dieser Fakten zu wählen.

Bedingungen für die Gültigkeit

Gültige Gitter haben keine Antworten (quer oder runter), die nur 1 Zeichen lang sind (zusätzliche Gutschrift, um die Mindestlänge zu einem Eingabeparameter zu machen) und weisen die übliche Symmetrie auf. Die übliche Symmetrie bedeutet, dass das Kreuzworträtsel danach gleich bleibt (drei äquivalente Beschreibungen derselben Operation):

  • Reflexion durch das eigene Zentrum
  • Reflexion sowohl vertikal als auch horizontal
  • 180 Grad Drehung

Testeingabe und erwartete Ausgabe

Geht vorbei:

5   5
#  ##
#    
  #  
    #
##  #

Schlägt bei kurzer Antwort fehl:

5   5
## ##
#    
  #  
    #
## ##

Symmetrie scheitert:

5   5
#  ##
#    
  #  
#   #
##  #

Beiseite

Dies ist die zweite von mehreren Herausforderungen im Zusammenhang mit Kreuzworträtseln. Ich plane, durchgehend eine konsistente Reihe von Dateiformaten zu verwenden und dabei eine seriöse Suite von Kreuzworträtsel-bezogenen Dienstprogrammen aufzubauen. Zum Beispiel erfordert ein nachfolgendes Puzzle das Drucken einer ASCII-Version des Kreuzworträtsels basierend auf der Eingabe und Ausgabe dieses Puzzles.

Frühere Herausforderungen in dieser Reihe:

dmckee --- Ex-Moderator Kätzchen
quelle
1
Gilt die Symmetrieanforderung auch für den bekannten Inhalt des Rasters oder nur für die Struktur (# oder nicht #)?
JB
Nur zur Struktur von blockierten und im Spiel befindlichen Feldern.
dmckee --- Ex-Moderator Kätzchen
Oh, dieser hatte schon ein Kopfgeld. Schade. Trotzdem denke ich, dass zwei Antworten ein paar sind.
Joey
Mittelsymmetrie und 180 ° -Rotation sind dasselbe - nicht wahr? Aber ich sehe weder vertikale noch horizontale Symmetrie. Aber 90 ° -Drehung.
Benutzer unbekannt

Antworten:

4

Ruby - 215 207

t,*d=$<.map &:chop;n,d,e=t.size+1,(d*S=?#).gsub(/[^#]/,W=" "),->c,i{puts [c,i/n+1,i%n+1]*" ";exit 1}
0.upto(d.size-1){|i|d[i]==d[-i-1]||e[?R,i];d[i]==W&&(d[i-1]!=W&&d[i+1]!=W||d[i-n]!=W&&d[i+n]!=W)&&e[?L,i]}

Ungolfed:

h, *g = $<.map &:chop
w = h.size+1
g = (g*?#).gsub(/[^#]/," ")
error = ->c,i{ puts [c,i/w+1,i% w+1]*" "; exit 1 }
0.upto(size-1) { |i|
        error[?R, i] if g[i] != g[-i-1]
        error[?L,i] if g[i]==" " && (g[i-1]!=" " && g[i+1]!=" " || g[i-w]!=" " && g[i+w] != " ")
}

.

h, *g = $<.map &:chop

Dadurch wird im Grunde das letzte Zeichen (Zeilenumbruch) jeder Eingabezeile entfernt, indem die chopMethode für sie aufgerufen und ein Array der Ergebnisse zurückgegeben wird.

hnimmt das erste Element dieses Arrays und *gnimmt den Rest. Am Ende haben wir also die erste Zeile hund die Kreuzworträtselzeilen g.

g = (g*?#).gsub(/[^#]/," ")

g*?#verbindet ( *) das Array gmit dem "#"( ?#ist ein Zeichenliteral). Dies ist das gleiche wie g.*("#")oder g.join("#"). Dann wird jedes Nicht #durch ein Leerzeichen ersetzt.

Für die Symmetrieprüfung müssen wir nur prüfen, ob das Zeichen an jedem Index dem Zeichen am gegenüberliegenden Index in der Zeichenfolge entspricht:

0.upto(g.size-1) { |i| if g[i] != g[g.size - i - 1]; error() }

In Ruby können wir Zeichenfolgen vom Ende mit negativen Indizes indizieren (beginnend mit -1statt 0), so dass dies g[-i-1]das Gegenteil von g[i]in der Zeichenfolge ist. Dies spart ein paar Zeichen:

0.upto(g.size-1) { |i| if g[i] != g[-i-1]; error() }

Wir können a ;mit einer bedingten Anweisung speichern :

0.upto(g.size-1) { |i| error() if g[i] != g[-i-1] }

In der Golfversion können wir noch ein paar Zeichen sparen:

0.upto(g.size-1){|i|g[i]==g[-i-1]||error()}

In einer früheren Version habe ich die Rekursion zum Durchlaufen der Zeichenfolge verwendet:

(f=->i{g[i]&&f[i+1]&&g[i]!=g[-i-1]&&error()})[0]

Ein nicht gebundener Zugriff auf ggibt null zurück. Sobald er g[i]zurückgegeben wird nil, wird die Iteration gestoppt.

Ausgabeformat:

{ L | R } line-number column-number

L für Längenfehler und R für Rotationsfehler ( L 1 2bedeutet also Längenfehler in Zeile 1, Spalte 2)

Arnaud Le Blanc
quelle
Möchten Sie denjenigen von uns, die kein Rubin sprechen, etwas erklären? Ich kann sehen, wie Sie Nicht-Schwarze von In-Play-Quadraten entfernt haben und wie die Überprüfung der Antwortlänge funktioniert (nett, übrigens), aber ich bekomme die Symmetrieprüfung nicht ganz.
dmckee --- Ex-Moderator Kätzchen
Ich sehe hier ein Problem, wie die Breite des Gitters bestimmt wird - indem man die Länge der 1. Zeile nimmt. Das ist falsch, es funktioniert nur in dem Beispiel, in dem diese Zeile "5 - 5" ist (drei Leerzeichen in der Mitte). Wenn es "5 5" war, wird es nicht funktionieren!
Nas Banov
Ich denke auch, dass es ein Problem mit "Veritcal Wrap-Around" gibt, wenn man über die erste Reihe geht und eine Reihe nach unten (+ n) und eine Reihe nach oben (-n) schaut - letztere wird in der letzten Reihe aussehen und möglicherweise irrtümlich Abholraum von dort!
Nas Banov
Nun, Sie sind richtig für die Breite des Gitters; Ich nahm an, dass in der ersten Zeile die zweite Zahl immer am Ende der Zeile ausgerichtet ist.
Arnaud Le Blanc
1

Referenzimplementierung

c99

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void readgrid(FILE *f, int m, int n, char grid[m][n]){
  int i = 0;
  int j = 0;
  int c = 0;
  while ( (c = fgetc(f)) != EOF) {
    if (c == '\n') {
      if (j != n) fprintf(stderr,"Short input line (%d)\n",i);
      i++;
      j=0;
    } else {
      grid[i][j++] = c;
    }
  }
}

int isSymmetric(int m, int n, char g[m][n]){
  for (int i=0; i<m; ++i)
    for (int j=0; j<n; ++j)
      if ( (g[i][j]=='#') != (g[m-i-1][n-j-1]=='#') )
    return j*m+i;
  return -1;
}

int isLongEnough(int m, int n, char g[m][n], int min){
  /* Check the rows */
  for (int i=0; i<m; ++i) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int j=0; j<n; ++j) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == j-1) && (j-lb <= min+1) ) return lo*m+i;
    lb=j;
      } else {
    /* In-play square */
    lo=j;
      }
    }
  }

  /* Check the columns */
  for (int j=0; j<n; ++j) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int i=0; i<m; ++i) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == i-1) && (i-lb <= min+1) ) return lo*m+i;
    lb=i;
      } else {
    /* In-play square */
    lo=i;
      }
    }
  }

  /* Passed */
  return -1;
}

int main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;
  int min=1;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the minium
         answer length */
    if ( (min=atoi(argv[2]))<1 ) {
      fprintf(stderr,"%s: Minimum length '%s' too short. Exiting.",
          argv[0],argv[2]);
      return 2;
    }
    /* FALLTHROUGH */
  case 2: /* exactly one argument */
    infname = argv[1];
    if (!(inf = fopen(infname,"r"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[1]);
      return 1;
    };
    break;
  default:
    printf("%s: Verify crossword grid.\n\t%s <grid file> [<minimum length>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0,e=-1;
  char lbuf[81];
  fgets(lbuf,81,inf);
  sscanf(lbuf,"%d %d",&m,&n);

  /* Intialize the grid */
  char grid[m][n];
  for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
      grid[i][j]='#';
    }
  }

  readgrid(inf,m,n,grid);

  if ((e=isSymmetric(m,n,grid))>=0) {
    fprintf(stderr,"Symmetry violation at %d,%d.\n",e/m+1,e%m+1);
    return 4;
  } else if ((e=isLongEnough(m,n,grid,min))>=0) {
    fprintf(stderr,"Short answer at %d,%d.\n",e/m+1,e%m+1);
    return 8;
  }
  return 0;
}
dmckee --- Ex-Moderator Kätzchen
quelle
1

C, 278 Zeichen

char*f,g[999],*r=g;i,j,h,w;main(e){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(g+h*w,99,f);++h);
for(;j++<h;)for(i=0;i++<w;++r)if(e=*r==35^g[g+w*h-r-1]==35?83:
*r==35||i>1&r[-1]!=35|i<w&r[1]!=35&&j>1&r[-w]!=35|j<h&r[w]!=35?0:76)
exit(printf("%d%c%d\n",j,e,i));exit(0);}

Wie zu erwarten, wurden die Fehlermeldungen selbst Golf gespielt. Sie haben folgende Form:

11L8 - zeigt einen Längenfehler in Zeile 11, Spalte 8 an

4S10 - zeigt einen Symmetriefehler in Zeile 4, Spalte 10 an

Brot-Box
quelle
1

APL (115)

{∨/,k←⍵≠⌽⊖⍵:'⍉',(,k×⍳⍴k)~⊂2/0⋄×⍴d←(,⊃,/(g(⍉g←⍳⍴⍵))×{k↑1⌽1⊖0 1 0⍷¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵}¨⍵(⍉⍵))~⊂2/0:'∘',d}d↑↑{'#'≠⍞}¨⍳⊃d←⎕

Wenn das Gitter nicht symmetrisch ist, wird es gefolgt von den Koordinaten ausgegeben, dh für das angegebene Beispiel

⍉ 2 5 4 1
Wenn das Raster kurze Antworten hat, werden die Ausgaben gefolgt von den Koordinaten ausgegeben, dh für das angegebene Beispiel
∘ 1 2 5 2

Erläuterung:

  • d↑↑{'#'≠⍞}¨⍳⊃d←⎕: Lesen Sie die erste Zeile als Liste von Zahlen und speichern Sie sie d, lesen Sie dann so viele Zeilen wie die erste Zahl und formen Sie sie als Matrix mit Größe um d. 'Geschlossene' Quadrate werden als 0 und 'offene' Quadrate als 1 gespeichert.
  • ∨/,k←⍵≠⌽⊖⍵: an kOrten lagern, an denen das Gitter asymmetrisch ist. Wenn es so einen Ort gibt ...
  • '⍉',(,k×⍳⍴k)~⊂2/0: Geben Sie ein ⍉ gefolgt von den fehlerhaften Koordinaten aus
  • : Andernfalls...
  • ~⊂2/0: Entfernen Sie die Nullkoordinaten aus der folgenden Liste:
  • ¨⍵(⍉⍵): sowohl für das Gitter als auch für seine Transponierung ...
  • ¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵: umgeben Sie das Gitter mit Nullen (dh geschlossenen Quadraten)
  • 0 1 0⍷: sehen, wo es ein 'offenes' Quadrat enthält, das von zwei 'geschlossenen' Quadraten umschlossen ist (= zu kurz)
  • k↑1⌽1⊖: Entfernen Sie den Ring der zusätzlichen Nullen erneut
  • ,⊃,/(g(⍉g←⍳⍴⍵))×: Mit Koordinaten und transponierten Koordinaten multiplizieren und zusammenfügen, um eine Liste der störenden Koordinaten (und vieler Nullen, die wir entfernen) zu bilden.
  • ×⍴d←: Speichern Sie die beleidigenden Koordinaten in d, und wenn es welche gibt ...
  • :'∘',d: a ∘ gefolgt von den Koordinaten ausgeben.
Marinus
quelle