Verificación de cuadrícula de crucigramas

8

Validar una cuadrícula de crucigramas propuesta.

Las entradas deben ser programas completos que simplemente prueben una cuadrícula propuesta para determinar si cumple con un conjunto de condiciones para hacer felices a los solucionadores de crucigramas.

Entrada

La entrada será el nombre de un archivo que representa la cuadrícula de crucigramas. El nombre de archivo de entrada se puede pasar como argumento, en la entrada estándar o por otros medios convencionales que no sean la codificación fija.

Formato de archivo de cuadrícula: la primera línea consta de dos constantes enteras separadas por espacios en blanco M y N. A continuación de esa línea hay M líneas que consisten en N caracteres (más una nueva línea) seleccionados entre [#A-Z ]. Estos caracteres se interpretan de tal manera que '#' indican un cuadrado bloqueado, ' 'un cuadrado abierto en el rompecabezas sin contenido conocido y cualquier letra un cuadrado abierto que contenga esa letra.

Salida

El programa no debe producir ninguna salida en cuadrículas válidas y salir con un estado de terminación normal. Si la cuadrícula propuesta falla, el programa debería generar un mensaje de error de diagnóstico y salir con un estado de terminación anormal (es decir, no 0 en Unix) si su entorno de ejecución lo admite. El mensaje de error debe indicar qué condición de validez se viola y la ubicación del cuadrado infractor; Usted es libre de elegir los medios para transmitir estos hechos.

Condiciones de validez

Las cuadrículas válidas no tendrán respuestas (cruzadas o hacia abajo) que tengan solo 1 carácter (crédito adicional por hacer que la longitud mínima sea un parámetro de entrada) y exhibirán la simetría habitual. La simetría habitual significa que el crucigrama permanece igual después (tres descripciones equivalentes de la misma operación):

  • reflexión a través de su propio centro
  • reflejo tanto vertical como horizontalmente
  • Rotación de 180 grados

Prueba de entrada y salida esperada

Pases

5   5
#  ##
#    
  #  
    #
##  #

Falla en la respuesta corta:

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

Falla en la simetría:

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

Aparte

Este es el segundo de varios desafíos relacionados con crucigramas. Planeo usar un conjunto consistente de formatos de archivo en todo momento y construir un conjunto respetable de utilidades relacionadas con crucigramas en el proceso. Por ejemplo, un rompecabezas posterior requerirá imprimir una versión ASCII del crucigrama basado en la entrada y salida de este rompecabezas.

Retos anteriores en esta serie:

dmckee --- gatito ex moderador
fuente
1
¿El requisito de simetría también se aplica a los contenidos conocidos de la cuadrícula, o solo a la estructura (# o no #)?
JB
Solo a la estructura de casillas bloqueadas y en juego.
dmckee --- gatito ex moderador
Oh, este ya tenía una recompensa. Gorrón. Aún así, creo que dos respuestas son un poco pocas.
Joey
La simetría central y la rotación de 180 ° son lo mismo, ¿no es así? Pero no veo simetría vertical ni horizontal. Pero 90 ° de rotación.
usuario desconocido

Respuestas:

4

Rubí - 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]}

Sin golf:

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

Básicamente, esto elimina el último carácter (salto de línea) de cada línea de entrada llamando al chopmétodo en ellos y devolviendo una matriz de los resultados.

htoma el primer elemento de esta matriz y *gtoma el resto. Así terminamos con la primera línea hy las líneas de la cuadrícula de crucigramas g.

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

g*?#une ( *) la matriz gcon "#"( ?#es un carácter literal). Esto es lo mismo que g.*("#"), o g.join("#"). Entonces cada no #es reemplazado por un espacio.

Para la verificación de simetría solo tenemos que verificar si el carácter en cada índice es igual al carácter en el índice opuesto en la cadena:

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

