StickStack adalah bahasa pemrograman berbasis stack yang sangat sederhana dengan hanya dua instruksi:
|
mendorong panjang tumpukan ke tumpukan-
muncul dua elemen teratas dari tumpukan dan mendorong kembali perbedaannya (second topmost - topmost
)
Detail bahasa
- Tumpukan kosong di awal program.
- Semua instruksi dijalankan secara berurutan dari kiri ke kanan.
- Jika ada kurang dari 2 angka di tumpukan,
-
instruksi tersebut ilegal. - Pada akhir eksekusi stack harus berisi tepat satu nomor .
Bilangan bulat apa pun dapat dihasilkan oleh program StickStack. Sebagai contoh:
|||--||-- generates the number 2 through the following stack states:
[]
[0]
[0, 1]
[0, 1, 2]
[0, -1]
[1]
[1, 1]
[1, 1, 2]
[1, -1]
[2]
Untuk mengevaluasi kode StickStack Anda, Anda dapat menggunakan evaluator online (CJam) ini . (Terima kasih atas @Martin untuk kodenya.)
Tugas
Anda harus menulis program atau fungsi yang memberikan angka integer sebagai input output atau mengembalikan string yang mewakili program StickStack yang menampilkan nomor yang diberikan.
Mencetak gol
- Skor utama Anda adalah total panjang program StickStack untuk kasus uji yang diberikan di bawah ini. Skor yang lebih rendah lebih baik.
- Kiriman Anda hanya valid jika Anda menjalankan program pada semua kasus uji dan menghitung skor Anda.
- Skor sekunder (tiebreak) Anda adalah panjang dari program atau fungsi pembangkit Anda.
Masukkan kasus uji
(Setiap angka adalah test case yang berbeda.)
-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730
Program Anda harus bekerja untuk bilangan bulat apa pun (yang tipe data Anda bisa tangani) tidak hanya untuk kasus uji yang diberikan. Solusi untuk nomor tes tidak boleh di-hardcode ke dalam program Anda. Jika ada keraguan tentang hardcoding nomor tes akan diubah.
sumber
Jawaban:
Python 2 - 5188
Cukup hemat waktu, dan tampaknya (mungkin) solusi optimal. Saya mengamati bahwa pola seperti
|||||-|||-|-|-|------
(solusi optimal untuk 25)dapat digambarkan sebagai
di mana masing-masing nilai total pada akhir adalah jumlah dari (nilai setiap tingkat dikalikan jumlah '|' s). Jadi misalnya di atas, sudah kita miliki
-1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25
. Dengan menggunakan ini saya menulis solusi ini yang menghasilkan output serupa dengan jawaban lain, dan dalam jumlah waktu yang sepele.Saya percaya ini adalah solusi optimal, karena saya menguji setiap ketinggian optimal yang mungkin (saya benar-benar menguji lebih dari yang diperlukan) dan saya cukup yakin solusinya selalu melibatkan paling banyak satu lapisan dengan dua 's selain yang terakhir (saya bisa garansi ini untuk angka positif tetapi tidak 100% yakin tentang negatif).
Ini kode yang saya gunakan untuk mengujinya
sumber
Jawa, 5208
524053066152Ini adalah fungsi rekursif yang tepi lebih dekat ke target, dengan kasus dasar ketika sampai dalam 5 (yang sering hanya satu langkah).
Pada dasarnya, Anda bisa mendapatkan
(a*b)+(a/2)
untuk(a+b)*2
tongkat dengan pola sederhana. Jikaa
aneh, hasilnya akan negatif, sehingga mengarah ke beberapa logika aneh.Ini membutuhkan satu menit atau lebih untuk 2 31 -1, dengan panjang 185.367 sebagai hasilnya. Ini bekerja hampir seketika untuk semua kasus uji. Skornya
4*(sqrt|n|)
rata-rata. Kasing uji individual terpanjang adalah9730
, yang menghasilkan tumpukan stick sepanjang 397:Memperbarui:
Menemukan cara yang lebih pendek untuk menambah / mengurangi dari pola dasar. Kembali memimpin (untuk sekarang)!
Dengan harness dan test case:
Akan bermain golf (lebih banyak) jika tidak ada pertandingan yang pasti.
sumber
JavaScript (ES6) 5296
6572Sunting Seperti yang saya katakan dalam penjelasan saya, saya tidak pandai memecahkan persamaan bilangan bulat. Tebakan saya tentang nilai b tidak begitu baik, jadi saya telah memperluas rentang nilai untuk dicoba.
Dan (wow) saya memimpin sekarang.Edit 2 Bug fix, hasil yang sama. Saya punya ide, tapi tidak bisa memahaminya.
Bytes: ~ 460, cukup golf. Ini bekerja pada bilangan bulat 32 bit, jalankan waktu dekat 0.
Kode tersebut adalah fungsi F (tersembunyi dalam cuplikan) di bawah ini.
Jalankan cuplikan untuk menguji (di FireFox).
Tampilkan cuplikan kode
Penjelasan
Angka-angka positif, untuk memulai. Mulai dengan "basis" (coba di CJam jika Anda suka, spasi diperbolehkan)
Ringkasan: 1 stick, lalu b * 2 stick, lalu b * 2 strip
Kemudian coba tambahkan satu atau lebih '- |' di tengah split. Masing-masing menambahkan kenaikan tetap yang merupakan dua kali basis awal dan dapat diulang berkali-kali. Jadi kami memiliki rumus, dengan b = basis dan r = faktor pengulangan kenaikan
Lihat? Nilai tambah bertambah dengan cepat dan setiap penambahan hanya 2 karakter. Peningkatan basis memberi 4 karakter lagi setiap kali.
Diberikan v dan rumus kita v = b + r * 2 * b, kita perlu menemukan 2 ints b dan r. Saya bukan ahli dalam persamaan semacam ini, tetapi b = int sqrt (v / 2) adalah tebakan awal yang bagus.
Kemudian kita memiliki r dan b yang bersama-sama memberikan nilai dekat v. Kita mencapai v persis dengan kenaikan berulang (|| -) atau penurunan (| -).
Ikuti alasan yang sama untuk angka negatif, sayangnya rumusnya sama tetapi tidak sama.
sumber
JavaScript, 398710
94 byte / karakter kode
Saya datang dengan solusi! ... dan kemudian baca jawaban Sparr dan itu persis sama.
Kupikir aku akan mempostingnya, karena js memungkinkan untuk karakter yang sedikit lebih sedikit.
Berikut adalah versi kode yang tidak dijinakkan:
sumber
Python, 398710 (71 byte)
Solusi yang paling sederhana, saya pikir. Menggunakan 4 * n (+/- 1) karakter stickstack untuk mewakili n.
sumber