Temukan Kemungkinan Rectangles Kata

8

Johnny mencoba membuat teka-teki silang, tetapi ia kesulitan membuat kata-kata yang cocok satu sama lain.

Dia telah datang dengan beberapa kata persegi panjang sederhana: yaitu, kelompok kata-kata yang membentuk persegi panjang di mana semua jalur horizontal dan vertikal membentuk sebuah kata.

//2x2 
PA
AM

//2x3
GOB
ORE

//3x3
BAG
AGO
RED

//3x4
MACE
AGES
WEES

Namun, untuk membuat teka-teki yang baik, ia membutuhkan beberapa kata persegi panjang yang agak lebih besar dari 3x4. Alih-alih menderita karena pengaturan surat selama berjam-jam, Johnny lebih memilih untuk memiliki program yang melakukan ini untuknya - dan dalam karakter sesedikit mungkin, karena blok kode yang panjang sangat menakutkan bagi programmer biasa seperti Johnny.


Diberikan

  • sebuah file teks kamus mana kata-kata dipisahkan oleh baris baru dalam urutan abjad,
  • input menentukan jumlah baris dan kolom dalam kata-kata persegi panjang (yang dapat disediakan namun paling nyaman dalam bahasa pemrograman pilihan Anda)

menghasilkan setidaknya satu kata persegi panjang. Jika tidak mungkin untuk menghasilkan kata persegi panjang dengan leksikon dan dimensi yang diberikan, program tidak perlu memiliki perilaku yang ditentukan. Tidak perlu bagi program untuk dapat menghasilkan persegi panjang yang berisi lebih dari 64 huruf atau memiliki dimensi yang melebihi 8 di kedua arah. Program harus dapat menyelesaikan dalam jumlah waktu yang wajar, katakanlah, dalam tiga puluh menit atau kurang.


EDIT: Jika Anda melakukan NxN persegi panjang, Anda diizinkan untuk menggunakan file kamus yang lebih kecil yang hanya berisi kata-kata yang memiliki panjang N huruf.

Peter Olson
sumber
Saya mungkin dapat mengadaptasi kode yang saya tulis untuk game Java4k .
Peter Taylor
1
Saya ingin tahu apakah ada yang memiliki implementasi yang dapat menghasilkan 8x8 dari daftar kata dalam waktu kurang dari ½ jam.
MtnViewMark
@ MTnViewMark Jika tidak, saya akan bersedia menurunkan persyaratan ukuran. Meski begitu, saya pikir implementasi Keith bisa dibuat sedikit lebih cepat jika dia bisa melakukan pengecekan untuk mengurangi jumlah kemungkinan.
Peter Olson
dan semua kata harus berbeda?
Ming-Tang
1
@MtnViewMark, daripada hanya menguji apakah awalan layak saya menggunakan trie yang menyimpan jumlah anak di bawah setiap node untuk memberikan heuristik yang kelanjutan yang paling mungkin untuk memberikan solusi. (Saya kemudian memilih satu secara acak tertimbang oleh heuristik - Saya mungkin harus mencoba hanya memilih kandidat terbaik, karena variabilitas hasil tidak secara eksplisit dalam spesifikasi). Saya menguji pengurangan untuk mengatur, menyelesaikan dengan link menari Knuth, atas dasar itu berlaku heuristik secara global daripada awalan, tapi sejauh ini tidak menjanjikan. Mungkin ada pengurangan yang lebih baik.
Peter Taylor

Jawaban:

5

Haskell, 586 karakter

import Data.List
import qualified Data.Vector as V
import System
data P=P[String](V.Vector P)
e=P[]$V.replicate 128 e
(a:z)∈(P w v)|a>' '=z∈(V.!)v(fromEnum a);_∈(P w _)=w
pw=q p w where q(P u v)=P(w:u).V.accum q v.x;x(a:z)=[(fromEnum a,z)];x _=[]
l%n=foldl'(∫)e.filter((==n).length)$l
d§(p,q:r)=map(\w->p++w:r)$q∈d;_§(p,_)=[p]
(d¶e)i=filter(not.any(null.(∈e))).map transpose.(d§).splitAt i
s i n d e m|i==n=["":m]|1<3=(d¶e)i m>>=(e¶d)i>>=s(i+1)n d e
p[b,a,n]w=take n$s 0(a`max`b)(w%a)(w%b)$replicate b$replicate a ' '
main=do{g<-map read`fmap`getArgs;interact$unlines.concat.p g.lines}

