Krzywa algebraiczna jest pewnym „podzbiorem 1D” „płaszczyzny 2D”, który można opisać jako zbiór zer {(x,y) in R^2 : f(x,y)=0 }wielomianu f. Uważamy tutaj płaszczyznę 2D za rzeczywistą, R^2dzięki czemu możemy łatwo wyobrazić sobie, jak mogłaby wyglądać taka krzywa, w zasadzie rzecz, którą można narysować ołówkiem.

Przykłady:

• 0 = x^2 + y^2 -1 okrąg o promieniu 1
• 0 = x^2 + 2y^2 -1 elipsa
• 0 = xyprzekroju kształt w zasadzie Związek osi x i na osi y
• 0 = y^2 - x parabola
• 0 = y^2 - (x^3 - x + 1)eliptyczna krzywa
• 0 = x^3 + y^3 - 3xy folium Kartezjusza
• 0 = x^4 - (x^2 - y^2) lemniscate
• 0 = (x^2 + y^2)^2 - (x^3 - 3xy^2) trifolium
• 0 = (x^2 + y^2 - 1)^3 + 27x^2y^2 astroid

Zadanie

Biorąc pod uwagę wielomian f(jak zdefiniowano poniżej) i zakresy x / y, wysyłaj czarno-biały obraz o wielkości co najmniej 100 x 100 pikseli, który pokazuje krzywą jako czarną linię na białym tle.

Detale

Kolor : możesz użyć dowolnych dwóch innych kolorów, po prostu łatwo je rozróżnić.

Fabuła : Zamiast obrazu pikselowego możesz również wyprowadzić ten obraz jako ascii-art, gdzie „piksele” w tle powinny być spacją / podkreśleniem lub innym znakiem, który „wygląda na pusty”, a linia może być utworzona z postaci, która wygląda na „ pełny ”jak Mlub Xlub #.

Nie musisz się martwić aliasingiem.

Musisz tylko wykreślić linie, w których znak wielomianu zmienia się z jednej strony linii na drugą (co oznacza, że ​​możesz np. Użyć algorytmu marszowego kwadratu), nie musisz poprawnie wykreślić „przypadków patologicznych, takich jak 0 = x^2znak nie zmieniaj się, przechodząc z jednej strony linii na drugą. Ale linia powinna być ciągła i oddzielać regiony różnych znaków f(x,y).

Wielomian : Wielomian podano jako (m+1) x (n+1)macierz / listę list (rzeczywistych) współczynników, w poniższym przykładzie warunki współczynników podano w ich pozycji:

[   1 * 1,   1 * x,   1 * x^2,   1 * x^3,  ... , 1 * x^n ]
[   y * 1,   y * x,   y * x^2,   y * x^4,  ... , y * x^n ]
[   ...  ,   ...   ,   ...   ,    ...   ,  ... ,   ...   ]
[ y^m * 1, y^m * x, y^m * x^2, y^m * x^3 , ..., y^m * x^n]

Jeśli wolisz, możesz założyć, że macierz jest kwadratowa (co zawsze można zrobić z niezbędnym uzupełnieniem zerowym), a jeśli chcesz, możesz również założyć, że rozmiar matrycy jest podany jako dodatkowe dane wejściowe.

Poniżej przykłady z góry są przedstawione jako macierz zdefiniowana w następujący sposób:

Circle:       Ellipse:      Parabola:  Cross:    Elliptic Curve: e.t.c
[-1, 0, 1]    [-1, 0, 1]    [ 0,-1]    [ 0, 0]   [-1, 1, 0,-1]
[ 0, 0, 0]    [ 0, 0, 0]    [ 0, 0]    [ 0, 1]   [ 0, 0, 0, 0]
[ 1, 0, 0]    [ 2, 0, 0]    [ 1, 0]              [ 1, 0, 0, 0]

Przypadki testowe z zakresem x / y:

(W niezbyt czytelnym, ale lepszym formacie umożliwiającym kopiowanie i wklejanie, dostępnym tutaj na pastebin .)

Circle:     
[-1, 0, 1]   [-2,2]   [-2,2]
[ 0, 0, 0]
[ 1, 0, 0]

Ellipse:
[-1, 0, 1]   [-2,2]   [-1,1]
[ 0, 0, 0]
[ 2, 0, 0]

Cross:
[ 0, 0]      [-1,2]   [-2,1]
[ 0, 1]

