Je regarde par la fenêtre de mon grenier dans la cour de mon voisin. Ils ont un chien enchaîné à un poteau au centre de la cour. Le chien court autour de la cour mais est toujours au bout de sa chaîne, donc il finit par laisser une trace dans la terre. Normalement, cette piste serait parfaitement circulaire, mais mes voisins ont d'autres poteaux dans leur cour sur lesquels la chaîne du chien est accrochée. Chaque fois que la chaîne du chien frappe un poteau, le chien commence à tourner autour du nouveau poteau avec la longueur de chaîne qui reste comme rayon. Puisque les pôles, le chien et la chaîne ont tous une largeur nulle (mes voisins sont des mathématiciens), la chaîne peut s'enrouler indéfiniment autour d'un pôle sans raccourcir le rayon du cercle. Le chien peut également passer à travers la chaîne (mais pas son collier) si la chaîne se trouve sur son chemin. Après avoir observé cette bizarrerie pendant un certain temps, je décide que j'écrirai du code pour simuler le chien de mon voisin. Le code prendra les emplacements d'un poteau central, auquel le chien est enchaîné, les emplacements des autres poteaux dans la cour de mes voisins, la longueur de la chaîne et l'emplacement de départ du chien, et affichera un diagramme indiquant la chemin où le chien a épuisé l'herbe. Vous pouvez supposer que toute combinaison des éléments suivants est constante (et ne les prenez donc pas en entrée):

• Emplacement du poteau auquel le chien est enchaîné

• Longueur de la chaîne

• Lieu de départ du chien

Le soleil se lève, donc l'espace au sol de mon grenier éclairé par la fenêtre se rétrécit, me laissant de moins en moins d'espace pour écrire mon code. Veuillez essayer de minimiser le nombre d'octets de votre code afin que j'aie de l'espace pour le rédiger sur mon grenier.

Cas de test

Ici, je suppose que le chien commence 3 unités au sud du pôle auquel il est enchaîné (le point rouge), situé à 0,0. J'ai indiqué où les pôles sont avec des points pour plus de clarté, vous n'avez pas besoin de les inclure dans votre sortie.

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 utilisant matplotlib, 457 octets

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

Parce que vos voisins sont des mathématiciens, j'ai supposé que le jardin de votre voisin occupe le domaine complexe et toutes les coordonnées des objets dans le jardin sont donc des nombres complexes. Pour utiliser cette fonction, vous devez donc lui passer une liste de nombres complexes indiquant l'emplacement des pôles dans le jardin de votre voisin. La représentation par défaut du système de coordonnées a été choisie, où à droite sont des nombres réels positifs et vers le haut sont des nombres imaginaires positifs. Cela signifie que les exemples deviennent:

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

En outre, le programme suppose les éléments suivants: la laisse est liée au point 0, la laisse fait 3 unités de long et la zone de tracé est de 10 sur 10 centrée autour de 0. Pour ces paramètres, les résultats correspondent exactement aux exemples, et voici à quoi ressemble le résultat (pour l'exemple final):

L'algorithme est assez simple, ne nécessitant qu'un conditionnel pour différencier la recherche dans le sens horaire et antihoraire. L'état de l'algorithme est défini par le point de rotation actuel et l'orientation / la longueur restante de la laisse lorsqu'elle atteint le point de rotation actuel. Cela fonctionne comme suit:

• Filtrez les points de l'ensemble de collision qui sont plus éloignés du point de rotation actuel que la longueur de laisse restante, ainsi que le point de rotation actuel.
• Si cet ensemble est vide, dessinez un cercle avec le rayon de la longueur de ceinture restante autour de ce point lorsque l'extrémité de ce bras a été atteinte.
• Déterminez le point où la différence de phase entre le vecteur de différence et l'orientation de la laisse est minimale / maximale. Il s'agit du point suivant que la laisse touchera respectivement dans le sens horaire / antihoraire.
• Tracez l'arc en fonction de ces vecteurs, prenez la longueur de la laisse, soustrayez l'amplitude de la distance et réglez l'orientation de la laisse sur l'orientation du vecteur de différence. Mettez à jour le point de rotation et continuez depuis le début.

Cet algorithme est ensuite exécuté d'abord dans le sens horaire, après quoi l'état est réinitialisé et il est exécuté dans le sens antihoraire. La simplicité de l'algorithme signifie qu'environ la moitié du nombre de sous-programmes est consacré aux fonctions de dessin. Si les routines de dessin étaient supprimées, cela supprimerait 218 octets de la taille du programme.

Ce qui suit est une version non golfée qui contient également du code de débogage, qui affiche également les points et les collisions en laisse:

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

La sortie qu'il produit ressemble à ceci:

Traitement 3, 815 833 835 876 879 octets

Enregistrement de deux octets grâce à @ZacharyT en supprimant les parenthèses inutiles

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

Exécutez ce programme comme ceci:

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

(la fonction sprend en a float[][]). Il s'agit essentiellement du testcase n ° 3, mais multiplié par 100 pour s'adapter à la fenêtre.

Plusieurs choses à noter:

• le programme ne dessine PAS de pôles
• les images apparaissent inversées car dans le système de coordonnées de Processing, l'axe y positif descend
• parce que le traitement utilise des flottants, les calculs ne sont pas très précis, vous pouvez donc le voir dans les images. J'ai demandé à l'OP si ces erreurs en virgule flottante importent.
• la taille de la fenêtre est de 600 pixels par 600 pixels
• de très petites coordonnées d'entrée gêneront le programme car la pile pushMatrix()et les popMatrix()opérations ne peuvent contenir que 32 matrices.
• le chien commence à (0, -300) et la chaîne commence à 300 pixels de long
• les images ci-dessous ont été réduites pour plus de commodité

Exemple de sortie pour le testcase ci-dessus.

Si vous voulez voir la sortie prettifiée, ajoutez cette ligne juste après la translate(w,w);fonction 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);

Et cela nous donne ce résultat:

Non golfé f()et explication

(contient également du code de débogage)

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

Pour le dire brièvement, le programme envoie deux "demandeurs", l'un va dans le sens anti-horaire et l'autre dans le sens horaire. Chacun de ces chercheurs trouve le pôle le plus proche et lui dessine un arc si la chaîne est suffisamment longue, sinon il dessine un cercle. Une fois qu'il dessine un arc, il envoie un autre chercheur à ce pôle et le processus se poursuit. f()contient le processus de chaque chercheur. Une explication plus détaillée viendra dès que je jouerai au golf.

LOGO, 305 298 297 293 octets

Essayez le code sur FMSLogo.

Définissez une fonction draw(jouée en tant que d) qui, donnée en entrée sous la forme d'une liste de coordonnées de pôle (par exemple draw [[0 100] [100 100] [-200 100] [-100 -50][0 0]], dessinera à l'écran le résultat.

Exigences:

1. Longueur de corde initiale = 300 pixels. (car 3 pixels est trop petit)
2. [0 0]doit être inclus dans la liste des pôles. Si le code de débogage (pôles de dessin) est activé, il [0 0]doit s'agir du dernier élément.
3. Le chien commence aux coordonnées x=0, y=-300(comme dans la description du problème)

Optimisations possibles:

1. -1 octet si un cas exceptionnel (le chien a couru dans un poteau) n'est pas tenu d'être mathématiquement correct en le remplaçant >=par>

Code de golf:

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

Code non golfé ( ;démarre un commentaire en ligne (utilisé pour l'explication) et :démarre un nom de variable):

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 octets

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

Le script lit la liste des points de stdin comme une liste de nombres complexes.

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

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