Encontre possíveis retângulos de palavras

8

Johnny está tentando criar palavras cruzadas, mas está tendo dificuldades para fazer as palavras se encaixarem.

Ele criou vários retângulos simples de palavras: ou seja, grupos de palavras que formam um retângulo onde todos os caminhos horizontais e verticais formam uma palavra.

//2x2 
PA
AM

//2x3
GOB
ORE

//3x3
BAG
AGO
RED

//3x4
MACE
AGES
WEES

No entanto, para fazer um bom quebra-cabeça, ele precisa de alguns retângulos de palavras um pouco maiores que 3x4. Em vez de agonizar as cartas de arranjo por horas, Johnny preferiria ter um programa que faça isso por ele - e no menor número possível de caracteres, porque longos blocos de código são extremamente intimidadores para programadores casuais como Johnny.


Dado

  • um dicionário de arquivo de texto em que as palavras são separadas por novas linhas em ordem alfabética,
  • entrada especificando o número de linhas e colunas no retângulo de palavras (que pode ser fornecido, porém, é mais conveniente na sua linguagem de programação preferida)

gere pelo menos um retângulo de palavras. Se não for possível gerar um retângulo de palavras com o léxico e as dimensões fornecidos, o programa não precisará ter um comportamento definido. Não é necessário que o programa possa gerar retângulos que contenham mais de 64 letras ou que tenham dimensões que excedam 8 em qualquer direção. O programa deve ser concluído em um período de tempo razoável, digamos, em trinta minutos ou menos.


EDIT: Se você estiver executando um retângulo NxN, poderá usar um arquivo de dicionário menor que contenha apenas palavras com um comprimento de N letras.

Peter Olson
fonte
Talvez eu consiga adaptar o código que escrevi para um jogo Java4k .
Peter Taylor
1
Estou curioso para saber se alguém tem uma implementação que possa gerar um 8x8 dessa lista de palavras em menos de meia hora.
MtnViewMark 14/05
@MtnViewMark Caso contrário, estarei disposto a diminuir o requisito de tamanho. Mesmo assim, acho que a implementação de Keith poderia ser feita um pouco mais rápida se ele pudesse fazer alguma verificação para reduzir o número de possibilidades.
Peter Olson
e todas as palavras devem ser diferentes?
Ming-Tang
1
@MtnViewMark, em vez de testar apenas se um prefixo é viável, uso um trie que armazena o número de filhos em cada nó para fornecer uma heurística para as quais continuações provavelmente darão uma solução. (Então eu escolho um aleatoriamente ponderado pela heurística - eu provavelmente deveria tentar escolher o melhor candidato, pois a variabilidade dos resultados não está explicitamente na especificação). Estou testando a redução para cobertura, resolvendo com os links de dança de Knuth, com base na aplicação heurística globalmente, e não nos prefixos, mas até agora não promissora. Talvez haja uma redução melhor.
Peter Taylor

Respostas:

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}

Invocado fornecendo 3 argumentos: número de linhas, número de colunas, número de soluções; e a lista de palavras é aceita em 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 você pode ver, o 7 × 7 roda relativamente rápido. Ainda cronometrando 8 × 8 e 7 × 6 ....

Seriam 9 caracteres mais curtos para remover o argumento do número de soluções e apenas produzir todas as soluções, mas torna-se impossível cronometrar.


  • Edit: (585 → 455) substituiu a estrutura de dados personalizada por um mapa simples da sequência de prefixos para possíveis substituições; estranhamente, isso é um pouco mais lento, talvez porque Map String aseja mais lento que uma árvore de Map Char a...
  • Editar: (455 → 586) Maior?!? !! Esta versão otimiza mais o espaço de pesquisa, usando as técnicas da minha solução original e as soluções python e awk. Além disso, a estrutura de dados personalizada, baseada em, Vectoré muito mais rápida do que usar uma simples Map. Por que fazer isso? Porque acho que uma solução mais próxima da meta de 8x8 em menos de meia hora é preferível a uma solução mais curta.
