Encuentra posibles rectángulos de palabras

8

Johnny está tratando de crear crucigramas, pero tiene dificultades para hacer que las palabras coincidan entre sí.

Se le han ocurrido varios rectángulos de palabras simples: es decir, grupos de palabras que forman un rectángulo donde todas las rutas horizontales y verticales forman una palabra.

//2x2 
PA
AM

//2x3
GOB
ORE

//3x3
BAG
AGO
RED

//3x4
MACE
AGES
WEES

Sin embargo, para hacer un buen rompecabezas, necesita algunos rectángulos de palabras que sean algo más grandes que 3x4. En lugar de agonizar por las cartas de arreglo durante horas, Johnny preferiría tener un programa que haga esto por él, y en la menor cantidad de caracteres posible, porque los bloques largos de código son extremadamente intimidantes para programadores casuales como Johnny.


Dado

  • un diccionario de archivos de texto donde las palabras están separadas por nuevas líneas en orden alfabético,
  • entrada que especifica el número de filas y columnas en el rectángulo de palabras (que se puede proporcionar, sin embargo, es más conveniente en el lenguaje de programación que elija)

generar al menos una palabra rectángulo. Si no es posible generar un rectángulo de palabras con el léxico y las dimensiones dadas, el programa no necesita tener un comportamiento definido. No es necesario que el programa pueda generar rectángulos que contengan más de 64 letras o que tengan dimensiones superiores a 8 en cualquier dirección. El programa debería poder completarse en un tiempo razonable, digamos, en treinta minutos o menos.


EDITAR: Si está haciendo un rectángulo NxN, puede usar un archivo de diccionario más pequeño que solo contiene palabras que tienen una longitud de N letras.

Peter Olson
fuente
Puede que sea capaz de adaptar el código que escribí para un juego Java4k .
Peter Taylor
1
Tengo curiosidad por saber si alguien tiene una implementación que pueda generar un 8x8 de esa lista de palabras en menos de ½ hora.
MtnViewMark
@MtnViewMark Si no, estaré dispuesto a reducir el requisito de tamaño. Aun así, creo que la implementación de Keith podría hacerse un poco más rápido si pudiera hacer algunas comprobaciones para reducir el número de posibilidades.
Peter Olson
y todas las palabras deben ser diferentes?
Ming-Tang
1
@MtnViewMark, en lugar de probar simplemente si un prefijo es viable, utilizo un trie que almacena el número de niños debajo de cada nodo para dar una heurística para la cual las continuaciones tienen más probabilidades de dar una solución. (Luego elijo uno al azar ponderado por la heurística; probablemente debería intentar elegir el mejor candidato, ya que la variabilidad de los resultados no está explícitamente en la especificación). Estoy probando la reducción para establecer una cobertura, resolviendo con los enlaces de baile de Knuth, sobre la base de que aplica la heurística globalmente en lugar de los prefijos, pero hasta ahora no es prometedor. Quizás haya una mejor reducción.
Peter Taylor

Respuestas:

5

Haskell, 586 caracteres

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}

Se invoca proporcionando 3 argumentos: número de filas, número de columnas, número de soluciones; y la lista de palabras se acepta en 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

Como puede ver, 7 × 7 corre relativamente rápido. Todavía cronometraje 8 × 8 y 7 × 6 ...

Sería 9 caracteres más cortos para eliminar el argumento de la cantidad de soluciones y solo producir todas las soluciones, pero luego se hace imposible el tiempo.


  • Editar: (585 → 455) reemplazó la estructura de datos personalizada con un mapa simple de cadena de prefijo para posibles reemplazos; Curiosamente, esto es un poco más lento, tal vez porque Map String aes más lento que un árbol de Map Char a...
  • Editar: (455 → 586) Más grande?!? !! Esta versión optimiza más el espacio de búsqueda, utilizando las técnicas de mi solución original y las soluciones python y awk. Además, la estructura de datos personalizada, basada en Vectores mucho más rápida que el uso de un simple Map. ¿Por qué hacer esto? Porque creo que una solución más cercana al objetivo de 8x8 en menos de ½ hora es preferible a una solución más corta.
