Arranjos mínimos como Boggle

14

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.

Passatempos de Calvin
fonte
4
Isso soa como um problema de otimização difícil. Eu acho que teria sido um bom desafio de código.
Martin Ender
1
Não consigo editar porque há uma edição pendente de um usuário de baixa reputação, mas o Mississippi tem dois duplos.
Peter Taylor
E quanto à distinção entre maiúsculas e minúsculas?
proud haskeller
1
@proudhaskeller Tenho certeza de que a entrada não diferencia maiúsculas de minúsculas, porque: 1) a entrada é apenas qualquer ASCII imprimível 2) o OP não mencionou o contrário 3) O exemplo de oklahoma não seria mínimo se a entrada não diferencia maiúsculas de minúsculas.
Martin Ender
@ MartinBüttner Eu acho que você quis caso sensível
Ypnypn

Respostas:

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)

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

Vai
fonte
Parece bom agora, apenas muito lento: /
Calvin's Hobbies
1
Você pode reduzi-lo um pouco removendo import syse substituindo sys.argv[1]por raw_input().
Hobbies de Calvin
@ Calvin'sHobbies thx novamente, dica legal :) Para sair cedo, você pode simplesmente mudar o elifpara elif not c and (not A or len(b)<len(A[-1])):e ele corre muito mais rápido
Será
1
se "Oklahoma!"for uma entrada OK, você pode simplesmente usar em input()vez de raw_input().
FryAmTheEggman #