Алгебраическая кривая - это некое «1D подмножество» «2D-плоскости», которое можно описать как набор нулей {(x,y) in R^2 : f(x,y)=0 }полинома f. Здесь мы рассматриваем 2D-плоскость как реальную плоскость R^2, так что мы можем легко представить, как могла бы выглядеть такая кривая, в основном то, что можно нарисовать карандашом.

Примеры:

• 0 = x^2 + y^2 -1 круг радиуса 1
• 0 = x^2 + 2y^2 -1 эллипс
• 0 = xyкрест форма, в основном , объединение оси абсцисс и ось ординат
• 0 = y^2 - x парабола
• 0 = y^2 - (x^3 - x + 1)эллиптической кривой
• 0 = x^3 + y^3 - 3xy лист Декарта
• 0 = x^4 - (x^2 - y^2) лемниската
• 0 = (x^2 + y^2)^2 - (x^3 - 3xy^2) трифолиум
• 0 = (x^2 + y^2 - 1)^3 + 27x^2y^2 астроид

задача

Учитывая полином f(как определено ниже) и диапазоны x / y, выведите черно-белое изображение размером не менее 100x100 пикселей, которое показывает кривую в виде черной линии на белом фоне.

Детали

Цвет : Вы можете использовать любые два других цвета по вашему выбору, их будет легко отличить друг от друга.

Сюжет : вместо пиксельного изображения вы также можете вывести это изображение как ascii-art, где фоновые «пиксели» должны быть пробелом / подчеркиванием или другим символом, который «выглядит пустым», а линия может быть сделана из символа, который выглядит » полный "нравится Mили Xили #.

Вам не нужно беспокоиться о псевдонимах.

Вам нужно только построить линии, в которых знак полинома меняется с одной стороны линии на другую (это означает, что вы можете, например, использовать алгоритм квадрата шествия), вам не нужно правильно изображать «патологические случаи, например, 0 = x^2когда знак меняет». не меняется при переходе с одной стороны линии на другую, но линия должна быть непрерывной и разделяющей области разных признаков f(x,y).

Полиномиальной : Полином задаются в виде (m+1) x (n+1)матрицы / список списков (действительные) коэффициентов, в примере ниже терминов коэффициентов приведены в своей позиции:

[   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]

Если вы предпочитаете, вы можете считать матрицу квадратной (что всегда можно сделать с необходимым заполнением нулями), и, если хотите, вы также можете предположить, что размер матрицы указан в качестве дополнительных входных данных.

Далее приведенные выше примеры представлены в виде матрицы, определенной следующим образом:

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]

Тестовые случаи с x-range / y-range:

(В не очень удобочитаемом, но лучше копируемо-способном формате, доступном здесь, на 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]

У меня есть вдохновение для некоторых кривых из этого PDF.

Haskell, 283 275 байт

Функция gдолжна вызываться с матрицей и двумя диапазонами в качестве аргументов. Матрица - это просто список списков, каждый из которых представляет собой список из двух элементов.

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

Вот результаты для более интересных случаев: обратите внимание, что мне пришлось уменьшить размер результата с 100x100 до 40x40, чтобы он вписался в консоль (просто измените жестко закодированный 102 на меньшее число). Также обратите внимание, что ось Y направлена ​​вниз.

Matlab, 114 100 92 байта

Правильный инструмент для работы? Я использую интересный способ, который Matlab использует printfдля генерации полинома в виде строки. Этот многочлен может быть представлен для того, чтобы ezplotпостроить неявную кривую в указанной области. Для удобства чтения код представлен после новой строки; который не нужен и не учитывается в размере.

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])

Гольф прогресс как расширяемый фрагмент.

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])

Вывод тестовых случаев (нажмите для полного просмотра):

Python 2, 261 байт

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))

Формат ввода: matrix,xbounds,ybounds(например [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]). Выходной формат: обычный PGM .

Это оценивает расстояние от каждого центра пикселя до кривой, используя приближение первого порядка d ( x , y ) = | p ( x , y ) | / | ∇ p ( x , y ) |, где ∇ p - градиент многочлена p . (Это расстояние от ( x , y ) до пересечения касательной плоскости в точке ( x , y , p ( x , y )) с плоскостью xy .) Тогда пиксели, где d ( x , y ) меньше ширины кривой на один пиксель пропорционально d ( x , y ), что приводит к хорошим сглаженным линиям (даже если это не является обязательным требованием).

Вот же графики с функцией расстояния, разделенной на 16, чтобы сделать ее видимой.

Python 3.5 + MatPlotLib + Numpy, 352 байта:

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()

Именованная функция. Довольно долго, но эй, я просто счастлив, что смог выполнить задачу. Принимает 3 входа, которые представляют собой m by nматрицу, x-range иy -range, которые все должны быть в массивах (например,[[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2] ). Выводит заполненный график в новом графическом интерактивном окне. Буду ли это играть в гольф больше времени, когда смогу, но сейчас я доволен этим.

Окончательные результаты для тестовых случаев:

MATL , 67 61 байт

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

Этот код запускается в версии 18.5.0 языка, который предшествует вызову. Input использует Факультативный m, nпараметры. Матрица имеет точки с запятой в качестве разделителей строк. Точный формат ввода (используя параболу в качестве примера)

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

Код производит изображение размером 255 × 255. Это можно проверить с помощью @Suever 's MATL Online компилятора, который, помимо других очень интересных функций, включает графический вывод. Смотри например

• Эллиптическая кривая ;
• Фолиум Декарта .

Этот компилятор все еще находится в экспериментальной стадии. Пожалуйста, сообщайте о любых проблемах @Suever в чате MATL . Если кнопка «Выполнить» не работает, попробуйте обновить страницу и нажать снова.

Если вы предпочитаете вывод ASCII , код необходимо немного изменить (изменения коснутся только первых двух и последних четырех символов кода выше):

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

Это создает сетку 100 × 100 ASCII, которая использует символ *для представления кривой. Вы также можете проверить это с @Dennis ' Попробуйте онлайн! Платформа:

• Эллиптическая кривая ;
• Фолиум Декарта .

Обратите внимание, что соотношение сторон вывода ASCII изменяется, потому что символы немного выше, чем широкие.

объяснение

Сначала код вычисляет полином от двух переменных на сетке x - y . Это интенсивно использует широковещание , вычисляя промежуточный 4D массив, где каждое измерение представляет x значений, значений y , показателей x , y показателей соответственно.

Из этой функции вычисляется линия нулевого уровня. Поскольку задача указывает, что необходимо обнаруживать только изменения знака, код применяет двухмерную свертку с блоком единиц 2 × 2 и помечает пиксель как принадлежащий линии, если не четыре значения блока имеют одинаковый знак.

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)

Все тесты

Вот все входные данные в соответствующем формате, если вы хотите попробовать:

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]