Introducción

Después de un día de beber y ver la copa del mundo, te sientas a jugar un juego amistoso de boggle. Los ánimos aumentan cuando se le acusa de perder el tiempo de todos con palabras sin sentido que ni siquiera están en el tablero. Es posible que esté viendo el doble, pero seguramente está pensando lo suficiente como para escribir un programa que verifique que sus palabras estén en la pizarra.

Tu tarea

Escriba un programa, secuencia de comandos o función que tome una pizarra y una palabra como entrada, y devuelva True si la palabra está en la pizarra y False si la palabra no lo está.

La entrada tendrá la forma de seis \nlíneas delimitadas. Las primeras cinco líneas comprenderán el tablero de boggle 5x5 y cada una contendrá cinco letras mayúsculas. La sexta línea contendrá la palabra en cuestión, también en mayúsculas.

Entrada de muestra:

AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER

La salida puede ser cualquier cosa que signifique inequívocamente Verdadero o Falso en el lenguaje de programación de su elección y se adhiera a las convenciones estándar de cero, nulo y vacío que significa Falso.

Salida de muestra para la entrada anterior:

1

Pautas de E / S

• La entrada puede leerse desde stdin, y responder la salida a stdout.

O

• La entrada puede ser un argumento de cadena única para una función, y la respuesta será el valor de retorno de esa función.

Reglas de Boggle

• Una palabra está 'en el tablero' si puede construir la palabra a través de una ruta de mosaicos consecutivos, adyacentes y no repetitivos en el tablero.
• Un mosaico se considera adyacente a los ocho mosaicos que lo rodean (se permiten caminos diagonales). Las fichas en el borde del tablero son adyacentes a solo cinco fichas. Los azulejos en la esquina son adyacentes a solo tres.
• Las letras consecutivas en la palabra deben ser adyacentes, la iletra th en la palabra debe ser adyacente a la i-1th y i+1th.
• Una letra puede aparecer en una palabra más de una vez, pero no puede usar el mismo cuadrado en el tablero de boggle más de una vez por palabra.
• El sitio en línea de boggle wordsplay.net puede ser útil si nunca antes ha jugado a boggle, pero quiere tener una idea de estas reglas.

A diferencia del boggle regular:

• NO tiene que preocuparse de que la palabra sea una palabra válida en inglés.
• No habrá un Qusolo mosaico.
• La palabra en cuestión puede tener cualquier longitud> 0

Ejemplo

En el tablero de

AJNES
TNFTR
LSAIL
UDNEX
EQGMM

Estas palabras deben devolver True: FATE, DATING, STANDS, LIFTS.

Estas palabras deberían devolver False: SADDEN, SULTANS, EXIST, SUEDE, QUEST

Este es un desafío de código de golf, por lo que gana el código más corto.

GolfScript, 74 caracteres

:^n%5>)]){{^@==}+29,\,{{+}+1$/}%\;}/{:s$..&=[s{.@-\}*;]1567`{7&.~)}%-!&},,

La entrada debe darse en STDIN. Imprime el número de rutas válidas en el tablero, es decir, 0ninguna y un número positivo (verdadero) más.

Puedes probar el ejemplo en línea .

Código con algunos comentarios:

:^              # assign the input to variable ^
n%              # split at newlines
5>              # truncate array such that [WORD] remains
)])             # prepares [[]] and WORD on the stack

# the following loop generates all possible paths (valid and invalid ones)
# by looking up all index combinations which yield the correct word
{               # loop over all characters
  {^@==}+29,\,  # get all indices of current character in the board
  {{+}+1$/}%\;  # append any index to all lists in the result set
}/              # end loop

# filter the results list for valid paths
{               # {...}, -> apply filter
  :s            # save path to variable s
  $..&=         # check if all numbers in path are unique
  [s{.@-\}*;]   # calculate differences along the path
  1567`{7&.~)}% # generate the array [1 -1 5 -5 6 -6 7 -7] of valid
                # differences
  -!            # check if all differences were valid
  &             # are both conditions fulfilled?
},              # end of filter block

,               # count the number of remaining paths

Javascript (E6) 137 160 175 190

Menos de 2 * Golfscript. Victoria moral ...

F=a=>[...a].some((e,p,b)=>(Q=(p,n)=>p>29||b[p]!=b[n]||(b.r|=!b[++n])||(b[p]=b[n+~[1,5,6,7].map(q=>Q(p+q,n)|Q(p-q,n),b[p]=0)]))(p,30)&b.r)

Edite la reorganización del código Golfed. Una y otra vez

Ungolfed Última versión, un poco difícil de seguir

