Я смотрю из окна на чердаке во двор соседа. У них есть собака, прикованная к столбу в центре двора. Собака бегает по двору, но всегда находится на конце своей цепи, так что в итоге она оставляет след в грязи. Обычно эта дорожка была бы идеально круглой, но у моих соседей есть некоторые другие полюсы в их дворе, которые цепляются за цепь собаки. Каждый раз, когда цепь собаки ударяется о столб, собака начинает вращаться вокруг нового полюса с любой длиной цепи, равной ее радиусу. Поскольку полюса, собака и цепь имеют нулевую ширину (мои соседи - математики), цепь может вращаться вокруг полюса бесконечно без сокращения радиуса круга. Собака также может пройти через цепь (только не ошейник), если цепь находится на ее пути. Наблюдая за этой странностью какое-то время, я решаю написать код, имитирующий собаку моего соседа. Код будет принимать местоположения центрального полюса, к которому прикована собака, местоположения других полюсов во дворе моих соседей, длину цепи и начальное местоположение собаки, и выводит диаграмму, указывающую путь, где собака стерла траву. Вы можете предположить, что любая комбинация из следующих является постоянной (и, следовательно, не принимать их в качестве входных данных):

• Расположение полюса, к которому прикована собака

• Длина цепи

• Исходное местоположение собаки

Солнце встает, поэтому пространство на полу моего чердака, освещаемое окном, сокращается, давая мне все меньше и меньше места для написания моего кода. Пожалуйста, постарайтесь свести к минимуму количество байтов в вашем коде, чтобы у меня было место для черновика на моем чердаке.

Контрольные примеры

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

Poles at 1,2 -1,2

Poles at 0,.5

Poles at 0,1 1,1 -2,1 -1,-.5

Poles at 0,1 1,1

Python 3 с использованием matplotlib, 457 байт

from cmath import*
from matplotlib import pyplot as g,patches as i
def x(p):
 p+=[0];d=180/pi;a=2;h=g.gca();h.set_xlim(-5,5);h.set_ylim(-5,5)
 while a:
  a-=1;c=0;y=3;z=-pi/2
  while 1:
   s=[n for n in p if abs(n-c)<=y and n!=c]
   if not s:h.add_patch(i.Arc((c.real,c.imag),y*2,y*2));break
   n=[max,min][a](s,key=lambda n:(z-phase(n-c))%(2*pi));l,r=polar(n-c);h.add_patch(i.Arc((c.real,c.imag),y*2,y*2,[z,r][a]*d,0,[r-z,z-r][a]*d));y-=l;z=r;c=n
 g.show()

Поскольку ваши соседи математики, я предположил, что сад вашего соседа занимает сложную область, и поэтому любые координаты объектов в саду являются комплексными числами. Чтобы использовать эту функцию, вы должны передать ей список комплексных чисел, обозначающих расположение полюсов в саду вашего соседа. Было выбрано представление системы координат по умолчанию, где справа - положительные действительные числа, а вверх - положительные мнимые числа. Это означает, что примеры становятся:

x([2j+1,2j-1])
x([.5j])
x([1j,1+1j,-2+1j,-1-.5j])
x([1j,1+1j])

Кроме того, программа предполагает следующее: привязь привязана к точке 0, длина привязи составляет 3 единицы, а площадь графика равна 10 на 10 с центром в районе 0. Для этих параметров результаты точно совпадают с примерами, и вот как выглядит результат (для последнего примера):

Алгоритм довольно прост, требуется только одно условие, чтобы различать поиск по часовой стрелке и против часовой стрелки. Состояние алгоритма определяется текущей точкой вращения и ориентацией / оставшейся длиной поводка, когда он достигает текущей точки вращения. Это работает следующим образом:

