Kompulsi Crossword!

14

Chris, pecandu teka-teki silang samar, memiliki satu set algoritma untuk urutan di mana dia memecahkannya.

masukkan deskripsi gambar di sini

Kami akan menggunakan gambar di atas sebagai panduan.

  1. Chris selalu memulai dengan petunjuk pertama, dalam hal ini 1 Across. Chris adalah penggila teka-teki silang yang cakap, sehingga diasumsikan bahwa ia akan selalu tahu jawaban atas petunjuk yang sedang dikerjakannya.
  2. Setelah Chris menyelesaikan suatu petunjuk, ia akan memeriksa semua petunjuk yang berdampingan dengan yang telah ia selesaikan (dalam kasus pertama, 1 Down, 2 Down, dan 3 Down) dan kemudian melengkapi petunjuk itu dengan angka terendah. Jika tidak ada petunjuk yang bersebelahan, ia akan pergi ke langkah 3.
  3. Jika petunjuknya sedemikian sehingga nomor berikutnya (seperti yang dijelaskan dalam Langkah 3) memiliki petunjuk lintas dan petunjuk turun, ia akan menyelesaikan petunjuk pertama (100% kepastian, ini berbatasan dengan OCD!)
  4. Jika tidak ada petunjuk yang berdampingan, ia akan pergi ke petunjuk yang tersedia berikutnya yang nomor berikutnya (melintasi atau ke bawah)
  5. Ulangi dari Langkah 2 sampai semua petunjuk selesai.

Dan ini adalah saatnya untuk Anda, coders sayang. Anda telah ditugaskan untuk membuat kode yang dapat, dengan disediakan template teka-teki silang, memberikan output yang menggambarkan urutan petunjuk berdasarkan algoritma Chris untuk menyelesaikannya.

Kode akan menerima input dari template teka-teki silang, dalam bentuk .mewakili kotak putih dan #mewakili kotak hitam.

Contoh :

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

Input dapat melalui: a) file yang membaca representasi dari teka-teki silang, atau b) dengan input baris dari setiap baris teka-teki silang, diikuti oleh \n, dengan \nEOF kedua yang mengindikasikan.

Dan kemudian akan menentukan metode dimana Chris akan menyelesaikannya sesuai dengan algoritma di atas yang telah dia jelaskan.

Output harus dalam format serangkaian instruksi yang dipisahkan koma dalam bentuk n(A|D), di mana nnomor petunjuk diikuti oleh Auntuk seluruh atau Duntuk ke bawah.

Jadi pada contoh di atas (baik dari gambar, dan contoh template, yang merupakan satu dan sama), hasilnya adalah:

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

Kode terpendek menang ...

Pengujian

Anda harus memberikan kode, jumlah byte, dan salah satu dari empat kasus uji yang diwakili dalam .dan #format, serta output yang dihasilkan dari input ini. Ada empat kasus uji, tiga di bawah ini serta contoh template di atas.

Contoh uji kasus:

Test Case 1

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

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

Test Case 2

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

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

Test Case 3

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

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

Test Case 4

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

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

Semoga berhasil!

WallyWest
sumber
Hanya untuk memastikan: Pada contoh gambar Anda, nomor manakah yang merupakan petunjuk kelima yang harus diisi secara kompulsif? (setelah 1H, 1V, 2V, 3V)
Dr. belisarius
@belisarius Gambar sesuai dengan test case keempat. Jadi petunjuk kelima yang harus diisi adalah 9 Across, atau seperti yang Anda katakan, 9H :) Sebagai satu-satunya petunjuk yang berdekatan setelah petunjuk keempat selesai adalah 9 dan 10 Across, Chris akan dipaksa untuk mengisi petunjuk terendah terlebih dahulu ...
WallyWest
Apakah byte dianggap hanya berdasarkan kode yang menghasilkan output yang benar. TKI, apakah Anda dihukum pada termasuk, C # namespace + class + Main, dan sejenisnya agar dapat dikompilasi atau masuk akal untuk menganggap bahwa jika saya menulisnya dalam C #, atau serupa, jumlah kode yang minimal diperlukan?
ChiefTwoPencils
1
@ BobbyDigital Yah, ini kode-golf ... Saya berharap jika Anda berencana menulisnya di C # Anda akan mencoba untuk tidak menggunakan terlalu banyak eksternal ... Anda harus menghitungnya, saya takut .. .
WallyWest
1
@WallyWest Saya pikir contoh ketiga Anda menghilangkan sebuah 17Adi akhir. Juga yang keempat 4Atepat setelahnya 4D.
Howard

