Considere cómo se podría organizar una palabra en una cuadrícula Boggle arbitrariamente grande si se ignora la regla sobre no usar el mismo cubo de letras más de una vez . También suponga que tiene un número ilimitado de cubos de letras (con todas las letras presentes), y Ques justo Q.

La palabra se MISSISSIPPIpodría arreglar usando solo 6 cubos. Aquí hay un posible arreglo:

 S
MIS
 PP

Comenzando en el M, repetidamente damos un paso horizontal, vertical o diagonal hasta que se deletrea toda la palabra.

Sorprendentemente, una frase más larga como AMANAPLANACANALPANAMAtambién solo necesita 6 cubos:

MAN
PLC

Sin embargo, el número mínimo de cubos necesarios para cadenas más largas y complejas no siempre es obvio.

Desafío

Escriba un programa que tome una cadena y la organice de manera similar a Boggle, de modo que se use el número mínimo de cubos . (Las dimensiones de la cuadrícula resultante y el número de celdas vacías son irrelevantes).

Suponga que tiene un número ilimitado de cubos para cada carácter ASCII imprimible, excepto el espacio (códigos hexadecimales 21 a 7E), ya que se utiliza como una celda de cuadrícula vacía. Solo se ingresarán cadenas ASCII imprimibles (sin espacios).

La entrada debe tomarse de stdin o la línea de comando. La salida debe ir a stdout (o la alternativa más cercana).

Las nuevas líneas y espacios iniciales o finales en la salida están bien (pero es de esperar que no haya una cantidad excesiva).

El espacio de búsqueda explota exponencialmente a medida que la cadena se alarga, pero no es necesario que intente hacer que su algoritmo sea eficiente (aunque eso sería bueno :)). Este es el código de golf, por lo que gana la solución más corta en bytes .

Ejemplo

Si la entrada fuera Oklahoma!(mínimo de 8 caracteres), todas estas serían salidas válidas porque todas tienen exactamente 8 celdas rellenas y siguen el patrón de lectura (revisado) de Boggle:

Oklaho
   !m

o

  !
Oamo
klh

o

   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)

La sangría en cuatro espacios es en realidad un carácter de tabulación.

AMANAPLANACANALPANAMA:

MC 
NA 
PL

MISSISSIPPI:

S  
SI 
PPM

Oklahoma!:

oh    
 ma   
 ! l  
    k 
     O

Llanfairpwllgwyngylles letal ;)