Masalah
Anda diberi urutan bola berwarna (merah R
dan hijau G
). Salah satu urutan yang mungkin adalah:
RGGGRRGGRGRRRGGGRGRRRG
Dalam gerakan sesedikit mungkin, Anda harus membuatnya sehingga setiap bola memiliki warna yang berbeda dengan tetangganya (yaitu urutan bergantian.)
RGRGRGRGRGRGRGRGRGRGRG
Anda harus menulis sebuah program yang dapat mengubah urutan yang tidak berurutan (dalam hal ini string) dengan jumlah "R" dan "G" yang sama menjadi urutan di mana item berganti. Satu contoh sesi di bawah ini, untuk algoritma naif ( <
adalah input ke program, >
adalah output. Tidak perlu untuk memasukkan tanda sisipan pada input atau output.)
< RGGGRRGGRGRRRGGGRGRRRG
> RGGRGRGGRGRRRGGGRGRRRG
> RGRGGRGGRGRRRGGGRGRRRG
> RGRGRGGGRGRRRGGGRGRRRG
> RGRGRGGRGGRRRGGGRGRRRG
> RGRGRGGRGRGRRGGGRGRRRG
> RGRGRGGRGRGRGRGRGGRRRG
> RGRGRGGRGRGRGRGRGRGRRG
> RGRGRGGRGRGRGRGRGRGRGR
> RGRGRGRGGRGRGRGRGRGRGR
> RGRGRGRGRGGRGRGRGRGRGR
> RGRGRGRGRGRGGRGRGRGRGR
> RGRGRGRGRGRGRGGRGRGRGR
> RGRGRGRGRGRGRGRGGRGRGR
> RGRGRGRGRGRGRGRGRGGRGR
> RGRGRGRGRGRGRGRGRGRGGR
> RGRGRGRGRGRGRGRGRGRGRG (15 moves)
Kemungkinan lain adalah mengeluarkan "5,7" misalnya untuk menunjukkan pertukaran posisi 5 dan 7.
Anda mungkin posisi baik merah atau hijau pertama, dan Anda tidak harus konsisten. Setiap urutan akan memiliki panjang yang sama dengan setiap urutan lainnya.
Anda hanya dapat menukar dua huruf apa pun di setiap gerakan (tidak perlu berdekatan).
Kriteria Menang
Program harus menunjukkan setiap langkah dari proses sortir. Program yang membuat total gerakan paling sedikit untuk semua string di bawah ini, menang. Jika ada seri, kode terpendek akan menang.
Input String
String berikut akan digunakan untuk menguji program:
GGGGGGGGGGRRRRRRRRRR
GGRRGGRRGGRRGGRRGGRR
RRGGGGRRRRGGGGRRRRGG
GRRGRGGGGRRRGGGGRRRR
GRGGGRRRRGGGRGRRGGRR
RGRGRGRGRGRGRGRGRGRG
Urutan terakhir harus menghasilkan nol gerakan.
sumber
Jawaban:
Python,
140122119115sumber
s
. Ini akan menghemat beberapa karakter lagi.APL 46
Menjalankan uji yang diberikan menghasilkan:
Solusi di atas menggunakan indeks asal 1 dengan swap yang diberikan di kolom matriks hasil. Dua karakter dapat disimpan jika vektor input i diinisialisasi dengan string input sebelum dieksekusi daripada menjadi input pada saat eksekusi.
sumber
GolfScript (47 karakter)
Misalnya (menggunakan test case yang jauh lebih mudah untuk memeriksa kebenaran daripada yang disarankan, yang semuanya memiliki banyak jawaban yang benar):
Output adalah daftar pasangan tanpa indeks untuk ditukar.
sumber
Python, 213 karakter
M
menemukan bergerak diperlukan untuk mengkonversiS
keT
. Itu melakukan ini dengan berulang kali menemukanR
danG
keluar dari posisi dan menukar mereka. Kami kemudian menemukan urutan langkah yang lebih pendek untuk mendapatkan salah satuRGRG...RG
atauGRGR...GR
.Harus menemukan urutan gerakan yang optimal untuk setiap input.
sumber
Mathematica 238
Kode
NB:
\[Transpose]
adalah karakter tunggal, "t", ditulis dalam Mathematica ]Contohnya
sumber
Mathematica 134 atau 124
Tergantung pada bagaimana Anda menghitung "Transpose []" yang pada Mathematica hanya satu karakter (tidak ada representasi di sini). Spaces ditambahkan untuk kejelasan
Sampel:
Keluaran
sumber
PadLeft[{}, 20, {y}], #, 1]
dapat dikompresi lebih sedikitJavascript - 173 karakter
Sebuah tantangan besar, membuat saya sibuk selama beberapa waktu.
Di sini kode hasil untuk kasus uji:
sumber
PHP - 34 bergerak - 193 karakter
Mungkin masih mencoba untuk memperbaiki ini ...
sumber
$argv[0]
sebagai gantinya, menghemat 2 byte / masing-masing. Dan akan lebih valid, karena$argv
sering digunakan untuk input melalui CMD