Skakmat (alias masalah urinoir)

35

Guru Precalc saya memiliki salah satu masalah favoritnya yang ia ciptakan (atau lebih mungkin mencuri terinspirasi oleh xkcd ) yang melibatkan sederetan nurinal. "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-Xatau -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--Xatau -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.

AMACB
sumber
3
Terkait .
betseg
3
Terkait
mbomb007
12
Kasus n = 0 harus 1. Ada tepat satu pengaturan yang merupakan skakmat, dan itu ''. Ini sama dengan faktorial dan permutasi, 0! = 1, karena ada tepat 1 cara untuk mengatur 0 item.
orlp
12
oeis.org/A228361
DJMcMayhem
19
Tidak ada toilet sama sekali memang situasi sekakmat. : D
Titus

Jawaban:

20

Oasis , 5 byte

Kode

cd+2V

Versi diperpanjang

cd+211

Penjelasan

1 = a(0)
1 = a(1)
2 = a(2)

a(n) = cd+
       c      # Calculate a(n - 2)
        d     # Calculate a(n - 3)
         +    # Add them up

Cobalah online!

Adnan
sumber
7
Ini adalah jawaban yang aneh, bahasa dibuat sekitar sebulan yang lalu tanpa dokumentasi yang tepat dalam repo ....
2
@tuskiomi Ada dokumen, diinfo.txt
TuxCrafting
6
@ TùxCräftîñg yakin, jika Anda ingin menjadi teknis. Saya bisa menggambar seekor kuda dan menyebutnya dokumentasi untuk proyek pemrograman saya. itu tidak membuatnya berguna, atau menentukan.
1
@tuskiomi info.txtberguna, berisi dokumentasi untuk setiap perintah Oasis
TuxCrafting
8
@tuskiomi Itulah hasil dari penundaan dan kemalasan. Saya akan mencoba menambahkan dokumentasi ringkas tentang cara kerja bahasa aktual hari ini.
Adnan
12

Java 7, 65 42 byte

int g(int u){return u>1?g(u-2)+g(u-3):1;}

Urutannya hanya menambahkan elemen sebelumnya untuk mendapatkan yang baru. Kiat ujung ke orlp dan Rod untuk metode yang lebih pendek ini;)

Tua:

int f(int u){return u<6?new int[]{1,1,2,2,3,4}[u]:f(u-1)+f(u-5);}

Setelah elemen kelima, celah dalam urutan naik oleh elemen lima sebelumnya.

Geobit
sumber
Jika u = 3 maka fungsi Anda mengembalikan 1 tetapi contoh menunjukkan bahwa itu harus 2.
Poke
Ups! Saya menggunakan ffungsi saya dari cuplikan lain alih-alih berulang. Bodoh saya, memperbaiki ...
Geobits
1
Tidak bisakah bagian terakhir itu ( u>0?u:1;) menjadi 1;?
Conor O'Brien
2
@ Jordan Jika ada nol urinal, maka "setiap urinal sudah terisi" dalam satu konfigurasi yang memungkinkan. Saya percaya test case yang ditunjukkan dalam pertanyaan salah.
Geobits
1
Anda dapat mengganti u>0?u:1;)dengan 1;jika Anda mengubah perbandingan pertama u>1, maka pada u = 2 output akan menjadi g (0) + g (-1), yang akan menjadi 2
Rod
9

Python 2, 42 40 39 35 byte

f=lambda n:n>1and f(n-2)+f(n-3)or 1

Menghasilkan set yang sebenarnya:

lambda n:["{:0{}b}".format(i,n).replace("0","-").replace("1","X")for i in range(2**n)if"11"not in"{:0{}b}".format(i*2,2+n).replace("000","11")]
orlp
sumber
8

Ruby, 58 34 byte

Sangat terinspirasi oleh jawaban Java asli Geobits.

f=->n{n<3?n:n<6?n-1:f[n-1]+f[n-5]}