• Отфильтруйте точки из набора столкновений, которые находятся дальше от текущей точки вращения, чем оставшаяся длина поводка, а также от текущей точки вращения.
• Если этот набор пуст, нарисуйте круг с радиусом оставшейся длины ремня вокруг этой точки, когда конец этого плеча достигнут.
• Определите точку, где разность фаз между вектором разности и ориентацией поводка минимальна / максимальна. Это следующая точка поворота поводка по часовой стрелке / против часовой стрелки соответственно.
• Нарисуйте дугу на основе этих векторов, возьмите длину поводка, вычтите величину расстояния и установите ориентацию поводка в соответствии с ориентацией разностного вектора. Обновите точку вращения и продолжайте с самого начала.

Затем этот алгоритм выполняется сначала в направлении по часовой стрелке, после чего состояние сбрасывается и выполняется в направлении против часовой стрелки. Простота алгоритма означает, что около половины всей программы тратится на функции рисования. Если бы процедуры рисования были удалены, он бы удалил 218 байт из размера программы.

Ниже приведена версия, не содержащая гольф, которая также содержит отладочный код, который также отображает точки и столкновения поводка:

from cmath import pi, rect, polar, phase
from matplotlib import pyplot, patches
def x_ungolfed(points):
    degrees = 180/pi # conversions

    # add the center point to the collision points
    points.append(0.0)

    # configure plot area
    axes=pyplot.gca()
    axes.set_xlim(-5,5)
    axes.set_ylim(-5,5)

    # plot the points
    x, y =zip(*((p.real, p.imag) for p in points))
    axes.scatter(x, y, 50, "b")

    # first iteration is clockwise, second counterclockwise
    clockwise = 2
    while clockwise:
        clockwise -= 1

        # initial conditions
        center = 0 + 0j;
        leash_size = 3
        leash_angle = -pi / 2

        # initial leash plot
        leash_start = rect(leash_size, leash_angle)
        axes.plot([center.real, leash_start.real], [center.imag, leash_start.imag], "r")

        # search loop
        while 1:
            # find possible collission candidates
            candidates = [n for n in points if abs(n - center) <= leash_size and n != center]
            # if we reached the end, draw a circle
            if not candidates:
                axes.add_patch(patches.Arc(
                    (center.real, center.imag), 
                    leash_size*2, leash_size*2
                ))
                break
            # find the actual collision by comparing the phase difference of the leash angle vs the difference between the candidate and the current node
            new = (min if clockwise else max)(candidates, key=lambda n: (leash_angle - phase(n - center)) % (2 * pi))

            # convert the difference to polar coordinates
            distance, new_angle = polar(new - center)
            # draw the arc
            if clockwise:
                axes.add_patch(patches.Arc(
                    (center.real, center.imag),
                    leash_size * 2, leash_size * 2,
                    new_angle * degrees,
                    0,
                    (leash_angle-new_angle) * degrees
                ))
            else:
                axes.add_patch(patches.Arc(
                    (center.real, center.imag),
                    leash_size * 2, leash_size * 2,
                    leash_angle * degrees,
                    0,
                    (new_angle - leash_angle) * degrees
                ))
            # draw intermediate lines
            edge = rect(leash_size, new_angle) + center
            axes.plot([center.real, edge.real], [center.imag, edge.imag], "g")

            # perform updates: decrease remaining leash size, set new leash angle, move rotation center to the collision
            leash_size -= distance
            leash_angle = new_angle
            center = new

    # show the graph
    pyplot.show()

Выходные данные выглядят так:

Обработка 3, 815, 833, 835, 876, 879 байтов.

Благодаря @ZacharyT удалось сэкономить два байта, удалив ненужные скобки

