Word Search Solver

13

Ayer me pregunté si podría escribir un programa para revisar una búsqueda de palabras y generar las respuestas. En realidad fue sorprendentemente fácil. Ahora me pregunto qué tan pequeños podemos llegar a ser.

Reglas

  • Su primera entrada es una cadena o colección de n líneas, cada una de las cuales tiene una longitud de n caracteres.
  • Su segunda entrada es una lista de palabras en cualquier formato para encontrar en el rompecabezas
  • Todas las palabras en la lista de búsqueda están garantizadas para estar en el rompecabezas
  • Las palabras pueden orientarse en cualquiera de las cuatro direcciones cardinales, así como en diagonal tanto hacia adelante como hacia atrás
  • Solo los caracteres en mayúscula AZ estarán presentes en el rompecabezas
  • Su código debe encontrar cada palabra en la cadena de búsqueda y generar la posición de coordenadas de la letra inicial, donde 0,0 es el carácter superior izquierdo.
  • En el caso de que localice más de una instancia de la misma palabra, puede manejarla como desee. Envíelo varias veces, o solo una vez, depende de usted

Ejemplos / Casos de prueba

Dada la siguiente tabla:

ABCD
EFGH
IJKL
MNOP

Y la siguiente cadena de búsqueda:

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

Su programa debería generar lo siguiente, en cualquier orden:

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 siempre, la respuesta más corta gana

morpen
fuente
66
Bienvenido a PPCG! ¡Buen primer desafío!
AdmBorkBork
2
Similar , la única diferencia real parece ser la inclusión de la ubicación en la salida.
FryAmTheEggman
@ NL628 Sí, todas las palabras de búsqueda están garantizadas para estar en el rompecabezas. Si hay más de una ocurrencia, puede emitirla las dos veces o ignorarla la segunda, depende de usted.
morpen
@ JonathanAllan Gran idea. Lo actualizaré como sugirió.
morpen
1
@RickHitchcock Sí, debería :)
morpen

Respuestas:

4

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

  • gracias a Arnauld por reducir en 2 bytes

devuelve una matriz de ubicaciones (antes era una cadena con nuevas líneas)

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

Pruébalo en línea!

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

Pruébalo en línea!

gtoma una ubicación inicial i,jy una direcciónu,v y, mediante recursión, extrae la cadena que comienza en esa ubicación en esa dirección.

fluego visita cada ubicación i,jy dirección de inicio U/3-1,U%3-1y comprueba cada palabra wpara ver si la cadena resultante comienza con w.

Chas Brown
fuente
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)]]

Pruébalo en línea!

Versión sin golf

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

La idea principal es que b[i::d]selecciona una porción del tablero de juego. El corte comienza como posición iy se extiende en la dirección d. Por ejemplo, d = h+1corresponde a la diagonal sureste, mientras d = ~hque, que es lo mismo -h-1, corresponde a la diagonal noroeste. [:len(y)] corta el corte en la misma longitud que la palabra que se busca.

RootTwo
fuente