Zastanów się, jak słowo może być ułożone na dowolnie dużej siatce Boggle, jeśli zignorowana zostanie reguła nieużywania tej samej kostki z literą więcej niż jeden raz . Załóżmy również, że masz nieograniczoną liczbę kostek z literami (wszystkie litery są obecne) i Qujest sprawiedliwa Q.

Słowo MISSISSIPPImożna ułożyć za pomocą tylko 6 kostek. Oto jeden z możliwych rozwiązań:

 S
MIS
 PP

Zaczynając od M, wielokrotnie robimy krok w poziomie, w pionie lub po przekątnej, aż całe słowo zostanie przeliterowane.

Zaskakujące, że dłuższa fraza AMANAPLANACANALPANAMArównież potrzebuje tylko 6 kostek:

MAN
PLC

Jednak minimalna liczba kostek potrzebna do dłuższych, bardziej złożonych ciągów nie zawsze jest oczywista.

Wyzwanie

Napisz program, który pobiera ciąg znaków i układa go w taki sposób, jak w Boggle, tak aby używana była minimalna liczba kostek . (Wymiary wynikowej siatki i liczba pustych komórek są nieistotne).

Załóżmy, że masz nieograniczoną liczbę kostek dla każdego drukowalnego znaku ASCII oprócz spacji (kody szesnastkowe od 21 do 7E), ponieważ jest on używany jako pusta komórka siatki. Wprowadzane będą tylko ciągi znaków ASCII do wydruku (bez spacji).

Dane wejściowe należy pobierać ze standardowego wejścia lub wiersza poleceń. Dane wyjściowe powinny przejść do standardowego wyjścia (lub najbliższej alternatywy).

Wiodące lub końcowe znaki nowej linii i spacje na wyjściu są w porządku (ale mam nadzieję, że nie ma nadmiernej ilości).

Przestrzeń wyszukiwania wysadza się wykładniczo, gdy ciąg się wydłuża, ale nie musisz próbować usprawniać działania algorytmu (choć byłoby to miło :)). To jest golf golfowy, więc wygrywa najkrótsze rozwiązanie w bajtach .

Przykład

Gdyby dane wejściowe miały Oklahoma!(minimum 8 znaków), wszystkie byłyby poprawnymi danymi wyjściowymi, ponieważ wszystkie mają dokładnie 8 wypełnionych komórek siatki i są zgodne ze (zmienionym) wzorcem odczytu Boggle:

Oklaho
   !m

lub

  !
Oamo
klh

lub

   lkO   
  !amo              
    h    

itp.

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)

Wcięcie na czterech spacjach jest tak naprawdę znakiem tabulacji.

AMANAPLANACANALPANAMA:

MC 
NA 
PL

MISSISSIPPI:

S  
SI 
PPM

Oklahoma!:

oh    
 ma   
 ! l  
    k 
     O

Llanfairpwllgwyngylljest śmiertelny ;)