Parabola:
[ 0,-1]      [-1,3]   [-2,2]
[ 0, 0]
[ 1, 0]

Elliptic Curve:
[-1, 1, 0,-1]    [-2,2]   [-3,3]
[ 0, 0, 0, 0]  
[ 1, 0, 0, 0]  

Folium of Descartes:
[  0,  0,  0,  1]    [-3,3]   [-3,3]
[  0, -3,  0,  0]
[  0,  0,  0,  0]
[  1,  0,  0,  0]

Lemniscate:
[  0,  0, -1,  0,  1]    [-2,2]   [-1,1]
[  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0]

Trifolium:
[ 0, 0, 0,-1, 1]    [-1,1]   [-1,1]
[ 0, 0, 0, 0, 0]
[ 0, 3, 2, 0, 0]
[ 0, 0, 0, 0, 0]
[ 1, 0, 0, 0, 0]

Astroid:
[ -1,  0,  3,  0, -3,  0,  1]    [-1,1]   [-1,1]
[  0,  0,  0,  0,  0,  0,  0]
[  3,  0, 21,  0,  3,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[ -3,  0,  3,  0,  0,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0,  0,  0]

Inspiracja do niektórych krzywych pochodzi z tego pliku pdf.

Haskell, 283 275 bajtów

Funkcję gnależy wywołać z macierzą i dwoma zakresami jako argumentami. Matryca to tylko lista list, a zakresy to lista dwóch elementów.

import Data.List
t=transpose
u=tail
z=zipWith
l%x=sum$z(*)l$iterate(*x)1                                   --generate powers and multiply with coefficients
e m y x=[l%x|l<-m]%y                                         --evaluate the encoded polynomial
a#b=[a,a+(b-a)/102..b]                                       --create a range
g m[u,w][i,j]=unlines$v[map((0<).e m y)$u#w|y<-i#j]          --evaluate the function on the grid, get the sign
f g=u[u$u$map fst$scanl(\(r,l)c->(c==l,c))(1<0,1<0) l|l<-g]  --find +- or -+ transitions within lines
a&b|a&&b=' '|0<1='#'                                         --helper function for creating the string
v g=z(z(&))(f g)(t$f$t g)                                    --create the string

Oto wyniki dla bardziej interesujących przypadków: Zauważ, że musiałem zmniejszyć wynik ze 100 x 100 do około 40 x 40, tak aby pasował do konsoli (wystarczy zmienić kod na 102 na mniejszą liczbę). Zauważ też, że oś y jest skierowana w dół.

Matlab, 114 100 92 bajtów

Odpowiednie narzędzie do pracy? Używam interesującego sposobu, w jaki Matlab printfgeneruje wielomian jako ciąg. Można podać ten wielomian, na ezplotktórym drukuje się ukrytą krzywą w określonej domenie. Dla czytelności kod jest prezentowany z nowymi wierszami po; co nie jest potrzebne i nie jest wliczane do rozmiaru.

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])

Postęp w golfa jako fragment rozwijany.

Iteration 1, clean arguments, 114 bytes
---------------------------------------
function P(A,W,H)
h=size(A,1);
t=0:numel(A)-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])

Iteration 1.5, historical revisionism (thanks @flawr), 111 bytes
--------------------------------------------------------------
function P(A,W,H)
[h,w]=size(A);
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])


Iteration 2, playing dirty, 100 bytes
-------------------------------------
The code can be golfed further if I use that taking matrix sizes as inputs are
fair game, but it feels sad to ruin such neat input arguments. However,
this is code golf and I'll abuse anything I can and I end up at a nice 100 bytes:

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H]);

Iteration 2.5, fix your code (thanks @LuisMendo), 98 bytes
----------------------------------------------------------
function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';fix(t/h);rem(t,h)]),[W,H]);

Iteration 3, more power to printf, 92 bytes [current best]
----------------------------------------------------------
Use `%.0f` instead of `fix`/`floor`.

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])

Wyjście przypadków testowych (kliknij, aby zobaczyć pełny widok):

Python 2, 261 bajtów

E=enumerate
M,[a,c],[b,d]=input()
e=(c-a)/199.
I=200
J=-int((b-d)/e-1)
print'P2',I,J,255
i=I*J
while i:i-=1;x,y=c-i%I*e,b+i/I*e;u,v,w=map(sum,zip(*((z*p/x,z*q/y,z)for q,R in E(M)for p,t in E(R)for z in[t*x**p*y**q])));print int(255*min(1,(w*w/(u*u+v*v))**.5/e))