Jawaban:

5

GolfScript, 154 karakter

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

Masukan harus diberikan di STDIN. Contoh-contoh menghasilkan hasil berikut (periksa online ):

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
sumber
+1 Sangat singkat. Bagaimana cara kerjanya?
DavidC
Wow, terima kasih sudah menjelaskan bahwa saya seharusnya tidak membuang waktu. Jelas harus menguasai bahasa yang lebih tepat. votes++
ChiefTwoPencils
@ BobbyDigital maksudku tidak ada rasa tidak hormat. C # adalah bahasa yang sangat verbose ... mungkin bukan yang terbaik untuk kode golf. Bowling kode atau untuk kontes popularitas di sini ... tapi Code Golf adalah ketel ikan yang sama sekali baru.
WallyWest
+1 di sini juga ... Mungkin salah satu entri GolfScript yang lebih panjang yang pernah saya lihat ... Bagus sekali.
WallyWest
1
@ BobbyDigital: Tugasnya sendiri cukup menarik. Cobalah dalam bahasa yang Anda kenal. Saya pikir Anda akan menikmati puzzle sebanyak yang saya lakukan - selidiki semua pendekatan yang berbeda untuk mengatasi puzzle. Sangat menyenangkan dengan sendirinya bahkan jika Anda tidak mencapai jumlah karakter serendah jawaban ini.
Howard
3

Mathematica 806 477

(Tampaknya ada kesalahan dalam pemesanan langkah-langkah solusi. Saya melihat ini.)

Golf

Fungsi qmenemukan urutan solusi teka-teki silang.

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

Tidak disatukan

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

boardmenampilkan teka-teki silang. Kode tidak termasuk dalam jumlah karakter. Beberapa sub fungsi dari qdipinjam di sini.

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", "6A", "8A", "8A", "9A"}}


3

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

board[t3]

q[t3]

t3

{"1A", "2D", "3D", "4D", "5D", "6D", "7A", "8D", "9A", "10A", "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", "8D", "9A", "10A", " 11A "," 12A "," 13A "," 14D "," 15A "," 15D "," 16A "," 17A "," 18D "," 19D "," 20A "," 21D "," 21D "," 22D " , "23A", "24A", "25D", "26D", "27A", "28A", "29A", "30A", "30A", "31A"}

DavidC
sumber
Saya pikir Anda memiliki masalah dengan kode Anda. Misalnya dalam contoh 2 3Aseharusnya tidak boleh tepat setelah 2Dkarena belum ada petunjuk. Juga solusi lain menunjukkan efek ini.
Howard
Howard, aku tidak mengerti maksudmu. Dari "4. Jika tidak ada petunjuk yang berdampingan, ia akan pergi ke petunjuk berikutnya yang tersedia yang berikutnya dalam angka (melintasi atau bawah)", tampaknya 3A mungkin setelah 2D.
DavidC
Tetapi misalnya 5Amemiliki petunjuk dan karena itu harus disukai 3A.
Howard
Anda telah menetapkan singkatan untuk ToStringdua kali
Dr. belisarius
Howard, Sekarang aku mengerti maksudmu. Terima kasih. Akan dikoreksi nanti.
DavidC