MtnViewMark
fuente
1
¿Qué versión de GHC estás usando? Usando los mismos comandos (excepto que necesito --makedespués de ghc) con la lista de palabras publicada en la pregunta, obtengo palabras que no están en la lista, como "zymesz" y "youthy".
Joey Adams
2
Quizás deberían modificarse los requisitos para decir que la cuadrícula de salida no debería ser su propia transposición.
Peter Taylor
1
@Joey: ¿Convertiste el archivo words.txt a finales de línea locales? Estoy ejecutando Mac OS X y convertí el archivo a \ n terminaciones de línea antes de usarlo.
MtnViewMark
Gracias, eso funcionó. El archivo de entrada debe estar en minúsculas y tener terminaciones de línea compatibles con el sistema.
Joey Adams
5

Python, 232 caracteres

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

Sin embargo, solo puede manejar hasta 6x6 en el límite de 1/2 hora.

Keith Randall
fuente
1
¿Genera todo el par o solo el par de palabras válidas? Cuando leo verticalmente de arriba a abajo, no parece formar una palabra válida. Por ejemplo, obtuve un resultado "aahs", "abet", "falta", pero la lectura vertical "stk" no está en la lista de palabras, y también para el parámetro anterior paso 3,3pero sus palabras de retorno3x4
USTED
Hmmm, eso no es lo que obtengo. Sospecho que el problema es con los saltos de línea en el diccionario. El archivo proporcionado tiene saltos de línea de Windows (\ r \ n), por lo que la longitud de las palabras es len (w) -2. Si de alguna manera convirtió los saltos de línea (o si Python en Windows lo hace por usted), cámbielo a len (w) -1 y eso debería solucionarlo.
Keith Randall
... y cambia el otro +2s por +1s.
Keith Randall
Ah, ya veo. Probé con Windows y Linux. Python en Windows eliminado automáticamente \rde w, y en Linux tengo archivo convertido a formato Unix, por lo tanto no funcionaba.
USTED
Esta es una solución muy elegante.
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;}}}

Lejos de ser el más corto, pero creo que es lo más cercano a cumplir con las limitaciones de tiempo. Ahorré 14 bytes asumiendo que el archivo de entrada se ha filtrado a palabras de la longitud correcta; en mi netbook, si alimentas todo, words.txtentonces pasa el primer minuto preprocesándolo, descartando la mayor parte de lo que produce, y luego toma solo unos 20 segundos para resolver 7x7. En mi escritorio, hace todo en menos de 15 segundos, dando:

rascals
areolae
serrate
coroner
alanine
latents
seeress

Lo dejé funcionar durante más de 50 horas sin encontrar una solución para 8x7 u 8x8. Las palabras de 8 letras parecen ser un límite crítico para este problema: simplemente se cierne a la mitad sin avanzar mucho.

El enfoque utilizado es de pivote completo y una heurística basada en el número de posibles compleciones horizontales multiplicado por el número de posibles compleciones verticales. Por ejemplo, si tenemos cuadrícula intermedia

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

entonces le damos a la esquina superior izquierda un valor heurístico de count(aean*)count(aa***) + count(bean*)count(ba***) + ... + count(zean*)count(za***). De todas las celdas, elegimos la que tiene el valor heurístico más pequeño (es decir, la más difícil de satisfacer), y luego trabajamos a través de las letras en orden descendente de la cantidad que contribuyeron al valor heurístico de esa celda (es decir, comenzando con la más probable de tener éxito )

Peter Taylor
fuente
Enfoque encantador y explicación.
MtnViewMark
2

F#

Solución de retroceso, pero voy a optimizar el espacio de búsqueda más tarde.

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
fuente
1

awk, 283

(puede que sea necesario agregar 14 para las banderas de entrada de parámetros)

Llame con, por ejemplo, awk -v x=2 -v y=2...
Encuentre la primera coincidencia e imprímala (283 caracteres):

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

Encuentra el número de partidos (245 caracteres, mucho más lento):

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

Para ambos programas (por supuesto, más para el recuento de soluciones), el tiempo de ejecución supera con creces los 30 minutos para algunos valores de x e y.

Solo como una cuestión de interés, aquí está el conteo de palabras para cada longitud de palabra:

 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
fuente