Das Sierpinski-Dreieck ist eine Reihe von Punkten in der Ebene, die konstruiert werden, indem mit einem einzelnen Dreieck begonnen wird und alle Dreiecke wiederholt in vier kongruente Dreiecke aufgeteilt und das mittlere Dreieck entfernt werden. Das rechte Sierpinski Dreieck hat Ecken an (0,0), (0,1)und (1,0), und sieht wie folgt aus :

Einige äquivalente Definitionen dieses Satzes lauten wie folgt:

• Punkte in der nIteration des oben beschriebenen Prozesses für alle n.

• Punkte (x,y)mit 0 <= x <= 1und 0 <= y <= 1so, dass für alle positiven ganzen Zahlen ndas nth-Bit in der binären Erweiterung von x und y nicht beide sind 1.

• Lassen T = {(0,0),(1,0),(0,1)}

  Sei feine Funktion für Sätze von 2D-Punkten, die durch Folgendes definiert sind:

  f(X) = {(0,0)} ∪ {(x+t)/2 | x∈X, t∈T}

  Dann ist das rechte Sierpinski-Dreieck der topologische Verschluss des am wenigsten festen Punktes (durch Mengeneinschluss) von f.

• Sei Sdas Quadrat{(x,y) | 0<=x<=1 and 0<=y<=1}

  Lassen Sie g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}(wo Tist wie oben definiert)

  Dann ist das rechte Sierpinski-Dreieck der größte Fixpunkt von g.

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die 4 Ganzzahlen akzeptiert a,b,c,dund einen wahrheitsgemäßen Wert angibt, wenn (a/b,c/d)er zum rechten Sierpinski-Dreieck gehört, und ansonsten einen falschen Wert.

Wertung

Dies ist ein Code Golf. Der kürzeste Code in Bytes gewinnt.

Testfälle

Folgendes befindet sich im rechten Sierpinski-Dreieck:

0 1 0 1
0 1 12345 123456
27 100 73 100
1 7 2 7
8 9 2 21
8 15 20 63
-1 -7 2 7

Folgendes befindet sich nicht im rechten Sierpinski-Dreieck:

1 1 1 1
-1 100 1 3
1 3 1 3
1 23 1 7
4 63 3 66
58 217 4351 7577
-1 -7 3 7

Python 2, 68

lambda n,d,N,D:1>=n/d>=0<=N/D<=1and(n<<abs(D*d))/d&(N<<abs(D*d))/D<1

Ein guter Weg, um nach einer Mitgliedschaft in der Dichtung zu suchen, die hässlich gemacht wurde. Wenn wir garantiert wären, dass die Eingaben nicht negativ sind und sich im Einheitsquadrat befinden, hätten wir 38:

lambda n,d,N,D:(n<<D*d)/d&(N<<D*d)/D<1

Die Idee ist, dass wir prüfen, ob ein Punkt innerhalb der Dichtung liegt, indem wir prüfen, ob sich ihr binärer Bruch bitweise UND auf 0 ausdehnt. Um das erste kZeichen der Erweiterung zu erhalten, verschieben wir die Zählerbits kvor der Ganzzahldivision durch den Nenner . Wir müssen kausreichend groß machen, um eine Wiederholung zu fangen. Wir stellen fest, dass die binäre Erweiterung n/dhöchstens eine Periode hat d, so dass die gemeinsamen Erweiterungen höchstens eine Periode haben d*D, was k=d*Dausreicht.

Der Rest besteht darin, zu prüfen, ob sich der Bruch in der Box befindet, und gegen Eingaben zu isolieren, die wie angegeben sind -1/-3.