O triângulo de Sierpinski é um conjunto de pontos no plano que é construído começando com um único triângulo e dividindo repetidamente todos os triângulos em quatro triângulos congruentes e removendo o triângulo central. O triângulo direito de Sierpinski tem cantos em (0,0)
, (0,1)
e (1,0)
, e fica assim:
Algumas definições equivalentes deste conjunto são as seguintes:
Pontos na
n
iteração do processo descrito acima, para todosn
.Pontos
(x,y)
com0 <= x <= 1
e0 <= y <= 1
tais que, para todos os números inteiros positivosn
, on
th bit na expansão binária de x e y não são ambos1
.Deixei
T = {(0,0),(1,0),(0,1)}
Seja
f
uma função em conjuntos de pontos 2D definidos pelo seguinte:f(X) = {(0,0)} ∪ {(x+t)/2 | x∈X, t∈T}
Então, o triângulo de Sierpinski à direita é o fechamento topológico do ponto menos fixo (por contenção definida) de
f
.Seja
S
o quadrado{(x,y) | 0<=x<=1 and 0<=y<=1}
Let
g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}
(ondeT
é como definido acima)Então o triângulo direito de Sierpinski é o maior ponto fixo de
g
.
Desafio
Escreva um programa ou função que aceite 4 números inteiros a,b,c,d
e dê um valor verdadeiro se (a/b,c/d)
pertencer ao triângulo de Sierpinski à direita e, caso contrário, dê um valor de falsey.
Pontuação
Este é um código de golfe. O menor código em bytes vence.
Casos de teste
A seguir, estão no triângulo direito 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
O seguinte não está no triângulo direito 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
fonte
-1 -3 1 1
uma entrada válida?Respostas:
Python 2, 68
Uma boa maneira de verificar se a associação de vedação está feia. Se tivéssemos a garantia de que as entradas não são negativas e no quadrado da unidade, teríamos 38:
A idéia é que verifiquemos se um ponto está dentro da gaxeta, verificando se a sua fração binária se expande bit a bit-AND para 0. Para obter o primeiro
k
caractere da expansão, alteramos osk
bits do numerador deixados antes da divisão do número inteiro pelo denominador . Precisamos fazer ok
suficiente para capturar uma repetição. Observamos que a expansão binárian/d
tem um período no máximod
, portanto as expansões conjuntas têm um período no máximod*D
, o quek=d*D
é suficiente.O resto é verificar se a fração está na caixa e isolar as entradas fornecidas como
-1/-3
.fonte