Format wejściowy: matrix,xbounds,ybounds(np [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2].). Format wyjściowy: zwykły PGM .

Szacuje się odległość od każdego środka piksela do krzywej za pomocą aproksymacji pierwszego rzędu d ( x , y ) = | p ( x , y ) | / | ∇ p ( x , y ) |, gdzie ∇ p jest gradientem wielomianu p . (Jest to odległość od ( x , y ) do przecięcia płaszczyzny stycznej w ( x , y , p ( x , y )) z płaszczyzną xy .) Następnie piksele, w których d (x , y ) ma mniej niż jeden piksel szerokości krzywej proporcjonalnie do d ( x , y ), co daje ładne linie antyaliasingu (nawet jeśli nie jest to wymagane).

Oto te same wykresy z funkcją odległości podzieloną przez 16, aby była widoczna.

Python 3.5 + MatPlotLib + Numpy, 352 bajty:

from matplotlib.pyplot import*;from numpy import*
def R(M,S,U,r=range):N=linspace;E='+'.join([str(y)+'*'+m for y,m in[q for i,g in zip(M,[[i+'*'+p for p in['1']+['x^%d'%p for p in r(1,len(M[0]))]]for i in['1']+['y^%d'%i for i in r(1,len(M))]])for q in zip(i,g)if q[0]]]);x,y=meshgrid(N(*S,200),N(*U,200));contour(x,y,eval(E.replace('^','**')),0);show()

Nazwana funkcja. Dość długo, ale hej, po prostu cieszę się, że udało mi się wykonać to zadanie. Pobiera 3 dane wejściowe, czyli m by nmacierz, the x-range i y-range, które powinny znajdować się w tablicach (na przykład [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]). Wysyła ukończony wykres w nowym graficznym, interaktywnym oknie. Będę grał w golfa więcej czasu, kiedy będę mógł, ale na razie jestem z tego zadowolony.

Końcowe wyniki dla przypadków testowych:

MATL , 67 61 bajtów

8Wt:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4=0YG

Ten kod działa w wersji 18.5.0 języka, który poprzedza wyzwanie. Wejście używa Opcjonalnie m, nparametry. Matryca ma średniki jako separatory wierszy. Dokładny format wejściowy (na przykładzie paraboli) to

[-1,3]
3  
[-2,2]
2
[0,-1; 0, 0; 1, 0]

Kod tworzy obraz o rozmiarze 255 × 255. To mogą być testowane za pomocą @Suever „s Mátl online kompilator, który, między innymi bardzo interesujących cech, zawiera wyjście graficznego. Zobacz na przykład

• Krzywa eliptyczna ;
• Folium Kartezjusza .

Ten kompilator jest wciąż w fazie eksperymentalnej. Proszę zgłaszać wszelkie problemy do @Suever na czacie MATL . Jeśli przycisk „Uruchom” nie działa, spróbuj odświeżyć stronę i kliknąć ponownie.

Jeśli wolisz wyjście ASCII , kod należy nieco zmodyfikować (zmiany dotyczą tylko pierwszych dwóch i czterech ostatnich znaków powyższego kodu):

101t:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4<42*c

W ten sposób powstaje siatka ASCII 100 × 100, która używa znaku *do reprezentowania krzywej. Możesz to również przetestować za pomocą @Dennis ' Wypróbuj online! Platforma:

• Krzywa eliptyczna ;
• Folium Kartezjusza .

Zauważ, że współczynnik kształtu wyjścia ASCII jest zmieniony, ponieważ znaki są nieco wyższe niż szerokie.

Wyjaśnienie

Kod najpierw oblicza wielomian dwóch zmiennych na siatce x - y . To często wykorzystuje transmisję , obliczając pośrednią macierz 4D, gdzie każdy wymiar reprezentuje odpowiednio x wartości, y wartości, x wykładników, y wykładników.

Na podstawie tej funkcji obliczana jest linia poziomu zerowego. Ponieważ w wyzwaniu określono, że należy wykryć tylko zmiany w znakach, kod stosuje splot 2D z blokiem 2 × 2 jedynek i oznacza piksel jako należący do linii, jeśli nie cztery wartości bloku mają ten sam znak.