Diminta dengan memberikan 3 argumen: jumlah baris, jumlah kolom, jumlah solusi; dan daftar kata diterima pada stdin:

$> ghc -O3 2554-WordRect.hs 
[1 of 1] Compiling Main             ( 2554-WordRect.hs, 2554-WordRect.o )
Linking 2554-WordRect ...

$> time ./2554-WordRect 7 7 1 < 2554-words.txt

zosters
overlet
seriema
trimmer
element
remends
startsy

real    0m22.381s
user    0m22.094s
sys     0m0.223s

Seperti yang Anda lihat 7x7 berjalan relatif cepat. Waktu masih 8 × 8 dan 7 × 6 ....

Akan lebih pendek 9 karakter untuk menghapus jumlah argumen solusi dan hanya menghasilkan semua solusi, tetapi kemudian menjadi tidak mungkin waktu.


  • Sunting: (585 → 455) mengganti struktur data khusus dengan peta sederhana string awalan untuk kemungkinan penggantian; anehnya, ini sedikit lebih lambat, mungkin karena Map String alebih lambat daripada pohon buatan tangan Map Char a...
  • Sunting: (455 → 586) Lebih besar?!? !! Versi ini melakukan lebih banyak optimasi ruang pencarian, menggunakan kedua teknik solusi asli saya, dan solusi python dan awk. Selanjutnya, struktur data khusus, berdasarkan Vectorjauh lebih cepat daripada menggunakan yang sederhana Map. Kenapa melakukan ini? Karena saya pikir solusi yang lebih dekat ke tujuan 8x8 di bawah ½ jam lebih disukai daripada solusi yang lebih pendek.
MtnViewMark
sumber
1
Versi GHC apa yang Anda gunakan? Menggunakan perintah yang sama (kecuali saya perlu --makesetelah ghc) dengan daftar kata yang diposting dalam pertanyaan, saya mendapatkan kata-kata yang tidak ada dalam daftar, seperti "zymesz" dan "muda".
Joey Adams
2
Mungkin persyaratan harus diubah untuk mengatakan bahwa grid output tidak boleh menjadi transpos sendiri.
Peter Taylor
1
@ Joey: Apakah Anda mengonversi file words.txt ke akhir baris lokal? Saya menggunakan Mac OS X, dan saya mengonversikan file ke \ line endings sebelum menggunakannya.
MtnViewMark
Terima kasih, itu berhasil. File input harus dalam huruf kecil dan memiliki ujung garis yang kompatibel dengan sistem seseorang.
Joey Adams
5

Python, 232 karakter

x,y=input()
H=[]
P={}
for w in open('words.txt'):
 l=len(w)-2
 if l==x:H+=[w]
 if l==y:
  for i in range(y+1):P[w[:i]]=1
def B(s):
 if(x+2)*y-len(s):[B(s+w)for w in H if all((s+w)[i::x+2]in P for i in range(x))]
 else:print s
B('')

Ini hanya dapat menangani hingga 6x6 dalam batas 1/2 jam.

