Schachmatt (auch bekannt als das Urinalproblem)

35

Mein Precalc-Lehrer hat eines seiner Lieblingsprobleme, das er sich ausgedacht hat (oder wahrscheinlich von xkcd inspiriert gestohlen hat ) und an dem eine Reihe von Urinalen beteiligt ist. "Schachmatt" ist eine Situation, in der jedes Urinal bereits besetzt ist ODER sich ein besetztes Urinal daneben befindet. Wenn zum Beispiel eine Person eine ist , dannnX

X-X--X

wird als Schachmatt angesehen. Beachten Sie, dass eine Person ein Urinal nicht neben einem bereits besetzten Urinal belegen kann.

Aufgabe

Ihr Programm nimmt eine Zahl stdin, Befehlszeilenargumente oder ein Funktionsargument durch. Ihr Programm druckt dann die Anzahl der Möglichkeiten aus oder gibt sie zurück, die Schachmatt mit der eingegebenen Anzahl von Urinalen auftreten können.

Beispiele

0 -> 1(Die Null Fall zählt als Schachmatt)
1 -> 1( X)
2 -> 2( X-oder -X)
3 -> 2( X-Xoder -X-)
4 -> 3( X-X-, -X-Xoder X--X)
5 -> 4( X-X-X, X--X-, -X-X-, oder -X--X)
6 -> 5( X-X-X-, X--X-X, X-X--X, -X--X-oder -X-X-X)
7 -> 7( X-X-X-X, X--X-X-, -X-X--X, -X--X-X, X-X--X-, X--X--Xoder -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-)
...

Wertung

Das kleinste Programm in Bytes gewinnt.

code-golf sequence counting AMACB
quelle
3
Verwandte .
Betseg
3
Related
mbomb007
12
Der Fall n = 0 sollte 1 sein. Es gibt genau ein Setup, das Schachmatt ist, und das ist ''. Dies ist das gleiche wie bei Fakultäten und Permutationen, 0! = 1, weil es genau 1 Möglichkeit gibt, 0 Elemente anzuordnen.
Orlp
12
oeis.org/A228361
DJMcMayhem
19
Keine Toilette ist in der Tat eine Schachmatt-Situation. : D
Titus

Antworten:

20

Oase , 5 Bytes

Code

cd+2V

Erweiterte Version

cd+211

Erläuterung

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

Probieren Sie es online!

Adnan
quelle
7
Dies ist eine seltsame Antwort, die Sprache wurde vor ungefähr einem Monat ohne ordnungsgemäße Dokumentation im
2
@tuskiomi Es gibt ein Dokument, ininfo.txt
TuxCrafting
6
@TùxCräftîñg sicher, wenn du technisch sein willst. Ich könnte ein Pferd zeichnen und es Dokumentation für mein Programmierprojekt nennen. das macht es nicht nützlich oder entscheidend.
1
@ Tuskiomi info.txtist nützlich, es enthält eine Dokumentation für alle Oasis-Befehle
TuxCrafting
8
@ Tuskiomi Das ist das Ergebnis von Aufschub und Faulheit. Ich werde versuchen, eine kurze Dokumentation darüber hinzuzufügen, wie die eigentliche Sprache heute funktioniert.
Adnan
12

Java 7, 65-42 Bytes

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

Die Sequenz fügt nur vorherige Elemente hinzu, um neue zu erhalten. Hutspitze zu Orlp und Rod für diese kürzere Methode;)

Alt:

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

Nach dem fünften Element steigt die Lücke in der Folge um das Element fünf vor.

Geobits
quelle
Wenn u = 3, dann gibt Ihre Funktion 1 zurück, aber die Beispiele zeigen, dass es 2 sein sollte.
Poke
Hoppla! Ich habe meine fFunktion aus dem anderen Snippet verwendet, anstatt sie zu wiederholen. Dumm mich zu reparieren ...
Geobits
1
Kann das nicht der letzte Teil ( u>0?u:1;) werden 1;?
Conor O'Brien
2
@Jordan Wenn es keine Urinale gibt, dann ist "jedes Urinal bereits belegt" in der einen Konfiguration möglich. Ich glaube, der in der Frage gezeigte Testfall ist falsch.
Geobits
1
Sie können ersetzen, u>0?u:1;)indem 1;Sie den ersten Vergleich auf ändern. Bei u>1u = 2 ist die Ausgabe g (0) + g (-1). Dies ist 2
Rod
9

Python 2, 42 40 39 35 Bytes

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

Generieren der tatsächlichen Mengen:

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
quelle
8

Rubin, 58 34 Bytes

Stark inspiriert von Geobits 'ursprünglicher Java-Antwort.

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

Siehe es auf repl.it: https://repl.it/Dedh/1

Erster Versuch

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

Siehe es auf repl.it: https://repl.it/Dedh

Jordan
quelle
6

