Finden Sie mögliche Wortrechtecke

8

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.

Peter Olson
quelle
Möglicherweise kann ich den Code anpassen, den ich für ein Java4k-Spiel geschrieben habe .
Peter Taylor
1
Ich bin gespannt, ob jemand eine Implementierung hat, die aus dieser Wortliste in weniger als einer halben Stunde ein 8x8 generieren kann .
MtnViewMark
@MtnViewMark Wenn nicht, bin ich bereit, die Größenanforderungen zu senken. Trotzdem denke ich, dass die Implementierung von Keith erheblich beschleunigt werden könnte, wenn er einige Überprüfungen durchführen könnte, um die Anzahl der Möglichkeiten zu verringern.
Peter Olson
und alle Wörter müssen unterschiedlich sein?
Ming-Tang
1
@MtnViewMark, anstatt nur zu testen, ob ein Präfix brauchbar ist, verwende ich einen Versuch, der die Anzahl der untergeordneten Knoten unter jedem Knoten speichert, um eine Heuristik zu erstellen, für die Fortsetzungen am wahrscheinlichsten eine Lösung liefern. (Ich wähle dann einen zufällig nach der Heuristik gewichteten aus - ich sollte wahrscheinlich versuchen, nur den besten Kandidaten auszuwählen, da die Variabilität der Ergebnisse nicht explizit in der Spezifikation enthalten ist.) Ich teste die Reduzierung, um Deckung zu setzen, und löse sie mit Knuths tanzenden Links auf der Grundlage, dass Heuristiken global und nicht auf Präfixe angewendet werden, aber bisher nicht vielversprechend. Vielleicht gibt es eine bessere Reduzierung.
Peter Taylor

Antworten:

5

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

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.
MtnViewMark
quelle
1
Welche Version von GHC verwenden Sie? Wenn ich dieselben Befehle (außer ich brauche --makenach ghc) mit der in der Frage angegebenen Wortliste verwende, erhalte ich Wörter, die nicht in der Liste enthalten sind, wie "zymesz" und "jugendlich".
Joey Adams
2
Vielleicht sollten die Anforderungen geändert werden, um zu sagen, dass das Ausgangsnetz keine eigene Transponierung sein sollte.
Peter Taylor
1
@Joey: Haben Sie die Datei words.txt in lokale Zeilenenden konvertiert? Ich verwende Mac OS X und habe die Datei vor der Verwendung in \ n Zeilenenden konvertiert.
MtnViewMark
Danke, das hat funktioniert. Die Eingabedatei muss in Kleinbuchstaben geschrieben sein und mit dem eigenen System kompatible Zeilenenden aufweisen.
Joey Adams
5

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.

Keith Randall
quelle
1
Erzeugt es nur das gesamte Paar oder das gültige Wortpaar? Wenn ich vertikal von oben nach unten lese, scheint es kein gültiges Wort zu bilden. ZB habe ich ein Ergebnis "aahs", "abet", "lack", aber vertikales Lesen "stk" ist nicht in der Wortliste, und auch für oben übergebe ich Parameter, 3,3aber seine Rückgabewörter3x4
YOU
Hmmm, das verstehe ich nicht. Ich vermute, das Problem liegt in Zeilenumbrüchen im Wörterbuch. Die bereitgestellte Datei enthält Windows-Zeilenumbrüche (\ r \ n), sodass die Länge der Wörter len (w) -2 beträgt. Wenn Sie die Zeilenumbrüche irgendwie konvertiert haben (oder wenn Python unter Windows das für Sie erledigt?), Ändern Sie sie in len (w) -1, und das sollte das Problem beheben.
Keith Randall
... und ändere die anderen +2s in +1s.
Keith Randall
Ah ich sehe. Ich habe mit Windows und Linux getestet. Python unter Windows automatisch entfernt \rvon wund auf Linux Ich habe konvertierte Datei in Unix - Format, so arbeiten beide nicht.
SIE
Dies ist eine sehr elegante Lösung.
Asoundmove
3

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

Peter Taylor
quelle
Schöne Herangehensweise und Erklärung.
MtnViewMark
2

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
Ming-Tang
quelle
1

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
asoundmove
quelle