Patrzę przez okno na poddaszu na podwórze mojego sąsiada. Mają psa przykutego do słupa na środku podwórza. Pies biegnie po podwórku, ale zawsze znajduje się na końcu łańcucha, więc kończy się śladem na ziemi. Zwykle ten tor byłby idealnie okrągły, ale moi sąsiedzi mają na swoim podwórku inne tyczki, na które zaczepia się łańcuch psa. Za każdym razem, gdy łańcuch psa uderza w słup, pies zaczyna obracać się wokół nowego bieguna, niezależnie od długości łańcucha jaka pozostała jego promień. Ponieważ bieguny, pies i łańcuch mają zerową szerokość (moi sąsiedzi są matematykami), łańcuch może owijać się wokół bieguna w nieskończoność bez promienia koła. Pies może również przejść przez łańcuch (ale nie jego obrożę), jeśli łańcuch jest na swojej drodze. Po dłuższej obserwacji tej dziwności postanawiam napisać kod do symulacji psa mojego sąsiada. Kod weźmie lokalizacje środkowego bieguna, do którego jest przykuty pies, lokalizacje innych biegunów na podwórku mojego sąsiada, długość łańcucha i początkową lokalizację psa, i wyświetli diagram wskazujący ścieżka, po której pies zużył trawę. Możesz założyć, że dowolna kombinacja następujących elementów jest stała (a zatem nie bierzesz ich za dane wejściowe):

• Lokalizacja słupa, do którego jest przykuty pies

• Długość łańcucha

• Lokalizacja początkowa psa

Wschodzi słońce, więc przestrzeń na podłodze mojego poddasza oświetlona oknem kurczy się, dając mi coraz mniej miejsca na pisanie kodu. Spróbuj zminimalizować liczbę bajtów kodu, aby mieć miejsce na szkicowanie go na podłodze na poddaszu.

Przypadki testowe

Zakładam, że pies zaczyna 3 jednostki na południe od bieguna, do którego jest przykuty (czerwona kropka), znajdującego się przy 0,0. Wskazałem, gdzie są bieguny z kropkami dla jasności, nie musisz włączać ich do swojego wyjścia.

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 przy użyciu matplotlib, 457 bajtów

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

Ponieważ twoi sąsiedzi są matematykami, założyłem, że ogród twojego sąsiada zajmuje złożoną domenę, a zatem wszelkie współrzędne obiektów w ogrodzie są liczbami złożonymi. Aby skorzystać z tej funkcji, należy przekazać jej listę liczb zespolonych oznaczających położenie biegunów w ogrodzie sąsiada. Wybrano domyślną reprezentację układu współrzędnych, gdzie po prawej stronie są dodatnie liczby rzeczywiste, a w górę - dodatnie liczby urojone. Oznacza to, że przykłady stają się:

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

Ponadto program zakłada następujące rzeczy: smycz jest przywiązana do punktu 0, smycz ma 3 jednostki długości, a powierzchnia działki wynosi 10 na 10, a jej środek wynosi 0. Dla tych parametrów wyniki odpowiadają dokładnie przykładom, i tak wygląda wynik (dla końcowego przykładu):

Algorytm jest dość prosty, wymagając tylko jednego warunku do rozróżnienia wyszukiwania w prawo i w lewo. Stan algorytmu jest określony przez bieżący punkt obrotu i orientację / pozostałą długość smyczy, gdy uderzy ona w bieżący punkt obrotu. Działa w następujący sposób:

• Odfiltruj punkty z zestawu kolizji, które są dalej od bieżącego punktu obrotu niż pozostała długość smyczy, a także bieżący punkt obrotu.
• Jeśli ten zestaw jest pusty, narysuj okrąg o promieniu pozostałej długości pasa wokół tego punktu po osiągnięciu końca tego ramienia.
• Określ punkt, w którym różnica faz między wektorem różnicy a orientacją smyczy jest minimalna / maksymalna. Jest to kolejny punkt, w którym smycz uderzy odpowiednio w prawo / w lewo.
• Narysuj łuk na podstawie tych wektorów, weź długość smyczy, odejmij wielkość odległości i ustaw orientację smyczy na orientację wektora różnicy. Zaktualizuj punkt obrotu i kontynuuj od początku.

