Disposiciones mínimas similares a Boggle

14

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.

Pasatiempos de Calvin
fuente
44
Esto suena como un difícil problema de optimización. Creo que habría sido un buen desafío de código.
Martin Ender
1
No puedo editar porque hay una edición pendiente de un usuario de baja representación, pero Mississippi tiene dos dobles.
Peter Taylor
¿Qué pasa con mayúsculas y minúsculas?
orgulloso haskeller
1
@proudhaskeller Estoy seguro de que la entrada no distingue entre mayúsculas y minúsculas, porque: 1) la entrada es cualquier ASCII imprimible 2) el OP no mencionó lo contrario 3) El ejemplo de Oklahoma no sería mínimo si la entrada no distingue entre mayúsculas y minúsculas.
Martin Ender
@ MartinBüttner Creo que te refieres a mayúsculas y minúsculas
Ypnypn

Respuestas:

5

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 ;)

Será
fuente
Se ve bien ahora, simplemente muy lento: /
Calvin's Hobbies
1
Puede acortarlo un poco quitándolo import sysy reemplazándolo sys.argv[1]con raw_input().
Hobbies de Calvin
@ Calvin'sHobbies THX de nuevo, limpio punta :) Para tener una salida temprana sólo se puede cambiar la elifde elif not c and (not A or len(b)<len(A[-1])):y se ejecuta mucho más rápido
Will
1
si "Oklahoma!"está bien, puede usar en input()lugar de raw_input().
FryAmTheEggman