Pascals Raute

20

Pascals Rhombus (das eigentlich ein Dreieck ist) erhält man durch Hinzufügen des folgenden Musters:

  *
 ***
  x

anstatt

* *
 x

Dies bedeutet, dass jede Zelle die Summe der drei Zellen in der Zeile direkt darüber und einer Zelle in der Zeile 2 darüber ist. Genau wie Pascals Dreieck enthält die nullte Zeile eine einzige 1, die das Dreieck erzeugt.

Hier sind die ersten paar Reihen von Pascals Rhombus

      1
    1 1 1
  1 2 4 2 1
1 3 8 9 8 3 1

Aufgabe

Wenn eine Zeilennummer (beginnend von oben) und eine Spaltennummer (beginnend von dem ersten Element ungleich Null in dieser Zeile) gegeben sind, wird der Wert in dieser bestimmten Zelle ausgegeben. Beide Eingänge können entweder 1 oder 0 indiziert sein (Sie können mischen und anpassen, wenn Sie möchten).

Dies ist daher sollten Sie versuchen, die Dateigröße Ihres Quellcodes so klein wie möglich zu halten.

OEIS A059317

Weizen-Assistent
quelle
4
Wie bei Pascals Dreieck ergibt die Parität der Raute schöne und fraktale Muster .
Martin Ender
Sie sollten versuchen, die Dateigröße Ihres Quellcodes so klein wie möglich zu halten. Was passiert, wenn ich meinen Code als Befehlszeilenargument einfüge? : P
Erik der Outgolfer
Ging für Abkürzungen googeln und anscheinend sagt arxiv.org/abs/1504.04404, dass das direkte Berechnen des Ergebnisses für Codegolf unbrauchbar ist.
JollyJoker

Antworten:

12

Haskell , 59-55 Bytes

Pascals Raute? Eher wie Haskells Raute! habe ich recht?

Dank Ørjan Johansen wurden 4 Bytes eingespart

Ich dachte, ich würde mein eigenes Problem angehen und mein Haskell üben. Hoffentlich wird dies mehr Menschen dazu inspirieren, darauf zu antworten.

1!1=1
n!k=sum[(n-2)!(k-2)+sum(map((n-1)!)[k-2..k])|n>1]

Probieren Sie es online!

Erläuterung

Dies ist mit dem neuesten Golf etwas veraltet

Anstatt zu rechnen

  *
 ***
  x

Wir rechnen

*
***
  x

Dies lässt unser gesamtes Dreieck schräg werden

1
1 1 1
1 2 4 2 1
1 3 8 9 8 3 1

Dadurch werden alle unsere Zeilen in einer Reihe angeordnet, sodass das n-te Element einer Spalte einfacher indiziert werden kann. Wir definieren dann unsere Basisfälle.

Die nullte Zeile besteht also nur aus Nullen

0!_=0

Es gibt eine Single 1bei Position, 1,1also definieren wir das

1!1=1

Und wir definieren den Rest der ersten Zeile ebenfalls als Nullen

1!_=0

Dann definieren wir den allgemeinen Fall rekursiv mit dem oben beschriebenen Muster:

n!k=(n-2)!(k-2)+(sum$map((n-1)!)[k-2..k])
Weizen-Assistent
quelle
Schlagen Sie mich dazu! Das ist auch viel sauberer als meins.
Julian Wolf
@JulianWolf Tut mir leid, als ich das gepostet habe, sah es so aus, als würde niemand anderes als Jorg das Problem lösen. Ich würde immer noch gerne Ihre Lösung sehen.
Weizen-Assistent
1
Mit können Sie vier Bytes speichern n!k=sum[(n-2)!(k-2)+sum(map((n-1)!)[k-2..k])|n>1].
Ørjan Johansen
10

Pascal , 122 Bytes

Nun, es ist Pascals Raute.

37 Bytes gespart dank @manatwork

function f(n,k:integer):integer;begin f:=1-Ord((k<0)or(k>n*2));if n>0then f:=f(n-1,k-2)+f(n-1,k-1)+f(n-1,k)+f(n-2,k-2)end;

Probieren Sie es online!

Uriel
quelle
Klammern um den gesamten ifZustand sind sinnlos. (Am 1. ifsparen Sie 2 Zeichen, am 2. if1 Zeichen, indem Sie zwischen dem thenSchlüsselwort und der vorhergehenden Ziffer kein Leerzeichen lassen .) Oh, und die Variable r ist völlig unnötig.
Manatwork
Seltsames Tier, das Pascal auf Ideone. Noch nie zuvor in einer Pascal-Variante durch Anführungszeichen getrennte Zeichenfolgen gesehen. Eine weitere Sache , die Sie entfernen können: die ;vor dem function‚s end.
Manatwork
@manatwork ja, jetzt, als Sie es erwähnt haben, haben sich alle anderen Online-Redakteure darüber beschwert
Uriel
@manatwork Ich bin nicht sicher, ob ich verstanden habe. würde das nicht einfach den code verlängern mit dem >= <=? Ich muss immer noch denif n=0
Uriel
Sorry @Uriel, ich habe diese Version nicht mehr. Derzeit bin ich beifunction f(n,k:integer):integer;begin f:=1-Ord((k<0)or(k>n*2));if n>0then f:=f(n-1,k-2)+f(n-1,k-1)+f(n-1,k)+f(n-2,k-2)end;
Manatwork
7

