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 Qu
itu adil Q
.
Kata MISSISSIPPI
itu bisa diatur hanya menggunakan 6 kubus. Berikut adalah satu pengaturan yang mungkin:
S
MIS
PP
Mulai dari M
kita berulang kali mengambil langkah apa pun secara horizontal, vertikal, atau diagonal hingga seluruh kata dieja.
Anehnya, frasa yang lebih panjang seperti AMANAPLANACANALPANAMA
juga 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.
Jawaban:
Python 342
355398Indent di empat spasi sebenarnya adalah karakter tab.
AMANAPLANACANALPANAMA
:MISSISSIPPI
:Oklahoma!
:Llanfairpwllgwyngyll
adalah mematikan ;)sumber
import sys
dan menggantisys.argv[1]
denganraw_input()
.elif
keelif not c and (not A or len(b)<len(A[-1])):
dan berjalan jauh lebih cepat"Oklahoma!"
input OK, Anda bisa menggunakaninput()
sajaraw_input()
.