Valide uma grade de palavras cruzadas proposta.

As inscrições devem ser programas completos que simplesmente testam uma grade proposta para determinar se ela atende a um conjunto de condições para tornar felizes os solucionadores de palavras cruzadas.

Entrada

A entrada será o nome de um arquivo que representa a grade de palavras cruzadas. O nome do arquivo de entrada pode ser passado como argumento, na entrada padrão ou por outros meios convencionais que não sejam codificados.

Formato de arquivo de grade: A primeira linha consiste em duas constantes inteiras separadas por espaços em branco M e N. A seguir, há linhas M, cada uma composta por N caracteres (mais uma nova linha) selecionados [#A-Z ]. Esses caracteres são interpretados de forma a '#' indicar um quadrado bloqueado, ' 'um quadrado aberto no quebra-cabeça sem conteúdo conhecido e qualquer letra um quadrado aberto que contenha essa letra.

Resultado

O programa não deve produzir saída em grades válidas e sair com o estado de terminação normal. Se a grade proposta falhar, o programa deverá produzir uma mensagem de erro de diagnóstico e sair com um estado de finalização anormal (ou seja, não 0 no unix) se isso for suportado pelo seu ambiente de execução. A mensagem de erro deve indicar qual condição de validade é violada e a localização do quadrado incorreto; você é livre para escolher os meios de transmitir esses fatos.

Condições de validade

As grades válidas não terão respostas (cruzadas ou inativas) com apenas 1 caractere (crédito extra por tornar o tamanho mínimo um parâmetro de entrada) e exibirão a simetria usual. A simetria usual significa que as palavras cruzadas permanecem as mesmas depois (três descrições equivalentes da mesma operação):

• reflexão através do seu próprio centro
• reflexão vertical e horizontalmente
• Rotação de 180 graus

Entrada de teste e saída esperada

Passes:

5   5
#  ##
#    
  #  
    #
##  #

Falha na resposta curta:

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

Falha na simetria:

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

a parte, de lado

Este é o segundo de vários desafios relacionados às palavras cruzadas. Pretendo usar um conjunto consistente de formatos de arquivo e criar um conjunto respeitável de utilitários relacionados a palavras cruzadas no processo. Por exemplo, um quebra-cabeça subsequente exigirá a impressão de uma versão ASCII das palavras cruzadas com base na entrada e saída desse quebra-cabeça.

Desafios anteriores desta série:

• Numeração de palavras cruzadas

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

Isso basicamente remove o último caractere (quebra de linha) de cada linha de entrada chamando o chopmétodo neles e retornando uma matriz dos resultados.

hpega o primeiro elemento dessa matriz e *gpega o resto. Então, terminamos com a primeira linha he as linhas de grade de palavras cruzadas g.

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

g*?#junta-se ( *) à matriz gcom "#"( ?#é um caractere literal). É o mesmo que g.*("#"), ou g.join("#"). Então todo não #é substituído por um espaço.

Para a verificação de simetria, basta verificar se o caractere em cada índice é igual ao caractere no índice oposto na string:

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

No Ruby, podemos indexar strings a partir do final usando índices negativos (começando em -1vez de 0), de modo que g[-i-1]é o oposto de g[i]na string. Isso economiza alguns caracteres:

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

Podemos salvar um ;usando uma declaração condicional:

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

Na versão golfed, podemos salvar mais alguns caracteres:

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

Em uma versão anterior, usei recursão para iterar sobre a string:

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

Um acesso fora do limite para gretornos nulos; portanto, uma vez g[i]retornado nil, isso interrompe a iteração.

Formato de saída:

{ L | R } line-number column-number

L para erros de comprimento e R para erro de rotação ( L 1 2significa erro de comprimento na linha 1, coluna 2)

Implementação de referência

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

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 seria de esperar, as próprias mensagens de erro foram jogadas no golfe. Eles assumem a seguinte forma:

11L8 - indica um erro de comprimento na linha 11, coluna 8

4S10 - indica um erro de simetria na linha 4, coluna 10

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←⎕

Se a grade não for simétrica, ela sai ⍉seguida pelas coordenadas, ou seja, por exemplo, fornece

2 5 4 1

1 2 5 2

Explicação:

• d↑↑{'#'≠⍞}¨⍳⊃d←⎕: leia a primeira linha como uma lista de números e armazene-a d, depois leia quantas linhas como o primeiro número e reformule como uma matriz de tamanho d. Os quadrados 'fechados' são armazenados como 0 e os quadrados 'abertos' como 1.
• ∨/,k←⍵≠⌽⊖⍵: armazene nos klocais onde a grade é assimétrica. Se existe um lugar assim ...
• '⍉',(,k×⍳⍴k)~⊂2/0: produza a ⍉ seguido pelas coordenadas incorretas
• ⋄: de outra forma...
• ~⊂2/0: remova as coordenadas zero da seguinte lista:
• ¨⍵(⍉⍵): para a grade e sua transposição ...
• ¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵: rode a grade com zeros (quadrados fechados)
• 0 1 0⍷: veja onde ele contém um quadrado 'aberto' delimitado por dois quadrados 'fechados' (= muito curto)
• k↑1⌽1⊖: remova o anel de zeros extras novamente
• ,⊃,/(g(⍉g←⍳⍴⍵))×: multiplique por coordenadas e coordenadas transpostas e junte-se para formar uma lista de coordenadas incorretas (e muitos zeros que removemos).
• ×⍴d←: armazene as coordenadas incorretas de, se houver alguma ...
• :'∘',d: produza a ∘ seguido pelas coordenadas.