En Ruby podemos indexar cadenas desde el final usando índices negativos (comenzando desde en -1lugar de 0), por lo que g[-i-1]es lo contrario de g[i]en la cadena. Esto ahorra algunos caracteres:

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

Podemos guardar un ;usando una declaración condicional:

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

En la versión de golf podemos guardar algunos caracteres más:

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

En una versión anterior, utilicé la recursión para iterar sobre la cadena:

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

Un acceso fuera de límite a gretornos nulo, por lo que una vez que g[i]regresa nil, esto detiene la iteración.

Formato de salida:

{ L | R } line-number column-number

L para errores de longitud y R para error de rotación ( L 1 2significa error de longitud en la línea 1, columna 2)

Arnaud Le Blanc
fuente
¿Te gustaría explicar un poco para aquellos de nosotros que no hablamos rubí? Puedo ver cómo eliminaste a los no negros de los cuadrados en juego y cómo funciona la comprobación de la longitud de la respuesta (bueno, por cierto), pero no estoy recibiendo la comprobación de simetría.
dmckee --- ex gatito moderador
Veo un problema aquí de cómo se determina el ancho de la cuadrícula, tomando la longitud de la primera línea. Eso es incorrecto, solo funcionará en el ejemplo donde esa línea es "5 --- 5" (tres espacios en el medio). ¡Si fuera "5 5" no funcionaría!
Nas Banov
También creo que hay un problema con el "ajuste veritcal", al pasar por la primera fila y mirar una fila hacia abajo (+ n) y una fila hacia arriba (-n): esta última se verá en la última fila y puede equivocarse espacio de recogida desde allí!
Nas Banov
Bueno, tienes razón para el ancho de la cuadrícula; Supuse que en la primera línea, el segundo número siempre está alineado con el final de la línea.
Arnaud Le Blanc
1

Implementación de referencia

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 --- gatito ex moderador
fuente
1

C, 278 caracteres

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);}

Como es de esperar, los mensajes de error se han mejorado. Toman la siguiente forma:

11L8 - indica un error de longitud en la fila 11 columna 8

4S10 - indica un error de simetría en la fila 4 columna 10

caja de pan
fuente
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←⎕

Si la cuadrícula no es simétrica, sale seguida de las coordenadas, es decir, para el ejemplo que da

⍉ 2 5 4 1
Si la cuadrícula tiene respuestas cortas, sale seguida de las coordenadas, es decir, para el ejemplo que da
∘ 1 2 5 2

Explicación:

  • d↑↑{'#'≠⍞}¨⍳⊃d←⎕: lea la primera línea como una lista de números y almacene d, luego lea tantas líneas como el primer número y vuelva a formar como una matriz de tamaño d. Los cuadrados 'cerrados' se almacenan como 0 y los cuadrados 'abiertos' como 1.
  • ∨/,k←⍵≠⌽⊖⍵: almacenar en klos lugares donde la cuadrícula es asimétrica. Si hay tal lugar ...
  • '⍉',(,k×⍳⍴k)~⊂2/0: muestra un ⍉ seguido de las coordenadas ofensivas
  • : de lo contrario ...
  • ~⊂2/0: elimina las coordenadas cero de la siguiente lista:
  • ¨⍵(⍉⍵): tanto para la cuadrícula como para su transposición ...
  • ¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵: rodea la cuadrícula con ceros (es decir, cuadrados cerrados)
  • 0 1 0⍷: vea dónde contiene un cuadrado 'abierto' encerrado por dos cuadrados 'cerrados' (= demasiado corto)
  • k↑1⌽1⊖: quite de nuevo el anillo de ceros adicionales
  • ,⊃,/(g(⍉g←⍳⍴⍵))×: multiplique por coordenadas y coordenadas transpuestas, y únalas para formar una lista de coordenadas ofensivas (y muchos ceros que eliminamos).
  • ×⍴d←: almacena las coordenadas ofensivas d, y si hay alguna ...
  • :'∘',d: genera un ∘ seguido de las coordenadas.
marinus
fuente