8W      % Push 2^8, that is, 256. (The ASCII-output version pushes 101 instead)
t:q     % Duplicate. Push range [0 1 ... 255]
wq      % Swap. Subtract 1 to obtain 255
/       % Divide. Gives normalized range [0 1/255 2/255... 1]
t       % Duplicate
2:"     % For loop: do this twice
  w     %   Swap top two elements in the stack
  i     %   Input two-number array defining x range (resp. y in second iteration)
  d     %   Difference of the two entries
  *     %   Multiply by normalized range
  2M1)  %   Push the array again and get its first entry
  +     %   Add. This gives the range for x values (resp. y)
  i     %   Input m (n in second iteration)
  :q    %   Range [0 1 ...m-1] (resp. [0 1 ...n-1])
  !     %   Convert to column array
  ^     %   Power, element-wise with broadcast. This gives a matrix of size m×256
        %   (resp. n×256) of powers of x (resp. y) for the range of values computed
        %   previously
]       % End for loop
!       % Transpose. This transforms the n×256 matrix of powers of y into 256×n
2       % Push 2
&!      % Permute dimensions 1 and 3: transforms the 256×n matrix into a 4D array
        % of size 1×n×256×1
w       % Swap top two elements in the stack: bring 256×m matrix to top
[1IK2]  % Push vector [1 3 4 2]
&!      % Permute dimensions as indicated by the vector: transforms the m×256 matrix
        % into a 4D array of size m×1×1×256
*       % Multiply element-wise with broadcast: gives 4D array of size m×n×256×256
        % with mixed powers of x and y for at the grid of x, y values
*       % Implicitly input m×n matrix. Multiply element-wise with broadcast: gives
        % 4D array of size m×n×256×256
ss      % Sum along first two dimensions: gives 4D array of size 1×1×256×256
&e      % Squeeze singleton dimensions: gives matrix of size 256×256. This is the
        % two-variable polynomial evaluated at the x, y grid.
        % Now we need to find the zero level curve of this function. We do this by 
        % detecting when the sign of the function changes along any of the two axes
ZS      % Matrix of sign values (1, 0 or -1)
5Y6     % Predefined literal: matrix [1 1; 1 1]
2&Y+    % Compute 2D convolution, keeping only the valid (central) part
|4=     % True if absolute value of result is 4, which indicates no sign changes.
        % (The ASCII version computes a negated version of this, for better display)
0YG     % Display as image. (The ASCII-output version does the following instead:
        % multiply by 42 and convert to char. 42 is ASCII for '*', and character 0 
        % is shown as space. The 2D char array is then implicitly displayed)

Wszystkie przypadki testowe

Oto wszystkie dane wejściowe w odpowiednim formacie, na wypadek gdybyś chciał spróbować:

Circle:
[-2,2]
3
[-2,2]
3
[-1, 0, 1; 0, 0, 0; 1, 0, 0]

Ellipse:
[-2,2]
3
[-1,1]
3
[-1, 0, 1; 0, 0, 0; 2, 0, 0]

Cross:
[-1,2]
2
[-2,1]
2
[0, 0; 0, 1]

Parabola:
[-1,3]
3  
[-2,2]
2
[0,-1; 0, 0; 1, 0]

Elliptic Curve:
[-2,2]
3
[-3,3]
4
[-1, 1, 0,-1; 0, 0, 0, 0; 1, 0, 0, 0]

Folium of Descartes:
[-3,3]
4
[-3,3]
4
[0,  0,  0,  1; 0, -3,  0,  0; 0,  0,  0,  0; 1,  0,  0,  0]


Lemniscate:
[-2,2]
3
[-1,1]
5
[0,  0, -1,  0,  1; 0,  0,  0,  0,  0; 1,  0,  0,  0,  0]

Trifolium:
[-1,1]
5
[-1,1]
5
[0, 0, 0,-1, 1; 0, 0, 0, 0, 0; 0, 3, 2, 0, 0; 0, 0, 0, 0, 0; 1, 0, 0, 0, 0]

Astroid
[-1,1]
7
[-1,1]
7
[-1,  0,  3,  0, -3,  0,  1; 0,  0,  0,  0,  0,  0,  0; 3,  0, 21,  0,  3,  0,  0; 0,  0,  0,  0,  0,  0,  0; -3,  0,  3,  0,  0,  0,  0; 0,  0,  0,  0,  0,  0,  0; 1,  0,  0,  0,  0,  0,  0]