PHP , 86 Bytes

rekursiv nur die Funktionszeile und -spalte 0-indiziert

function f($r,$c){return$r|$c?$r<0?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

Probieren Sie es online!

PHP , 114 Bytes

rekursiver Weg volles Programm Zeile und Spalte 0-indiziert

<?=f(...$_GET);function f($r,$c){return$r|$c?$r<0|$c<0|$c>2*$r?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

Probieren Sie es online!

PHP , 129 Bytes

Zeile und Spalte 0-indiziert

for(;$r<=$argv[1];$l=$t[+$r++])for($c=~0;$c++<$r*2;)$t[+$r][$c]=$r|$c?$t[$r-2][$c-2]+$l[$c]+$l[$c-1]+$l[$c-2]:1;echo$l[$argv[2]];

Probieren Sie es online!

Jörg Hülsermann
quelle
und +1 für die tatsächliche Verbesserung :)
Uriel
4

Jelly , 22 20 19 Bytes

3ḶṚp@Ḣḣ4
Ḟ_ЀÇ߀ȯ¬S

Nimmt ein 0-basiertes Indexpaar als Befehlszeilenargument.

Probieren Sie es online!

Dennis
quelle
3

MATL , 22 20 19 Bytes

Ti:"2Y6Y+FT_Y)]!i_)

Beide Eingänge sind 0-basiert.

Probieren Sie es online!

Erläuterung

Lassen Sie rund cbezeichnen Sie die zwei Eingaben, die 0-basierte Zeile bzw. Spalte angeben.

Jede neue Zeile in Pascals Rhombus kann aus der Matrix erstellt werden, die die vorherigen beiden Zeilen enthält, indem Sie mit dem Kernel zusammenarbeiten [1 1 1; 0 1 0]und die letzten beiden Zeilen des Ergebnisses vertauschen. Dies geschieht rmal ausgehend von der Matrix 1.

Es stellt sich als kürzer heraus, den Kernel zu verwenden [0 1 0; 1 1 1; 0 1 0], der ein vordefiniertes Literal ist. Dies erzeugt eine zusätzliche Zeile, die verworfen wird.

Betrachten Sie zum Beispiel r = 3, so gibt es 3Iterationen.

  1. Ab

    1
    

    Faltung mit [0 1 0; 1 1 1; 0 1 0]gibt

    0 1 0
    1 1 1
    0 1 0
    

    Halten Sie die letzten beiden Zeilen (in diesem Fall die gesamte Matrix) und tauschen Sie sie aus

    0 1 0
    1 1 1
    
  2. Faltung der obigen mit [0 1 0; 1 1 1; 0 1 0]gibt

    0 0 1 0 0
    0 1 1 1 0
    1 2 4 2 1
    0 1 1 1 0
    

    Die Matrix aus den beiden zuletzt getauschten Zeilen lautet

    0 1 1 1 0
    1 2 4 2 1
    

    Diese enthält die neue Zeile unten und die vorherige Zeile mit Nullen.

  3. Nochmaliges Wickeln ergibt

    0 0 1 1 1 0 0
    0 1 2 3 2 1 0
    1 3 8 9 8 3 1
    0 1 2 4 2 1 0
    

    Das Nehmen der letzten zwei getauschten Reihen gibt

    0 1 2 4 2 1 0
    1 3 8 9 8 3 1
    

Nach den rIterationen ist die Ausgabe in der letzten Zeile der endgültigen Matrix enthalten. Zum Beispiel wäre für c = 2(0-basiert) das Ergebnis 8. Anstatt die letzte Zeile und die gewünschte Spalte zu indizieren, kann ein Trick verwendet werden, der die Symmetrie jeder Zeile ausnutzt : Die endgültige Matrix wird transponiert

0 1
1 3
2 8
4 9
2 8
1 3
0 1

und sein -c-tes Element wird genommen. Dies verwendet die lineare Indizierung, das heißt, die Matrix wird durch einen einzelnen Index in der Reihenfolge des Spaltenhauptteils indiziert . Da die Indizierung modular ist , befindet sich der 0-Eintrag in der unteren rechten Ecke (Wert 1) und der -2-te Eintrag in zwei Schritten oberhalb (Wert 8).

T       % Push true
i       % Input row number
:"      % Do the following that many times
  2Y6   %   Push predefined literal [0 1 0; 1 1 1; 0 1 0]
  Y+    %   2D convolution, increasing size
  FT_   %   Push [0 -1]
  Y)    %   Matrix with rows 0 (last) and -1 (second-last), in that order
]       % End
!       % Transpose
i       % Input: colun number
_       % Negate
)       % Entry with that index. Implicitly display
Luis Mendo
quelle
2

