Utas polisi
Di utas ini, tugas Anda adalah membuat program / fungsi berbasis rekursi untuk menghasilkan seri integer apa pun. Perampok akan mencoba dan menemukan solusi non-rekursif yang lebih pendek di utas Perampok .
Tantang sinopsis
Dalam banyak bahasa, fungsi rekursif secara signifikan dapat menyederhanakan tugas pemrograman. Namun, sintaks overhead untuk rekursi yang tepat dapat membatasi kegunaannya dalam kode-golf.
The polisi akan membuat program atau fungsi mengambil satu bilangan bulat n
, yang akan menghasilkan pertama n
entri dari seri integer, hanya menggunakan rekursi 1 . Mereka juga harus memastikan ada cara non rekursif yang lebih pendek untuk menghasilkan urutan agar menandai entri mereka aman.
The perampok akan mencoba untuk menemukan lebih pendek program atau fungsi dalam bahasa yang sama, menghasilkan seri integer yang sama, tidak menggunakan rekursi 2 .
Jika pengajuan polisi tidak retak dalam sepuluh hari (240 jam), polisi akan membuktikan bahwa sebenarnya mungkin untuk memiliki pendekatan non-rekursif yang lebih pendek dengan mengungkapkan solusi mereka sendiri. Mereka kemudian dapat menandai pengiriman mereka sebagai aman .
Pemenang tantangan polisi adalah pengajuan berbasis rekursi terpendek (menurut kode-golf ) yang ditandai aman.
Pemenang tantangan perampok adalah perampok yang memecahkan sebagian besar solusi.
1: Itu hanya perlu rekursif dalam sintaksis; Anda tidak perlu khawatir tentang misalnya optimasi panggilan ekor.
2: Sekali lagi, non-rekursif dalam sintaksis; jadi Anda tidak dapat memposting solusi rekursif dan mengklaimnya dikompilasi ke loop berkat optimasi panggilan ekor.
Persyaratan pengiriman
Setiap pengajuan akan mengambil bilangan bulat tunggal n
(berbasis nol atau satu). Pengajuan kemudian akan menampilkan atau mengembalikan n
entri pertama dari serangkaian pilihan integer. (perhatikan bahwa seri bilangan bulat ini tidak boleh bergantung pada n
). Metode input dan output mungkin berbeda antara pendekatan rekursif dan non-rekursif. Seri integer dapat berupa seri deterministik dengan panjang setidaknya 5. Seri harus dijelaskan dengan benar.
Kiriman Anda tidak harus bekerja untuk yang sewenang-wenang n
, tetapi setidaknya harus bekerja n=5
. Pendekatan non-rekursif harus dapat bekerja hingga setidaknya sama n
dengan pendekatan rekursif, atau hingga n=2^15-1
, mana yang lebih kecil.
Pengulangan
Demi tantangan ini, rekursi didefinisikan sebagai menciptakan urutan yang diinginkan menggunakan fungsi (atau fungsi seperti konstruksi) yang memanggil dirinya sendiri (atau memanggil urutan fungsi yang akhirnya memanggil dirinya sendiri; ini termasuk konstruksi seperti kombinator Y). Kedalaman rekursi harus menuju ke infinity seperti n
menuju infinity. Pendekatan non-rekursif adalah segala sesuatu yang tidak rekursif.
sumber
for
dilakukan dengan rekursif di belakang, apakahfor
rekursif atau loop?n
jika secara teoritis benar, tetapi tidak dapat dijalankan karena kendala waktu atau memori?n=5
harus dihitungxfor
tersedia melalui semacam impor?) Jadi mungkin bahasa ini tidak dapat bersaing.Jawaban:
Python 3 , 65 byte (Aman)
Cobalah online!
Coba lagi dengan Python.
Urutannya adalah "jumlah cara untuk mengisi papan 2-by-n dengan kartu domino dalam tiga warna, sehingga tidak ada dua kartu domino berwarna sama yang saling menyentuh". Bukan pada OEIS.
Katakan saja
n=6
. Papan terlihat seperti:dan ini adalah domino tilings yang valid dalam tiga warna (
1-3
masing-masing mewakili warna):tetapi ini bukan (dua domino berwarna sama saling bersentuhan):
Urutan menghitung semua kemungkinan domino yang memenuhi aturan untuk masing-masing
n
.Solusi yang dimaksudkan, 58 byte
Cobalah online!
Sayangnya sepertinya tidak ada yang peduli untuk menyederhanakan hubungan perulangan, yang jelas ditunjukkan dalam kode rekursif. Membuat program dengan perulangan ganda sebagaimana adanya tidak berfungsi karena Python 3.
sumber
Oktaf , 47 byte, dipecahkan oleh l4m2
Cobalah online!
Sebagai contoh, di sini adalah entri Oktaf yang menghasilkan
n
bilangan bulat positif pertama , https://oeis.org/A000027 .sumber
l4m2
mengalahkan Anda.Python 3 , 75 byte, dipecahkan oleh xnor
Cobalah online!
Angka-angka Hamming yang terkenal, alias angka 5-halus ( A051037 ).
Solusi retak, 51 byte
Cobalah online!
Solusi yang dimaksudkan, 74 byte
Cobalah online!
sumber
Keempat (gforth) , 39 byte, dipecahkan oleh NieDzejkob
Cobalah online!
sumber
[1,2,...,n]
, Anda tahu itu kan?Röda , 40 byte
Cobalah online!
Fungsi ini memberikan urutan terbatas berikut (90 angka Fibonacci pertama):
Saya tahu ini dapat menghasilkan lebih banyak angka Fibonacci, tetapi untuk tujuan tantangan ini cukup untuk menghasilkan angka-angka ini.
sumber
JavaScript (Node.js) , 91 byte, Retak oleh l4m2
Cobalah online!
Mencetak n hal pertama dari urutan OEIS A022559 (mulai dari i = 1).
l4m2 cocok 3 untuk loop ke
7472 byte dan meretakkan pos polisi saya:Namun, jawaban yang saya maksudkan sebenarnya hanya memiliki 2 untuk loop:
Cobalah online!
sumber
Fungsi x86 .COM, 12 byte, Retak oleh NieDzejkob
Input DX, Output [DI] ~ [DI + 2 * DX-1]
Solusi Cracker:
Solusi yang dimaksudkan:
sumber
Python 3 , 62 byte, Retak oleh mwchase
Cobalah online!
Saya merasa ini akan terlalu mudah ...
Urutannya adalah urutan Fibonacci
f(n) = f(n-1) + f(n-2)
denganf(0) = f(1) = 1
sumber
Gol> <> , 15 byte, dipecahkan oleh mbomb007
Cobalah online!
Seri ini
0,1,2,3,4,5
tetapi setiap elemen diikuti oleh banyak 0s.Misalnya, beberapa nilai pertama adalah:
sumber
JavaScript, 63 byte, Retak
Cobalah online!
Mengembalikan elemen n pertama dalam array terbalik
sumber
Windows .BAT, 80 Bytes
Pemakaian:
Versi loop dapat diasumsikan dalam kamus saat ini, tetapi harus init atau reset
sumber
Python, 82 byte; retak
Ini adalah implementasi Python rekursif dari urutan OEIS A004001 dalam 82 byte. Lebih banyak latar belakang pada seri ini dapat ditemukan di Wolfram's Mathworld .
30 angka pertama dalam urutan ini adalah:
sumber