Bantu pannenkoek menghitung penekan

28

pannenkoek2012 bertujuan untuk menyelesaikan Super Mario 64 dengan sesedikit mungkin menekan tombol A, yang membuat Mario melompat. Setiap "Pers" terdiri dari tiga bagian:

  • Menekan tombol
  • Memegangnya untuk waktu yang lama
  • Melepaskannya

Bagian dari pers A, dari video oleh Pannenkoek2012

Lihat video ini (1:15 - 3:23) untuk penjelasan hebat yang mencakup gambar di atas. (Namun, tantangan ini tidak akan menggunakan terminologi setengah tekan dan akan menempatkan hambatan yang mengharuskan pelepasan A.)

Tugas:

Diberi urutan hambatan yang membutuhkan penekanan (P), menahan (H), atau melepaskan (R) tombol A, menghasilkan jumlah penekanan terkecil yang diperlukan untuk mengatasinya dalam urutan yang diberikan. Tombol A pada awalnya tidak ditahan.

Dinyatakan secara formal: diberi string S karakter PHR, pertimbangkan string bentuk (PH*R)*yang berisi S sebagai urutan, dan hasilkan jumlah terkecil yang mungkin Pdalam string tersebut. Atau, alternatifnya, temukan potongan terkecil dari bentuk P?H*R?yang dapat dibagi S.

Contoh

