Minimale Boggle-ähnliche Arrangements

14

Überlegen Sie, wie ein Wort in einem beliebig großen Boggle- Raster angeordnet werden kann, wenn die Regel, dass der gleiche Buchstabenwürfel nicht mehr als einmal verwendet wird, ignoriert wird . Nehmen Sie auch an, dass Sie eine unbegrenzte Anzahl von Buchstabenwürfeln (mit allen vorhandenen Buchstaben) haben und dies Qugerecht ist Q.

Das Wort MISSISSIPPIkönnte mit nur 6 Würfeln arrangiert werden. Hier ist eine mögliche Anordnung:

 S
MIS
 PP

Beginnend mit dem MSchritt machen wir wiederholt einen horizontalen, vertikalen oder diagonalen Schritt, bis das gesamte Wort buchstabiert ist.

Überraschenderweise benötigt eine längere Phrase wie AMANAPLANACANALPANAMAauch nur 6 Würfel:

MAN
PLC

Die Mindestanzahl von Cubes für längere, komplexere Strings ist jedoch nicht immer offensichtlich.

Herausforderung

Schreiben Sie ein Programm, das eine Zeichenfolge aufnimmt und sie in einer Art Boggle so anordnet, dass die Mindestanzahl von Cubes verwendet wird . (Die Abmessungen des resultierenden Gitters und die Anzahl der leeren Zellen sind irrelevant.)

Angenommen, Sie haben eine unbegrenzte Anzahl von Cubes für jedes druckbare ASCII-Zeichen mit Ausnahme des Leerzeichens (Hex-Codes 21 bis 7E), da es als leere Gitterzelle verwendet wird. Es werden nur druckbare ASCII-Zeichenfolgen (ohne Leerzeichen) eingegeben.

Die Eingabe sollte über stdin oder die Befehlszeile erfolgen. Die Ausgabe sollte auf stdout (oder die nächstgelegene Alternative) gehen.

Führende oder nachfolgende Zeilenumbrüche und Leerzeichen in der Ausgabe sind in Ordnung (aber hoffentlich gibt es keine übermäßige Menge).

Der Suchraum explodiert exponentiell, wenn die Zeichenfolge länger wird, aber Sie müssen nicht versuchen, Ihren Algorithmus effizienter zu gestalten (obwohl das schön wäre :)). Das ist Code-Golf, also gewinnt die kürzeste Lösung in Bytes .

Beispiel

Wenn die Eingabe Oklahoma!(mindestens 8 Zeichen) wäre, wären dies alles gültige Ausgaben, da alle genau 8 gefüllte Gitterzellen haben und dem (überarbeiteten) Boggle-Lesemuster folgen:

Oklaho
   !m

oder

  !
Oamo
klh

oder

   lkO   
  !amo              
    h    

etc.

Calvins Hobbys
quelle
4
Das klingt nach einem schwierigen Optimierungsproblem. Ich denke, dass es eine nette Code-Herausforderung gemacht hätte.
Martin Ender
1
Ich kann nicht bearbeiten, da von einem Benutzer mit geringen Wiederholungszahlen eine Bearbeitung aussteht, aber Mississippi verfügt über zwei Doppel-s.
Peter Taylor
Was ist mit Groß- / Kleinschreibung?
stolzer Haskeller
1
@proudhaskeller Ich bin sicher, dass bei der Eingabe die Groß- und Kleinschreibung nicht berücksichtigt wird, da: 1) die Eingabe nur ein druckbares ASCII-Format ist 2) das OP nichts anderes erwähnt 3) das Oklahoma-Beispiel wäre nicht minimal, wenn bei der Eingabe die Groß- und Kleinschreibung nicht berücksichtigt wird.
Martin Ender
@ MartinBüttner Ich denke, Sie meinten Groß- und Kleinschreibung
Ypnypn

Antworten:

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)

Einzug bei vier Leerzeichen ist eigentlich ein Tabulatorzeichen.

AMANAPLANACANALPANAMA:

MC 
NA 
PL

MISSISSIPPI:

S  
SI 
PPM

Oklahoma!:

oh    
 ma   
 ! l  
    k 
     O

Llanfairpwllgwyngyllist tödlich ;)

Wille
quelle
Sieht jetzt gut aus, nur sehr langsam: /
Calvins Hobbys
1
Sie können es ein wenig verkürzen , indem import sysund Ersetzen sys.argv[1]mit raw_input().
Calvins Hobbys
@ Calvin'sHobbies thx wieder ordentlich Spitze :) Um eine frühe aussteigen Sie nur das ändern kann elifzu elif not c and (not A or len(b)<len(A[-1])):und es viel schneller läuft
Will
1
wenn "Oklahoma!"OK - Eingang ist, könnten Sie nur verwenden input()statt raw_input().
FryAmTheEggman