Is this word on the boggle board?

Question

Introduction

After a day of drinking and watching the world cup, you sit down to play friendly game of boggle. Tempers rise as you are accused of wasting everyone's time with nonsense words that aren't even on the board! You may be seeing double, but surely you're thinking straight enough to write a program that will verify that your words are on the board.

Your Task

Write a program, script, or function that takes a boggle board and a word as input, and returns True if the word is on the board and False if the word isn't.

The input will be in the form of six \n delimited lines. The first five lines will comprise the 5x5 boggle board and will each contain five capital letters. The sixth line will contain the word-in-question, also in all capital letters.

Sample input:

AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER

The output can be anything that unambiguously signifies True or False in your programming language of choice and adheres to standard conventions of zero, null, and empty signifying False.

Sample output for above input:

1

I/O Guidelines

• The input may be read from stdin, and answer output to stdout.

Or

• The input may be a single string argument to a function, and answer be the return value of that function.

Boggle Rules

• A word is 'on the board' if you can construct the word via a path of consecutive, adjacent, non-repeating tiles on the board.
• A tile is considered adjacent to the eight tiles that surround it (diagonal paths are allowed). Tiles on the edge of the board are adjacent to only five tiles. Tiles in the corner are adjacent to only three.
• Consecutive letters in the word must be adjacent, the ith letter in the word must be adjacent to the i-1th and i+1th.
• A letter may appear in a word more than once, but you cannot use the same square on the boggle board more than once per word.
• The online boggle site wordsplay.net may be useful if you have never played boggle before, but want to get a feel for these rules.

Unlike regular boggle:

• You do NOT have to worry about the word being a valid English word.
• There will be NO Qu single tile.
• The word-in-question may be of any length > 0

Example

On the board of

AJNES
TNFTR
LSAIL
UDNEX
EQGMM

These words should return True: FATE, DATING, STANDS, LIFTS.

These words should return False: SADDEN, SULTANS, EXIST, SUEDE, QUEST

This is a code-golf challenge, so shortest code wins!

Answer 1

GolfScript, 74 characters

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

The input must be given on STDIN. Prints the number of valid paths on the board, i.e. 0 for none and a positive number (true) else.

You can test the example online.

Code with some comments:

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

Answer 2

Javascript (E6) 137 160 175 190

Less than 2*Golfscript. Moral victory ...

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)

Edit Golfed code reorganization. Again and again

Ungolfed Last version, a bit tricky to follow

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 First version , should be clearer

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

Test

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

Output:

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

Answer 3

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

Replacing ... (b[i]==w[0])*any ... with ... b[i]==w[0]and any ... gives much better performance at the cost of 2 characters.

Answer 4

J - 75 char

Eugh, this one looks nasty. And not even tying with Golfscript! This is a function taking a string as its sole argument. You can use any one-character delimiter as long as it's found at the end of each line, including the last.

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

An explanation follows. Note that the function can be cleaved into 5 distinct top-level parts, each separated by @, so we will treat each of those parts separately, from right to left.

• (<;._2) - This splits the lines up on the newlines/separator characters. It uses the character at the end of the string as the character on which to split. We put everything into boxes (<) because if we don't we get some padding issues when J gives us the result back.

• (((<@#:i.)5 5)<@#~&,"2{:=/&:>}:) - For each letter in the word to check, create a list of indices in the Boggle board where one can find that letter.

  • {: is the last split piece (the word to check) and }: is everything but the last (the Boggle board).

  • &:> opens up the boxes we made previously, with the useful byproduct of turning }: into a 2D array of characters. =/ then makes a copy of this Boggle board for each letter in the word, and turns the positions into booleans depending on whether the letter in the board matched that letter in the word.

  • ((<@#:i.)5 5) is a short way of expressing a 5x5 array of indices. x#:y is converts y into an array of the base x representation. (Well, almost. The truth is more complex, but this works for our purposes.)

  • <@#~&,"2 - For each letter's resulting boolean matrix, collect all the correspondingly true indices together. "2 makes everything work on on the right results, #~&, does the selecting, and <@ collects each result into a box to prepare for the next step.

• { - This verb, used monadically, is called Catalogue, and it takes a list of boxes as argument. It combines the insides of each box in every possible way. So e.g. a catalogue on some boxes containing the strings "AB" and "abc" would give the results "Aa", "Ab", "Ac", "Ba", "Bb", "Bc".

  Running this on our boxed list of lists of indices makes every possible combination of indices. This can be a big set if there the word is long and there are many repeated letters, but also empty if any letter is not on the board. We also note that we reuse tiles in some of these paths: we will account for this later.

• ([:*/"1^:2(2(=*)@-/\>@~.)S:1) - Here we check each path to see if it's valid.

  • (...)S:1 applies the (...) to each path and collects the results into a flat list. This is crucial because the result of { is a multi-dimensional array, and we don't care about the structure of that array, just its contents at each box.

  • 2(=*)@-/\> gives a 1 if each coordinate of each index is at most one away from the one following it, and 0 otherwise. The 2 and the /\ are responsible for doing this pairwise.

  • */"1^:2 logical-ANDs these all together at the end. The [: part is a structural thing in J, don't worry about it.

  • Adding @~. to the > is actually a clever way to exclude paths with repeated entries. ~. takes the unique items of a list, so the list is shortened if it self-intersects, and shorter lists get automatically padded with 0s when they're put together, like the way that the results are combined as they come out of S:. This is ultimately shorter than explicitly excluding self-intersecting paths.

• +/ - Finally, we simply add everything together at the end. The result is the number of valid paths that make the word on the board, with 0 meaning no paths, i.e. this word is not on the board. For the cost of one character, we can write +./ (logical-ORing everything together) instead, which will explicitly give a boolean 1 or 0.

Here are some example runs. You can get the J interpreter at jsoftware.com or try it online at 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

Answer 5

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

I thought Prolog might be a good language for this one, with the built-in backtracking support, but I guess it's more handicapped by needing a variable for almost every computed value.

Tested with GNU Prolog; should be compliant with 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, _, []).