F = a => 
  [...a] // input string to array, 30 chars of board then the target word
  .some ( // use some to scan the board, return true when found
      (e,p,b)=> // params to callback: element, position, complete array 
      (         // NB array b has no .r property, so use it for return value (it's undefined at start) 
        Q = (p,n) =>         // Scan function, p=position in board, n=nth char of target word
          p > 29 ||          // Chaek if going outside the board to the target word
          b[p] != b[n] ||    // if invalid char at current position, return
          (b.r |= !b[++n]) ||  // if at end of target, set r to 1 and return (also increment n )
          (                  // else... (NB next tree lines are coalesced in golfed code)
            b[p] = 0,        // remove current char (to avoid reusing) 
            [1,5,6,7].map( q => Q(p+q,n)|Q(p-q,n)), // recursive call for + - 1,5,6,7
            b[p] = b[n-1]    // put current char into array again 
          )
      )(p,30) & b.r // initial position 0 in target word is 30 in the array
  ) 

Primera versión de Ungolfed , debería ser más clara

F = a => (
  b = a.split('\n'),
  w = b.pop(),
  r = 0,
  Q = (p, n) => 
    (r |= !w[n]) || 
    (
      b[p] = 0,
      [1,5,6,7,-1,-5,-6,-7].map( q => b[q+=p]==w[n] && Q(q,n+1)),
      b[p] = w[n-1]
    ),
  b = [...b+''],
  b.map((e, p) => e==w[0] && Q(p,1)),
  r
)

Uso

F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\nLIFTS\nDAFTER")

Prueba

['DAFTER', 'STANDS', 'LIFTS', 'FATE', 'DATING' ,
 'SADDEN','SULTANS', 'EXIST', 'SUEDE', 'QUEST']
