Can an ant spell words by walking on cube?

Question

Write a function that takes two parameters: a positive integer n and a list of words.

Given a cube of n-by-n-by-n units, assign a random letter (A-Z) to each surface unit. (For a 3x3x3 cube, there would be 9 surface units on each face.)

Then determine whether it's possible for an ant walking along the surface (with the ability to cross faces) to spell each of the supplied words. Assume that to spell a word, the letters must be up/down or left/right adjacent, but not necessarily on the same face. [Edit, for clarity: The ant can reverse its path and use letters more than once. Each surface unit counts as one character, so to spell a word with repeated letters (e.g. "see") the ant would have to visit three adjacent units.]

The function should output two things:

1) Each of the letters on each face, in such a way that the topology can be inferred. For instance, for a 2x2x2 cube, an acceptable output would look like:

   QW
   ER
TY OP UI
DF JK XC
   AS
   GH
   LZ
   VB

2) Each of the words, along with a boolean representing whether it's possible for the ant to spell the word by walking along the surface of the cube. For instance:

1 ask
0 practical
1 pure
0 full

Bonus challenge (will not factor into score, just for fun): Instead of n representing only the size of the cube, let n also represent the dimensionality of the shape. So, an n of 2 would yield a 2x2 square; an n of 3 would yield a 3x3x3 cube; and an n of 4 would yield a 4x4x4x4 tesseract.

Answer 1

Ruby, 272 bytes

Two unnecessary newlines are added to the code either side of nested function g to improve readability. These are excluded from the score. The characters f= which assign the anonymous function to a variable are also excluded.

Output format is 0 or 1 per the question instead of Ruby's native true and false. A newline (rather than a space) is used to separate the boolean and the word. My understanding is that this is an acceptable interpretation of the output requirements, but if not, the impact on the byte count would be minor.

f=->n,l{c=''
x=[p=6*n,1,-p,-1]
(m=3*p*n).times{|i|c<<(5+i/n%6-i/n/p&6==6?65+rand(26):i%p==p-1?10:46)}
q=m+3*n
puts c

g=->w,i,d{w==''?$r=1:c[i]<?A?g[w,(i+x[d])%q,d^1]:w[0]==c[i]&&4.times{|j|g[w[1..-1],(i+x[j])%q,j^1]}}

l.each{|w|$r=0
m.times{|i|c[i]>?@&&g[w,i,0]}
puts $r,w}}

Output

After about 50 calls like this:

f[4,['PPCG','CODE','GOLF','ANT','CAN','CUBE','WORD','WALK','SPELL']]

I finally got the following output with 2 hits. ANT is at the bottom right going upwards, and the AN is shared by CAN, with the C wrapping round to top left.

....KCAAXRHT...........
....ALRZXRKL...........
....NDDLCMCT...........
....ETQZHXQF...........
........FYYUSRZX.......
........CFNPAUVX.......
........ZTJVHZVQ.......
........AUWKGVMC.......
............XWKSDWVZ...
............DPLUVTZF...
............DMFJINRJ...
............ZRXJIAFT...
0
PPCG
0
CODE
0
GOLF
1
ANT
1
CAN
0
CUBE
0
WORD
0
WALK
0
SPELL

Explanation

The particular unfolding of the cube selected, was chosen partly for its ease of drawing, but mainly for its ease of searching.

The non-alphabet characters (the dots plus the newline at the end of each line) are an important part of the field where the ant may be found walking.

Searching is performed by the recursive function g, which is nested in function f . If the word passed is an empty string the search is complete and $r is set to 1. If the ant is on a letter square which corresponds to the first letter of the word, the search is continued in all four directions: the function is called again with the word shortened by removing its first letter. In this case the direction parameter is ignored. The moving is done by recursively calling with the cell index altered by the values in x. The result of the addition is taken modulo the size of the grid plus an extra half line. This means that the bottom line wraps round to the top and vice versa, with the correct horizontal offset.

If the ant is on a non-letter square, she must zigzag in a staircase motion until she finds a letter square. She will zizag in southeast or northwest direction. This is simulated by recursive calls with the d parameter being XORed with 1 each time to keep track of her movement. Until she reaches the next letter square, there is no shortening of the input word. Conveniently, this may be done by the same recursion as is used when we are searching in the area with letters. The difference is, the recursion has only one branch when the ant is in the whitespace area, as opposed to 4 in the letter area.

Commented code

->n,l{                                   #n=square size, l=list of words to search
  c=''                                   #empty grid
  x=[p=6*n,1,-p,-1]                      #offsets for south, east, north, west. p is also number of characters per line
  (m=3*p*n).times{|i|                    #m=total cells in grid. for each cell
    c<<(5+i/n%6-i/n/p&6==6?              #apppend to c (according to the formula)
      65+rand(26):                       #either a random letter
      i%p==p-1?10:46)                    #or a "whitespace character" (newline, ASCII 10 or period, ASCII 46)
  }
  q=m+3*n                                #offset for vertical wraparound = grid size plus half a row.                           
  puts c                                 #print grid

  g=->w,i,d{                             #search function. w=word to search for, i=start index in grid, d=direction
    w==''?                               #if length zero, already found,
      $r=1:                              #so set flag to 1. Else
      c[i]<?A?                           #if grid cell is not a letter
        g[w,(i+x[d])%q,d^1]:             #recursively call from the cell in front, with the direction reflected in NW-SE axis
        w[0]==c[i]&&                     #else if the letter on the grid cell matches the start of the word
          4.times{|j|                    #for each direction (iterate 4 times, each time a different direction is "in front")
            g[w[1..-1],(i+x[j])%q,j^1]}  #recursively call from the cell in front. Chop first letter off word. 
   }                                       #Direction parameter is XORed (reflected in NW-SE axis) in case ant hits whitespace and has to zigzag.

   l.each{|w|                            #for each word in the list
     $r=0                                #set global variable $r to zero to act as a flag
     m.times{|i|c[i]>?@&&g[w,i,0]}       #call g from all cells in the grid that contain a letter 
     puts $r,w}                          #output flag value and word
}