Solver Pesquisa de Palavras

13

Ontem, me perguntei se poderia escrever um programa para vasculhar uma determinada pesquisa de palavras e gerar as respostas. Foi realmente surpreendentemente fácil. Agora eu me pergunto o quão pequeno podemos ficar.

Regras

  • Sua primeira entrada é uma sequência ou coleção de n linhas, cada uma com n caracteres
  • Sua segunda entrada é uma lista de palavras em qualquer formato para encontrar no quebra-cabeça
  • Todas as palavras da lista de pesquisa estão garantidas no quebra-cabeça
  • As palavras podem ser orientadas em qualquer uma das quatro direções cardeais, bem como na diagonal para a frente e para trás
  • Apenas caracteres AZ maiúsculos estarão presentes no quebra-cabeça
  • Seu código deve encontrar todas as palavras na cadeia de pesquisa e gerar a posição de coordenadas da letra inicial, onde 0,0 é o caractere superior esquerdo.
  • Caso você localize mais de uma instância da mesma palavra, você poderá manipulá-la da maneira que desejar. Saída várias vezes, ou apenas uma vez, cabe a você

Exemplos / Casos de Teste

Dado o seguinte quadro:

ABCD
EFGH
IJKL
MNOP

E a seguinte cadeia de pesquisa:

ABCD,CGKO,POMN,NJF,AFKP,CFI,LGB,MJGD

Seu programa deve gerar o seguinte, em qualquer ordem:

ABCD at 0,0
CGKO at 0,2
PONM at 3,3
NJF at 3,1
AFKP at 0,0
CFI at 0,2
LGB at 2,3
MJGD at 3,0

Como sempre, a resposta mais curta ganha

morpen
fonte
6
Bem-vindo ao PPCG! Bom primeiro desafio!
AdmBorkBork
2
Similar , a única diferença real parece ser a inclusão do local na saída.
FryAmTheEggman
@ NL628 Sim, todas as palavras de pesquisa estão garantidas no quebra-cabeça. Se houver mais de uma ocorrência, você poderá produzi-la nas duas vezes ou ignorá-la na segunda, depende de você.
morpen
@JonathanAllan Ótima idéia. Vou atualizá-lo como você sugeriu.
morpen
1
@RickHitchcock Sim, deve :)
morpen

Respostas:

4

JavaScript (Node.js) , 154 152 150 141 bytes

  • graças a Arnauld por reduzir em 2 bytes

retorna uma matriz de locais (era uma string com novas linhas antes)

(b,w)=>w.map(s=>[...b].map((_,p)=>[1,-1,r=b.search`
`,-r,~r,++r,-~r,~r].map(d=>[...s].every((c,i)=>c==b[p+d*i])?s+=" at "+[p/r|0,p%r]:0))&&s)

Experimente online!

DanielIndie
fonte
3

Python 2 , 213 bytes

lambda a,W:[(w,i,j)for w in W for i in R(L(a))for j in R(L(a[0]))for U in R(9)if U-4and g(i,j,U/3-1,U%3-1,a).find(w)==0]
g=lambda i,j,u,v,a,s='':L(a)>i>=0<=j<L(a[0])and g(i+u,j+v,u,v,a,s+a[i][j])or s
L=len;R=range

Experimente online!

gtoma um local de partida i,je uma direção u,ve, por recursão, extrai a sequência iniciando nesse local nessa direção.

fdepois visita cada local i,je direção inicial U/3-1,U%3-1e verifica cada palavra wpara ver se a sequência resultante começa com w.

Chas Brown
fonte
2

Python 3 , 149 147 bytes

def g(b,w):h=b.find('\n')+1;return[f'{y} at {i//h},{i%h}'for y in w for i in range(len(b))for d in(1,h+1,h,h-1,-1,~h,-h,1-h)if y==b[i::d][:len(y)]]

Experimente online!

Versão ungolfed

def g(b,w):
    h = b.find('\n') + 1                              # width of a row plus the '\n'
    a = []
    for y in w:                                       # iterate over the words
        for i in range(len(b)):                       #   iterate over the game board
            for d in(1,h+1,h,h-1,-1,~h,-h,1-h):       #     for each possible direction
                if y==b[i::d][:len(y)]:               #       see if the word matches
                    a.append(f'{y} at {i//h},{i%h}')
    return a

A idéia principal é que b[i::d]selecione uma fatia do tabuleiro de jogo. A fatia começa como posição ie se estende na direção d. Por exemplo, d = h+1corresponde à diagonal sudeste, enquanto d = ~hque é igual a -h-1corresponde à diagonal noroeste. [:len(y)] corta a fatia no mesmo comprimento que a palavra que está sendo pesquisada.

RootTwo
fonte