Lihat di repl.it: https://repl.it/Dedh/1

Percobaan pertama

->n{(1...2**n).count{|i|!("%0#{n}b"%i)[/11|^00|000|00$/]}}

Lihat di repl.it: https://repl.it/Dedh

Jordan
sumber
6

Python, 33 byte

f=lambda n:+(n<2)or f(n-2)+f(n-3)

Menggunakan kasus dasar bergeser f(-1) = f(0) = f(1) = 1. Jika Truedapat digunakan untuk 1, kita tidak perlu 3 byte untuk +().

Tidak
sumber
6

J, 31 27 23 byte

Disimpan 4 byte berkat mil!

0{]_&(]}.,+/@}:)1 1 2"_

Penjelasan akan segera hadir.

Solusi lama

(>.1&^)`(-&3+&$:-&2)@.(2&<)

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:

   1 ^ 0 1 2
1 1 1
   (1&^) 0 1 2
1 1 1
   0 1 2 >. (1&^) 0 1 2
1 1 2
   (>.1&^) 0 1 2
1 1 2

Di sini, >.ambil maks dua nilai. Dengan demikian, menghasilkan 1, 1, dan 2 sebagai istilah awal.

Kata kerja kedua dalam gerund adalah garpu:

-&3 +&$: -&2

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

   f =: (>.1&^)`(-&3+&$:-&2)@.(2&<)
   f 0
1
   f 2
2
   f 4
3
   f 6
5
   f 8
9
   F =: f"0         NB. for tables
   F i.13
1 1 2 2 3 4 5 7 9 12 16 21 28
   i.13
0 1 2 3 4 5 6 7 8 9 10 11 12
   (,. F) i.13
 0  1
 1  1
 2  2
 3  2
 4  3
 5  4
 6  5
 7  7
 8  9
 9 12
10 16
11 21
12 28
Conor O'Brien
sumber
4

MATL , 25 23 byte

W:qB7BZ+t!XAw3BZ+!3>a>s

Cobalah 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. 1dalam array ini mewakili posisi yang diduduki. Misalnya, untuk input 4array A adalah

0 0 0 0
0 0 0 1
0 0 1 0
···
1 1 1 0
1 1 1 1

Kode 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:

0 0 0 0
0 0 1 1
0 1 1 1
···
2 3 2 1
2 3 3 2

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 1di A. Secara ekuivalen, ia tidak dapat memiliki dua nilai bersebelahan dalam B melebihi 1. Jadi kita dapat mendeteksi ini dengan menggabungkan B dengan [1 1]dan memeriksa bahwa dalam array yang dihasilkan, C,

0 0 0 0
0 1 2 1
1 2 2 1
···
5 5 3 1
5 6 5 2

tidak ada nilai di baris yang melebihi 3. Hasil akhir adalah jumlah konfigurasi yang memenuhi kedua kondisi tersebut.

W:q    % Range [0 1 ... n-1], where n is implicit input
B      % Convert to binary. Each number produces a row. This is array A
7B     % Push array [1 1 1] 
Z+     % 2D convolution, keeping size. Entries that are 1 or are horizontal 
       % neighbours of 1 produce a positive value. This is array B
t!     % Duplicate and transpose (rows become columns)
XA     % True for columns that contain no zeros
w      % Swap. Brings array B to top
3B     % Push array [1 1]
Z+     % 2D convolution, keeping size. Two horizontally contiguous entries
       % that exceed 1 will give a result exeeding 3. This is array C
!      % Transpose
3>     % Detect entries that exceed 3
a      % True for columns that contain at least one value that exceeds 3
>      % Element-wise greater-than comparison (logical and of first
       % condition and negated second condition)
s      % Sum (number of true values)
Luis Mendo
sumber
4

PHP, 105 113 93 byte

+3 untuk n=1; +9 untuk $argv, -1-3 golf
-20: perhatikan bahwa saya tidak perlu kombinasi, tetapi hanya hitungan mereka