Python, 33 Bytes

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

Verwendet die verschobenen Basisfälle f(-1) = f(0) = f(1) = 1. Wenn Truefür 1 verwendet werden könnte, bräuchten wir keine 3 Bytes für die +().

xnor
quelle
6

J, 31 27 23 Bytes

Dank Meilen 4 Bytes gespart!

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

Eine Erklärung folgt in Kürze.

Alte Lösung

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

Dies ist eine Agenda. Die LHS ist ein Gerundium aus zwei Verben: >.1&^und -&3+&$:-&2. Der erste wird verwendet, wenn die Bedingung ( 2&<) fehlschlägt. Das heißt, der Fork >.1&^wird über dem Argument aktiviert. Beobachten:

   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

Hier werden >.maximal zwei Werte angenommen. Somit ergibt es 1, 1 und 2 als anfängliche Terme.

Das zweite Verb im Gerundium ist eine Gabelung:

-&3 +&$: -&2

Die linken und rechten Zinken werden auf das Verb angewendet, wobei jeweils 3 und 2 subtrahiert werden. dann wird das mittlere Verb mit den gleichen linken und rechten Argumenten aufgerufen. $:ruft das Verb für jedes Argument auf und +addiert diese beiden. Es ist im Grunde gleichbedeutend mit($: arg - 3) + ($: arg - 2)

Testfälle

   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
quelle
4

MATL , 25 23 Bytes

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

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Zwei Windungen! Yay!

Auf diese Weise wird ein Array (z. B. A) erstellt, in dem jede mögliche Konfiguration eine Zeile ist. 1in diesem Array steht für eine besetzte Position. Zum Beispiel ist für die Eingabe 4das Array A

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

Der Code faltet dann Array A mit [1 1 1]. Dies ergibt ein Array B. Besetzte Positionen und Nachbarn von besetzten Positionen in A ergeben ein Ergebnis ungleich Null in Array B:

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

Die erste Bedingung für eine Konfiguration als Schachmatt ist, dass B in dieser Zeile keine Nullen enthält. Dies bedeutet, dass es in dieser Reihe von A keine leeren Positionen gab oder dass es einige gab, aber Nachbarn von besetzten Positionen.

Wir brauchen eine zweite Bedingung. Beispielsweise erfüllt die letzte Zeile die obige Bedingung, ist jedoch nicht Teil der Lösung, da die Konfiguration anfangs nicht gültig war. Eine gültige Konfiguration kann keine zwei benachbarten besetzten Positionen haben, dh keine zwei zusammenhängenden 1in A. Entsprechend können zwei zusammenhängende Werte in B nicht überschritten werden 1. Wir können dies also erkennen, indem wir B mit [1 1]dem resultierenden Array C zusammenfalten und überprüfen,

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

Kein Wert in dieser Zeile überschreitet 3. Das Endergebnis ist die Anzahl der Konfigurationen, die die beiden Bedingungen erfüllen.

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
quelle
4

PHP, 105 113 93 Bytes

+3 für n=1; +9 für $argv, -1-3 golfed
-20: habe gemerkt, dass ich nicht die kombinationen habe, sondern nur deren anzahl

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

renn mit -r

Schleife von 2 ** n-1 nach 0:

  • überprüft binäre n stellige Darstellung für 11, 000,00 am Anfang oder am Ende, oder ein einzigen0
  • Wenn keine Übereinstimmung vorliegt, erhöhen Sie das Ergebnis

Druckergebnis

gleiche Größe, etwas einfacher Regex

for($i=1<<$n=$argv[1];--$i;)$r+=!preg_match("#11|^00|00[,0]#",sprintf("%0{$n}b,",$i));echo$r;
  • Schleife von 2 ** n-1 nach 1 (anstelle von 0)
  • Überprüfen Sie die Binärdarstellung auf 11, 00am Anfang oder am Ende, oder000
  • druckt nichts für n = 0

PHP, 82 Bytes

Arnauld antwortete portiert und golfen:

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

druckt nichts für n = 0

Titus
quelle
3 Bytes für das Neue hinzufügen n=0: ?:1vor dem Finale einfügen;
Titus
4

Jelly , 11 Bytes

,’fR_2߀So1

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

,’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
quelle
2
Wie funktioniert das? Verwendet es die rekursive Formel oder etwas anderes?
Conor O'Brien
@ ConorO'Brien Ja, es wird die rekursive Formel verwendet. Ich habe eine Erklärung hinzugefügt.
Dennis
4

JavaScript (ES6) / Rekursiv, 30 bis 27 Byte

Bearbeiten: 3 Bytes dank Shaun H gespeichert

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));
}
Erweitern Sie das Snippet

JavaScript (ES6) / Nicht rekursiv 90 77 Bytes

Bearbeiten: 13 Bytes dank Conor O'Brien und Titus gespeichert

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));
}
Erweitern Sie das Snippet