void settings(){size(600,600);}int i,w,x,n;float l,d,t,a,f,g,m,R,U;float[][]N,T;float[]S,p;void s(float[][]t){N=new float[t.length+1][2];N[0][0]=N[0][1]=i=0;for(float[]q:t)N[++i]=q;translate(w=300,w);noFill();pushMatrix();f(N,0,-w,w,1,0);popMatrix();f(N,0,-w,w,0,0);}float p(float a,float b){for(a+=PI*4;a>b;)a-=PI*2;return a;}void f(float[][]P,float x,float y,float L,int c,int I){l=2*PI;d=i=0;S=null;for(;i<P.length;i++){float[]p=P[i];g=atan2(y,x);m=atan2(p[1],p[0]);if(p(f=(c*2-1)*(g-m),0)<l&(t=dist(0,0,p[0],p[1]))<=L&I!=i){l=p(f,0);S=new float[]{g,m};d=t;n=i;}}if(S==null)ellipse(0,0,2*(L-d),2*(L-d));else{arc(0,0,L*2,L*2,p(S[c],S[1-c]),S[1-c]);R=cos(a=S[1]);U=sin(a);translate(d*R,d*U);T=new float[P.length][2];for(int i=0;i<T.length;T[i][1]=P[i][1]-d*U,i++)T[i][0]=P[i][0]-d*R;f(T,(L-d)*R,(L-d)*U,L-d,c,n);}}

Запустите эту программу так:

void setup() {
    s(new float[][]{{0,100},{100,100},{-200,100},{-100,-50}});
}

(функция sпринимает в float[][]). По сути, это тестовый пример № 3, но умноженный на 100, чтобы соответствовать окну.

Несколько вещей на заметку:

• программа НЕ рисует столбы
• изображения выглядят перевернутыми вверх ногами, потому что в системе координат обработки положительная ось Y идет вниз
• Поскольку при обработке используются числа с плавающей запятой, вычисления не очень точны, поэтому вы можете увидеть это на изображениях. Я спросил ОП, имеют ли значение эти ошибки с плавающей точкой.
• размер окна 600 пикселей на 600 пикселей
• очень маленькие входные координаты будут мешать программе, потому что стек pushMatrix()и работа popMatrix()могут содержать только 32 матрицы.
• собака начинается с (0, -300), а цепь начинается с 300 пикселей в длину
• изображения ниже были уменьшены для удобства

Пример вывода для приведенного выше теста.

Если вы хотите увидеть предварительно подтвержденный вывод, добавьте эту строку сразу после translate(w,w);функции in s.

background(-1);scale(1,-1);fill(255,0,0);ellipse(0,0,25,25);fill(0);for(float[]q:N)ellipse(q[0],q[1],25,25);

И это дает нам такой результат:

Неуправляемый f()и объяснение

(также содержит отладочный код)

void f(float[][]points, float x, float y, float len, int c, int pindex) {
    print(asd+++")");
    float closest = 2*PI;
    float d=0,t;
    float[]stuff = null;
    int index = 0;
    for(int i=0;i<points.length;i++) {
        if(pindex != i) {
            float[]p = points[i];
            float originAngle = atan2(y, x);
            float tempAngle = atan2(p[1], p[0]);
            //println(x,y,p[0],p[1]);
            float diff = c<1?tempAngle-originAngle:originAngle-tempAngle;
            println("@\t"+i+"; x=\t"+x+"; y=\t"+y+"; tx=\t"+p[0]+"; ty=\t",p[1], diff, originAngle, tempAngle);
            if(p(diff) < closest && (t=dist(0,0,p[0],p[1])) < len) {
                println("+1");
                closest = p(diff);
                stuff = new float[]{originAngle, tempAngle};
                d=t;
                index = i;
            }
        }
    }
    if(stuff == null) {
        ellipse(0,0,2*(len-d),2*(len-d));
        println("mayday");
    } else {
        println("d angles",d,p(stuff[c],stuff[1-c],c), stuff[1-c]);
        //println(points[0]);
        arc(0, 0, len*2, len*2, p(stuff[c],stuff[1-c],c), stuff[1-c]);
        float angle = stuff[1];
        translate(d*cos(angle), d*sin(angle));
        println("Translated", d*cos(angle), d*sin(angle));
        println("angle",angle);
        float[][]temp=new float[points.length][2];
        for(int i=0;i<temp.length;i++){
            temp[i][0]=points[i][0]-d*cos(angle);
            temp[i][1]=points[i][1]-d*sin(angle);
            println(temp[i]);
        }
        println(d*sin(angle));
        pushMatrix();
        println();
        f(temp, (len-d)*cos(angle), (len-d)*sin(angle), (len-d), c, index);
        popMatrix();
        //f(temp, (len-d)*cos(angle), (len-d)*sin(angle), (len-d), 0, index);
    }
}

