Teks rasa
Esolang Underload berbasis stack memiliki ikatan yang menarik dengan pemrograman fungsional. Salah satunya adalah perlakuan terhadap datatype numerik — seperti kalkulus lambda, Anda mewakili bilangan alami N dengan fungsi yang melakukan tindakan N kali.
Untuk mempermudah, kami hanya akan mempertimbangkan hanya sebagian perintah Underload berikut:
:
- Perintah ini menduplikasi item teratas di stack.*
- Perintah ini menggabungkan dua item teratas di stack menjadi satu item.
Kami mendefinisikan angka Underload N sebagai string :
dan *
yang, ketika dieksekusi, mengkonsumsi item teratas di stack, dan menghasilkan N salinan item yang digabungkan bersama-sama. Beberapa contoh:
- Tidak ada angka Underload 0, -1, 1/2, π.
- String kosong
adalah angka Underload 1, karena membiarkan tumpukan tidak tersentuh.
:*
adalah Underload numeral 2, karena menduplikasi item teratas, dan kemudian menggabungkan kedua salinan tersebut menjadi satu item:(A):*
=(A)(A)*
=(AA)
.::**
adalah angka Underload 3:(A)::**
=(A)(A):**
=(A)(AA)*
=(AAA)
.:::***
adalah angka Underload 4.:*:*
juga merupakan angka Underload 4:(A):*:*
=(AA):*
=(AA)(AA)*
=(AAAA)
.
Secara umum, Anda akan menemukan bahwa, jika M
dan N
adalah angka Underload M dan N, maka :N*
adalah angka N +1, danMN
merupakan angka M × N.
Tantangan
Tugas Anda adalah menulis program terpendek (mengambil input pada STDIN) atau fungsi (mengambil input melalui argumen) yang menghasilkan representasi terpendek dari angka Underload untuk inputnya sebagai string. Dengan kata lain, jika inputnya adalah bilangan asli positif N> 1, Anda harus menghasilkan angka N Underload yang panjang karakternya kurang dari atau sama dengan setiap Underload lainnya bilangan N.
Input dan output sampel: ("Input - OUTPUT
.")
- 1 -
.
- 2 -
:*
. - 5 -
::*:**
(2 × 2 +1). - 7 -
::*::***
(2 × 3 +1) atau:::**:**
(3 × 2 +1). - 33 -
::*:*:*:*:**
(2 × 2 × 2 × 2 × 2 + 1). - 49 -
::*:*:*:*::***
(16 × 3 + 1, panjang 14) tetapi tidak::*::***::*::***
(7 × 7, panjang 16).
Jika inputnya bukan angka alami positif, Anda bebas untuk mengembalikan kesalahan, menghasilkan perilaku yang tidak terdefinisi, atau bahkan gagal menghentikannya. Penjelasan tentang metode kiriman Anda untuk menemukan jawabannya sangat dihargai.
Batasan celah jalan standar berlaku: tidak ada input tambahan, tidak ada permintaan web, nilai output / pengembalian harus tepat jawaban dan bukan aliran acak tak terbatas dari :
dan *
, dll.
x
adalah di2*A117498(x)
mana A117498 memberikan kombinasi optimal metode biner dan faktor untuk menemukan rantai tambahan.Jawaban:
GolfScript (
61 60 55 5453 karakter)Ini kurang rumit dari versi saya sebelumnya dan mengambil pendekatan yang sedikit berbeda, tetapi masih kasar. Kami tahu itu
':'X*'*'X*+
adalah solusi kandidat, jadi jika kami menghasilkan semua string yang seimbang hingga panjang itu dan mengambil yang terpendek yang mengevaluasi ke hal yang benar, kami dapat yakin untuk menemukannya.Terima kasih kepada Howard, dari solusinya saya telah mencuri beberapa tweak 1-char.
sumber
.&
tepat setelah loop dalam (yaitu antara~}%
dan}*
.GolfScript (
5453 karakter)Ini adalah pendekatan yang dalam semangat Howard (membangun string yang mengevaluasi ke nilai yang benar dan memilih yang terpendek, bukan kekerasan melalui kandidat string untuk menemukan mereka yang mengevaluasi ke nilai yang benar), tetapi cukup berbeda yang saya pikir itu termasuk dalam jawaban yang terpisah.
Demo online tidak tersedia karena menjalankan versi buggy dari interpreter.
sumber
3+
dengan)
(mengeksploitasi fakta yang[]0=
tidak meninggalkan apa pun di tumpukan) jika tidak[]2>
menyebabkan kesalahan.[]2>
hasil[]
tanpa kesalahan.'1'
.((=
bukan-1=
.Python 2.7 -
878492Penjelasan:
Ini adalah solusi yang sangat mudah. Ini secara rekursif menguji semua representasi yang mungkin dari n sebagai produk dari dua angka atau sebagai
:(n-1)*
, dan kemudian menemukan solusi panjang minimum. range (2, n) diperlukan agar rekursi telah membatasi kedalaman, dan n <2 memberikan case dasar.Catatan:
i dan n / i adalah dua faktor dari n. Pengganti ... dan ... atau ... untuk ... jika ... yang lain ... tidak berfungsi karena '' dinilai salah. min string memberikan salah satu string terpendek. Python 2.7 menyimpan 1 karakter dengan menggunakan / bukannya //.
Sunting: Memindahkan casing dasar ke bagian belakang ekspresi, memungkinkan saya untuk menggunakan ... dan ... atau ... dan mencukur beberapa spasi.
Kasus uji:
sumber
key=len
. Ini memberikan string paling awal secara leksikografis. ( Contoh ). Karena'*' < ':'
ini berarti Anda memiliki bias terhadap solusi yang melibatkan kekuatan 2, tetapi apakah mereka selalu yang terpendek?u(33)
, yang mana pengurutan leksikografis menghasilkan 14-char::**::*::*:***
tetapi memilah menurut panjangnya memberikan 12-char::*:*:*:*:**
GolfScript,
635856 karakterKode mengambil input pada STDIN dan mencetak hasilnya.
Contoh:
Anda dapat menguji kasus Anda sendiri secara online .
sumber
:x(=
. +1, karena dapat menjalankan 49 dalam jumlah waktu yang wajar.x,2>{x\%!},
memberikan semua pembagi sejatix
,{.v=x@/v=+}/
kemudian menggabungkan solusi untukd
danx/d
untuk semua pembagid
.{,}$
mengurutkan mereka berdasarkan panjang dan0=
mengambil yang terpendek dari mereka (ditambah:(x-1)*
kasus awal ).Brachylog 2 , 30 (mungkin akhirnya 26) byte, tantangan tanggal bahasa
Berikut adalah fungsi yang berfungsi dengan implementasi Brachylog 2 saat ini (dan mengembalikan daftar kode karakter karena implementasi saat ini mengalami beberapa masalah dengan penanganan string):
Cobalah online!
Bahasanya masih sangat baru. Berikut adalah versi 26 byte dari program yang harus bekerja sesuai dengan spesifikasi, tetapi menggunakan beberapa fitur yang tidak diimplementasikan, dan dengan demikian belum valid, tetapi mungkin akan ada di masa depan (itu juga bahkan kurang efisien):
Penjelasan
Ide dasarnya cukup sederhana: kami bergantian antara mendekomposisi angka menjadi (1 atau lebih) faktor (tidak harus faktor prima, tetapi faktor 1 tidak diperbolehkan), dan menyatakan masing-masing sebagai 1 + (representasi yang diperoleh dari rekursif panggilan). Ini dijamin untuk mencari semua kemungkinan representasi Underload dari angka (kita dapat menerapkan tahap perkalian "dua kali berturut-turut" dengan mengalikan bersama lebih dari 2 angka, dan tahap kenaikan dua kali berturut-turut melalui memisahkannya dengan tahap perkalian yang mengalikan bersama hanya satu nomor). Kita tidak memerlukan kasus dasar eksplisit, karena penguraian 1 menjadi faktor prima memberi kita daftar kosong, dan dengan demikian kita membangunnya dengan tahap perkalian yang mengalikan angka nol bersama-sama.
Program ini cukup tidak efisien, terutama karena petunjuk urutan evaluasi yang saya berikan (menghasilkan jawaban terpendek hingga terpanjang dalam hal ukuran output akhirnya), sementara memecahkan bagian "terpendek" dari pertanyaan, tidak terlalu bagus dalam hal sebenarnya membuat program selesai dengan cepat ( petunjuk yang jauh lebih berguna adalah "hanya menghasilkan jawaban terpendek pada setiap tahap rekursif", tetapi itu membutuhkan lebih banyak byte ...). Selain itu,
ḋp~c×ᵐ
dapat menghasilkan partisi multiplikatif beberapa kali masing-masing, membuat program ini melakukan banyak pekerjaan yang berlebihan.sumber
J - 81 char
Untuk anak cucu, ini adalah yang terbaik yang bisa saya lakukan di J.
Kami membuat daftar hasil, dimulai dengan dua string kosong (itu adalah
,~
dana:
) mewakili 0 (tidak pernah digunakan) dan 1, dan kemudian iterasi kata kerja di atasnya (penggunaan licik kait, kereta api dan&
) yang menambahkan representasi terpendek nomor berikutnya.Kata kerja aktual yang kita gunakan menggunakan panjang daftar sebagai indikator dari nomor apa kita beroperasi. Pertama, kami memfaktorkan angka ini menjadi pasangan faktor (
#(#~]-:"1<.)@(],.%)2}.i.@#
), dan mengambil setiap pasangan dengan menarik dari array ({~
). Kami mengubah masing-masing pasangan (mungkin ada 0 dari mereka jika bilangan prima) menjadi string tunggal (<@;"1
).Lalu kami menambahkan ke daftar itu entri untuk hasil sebelumnya diurutkan dengan
:
dan*
, dan mengurutkan daftar ini berdasarkan panjangnya ((/:#&>)
). Akhirnya, kami mengambil hasil pertama dari daftar ini (0{
) dan menambahkannya ke akhir array basis ([,
). Ketika loop selesai iterasi, kami memiliki daftar panjang 2 lebih dari input, mulai dari 0. Jadi apa yang harus kami kembalikan adalah string next-to-last (_2{::
).sumber
Jelly , 33 byte, tantangan tanggal kiriman bahasa
Cobalah online!
Solusi brute force langsung.
Penjelasan
Program utama
Program utama menggunakan fungsi helper untuk menghitung semua cara yang mungkin untuk menghasilkan nilai melalui perkalian, kemudian mencoba menghasilkan nilai dengan penambahan, dan mengembalikan kemungkinan terpendek. Ini juga menangani kasus dasar (input dari
1
).Fungsi pembantu
Fungsi helper mencoba semua metode yang mungkin untuk mengekspresikan input sebagai perkalian dua angka, dan saling memanggil program utama secara rekursif untuk mendapatkan representasi terpendek mereka.
sumber
GNU Prolog, 96 byte
Baris pertama adalah tata bahasa yang menerapkan evaluasi Underload, dan bekerja di arah sebaliknya (sebenarnya, itu tidak cukup bekerja di arah maju karena
A#<B
kendala; ubah ini menjadiA#<N
untuk program yang lebih lambat yang bekerja dua arah). Baris kedua mendefinisikan predikat seperti fungsis
(yang merupakan fungsi yang diimplementasikan sebagai solusi untuk program ini) yang menemukan string sesingkat mungkin yang mengevaluasi ke angka yang diberikan sebagai input (ini dengan frustasi menyatakan untuk apa tugas yang relatif sederhana, tetapi itulah Prolog untuk Anda ...).Program ini harus cukup jelas, mengingat bahwa itu lebih atau kurang merupakan terjemahan langsung dari spesifikasi ke tata bahasa, dan kemudian ke sintaksis Prolog; definisi
v
mengatakan bahwaN
adalah 1 dalam string kosong, atauN
merupakanA
×B
(denganA
kurang dariB
kurang dariN
) dan string adalah gabungan dariv(A)
danv(B)
, atauN
adalahM
+ 1 dan string adalah:
concatenated denganv(M)
digabungkan dengan*
. Baris kedua sedikit lebih halus;length(S,_)
berarti "S memiliki panjang", tetapi menetapkan ini sebagai hal pertama di baris bertindak sebagai petunjuk untuk implementasi Prolog bahwa ia harus memeriksa panjang terpendek terlebih dahulu (yang berarti kita akan mendapatkan panjang terpendek yang mungkin untuk nilai pengembalian) .sumber