Mari kita lihat inputnya RHRPHHHR. Tombol A mulai tidak ditahan, jadi untuk mengatasi kendala awal Rdiperlukan tombol yang ditekan lalu dilepaskan (tekan # 1). Selanjutnya kita diharuskan menahan tombol H, yang sekali lagi mengharuskannya ditekan (tekan # 2). Kemudian, kemudian dapat dirilis setelahnya untuk memuaskan Rsetelahnya. Akhirnya, sisanya PHHHRdapat dipenuhi dengan sekali tekan (tekan # 3) diikuti dengan menahan HHHdan melepaskan R. Jadi, jumlah output adalah 3.

Cara lain untuk melihatnya, adalah bahwa kita dapat membagi string input menjadi 3 bagian bentuk di PHH..HHRmana huruf dapat dihilangkan.

R
HR
PHHHR    

Masukkan format

Input akan berupa daftar atau rangkaian elemen yang mewakili pers, tahan, dan lepaskan sebagai pilihan Anda:

  • P, H, R
  • p, h, r
  • 1, 2, 3
  • 0, 1, 2

cocok dengan urutan yang diberikan. Masukan tidak akan kosong.

Kasus uji:

P 1
H 1
R 1
HP 2
RHP 3
HHR 1
PHRH 2
RHRPHHHR 3
HHHHHH 1
PPRRHHPP 6
HPPRHRPRHPPRHPPHRP 12
PRHRHPHHPRRRHPPRHHPPRRRHRHPRPHPRPRHHRPPPRHPRP 28

Papan peringkat:

Tidak
sumber
1
Bagaimana dengan rintangan yang membutuhkan tombol A agar tidak ditahan? Ada empat tombol di grafik (saya pikir ini mungkin juga ada di dalam game)
Random832
3
Pada kenyataannya, ada 3 negara: Tekan, Dimiliki, dan Tidak ditahan. Tidak ada status yang membutuhkan tombol A. Tantangannya sedikit salah jika dibandingkan dengan kenyataan.
user202729
1
@ 11684 "untuk rilis, yah, saat ini tidak ada kasus di mana itu berguna atau penting jadi jangan khawatir tentang bagian itu." (1:48 - 1:52)
user202729
3
Adakah yang ingin melakukan ini dalam perakitan MIPS? (bahasa yang digunakan untuk memprogram Super Mario 64)
user202729
1
@ user202729 Wow, itu satu pancake menyeluruh. Terima kasih!
11684

Jawaban:

3

Pyth , 13 byte

tl:z"P?H*R?"3

Coba di sini! atau Verifikasi semua kasus uji.

Perhatikan bahwa 1juga berfungsi sebagai pengganti 3.

Bagaimana itu bekerja?

tl: z "P? H * R?" 3 | Program lengkap. Mengambil input dari STDIN, output ke STDOUT.

  : z 3 | Pisahkan string input pada kecocokan ...
    "P? H * R?" | Ekspresi reguler "P? H * R?".
 aku | Dapatkan panjangnya.
t | Decrement (karena pemisahan termasuk string kosong).

Lebih lanjut tentang regex:

P? | P - Karakter literal P, case sensitive.
       | ? - Kuantifikasi. Cocok dengan satu atau nol kali karakter sebelumnya.
  H * | H - Karakter literal H, peka huruf besar-kecil.
       | * - Kuantifikasi. Cocok dengan jumlah kemunculan karakter sebelumnya.
    R? | R - Karakter literal R, case sensitive.
       | ? - Kuantifikasi. Cocok dengan satu atau nol kali karakter sebelumnya.
Tuan Xcoder
sumber
Ah, sial, kau mengalahkanku!
Shaggy
bagus! Baris kedua hingga terakhir dalam deskripsi regexp harus bertuliskan "Karakter literal R", kan?
vidstige
@vidstige Ya, terima kasih. Diperbaiki
Mr. Xcoder
2

Jelly , 10 byte

o5ḄƝ%⁵>4S‘

Rantai monadik mengambil daftar ( P,H,R : 0,1,2opsi) dan mengembalikan bilangan bulat, hitungan.

Cobalah online! atau lihat test-suite

Bagaimana?

Efektif bekerja dengan mendapatkan semua pasangan yang berdekatan maka menghitung setiap yang tidak "pasangan kelanjutan" ( PR, PH, HR, atau HH) dan menambahkan satu.

o5ḄƝ%⁵>4S‘ - Link: list of integers (in [0,1,2])  e.g.: [0,0,1,0,2,1,1,2,2,0] (representing PPHPRHHRRP)
o5         - logical OR with 5                          [5,5,1,5,2,1,1,2,2,5]
   Ɲ       - for all adjacent pairs:              i.e.: [5,5],[5,1],[1,5],[5,2],[2,1],[1,1],[1,2],[2,2],[2,5]
  Ḅ        -   convert from binary                      [ 15 ,  11 ,  7  ,  12 ,  5  ,  3  ,  4  ,  6  ,  9 ]
     ⁵     - literal ten
    %      - modulo                                     [  5 ,   1 ,  7  ,   2,   5  ,  3  ,  4  ,  6  ,  9 ]
      >4   - greater than four?                         [  1 ,   0 ,  1  ,   0,   1  ,  0  ,  0  ,  1  ,  1 ]
        S  - sum                                        5
         ‘ - increment                                  6

Solusi 11 byte sebelumnya:

ḅ3Ɲạ3ḟ1,2L‘

Cobalah online! atau lihat test-suite

Bagaimana?

Bekerja seperti di atas, tetapi dengan cara yang sama sekali berbeda ...

ḅ3Ɲạ3ḟ1,2L‘ - Link: list of integers (in [0,1,2])  e.g.: [0,0,1,0,2,1,1,2,2,0] (representing PPHPRHHRRP)
  Ɲ         - for all adjacent pairs:              i.e.: [0,0],[0,1],[1,0],[0,2],[2,1],[1,1],[1,2],[2,2],[2,0]
ḅ3          -   convert from base three                  [ 0  ,  1  ,  3  ,  2  ,  7  ,  4  ,  5  ,  8  ,  6 ]
   ạ3       - absolute difference with three             [ 3  ,  2  ,  0  ,  1  ,  4  ,  1  ,  2  ,  5  ,  3 ]
     ḟ1,2   - filter discard if in [1,2]                 [ 3        ,  0        ,  4              ,  5  ,  3 ]
         L  - length                                     5
          ‘ - increment                                  6

dan yang lainnya, sekali lagi sangat berbeda:

+19*Ɲ%13ḂS‘

(tambahkan 19 untuk masing-masing, kemudian untuk pasangan yang berdekatan melakukan eksponensial, modulo dengan 13, modulo dengan 2, jumlah dan tambahkan satu).

Jonathan Allan
sumber
Jelly baru cepat!
user202729
2

Batch, 69 byte

@set/ab=2,n=0
@for %%b in (%*)do @set/an+=b/2^|!%%b,b=%%b
@echo %n%

Mengambil input sebagai daftar parameter baris perintah 0-diindeks, tetapi Anda dapat menggunakan daftar huruf p, h, rdalam huruf besar atau kecil jika Anda mengetik set /a p=0, h=1, r=2pertama. Penjelasan: bmempertahankan input terakhir (default ke 2untuk dirilis) dan njumlah penekanan. Setiap input menambahkan pers jika input terakhir adalah rilis atau input saat ini adalah pers.

Neil
sumber
Oh, setdapatkah mengatur beberapa variabel sekaligus? Berguna untuk tahu.
user202729
1
@ user202729 set /aadalah evaluasi aritmatika, jadi selama semua variabel yang ingin Anda atur adalah numerik, Anda bisa menggunakan operator koma untuk menyatukan ekspresi penugasan.
Neil
2

Python 2, 44 byte

Penggunaan P-> 1 H-> 2 R-> 3

lambda a:sum(1/y|x/3for x,y in zip([3]+a,a))
feersum
sumber
1

Python 2 , 48 byte

f=lambda a,*l:l==()or(a>l[0]or l[0]==a!=1)+f(*l)

Cobalah online!

Dibawa 0,1,2sebagai input.

ovs
sumber
1

Sekam , 6 5 byte

Lġo&ε

Cobalah online! Input adalah daftar selesai 0,1,2(tautan TIO menggunakan huruf untuk memudahkan penyalinan salinan kasus uji).

Penjelasan

Saya menggunakan ide umum yang sama dengan jawaban Jonathan Jonathan Allan's : berpisah pada kejadian "pasangan diskontinuitas" PP, HP, RH, RR dan RP, dan hitung blok yang dihasilkan. Dalam pengkodean 0,1,2, pasangan ini adalah persisnya yang elemen kirinya adalah 2 atau elemen kanan adalah 0.

Lġo&ε  Input is a list.
 ġ     Split between pairs that do not satisfy:
    ε  the left element is at most 1
  o&   and the right element is truthy.
L      Length.
Zgarb
sumber
1

Javascript (ES6), 30 byte

f=s=>s.match(/P?H*R?/g).length-1
<input id=i oninput="o.innerText=f(i.value)" value="PHHR"><pre id=o>l

Herman L.
sumber
1

Jelly , 10 byte

Pn1></µƝS‘

Cobalah online! atau Test suite! ( Dicuri Dipinjam dari Jonathan.)

Alternatif:

P=1=</µƝS‘

Cobalah online!

Pn1></µƝS‘ | Monadic chain.

      µƝ   | Map over each pair of "neighbours" (x, y) in the list.
P          | And check whether their product...
 n1        | ... 1 if it doesn't equal 1, 0 otherwise...
   >       | Is higher than?
    </     | The pair reduced by "Smaller than?". 1 if x < y, else 0.
        S  | Sum.
         ‘ | Add 1.

Jelly , 11 byte

Disimpan 1 byte dengan bantuan dari caird coinheringaahing.

ḅ3Ɲf⁽vḲD¤L‘

Cobalah online!

Tuan Xcoder
sumber
Aww, saya melewatkan kesempatan untuk menjadi yang pertama menggunakan tetangga cepat :(
caird coinheringaahing
Anda dapat menghapus yang μketiga
caird coinheringaahing
1

Kotlin , 36 byte

Regex("P?H*R?").findAll(i).count()-1

Yg diperindahkan

Regex("P?H*R?").findAll(i).count()-1

Uji

fun f(i:String) =
Regex("P?H*R?").findAll(i).count()-1
data class Test(val input: String, val output: Int)

val TESTS = listOf(
        Test("P", 1),
        Test("H", 1),
        Test("R", 1),
        Test("HP", 2),
        Test("RHP", 3),
        Test("HHR", 1),
        Test("PHRH", 2),
        Test("RHRPHHHR", 3),
        Test("HHHHHH", 1),
        Test("PPRRHHPP", 6),
        Test("HPPRHRPRHPPRHPPHRP", 12),
        Test("PRHRHPHHPRRRHPPRHHPPRRRHRHPRPHPRPRHHRPPPRHPRP", 28)
)

fun main(args: Array<String>) {
    for ((input, expectded) in TESTS) {
        val actual = f(input)
        if (actual != expectded) {
            throw AssertionError("$input $expectded $actual")
        }
    }
}

TIO

TryItOnline

jrtapsell
sumber
0

J , 18 17 byte

-1 Terima kasih kepada @FrownyFrog

1+1#.}:(<+:1=*)}.

Mengambil input dalam bentuk 0,1,2. Fungsi helper pada TIO mengubah kasus uji ke formulir ini.

Cobalah online!

Logika perbandingannya mungkin masih bisa golf. Aku memutar otakku menjadi simpul, mencoba memikirkan pernyataan yang lebih setara dan lebih pendek.

Penjelasan (solusi sebelumnya)

1+1#.2(</+:1=*/)\]

Satu-satunya perbedaan antara solusi saat ini dan yang sebelumnya adalah bagaimana perbandingan dihasilkan. Solusi saat ini secara eksplisit membandingkan elemen-elemen yang berdekatan dengan mengimbangi array dan solusi sebelumnya membandingkan elemen-elemen yang berdekatan dengan melihat infiks 2.

1 + 1 #. 2 (</ +: 1 = */)\ ]
         2               \ ]  On infixes of 2 on the input
                  1 = */        Is the infix 1 1 (two holds)?
            </                  Is the infix x y such that x < y?
               +:               These results NORed
    1 #.                       Add all of the results together (debase to base 1)
1 +                            Add one

Ini akan jauh lebih bersih jika dua pegangan tidak melakukan apa pun. Kode mengambil infiks dua dan memeriksa apakah tidak naik dan bukan dua terus. Jika ini masalahnya, maka kami menambahkan satu ke jumlah akhir kami. Kami harus menambahkan 1 pada bagian akhir karena kami menonaktifkannya dengan cara lain (atau Anda dapat menambahkan _atau nilai lebih dari 2).

Cara memeriksa apakah infiks adalah dua tahan adalah dengan mengalikan dua nilai bersama-sama dan melihat apakah itu satu (dua tahan adalah 1 1).

cole
sumber
1
1+1#.}:(<+:1=*)}.lebih pendek.
FrownyFrog
@FrownyFrog pintar, saya akan mengeditnya masuk
Cole
1
14:1+1#.0=}.*2-}:
FrownyFrog
0

Vim + wc, 25 byte

:s/P\?H*R\?/a/g␊V!wc -c␊␘

adalah kunci kembali dan adalah Ctrl+X

Cobalah online!

Penjelasan

:s/P\?H*R\?/a/g␊    Replace all button presses with the character a
V!wc -c␊␘          Count the characters using the wc command
Herman L.
sumber