Keith Randall
sumber
1
Apakah itu menghasilkan semua pasangan atau hanya pasangan kata yang valid? Ketika saya membaca vertikal dari atas ke bawah, sepertinya tidak membentuk kata yang valid. Mis., Saya mendapat satu hasil "aah", "abet", "kurang", tetapi bacaan vertikal "stk" tidak ada dalam daftar kata, dan juga untuk di atas saya melewatkan parameter 3,3tetapi kata3x4
ANDA
Hmmm, bukan itu yang saya dapatkan. Saya menduga masalahnya adalah dengan linebreak dalam kamus. File yang disediakan memiliki Windows linebreaks (\ r \ n) di dalamnya, sehingga panjang kata-katanya adalah len (w) -2. Jika Anda entah bagaimana mengubah jeda baris (atau jika Python di Windows melakukan itu untuk Anda?), Ubahlah menjadi len (w) -1 dan itu akan memperbaikinya.
Keith Randall
... dan ubah yang lain +2menjadi +1s.
Keith Randall
Ah, begitu. Saya diuji dengan Windows, dan Linux. Python pada Windows secara otomatis dihapus \rdari w, dan di Linux saya telah mengkonversi file ke format Unix, sehingga keduanya tidak berfungsi.
ANDA
Ini adalah solusi yang sangat elegan.
asoundmove
3

Java (1065 byte)

import java.util.*;public class W{public static void main(String[]a){new
W(Integer.parseInt(a[0]),Integer.parseInt(a[1]));}W(int w,int h){M
H=new M(),V=new M();String L;int i,j,l,m,n=w*h,p[]=new int[n];long
I,J,K,M,C=31;long[]G=new long[h],T=new long[w],W[]=new long[n][],X;try{Scanner
S=new Scanner(new java.io.File("words.txt"));while(0<1){L=S.nextLine();l=L.length();for(i=0;i>>l<1;i++){K=0;for(j=0;j<l;j++)K+=(i>>j&1)*(L.charAt(j)-96L)<<5*j;if(l==w)H.put(K,H.g(K)+1);if(l==h)V.put(K,V.g(K)+1);}}}catch(Exception
E){}while(n-->0){j=1;if(W[n]==null){M=1L<<62;for(i=w*h;i-->0;){m=i/w;l=i%w*5;if((G[m]>>l&C)<1){X=new
long[27];I=K=0;for(;K++<26;){J=H.g(G[m]+(K<<l))*V.g(T[i%w]+(K<<5*m));X[(int)K]=K-32*J;I+=J;}if(I<1)j=0;if(I<M){M=I;p[n]=i;W[n]=X;}}}}X=W[n];Arrays.sort(X);M=X[0]*j;X[0]=0;K=M&C;i=p[n]%w;j=p[n]/w;l=5*i;m=5*j;G[j]&=~(C<<l);G[j]+=K<<l;T[i]&=~(C<<m);T[i]+=K<<m;if(M>=0){W[n]=null;n+=2;}}for(long
A:G){L="";for(i=0;i<w;)L+=(char)(96+(C&A>>5*i++));System.out.println(L);}}class
M extends HashMap<Long,Long>{long g(Long s){return get(s)!=null?get(s):0;}}}

Jauh dari menjadi yang terpendek, tapi saya pikir itu yang paling dekat dengan memenuhi batasan waktu. Saya menyimpan 14 byte dengan mengasumsikan bahwa file input telah disaring dengan kata-kata dengan panjang yang tepat; di netbook saya, jika Anda memberi makan keseluruhan words.txtmaka ia menghabiskan menit pertama preprocessing itu, membuang sebagian besar apa yang dihasilkannya, dan kemudian hanya membutuhkan sekitar 20 detik untuk menyelesaikan 7x7. Di desktop saya itu melakukan semuanya dalam waktu kurang dari 15 detik, memberikan:

rascals
areolae
serrate
coroner
alanine
latents
seeress

Saya telah membiarkannya berjalan selama lebih dari 50 jam tanpa menemukan solusi 8x7 atau 8x8. Kata 8 huruf sepertinya menjadi batas kritis untuk masalah ini - hanya sekitar setengah penuh tanpa membuat banyak kemajuan.

Pendekatan yang digunakan adalah pivot penuh dan heuristik berdasarkan jumlah kemungkinan penyelesaian horizontal dikalikan jumlah kemungkinan penyelesaian vertikal. Misal jika kita memiliki kisi perantara

*ean*
algae
*ar**
*ier*
*nee*

