Écrivez une fonction qui prend deux paramètres: un entier positif n et une liste de mots.

Étant donné un cube de n -by- n -by- n unités, attribuer une lettre aléatoire (AZ) à chaque unité de surface. (Pour un cube 3x3x3, il y aurait 9 unités de surface sur chaque face.)

Déterminez ensuite s'il est possible pour une fourmi de marcher le long de la surface (avec la possibilité de traverser les visages) pour épeler chacun des mots fournis. Supposons que pour épeler un mot, les lettres doivent être adjacentes haut / bas ou gauche / droite, mais pas nécessairement sur la même face. [ Modifier, pour plus de clarté: la fourmi peut inverser son chemin et utiliser des lettres plus d'une fois. Chaque unité de surface compte pour un caractère, donc pour épeler un mot avec des lettres répétées (par exemple "voir"), la fourmi devrait visiter trois unités adjacentes.]

La fonction doit produire deux choses:

1) Chacune des lettres sur chaque face, de manière à pouvoir en déduire la topologie. Par exemple, pour un cube 2x2x2, une sortie acceptable ressemblerait à:

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

2) Chacun des mots, avec un booléen représentant s'il est possible pour la fourmi d'épeler le mot en marchant le long de la surface du cube. Par exemple:

1 ask
0 practical
1 pure
0 full

Défi bonus (ne sera pas pris en compte dans le score, juste pour le plaisir): au lieu de n représentant uniquement la taille du cube, n représente également la dimensionnalité de la forme. Ainsi, un n de 2 donnerait un carré 2x2; un n de 3 donnerait un cube de 3x3x3; et un n de 4 donnerait un tesseract 4x4x4x4.

Rubis, 272 octets

Deux sauts de ligne inutiles sont ajoutés au code de chaque côté de la fonction imbriquée gpour améliorer la lisibilité. Ceux-ci sont exclus du score. Les caractères f=qui affectent la fonction anonyme à une variable sont également exclus.

Le format de sortie est 0ou 1par la question au lieu de Ruby natif trueet false. Une nouvelle ligne (plutôt qu'un espace) est utilisée pour séparer le booléen et le mot. Je crois comprendre qu'il s'agit d'une interprétation acceptable des exigences de sortie, mais sinon, l'impact sur le nombre d'octets serait mineur.

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

Production

Après environ 50 appels comme celui-ci:

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

J'ai finalement obtenu la sortie suivante avec 2 hits. ANTest en bas à droite en haut, et le ANest partagé par CAN, avec le Ctour d'emballage en haut à gauche.

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

Explication

Le dépliage particulier du cube sélectionné, a été choisi en partie pour sa facilité de dessin, mais surtout pour sa facilité de recherche.

Les caractères non alphabétiques (les points plus la nouvelle ligne à la fin de chaque ligne) sont une partie importante du champ où la fourmi peut être trouvée en train de marcher.

La recherche est effectuée par la fonction récursive g, qui est imbriquée dans la fonction f. Si le mot passé est une chaîne vide, la recherche est terminée et $rest définie sur 1. Si la fourmi est sur un carré de lettres qui correspond à la première lettre du mot, la recherche se poursuit dans les quatre directions: la fonction est à nouveau appelée avec le mot raccourci en supprimant sa première lettre. Dans ce cas, le paramètre direction est ignoré. Le déplacement se fait en appelant récursivement avec l'index de cellule modifié par les valeurs dans x.Le résultat de l'addition est pris modulo la taille de la grille plus une demi-ligne supplémentaire. Cela signifie que la ligne du bas s'enroule vers le haut et vice versa, avec le décalage horizontal correct.

Si la fourmi se trouve sur un carré non-lettre, elle doit zigzaguer dans un mouvement d'escalier jusqu'à ce qu'elle trouve un carré lettre. Elle zizagera en direction sud-est ou nord-ouest. Ceci est simulé par des appels récursifs avec le dparamètre étant XORé avec 1 à chaque fois pour garder une trace de son mouvement. Jusqu'à ce qu'elle atteigne le carré de lettre suivant, il n'y a pas de raccourcissement du mot d'entrée. Idéalement, cela peut être fait par la même récursivité que celle utilisée lorsque nous recherchons dans la zone avec des lettres. La différence est que la récursivité n'a qu'une seule branche lorsque la fourmi est dans la zone des blancs, contre 4 dans la zone des lettres.

Code commenté

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