.map(w => [w, F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\n" +w)])

Salida:

[["DAFTER", true], ["STANDS", true], ["LIFTS", true], ["FATE", true], ["DATING", true], 
["SADDEN", false], ["SULTANS", false], ["EXIST", false], ["SUEDE", false], ["QUEST", false]]

Python, 207 204 203

g=raw_input
r=range
b=''.join(g()for _ in r(5))
w=g()
s=lambda b,w,i:0<=i<25and(not w or(b[i]==w[0])*any(s(b[:i]+'_'+b[i+1:],w[1:],i+j+k*5-6)for j in r(3)for k in r(3)))
print any(s(b,w,i)for i in r(25))

Reemplazar ... (b[i]==w[0])*any ...con ... b[i]==w[0]and any ...ofrece un rendimiento mucho mejor a costa de 2 caracteres.

J - 75 char

Eugh, este se ve desagradable. ¡Y ni siquiera empatando con Golfscript! Esta es una función que toma una cadena como único argumento. Puede usar cualquier delimitador de un carácter siempre que se encuentre al final de cada línea, incluida la última.

+/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2)

Sigue una explicación. Tenga en cuenta que la función se puede dividir en 5 partes distintas de nivel superior, cada una separada por @, por lo que trataremos cada una de esas partes por separado, de derecha a izquierda.

• (<;._2)- Esto divide las líneas en las líneas nuevas / caracteres separadores. Utiliza el carácter al final de la cadena como el carácter en el que se divide. Ponemos todo en cajas ( <) porque si no lo hacemos, tenemos algunos problemas de relleno cuando J nos devuelve el resultado.

• (((<@#:i.)5 5)<@#~&,"2{:=/&:>}:) - Para cada letra de la palabra a verificar, cree una lista de índices en el tablero de Boggle donde pueda encontrar esa letra.

  • {:es la última pieza dividida (la palabra para verificar) y }:es todo menos la última (el tablero de Boggle).

  • &:>abre las cajas que hicimos anteriormente, con el subproducto útil de convertirse }:en una matriz 2D de personajes. =/luego hace una copia de este tablero de Boggle para cada letra de la palabra y convierte las posiciones en booleanos dependiendo de si la letra del tablero coincide con esa letra en la palabra.

  • ((<@#:i.)5 5)es una forma corta de expresar una matriz de índices 5x5. x#:yse convierte yen una matriz de la xrepresentación base . (Bueno, casi. La verdad es más compleja, pero esto funciona para nuestros propósitos).

  • <@#~&,"2- Para cada matriz booleana resultante de cada letra, recopile todos los índices verdaderos correspondientes. "2hace que todo funcione con los resultados correctos, #~&,realiza la selección y <@recopila cada resultado en un cuadro para prepararse para el siguiente paso.

• {- Este verbo, usado monádicamente, se llama Catálogo, y toma una lista de cuadros como argumento. Combina el interior de cada caja de todas las formas posibles. Entonces, por ejemplo, un catálogo en algunas cajas que contienen las cadenas "AB" y "abc" daría los resultados "Aa", "Ab", "Ac", "Ba", "Bb", "Bc".

  Ejecutar esto en nuestra lista en caja de listas de índices hace todas las combinaciones posibles de índices. Este puede ser un conjunto grande si la palabra es larga y hay muchas letras repetidas, pero también está vacía si alguna letra no está en el tablero. También notamos que reutilizamos mosaicos en algunas de estas rutas: explicaremos esto más adelante.

• ([:*/"1^:2(2(=*)@-/\>@~.)S:1) - Aquí verificamos cada ruta para ver si es válida.

  • (...)S:1aplica el (...)a cada ruta y recopila los resultados en una lista plana. Esto es crucial porque el resultado {es una matriz multidimensional, y no nos importa la estructura de esa matriz, solo su contenido en cada cuadro.

  • 2(=*)@-/\>da un 1 si cada coordenada de cada índice está como máximo a una distancia de la siguiente, y 0 en caso contrario. El 2y el /\son responsables de hacer esto en parejas.

  • */"1^:2lógico-ANDs todos juntos al final. La [:parte es algo estructural en J, no te preocupes por eso.

  • Agregar @~.a esto >es en realidad una forma inteligente de excluir rutas con entradas repetidas. ~.toma los elementos únicos de una lista, por lo que la lista se acorta si se cruza automáticamente, y las listas más cortas se rellenan automáticamente con 0 cuando se juntan, como la forma en que se combinan los resultados a medida que salen S:. Esto es, en última instancia, más corto que excluir explícitamente las rutas auto intersectantes.

• +/- Finalmente, simplemente sumamos todo al final. El resultado es el número de rutas válidas que hacen que la palabra en el tablero, con 0 significa que no hay rutas, es decir, esta palabra no está en el tablero. Por el costo de un carácter, podemos escribir +./(OR-lógico todo junto) en su lugar, lo que dará explícitamente un booleano 1 o 0.

Aquí hay algunos ejemplos de carreras. Usted puede obtener el intérprete J en jsoftware.com o probarlo en línea en tryj.tk .

   NB. the  0 : 0 ... )  thing is how you do multiline strings in J
   +/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2) 0 : 0
AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER
)
1
   b =: +/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2)
   b 'AJNES TNFTR LSAIL UDNEX EQGMM FATE '    NB. any separator will do
1
   b 'AJNES TNFTR LSAIL UDNEX EQGMM SADDEN '  NB. not on the board
0
   b 'AJNES TNFTR LSAIL UDNEX EQGMM SANDS '   NB. self-intersecting path
0
   b 'AJNES TNFTR LSAIL UDNEX EQGMM MEND '    NB. multiple paths
2

Prólogo - 315

r(L):-get_char(C),(C='\n',!,L=[];r(T),L=[C|T]).
b(0,[]):-!.
b(N,[R|T]):-M is N-1,r(R),b(M,T).
d(-1). d(0). d(1).
d([A,B],[C,D]):-d(X),C is A+X,d(Y),D is B+Y.
f([L|W],B,P,U):-P=[X,Y],nth(Y,B,R),nth(X,R,L),\+member(P,U),(W=[];d(P,Q),f(W,B,Q,[P|U])).
m:-b(5,B),r(W),f(W,B,_,[]),write(t);write(f).
:-initialization(m).

Pensé que Prolog podría ser un buen lenguaje para este, con el soporte de retroceso incorporado, pero supongo que es más perjudicado al necesitar una variable para casi todos los valores calculados.

Probado con GNU Prolog; debe cumplir con ISO Prolog.

Sin golf:

get_line(Line) :-
    get_char(C),
    (   C='\n', !, Line=[]
    ;   get_line(Tail), Line=[C|Tail]
    ).

% The cut prevents recursion to help_get_board(-1, MoreRows)
% (and golfs one character shorter than putting N>0 in the second rule).
help_get_board(0, []) :- !.
help_get_board(N, [Row|Tail]) :-
    M is N-1, get_line(Row), help_get_board(M, Tail).

% The golfed version doesn't define an equivalent to get_board/1.
% help_get_board(5,Board) is used directly instead.
get_board(Board) :- help_get_board(5,Board).

small(-1). small(0). small(1).
step([X1,Y1],[X2,Y2]) :-
    small(DX), X2 is X1+DX,
    small(DY), Y2 is Y1+DY.

% The golfed version doesn't define an equivalent to letter_at/3.
% See find_word/4.
letter_at([X,Y], Letter, Board) :-
    nth(Y, Board, Row),
    nth(X, Row, Letter).

find_word([Letter|Word], Board, Pos1, Used) :-
%    letter_at(Pos1, Letter, Board),  % "inlined" to next three lines:
    ( Pos1 = [X,Y],
      nth(Y, Board, Row),
      nth(X, Row, Letter) ),
    \+member(Pos1, Used),
    (   Word=[]
    ;
        step(Pos1, Pos2),
        find_word(Word, Board, Pos2, [Pos1|Used])
    ).

main :-
    get_board(Board),
    get_line(Word),
    % Begin at any position. Initially no positions are "Used".
    find_word(Word, Board, _, []).