for($i=1<<$n=$argv[1];$i--;)$r+=!preg_match("#11|(0|^)0[0,]#",sprintf("%0{$n}b,",$i));echo$r;

jalankan bersama -r

loop dari 2 ** n-1 ke 0:

  • memeriksa biner representasi n-digit untuk 11, 000, 00di awal atau akhir, atau satu0
  • jika tidak cocok, tambah hasilnya

hasil cetak

ukuran yang sama, regex sedikit lebih sederhana

for($i=1<<$n=$argv[1];--$i;)$r+=!preg_match("#11|^00|00[,0]#",sprintf("%0{$n}b,",$i));echo$r;
  • loop dari 2 ** n-1 ke 1 (bukan 0)
  • periksa representasi biner untuk 11, 00di awal atau di akhir, atau000
  • tidak mencetak apapun untuk n = 0

PHP, 82 byte

Jawaban Arnauld porting dan golf :

for($i=$k=1<<$n=$argv[1];--$i;)$r+=!($i&$x=$i/2|$i*2)&&(($i|$x)&~$k)==$k-1;echo$r;

tidak mencetak apapun untuk n = 0

Titus
sumber
tambahkan 3 byte untuk yang baru n=0: masukkan ?:1sebelum final;
Titus
4

Jelly , 11 byte

,’fR_2߀So1

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

,’fR_2߀So1  Main link. Argument: n

 ’           Decrement; yield n - 1.
,            Pair; yield [n, n - 1].
   R         Range; yield [1, ..., n].
  f          Filter; keep the elements that are common to both lists.
             This yields [n, n - 1] if n > 1, [1] if n = 1, and [] if n < 1.
    _2       Subtract 2 from both elements, yielding [n - 2, n - 3], [-1], or [].
      ߀     Recursively call the main link for each integer in the list.
        S    Take the sum of the resulting return values.
         o1  Logical OR with 1; correct the result if n < 1.
Dennis
sumber
2
Bagaimana cara kerjanya? Apakah itu menggunakan rumus rekursif, atau yang lain?
Conor O'Brien
@ ConorO'Brien Ya, ini menggunakan rumus rekursif. Saya telah menambahkan penjelasan.
Dennis
4

JavaScript (ES6) / Rekursif, 30 27 byte

Sunting: disimpan 3 byte berkat Shaun H

let

f=n=>n<3?n||1:f(n-2)+f(n-3)

for(var n = 1; n < 16; n++) {
  console.log(n, f(n));
}

JavaScript (ES6) / Non-rekursif 90 77 byte

Sunting: disimpan 13 byte berkat Conor O'Brien dan Titus

let f =

n=>[...Array(k=1<<n)].map((_,i)=>r+=!(i&(x=i>>1|i+i))&&((i|x)&~k)==k-1,r=0)|r

for(var n = 1; n < 16; n++) {
  console.log(n, f(n));
}

Arnauld
sumber
1
Saya pikir ((i|r|l)&(k-1))bisa menjadi ((i|r|l)&k-1), atau bahkan((i|r|l)&~-k)
Conor O'Brien
satu byte: i<<1-> i*2ataui+i
Titus
1
Anda dapat menggunakan satu variabel untuk l dan r, tabungan 6 bytes: !(i&(x=i>>1|i+i))&&((i|x)&(k-1))==k-1; dan jika Anda dapat menyisipkan di ,k--suatu tempat, Anda dapat menggantinya k-1dengan kuntuk menyimpan parens.
Titus
&(k-1)toh tidak membutuhkan orangtua; tetapi Anda bisa menggunakannya &~k.
Titus
1
Saya hanya akan meninggalkan ini di sini:f=n=>n<3?n||1:f(n-2)+f(n-3)
Shaun H
3

Mathematica, 35 byte

a@0=a@1=1;a@2=2;a@b_:=a[b-2]+a[b-3]