MtnViewMark
fonte
1
Qual versão do GHC você está usando? Usando os mesmos comandos (exceto que eu preciso --makedepois do ghc) com a lista de palavras postada na pergunta, estou recebendo palavras que não estão na lista, como "zymesz" e "youthy".
Joey Adams
2
Talvez os requisitos devam ser alterados para dizer que a grade de saída não deve ser sua própria transposição.
Peter Taylor
1
@ Joey: Você converteu o arquivo words.txt em finais de linhas locais? Estou executando no Mac OS X e converti o arquivo para \ n finais de linha antes de usá-lo.
MtnViewMark 14/05
Obrigado, isso funcionou. O arquivo de entrada deve estar em letras minúsculas e ter finais de linha compatíveis com o 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('')

No entanto, ele pode suportar até 6x6 no limite de meia hora.

Keith Randall
fonte
1
Ele gera todo o par ou apenas palavras válidas? Quando leio vertical de cima para baixo, parece não formar uma palavra válida. Por exemplo, obtive um resultado "aahs", "abet", "falta", mas a leitura vertical "stk" não está na lista de palavras e também acima eu passo o parâmetro, 3,3mas suas palavras de retorno3x4
VOCÊ
Hmmm, não é isso que eu recebo. Eu suspeito que o problema está com quebras de linha no dicionário. O arquivo fornecido possui quebras de linha do Windows (\ r \ n), portanto, o comprimento das palavras é len (w) -2. Se você de alguma forma converteu as quebras de linha (ou se o Python no Windows faz isso por você?), Altere-o para len (w) -1 e isso deve corrigi-lo.
Keith Randall
... e mude os outros +2s para +1s.
Keith Randall
Ah entendo. Eu testei com Windows e Linux. Python no Windows automaticamente removido \ra partir w, e no Linux eu tenho arquivo convertido para o formato Unix, então ambos não funcionou.
VOCÊ
Esta é uma solução muito elegante.
Asoundmove 15/05
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;}}}

Muito longe de ser o mais curto, mas acho que é o mais próximo de atender às restrições de tempo. Eu salvei 14 bytes assumindo que o arquivo de entrada foi filtrado para palavras do tamanho certo; no meu netbook, se você alimentar o todo words.txt, ele passará o primeiro minuto pré-processando-o, descartando a maior parte do que ele produz e, em seguida, leva apenas 20 segundos para resolver 7x7. Na minha área de trabalho, ele faz tudo em menos de 15 segundos, fornecendo:

rascals
areolae
serrate
coroner
alanine
latents
seeress

Deixei que funcionasse por mais de 50 horas sem encontrar uma solução para 8x7 ou 8x8. As palavras de 8 letras parecem ser um limite crítico para esse problema - apenas paira pela metade sem fazer muito progresso.

A abordagem utilizada é a articulação completa e uma heurística com base no número de conclusões horizontais possíveis vezes o número de conclusões verticais possíveis. Por exemplo, se tivermos grade intermediária

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

então, atribuímos um valor heurístico ao canto superior esquerdo count(aean*)count(aa***) + count(bean*)count(ba***) + ... + count(zean*)count(za***). De todas as células, escolhemos aquela com o menor valor heurístico (ou seja, mais difícil de satisfazer) e, em seguida, trabalhamos com as letras em ordem decrescente da quantidade em que elas contribuíram para o valor heurístico dessa célula (ou seja, começando pelo mais provável) )

Peter Taylor
fonte
Adorável abordagem e explicação.
MtnViewMark
2

F #

Solução de retrocesso, mas vou otimizar o espaço de pesquisa mais 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
fonte
1

awk, 283

(pode ser necessário adicionar 14 para sinalizadores de entrada de parâmetro)

Ligue com, por exemplo awk -v x=2 -v y=2...
Encontre a primeira correspondência e imprima-a (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}

Encontre o número de correspondências (245 caracteres, muito mais 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 os programas (é claro, mais para a contagem de soluções), o tempo de execução excede em muito 30 minutos alguns valores de x e y.

Por uma questão de interesse, eis a contagem de palavras para cada tamanho de palavra:

 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
fonte