Considere como uma palavra pode ser organizada em uma grade Boggle arbitrariamente grande se a regra de não usar o mesmo cubo de letras mais de uma vez for ignorada . Suponha também que você tenha um número ilimitado de cubos de letras (com todas as letras presentes) e Quseja justo Q.

A palavra MISSISSIPPIpode ser organizada usando apenas 6 cubos. Aqui está um arranjo possível:

 S
MIS
 PP

Começando no M, repetidamente, damos qualquer passo na horizontal, na vertical ou na diagonal até que a palavra inteira seja escrita.

Surpreendentemente, uma frase mais longa como AMANAPLANACANALPANAMAtambém precisa apenas de 6 cubos:

MAN
PLC

No entanto, o número mínimo de cubos necessário para seqüências mais longas e mais complexas nem sempre é óbvio.

Desafio

Escreva um programa que pegue uma string e organize-o dessa maneira semelhante ao Boggle, de modo que o número mínimo de cubos seja usado . (As dimensões da grade resultante e o número de células vazias são irrelevantes.)

Suponha que você tenha um número ilimitado de cubos para cada caractere ASCII imprimível, exceto o espaço (códigos hexadecimais 21 a 7E), pois é usado como uma célula de grade vazia. Somente seqüências de caracteres ASCII imprimíveis (sem espaços) serão inseridas.

A entrada deve ser obtida no stdin ou na linha de comando. A saída deve ir para stdout (ou alternativa mais próxima).

Novas linhas e espaços à esquerda ou à direita na saída são bons (mas espero que não haja uma quantidade excessiva).

O espaço de pesquisa explode exponencialmente à medida que a cadeia fica mais longa, mas não é necessário tentar tornar seu algoritmo eficiente (embora isso seja bom :)). Isso é código-golfe, então a solução mais curta em bytes vence.

Exemplo

Se a entrada fosse Oklahoma!(mínimo de 8 caracteres), todas seriam saídas válidas porque todas possuem exatamente 8 células de grade preenchidas e seguem o padrão de leitura Boggle (revisado):

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)

Recuar em quatro espaços é na verdade um caractere de tabulação.

AMANAPLANACANALPANAMA:

MC 
NA 
PL

MISSISSIPPI:

S  
SI 
PPM

Oklahoma!:

oh    
 ma   
 ! l  
    k 
     O

Llanfairpwllgwyngyllé letal ;)