Johnny versucht Kreuzworträtsel zu erstellen, aber er hat Schwierigkeiten, Wörter aufeinander abzustimmen.

Er hat sich mehrere einfache Wortrechtecke ausgedacht: dh Wortgruppen, die ein Rechteck bilden, wobei alle horizontalen und vertikalen Pfade ein Wort bilden.

//2x2 
PA
AM

//2x3
GOB
ORE

//3x3
BAG
AGO
RED

//3x4
MACE
AGES
WEES

Um ein gutes Puzzle zu erstellen, benötigt er jedoch einige Wortrechtecke, die etwas größer als 3x4 sind. Anstatt sich stundenlang über die Arrangement-Briefe zu quälen, würde Johnny es vorziehen, ein Programm zu haben, das dies für ihn erledigt - und zwar in möglichst wenigen Zeichen, da lange Codeblöcke für Gelegenheitsprogrammierer wie Johnny äußerst einschüchternd sind.

Gegeben

• ein Textdatei- Wörterbuch, in dem Wörter durch Zeilenumbrüche in alphabetischer Reihenfolge getrennt sind;
• Eingabe unter Angabe der Anzahl der Zeilen und Spalten im Wortrechteck (die bereitgestellt werden kann, ist jedoch in der Programmiersprache Ihrer Wahl am bequemsten)

Generieren Sie mindestens ein Wortrechteck. Wenn es nicht möglich ist, ein Wortrechteck mit dem angegebenen Lexikon und den angegebenen Dimensionen zu generieren, muss das Programm kein definiertes Verhalten haben. Es ist nicht erforderlich, dass das Programm Rechtecke mit mehr als 64 Buchstaben oder Abmessungen von mehr als 8 in beide Richtungen generieren kann. Das Programm sollte in angemessener Zeit abgeschlossen sein können, beispielsweise in 30 Minuten oder weniger.

BEARBEITEN: Wenn Sie ein NxN-Rechteck erstellen, dürfen Sie eine kleinere Wörterbuchdatei verwenden, die nur Wörter mit einer Länge von N Buchstaben enthält.

Haskell, 586 Zeichen

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
p∫w=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}

Wird durch Angabe von 3 Argumenten aufgerufen: Anzahl der Zeilen, Anzahl der Spalten, Anzahl der Lösungen; und die Wortliste wird akzeptiert am 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

Wie Sie sehen können, läuft 7 × 7 relativ schnell. Immer noch Timing 8 × 8 und 7 × 6 ....

Es wäre 9 Zeichen kürzer, das Argument für die Anzahl der Lösungen zu entfernen und nur alle Lösungen zu erstellen, aber dann wird es unmöglich, die Zeit zu bestimmen.

• Bearbeiten: (585 → 455) hat die benutzerdefinierte Datenstruktur durch eine einfache Zuordnung der Präfixzeichenfolge zu möglichen Ersetzungen ersetzt. Seltsamerweise ist dies etwas langsamer, vielleicht weil Map String aes langsamer ist als ein handgefertigter Baum aus Map Char a...
• Edit: (455 → 586) Größer?!? !! Diese Version optimiert den Suchraum stärker, indem sowohl die Techniken meiner ursprünglichen Lösung als auch die der Python- und Awk-Lösungen verwendet werden. Darüber hinaus ist die benutzerdefinierte Datenstruktur, auf der Vectorbasiert, viel schneller als die Verwendung einer einfachen Map. Warum das? Weil ich denke, dass eine Lösung, die in weniger als einer halben Stunde näher am Ziel von 8x8 liegt, einer kürzeren Lösung vorzuziehen ist.

Python, 232 Zeichen

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('')

Es kann jedoch nur bis zu 6x6 im 1/2-Stunden-Limit verarbeiten.

Java (1065 Bytes)

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

Weit davon entfernt, der kürzeste zu sein, aber ich denke, es ist am nächsten an der Einhaltung der zeitlichen Einschränkungen. Ich habe 14 Bytes gespeichert, indem ich angenommen habe, dass die Eingabedatei nach Wörtern der richtigen Länge gefiltert wurde. Wenn Sie auf meinem Netbook das Ganze füttern words.txt, verbringt es die erste Minute damit, es vorzuverarbeiten, das meiste von dem, was es produziert, zu verwerfen, und dann dauert es nur etwa 20 Sekunden, um 7x7 zu lösen. Auf meinem Desktop erledigt es das Ganze in weniger als 15 Sekunden und gibt:

rascals
areolae
serrate
coroner
alanine
latents
seeress

Ich habe es über 50 Stunden laufen lassen, ohne eine Lösung für 8x7 oder 8x8 zu finden. 8-Buchstaben-Wörter scheinen eine kritische Grenze für dieses Problem zu sein - es schwebt nur halb voll, ohne große Fortschritte zu machen.

Der verwendete Ansatz ist das vollständige Schwenken und eine Heuristik, die auf der Anzahl möglicher horizontaler Abschlüsse multipliziert mit der Anzahl möglicher vertikaler Abschlüsse basiert. ZB wenn wir ein Zwischengitter haben

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

dann geben wir der oberen linken Ecke einen heuristischen Wert von count(aean*)count(aa***) + count(bean*)count(ba***) + ... + count(zean*)count(za***). Von allen Zellen wählen wir die mit dem kleinsten heuristischen Wert aus (dh am schwierigsten zu befriedigen) und arbeiten dann die Buchstaben in absteigender Reihenfolge des Betrags durch, den sie zum heuristischen Wert dieser Zelle beigetragen haben (dh beginnend mit dem wahrscheinlichsten Erfolg) ).

F #

Backtracking-Lösung, aber ich werde den Suchraum später optimieren.

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

awk, 283

(Möglicherweise müssen 14 für Parametereingabeflags hinzugefügt werden.)

Rufen Sie an mit zB awk -v x=2 -v y=2...
Finden Sie die erste Übereinstimmung und drucken Sie sie aus (283 Zeichen):

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

Anzahl der Übereinstimmungen ermitteln (245 Zeichen, viel langsamer):

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

Für beide Programme (natürlich mehr für die Anzahl der Lösungen) überschreitet die Laufzeit für einige Werte von x und y 30 Minuten bei weitem.

Aus Gründen des Interesses ist hier die Wortanzahl für jede Wortlänge:

 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