Haskell , 74 Bytes

0#0=1
n#m|m<=2*n&&m>=0=sum[(n-a)#(m-b)|(a,b)<-zip[2,1,1,1]$2:[0..2]]
n#m=0

Probieren Sie es online!

Rufe mit auf n # m, wo nist die Zeile und mist die Spalte.

Julian Wolf
quelle
m<=2*n&&m>=0kann gerecht sein n>0.
Ørjan Johansen
2

Mathematica, 56 Bytes

If[#<1,Boole[##==0],Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}]]&

Reine Funktion, die zwei Ganzzahlargumente (erste Zeile, zweite Spalte) und eine Ganzzahl zurückgibt. Funktioniert auch für negative Ganzzahlargumente und gibt zurück 0. Eine recht einfache rekursive Struktur: If[#<1,Boole[##==0],...]Definiert das Basisfallverhalten für die 0. Zeile (und höher) und Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}]implementiert die rekursive Definition.

Greg Martin
quelle
1

JavaScript (ES6), 68 Byte

f=(y,x)=>x<0|x>y+y?0:x>0&x<y+y?f(--y,x)+f(y,--x)+f(y,--x)+f(--y,x):1
Neil
quelle
1

Mathematica, 53 Bytes

D[1/(1-x(1+y+y^2(1+x))),{x,#},{y,#2}]/#!/#2!/.x|y->0&

Generierungsfunktion verwenden.

Alephalpha
quelle
0

Python 3 , 82 84 Bytes

Dies ist eine rekursive Implementierung mit 1-indizierten Zeilen und Spalten. (Benötigt technisch einef= vorne jemanden, der mich wissen lässt, ob ich ihn auf 84 Bytes ändern soll. Noch neu und nicht 100% regelsicher.)

Dabei wird die rekursive Formel verwendet, die auf der OEIS-Seite zu finden ist , wobei jedoch die kdes nach links verschoben ist, um eine ordnungsgemäße Ausrichtung zu gewährleisten. Zufällig sum(f(n-1,k-i)for i in(0,1,2))ist die gleiche Größe wie f(n-1,k)+f(n-1,k-1)+f(n-1,k-2). Die ganze Funktion ist der Python- and orTrick, bei dem die erste Bedingung prüft, ob sich k innerhalb des Dreiecks und nicht an der Grenze befindet. In diesem Fall wird die rekursive Formel verwendet. Ist dies nicht der Fall, wird der Teil nach dem orzurückgegeben, der prüft, ob kin (1, 2*n-1), dh an der Grenze, Trueund zurückgegeben wird False. k+1in(2,2*n)ist ein Byte kürzer als k in(1,2*n-1). Wenn Sie das in Klammern setzen und ein voranstellen, wird es in eine +Ganzzahl konvertiert, was erforderlich ist.

f=lambda n,k:2*n-1>k>1and sum(f(n-1,k-i)for i in(0,1,2))+f(n-2,k-2)or+(k+1in(2,2*n))

Probieren Sie es online!

C McAvoy
quelle
Rekursive Funktionen benötigen die f=.
Weizen-Assistent
Während ich persönlich nicht damit einverstanden bin, was diesen etwas vergrabenen Metakonsens betrifft, können Sie eine Ausgabe vornehmen, Trueanstatt 1dass sie sich wie 1Python verhält . Dadurch können Sie die +(...)am Ende entfernen . Ich verstehe, wenn Sie dies nicht tun möchten, weil es die Ausgabe ein wenig seltsam aussehen lässt, ist es eine Option.
Weizen-Assistent
@ WheatWizard Wow, das ist sehr interessant. Danke für den Tipp.
C McAvoy
0

Java (OpenJDK 8) , 87 Byte

int f(int r,int c){return c<0|2*r<c?0:0<c&c<2*r?f(--r,c)+f(r,--c)+f(r,--c)+f(--r,c):1;}

Probieren Sie es online!

Zuerst war ich mit meiner 160-Byte-Iterationsmethode zufrieden ... Hmmm ... lass es uns einfach vergessen, OK?

Olivier Grégoire
quelle
0

Python 3 , 75 Bytes

Dies ist ein rekursives Lambda, das Spalte und Zeile als 0-indizierte Ganzzahlen verwendet.

p=lambda r,c:(r<0 or((c==0)|p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

Hier ist eine (etwas) besser lesbare Version mit Druckfunktion:

p = lambda r,c:(r<0 or ((c==0) | p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

def pp(r):
    ml = len(str(p(r,r)))+1
    for i in range(0, r):
            a=" "*ml*(r-i)
            for j in range(0,i*2 + 1):
                    a+=str(p(i,j))+(" "*(ml-len(str(p(i,j)))))
            print(a)
Eric Canam
quelle