A Dog on a Chain

Question

I'm looking out of my attic window into my neighbor's yard. They have a dog chained to a post in the center of the yard. The dog runs around the yard but is always on the end of its chain, so it ends up leaving a track in the dirt. Normally this track would be perfectly circular, but my neighbors have some other poles in their yard that the dog's chain gets caught on. Each time the dogs chain hits a pole the dog begins rotating about the new pole with whatever length of chain is left as its radius. Since the poles, the dog and the chain all have zero width (my neighbors are mathematicians) the chain can wind around a pole indefinitely without the radius of the circle shortening. The dog can also pass through the chain (just not its collar) if the chain is in its path. After observing this oddity for a while I decide I will write some code to simulate my neighbor's dog. The code will take the locations of a center pole, to which the dog is chained, the locations of the other poles in my neighbors yard, the length of the chain, and the starting location of the dog, and will output a diagram indicating the path where the dog has worn down the grass. You may assume that any combination of the following are constant (and thus not take them as input):

• Location of the pole to which the dog is chained

• Length of the chain

• Starting location of the dog

The sun is rising, so the space on the floor of my attic illuminated by the window is shrinking, giving me less and less space to write my code. Please try to minimize the byte count of your code so that I have space to draft it on my attic floor.

Test cases

Here I assume that the dog starts 3 units south from the to which pole it is chained (the red dot), located at 0,0. I have indicated where the poles are with dots for clarity, you do not need to include them in your output.

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

Answer 1

Python 3 using matplotlib, 457 bytes

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

Because your neighbors are mathematicians I've assumed that your neighbor's garden occupies the complex domain and any coordinates of objects in the garden are therefore complex numbers. To use this function, you should therefore pass it a list of complex numbers signifying the locations of the poles in your neighbor's garden. The default coordinate system representation has been chosen, where to the right are positive real numbers and upwards are positive imaginary numbers. This means the examples become:

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

Furthermore, the program assumes the following things: the leash is tied to the point 0, the leash is 3 units long, and the plot area is 10 by 10 centered around 0. For these parameters, the results match up exactly with the examples, and this is how the result looks like (for the final example):

The algorithm is quite simple, only requiring one conditional to differentiate the clockwise and the counterclockwise search. The state of the algorithm is defined by the current rotation point and the orientation/remaining length of the leash when it hit the current rotation point. It works as follows:

• Filter out points from the collision set that are further away from the current rotation point than the remaining leash length, as well as the current rotation point.
• If this set is empty, draw a circle with the radius of the remaining belt length around this point as the end of this arm has been reached.
• Determine the point where the phase difference between the difference vector and the leash orientation is minimal/maximal. This is the next point the leash will hit in the clockwise/counterclockwise direction respectively.
• Draw the arc based on these vectors, take the leash length, subtract the magnitude of the distance and set the leash orientation to the orientation of the difference vector. Update the rotation point and continue from the start.

This algorithm is then performed first in the clockwise direction, after which the state is reset and it is executed in the counterclockwise direction. The simplicity of the algorithm means that about half of the program bytecount is spent on the drawing functions. If the drawing routines were stripped out it would remove 218 bytes from the program size.

The following is an ungolfed version that also contains debug code, which also displays points and leash collisions:

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

The output it produces looks like this:

Answer 2

Processing 3, 815 833 835 876 879 bytes

Saved two bytes thanks to @ZacharyT by removing unnecessary parentheses

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

Run this program like so:

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

(the function s takes in a float[][]). This is essentially testcase #3, but multiplied by 100 to fit the window.

Several things to note:

• the program does NOT draw poles
• the images appear flipped upside-down because in Processing's coordinate system, the positive y-axis goes down
• because Processing uses floats, the calculations are not very accurate, so you might see this in the images. I have asked the OP if these floating-point error matter.
• the size of the window is 600 pixels by 600 pixels
• very small input coordinates will bork the program because the stack pushMatrix() and popMatrix() operate on can only hold 32 matrices.
• the dog starts at (0, -300) and the chain starts at 300 pixels long
• the images below have been minified for convenience

Sample output for the above testcase.

If you want to see the prettified output, add this line right after the translate(w,w); in function 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);

And this gives us this result:

Ungolfed f() and explanation

(contains debug code as well)

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

To put it shortly, the program sends two "seekers", one goes anti-clockwise and the other clockwise. Each of these seekers finds the closest pole and draws an arc to it if the chain is long enough, other wise it draws a circle. Once it draws an arc, it sends another seeker to that pole and the process continues. f() contains the process of each seeker. A more detailed explanation will come as soon as I golf this more.

Answer 3

LOGO, 305 298 297 293 bytes

Try the code on FMSLogo.

Define a function draw (golfed as d) that, given input as a list of pole coordinate (for example draw [[0 100] [100 100] [-200 100] [-100 -50][0 0]], will draw on screen the result.

Requirements:

1. Initial rope length = 300 pixels. (as 3 pixels is too small)
2. [0 0] must be included in pole list. If debug code (draw poles) is turned on, then [0 0] must be the last item.
3. The dog start at coordinate x=0, y=-300 (as in the problem description)

Possible optimizations:

1. -1 byte if exceptional case (the dog run into a pole) is not required to be mathematically correct by replacing >= with >

---

Golfed code:

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

---

Ungolfed code (; starts an inline comment (used for explanation), and : starts a variable name):

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

Answer 4

Python 2 + PIL, 310 bytes

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

The script reads the list of points from stdin as a list of complex numbers.

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

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