Pada konsol game modern dan perangkat lain tanpa keyboard tradisional, mencoba memasukkan teks adalah mimpi buruk. Harus mengetik dengan beberapa tombol dan joystick pada keyboard virtual itu menyebalkan, dan saya ingin membuat gerakan / tombol sesedikit mungkin menekan.
Keyboard yang akan Anda gunakan terlihat seperti ini:
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
+---+---+---+---+---+---+---+---+---+---+
| q | w | e | r | t | y | u | i | o | p |
+---+---+---+---+---+---+---+---+---+---+
| a | s | d | f | g | h | j | k | l | - |
+---+---+---+---+---+---+---+---+---+---+
| z | x | c | v | b | n | m | _ | @ | . |
+---+---+---+---+---+---+---+---+---+---+
Operasi berikut dapat digunakan:
L
: pindahkan satu kotak ke kiri di keyboard (membungkus)R
: pindahkan satu kotak ke kanan di keyboard (membungkus)U
: pindahkan satu kotak ke atas pada keyboard (membungkus)D
: pindahkan satu kotak ke bawah pada keyboard (membungkus)Y
: masukkan spasiB
: pindahkan pointer penyisipan satu spasi ke kiri (tidak melakukan apa-apa jika pointer ada di awal)F
: pindahkan pointer penyisipan satu spasi ke kanan (tidak melakukan apa-apa jika pointer ada di ujung)C
: beralih caps lockA
: masukkan karakter yang dipilih di posisi pointer penyisipan
Diberikan string input yang hanya berisi karakter ASCII yang dapat diketik menggunakan keyboard dan perintah di atas (cocok [a-zA-Z0-9 [email protected]]*
), menampilkan urutan perintah yang akan menghasilkan string output. Posisi awal kursor ada pada 1
tombol (kiri atas), dan caps lock pada awalnya mati.
Mencetak gol
Untuk string apa pun yang diberikan, pendekatan naif akan, untuk setiap karakter dalam string, arahkan ke karakter pada keyboard dengan jalur terpendek, beralih caps lock jika perlu, dan pilih karakter. Pendekatan naif semacam itu akan menghasilkan perintah panjang (length of input string) + (sum of Manhattan distances on keyboard between consecutive non-space characters) + (number of times the string alternates between lowercase and uppercase characters) + (1 if string starts with an uppercase letter else 0)
. Misalnya, pendekatan naif untuk 101
akan menghasilkan ALARA
, perintah panjang 5, dan Noob 5
akan menghasilkan DDDRRRRRCAUURRRCAADDLLLLAYUUUA
, perintah panjang 30.
Namun, pengajuan Anda berupaya lebih baik daripada pendekatan naif. Untuk setiap string input, kiriman Anda akan menerima poin yang sama dengan jumlah perintah yang digunakan oleh pendekatan naif dikurangi jumlah perintah yang dihasilkan kiriman Anda. Skor keseluruhan Anda akan menjadi jumlah skor individual.
Aturan
- Kiriman akan dijalankan di ruang kerja virtual Cloud9 gratis. Ruang kerja memiliki RAM 512 MB, 2 GB ruang disk, 8 Intel (R) Xeon (R) CPU @ 2,50 GHz (info CPU lengkap, ditemukan dengan menjalankan
cat /proc/cpuinfo
, dapat ditemukan di sini ), dan menjalankan 64-bit Ubuntu 14.04 Terpercaya Anda dapat meminta akses ke ruang kerja pengujian untuk menjalankan dan menilai kiriman Anda, atau saya dapat mencetaknya untuk Anda. - Pengajuan akan dijalankan sekali per test case. Menyimpan status di antara deretan dilarang. Kiriman tidak boleh menulis ke atau membaca dari file apa pun selain file sumber (yang tidak dapat dimodifikasi antara berjalan), dengan kemungkinan pengecualian membaca file input jika diperlukan.
- Pengajuan dibatasi hingga 1 menit runtime untuk setiap test case. Pengajuan dapat menghasilkan beberapa solusi, tetapi hanya solusi terakhir yang valid dalam waktu yang ditentukan yang akan digunakan untuk penilaian. Kegagalan untuk menghasilkan solusi apa pun yang valid dalam waktu yang ditentukan akan menghasilkan skor 0 untuk test case tersebut.
- Harap sertakan petunjuk tentang cara mengajukan kiriman Anda, serta alat / pustaka yang perlu diinstal yang tidak disertakan dengan instalasi Ubuntu 14.04 standar.
- Pemenang akan menjadi pengajuan dengan skor terbesar. Dalam hal seri, pengajuan dengan kompleksitas algoritme yang lebih baik akan menang. Jika dasi masih belum terselesaikan, pengiriman pertama untuk mencapai skor dan kompleksitas algoritmik akan menang.
- Kiriman tidak dapat dioptimalkan untuk kasus uji. Saya berhak mengubah kasus uji jika saya merasa perlu.
Uji kasus
Format: input string => naive score
(jika Anda melihat kesalahan dalam hal ini, silakan tinggalkan komentar dengan koreksi)
101 => 5
quip => 12
PPCG => 15
Mego => 25
Noob 5 => 26
penguin => 27
867-5309 => 32
2_sPoOkY_4_mE => 60
The Nineteenth Byte => 76
[email protected] => 95
8xM3R__5ltZgrkJ.-W b => 98
correcthorsebatterystaple => 104
verylongRUNSOFCAPSandnocaps => 118
This is an English sentence. => 122
WNtza.akjzSP2GI0V9X .0epmUQ-mo => 131
Programming Puzzles and Code Golf => 140
Jawaban:
C
Skornya adalah 193.
Kompilasi dengan sebagai "gcc virtualKeyboard.c". Jalankan tanpa argumen "./a.out". Bunyinya input dari stdin dan tulis outputnya ke stdout.
sumber
C99
Inilah upaya saya untuk mencari solusi. Memperoleh skor 62.
Tampaknya bekerja dengan baik untuk kata-kata yang lebih kecil dan saya hanya berasumsi yang lebih besar juga berfungsi dengan baik karena terlalu besar untuk saya uji secara manual.
Kompilasi dengan "gcc -std = gnu99"
Penggunaan adalah "virtualKeyboard" string ""
sumber
Noob 5
adalahRRRRRUCALCAYRRRRARRRRDBBBAA
, yang menghasilkanN33b @
, dan output kedua AndaLLDAAYRRRRAUBBARBBBCA
, yang menghasilkan4oo3 e
. Seperti berdiri, skor Anda saat ini adalah 5, karena program Anda hanya mencetak urutan perintah yang valid untuk 3 kasus uji pertama.