Pengaturan seperti Kericuhan Minimal

14

Pertimbangkan bagaimana sebuah kata dapat diatur pada kotak Boggle besar yang sewenang-wenang jika aturan tentang tidak menggunakan huruf yang sama lebih dari satu kali diabaikan . Juga asumsikan bahwa Anda memiliki jumlah huruf yang tidak terbatas (dengan semua huruf ada), dan Quitu adil Q.

Kata MISSISSIPPIitu bisa diatur hanya menggunakan 6 kubus. Berikut adalah satu pengaturan yang mungkin:

 S
MIS
 PP

Mulai dari Mkita berulang kali mengambil langkah apa pun secara horizontal, vertikal, atau diagonal hingga seluruh kata dieja.

Anehnya, frasa yang lebih panjang seperti AMANAPLANACANALPANAMAjuga hanya membutuhkan 6 kubus:

MAN
PLC

Namun, jumlah minimum kubus yang dibutuhkan untuk string yang lebih panjang dan lebih kompleks tidak selalu jelas.

Tantangan

Tulis sebuah program yang mengambil string dan mengaturnya dengan cara Boggle seperti ini sehingga jumlah minimum kubus digunakan . (Dimensi grid yang dihasilkan dan jumlah sel kosong tidak relevan.)

Asumsikan Anda memiliki jumlah kubus yang tidak terbatas untuk setiap karakter ASCII yang dapat dicetak kecuali spasi (kode hex 21 hingga 7E), karena itu digunakan sebagai sel kotak kosong. Hanya string ASCII yang dapat dicetak (tanpa spasi) yang akan dimasukkan.

Masukan harus diambil dari stdin atau baris perintah. Output harus menuju stdout (atau alternatif terdekat).

Leading atau trailing newlines dan spasi dalam output baik-baik saja (tapi mudah-mudahan tidak ada jumlah yang berlebihan).

Ruang pencarian meledak secara eksponensial saat string semakin panjang, tetapi Anda tidak diharuskan untuk membuat algoritma Anda efisien (meskipun itu akan menyenangkan :)). Ini adalah kode-golf, jadi solusi terpendek dalam byte menang.

Contoh

Jika inputnya adalah Oklahoma!(minimum 8 karakter), ini semua akan menjadi output yang valid karena semua memiliki 8 sel grid yang diisi dengan tepat dan mereka mengikuti pola bacaan Boggle yang direvisi:

Oklaho
   !m

atau

  !
Oamo
klh

atau

   lkO   
  !amo              
    h    

dll.

Hobi Calvin
sumber
4
Ini terdengar seperti masalah optimasi yang sulit. Saya pikir itu akan membuat tantangan kode yang bagus.
Martin Ender
1
Saya tidak dapat mengedit karena ada suntingan yang ditangguhkan dari pengguna rep rendah, tetapi Mississippi memiliki dua double-s.
Peter Taylor
Bagaimana dengan sensitivitas kasus?
haskeller bangga
1
@proudhaskeller Saya yakin inputnya case-insensitive, karena: 1) inputnya sembarang ASCII yang bisa dicetak 2) OP tidak menyebutkan sebaliknya. 3) Contoh oklahoma tidak akan minimal jika inputnya case-insensitive.
Martin Ender
@ MartinBüttner Saya pikir Anda maksudkan case- sensitive
Ypnypn

Jawaban:

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)

Indent di empat spasi sebenarnya adalah karakter tab.

AMANAPLANACANALPANAMA:

MC 
NA 
PL

MISSISSIPPI:

S  
SI 
PPM

Oklahoma!:

oh    
 ma   
 ! l  
    k 
     O

Llanfairpwllgwyngylladalah mematikan ;)

Akan
sumber
Terlihat bagus sekarang, hanya sangat lambat: /
Hobi Calvin
1
Anda dapat mempersingkatnya sedikit dengan menghapus import sysdan mengganti sys.argv[1]dengan raw_input().
Calvin Hobbies
@ CalvinHobbies thx lagi, tip rapi :) Untuk mendapatkan awal Anda hanya dapat mengubah elifke elif not c and (not A or len(b)<len(A[-1])):dan berjalan jauh lebih cepat
Will
1
jika "Oklahoma!"input OK, Anda bisa menggunakan input()saja raw_input().
FryAmTheEggman