introduction

Après une journée de beuverie et de regarder la coupe du monde, vous vous asseyez pour jouer à un jeu amical de boggle. Les esprits augmentent parce que vous êtes accusé de perdre tout le temps de tout le monde avec des mots absurdes qui ne figurent même pas sur le tableau! Vous voyez peut-être double, mais vous pensez sûrement assez pour écrire un programme qui permettra de vérifier que vos mots sont bien au tableau.

Ta tâche

Ecrivez un programme, un script ou une fonction qui utilise un tableau erroné et un mot en entrée et renvoie Vrai si le mot est sur le tableau et Faux si le mot ne l’est pas.

L'entrée se présentera sous la forme de six \nlignes délimitées. Les cinq premières lignes comprendront le tableau 5x5 et contiendront chacune cinq lettres majuscules. La sixième ligne contiendra le mot en question, également en toutes lettres majuscules.

Exemple de saisie:

AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER

La sortie peut être tout ce qui signifie sans ambiguïté Vrai ou Faux dans le langage de programmation de votre choix et qui respecte les conventions standard zéro, null et vide qui signifie Faux.

Exemple de sortie pour l'entrée ci-dessus:

1

Directives I / O

• L'entrée peut être lue à partir de stdin et la réponse à stdout.

Ou

• L'entrée peut être un argument de chaîne unique à une fonction et answer à la valeur de retour de cette fonction.

Règles Boggle

• Un mot est «sur le tableau» si vous pouvez le construire via un chemin composé de tuiles consécutives, adjacentes et non répétitives.
• Une tuile est considérée comme adjacente aux huit tuiles qui l’entourent (les chemins diagonaux sont autorisés). Les tuiles sur le bord du plateau sont adjacentes à seulement cinq tuiles. Les tuiles dans le coin sont adjacentes à seulement trois.
• Les lettres consécutives du mot doivent être adjacentes, la ith lettre du mot doit être adjacentes aux i-1th et i+1th.
• Une lettre peut apparaître dans un mot plus d'une fois, mais vous ne pouvez pas utiliser le même carré sur le tableau d'affichage plus d'une fois par mot.
• Le site boggle en ligne wordsplay.net peut être utile si vous n'avez jamais joué au boggle auparavant, mais souhaitez avoir une idée de ces règles.

Contrairement à l'étranglement normal:

• Vous n'avez PAS à vous inquiéter du fait que le mot soit un mot anglais valide.
• Il n'y aura pas de Qutuile simple.
• Le mot en question peut avoir n'importe quelle longueur> 0

Exemple

Au conseil de

AJNES
TNFTR
LSAIL
UDNEX
EQGMM

Ces mots doivent renvoyer True: FATE, DATING, STANDS, LIFTS.

Ces mots doivent renvoyer False: SADDEN, SULTANS, EXIST, SUEDE, QUEST

Ceci est un défi de code-golf, donc le code le plus court gagne!

GolfScript, 74 caractères

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

L'entrée doit être donnée sur STDIN. Imprime le nombre de chemins valides sur le tableau, c.-à-d.0 à- pour aucun et un nombre positif (vrai) sinon.

Vous pouvez tester l'exemple en ligne .

Code avec quelques commentaires:

:^              # 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

Moins de 2 * Golfscript. Victoire morale ...

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)

Modifier la réorganisation du code golfé. Encore et encore

Ungolfed Dernière version, un peu difficile à suivre

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
  ) 

Ungolfed Première version, devrait être plus clair

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
)

Usage

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

Tester

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

Sortie:

[["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))

Remplacer ... (b[i]==w[0])*any ...par ... b[i]==w[0]and any ...donne une bien meilleure performance au prix de 2 caractères.

J - 75 caractères

Euh, celui-ci a l'air méchant. Et même pas lié avec Golfscript! Ceci est une fonction prenant une chaîne comme unique argument. Vous pouvez utiliser n'importe quel séparateur à un caractère à condition qu'il se trouve à la fin de chaque ligne, y compris la dernière.

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

Une explication suit. Notez que la fonction peut être scindée en 5 parties de niveau supérieur distinctes, chacune étant séparée par @, nous traiterons donc chacune de ces parties séparément, de droite à gauche.

• (<;._2)- Cela divise les lignes sur les caractères de nouvelle ligne / séparateur. Il utilise le caractère à la fin de la chaîne comme caractère à scinder. Nous mettons tout dans des boîtes ( <) car sinon, nous avons des problèmes de bourrage lorsque J nous renvoie le résultat.

• (((<@#:i.)5 5)<@#~&,"2{:=/&:>}:) - Pour chaque lettre du mot à vérifier, créez une liste d’index dans le tableau Boggle où l’on peut trouver cette lettre.

  • {:est la dernière pièce fendue (le mot à vérifier) ​​et }:est tout sauf la dernière (le tableau Boggle).

  • &:>ouvre les boîtes que nous avons faites précédemment, avec le sous-produit utile de transformer }:en un tableau 2D de caractères. =/fait ensuite une copie de ce tableau Boggle pour chaque lettre du mot et transforme les positions en booléens selon que la lettre du tableau correspond ou non à cette lettre.

  • ((<@#:i.)5 5)est un moyen court d'exprimer un tableau d'indices 5x5. x#:yest converti yen un tableau de la xreprésentation de base . (Eh bien, presque. La vérité est plus complexe, mais cela fonctionne pour nos besoins.)

  • <@#~&,"2- Pour la matrice booléenne résultante de chaque lettre, rassemblez tous les indices vrais correspondants. "2fait en sorte que tout fonctionne avec les bons résultats, #~&,effectue la sélection et <@rassemble chaque résultat dans une boîte pour préparer l'étape suivante.

• {- Ce verbe, utilisé de façon monadique, s'appelle Catalogue et prend une liste de cases en argument. Il combine l'intérieur de chaque boîte de toutes les manières possibles. Ainsi, par exemple, un catalogue sur certaines boîtes contenant les chaînes "AB" et "abc" donnerait les résultats "Aa", "Ab", "Ac", "Ba", "Bb", "Bc".

  En exécutant ceci sur notre liste encadrée de listes d’indexes, chaque combinaison d’index est possible. Cela peut être un gros jeu si le mot est long et qu'il y a beaucoup de lettres répétées, mais aussi vide si aucune lettre ne figure au tableau. Nous notons également que nous réutilisons les carreaux dans certains de ces chemins: nous en rendrons compte plus tard.

• ([:*/"1^:2(2(=*)@-/\>@~.)S:1) - Ici, nous vérifions chaque chemin pour voir s'il est valide.

  • (...)S:1applique le (...)à chaque chemin et rassemble les résultats dans une liste simple. Ceci est crucial car le résultat {est un tableau multi-dimensionnel, et nous ne nous soucions pas de la structure de ce tableau, mais de son contenu à chaque case.

  • 2(=*)@-/\>donne un 1 si chaque coordonnée de chaque index est au plus éloignée de celle qui le suit, et 0 sinon. Le 2et le /\sont responsables de le faire par paire.

  • */"1^:2ET-logiques ceux-ci tous ensemble à la fin. La [:partie est structurelle en J, ne vous inquiétez pas.

  • Ajouter @~.à >est un moyen astucieux d’exclure des chemins avec des entrées répétées. ~.prend les éléments uniques d'une liste, de sorte que la liste est raccourcie si elle se croise automatiquement et que les listes plus courtes sont automatiquement complétées par des 0 lorsqu'elles sont assemblées, comme la façon dont les résultats sont combinés au fur et à mesure qu'ils sortent S:. Cela est finalement plus court que d’exclure explicitement les chemins qui se croisent.

• +/- Enfin, nous ajoutons simplement tout à la fin. Le résultat est le nombre de chemins valides qui composent le mot sur le tableau, 0 signifiant aucun chemin, c'est-à-dire que ce mot n'est pas sur le tableau. Pour le coût d'un caractère, nous pouvons +./plutôt écrire (tout mettre ensemble), ce qui donnera explicitement un booléen 1 ou 0.

Voici quelques exemples de pistes. Vous pouvez obtenir l'interprète J à jsoftware.com ou essayer en ligne à 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

Prolog - 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).

Je pensais que Prolog pourrait être un bon langage pour celui-ci, avec le support de retour arrière intégré, mais je suppose qu'il est plus handicapé par le besoin d'une variable pour presque chaque valeur calculée.

Testé avec GNU Prolog; devrait être conforme à ISO Prolog.

Ungolfed:

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, _, []).