Короче говоря, программа отправляет двух «искателей», один идет против часовой стрелки, а другой по часовой стрелке. Каждый из этих искателей находит ближайший полюс и рисует дугу к нему, если цепь достаточно длинная, в противном случае он рисует круг. Как только он рисует дугу, он отправляет другого искателя к этому полюсу, и процесс продолжается. f()содержит процесс каждого ищущего. Более подробное объяснение придет, как только я пойду в гольф.

LOGO, 305 298 297 293 байта

Попробуйте код на FMSLogo.

Определите функцию draw(как «гольф» d), которая при вводе в виде списка координат полюса (например draw [[0 100] [100 100] [-200 100] [-100 -50][0 0]], отобразит на экране результат).

Требования:

1. Начальная длина веревки = 300 пикселей. (так как 3 пикселя слишком мало)
2. [0 0]должен быть включен в список полюсов. Если включен код отладки (отрисовки полюсов), то он [0 0]должен быть последним.
3. Собака начинается с координаты x=0, y=-300(как в описании проблемы)

Возможные оптимизации:

1. -1 байт, если исключительный случай (собака сталкивается с шестом) не обязательно должен быть математически корректным путем замены >=на>

Гольф-код:

to f
op(if ?=pos 360 modulo :m*(180+heading-towards ?)360)
end
to x :m[:1 300]
home
forever[make 2 filter[:1>=u ?](sort :p[(u ?)<u ?2])invoke[pd
arc -:m*f :1
pu
if 360=f[stop]make 1 :1-u ?
lt :m*f
setpos ?]reduce[if f<invoke[f]?2[?][?2]]:2]
end
to d :p
copydef "u "distance
foreach[1 -1]"x
end

Развернутый код ( ;запускает встроенный комментарий (используется для пояснения) и :запускает имя переменной):

to f
    op ifelse ? = pos 360 modulo :m*(180 + heading - towards ?) 360
end

to x
    home
    foreach :poles [pu setpos ? pd circle 5] ; debug code
    make "length 300 ; initial length of rope
    forever [
        make "tmp filter [:length >= distance ?] ; floating point error makes > and >= similar,  ~
            ; but >= is correct mathematically ~
            (sort :poles [(distance ?) < distance ?2])
         ; the last = longest element will be rotated
        invoke [
            pd
            arc -:m*f :length
            pu
            if 360=f [stop]
            make "length :length - distance ?
            lt :m*f
            setpos ?
        ] reduce [
            if f < invoke[f]?2 [?] [?2]
        ] :tmp ; apply to use ? instead of :pos
    ]
end

to draw :poles
    foreach [1 -1] [[m]
        x
    ]
end

Python 2 + PIL, 310 байт

from PIL import Image
from cmath import*
I,_,X,P=Image.new('1',(300,300),'white'),abs,polar,input()
def r(s):
 a,C,l=0,0,3
 while _(a)<99:
  c=C+l*exp(1j*a);I.load()[c.real*30+150,150-c.imag*30]=0
  for p in P+[0]:
   N,E=X(C-c);n,e=X(C-p)
   if n<=N and _(E-e)<.1:l-=_(p-C);C=p
  a+=s
r(.01)
r(-.01)
I.show()

Скрипт читает список точек из стандартного ввода в виде списка комплексных чисел.

printf '[complex(0,0.5)]' | python2 snippet.py

printf '[complex(0,1), complex(1,1)]' | python2 snippet.py