El triángulo de Sierpinski es un conjunto de puntos en el plano que se construye comenzando con un solo triángulo y dividiendo repetidamente todos los triángulos en cuatro triángulos congruentes y eliminando el triángulo central. El triángulo de Sierpinski derecha tiene esquinas en (0,0)
, (0,1)
y (1,0)
, y se ve así:
Algunas definiciones equivalentes de este conjunto son las siguientes:
Puntos en la
n
iteración del proceso descrito anteriormente, para todosn
.Puntos
(x,y)
con0 <= x <= 1
y0 <= y <= 1
tal que para todos los enteros positivosn
, eln
bit th en la expansión binaria de x e y no son ambos1
.Dejar
T = {(0,0),(1,0),(0,1)}
Sea
f
una función en conjuntos de puntos 2D definidos por lo siguiente:f(X) = {(0,0)} ∪ {(x+t)/2 | x∈X, t∈T}
Entonces el triángulo de Sierpinski derecho es el cierre topológico del punto menos fijo (por contención establecida) de
f
.Deja
S
ser el cuadrado{(x,y) | 0<=x<=1 and 0<=y<=1}
Let
g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}
(dondeT
es como se definió anteriormente)Entonces el triángulo rectángulo de Sierpinski es el mayor punto fijo de
g
.
Desafío
Escriba un programa o función que acepte 4 enteros, a,b,c,d
y dé un valor verdadero si (a/b,c/d)
pertenece al triángulo Sierpinski correcto, y de lo contrario da un valor falsey.
Puntuación
Este es un código de golf. El código más corto en bytes gana.
Casos de prueba
Los siguientes están en el triángulo rectángulo de Sierpinski:
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
Los siguientes no están en el triángulo rectángulo de Sierpinski:
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
fuente
-1 -3 1 1
una entrada válida?Respuestas:
Pitón 2, 68
Una buena manera de comprobar si la membresía de la junta es fea. Si se nos garantizara que las entradas no son negativas y están en el cuadrado de la unidad, tendríamos 38:
La idea es que verifiquemos si un punto se encuentra dentro de la junta comprobando si su fracción binaria se expande bit a bit Y a 0. Para obtener el primer
k
carácter de la expansión, desplazamos losk
bits del numerador a la izquierda antes de dividirlos por el denominador . Necesitamos hacer lok
suficientemente grande como para atrapar una repetición. Observamos que la expansión binarian/d
tiene un período como máximod
, por lo que las expansiones conjuntas tienen un período como máximod*D
, por lo que esk=d*D
suficiente.El resto es verificar si la fracción está en el cuadro y aislar contra entradas dadas como
-1/-3
.fuente