Biorąc pod uwagę trzy wzajemnie styczne koła, zawsze możemy znaleźć dwa kolejne koła, które są styczne do wszystkich trzech z nich. Te dwa nazywane są kręgami Apolli . Zauważ, że jedno z kręgów apollińskich może faktycznie znajdować się wokół trzech początkowych kręgów.

Zaczynając od trzech stycznych kół, możemy utworzyć fraktal zwany uszczelką apollińską w następujący sposób:

1. Nazwij pierwsze 3 kręgi kręgami nadrzędnymi
2. Znajdź dwa koła apollońskie kręgów macierzystych
3. Dla każdego koła apollińskiego:
   4. Dla każdej pary trzech par kręgów nadrzędnych:
      5. Nazwij krąg Apolliński i dwa koła nadrzędne nowym zestawem kół nadrzędnych i zacznij od kroku 2.

Np. Zaczynając od kół o równej wielkości, otrzymujemy:

^{Obraz znaleziony na Wikipedii}

Potrzebujemy jeszcze jednej notacji. Jeśli mamy okrąg o promieniu r ze środkiem (x, y) , możemy zdefiniować jego krzywiznę jako k = ± 1 / r . Zwykle k będzie dodatnie, ale możemy użyć ujemnego k, aby oznaczyć okrąg, który otacza wszystkie pozostałe koła w uszczelce (tj. Wszystkie styczne dotykają tego okręgu od wewnątrz). Następnie możemy określić okrąg z trojaczką liczb: (k, x * k, y * k) .

Na potrzeby tego pytania przyjmiemy dodatnią liczbę całkowitą k oraz wymierną x i y .

Dalsze przykłady takich kręgów można znaleźć w artykule w Wikipedii .

W tym artykule jest też kilka interesujących rzeczy na temat uszczelek integralnych (między innymi zabawne rzeczy z kołami).

Wyzwanie

Otrzymasz 4 specyfikacje koła, z których każda będzie wyglądać (14, 28/35, -112/105). Możesz użyć dowolnego formatu listy i operatora podziału, który jest wygodny, dzięki czemu możesz po prostu evalwprowadzić dane, jeśli chcesz. Możesz założyć, że 4 koła są rzeczywiście styczne do siebie i że pierwszy z nich ma krzywiznę ujemną. Oznacza to, że masz już otaczający apolloński krąg pozostałych trzech. Lista prawidłowych przykładowych danych wejściowych znajduje się w dolnej części wyzwania.

Napisz program lub funkcję, która przy tych wejściach rysuje uszczelkę apollińską.

Możesz przyjmować dane wejściowe za pomocą argumentu funkcji, ARGV lub STDIN i renderować fraktal na ekranie lub zapisywać go w pliku obrazu w wybranym formacie.

Jeśli powstały obraz jest rasteryzowany, musi mieć co najmniej 400 pikseli z każdej strony, z mniej niż 20% wypełnienia wokół największego koła. Możesz przestać się powtarzać, gdy dotrzesz do okręgów, których promień jest mniejszy niż 400. największego okręgu wejściowego, lub okręgów mniejszych niż piksel, w zależności od tego, co nastąpi wcześniej.

Musisz rysować tylko kontury kół, a nie pełne dyski, ale kolory tła i linii są twoim wyborem. Kontury nie mogą być szersze niż 200th średnicy zewnętrznych kół.

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Przykładowe dane wejściowe

Oto wszystkie integralne uszczelki z artykułu z Wikipedii przekonwertowane na określony format wejściowy:

[[-1, 0, 0], [2, 1, 0], [2, -1, 0], [3, 0, 2]]
[[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]
[[-3, 0, 0], [4, 1/3, 0], [12, -3, 0], [13, -8/3, 2]]
[[-3, 0, 0], [5, 2/3, 0], [8, -4/3, -1], [8, -4/3, 1]]
[[-4, 0, 0], [5, 1/4, 0], [20, -4, 0], [21, -15/4, 2]]
[[-4, 0, 0], [8, 1, 0], [9, -3/4, -1], [9, -3/4, 1]]
[[-5, 0, 0], [6, 1/5, 0], [30, -5, 0], [31, -24/5, 2]]
[[-5, 0, 0], [7, 2/5, 0], [18, -12/5, -1], [18, -12/5, 1]]
[[-6, 0, 0], [7, 1/6, 0], [42, -6, 0], [43, -35/6, 2]]
[[-6, 0, 0], [10, 2/3, 0], [15, -3/2, 0], [19, -5/6, 2]]
[[-6, 0, 0], [11, 5/6, 0], [14, -16/15, -4/5], [15, -9/10, 6/5]]
[[-7, 0, 0], [8, 1/7, 0], [56, -7, 0], [57, -48/7, 2]]
[[-7, 0, 0], [9, 2/7, 0], [32, -24/7, -1], [32, -24/7, 1]]
[[-7, 0, 0], [12, 5/7, 0], [17, -48/35, -2/5], [20, -33/35, 8/5]]
[[-8, 0, 0], [9, 1/8, 0], [72, -8, 0], [73, -63/8, 2]]
[[-8, 0, 0], [12, 1/2, 0], [25, -15/8, -1], [25, -15/8, 1]]
[[-8, 0, 0], [13, 5/8, 0], [21, -63/40, -2/5], [24, -6/5, 8/5]]
[[-9, 0, 0], [10, 1/9, 0], [90, -9, 0], [91, -80/9, 2]]
[[-9, 0, 0], [11, 2/9, 0], [50, -40/9, -1], [50, -40/9, 1]]
[[-9, 0, 0], [14, 5/9, 0], [26, -77/45, -4/5], [27, -8/5, 6/5]]
[[-9, 0, 0], [18, 1, 0], [19, -8/9, -2/3], [22, -5/9, 4/3]]
[[-10, 0, 0], [11, 1/10, 0], [110, -10, 0], [111, -99/10, 2]]
[[-10, 0, 0], [14, 2/5, 0], [35, -5/2, 0], [39, -21/10, 2]]
[[-10, 0, 0], [18, 4/5, 0], [23, -6/5, -1/2], [27, -4/5, 3/2]]
[[-11, 0, 0], [12, 1/11, 0], [132, -11, 0], [133, -120/11, 2]]
[[-11, 0, 0], [13, 2/11, 0], [72, -60/11, -1], [72, -60/11, 1]]
[[-11, 0, 0], [16, 5/11, 0], [36, -117/55, -4/5], [37, -112/55, 6/5]]
[[-11, 0, 0], [21, 10/11, 0], [24, -56/55, -3/5], [28, -36/55, 7/5]]
[[-12, 0, 0], [13, 1/12, 0], [156, -12, 0], [157, -143/12, 2]]
[[-12, 0, 0], [16, 1/3, 0], [49, -35/12, -1], [49, -35/12, 1]]
[[-12, 0, 0], [17, 5/12, 0], [41, -143/60, -2/5], [44, -32/15, 8/5]]
[[-12, 0, 0], [21, 3/4, 0], [28, -4/3, 0], [37, -7/12, 2]]
[[-12, 0, 0], [21, 3/4, 0], [29, -5/4, -2/3], [32, -1, 4/3]]
[[-12, 0, 0], [25, 13/12, 0], [25, -119/156, -10/13], [28, -20/39, 16/13]]
[[-13, 0, 0], [14, 1/13, 0], [182, -13, 0], [183, -168/13, 2]]
[[-13, 0, 0], [15, 2/13, 0], [98, -84/13, -1], [98, -84/13, 1]]
[[-13, 0, 0], [18, 5/13, 0], [47, -168/65, -2/5], [50, -153/65, 8/5]]
[[-13, 0, 0], [23, 10/13, 0], [30, -84/65, -1/5], [38, -44/65, 9/5]]
[[-14, 0, 0], [15, 1/14, 0], [210, -14, 0], [211, -195/14, 2]]
[[-14, 0, 0], [18, 2/7, 0], [63, -7/2, 0], [67, -45/14, 2]]
[[-14, 0, 0], [19, 5/14, 0], [54, -96/35, -4/5], [55, -187/70, 6/5]]
[[-14, 0, 0], [22, 4/7, 0], [39, -12/7, -1/2], [43, -10/7, 3/2]]
[[-14, 0, 0], [27, 13/14, 0], [31, -171/182, -10/13], [34, -66/91, 16/13]]
[[-15, 0, 0], [16, 1/15, 0], [240, -15, 0], [241, -224/15, 2]]
[[-15, 0, 0], [17, 2/15, 0], [128, -112/15, -1], [128, -112/15, 1]]
[[-15, 0, 0], [24, 3/5, 0], [40, -5/3, 0], [49, -16/15, 2]]
[[-15, 0, 0], [24, 3/5, 0], [41, -8/5, -2/3], [44, -7/5, 4/3]]
[[-15, 0, 0], [28, 13/15, 0], [33, -72/65, -6/13], [40, -25/39, 20/13]]
[[-15, 0, 0], [32, 17/15, 0], [32, -161/255, -16/17], [33, -48/85, 18/17]]

GolfScript (wektor 289 bajtów / raster 237 bajtów)

Przy 289 bajtach i wykonaniu w rozsądnym czasie:

'/'/n*','/']['*0,`1/*~1.$[]*(~-400*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%'<svg><g fill="none" stroke="red">'puts.{[[~@:b[D&*\abs]{@&*[b]+}2*]{'.0/'*'"#{
}"'n/*~}%'<circle r="
" cx="
" cy="
" />'n/\]zip puts}:|/[{.([.;]+}3*]{(:?zip{)\~++2*\-}%:c.|0=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do'</g></svg>'

To pobiera dane wejściowe na standardowe wejście i generuje plik SVG na standardowe wejście. Niestety demo online trwa trochę za długo, ale poprawiona wersja, która przerywa się wcześniej, może dać ci pomysł.

Biorąc pod uwagę wejście [[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]na wyjście (przeliczona do PNG za pomocą programu Inkscape) jest

Ma 237 bajtów i zajmuje dużo czasu (ekstrapoluję, że wyprodukowanie danych wyjściowych podobnych do powyższego zajęłoby nieco ponad tydzień, choć w czarno-białych bitach):

'/'/n*','/']['*0,`1/*~1.$[]*(~-400*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%.[{.([.;]+}3*]{(:?[zip{)\~++2*\-}%:c]@+\0c=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do;:C;'P1 ''801 '2*.~:B*,{:P;C{:?[0=2/.D&*-.*\D&*+.*]{2,{P{B/}2$*B%400-?0=*\)?=&*-.*}/+<},,1=},!}/

Wyjście jest w formacie NetPBM bez znaków nowej linii, więc prawdopodobnie nie jest ściśle zgodne ze specyfikacją, chociaż GIMP nadal go ładuje. Jeśli wymagana jest ścisła zgodność, wstawić npo ostatnim !.

Rasteryzacja polega na testowaniu każdego piksela na każdym kole, więc czas potrzebny jest raczej liniowy w liczbie pikseli razy liczba kół. Zmniejszając wszystko o współczynnik 10,

'/'/n*','/']['*0,`1/*~1.$[]*(~-40*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%.[{.([.;]+}3*]{(:?[zip{)\~++2*\-}%:c]@+\0c=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do;:C;'P1 ''81 '2*.~:B*,{:P;C{:?[0=2/.D&*-.*\D&*+.*]{2,{P{B/}2$*B%40-?0=*\)?=&*-.*}/+<},,1=},!}/

uruchomi się za 10 minut i wyprodukuje

(konwertowany do PNG za pomocą GIMP). Po 36 godzinach wyprodukował 401 x 401

JavaScript ( 418 410 bajtów)

Zaimplementowane jako funkcja:

function A(s){P='<svg><g fill=none stroke=red transform=translate(400,400)>';Q=[];s=eval(s);S=-400*s[0][0];function d(c){P+='<circle r='+Math.abs(p=S/c[0])+' cx='+p*c[1]+' cy='+p*c[2]+' />'}for(c=4;c--;d(s[0]),s.push(s.shift()))Q.push(s.slice());for(;s=Q.shift();d(c)){c=[];for(i=4;i--;)c[i]=2*(s[0][i]+s[1][i]+s[2][i])-s[3][i];for(i=6;c[0]<S&&i;)Q.push([s[i--%3],s[i--%3],c,s[i%3]])}document.body.innerHTML=P}

Demo online (uwaga: nie działa w przeglądarkach, które nie spełniają wymagań specyfikacji SVG w odniesieniu do niejawnego rozmiaru, więc oferuję nieco dłuższą wersję, która działa wokół tego błędu; przeglądarki mogą również renderować SVG mniej dokładnie niż np. Inkscape, chociaż Inkscape jest nieco bardziej rygorystyczny w zakresie cytowania atrybutów).

Zauważ, że 8 bajtów można zapisać za pomocą document.write, ale to poważnie niszczy jsFiddle.

Mathematica 289 znaków

Rozwiązując układ dwuliniowy zgodnie z http://arxiv.org/pdf/math/0101066v1.pdf Twierdzenie 2.2 (wysoce nieefektywne).

Miejsca niepotrzebne, wciąż gra w golfa:

w = {k, x, y};
d = IdentityMatrix;
j = Join;
p_~f~h_ := If[#[[-1, 1]] < 6! h,
    q = 2 d@4 - 1;
    m = #~j~{w};
    r = Complement[w /. NSolve[ And @@ j @@ 
                        MapThread[Equal, {[email protected], 4 d@3 {0, 1, 1}}, 2], w], a];
    If[r != {},
     a~AppendTo~# & @@ r;
     Function[x, x~j~{#}~f~h & /@ r]@#]] & /@ p~Subsets~{3}; 
Graphics[Circle @@@ ({{##2}, 1}/# & @@@ (f[a = #, -Tr@#]; a))] &

Animacja o zmniejszonym rozmiarze z wejściem {{-13, 0, 0}, {23, 10/13, 0}, {30, -84/65, -1/5}, {38, -44/65, 9/5}}

Klon (960 bajtów)

Użyłem Twierdzenia Kartezjusza, aby wygenerować Uszczelkę Apollińską, a następnie użyłem systemu kreślenia Maple, aby ją wykreślić. Jeśli mam czas, chcę pograć w golfa i zmienić go na Python (klon nie jest najlepszy do fraktali). Oto link do darmowego odtwarzacza Maple, jeśli chcesz uruchomić mój kod.

X,Y,Z,S,N:=abs,evalf,member,sqrt,numelems;
f:=proc(J)
    L:=map((x)->[x[1],(x[2]+x[3]*I)/x[1]+50*(1+I)/X(J[1][2])],J);
    R:=Vector([L]);
    T,r:=X(L[1][3]),L[1][4];
    A(L[1][5],L[2][6],L[3][7],L[1][8],L[2][9],L[3][10],R,T,r);
    A(L[1][11],L[2][12],L[4][13],L[1][14],L[2][15],L[4][16],R,T,r);
    A(L[1][17],L[3][18],L[4][19],L[1][20],L[3][21],L[4][22],R,T,r);
    A(L[2][23],L[3][24],L[4][25],L[2][26],L[3][27],L[4][28],R,T,r);
    plots[display](seq(plottools[circle]([Re(R[i][29]),Im(R[i][30])],X(1/R[i][31])),i=1..N(R))):
end proc:
A:=proc(a,b,c,i,j,k,R,E,F)
    K:=i+k+j+2*S(i*k+i*j+k*j);
    if K>400*E then
    return;
    end if;
    C:=(a*i+c*k+b*j+2*S(a*c*i*k+b*c*j*k+a*b*i*j))/K;
    C2:=(a*i+c*k+b*j-2*S(a*c*i*k+b*c*j*k+a*b*i*j))/K;
    if Y(X(C-F))<1/E and not Z([K,C],R) then
    R(N(R)+1):=[K,C];
    A(a,b,C,i,j,K,R,E,F);
    A(a,c,C,i,k,K,R,E,F);
    A(b,c,C,j,k,K,R,E,F);
    end if:    
    if Y(X(C2-F))<1/E and not Z([K,C2],R) then
    R(N(R)+1):=[K,C2];
    A(a,b,C2,i,j,K,R,E,F);
    A(a,c,C2,i,k,K,R,E,F);
    A(b,c,C2,j,k,K,R,E,F);
    end if: 
end proc:

Niektóre przykładowe uszczelki

f([[-1, 0, 0], [2, 1, 0], [2, -1, 0], [3, 0, 2]]);

f([[-9, 0, 0], [14, 5/9, 0], [26, -77/45, -4/5], [27, -8/5, 6/5]]);