Considérez comment un mot pourrait être organisé sur une grille Boggle arbitrairement grande si la règle de ne pas utiliser le même cube de lettres plus d'une fois est ignorée . Supposez également que vous avez un nombre illimité de cubes de lettres (avec toutes les lettres présentes), et Quc'est juste Q.

Le mot MISSISSIPPIpourrait être arrangé en utilisant seulement 6 cubes. Voici un arrangement possible:

 S
MIS
 PP

En commençant par le, Mnous prenons à plusieurs reprises n'importe quelle étape horizontalement, verticalement ou en diagonale jusqu'à ce que le mot entier soit épelé.

Étonnamment, une phrase plus longue comme AMANAPLANACANALPANAMAn'a également besoin que de 6 cubes:

MAN
PLC

Cependant, le nombre minimum de cubes nécessaires pour des chaînes plus longues et plus complexes n'est pas toujours évident.

Défi

Écrivez un programme qui prend une chaîne et l'arrange de cette façon, comme Boggle, de sorte que le nombre minimum de cubes soit utilisé . (Les dimensions de la grille résultante et le nombre de cellules vides ne sont pas pertinents.)

Supposons que vous disposez d'un nombre illimité de cubes pour chaque caractère ASCII imprimable à l' exception de l'espace (codes hexadécimaux 21 à 7E), car il est utilisé comme cellule de grille vide. Seules les chaînes ASCII imprimables (sans espaces) seront entrées.

L'entrée doit provenir de stdin ou de la ligne de commande. La sortie doit aller vers stdout (ou l'alternative la plus proche).

Les nouvelles lignes et les espaces de début ou de fin dans la sortie sont corrects (mais j'espère qu'il n'y a pas un montant excessif).

L'espace de recherche explose de façon exponentielle à mesure que la chaîne s'allonge, mais vous n'êtes pas obligé d'essayer de rendre votre algorithme efficace (bien que ce serait bien :)). Il s'agit de code-golf, donc la solution la plus courte en octets l' emporte.

Exemple

Si l'entrée était Oklahoma!(8 caractères minimum), ce seraient toutes des sorties valides car toutes ont exactement 8 cellules de grille remplies et elles suivent le modèle de lecture Boggle (révisé):

Oklaho
   !m

ou

  !
Oamo
klh

ou

   lkO   
  !amo              
    h    

etc.

Python 342 355 398

R=(-1,0,1)
A=[];b={}
def s(w,x,y):
 if w: # not at the end of the word yet?
  for I in R: # search adjacent squares
   for j in R:
    if I|j: # skip the square we are on
     i=I+x;j+=y;c=b.get((i,j)) # get square in board
     if c==w[0]:s(w[1:],i,j) # square is what we are looking for?
     elif not c:b[i,j]=w[0];s(w[1:],i,j);del b[i,j] # we can set square?
 else:A.append(dict(b)) # all solutions
s(raw_input(),9,9) # run the search
A=min(A,key=len) # A is now the shortest solution
C=sum(map(list,A),[]) # put all board coords together
C=range(min(C),max(C)+1) # find the board biggest square bound
for r in C:print"".join(A.get((c,r)," ") for c in C)

Le retrait à quatre espaces est en fait un caractère de tabulation.

AMANAPLANACANALPANAMA:

MC 
NA 
PL

MISSISSIPPI:

S  
SI 
PPM

Oklahoma!:

oh    
 ma   
 ! l  
    k 
     O

Llanfairpwllgwyngyllest mortel ;)