Verifikasi grid teka-teki silang

8

Validasi kisi teka-teki silang yang diusulkan.

Entri harus berupa program lengkap yang hanya menguji kisi yang diusulkan untuk menentukan apakah memenuhi serangkaian persyaratan untuk membuat pemecah teka-teki silang bahagia.

Memasukkan

Input akan menjadi nama file yang mewakili kisi teka-teki silang. Nama file input dapat diberikan sebagai argumen, pada input standar, atau dengan cara konvensional lain selain hardcoding.

Format file kisi: Baris pertama terdiri dari dua konstanta integer yang dipisahkan spasi-putih M dan N. Berikut adalah garis M yang masing-masing terdiri dari N karakter (ditambah baris baru) dipilih [#A-Z ]. Karakter-karakter ini diinterpretasikan sedemikian rupa sehingga '#' mengindikasikan kotak yang diblokir, ' 'kotak terbuka dalam teka-teki tanpa isi yang diketahui dan huruf apa pun berupa kotak terbuka yang berisi huruf itu.

Keluaran

Program seharusnya tidak menghasilkan output pada kisi yang valid dan keluar dengan keadaan terminasi normal. Jika kisi yang diusulkan gagal, program harus menghasilkan pesan kesalahan diagnostik dan keluar dengan keadaan terminasi abnormal (yaitu bukan 0 pada unix) jika ini didukung oleh lingkungan eksekusi Anda. Pesan kesalahan harus menunjukkan kondisi mana untuk validitas dilanggar dan lokasi alun-alun yang menyinggung; Anda bebas memilih cara menyampaikan fakta-fakta ini.

Ketentuan untuk validitas

Kisi yang valid tidak akan memiliki jawaban (melintasi atau turun) yang panjangnya hanya 1 karakter (kredit tambahan untuk membuat panjang minimum sebagai parameter input), dan akan menunjukkan simetri yang biasa. Simetri yang biasa berarti teka-teki silang tetap sama setelah (tiga deskripsi setara dari operasi yang sama):

  • refleksi melalui pusat itu sendiri
  • refleksi baik secara vertikal maupun horizontal
  • Rotasi 180 derajat

Uji input dan output yang diharapkan

Passes:

5   5
#  ##
#    
  #  
    #
##  #

Gagal pada jawaban singkat:

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

Gagal pada simetri:

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

Ke samping

Ini adalah tantangan kedua terkait beberapa teka-teki silang. Saya berencana untuk menggunakan serangkaian file-format yang konsisten di seluruh dan untuk membangun seperangkat utilitas terkait silang yang terhormat dalam prosesnya. Misalnya teka-teki selanjutnya akan meminta untuk mencetak versi ASCII dari teka-teki silang berdasarkan input dan output dari teka-teki ini.

Tantangan sebelumnya dalam seri ini:

dmckee --- mantan kucing moderator
sumber
1
Apakah persyaratan simetri juga berlaku untuk konten kisi yang diketahui, atau hanya pada struktur (# atau tidak #)?
JB
Hanya untuk struktur kotak yang diblokir dan dalam permainan.
dmckee --- ex-moderator kitten
Oh, yang ini sudah punya karunia. Kekecewaan. Meski begitu, saya pikir dua jawaban sedikit.
Joey
Simetri pusat dan rotasi 180 ° adalah hal yang sama - bukan? Tapi saya tidak melihat simetri vertikal atau horizontal. Tapi 90 ° -pemindahan.
pengguna tidak dikenal

Jawaban:

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

Tidak Disatukan:

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

Ini pada dasarnya menghapus char (line break) terakhir dari setiap baris input dengan memanggil chopmetode pada mereka, dan mengembalikan array hasil.

hmengambil elemen pertama dari array ini dan *gmengambil sisanya. Jadi kita berakhir dengan baris pertama hdan garis kotak silang masuk g.

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

g*?#bergabung ( *) array gdengan "#"( ?#adalah karakter literal). Ini sama dengan g.*("#"), atau g.join("#"). Maka setiap non #diganti dengan spasi.

Untuk pemeriksaan simetri kita hanya perlu memeriksa apakah char di setiap indeks sama dengan char di indeks yang berlawanan dalam string:

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

Di Ruby kita bisa mengindeks string dari ujung menggunakan indeks negatif (mulai dari -1bukan 0), jadi itu g[-i-1]kebalikan dari g[i]dalam string. Ini menghemat beberapa karakter:

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

Kami dapat menyimpan ;dengan menggunakan pernyataan kondisional:

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

Dalam versi golf kita dapat menyimpan beberapa karakter lagi:

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

Dalam versi sebelumnya saya menggunakan rekursi untuk iterasi pada string:

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

Akses tidak terikat ke gpengembalian nihil, jadi setelah g[i]kembali nil, ini menghentikan iterasi.

Format output:

{ L | R } line-number column-number

L untuk kesalahan panjang, dan R untuk kesalahan rotasi (jadi L 1 2berarti kesalahan panjang pada baris 1, kolom 2)

Arnaud Le Blanc
sumber
Maukah Anda menjelaskan sedikit untuk kita yang tidak berbicara ruby? Saya bisa melihat bagaimana Anda telah menghapus non-kulit hitam dari kotak dalam-bermain, dan bagaimana memeriksa panjang jawaban bekerja (bagus, BTW), tapi saya tidak cukup mendapatkan pemeriksaan simetri.
dmckee --- ex-moderator kitten
Saya melihat masalah di sini tentang bagaimana lebar grid ditentukan - dengan mengambil panjang garis 1. Itu tidak benar, itu hanya akan bekerja pada contoh di mana garis itu "5 --- 5" (tiga spasi di tengah). Jika "5 5" itu tidak akan berhasil!
Nas Banov
Juga saya pikir ada masalah dengan "veritcal wrap-around", ketika melewati baris ke-1 dan melihat satu baris ke bawah (+ n) dan satu baris ke atas (-n) - yang terakhir akan terlihat di baris terakhir dan mungkin keliru ambil ruang dari sana!
Nas Banov
Nah Anda benar untuk lebar grid; Saya berasumsi bahwa pada baris pertama, angka kedua selalu selaras dengan akhir baris.
Arnaud Le Blanc
1

Implementasi referensi

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 --- mantan kucing moderator
sumber
1

C, 278 karakter

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

Seperti yang mungkin Anda harapkan, pesan kesalahannya sendiri telah di-golf. Mereka mengambil bentuk berikut:

11L8 - menunjukkan kesalahan panjang pada baris 11 kolom 8

4S10 - menunjukkan kesalahan simetri pada baris 4 kolom 10

kotak roti
sumber
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←⎕

Jika grid tidak simetris, itu output diikuti oleh koordinat, yaitu untuk contoh yang diberikannya

⍉ 2 5 4 1
Jika kisi-kisi memiliki jawaban pendek, hasilnya diikuti oleh koordinat, yaitu untuk contoh yang diberikannya
∘ 1 2 5 2

Penjelasan:

  • d↑↑{'#'≠⍞}¨⍳⊃d←⎕: baca baris pertama sebagai daftar angka dan simpan d, kemudian baca baris sebanyak angka pertama, dan bentuk ulang sebagai matriks ukuran d. Kotak 'Tertutup' disimpan sebagai 0 dan kotak 'terbuka' sebagai 1.
  • ∨/,k←⍵≠⌽⊖⍵: simpan di ktempat-tempat di mana grid tidak simetris. Jika ada tempat seperti itu ...
  • '⍉',(,k×⍳⍴k)~⊂2/0: output a ⍉ diikuti oleh koordinat yang menyinggung
  • : jika tidak...
  • ~⊂2/0: hapus koordinat nol dari daftar berikut:
  • ¨⍵(⍉⍵): untuk grid dan transposnya ...
  • ¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵: mengelilingi grid dengan nol (yaitu kotak tertutup)
  • 0 1 0⍷: lihat di mana itu berisi kotak 'terbuka' yang dikelilingi oleh dua kotak 'tertutup' (= terlalu pendek)
  • k↑1⌽1⊖: lepaskan cincin nol tambahan lagi
  • ,⊃,/(g(⍉g←⍳⍴⍵))×: kalikan dengan koordinat dan koordinat yang dialihkan, dan gabung bersama, untuk membentuk daftar koordinat yang menyinggung (dan banyak nol yang kita hapus).
  • ×⍴d←: simpan koordinat yang menyinggung di d, dan jika ada ...
  • :'∘',d: output a ∘ diikuti oleh koordinat.
marinus
sumber