Arnauld
quelle
1
Ich denke, werden ((i|r|l)&(k-1))kann ((i|r|l)&k-1), oder sogar((i|r|l)&~-k)
Conor O'Brien
Ein Byte: i<<1-> i*2oderi+i
Titus
1
Sie können eine Variable für l und r, Speicher 6 Bytes verwenden !(i&(x=i>>1|i+i))&&((i|x)&(k-1))==k-1; und wenn Sie einfügen können ,k--irgendwo, können Sie ersetzen k-1mit kzu speichern Pars.
Titus
&(k-1)braucht sowieso keine Eltern; aber Sie können &~kstattdessen verwenden.
Titus
1
Ich lasse das hier:f=n=>n<3?n||1:f(n-2)+f(n-3)
Shaun H
3

Mathematica, 35 Bytes

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

Definiert eine Funktion a. Nimmt eine Ganzzahl als Eingabe und gibt eine Ganzzahl als Ausgabe zurück. Einfache rekursive Lösung.

LegionMammal978
quelle
3

AnyDice , 51 Bytes

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

Hier sollte es mehr AnyDice-Antworten geben.

Meine Lösung definiert eine rekursive Funktion, die berechnet a(n)=a(n-2)+a(n-3). Es kehrt zurück a(0)=a(1)=1und a(2)=2verwendet einige ganzzahlige Divisionsmagie.

Probieren Sie es online aus

Hinweis: Die Ausgabe kann seltsam aussehen, da sie normalerweise zur Ausgabe von Würfelwahrscheinlichkeiten verwendet wird. Schauen Sie sich einfach die Zahl links neben dem Balkendiagramm an.

DanTheMan
quelle
3

Perl, 35 34 Bytes

Beinhaltet +1 für -p

Geben Sie auf STDIN Eingang

checkmate.pl <<< 8

checkmate.pl:

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

Eine neu entwickelte Geheimformel. Ripple Update 3-Statusvariablen, ohne dass parallele Zuweisungen erforderlich sind.

Es ist ebenso kurz (aber viel langsamer und benötigt viel mehr Speicher), um das ursprüngliche Problem zu lösen:

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

aber das funktioniert nicht für 0

Tonne Hospel
quelle
2

JavaScript (ES6), 62 Byte

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

Dies ist das erste Mal, dass ich zwei Dummy-Variablennamen benötige. Eine rekursive Version wäre wahrscheinlich kürzer, aber ich mag es wirklich reduce...

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

Jelly , 19 Bytes

Die rekursive Lösung ist wahrscheinlich kürzer ...

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

Sehen Sie es bei TryItOnline
oder in der Serie für n = [0, 99], auch bei TryItOnline

Wie?

Gibt die n+3Nummer des th Padovans durch Zählen von Kombinationen zurück

Ḥ⁹_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
quelle
2

> <> , 25 + 2 = 27 Bytes

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

Muss der Eingang beim Programmstart auf dem Stack vorhanden sein, also +2 Byte für das -vFlag. Probieren Sie es online!

Die erste Zeile initialisiert den Stapel auf 1 1 2 n, wobei ndie eingegebene Nummer ist. Die zweite Zeile, die rückwärts läuft, überprüft, ob ngrößer als 1 ist. Wenn dies der nFall ist, wird sie dekrementiert, und das nächste Element in der Sequenz wird wie folgt generiert:

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

Die letzte Zeile gibt die Nummer am unteren Rand des Stapels aus, bei der es sich um das erforderliche Element in der Sequenz handelt.

Sok
quelle
2

CJam , 20 Bytes

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

Probieren Sie es online!

Erläuterung

Dies verwendet die Wiederholungsbeziehung, die auf der OEIS-Seite angezeigt wird .

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
quelle
2

05AB1E , 12 Bytes

XXXIGX@DŠ0@+

Erläuterung

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

Probieren Sie es online!

Emigna
quelle
1

FRACTRAN, 104 93 Bytes

Eingabe ist 11**n*29und Ausgabe ist 29**checkmate(n).

Dies ist hauptsächlich zum Spaß, zumal ich gerade von Python, JS und Java überfordert bin . Die gleiche Anzahl von Bytes wie bei PHP: D Golfvorschläge sind willkommen.

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

Ungolfing

               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
quelle
1

Eigentlich 25 Bytes

Dies scheint für eine einfache f(n) = f(n-2) + f(n-3)Wiederholungsbeziehung ein wenig lang zu sein . Golfvorschläge sind willkommen. Probieren Sie es online!

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

Ungolfing

         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
quelle
1

Eigentlich 18 Bytes

Dies ist eine Portierung von Dennis 'längerer Gelee-Antwort. Golfvorschläge sind willkommen. Probieren Sie es online!

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

Ungolfing

         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
quelle