Menentukan fungsi a. Mengambil integer sebagai input dan mengembalikan integer sebagai output. Solusi rekursif sederhana.

LegionMammal978
sumber
3

AnyDice , 51 byte

function:A{ifA<3{result:(A+2)/2}result:[A-2]+[A-3]}

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 dan a(2)=2menggunakan 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.

DanTheMan
sumber
3

Perl, 35 34 byte

Termasuk +1 untuk -p

Berikan masukan pada STDIN

checkmate.pl <<< 8

checkmate.pl:

#!/usr/bin/perl -p
$\+=$b-=$.-=$\-$b*4for(++$\)x$_}{

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:

#!/usr/bin/perl -p
$_=grep!/XX|\B-\B/,glob"{X,-}"x$_

tapi itu tidak berhasil 0

Ton Hospel
sumber
2

JavaScript (ES6), 62 byte

n=>[1,...Array(n)].reduce(($,_,i,a)=>a[i]=i<3?i:a[i-3]+a[i-2])

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:

n=>[1,...Array(n)].reduce((p,_,i,a)=>a[i]=i<5?i+2>>1:a[i-5]+p)
Neil
sumber
2

Jelly , 19 byte

Solusi rekursif adalah mungkin lebih pendek ...

Ḥ⁹_c@⁸
+3µ:2R0;瀵S

Lihat di TryItOnline
Atau lihat seri untuk n = [0, 99], juga di TryItOnline

Bagaimana?

Mengembalikan nomor n+3Padovan ke th dengan menghitung kombinasi

Ḥ⁹_c@⁸ - Link 1, binomial(k, n-2k): k, n
Ḥ      - double(2k)
 ⁹     - right argument (n)
  _    - subtract (n-2k)
     ⁸ - left argument (k)
   c@  - binomial with reversed operands (binomial(k, n-2k))

+3µ:2R0;瀵S - Main link: n
  µ       µ  - monadic chain separation
+3           - add 3 (n+3)
   :2        - integer divide by 2 ((n+3)//2)
     R       - range ([1,2,...,(n+3)//2]
      0;     - 0 concatenated with ([0,1,2,...,(n+3)//2]) - our ks
        ç€   - call previous link as a dyad for each
           S - sum
Jonathan Allan
sumber
2

> <> , 25 + 2 = 27 byte

211rv
v!?:<r@+@:$r-1
>rn;

Membutuhkan input untuk hadir pada stack saat program dimulai, jadi +2 byte untuk -vflag. Cobalah online!

Baris pertama menginisialisasi tumpukan 1 1 2 n, di mana nnomor input. Baris kedua, berjalan mundur, memeriksa yang nlebih besar dari 1. Jika itu, ndikurangi dan elemen berikutnya dalam urutan dihasilkan sebagai berikut:

r$:@+@r              a(n-3) a(n-2) a(n-1) n

r        Reverse   - n a(n-1) a(n-2) a(n-3)
 $       Swap      - n a(n-1) a(n-3) a(n-2)
  :      Duplicate - n a(n-1) a(n-3) a(n-2) a(n-2)
   @     Rotate 3  - n a(n-1) a(n-2) a(n-3) a(n-2)
    +    Add       - n a(n-1) a(n-2) a(n)
     @   Rotate 3  - n a(n) a(n-1) a(n-2)
      r  Reverse   - a(n-2) a(n-1) a(n) n

Baris terakhir menampilkan angka di bagian bawah tumpukan, yang merupakan elemen yang diperlukan dalam urutan.

Sok
sumber
2

CJam , 20 byte

1_2_{2$2$+}ri*;;;o];

Cobalah online!

Penjelasan

Ini menggunakan hubungan pengulangan yang ditunjukkan di halaman OEIS .

1_2_                   e# Push 1, 1, 2, 2 as initial values of the sequence
           ri          e# Read input
    {     }  *         e# Repeat block that many times
     2$2$              e# Copy the second and third elements from the top
         +             e# Add them
              ;;;      e# Discard the last three elements
                 o     e# Output
                  ];   e# Discard the rest to avoid implicit display
Luis Mendo
sumber
2

05AB1E , 12 byte

XXXIGX@DŠ0@+

Penjelasan

XXX            # initialize stack as 1, 1, 1
   IG          # input-1 times do:
     X@        # get the item 2nd from bottom of the stack
       DŠ      # duplicate and push one copy down as 2nd item from bottom of the stack
         0@    # get the bottom item from the stack
           +   # add the top 2 items of the stack (previously bottom and 2nd from bottom)
               # implicitly print the top element of the stack after the loop

Cobalah online!

Emigna
sumber
1

FRACTRAN, 104 93 byte

Input adalah 11**n*29dan output 29**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.

403/85 5/31 3/5 9061/87 3/41 37/3 667/74 37/23 7/37 38/91 7/19 5/77 1/7 1/17 1/2 340/121 1/11

Tidak melakukanolf

               At the start we have 11**n * 29
1/11           If n < 2, we remove the 11s and print 29**1
340/121        If n >= 2, we subtract two 11s (n-2) and add one 17, two 2s and one 5.
                 We now have 17**1 * 29**1 * 2**2 * 5.
                 These are the register for a, b, c at registers 17, 29, and 2.
                 5 is an indicator to start the first loop.
                 This loop will move a to register 13.
403/85 5/31    Remove the 17s one at a time, adds them to the 13 register.
                 5 and 31 reset the loop.
3/5            Next loop: moves b to a and adds b to a in register 13.
9061/87 3/41   Remove the 29s one at a time, adds them to the 17 and 13 registers.
                 3 and 41 reset the loop.
37/3           Next loop: moves c to b in register 29.
667/74 37/23   Remove the 2s one at a time, adds them to the 29 register.
                 37 and 23 reset the loop.
7/37           Next loop: moves a+b to c in register 2.
38/91 7/19     Remove the 13s one at a time, adds them to the 2 register.
                 7 and 19 reset the loop.
5/77           Move to the first loop if and only if we have an 11 remaining.
1/7 1/17 1/2   Remove the 7 loop indicator, and all 17s and 2s.
               Return 29**checkmate(n).
Sherlock9
sumber
1

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!

╗211╜¬`);(+)`nak╜2╜2<I@E

Tidak melakukanolf

         Implicit input n.
╗        Save n to register 0.
211      Stack: 1, 1, 2. Call them a, b, c.
╜¬       Push n-2.
`...`n   Run the following function n-2 times.
  );       Rotate b to TOS and duplicate.
  (+       Rotate a to TOS and add to b.
  )        Rotate a+b to BOS. Stack: b, c, a+b
         End function.
ak       Invert the resulting stack and wrap it in a list. Stack: [b, c, a+b]
╜        Push n.
2        Push 2.
╜2<      Push 2 < n.
I        If 2<n, then 2, else n.
@E       Grab the (2 or n)th index of the stack list.
         Implicit return.
Sherlock9
sumber
1

Sebenarnya , 18 byte

Ini sebenarnya pelabuhan jawaban Jelly yang lebih panjang dari Dennis. Saran golf diterima. Cobalah online!

3+;╖½Lur⌠;τ╜-@█⌡MΣ

Tidak melakukanolf

         Implicit input n.
3+       Add 3. For readibility, m = n+3.
;╖       Duplicate and store one copy of m in register 0.
½Lu      floor(m/2) + 1.
r        Range from 0 to (floor(m/2)+1), inclusive.
⌠...⌡M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  τ╜-      Push m-2k. Stack: [m-2k, k]
  @█       Swap k and m-2k and take binomial (k, m-2k).
            If m-2k > k, █ returns 0, which does not affect the sum() that follows.
         End function.
Σ        Sum the list that results from the map.
         Implicit return.
Sherlock9
sumber