Algorytm ten jest następnie wykonywany najpierw w kierunku zgodnym z ruchem wskazówek zegara, po czym stan jest resetowany i wykonywany w kierunku przeciwnym do ruchu wskazówek zegara. Prostota algorytmu oznacza, że ​​około połowa programu według liczby bajtów jest przeznaczona na funkcje rysowania. Usunięcie procedur rysowania spowodowałoby usunięcie 218 bajtów z rozmiaru programu.

Poniżej znajduje się wersja bez golfa, która zawiera również kod debugowania, który wyświetla także punkty i kolizje smyczy:

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

Dane wyjściowe, które produkuje, wyglądają następująco:

Przetwarzanie 3, 815 833 835 876 879 bajtów

Zaoszczędź dwa bajty dzięki @ZacharyT, usuwając niepotrzebne nawiasy

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

Uruchom ten program tak:

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

(funkcja sprzyjmuje a float[][]). Jest to zasadniczo przypadek testowy nr 3, ale pomnożony przez 100 w celu dopasowania do okna.

Kilka rzeczy do zapamiętania:

• program NIE rysuje biegunów
• obrazy wydają się odwrócone do góry nogami, ponieważ w układzie współrzędnych Przetwarzania dodatnia oś y zmniejsza się
• ponieważ Przetwarzanie używa liczb zmiennoprzecinkowych, obliczenia nie są bardzo dokładne, więc możesz to zobaczyć na obrazach. Zapytałem OP, czy te zmiennoprzecinkowe błędy mają znaczenie.
• rozmiar okna wynosi 600 na 600 pikseli
• bardzo małe współrzędne wejściowe rozbijają program, ponieważ stos pushMatrix()i popMatrix()operacja mogą pomieścić tylko 32 macierze.
• pies zaczyna się od (0, -300), a łańcuch zaczyna się od 300 pikseli
• poniższe zdjęcia zostały zminimalizowane dla wygody

Przykładowe dane wyjściowe dla powyższej skrzynki testowej.

Jeśli chcesz zobaczyć upiększone wyjście, dodaj ten wiersz zaraz po translate(w,w);funkcji 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);

A to daje nam ten wynik:

Bez golfa f()i wyjaśnienia

(zawiera również kod debugowania)

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

Krótko mówiąc, program wysyła dwóch „poszukiwaczy”, jeden idzie w lewo, a drugi w prawo. Każdy z tych poszukiwaczy znajduje najbliższy biegun i rysuje do niego łuk, jeśli łańcuch jest wystarczająco długi, w przeciwnym razie rysuje okrąg. Gdy narysuje łuk, wysyła kolejnego poszukiwacza na ten biegun i proces trwa. f()zawiera proces każdego poszukiwacza. Bardziej szczegółowe wyjaśnienie pojawi się, gdy tylko zacznę grać w golfa.

LOGO, 305 298 297 293 bajtów

Wypróbuj kod na FMSLogo.

Zdefiniuj funkcję draw(golfed as d), która podana jako lista współrzędnych biegunowych (na przykład draw [[0 100] [100 100] [-200 100] [-100 -50][0 0]]wyświetli wynik na ekranie).

Wymagania:

1. Początkowa długość liny = 300 pikseli. (ponieważ 3 piksele są za małe)
2. [0 0]musi znajdować się na liście biegunów. Jeśli włączony jest kod debugowania (bieguny losowania), [0 0]musi to być ostatni element.
3. Pies zaczyna od współrzędnych x=0, y=-300(jak w opisie problemu)

Możliwe optymalizacje:

1. -1 bajt, jeśli wyjątkowy przypadek (pies wpada na tyczkę) nie musi być matematycznie poprawny przez zastąpienie >=go>

Kod do gry w golfa:

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

Nieskluczony kod ( ;uruchamia wbudowany komentarz (służy do wyjaśnienia) i :uruchamia nazwę zmiennej):

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 bajtów

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

Skrypt czyta listę punktów ze standardowego wejścia jako listę liczb zespolonych.

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

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