lalu kita beri sudut kiri atas nilai heuristik count(aean*)count(aa***) + count(bean*)count(ba***) + ... + count(zean*)count(za***). Dari semua sel, kita memilih sel dengan nilai heuristik terkecil (yaitu yang paling sulit untuk dipenuhi), dan kemudian bekerja dengan huruf-huruf dalam urutan jumlah yang mereka berikan pada nilai heuristik sel tersebut (yaitu mulai dengan yang paling mungkin berhasil) ).

Peter Taylor
sumber
Pendekatan dan penjelasan yang bagus.
MtnViewMark
2

F #

Solusi mundur, tapi saya akan mengoptimalkan ruang pencarian nanti.

open System

(*-NOTES
    W=7 H=3
    abcdefg<-- searching from wordsW
    abcdefg
    abcdefg
    ^
    partial filtering from wordsH
  *)

let prefix (s : char[]) (a : char[]) =
  a.[0..s.Length - 1] = s

let filterPrefix (s : char[]) =
  Array.filter (prefix s)

let transpose (s : char[][]) =
  [|
    for y = 0 to s.[0].Length - 1 do
      yield [|
        for x = 0 to s.Length - 1 do
          yield s.[x].[y]
      |]
  |]

[<EntryPoint>]
let main (args : String[]) =
  let filename, width, height = "C:\Users\AAA\Desktop\words.txt", 3, 3
  let lines = System.IO.File.ReadAllLines filename |> Array.map (fun x -> x.ToCharArray())
  let wordsW = Array.filter (Array.length >> ((=) width)) lines
  let wordsH = Array.filter (Array.length >> ((=) height)) lines

  let isValid (partial : char[][]) =
    if partial.Length = 0 then
      true
    else
      seq {
        for part in transpose partial do
          yield Seq.exists (prefix part) wordsH
      }
      |> Seq.reduce (&&)

  let slns = ref []
  let rec back (sub : char[][]) =
    if isValid sub then
      if sub.Length = height then
        slns := sub :: !slns
      else
        for word in wordsW do
          back <| Array.append sub [| word |]

  back [| |]
  printfn "%A" !slns
  0
Ming-Tang
sumber
1

awk, 283

(mungkin perlu menambahkan 14 untuk flag input parameter)

Panggil dengan misalnya awk -v x=2 -v y=2...
Temukan kecocokan pertama dan cetak (283 karakter):

{if(x==L=length)w[++n]=$0;if(y==L)for(;L>0;L--)W[substr($0,1,L)]++}END{for(i[Y=1]++;i[j=1]<=n;){b[Y]=w[i[Y]];while(j<=x){s="";for(k=1;k<=Y;k++)s=s substr(b[k],j,1);W[s]?0:j=x;j++}if(W[s])if(Y-y)i[++Y]=0;else{for(k=1;k<=Y;k++)print b[k];exit}i[Y]++;while(Y>1&&i[Y]>n)i[--Y]++}print N}

Temukan jumlah kecocokan (245 karakter, jauh lebih lambat):

{if(x==L=length)w[++n]=$0;if(y==L)for(;L>0;L--)W[substr($0,1,L)]++}END{for(i[Y=1]++;i[j=1]<=n;){b[Y]=w[i[Y]];while(j<=x){s="";for(k=1;k<=Y;k++)s=s substr(b[k],j,1);W[s]?0:j=x;j++}W[s]?Y-y?i[++Y]=0:N++:0;i[Y]++;while(Y>1&&i[Y]>n)i[--Y]++}print N}

Untuk kedua program (tentu saja lebih untuk solusi dihitung), waktu berjalan jauh melebihi 30 menit untuk beberapa nilai x dan y.

Yang menarik, berikut adalah jumlah kata untuk setiap panjang kata:

 2     85
 3    908
 4   3686
 5   8258
 6  14374
 7  21727
 8  26447
 9  16658
10   9199
11   5296
12   3166
13   1960
14   1023
15    557
16    261
17    132
18     48
19     16
20      5
21      3
pindahkan
sumber