Guru Precalc saya memiliki salah satu masalah favoritnya yang ia ciptakan (atau lebih mungkin mencuri terinspirasi oleh xkcd ) yang melibatkan sederetan n
urinal. "Skakmat" adalah situasi di mana setiap urinoir sudah terisi ATAU memiliki urin yang terisi di sebelahnya. Misalnya, jika seseorang adalah seorang X
, maka
X-X--X
dianggap sekakmat. Perhatikan bahwa seseorang tidak dapat menempati urinoir di sebelah urinoir yang sudah diduduki.
Tugas
Program Anda akan mengambil nomor melalui stdin
, argumen baris perintah, atau argumen fungsi. Program Anda kemudian akan mencetak atau mengembalikan jumlah cara skakmat dapat terjadi dengan jumlah urinal yang dimasukkan.
Contohnya
0 -> 1
(penghitungan kasus null sebagai skakmat)
1 -> 1
( X
)
2 -> 2
( X-
atau -X
)
3 -> 2
( X-X
atau -X-
)
4 -> 3
( X-X-
, -X-X
, atau X--X
)
5 -> 4
( X-X-X
, X--X-
, -X-X-
, atau -X--X
)
6 -> 5
( X-X-X-
, X--X-X
, X-X--X
, -X--X-
atau -X-X-X
)
7 -> 7
( X-X-X-X
, X--X-X-
, -X-X--X
, -X--X-X
, X-X--X-
, X--X--X
atau -X-X-X-
)
8 -> 9
( -X--X--X
, -X--X-X-
, -X-X--X-
, -X-X-X-X
, X--X--X-
, X--X-X-X
, X-X--X-X
, X-X-X--X
, X-X-X-X-
)
...
Mencetak gol
Program terkecil dalam byte menang.
''
. Ini sama dengan faktorial dan permutasi, 0! = 1, karena ada tepat 1 cara untuk mengatur 0 item.Jawaban:
Oasis , 5 byte
Kode
Versi diperpanjang
Penjelasan
Cobalah online!
sumber
info.txt
info.txt
berguna, berisi dokumentasi untuk setiap perintah OasisJava 7,
6542 byteUrutannya hanya menambahkan elemen sebelumnya untuk mendapatkan yang baru. Kiat ujung ke orlp dan Rod untuk metode yang lebih pendek ini;)
Tua:
Setelah elemen kelima, celah dalam urutan naik oleh elemen lima sebelumnya.
sumber
f
fungsi saya dari cuplikan lain alih-alih berulang. Bodoh saya, memperbaiki ...u>0?u:1;
) menjadi1;
?u>0?u:1;)
dengan1;
jika Anda mengubah perbandingan pertamau>1
, maka pada u = 2 output akan menjadi g (0) + g (-1), yang akan menjadi 2Python 2,
42403935 byteMenghasilkan set yang sebenarnya:
sumber
Ruby,
5834 byteSangat terinspirasi oleh jawaban Java asli Geobits.
Lihat di repl.it: https://repl.it/Dedh/1
Percobaan pertama
Lihat di repl.it: https://repl.it/Dedh
sumber
Python, 33 byte
Menggunakan kasus dasar bergeser
f(-1) = f(0) = f(1) = 1
. JikaTrue
dapat digunakan untuk 1, kita tidak perlu 3 byte untuk+()
.sumber
J,
312723 byteDisimpan 4 byte berkat mil!
Penjelasan akan segera hadir.
Solusi lama
Ini adalah agenda. LHS adalah gerund yang terdiri dari dua kata kerja:
>.1&^
dan-&3+&$:-&2
. Yang pertama digunakan jika kondisi (2&<
) gagal. Itu berarti garpu>.1&^
diaktifkan atas argumen. Mengamati:Di sini,
>.
ambil maks dua nilai. Dengan demikian, menghasilkan 1, 1, dan 2 sebagai istilah awal.Kata kerja kedua dalam gerund adalah garpu:
Tine kiri dan kanan diterapkan pada kata kerja, masing-masing dikurangi 3 dan 2; maka kata kerja tengah disebut dengan argumen kiri dan kanan sama dengan mereka.
$:
memanggil kata kerja pada setiap argumen, dan+
menambahkan keduanya. Ini pada dasarnya setara dengan($: arg - 3) + ($: arg - 2)
Uji kasus
sumber
MATL ,
2523 byteCobalah online! Atau periksa semua kasus uji .
Penjelasan
Dua belitan! Yay!
Ini membangun sebuah array, katakanlah A, di mana setiap konfigurasi yang mungkin adalah sebuah baris.
1
dalam array ini mewakili posisi yang diduduki. Misalnya, untuk input4
array A adalahKode kemudian menggabungkan array A dengan
[1 1 1]
. Ini memberikan array B. Posisi yang diduduki dan tetangga dari posisi yang ditempati di A memberikan hasil yang tidak nol dalam array B:Jadi syarat pertama untuk konfigurasi menjadi skakmat adalah bahwa B tidak mengandung nol di baris itu. Ini berarti bahwa dalam barisan A itu tidak ada posisi kosong, atau ada beberapa tetapi tetangga dari posisi yang diduduki.
Kami membutuhkan kondisi kedua. Misalnya, baris terakhir memenuhi kondisi di atas, tetapi bukan bagian dari solusi karena konfigurasi tidak valid untuk memulai. Konfigurasi yang valid tidak dapat memiliki dua posisi yang diduduki tetangga, yaitu tidak dapat memiliki dua bersebelahan
1
di A. Secara ekuivalen, ia tidak dapat memiliki dua nilai bersebelahan dalam B melebihi1
. Jadi kita dapat mendeteksi ini dengan menggabungkan B dengan[1 1]
dan memeriksa bahwa dalam array yang dihasilkan, C,tidak ada nilai di baris yang melebihi
3
. Hasil akhir adalah jumlah konfigurasi yang memenuhi kedua kondisi tersebut.sumber
PHP,
10511393 byte+3 untuk
n=1
; +9 untuk$argv
, -1-3 golf-20: perhatikan bahwa saya tidak perlu kombinasi, tetapi hanya hitungan mereka
jalankan bersama
-r
loop dari 2 ** n-1 ke 0:
11
,000
,00
di awal atau akhir, atau satu0
hasil cetak
ukuran yang sama, regex sedikit lebih sederhana
11
,00
di awal atau di akhir, atau000
PHP, 82 byte
Jawaban Arnauld porting dan golf :
tidak mencetak apapun untuk n = 0
sumber
n=0
: masukkan?:1
sebelum final;
Jelly , 11 byte
Cobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
sumber
JavaScript (ES6) / Rekursif,
3027 byteSunting: disimpan 3 byte berkat Shaun H
JavaScript (ES6) / Non-rekursif
9077 byteSunting: disimpan 13 byte berkat Conor O'Brien dan Titus
sumber
((i|r|l)&(k-1))
bisa menjadi((i|r|l)&k-1)
, atau bahkan((i|r|l)&~-k)
i<<1
->i*2
ataui+i
!(i&(x=i>>1|i+i))&&((i|x)&(k-1))==k-1
; dan jika Anda dapat menyisipkan di,k--
suatu tempat, Anda dapat menggantinyak-1
dengank
untuk menyimpan parens.&(k-1)
toh tidak membutuhkan orangtua; tetapi Anda bisa menggunakannya&~k
.f=n=>n<3?n||1:f(n-2)+f(n-3)
Mathematica, 35 byte
Menentukan fungsi
a
. Mengambil integer sebagai input dan mengembalikan integer sebagai output. Solusi rekursif sederhana.sumber
AnyDice , 51 byte
Seharusnya ada lebih banyak jawaban AnyDice di sekitar sini.
Solusi saya mendefinisikan fungsi rekursif yang menghitung
a(n)=a(n-2)+a(n-3)
. Ia kembalia(0)=a(1)=1
dana(2)=2
menggunakan beberapa sihir divisi integer.Cobalah online
Catatan: output mungkin terlihat aneh, dan itu karena biasanya digunakan untuk menampilkan probabilitas dadu. Lihat saja angka di sebelah kiri grafik batang.
sumber
Perl,
3534 byteTermasuk +1 untuk
-p
Berikan masukan pada STDIN
checkmate.pl
:Formula rahasia yang baru dikembangkan. Riak memperbarui 3 variabel keadaan tanpa perlu penugasan paralel.
Sama pendeknya (tapi jauh lebih lambat dan lebih banyak memori) untuk menyelesaikan masalah aslinya:
tapi itu tidak berhasil
0
sumber
JavaScript (ES6), 62 byte
Ini adalah pertama kalinya saya membutuhkan dua nama variabel dummy. Versi rekursif mungkin akan lebih pendek, tapi saya sangat suka
reduce
... Edit: Menemukan solusi, juga 62 byte, yang hanya memiliki satu variabel dummy:sumber
Jelly , 19 byte
Solusi rekursif adalah
mungkinlebih pendek ...Lihat di TryItOnline
Atau lihat seri untuk
n = [0, 99]
, juga di TryItOnlineBagaimana?
Mengembalikan nomor
n+3
Padovan ke th dengan menghitung kombinasisumber
> <> , 25 + 2 = 27 byte
Membutuhkan input untuk hadir pada stack saat program dimulai, jadi +2 byte untuk
-v
flag. Cobalah online!Baris pertama menginisialisasi tumpukan
1 1 2 n
, di manan
nomor input. Baris kedua, berjalan mundur, memeriksa yangn
lebih besar dari 1. Jika itu,n
dikurangi dan elemen berikutnya dalam urutan dihasilkan sebagai berikut:Baris terakhir menampilkan angka di bagian bawah tumpukan, yang merupakan elemen yang diperlukan dalam urutan.
sumber
CJam , 20 byte
Cobalah online!
Penjelasan
Ini menggunakan hubungan pengulangan yang ditunjukkan di halaman OEIS .
sumber
05AB1E , 12 byte
Penjelasan
Cobalah online!
sumber
FRACTRAN,
10493 byteInput adalah
11**n*29
dan output29**checkmate(n)
.Ini sebagian besar untuk bersenang-senang, terutama karena saya saat ini sedang dikalahkan oleh Python, JS, dan Java. Jumlah byte yang sama dengan PHP: D Selamat datang saran Golf.
Tidak melakukanolf
sumber
Sebenarnya, 25 byte
Ini tampaknya agak lama untuk
f(n) = f(n-2) + f(n-3)
hubungan pengulangan yang sederhana . Saran golf diterima. Cobalah online!Tidak melakukanolf
sumber
Sebenarnya , 18 byte
Ini sebenarnya pelabuhan jawaban Jelly yang lebih panjang dari Dennis. Saran golf diterima. Cobalah online!
Tidak melakukanolf
sumber
Stax , 7 byte
Jalankan dan debug itu
Menggunakan relasi perulangan.
C(n) = C(n-2) + C(n-3)
sumber
C (gcc) , 33 byte
Cobalah online!
sumber
Haskell , 27 byte
Cobalah online!
sumber