title: Drawing Epicyclogons

text:
# Question
Title: Drawing Epicyclogons
An epicycloid is the curve a point on a circle makes as it rolls around another circle. A cyclogon is the shape a point on a regular polygon makes as it rolls across a plane. An *epicyclogon* is the curve traced by a point on one regular polygon as it rolls around another.

Write a program that draws an epicyclogon given `r`, `r1`, `r2`, `n1`, `n2`:

```
r = number of clockwise revolutions rolling polygon makes around stationary polygon (any real number as limited by float values)
r1 = distance from center of stationary polygon to each of its vertices (positive real number)
r2 = distance from center of rolling polygon to each of its vertices (positive real number)
n1 = number of sides stationary polygon has (integer greater than 2)
n2 = number of sides rolling polygon has (integer greater than 2)

```

### Notes

* When `r` is negative the roller should go **counterclockwise**.
* For `r`, one revolution occurs when the line connecting the centroids of the two shapes sweeps out a full 360 degrees. This notion is expanded to include all values of `r`. (So in a quarter revolution the line connecting the centroids sweeps out 90 degrees.)
* These arguments should come from the command line or your program should prompt for them (e.g. with Python's `input()`).
* `r1` and `r2` are relative to each other, not the dimensions of the image. So you can set one "unit" to be any number of actual pixels.

The point you must trace out is one of the vertices of the rolling shape. The shapes must start with this vertex touching a stationary vertex and two sides adjacent:

The exact starting vertices and the angle of the stationary polygon do not matter.

# Output

The output should go to an image that is at least 600x600 pixels (or some variable dimension than can be set to 600). It must show the entire epicyclogon curve specified by the parameters, well framed in the image.

The rolling and stationary polygons must also be drawn (with the roller in it's final state). The two shapes and the epicyclogon should be three noticeably different colors.

There must also be a simple way to *not* draw the polygons (a change of `true` to `false` in the code suffices).

Please show us at least 2 output images. It's ok to shrink them if necessary.

# Scoring

The shortest code that produces valid output images wins.

**Bonuses**

* Minus 50 bytes if the output is an animated gif (or similar) of the curve being drawn.
* Minus 150 bytes if you let `n1` and `n2` take the value 2 so the shapes become line segments of length `2 * r1` (or `r2`), "rolling" around each other. How you handle `r` when `n1` and `n2` are 2 is up to you since the centroids don't revolve around each other the way they do in other cases. (Not "rolling" at all does not count as handling it.)

Since I am quite eager to see this novel idea executed well (and it's not exactly a cakewalk), **I am going to award 150 bounty rep** to the winner. The contest will end the same day the bounty runs out.

The bounty will not be awarded to the winner if it is clear that they simply rewrote most of the code from another submission.

Library functions that already happen to do this (if there are any) are not allowed.

*Note: This came from my leftover questions that anyone is free to post. But if no one else posts them there's a good chance I will in time. :P*

# Answer
> 3 votes
# MATLAB: 735 bytes - 200 bonus = 535

My program handles the n=2 case and draws a real-time animation. There are a few differences between the golfed and ungolfed versions:

The ungolfed version only has an option to save the animation to a file 'g.gif', by setting `savegif = 1` in the code. It is off by default as it can be annoying for a few reasons:

* Creation of an unwanted file
* Possible lag
* An error is generated if you have multiple monitors and the plot window is not on the right one... The gif saving had to be dropped in the golfed version as it took about 100 bytes, exceeding the size of the bonus.

The ungolfed version draws a circle on the tracer vertex. It also produces more frames and moves faster (though this can be adjusted in the golfed version by changing the numbers).

## Samples:

`f(11,5,90,2,99,0)` after program termination

`epic(1.3,4,2,6,6,1)` with gif output

## Ungolfed code

```
%epicyclogon animation outputs to 'g.gif' if savegif=1 as well as animating in real time

function[] = epic(r,r1,r2,n1,n2,dispPoly)

savegif = 0;  %set to 1 to write .gif

cs = @(a) [cos(a);sin(a)];
vert = @(r, n, v) r * cs(2*pi*v/n);
polyPt = @(l, s, n, r) vert(r, n, floor(l/s)) + mod(l/s,1)*(vert(r, n, floor(l/s)+1) - vert(r, n, floor(l/s)));
polyPt2 = @(i, f, n, r) vert(r, n, i) + f*(vert(r, n, i+1) - vert(r, n, i));
rotm = @(a) [cos(a) -sin(a);sin(a) cos(a)];
arrpluspt = @(a, p) a + kron(p, ones(1,length(a)));
arg = @(p) atan2(p(2), p(1));

E = 1e-9;

dispPoly = dispPoly / dispPoly;

sgn = sign(-r);
r = abs(r);

s1 = 2*r1*sin(pi/n1);
s2 = 2*r2*sin(pi/n2);

%d1 = (r1*r1 - s1*s1*.25)^.5;
d2 = (r2*r2 - s2*s2*.25)^.5;

plotmax = r1+2*r2;

astep = .05; %determines amount of frames per rotation
delay = .01; % time per frame

l = 0;

lRem = 0;
lr = 0;

P1 = vert(r1, n1, 1:n1+1) * dispPoly;
trace = [];

first = 1;
while 1

    if lr %exists while rotating about a corner of the stationary
        rotA = 2*pi/n1;
    else
        rotA = 2*pi/n2;
    end
    rotPt = polyPt(l, s1, n1, r1);
    lb = l + lRem;
    side1 = floor(l / s1 - E);
    side1up = side1 + lr;
    p2cen = polyPt2(side1, lb/s1 -side1 - .5 * s2/s1, n1, r1) + d2 * cs(2*pi*(side1+.5)/n1);
    if first
        p2cen0 = p2cen;
        r = r + arg(p2cen0)/(2*pi);
    end

    for a = 0:astep:rotA
        P2 = vert(r2, n2, 0:n2);
        P2 = rotm( pi +pi/n1 -pi/n2   +2*pi*side1/n1) * P2;
        P2 = arrpluspt(P2, p2cen);
        P2 = arrpluspt(P2, -rotPt);
        P2 = rotm(a) * P2;
        P2 = arrpluspt(P2, rotPt);
        trV = mod(floor(l/s2 + E) + lr, n2) + 1;

        cen = rotm(a) * (p2cen - rotPt) + rotPt;
        trace = [trace,P2(:,trV)];

        plot(P1(1,:), sgn*P1(2,:), P2(1,:)*dispPoly, sgn*P2(2,:)*dispPoly, trace(1,:),sgn*trace(2,:),P2(1,trV), sgn*P2(2,trV),'o');

        %plot(P1(1,:), P1(2,:), P2(1,:), P2(2,:), trace(1,:),trace(2,:),...
        %[0,p2cen0(1)],[0,p2cen0(2)],[0,cen(1)],[0,cen(2)], P2(1,trV), P2(2,trV),'o');

        axis([-plotmax,plotmax,-plotmax,plotmax]);
        axis square
        figure(1);
       if savegif
           drawnow
           frame = getframe(1); % plot window must be on same monitor!
           img = frame2im(frame);
           [img1,img2] = rgb2ind(img,256);
       end
       if first
           if savegif
               imwrite(img1,img2,'g','gif','DelayTime',2*delay); %control animation speed(but not really)
           end
           first = 0;
       else
           if savegif
               imwrite(img1,img2,'g','gif','WriteMode','append','DelayTime', 2*delay);
           end
       end
       pause(.01);

        adf = mod(arg(cen) - r*2*pi, 2*pi);
        if adf < astep & l/(n1*s1) + .5 > r
            return
        end

    end

%cleanup for next iteration
    jump = lRem + ~lr * s2;
    lnex = l + jump;

    if floor(lnex / s1 - E) > side1up
        lnex = s1*(side1up+1);
        lRem = jump - (lnex - l);
        lr = 1;
    else
        lRem = 0;
        lr = 0;
    end
    l = lnex;
end

```

## Golfed code

```
function[]=f(r,h,H,n,N,d)
P=pi;T=2*P;F=@floor;C=@(a)[cos(a);sin(a)];g=@(i,f,n,r)r*C(T*i/n)*(1-f)+f*r*C(T*(i+1)/n);R=@(a)[C(a),C(a+P/2)];W=@(a,p)[a(1,:)+p(1);a(2,:)+p(2)];b=@(p)atan2(p(2),p(1));E=1e-9;d=d/d;S=1-2*(r>0);r=-r*S;x=2*h*sin(P/n);X=2*H*sin(P/N);M=h+2*H;l=0;z=0;L=0;A=h*C(T*(0:n)/n)*d;t=[];while 1
v=l/x;D=F(v-E);q=g(D,v-D,n,h);Z=D+L;c=g(D,v+z/x-D-.5*X/x,n,h)+H*cos(P/N)*C(T*D/n+P/n);r=r+~(l+L)*b(c)/T;for a=0:.1:T/(L*n+~L*N)
O=@(p)W(R(a)*W(p,-q),q);B=O(W(R(P+P/n-P/N+T*D/n)*H*C(T*(0:N)/N),c));t=[t,B(:,mod(F(l/X+E)+L,N)+1)];plot(A(1,:),S*A(2,:),d*B(1,:),d*S*B(2,:),t(1,:),t(2,:)*S)
axis([-M,M,-M,M],'square');pause(.1);if.1>mod(b(O(c))-r*T,T)&v/n+.5>r
return;end;end;j=z+~L*X;J=l+j;L=F(J/x-E)>Z;l=L*x*(Z+1)+~L*J;z=L*(J-l);end

```

## Instructions:

Save the function to a file with the same name, i.e. `epic.m` or `f.m`. Run it by calling the function from the Matlab console.

Usage: `epic(r, r1, r2, n1, n2, dispPoly)` where `dispPoly` is a Boolean variable (zero if false, a nonzero number if true) determining whether to draw the polygons.

Edit: Added bonus of 50 for animated image.

# Answer
> 14 votes
# Java - ~~2,726~~ 2,634 - 200 = 2434 characters

Improved from 3800 ish bytes

Thanks to all for your suggestions (especially pseudonym117), here is the new version.

I added a class P which is the point class and a class L which extends ArrayList

I also added some minor logic changes.

Here is the main class (not golfed):

```
import java.awt.*;
import java.awt.geom.*;

import javax.swing.*;
public class Polygons2 extends JPanel{
    public static void main(String[] args) throws InterruptedException{new Polygons2(args);}
    double q=Math.PI*2;
    int d=1;
    public Polygons2(String[] args) throws InterruptedException{
        double revolutions=Double.valueOf(args[0])*q;
        double stationaryRadius = Double.valueOf(args[1]);
        double rollingRadius = Double.valueOf(args[2]);
        int stationarySides = Integer.valueOf(args[3]);
        int rollingSides = Integer.valueOf(args[4]);
        double dist = stationaryRadius+rollingRadius+70;
        P sp = new P(dist,dist);
        P rp = new P(sp.x,sp.y-rollingRadius-stationaryRadius);
        //get points for rolling polygon and stationary polygon
        int key=0;
        for(double stationaryAngle=-q/4;stationaryAngle<q-q/4;stationaryAngle+=q/stationarySides){
            P p=new P(Math.cos(stationaryAngle)*stationaryRadius+sp.x,Math.sin(stationaryAngle)*stationaryRadius+sp.y);
            p.k=key;key++;
            stationaryPoints.add(p);
        }
        for(double rollingAngle=q/4;rollingAngle<q+q/4;rollingAngle+=q/rollingSides){
            P p=new P(Math.cos(rollingAngle)*rollingRadius+rp.x,Math.sin(rollingAngle)*rollingRadius + rp.y);
            p.k=key;key++;
            rollingPoints.add(p);
        }
        double g=(q/2)-((q/2-(q/rollingSides))/2) - ((q/2-(q/stationarySides))/2)-.05;
        for(P p:rollingPoints){p.r(getPoint(0), g);}
        //set up JFrame
        JFrame f = new JFrame();
        f.add(this);
        f.setSize((int)dist*2+60,(int)dist*2+60);
        f.setVisible(true);
        int[] pKeys= new int[]{stationaryPoints.get(0).k,rollingPoints.get(0).k};
        int index=1;
        P rc = rollingPoints.c();
        P sc =stationaryPoints.c();
        double currentRadian=Math.atan2(rc.y-sc.y,rc.x-sc.x);
        double totalRadian = 0;
        while(Math.abs(totalRadian)<revolutions){
            P rc2 = rollingPoints.c();
            P sc2 =stationaryPoints.c();
            double angle = Math.atan2(rc2.y-sc2.y,rc2.x-sc2.x);
            if(currentRadian-angle<2){totalRadian+=(angle-currentRadian);}
            currentRadian=angle;
            L clone=(L)path.clone();
            clone.add(new P(rollingPoints.get(1).x,rollingPoints.get(1).y));
            path = clone;
            for(P p:rollingPoints){
                p.r(getPoint(pKeys[index]),.01);
                int size = stationaryPoints.size();
                for(int i=0;i<size;i++){
                    P stationaryPointAtI = stationaryPoints.get(i);
                    P nextPoint=null;
                    if(i==size-1){nextPoint=stationaryPoints.get(0);}
                    else{nextPoint=stationaryPoints.get(i+1);}
                    if(p.b(stationaryPointAtI, nextPoint)==1&&containsKey(pKeys,p.k)==0){
                        //rolling point is between 2 stationary points
                        if(index==1){index=0;}else{index=1;}
                        pKeys[index]=p.k;
                    }
                    int size2=rollingPoints.size();
                    for(int h=0;h<size2;h++){
                        P nextPoint2=null;
                        if(h==size2-1){nextPoint2=rollingPoints.get(0);}
                        else{nextPoint2=rollingPoints.get(h+1);}
                        if(stationaryPointAtI.b(rollingPoints.get(h), nextPoint2)==1&&containsKey(pKeys,stationaryPointAtI.k)==0){
                            //stationary point is between 2 rolling points
                            if(index==1){index=0;}else{index=1;}
                            pKeys[index]=stationaryPointAtI.k;
                        }
                    }
                }
            }
            repaint();
            Thread.sleep(5);
        }
    }
    volatile L path = new L();
    L rollingPoints = new L();
    L stationaryPoints = new L();
    P getPoint(int key){
        for(P p:rollingPoints){if(p.k==key){return p;}}
        for(P p:stationaryPoints){if(p.k==key){return p;}}
        return null;
    }
    int containsKey(int[] keys,int key){
        for(int i:keys){if(key==i){return 1;}}
        return 0;
    }
    @Override
    public void paintComponent(Graphics g){
        Path2D.Double sPath = new Path2D.Double();
        sPath.moveTo(stationaryPoints.get(0).x, stationaryPoints.get(0).y);
        for(P p:stationaryPoints){
            sPath.lineTo(p.x, p.y);
        }
        sPath.closePath();
        Path2D.Double rPath = new Path2D.Double();
        rPath.moveTo(rollingPoints.get(0).x, rollingPoints.get(0).y);
        for(P p:rollingPoints){
            rPath.lineTo(p.x, p.y);
        }
        rPath.closePath();
        g.setColor(Color.white);
        g.fillRect(0,0,getWidth(),getHeight());
        Graphics2D t = (Graphics2D)g;
        if(d==1){
        t.setColor(Color.black);
        t.draw(sPath);
        t.setColor(Color.blue);
        t.draw(rPath);
        }
        g.setColor(Color.green);
        for(P p:path){g.fillOval((int)p.x-1, (int)p.y-1, 2, 2);}
    }
}

```

And the golfed version:

```
import java.awt.*;import java.awt.geom.*;import javax.swing.*;import static java.lang.Math.*;class Polygons2Golfed extends JPanel{public static void main(String[]a)throws Exception{new Polygons2Golfed(a);}double q=PI*2;int d=1;public Polygons2Golfed(String[]a)throws Exception{double b,c,f;b=Double.valueOf(a[1]);c=Double.valueOf(a[2]);int d,e;d=Integer.valueOf(a[3]);e=Integer.valueOf(a[4]);f=b+c+100;P o=new P(f,f);P r=new P(o.x,o.y-c-b);int s=0;for(double u=-q/4;u<q-q/4;u+=q/d){P p=new P(cos(u)*b+o.x,sin(u)*b+o.y);p.k=s;s++;l.add(p);}for(double u=q/4;u<q+q/4;u+=q/e){P p=new P(cos(u)*c+r.x,sin(u)*c+r.y);p.k=s;s++;k.add(p);}double g=q/e/2+q/d/2-.05;for(P p:k){p.r(v(0),g);}JFrame j=new JFrame();j.add(this);j.setSize((int)f*2+60,(int)f*2+60);j.setVisible(true);m=new int[]{l.get(0).k,k.get(0).k};int ad=1;P rc=k.c();P sc=l.c();double ab,ac;ab=atan2(rc.y-sc.y,rc.x-sc.x);ac=0;while(abs(ac)<Double.valueOf(a[0])*q){P rc2=k.c();P sc2=l.c();double ah=atan2(rc2.y-sc2.y,rc2.x-sc2.x);if(ab-ah<2)ac+=(ah-ab);ab=ah;L ag=(L)n.clone();ag.add(new P(k.get(1).x,k.get(1).y));n=ag;for(P p:k){p.r(v(m[ad]),.01);int af=l.size();for(int i=0;i<af;i++){P aa=l.get(i);P w=null;if(i==af-1){w=l.get(0);}else{w=l.get(i+1);}if(p.b(aa, w)==1&&w(p.k)==0){if(ad==1)ad=0;else ad=1;m[ad]=p.k;}int ae=k.size();for(int h=0;h<ae;h++){P u=null;if(h==ae-1)u=k.get(0);else u=k.get(h+1);if(aa.b(k.get(h),u)==1&&w(aa.k)==0){if(ad==1)ad=0;else ad=1;m[ad]=aa.k;}}}}repaint();Thread.sleep(5);}}L n=new L();L k=new L();L l=new L();P v(int key){for(P p:k){if(p.k==key)return p;}for(P p:l){if(p.k==key)return p;}return null;}int[]m;int w(int key){for(int i:m){if(key==i)return 1;}return 0;}@Override public void paintComponent(Graphics g){Path2D.Double aq=new Path2D.Double();aq.moveTo(l.get(0).x,l.get(0).y);for(P p:l){aq.lineTo(p.x, p.y);}aq.closePath();Path2D.Double aw=new Path2D.Double();aw.moveTo(k.get(0).x, k.get(0).y);for(P p:k){aw.lineTo(p.x, p.y);}aw.closePath();g.setColor(Color.white);g.fillRect(0,0,getWidth(),getHeight());Graphics2D t=(Graphics2D)g;if(d==1){t.setColor(Color.black);t.draw(aq);t.setColor(Color.blue);t.draw(aw);}g.setColor(Color.green);for(P p:n){g.fillOval((int)p.x-1,(int)p.y-1,2,2);}}}

```

As well as classes P:

```
import java.awt.geom.*;class P{double x,y;public P(double a,double b){x=a;y=b;}int k;void r(P c,double g){double a,r;a=Math.atan2(y-c.y,x-c.x)+g;r=Math.sqrt((c.x-x)*(c.x-x)+(c.y-y)*(c.y-y));x=Math.cos(a)*r+c.x;y=Math.sin(a)*r+c.y;}public int b(P a,P b){if(Line2D.ptSegDist(a.x,a.y,b.x,b.y,x,y)<.5)return 1;return 0;}}

```

And L:

```
import java.util.*;public class L extends ArrayList<P>{public P c(){double x,y;x=0;y=0;for(P p:this){x+=p.x;y+=p.y;}return new P(x/size(),y/size());}}

```

Change int d to 0 or 1 to show polygons

arguments - 1 100 50 5 2

args - 1.5 100 100 7 3

args - 2 40 100 3 7

# Answer
> 12 votes
# Javascript, 1284 chars (-200 = 1084 chars)

Minified code is

```
function epi(B,r2,r1,n2,n1){K=Math;function C(t){return K.cos(t)}function S(t){return K.sin(t)}function A(y,x){return K.atan2(y,x)}P=K.PI;v=[[],[]];w=[[],[]];z=[];function Z(x,y,j){c=C(t=f*H+P/2);s=S(t);v[j][n]=c*x-s*y;w[j][n]=s*x+c*y;}function E(i){return{x:r1*S(t=p-i*q),y:r1*C(t)};}function D(x,y,X,Y,t){L=A(m.y,m.x);M=K.sqrt(m.x*m.x+m.y*m.y);N=K.sqrt(X*X+Y*Y);O=~~(t*(M>N?M:N)+1);for(i=J;i<=O;i++){J=1;z[n]=f*H+P+t*i/O;Z(x+M*C(T=L+t*i/O),y+M*S(T),0);Z(x+N*C(T=A(Y,X)+t*i/O),y+N*S(T),1);n++}}function F(x,y,n,r,L,s){I.strokeStyle=s;I.beginPath();for(i=0;i<n;i++)I[i?'lineTo':'moveTo'](x+r*C(t=L+(1-2*i)*P/n),y+r*S(t)*W);I.closePath();I.stroke()}p=P/n1;q=2*p;u=P/n2;H=2*u;s2=r2*S(u);g=f=l=n=J=h=0;R=300;while(l<=(B*2+1)*P/H){o=E(0);m=E(h);m.y-=o.y;m.x-=o.x;if(g<s2){D(g,-r2*C(u),-o.x,-o.y,q);h=(h+1)%n1;g+=2*r1*S(p)}else{m.x+=g-s2;D(s2,-r2*C(u),-o.x+g-s2,-o.y,H);g-=s2*2;f=(f+1)%n2;l++}}return function(e_,t,aa,W_){W=aa?-1:1;I=(e=e_).getContext('2d');I.fillStyle='black';I.fillRect(0,0,600,600);W_&1&&F(R,R,n2,r2,0,'white');T=A(w[1][0],v[1][0]);U=V=0;I.strokeStyle='teal';I.beginPath();I.moveTo(R+v[0][0],R+w[0][0]*W);while(U<t){_=A(w[1][V+1],v[1][V+1]);U+=_-T+(_+1<T?2*P:0);T=_;V++;I.lineTo(R+v[0][V],R+w[0][V]*W)}W_&2&&I.stroke();W_&4&&F(R+v[1][V],R+w[1][V]*W,n1,r1,z[V],'red')}}

```

Full code is

```
function epi( nr, r2, r1, n2, n1 ) {
function C( t )
    { return Math.cos( t ); }
function S( t )
    { return Math.sin( t ); }
function A( dy, dx )
    { return Math.atan2( dy, dx ); }

var iCCW, e, t_, xs = [[],[]], ys = [[],[]], ts = [], n = 0, iArc0 = 0;

function addpt( x, y, iBin ) {
    var c_ = C(t_ = iFrame*t2 + Math.PI/2 ),
        s_ = S(t_);

    xs[iBin][n] = c_*x-s_*y;
    ys[iBin][n] = s_*x+c_*y;
}

function poly1pt( iP )
    { return { x: r1*S(t_ = t1b2-iP*t1), y: r1*C(t_) }; }

function arc1( P_Arc_, xP_, yP_, xC_, yC_, t ) {
    var dx_, dy_, dxC, dyC;
    var t0 = A( dy_ = P_Arc_.y, dx_ = P_Arc_.x ),
        r_ = Math.sqrt( dx_*dx_ + dy_*dy_ ),
        t0C = A( dyC = yC_, dxC = xC_ ),
        rC = Math.sqrt( dxC*dxC + dyC*dyC ),
        nt = ~~(t*(r_>rC?r_:rC)+1);

    for( var i = iArc0; i <= nt; i++ ) {
        iArc0 = 1;
        ts[n] = iFrame*t2 + Math.PI + t*i/nt;
        addpt( xP_ + r_*C(t_ = t0+t*i/nt), yP_ + r_*S(t_), 0 );
        addpt( xP_ + rC*C(t_ = t0C+t*i/nt), yP_ + rC*S(t_), 1 );
        n++;
    }
}

function poly( x,y, n, r, t0, sColor ) {
    var Cx = e.getContext('2d');
    Cx.strokeStyle = sColor;
    Cx.beginPath();
    for( var i = 0; i < n; i++ )
        Cx[i ? 'lineTo' : 'moveTo']( x + r*C(t_ = t0+(1-2*i)*Math.PI/n), y + r*S(t_)*iCCW );

    Cx.closePath();
    Cx.stroke();
}

var t1b2 = Math.PI/n1,
    t1 = 2*t1b2,
    t2b2 = Math.PI/n2,
    t2 = 2*t2b2,
    s1 = 2*r1*S(t1b2),
    s2 = 2*r2*S(t2b2),
    xPivot = 0,
    iPivot = 0,
    iFrame = 0,
    P_Pivot, P_Arc,
    nFrame = 0;

while( nFrame <= (nr*2+1)*Math.PI/t2 ) {
    P_Pivot = poly1pt( 0 );
    P_Arc = poly1pt( iPivot );
    if( xPivot < s2/2 ) {
        P_Arc.x -= P_Pivot.x;
        P_Arc.y -= P_Pivot.y;
        arc1( P_Arc, xPivot, -r2*C(t2b2), -P_Pivot.x, -P_Pivot.y, t1 );
        iPivot = (iPivot+1) %n1;
        xPivot += s1;
    } else {
        P_Arc.x -= (P_Pivot.x - (xPivot - s2/2));
        P_Arc.y -= P_Pivot.y;
        arc1( P_Arc, s2/2, -r2*C(t2b2), -P_Pivot.x + xPivot - s2/2, -P_Pivot.y, t2 );
        xPivot -= s2;
        iFrame = (iFrame+1) %n2;
        nFrame++;
    }
}

function renderTo( eCanvas, t, isCCW, sWhat ) {
    iCCW = isCCW ? -1 : 1;
    var Cx = (e = eCanvas).getContext('2d');
    Cx.fillStyle = 'black';
    Cx.fillRect( 0,0, 600,600 );

    if( sWhat &1 )
        poly( 300,300, n2, r2, 0, 'white' );

    var tRef = A( ys[1][0], xs[1][0] ),
        tCum = 0,
        i0 = 0;

    Cx.strokeStyle = 'green';
    Cx.beginPath();
    Cx.moveTo( 300+xs[0][0], 300+ys[0][0]*iCCW );
    while( tCum < t ) {
        t_ = A( ys[1][i0+1], xs[1][i0+1] );
        tCum += t_ - tRef + (t_ - tRef < -1 ? 2*Math.PI : 0);
        tRef = t_;
        i0++;
        Cx.lineTo( 300+xs[0][i0], 300+ys[0][i0]*iCCW );
    }
    if( sWhat &2 )
        Cx.stroke();
    if( sWhat &4 )
        poly( 300+xs[1][i0], 300+ys[1][i0]*iCCW, n1, r1, ts[i0], 'red' );
}

return renderTo;
}

```

A fiddle to behold the routine in all its polygony glory (and to demonstrate animation) is found at

http://jsfiddle.net/7rv751jy/2/embedded/result/

The script defines a function called `epi` that accepts the five listed parameters in the OP. `epi` returns a function with the signature `(e,t,isCCW,flags)` which accepts arguments:

* `e` \- a reference to a 600x600 HTML5 canvas element on which to render
* `t` \- the total angle (in radians) that the centroid of the second polygon should sweep around the centroid of the first. The argument passed in should not exceed 2 pi times the number of rotations passed to `epi`.
* `isCCW` \- boolean indicating whether the trace should proceed in a counterclockwise direction (as opposed to a clockwise one)
* `flags` \- a set of bit flags indicating which elements should be rendered
    + bit 1 - render polygon 1 if set
    + bit 2 - render trace if set
    + bit 3 - render polygon 2 if set

The function can be called any number of times with varying sets of arguments.

**Some Notes:**

* The routine handles the degenerate cases where `n1 = 2` and/or `n2 = 2`. When animating, certain combinations of lengths will cause sudden rapid advances in the trace. This is because the animation frames are indexed by the angle to the centroid of the second polygon, and d theta poly2 / d theta centroid becomes singular in cases where the centroid of 2-sided poly 2 is near a vertex of 2-sided poly 1. This does not affect the trace, however.
* The parameter names in `epi` will seem confusing since throughout development, I referred to polygon 1 as "2", and polygon 2 as "1". When I realized the inconsistency between my convention and that of the OP, rather than swapping all of the indices in the code, I simply swapped the order of the arguments in `epi`.
* The fiddle above imports jQuery, but this is to handle the UI. The `epi` function has no library dependencies.
* The code handles CCW traces by simply inverting the Y axis. This is somewhat inelegant since polygon 2 starts in a Y-inverted position during CCW traces, but nobody said the routine had to be elegant. ;)

---
Tags: code-golf, graphical-output, geometry
---


# Question
Title: Put together cut strips of paper to get original message
This question is from a programming challenge (not DARPA) which has ended. A sheet of paper consists of message, which has been shredded into vertical strips. Given the vertical strips and a dictionary of valid words, the goal is to put together the original message.

The vertical strips contain only one character from a line. The input to the program is the number of vertical strips (N), number of lines in the original message (K) and a string containing the characters in each vertical strip. Then the number of words in the dictionary and the list of valid words.

**EXAMPLE INPUT**

```
10
3
"MrM"
"ak "
"Gaa"
"oM "
" d "
"t 3"
" aP"
"nt "
"ont"
"ie "
15
1
2
3
4
5
AND
AM
AT
GO
IN
Main
Market
ON
PM
TO

```

**OUTPUT**

```
Go to Main
and Market
at 3 PM

```

**Description of the input above**
`10` \- number of vertical strips
`3` \- number of lines in the original message corresponds to number of characters in each string of the veritcal strips
*{actual strings}* \- pay careful attention to spaces in strings
`15` \- number of words in the dictionary
*{valid words}*

I was able to create a map of characters -\> count of each character, for each line from the vertical strips. Then parsing the dictionary and looking at the character map, you can recreate words in each line. Looks like finding the order of words is the difficult problem. What is the best approach to finding the correct message?

# Answer
## Python 3 - Trie and DFS

Trie is a tree shape data structure. If we build a trie from a collection of words, then each path from the root to a leaf node will represent a word from the collection.

To solve this problem, first we build a trie using the valid words. Suppose the original text has `n` rows and `m` columns, then we will have `m` strips to put together. We try to reconstruct the original text from left to right, column by column, using a recursive depth-first search. To perform branch elimination, we also maintain a list of heads on the trie, name it `heads`. Each head points to a node on the trie and point to the root at first. We will need `n` heads, each correspond to a row. Each time after a column(`strip`) is appended, `heads[i]` will be moved according to the character `strip[i]`. If we found any head that cannot be moved, then we know the column just appended is incorrect. After putting `m` columns, we get the original text.

I implemented this algorithm using Python. It is fast enough to solve a 40x80 case with 10000 valid word in instant.

I use this python 3 script to generate test cases. Run it with:

```
python3 make_script.py {dict path} {n rows} {n cols} > intput.txt

```

The following is a 40 x 80 case. The dictionary file can be found here, which has 10000 words.

```
80
40
c el efp e otl  desaiweseeme  jomp ebc g
synwds  irnsatseityl rkutpsiysei ssraat
gvmjewrell fclpadrll nbsvwiwteqdeniditba
uet criderndm eesih dalbrcra d iacnnoi e
lbipoeivedrwddivensne aeihrpaa eicangpni
 gontgtulvcbatdo glunsniiguoleu eigtbelh
xmsyyu ereio edvrttdonure tpselriniipnxs
ssdieop bgkg  wu  eloyr dllrhza t hic af
rttruminetnt rcu rasa ogosrywrnietvldgod
lpe aritour alolt yeomlpimmxryftenen  sn
cneregsc igodbsigeca r kbhiiisoss eagglp
crm nhdreh raokdtr rcfiotpsfgtjanotaaiaf
s pntenpnmv plemiaaxeeittgtg ncnaooaou a
srrganeu ut toaantetedccnr seiise eur ni
 xpndg psafl ooemlusof nba pauosina esnb
ge du  tbfe  spuoeuesen o s um ldsted  w
eto rs l nhuc caexr bsoptwcrrnaennrasary
e  maldneg nep nmaid isie ko ctedh necaa
esoeisi u ifran  rgirrts ntipuneccnvftrp
gui oeriwraisc og vsepharn latotts aenra
eenylorobneyrem nwtefrasdeoeet ot  osdsr
abia e i iwrcneaaiaeeu lie oihotgdicntdi
euugmjsdfcamazndei e yoagaserxatrultoaio
tamdfesgtitc xseuegs  fene thatfueo l ut
ocn sdrtn mai aerwmimoss te  oceorrit el
netbu wymsrfobelltemetrisioao uri  l ce
deaa ee e aadrgcoln cnto semroi  ofdnanu
aeaunrmvonirieaxapicnaioxaoromeviiuaeoou
 oaodtb hpretdarie n e recei etunsrsedal
ejht n jy ees tnr gsegr s  e jhb ayegup
ohids bi g iesiogs rytimtorrsab pnirwlc
ieuereaklieapeatlan sdeeg e lasedaob  be
rihbegaisvdtrprnatservaraco na imtcgplna
denrdnnelymisenimi gnfw bssalupcnansu et
itsrwnbeclwfmstasg craaim ei  atrifvpr
ubksogxernu auletinieo krte cgmltiliioir
atnhndcutigiasuir ntsaiauem usiireg idms
yniis ssle aisicsngqseazdifiertercaauvoc
ds prcatnoiaafsiopiratdrrmksnfidakr  gon
p ngaoolyeolg nep oae dnsnln srfcontsrve
boges massscgss arsobod ierseh rnivtagsp
nlstadhndnroieecntc slhoucbrcouo uohtiis
ltainnpif nfrn tinrdoi ninsanteu n   aeb
oun htoioaftupedsmowtmeatanyi sltnh ftto
a emgrasancass oelrefddy alacinsut n s
kgttnltednrmea t yhug welentn tu fsneeah
yia bilgwybnisgfrmidlh t rssnaiultgagk a
  iaeeorega sdbhc otadiresdagcipcuet rde
tygui artnsot le wtes etrracm pde oev e
cvrpsabemddamylpeiscdmktpnnolbsesardlwro
rnirmestiwntlrfresosedlvshydrsrrucnntr a
nans hinslmoxenfeolo cxeeneosgrphantiuyg
m dans llnrtlav ensptun acfaev s gtesfad
litl gonungirgk pioeutvinsstgintpsmbrdsu
altpjretooode rtnseeyepdrotllxric s rice
aikaunnskdoh agtnl cuegoacwhnsx esrurgg
ef drant  rsaaeymreleiiessmniesdoeeroeer
eereozurmoicueeegtcolbeioteodocrsnaeaatt
 h cre g  snsihssatlunisi odeelcpminoeba
oisstnirhpmnaybaertcnenhdnondsunaaprlipr
vetou egriemerpicacb  ygmiaw rrrocnisecm
ibs tara  neeiaqlbbtsgegcs sooeoeuel ten
blrkqaiacortqmn ien ylrrrnecieircs qeind
en s e ieu cnaiscikuirocnr hlnpfjooimohs
dctlehtr ntlgpddeoipmog elllrnncnkgcseeu
o  aaet henyaue mbntgeeselsws   mmawnwve
lns e xoorail yn  eesnee uctaud nrasenha
swydiecacaefolsenmttnsoer ohmahttpt radc
yvltaxin pgrauluktystkmot mrf aluuiepl
b sea usksoim hr idhtttd e owrn cnferevc
lstsibaocesfsmbejsdaellmepmbdedoffdbrtmq
axou nlnae ise gn esse  ihbstgsfmeteestf
yeaasra oopaeaildkiynteteidilnuenec vral
msylcdecsy  lkgr  icdkxrmie strle fei sz
 rdae gde al ngswsc soaru  tlsrtg durfne
 rrpodl i asg  essvuo aeaaheenaloe  geru
grus nbrls eqme ydioradhsoolmdiouoggnssv
 tfirotrkdnnnrtmwenan   abs cfcigscmpsed
 a soteiicdero nsaeuisrmisntau iirammlyi
anroiim tsiiaarrhoyaimdo oera dblogysmr

```

Solved:

```
lacerated deliberateness canvas gould scold sexually piggyback obey agrimony moe
seventy except fixates warble shrubbery instrumenting beveling convolute hairs j
tarring aptness homotopy misted unkindness frustrations marketing latitudinary h
superhumanly redbud bends atomics sprawls piggy oiling djakarta estop reads plat
insomnia delaware fruition auger hooded terramycin statuesqueness adjourns boca
brazed leghorn agnes seethed roentgen sen conjuring goa wrangled extremes hidden
ambuscade tribunals winced heap boxing fixates impostor rainstorm iberia billet
overturn protestingly pairings grieved protruded insulate ascertain tinkling c j
committees bock sat muncie drab lorelei honk fretfully block dense howell swishy
endowing annuls veins machining sandy reproducers neve flooding supportingly ye
sidings afterword thrived wrecks furman maintaining cone programs groaner mba ne
fractionally fisticuff ferromagnet wilsonian modifiable fathom accreditations ye
simulated grammars corporacies squads atalanta marriage ceq designates plexiglas
meyers propels apex ballooners impudently froze angst islamabad saud creases ku
baleful godmother scenes keep wheelings bystander kidnappings basilar caving get
experienced laryngeal mendacious devise animadvert coequal tithe surtout offer n
jaeger moments manuel instance systemwide ownerships plodding cracking legers mr
spits wallow girt extramarital administer petitioning berkeley writes ransoms b
discontinuity desegregate accretions cysteine thyroglobulin chomsky evans living
accosted speechless mixture bellowing lacerated adequately cautiousness products
endless comforters berenices fourteens insane odiousness nyu gambit yeasty lodge
lambda informative stressful dynamo forwent dynamites gentler doorkeep dutch keg
likeliest galatia fortiori hydride awakened could vandenberg wisdom phoenix axer
motivation spider epistemology shake rusher carbonizing strokers cordage meters
exposure bedim saints tritium distributed ranger indiscoverable interrogate ames
panther salem eschewing special oaths penumbra consigns winchester cons conrail
moneymake lome mob cottons ballooners smocks stressful sidewinder met refreshes
brood complexion straightforwardly patients separations wichita shrilly arose we
doldrum rarer winthrop magic chemically dancers angel outlining elf lawlessness
emboss county reagan unauthorized gauss suffixed tiresomeness cohn extravagant j
description fans staunch journalism prejudicial denture quixotic patrons briar h
override scott differentiators collection distribute folder superfluities pull b
fissured intercommunicating outputting managerial precedences conjuncted phloem
fiance honk nineteen coproduct monica sparks unconsciousness furious stagnate ma
durango fag effector notation highlands parceling magnetic reservoirs voting fay
baden end converge alva machining insurers mutiny battled quantities alberta ewe
relativeness propels formants configurable propos rubs diverge tampered swigging
toward cased reels actualities estop facings animadvert trigger golding fluke wu
mort meanness venturer dyadic abstinent phoenix resolve bangladesh acrobacy rsvp
quotas auburn crafty pacifism favorite grandiose buchenwald phelps leaded gauze

```

### Code

```
def build_trie(words):
    root = {}
    for word in words:
        node = root
        for c in word:
            if c in node:
                node1 = node[c]
            else:
                node1 = node[c] = {}
            node = node1
    return root

def search_origins(root, strips):
    n_rows = len(strips[0])
    n_cols = len(strips)
    ordered = [None] * n_cols
    heads = [root] * n_rows
    used = set()

    def get_next(node, c):
        if c == ' ':
            return root
        return node.get(c, None)

    def search(col_id, heads):
        if col_id == n_cols:
            yield transpose(ordered)
            return
        for i in range(n_cols):
            if i in used:
                continue
            heads1 = [get_next(head, c) for c, head in zip(strips[i].lower(), heads)]
            if any(x is None for x in heads1):
                continue
            used.add(i)
            ordered[col_id] = strips[i]
            yield from search(col_id + 1, heads1)
            used.remove(i)
    yield from search(0, heads)

def transpose(cols):
    return '\n'.join(map(''.join, zip(*cols)))

def parse():
    m = int(input())
    n = int(input())
    strips = []
    for i in range(m):
        strip = input()
        if strip[0] == '"':
            strip = strip[1:1 + n]
        strips.append(strip)
    n_words = input()
    if n_words:
        words = [input() for _ in range(int(n_words))]
    else:
        dict_path = input()
        words = list(map(str.rstrip, open(dict_path)))
    return words, strips

def main():
    words, strips = parse()
    words = list(map(str.lower, words))
    # print(words, strips)
    root = build_trie(words)
    for i, result in enumerate(search_origins(root, strips)):
        print('#{}{}'.format(i, '-' * 80))
        print(result)
        # Uncomment next line if you want only one result
        # break

if __name__ == '__main__':
    main()

```
> 5 votes

# Answer
**Groovy 311**

```
i=(args[0]as File).readLines()
(a,b)=i[0..1]*.toShort()
j=2
s=[]
a.times{s<<i[j++]-'"'-'"'}
d=[]
i[j++].toLong().times{d<<i[j++].toLowerCase()}
f={(0..<b).collect{c->it.collect{it[c]}.join()}.join("\n")}
o=0;l=0
z=s.permutations().each{x=f(it);c=d.count{x.toLowerCase().contains(it)};if(c>l){l=c;o=x}}
print o

```

let's start the bidding and just go brute force; return the first result with the most matches against the dictionary by checking all permutations

Here is a shorter example `helloworld.txt`

```
5
2
"HW"
"eo"
"lr"
"ll"
"od"
2
hello
world

```

run as

```
% groovy destriper.groovy helloworld.txt

```
> 0 votes

---
Tags: code-golf, string
---


title: Decipher a Code Stick

text:
# Question
Title: Decipher a Code Stick
## Introduction

You're an American spy during the heat of the Cold War and you've managed to intercept a Russian message. Immediately you recognise it as a code stick cipher and wrap it around a pencil. Looking at the paper on the pencil, you don't see anything. Then you try a bigger pencil, and you see it.

## Challenge

You have to write a program that deciphers a code stick. As this is code golf, the shortest program wins.

You may use any English dictionaries for looking up words. Some examples of dictionaries include:

* Querying a text file of words
* Using an inbuilt OS dictionary
* Querying an online dictionary (screen scraping etc.)
* Using an external lib

### All words MUST be valid English words

## Your pencils

Each of your pencils has four equally sized faces and are infinitely long. You have five differently sized pencils:

```
Pencil 1: Shows 1 character on each face
Pencil 2: Shows 2 characters on each face
Pencil 3: Shows 4 characters on each face
Pencil 4: Shows 6 characters on each face
Pencil 5: Shows 8 characters on each face

```

All ciphers can be deciphered by placing the start of the paper at the top of the pencil and wrapping it down.

## Examples

The following is an example of a cipher:

```
Hepoge slljghadso bvvbgh

```

This can be deciphered by wrapping it around Pencil 2:

```
Side 1 | Side 2 | Side 3 | Side 4
-------+--------+--------+-------
He     | po     | ge     |  s
ll     | jg     | ha     | ds
o      | bv     | vb     | gh

```

So now you have four combinations:

```
Hello , pojgbv, gehavb,  sdsgh

```

You can now perform a dictionary lookup and see that `Hello` is the only valid word. Therefore, `Hello` is the cracked cipher.

***Note:*** Deciphered codes may have spaces in. Example: `Hello World`

## Test cases

Ciphers can be inputted in any way apart from being hardcoded. The following are a few test cases. You **will not** be given the pencil size.

```
boasonespetrabbittonespongomezesray long
lsbvmii derfghthstthasinlomnrtk fg dndthugssawerpoloasefnxafqeormnaqwge padhndi mbavwgam
lipois lisptloopoolsisp lortfippinglthe asse rtedgoodcodeis the best  of enlymoolfangthe  leamingsoulsgodsingering
antidisebd sldkfdw sld sja dmddystablishjzkapxmjhavzlx dld slzbfmentariabahdjdlljagzlxbxlffnd ldnism is hdbsh spjalcpdhstd flcnda very cbd skd alsbfo kfvwfd xlconvolutehs ska ckw dlc fjzlxbckxd word  hs sla k dk skdnlcjcu dk

```

Any more test cases would be appreciated

### Answers to the test cases

> **1:** astronomy
> **2:** i think therefore i am
> **3:** is lisp the code of the gods
> **4:** antidisestablishmentarianism is a very convoluted word

### Script to generate code stick ciphers:

```
import string, random, math

word = input('Word:\t')
n = int(input('Pencil:\t'))
pencil = int(-((4*(17*n-77))/((n**4)-(19*n**3)+(136*n**2)-(444*n)+566)))

alpha = string.ascii_lowercase+' '
cipher = ''

side = random.randint(1, 4)
sides =['','','','']

for j in range(len(sides)):
    if j+1 == side:
        sides[j] = word
        if len(word)%pencil != 0:
            sides[j] += ' '*(len(word)%pencil)
    else:
        for k in range(math.ceil(len(word)+(len(word)%pencil))):
              sides[j]+=random.choice(alpha)

for l in range(0, math.ceil(len(word)/pencil)*pencil, pencil):
    for m in sides:
        cipher += m[l:l+pencil]

print('Cipher:\t'+cipher)
print('Side:\t'+str(side))

```

# Answer
# Python - ~~219~~ ~~178~~ ~~172~~ 175

First crack at it. I'm sure there's room for improvement.

**edit1: After suggestions, and copying words file to local file named 'w'**
**edit2: Fixed a bug where it wasn't using the right number of letters per side. Added 3 chars :(**

```
r=range
s=raw_input()
print[a for a in(''.join(s[m:m+n]for m in r(o*n,len(s),4*n))for o in r(4)for n in(1,2,4,6,8))if not set(a.lower().split())-set(map(str.strip,open('w')))]

```
> 2 votes

# Answer
# Mathematica ~~270 230~~ 251

---

This now requires that all parsed words be found in a dictionary.

```
f@q_:=
Module[{c=Characters@q,wd,u=DictionaryLookup},
j@d_:=Union[u@d,u[ToLowerCase@d],WordData@d];
Flatten@Select[Flatten[Table[
StringSplit[""<>Flatten@#]&/@Transpose@ArrayReshape[c,{Round[Length@c/(4 m)],4,m},""],{m,{1,2,4,6,8}}],1],!MemberQ[j/@#,{}]&]]

```

**Test Cases**

```
f["boasonespetrabbittonespongomezesray long"]
f["Hepoge slljghadso bvvbgh"]
f["lsbvmii derfghthstthasinlomnrtk fg dndthugssawerpoloasefnxafqeormnaqwge padhndi mbavwgam"]

```

> {"astronomy"}
> {"Hello"}
> {"i", "think", "therefore", "i", "am"}
> 1 votes

---
Tags: code-golf
---


title: Family Tree Solver

text:
# Question
Title: Family Tree Solver
*This is one of several challenges left for the community by Calvin's Hobbies.*

Take a "family tree describing" file with lines of the form:

```
[ID] [mother ID] [father ID] [gender] [full name]

```

such as this which describes the first family tree at http://en.wikipedia.org/wiki/Cousin:

```
1 ? ? M Adam
2 ? ? F Agatha
3 ? ? M Bill
4 2 1 F Betty
5 2 1 M Charles
6 ? ? F Corinda
7 3 4 M David
8 6 5 F Emma

```

Write a program or function that takes in the file name and two IDs and outputs how those people are blood-related in simplest terms, using the common English names for relations. Input may be via STDIN, ARGV or function arguments but output should be to STDOUT.

## Notes

* IDs are positive integers.
* `?` is used when parentage is not known.
* Assume the graph will be connected and has no cycles.
* You may *not* assume that each person's parents are listed before that person (so a person's parent ID could be greater than their own ID).
* Assume everyone is either male or female and everyone has exactly one mother and exactly one father (of correct gender), although they might be unknown.
* Assume names are unique.
* Names can have spaces in them.

## Blood relations

The following definitions of relationships *R* determine if person *A* is the *R* or person *B*. If two variants of *R* are listed, the first is for female *A* and the second for male *A*. All of these need to be implemented. If multiple definitions match, the earlier one is to be used. Terms in parentheses are gender-neutral terms, which do not need to be implemented but will be reused in further definitions. In definitions involving *N* and *M*, assume *N \> 1* and *M \> 0*.

* daughter/son: *A* lists *B* as either parent.
* mother/father (parent): *B* lists *A* as either parent.
* sister/brother (sibling): *A* and *B* list the same mother *and* father.
* half-sister/half-brother (sibling): *A* and *B* list the same mother **or** the same father.
* niece/nephew: *A* lists a parent who is the sibling of *B*.
* aunt/uncle: *B* is *A*'s niece or nephew.
* granddaughter/grandson (grandchild): *A* lists a parent who lists *B* as their parent.
* grandmother/grandfather (grandparent): *B* is *A*'s grandchild.
* great-niece/great-nephew: *A* is the grandchild of *C* who is the sibling of *B*.
* great-aunt/great-uncle: *B* is *A*'s great-niece or great-nephew.
* great-granddaughter/son (1st great-grandchild): *A* is a grandchild of *C* who lists *B* as their parent.
* great-grandmother/father (1st great-grandparent): *B* is *A*'s 1st great-grandchild.
* Nth great-granddaughter/son (Nth great-grandchild): *A* is an (N-1)th grandchild of *C* who lists *B* as their parent.
* Nth great-grandmother/father (Nth great-grandparent): *B* is *A*'s Nth great-grandchild.
* Nth great-niece/nephew: *A* is the (N-1)th great-grandchild of *C* who is the sibling of *B*.
* Nth great-aunt/uncle: *B* is *A*'s Nth great-niece of Nth great-nephew.
* cousin: *A* is the grandchild of *C* who is the grandparent of *B*.
* Nth cousin: *A* is the (N-1)th grandchild of *C* who is the (N-1)th grandparent of *B*.
* cousin, M times removed: *A* is the grandchild of *C* who is the Mth grandparent of *B* **or** *A* is the Mth grandchild of *C* who is the grandparent of *B* .
* Nth cousin, M times removed: *A* is the Pth great-grandchild of *C* who is the Qth great-grandparent of *B*, where `N = min(P,Q) + 1` and `M = |P-Q|`.

For `Nth`, write `2nd`, `3rd`, `4th`, `5th` etc.

For `M times`, write `once`, `twice`, `thrice`, `4 times`, `5 times` etc.

## Examples

Assume the following file is used (you don't have to be able to deal with multiple spaces, but I added them for legibility):

```
 1  ?  ? F Agatha
 2  ?  ? M Adam
 3  ?  ? F Betty
 4  1  2 M Bertrand
 5  1  2 F Charlotte
 6  ?  ? M Carl
 7  ?  ? F Daisy
 8  3  4 M David
 9  5  6 F Emma
10  ?  ? M Edward
11  ?  ? F Freya
12  7  8 M Fred
13  9 10 F Grace
14  ?  ? M Gerald
15  ?  ? F Hillary
16 11 12 M Herbert
17 13 14 F Jane
18  ?  ? M James
19 15 16 F Kate
20 17 18 M Larry
21  ? 18 F Mary

```

Then input IDs should map to outputs as follows:

```
 1  2 --> Agatha is not a blood relative to Adam.
 8  3 --> David is the son of Betty.
 9 13 --> Emma is the mother of Grace.
 4  5 --> Bertrand is the brother of Charlotte.
 9  4 --> Emma is the niece of Bertrand.
 5  8 --> Charlotte is the aunt of David.
16  7 --> Herbert is the grandson of Daisy.
 1  9 --> Agatha is the grandmother Emma.
12  5 --> Fred is the great-nephew of Charlotte.
 4 13 --> Bertrand is the great-uncle of Grace.
16  3 --> Herbert is the great-grandson of Betty.
 6 17 --> Carl is the great-grandfather of Jane.
19  2 --> Kate is the 3rd great-granddaughter of Adam.
 1 17 --> Agatha is the 2nd great-grandmother of Jane.
20  4 --> Larry is the 3rd great-nephew of Bertrand.
 5 16 --> Charlotte is the 2nd great-aunt of Herbert.
 8  9 --> David is the cousin of Emma.
19 20 --> Kate is the 4th cousin of Larry.
16  9 --> Herbert is the cousin, twice removed, of Emma.
12 17 --> Fred is the 2nd cousin, once removed, of Jane.
21 20 --> Mary is the half-sister of Larry.

```

I wrote those up by hand so let me know if you spot any mistakes.

*Another set of test data (provided by Scott Leadley, any errors are mine and not Martin's)*
Ptolemy family tree
The picture is illustrative; the data below comes from the Wikipedia article "Ptolemaic dynasty".

```
 1  ?  ? F Berenice I of Egypt
 2  ?  ? M Ptolemy I Soter
41  1  2 F Arsinoe II of Egypt
 3  1  2 M Ptolemy II Philadelphus
 4  ?  ? F Arsinoe I of Egypt
 5  ?  ? M Philip
 6  4  3 M Ptolemy III Euergetes
 7  1  5 F Magas of Cyrene
 8  7  ? F Berenice II
 9  8  6 M Ptolemy IV Philopator
10  8  6 F Arsinoe III of Egypt
11 10  9 M Ptolemy V Epiphanes
12  ?  ? F Cleopatra I of Egypt
13 12 11 M Ptolemy VI Philometor
14 12 11 F Cleopatra II
15 12 11 M Ptolemy VIII Physcon
19  ?  ? F Eirene
16 14 13 M Ptolemy VII Neos Philopator
17 14 13 F Cleopatra III
18 14 15 M Ptolemy Memphites
20 19 15 M Ptolemy Apion
21 17 15 F Cleopatra IV
22 17 15 M Ptolemy IX Lathyros
23 17 15 F Cleopatra Selene I
24 17 15 M Ptolemy X Alexander I
25 23 22 F Berenice III of Egypt
26 23 24 M Ptolemy XI Alexander II
27 21 22 M Ptolemy XII Auletes
28 25 24 F Cleopatra V of Egypt
29 28 27 F Cleopatra VI of Egypt
30 28 27 F Berenice IV of Egypt
31 28 27 M Ptolemy XIII Theos Philopator
32 28 27 F Cleopatra VII Thea Philopator
33 28 27 M Ptolemy XIV
34 28 27 F Arsinoe IV of Egypt
35  ?  ? M Julius Caesar
37 32 35 M Ptolemy XV Caesarion
36  ?  ? M Mark Anthony
38 32 36 M Alexander Helios
39 32 36 M Ptolemy XVI Philadelphus
40 32 36 F Cleopatra Selene II

```

# Answer
# ECMAScript 6, 886

Division by zero is a wonderful thing.

This uses quasi-literals once (which are not implemented in Firefox 33 or node.js, but *are* available in the nightly builds of Firefox). The quasi literal used:

```
`
`

```

may be replaced with `"\n"` if whatever you are using lacks support for these.

This script constructs a tree from the list of people, storing both parents and children. Every path from person A to person B is tried, and the optimal path is saved. A path is considered valid if it only changes from going up to going down the tree once. The opposite change is not allowed - if one needs to go down to a children and back up to another parent in order to find a path, the two people are not blood relatives. (`UUUUUDDD` is valid, `UUDUUU` is not. `U` means go up (to a parent), `D` means go down (to a child)).

Sort of golfed:

```
R=(a,b)=>{F="forEach",C='';p=[],g=[],c={},n=[],e=m=1/0;y=i=>i+(k=i%10,k&&k<4&&~~(i%100/10)-1?[,'st ','nd ','rd '][k]:'th ');q=(a,b,s,$)=>!($=$.slice())|!a|~$.indexOf(a)||a-b&&$.push(a)|[p,c][F]((M,N)=>M[a][F](j=>q(j,b,s+N,$)))||(z=(s.match(/0/g)||[]).length,r=s.length-z,_=e+m-z-r,s.indexOf(10)<0&_>0|!_&m>r&&(e=z,m=r));I.split(`
`)[F](V=>{P=V.split(' ');D=+P[0];p[D]=[+P[1],+P[2]];g[D]=P[3]<'L';n[D]=P.slice(4).join(' ');c[D]=[]});p[F]((V,I)=>V[F](Y=>Y&&c[Y].push(I)));q(a,b,C,[]);U=e>m?m:e,V=e>m?e:m;alert(n[a]+' is '+(e/m+1?'the '+(U*V---1?U<2?(V<3?C:y(V-1))+(V<2?C:'great-')+(V*!U?'grand':C)+'son0father0nephew0uncle0daughter0mother0niece0aunt'.split(0)[g[a]*4+2*U+(U==e)]:(V-=--U,(U<2?C:y(U))+'cousin'+(V?', '+(V>3?V+' times':[,'on','twi','thri'][V]+'ce')+' removed,':C)):(p[a].join()==p[b].join()?C:'half-')+(g[a]?'sister':'brother'))+' of ':'not a blood relative to ')+n[b]+'.')}

```

Ungolfed (kind of):

```
// function for running.
R=(a,b)=>{
F="forEach",C='';
p=[], g=[], c={}, n=[], e=m=1/0;
// returns suffixed number (1->1st, 2->2nd, etc)
y= i=>i+(k=i%10,k&&k<4&&~~(i%100/10)-1?[,'st ','nd ','rd '][k]:'th ');
// this looks for the shortest path up/down the family tree between a and b.
q=(a,b,s,$)=>
  // copy the array of visited people
  !($=$.slice())
  // check if a is invalid
  | !a
  // check to make sure we are not visiting a for a second time
  | ~$.indexOf(a)
  // if a != b
  || a-b
  // add a to visited, and call q(...) on all parents and children
  && $.push(a) |
   [p,c][F]((M,N)=>M[a][F](j=>q(j,b,s+N,$)))
  || (
    // a == b
    // get number of ups and downs
    z=(s.match(/0/g)||[]).length,
    r=s.length-z,

    _=e+m-z-r,
    // if DU: path is invalid.
    // if _>0: path is shorter
    // if _==0: check m > r to see if new path should replace old
    s.indexOf(10)<0 & _>0|!_&m>r && (e=z,m=r));
// load list of people into arrays
I.split(`
`)[F](V=>{
  P=V.split(' ');
  // ID
  D=+P[0];
  // parents: NaN if not given
  p[D]=[+P[1],+P[2]];
  // gender: 1 if female, 0 if male
  g[D]=P[3]<'L';
  // merge the rest of the array to get name
  n[D]=P.slice(4).join(' ');
  // empty children array..for now
  c[D]=[]
});
// push current ID to parents' children array.
p[F]((V,I)=>V[F](Y=>Y&&c[Y].push(I)));

// get shortest path
q(a,b,C,[]);

U=e>m?m:e,V=e>m?e:m;
G=(a,b,c,d)=>(a<3?C:y(a-1))+(a<2?C:'great-')+(a*!b?'grand':C)+'son0father0nephew0uncle0daughter0mother0niece0aunt'.split(0)[g[d]*4+2*b+(b==c)];

// output
alert(n[a]+' is '+(e/m+1?'the '+(U*V---1?
    U<2?
        G(V,U,e,a)
    :(V-=--U,
     (U<2?C:y(U))+'cousin'+
     (V?
        ', '+(V>3?V+' times':[,'on','twi','thri'][V]+'ce')+' removed,'
     :C)
     )
:(p[a].join()==p[b].join()?C:'half-')+(g[a]?'sister':'brother'))+' of ':'not a blood relative to ')+n[b]+'.')
}

```

Notes:

* List of people should be placed in a variable `I` (as a string, with single spaces and newlines).
* To call: `R(a,b)`, where `a` and `b` are the IDs of the two people being compared.
> 3 votes

# Answer
# Cobra - 932

Out of all the challenges I've answered in Cobra, this is by far one of the best examples of what it can do.

EDIT: It's now a function, but must be prefixed by the signature for Z (included in char count).

```
sig Z(m,n=nil,r=nil)as String?
def f(f='',u='',v='')
    d={:}
    for l in File.readAllLines(f)
        w=l.trim.split
        i,j,k,p=w[:4]
        q=w[4:].join(' ')
        if i==u,x,g=q,if(p<'M',1,0)
        if i==v,y=q
        d.add(i,[j,k])
    o as Z=do(n,m,r)=if(n>1,"[n][if(0<n%10<4and not 10<n%100<14,'stndrd'[n%10-1:n%10+2],'th')] ",'')
    z as Z=do(m,n,r)
        h,a,b=n
        if m[0]==m[1]
            if if(b<1or 0<b<3and a>b,s=2,s=0),a,b=b,a
            r="the [if(a,if(a<2,if(b<2,if(not'?'in'[c=d[u]][e=d[v]]'and c==e,'','half-')+['brother','sister'][g],if(b<3,'',o(b-2)+'great-')+['uncle','aunt','nephew','neice'][s+g]),o(a-1)+'cousin'+if(b>a,', '+if((b-=a)<4,['on','twi','thri'][b-1]+'ce','[b] times')+' removed,','')),if(b,if(b<3,'',o(b-2)+'great-')+'grand','')+['father','mother','son','daughter'][s+g])] of"
        for t in d[m[h]],if'?'<>h,r?=if(h,z([m[0],t],[1,a,b+1]),z(m,[1,a,0])?z([t,v],[0,a+1,0]))
        return r to String?
    print x+" is [z([u,v],[0,0,0])?'not a blood relative to'] [y]."

```

Commented: (out of date, but still the same code-flow)

```
class F
    # Initilaise link dict
    var d={'?':@[''][:0]}
    # Gender bool
    var g
    def main
        # Initilaise name dict
        d={'?':@[''][:0]}
        # Take args
        f,a,b=CobraCore.commandLineArgs[1:]
        # For line in file
        for l in File.readAllLines(f)
            # Split line
            i=l.split
            # Add links to link dict
            .d.add(i[0],i[1:3])
            # Add names to name dict
            d.add(i[0],i[3:])
        # Get gender
        .g=if(d[a][0]=='F',1,0)
        # Print result
        print _
            '[d[a][1]] is '+ _ # Name A
                .r(@[1,0,0],@[a,a,b,b]) _ # If link found, link
                ? _ # Else
                'not a blood relative'+ _ # Not related
            ' of [d[b][1]].' # Name B
    def r(n as int[],m as String[])as String?
        # Recurse through the links at each level from A (A1), climbing when no links are found to B
        # For each level incremented for A, search upwards to the end of all nodes from B (B1), looking for A1
        r=nil
        # Check if we're done searching/climbing
        if m[1]==m[2]
            a,b=n[1:]
            s=if(b<1or b in[1,2]and a>b,1,0)
            if s,a,b=b,a
            # Take the A and B distance and translate them into a phrase
            return'the '+ _
                if(a, _
                    if(a<2, _
                        if(b<2, _
                            if('?'not in'[.d[m[0]]][.d[m[3]]]'and.d[m[0]]==.d[m[3]], _
                                '', _
                                'half-' _
                            )+['brother','sister'][.g], _
                            if(b<3, _
                                '', _
                                .o(b-2)+'great-' _
                            )+[['uncle','aunt'],['nephew','neice']][s][.g] _
                        ), _
                        .o(a-1)+'cousin'+if(b>a, _
                            ', '+if((b-=a)<4, _
                                ['once','twice','thrice'][b-1], _
                                '[b] times' _
                            )+' removed,', _
                            '' _
                        ) _
                    ), _
                    if(b, _
                        if(b<3, _
                            '', _
                            '[.o(b-2)]great-' _
                        )+'grand', _
                        '' _
                    )+[['father','mother'],['son','daughter']][s][.g] _
                )
        # Check if we're climbing
        if n[0]
            # For each link in the current A-level
            for x in.d[m[1]]
                r?= _
                    .r(@[0,n[1],0],m) _ # Start a search
                    ? _ # If the search failed
                    .r(@[1,n[1]+1,0],@[m[0],x,m[3],m[3]]) # Climb again
        # Check if we're searching
        else
            # For each link in the current B-level
            for x in.d[m[2]]
                # Search up one level from the current B-level
                r?=.r(@[0,n[1],n[2]+1],@[m[0],m[1],x,m[3]])
        return r
    def o(n as int)as String
        # Get ordinal string for the number
        return if(n>1,'[n][if(0<n%10<4and not 10<n%100<14,['st','nd','rd'][n%10-1],'th')] ','')

```
> 5 votes

# Answer
### Ruby - ~~1892~~ ~~1290~~ 1247

Run as `ruby relation.rb ID1 ID2 relationship_file`.

```
P=Struct.new(:i,:m,:f,:s,:n,:c)
def f u,v,w,x,y,z
t=[y,z,v]
return t if v=='?'||x.include?(v)||v==w
r=x+[v];p=u[v]
p.c.each{|o|s=f(u,o,w,r,y,z+1);return s if s.last==w}
return t if z>0
[:m,:f].each{|i|s=f(u,p[i],w,r,y+1,z);return s if s.last==w}
t;end
def g j,a,r,b;puts"#{j[a].n} is the #{r} of #{j[b].n}.";end
def k n;n<2?'':n<3?'2nd':n<4?'3rd':"#{n}th";end
def h n;n<2?'':n<3?'great-':"#{k(n-1)} great-";end
def e n;s=n<2?'once':n<3?'twice':n<4?'thrice':"#{n} times";", #{s} removed,";end
def d u,a,b,x;y,z=x
if y==1&&z==1
w=u[a];v=u[b]
g(u,a,((w.f==v.f&&w.m==v.m)?'':'half-')+((w.s=='F')?'sister':'brother'),b)
elsif y<1||z<1
t=[y,z].max
g(u,a,h(t-1)+(t>=2?'grand':'')+(u[a].s=='F'?y>0?'daughter':'mother':y>0?'son':'father'),b)
elsif y==1||z==1
t=[y,z].max
g(u,a,h(t-1)+(u[a].s=='F'?y==1?'aunt':'niece':y==1?'uncle':'nephew'),b)
else
s=[y,z].min
g(u,a,(s-1>1?"#{k(s-1)} ":'')+'cousin'+((y==z)?'':e((z-y).abs)),b)
end;end
A,B=$*.shift(2);j={}
ARGF.each_line{|l|a=l.scan(/\s*(\d+)\s+(\d+|\?)\s+(\d+|\?)\s+([MF])\s+([\w\s]*\w+)\s*/).flatten;j[a[0]]=P.new(a[0],a[1],a[2],a[3],a[4],[])}
j.each{|k,i|[:f,:m].each{|l|j[i[l]].c<<k if i[l]!='?'}}
a=f(j,A,B,[],0,0)
if a.pop==B
d(j,A,B,a)
else
puts"#{j[A].n} is not a blood relative to #{j[B].n}."

```

Ungolfed version - ~~5251~~ 3416 (same call tree, just did a lot of code folding)

```
Person = Struct.new( :id, :mother, :father, :sex, :name, :children )

#       Find a path between "start" and "finish". To reflect human consanguinity
# rules, either travel down through descendants or up through ancestors with a
# possible down leg through their descendants.
#
# Use depth-first search until forced to improve.
# If start up, path allowed one inflection point.
# Once start down, path must continue down.
# returns [stepsUp, stepsDown, trialResult],
#   shortest path found if trialResult == finish
def findRelationship(people, start, finish, pathSoFar, stepsUp, stepsDown)
  trialResult = [stepsUp, stepsDown, start]
  #     Return success or failure.
  return trialResult if start == '?' || pathSoFar.include?(start) || start == finish
  #     If success or failure not known, explore further.
  pathNext = pathSoFar + [start]
  person = people[start]
  #     Follow descendants.
  person[:children].each do |child|
    trial = findRelationship(people, child, finish, pathNext, stepsUp, stepsDown+1)
    return trial  if trial.last == finish
  end
  #     Already past inflection point?
  return trialResult  if stepsDown > 0
  #     Follow ancestry.
  [:mother, :father].each do |parent|
    trial = findRelationship(people, person[parent], finish, pathNext, stepsUp+1, stepsDown)
    return trial  if trial.last == finish
  end
  return trialResult
end

def printRelationship(people, a, relationship, b)
  puts "#{people[a][:name]} is the #{relationship} of #{people[b][:name]}."
end

def formatNth(n)
  return n<2?'':n<3?'2nd':n<4?'3rd':"#{n}th"
end

def formatGenerations(n)
  return n<2?'':n<3?'great-':"#{formatNth(n-1)} great-"
end

def formatRemoves(n)
  s=n<2?'once':n<3?'twice':n<4?'thrice':"#{n} times"
  return ", #{s} removed,"
end

def describeRelationship(people, a, b, legLengths)
  down = legLengths.pop
  up = legLengths.pop
  if up==1 && down==1
    who = people[a]
    what = people[b]
    printRelationship(people, a,
        (who[:father] == what[:father]  &&  who[:mother] == what[:mother] ? '' : 'half-') +
          ((who[:sex] == 'F') ? 'sister' : 'brother'),
        b)
  elsif up<1 || down<1
    pathLength = [up, down].max
    printRelationship(people, a,
        formatGenerations(pathLength-1) + ((pathLength>=2) ? 'grand' : '') +
          (up>0 ?
            people[a][:sex] == 'F' ? 'daughter' : 'son'  :
            people[a][:sex] == 'F' ? 'mother': 'father'
          ),
        b)
  elsif up==1 || down==1
    pathLength = [up, down].max
    printRelationship(people, a,
        formatGenerations(pathLength-1) +
          (up==1 ?
            people[a][:sex] == 'F' ? 'aunt': 'uncle'  :
            people[a][:sex] == 'F' ? 'niece': 'nephew'
          ),
        b)
  else
    shortestLeg = [up, down].min
    printRelationship(people, a,
        (shortestLeg-1>1 ? "#{formatNth(shortestLeg-1)} " : '') +
          'cousin' +
          (up==down ? '' : formatRemoves((down-up).abs)),
        b)
  end
end

A = $*.shift
B = $*.shift
#       Meet and greet.
people = {}
ARGF.each_line do |line|
  a = line.scan(/\s*(\d+)\s+(\d+|\?)\s+(\d+|\?)\s+([MF])\s+([\w\s]*\w+)\s*/).flatten
  people[a[0]] = Person.new( a[0], a[1], a[2], a[3], a[4], [] )
end
#       Build lineage.
people.each do |key, individual|
  [:father, :mother].each do |l|
      people[individual[l]][:children] << key  if individual[l] != '?'
  end
end
#       How are A and B related?
a = findRelationship(people, A, B, [], 0, 0)
if a.pop == B
  describeRelationship(people, A, B, a)
else
  puts "#{people[A][:name]} is not a blood relative to #{people[B][:name]}."
end

```

Passes the following test suite:

```
#!/usr/bin/env perl
#
use strict;
use warnings;
require File::Temp;
use File::Temp qw( tempfile tempdir );

use Test::More qw(no_plan);
# use Test::More tests => 38;

#       solution executable
my $solver='ruby relation.rb';

#       "happy" path
my $dir = tempdir( CLEANUP => 1 );
my ($fh, $filename) = tempfile( DIR => $dir );
my $testData = <<'END_TEST_DATA';
 1  ?  ? F Agatha
 2  ?  ? M Adam
 3  ?  ? F Betty
 4  1  2 M Bertrand
 5  1  2 F Charlotte
 6  ?  ? M Carl
 7  ?  ? F Daisy
 8  3  4 M David
 9  5  6 F Emma
10  ?  ? M Edward
11  ?  ? F Freya
12  7  8 M Fred
13  9 10 F Grace
14  ?  ? M Gerald
15  ?  ? F Hillary
16 11 12 M Herbert
17 13 14 F Jane
18  ?  ? M James
19 15 16 F Kate
20 17 18 M Larry
21  ? 18 F Mary
END_TEST_DATA
print $fh  $testData;
close($fh);

is( `$solver 1  2 $filename 2>&1`, "Agatha is not a blood relative to Adam.\n", 'OP example #1,  1  2');
is( `$solver 8 3 $filename 2>&1`, "David is the son of Betty.\n", 'OP example #2,  8  3');
is( `$solver 9 13 $filename 2>&1`, "Emma is the mother of Grace.\n", 'OP example #3,  9 13');
is( `$solver 4 5 $filename 2>&1`, "Bertrand is the brother of Charlotte.\n", 'OP example #4,  4  5');
is( `$solver 9 4 $filename 2>&1`, "Emma is the niece of Bertrand.\n", 'OP example #5,  9  5');
is( `$solver 5 8 $filename 2>&1`, "Charlotte is the aunt of David.\n", 'OP example #6,  5  8');
is( `$solver 16 7 $filename 2>&1`, "Herbert is the grandson of Daisy.\n", 'OP example #7, 16  7');
is( `$solver 1 9 $filename 2>&1`, "Agatha is the grandmother of Emma.\n", 'OP example #8,  1  9 (amended)');
is( `$solver 12 5 $filename 2>&1`, "Fred is the great-nephew of Charlotte.\n", 'OP example #9, 12  5');
is( `$solver 4 13 $filename 2>&1`, "Bertrand is the great-uncle of Grace.\n", 'OP example #10,  4 13');
is( `$solver 16 3 $filename 2>&1`, "Herbert is the great-grandson of Betty.\n", 'OP example #11, 16  3');
is( `$solver 6 17 $filename 2>&1`, "Carl is the great-grandfather of Jane.\n", 'OP example #12,  6 17');
is( `$solver 19 2 $filename 2>&1`, "Kate is the 3rd great-granddaughter of Adam.\n", 'OP example #13, 19  2 (amended)');
is( `$solver 1 17 $filename 2>&1`, "Agatha is the 2nd great-grandmother of Jane.\n", 'OP example #14,  1 17 (amended)');
is( `$solver 20 4 $filename 2>&1`, "Larry is the 3rd great-nephew of Bertrand.\n", 'OP example #15, 20  4');
is( `$solver 5 16 $filename 2>&1`, "Charlotte is the 2nd great-aunt of Herbert.\n", 'OP example #16,  5 16');
is( `$solver 8 9 $filename 2>&1`, "David is the cousin of Emma.\n", 'OP example #17,  8  9');
is( `$solver 19 20 $filename 2>&1`, "Kate is the 4th cousin of Larry.\n", 'OP example #18, 19 20');
is( `$solver 16 9 $filename 2>&1`, "Herbert is the cousin, twice removed, of Emma.\n", 'OP example #19, 16  9');
is( `$solver 12 17 $filename 2>&1`, "Fred is the 2nd cousin, once removed, of Jane.\n", 'OP example #20, 12 17');
is( `$solver 21 20 $filename 2>&1`, "Mary is the half-sister of Larry.\n", 'OP example #21, 21 20');

#       "sad" path
# none!

#       "bad" path
# none!

exit 0;

```
> 3 votes

# Answer
## C - ungolfed

```
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef enum {
    MALE,
    FEMALE
} gender_t;

typedef enum {
    VISITED_A,
    VISITED_B,
    NOT_VISITED
} visited_t;

struct node {
    int id;
    int mother;
    int father;
    char *name;
    int height;
    gender_t gender;
    visited_t visited;
};

struct queue_item {
    void *item;
    struct queue_item *next;
    struct queue_item *previous;
};

struct queue {
    struct queue_item *first;
    struct queue_item *last;
};

void queue_push(struct queue *q, struct node *n)
{
    struct queue_item *i = malloc(sizeof(*i));
    i->item = (void *)n;
    i->next = q->last;
    i->previous = NULL;
    q->last = i;
    if(i->next != NULL) {
        i->next->previous = i;
    } else {
        q->first = i;
    }
}

void queue_pop(struct queue *q)
{
    struct queue_item *temp = q->first;
    if(temp) {
        q->first = q->first->previous;
        if(q->first == NULL) {
            q->last = NULL;
        } else {
            q->first->next = NULL;
        }
        free(temp);
    }
}

struct node *queue_front(struct queue *q)
{
    if(q->first) {
        return (struct node *)q->first->item;
    } else {
        return NULL;
    }
}

void queue_free(struct queue *q) {
    while(queue_front(q) != NULL) {
        queue_pop(q);
    }

    free(q);
}

struct node *find_shortest_path(struct node **nodes, struct node *a, struct node *b)
{

    struct queue *q = malloc(sizeof(*q));
    q->first = NULL;
    q->last = NULL;

    a->visited = VISITED_A;
    queue_push(q, a);
    b->visited = VISITED_B;
    queue_push(q, b);

    struct node *n, *father, *mother;

    while((n = queue_front(q)) != NULL) {
        if(n->visited == VISITED_A) {
            if(n->father != 0) {
                father = nodes[n->father-1];
                if(father->visited == VISITED_B) {
                    a->height = n->height + 1;
                    b->height = father->height;
                    n = father;
                    goto exit_queue_free;
                } else  if(father->visited == NOT_VISITED) {
                    father->visited = VISITED_A;
                    father->height = n->height+1;
                    queue_push(q, father);
                }
            }
            if(n->mother != 0) {
                mother = nodes[n->mother-1];
                if(mother->visited == VISITED_B) {
                    a->height = n->height + 1;
                    b->height = mother->height;
                    n = mother;
                    goto exit_queue_free;
                } else  if(mother->visited == NOT_VISITED) {
                    mother->visited = VISITED_A;
                    mother->height = n->height+1;
                    queue_push(q, mother);
                }
            }
        } else if (n->visited == VISITED_B) {
            if(n->father != 0) {
                father = nodes[n->father-1];
                if(father->visited == VISITED_A) {
                    b->height = n->height + 1;
                    a->height = father->height;
                    n = father;
                    goto exit_queue_free;
                } else  if(father->visited == NOT_VISITED) {
                    father->visited = VISITED_B;
                    father->height = n->height+1;
                    queue_push(q, father);
                }
            }
            if(n->mother != 0) {
                mother = nodes[n->mother-1];
                if(mother->visited == VISITED_A) {
                    b->height = n->height + 1;
                    a->height = mother->height;
                    n = mother;
                    goto exit_queue_free;
                } else  if(mother->visited == NOT_VISITED) {
                    mother->visited = VISITED_B;
                    mother->height = n->height+1;
                    queue_push(q, mother);
                }
            }
        }

        queue_pop(q);
    }

exit_queue_free:
    queue_free(q);
    return n;
}

int main(int argc, char *argv[]) {

    if(argc != 4) {
        return -1;
    }

    FILE *file = fopen(argv[1], "r");
    int id_1 = strtol(argv[2], NULL, 0);
    int id_2 = strtol(argv[3], NULL, 0);

    char name[128];
    char id[128];
    char id_father[128];
    char id_mother[128];
    char gender;

    struct queue *read_queue = malloc(sizeof(*read_queue));
    read_queue->first = NULL;
    read_queue->last = NULL;
    int nr_nodes = 0;

    while(fscanf(file, "%s %s %s %c %s",
        id, id_mother, id_father, &gender, name) == 5) {

        struct node *n = malloc(sizeof(*n));
        if(strcmp(id, "?") == 0) {
            n->id = 0;
        } else {
            n->id = strtol(id, NULL, 0);
        }

        if(strcmp(id_mother, "?") == 0) {
            n->mother = 0;
        } else {
            n->mother = strtol(id_mother, NULL, 0);
        }

        if(strcmp(id_father, "?") == 0) {
            n->father = 0;
        } else {
            n->father = strtol(id_father, NULL, 0);
        }

        if(gender == 'M') {
            n->gender = MALE;
        } else {
            n->gender = FEMALE;
        }

        n->name = malloc(strlen(name)+1);

        strcpy(n->name, name);

        n->visited = NOT_VISITED;
        n->height = 0;

        queue_push(read_queue, n);

        nr_nodes++;
    }

    struct node **nodes = malloc(sizeof(*nodes) * nr_nodes);
    struct node *temp;
    while((temp = queue_front(read_queue)) != NULL) {
        nodes[temp->id-1] = temp;
        queue_pop(read_queue);
    }

    queue_free(read_queue);

    struct node *a = nodes[id_1-1], *b = nodes[id_2-1];

    temp = find_shortest_path(nodes, a, b);

    if(temp) {
        if(a->height == b->height) {
            if(a->height == 1) {
                if((a->father == b->father) &&
                    (a->mother == b->mother)) {
                    printf("%s is the %s of %s.\n", a->name,
                        a->gender == MALE ?
                        "brother" : "sister",
                        b->name);
                } else {
                    printf("%s is the half-%s of %s.\n",
                        a->name,
                        a->gender == MALE ?
                        "brother" : "sister",
                        b->name);
                }
            } else if (a->height == 2) {
                printf("%s is the cousin of %s.\n", a->name,
                    b->name);
            } else if (a->height == 3){
                printf("%s is the 2nd cousin of %s.\n", a->name,
                    b->name);
            } else if (a->height == 4) {
                printf("%s is the 3rd cousin of %s.\n", a->name,
                    b->name);
            } else {
                printf("%s is the %dth cousin of %s.\n", a->name,
                    a->height-1,b->name);
            }
        } else if (a->height == 0) {
            if(b->height == 1) {
                printf("%s is the %s of %s.\n", a->name,
                    a->gender == MALE ? "father" :
                    "mother", b->name);
            } else if (b->height == 2) {
                printf("%s is the grand%s of %s.\n", a->name,
                    a->gender == MALE ? "father" :
                    "mother", b->name);
            } else if (b->height == 3) {
                printf("%s is the great-grand%s of %s.\n",
                    a->name, a->gender == MALE ?
                    "father" : "mother", b->name);
            } else if (b->height == 4) {
                printf("%s is the 2nd great-grand%s of %s.\n",
                    a->name, a->gender == MALE ?
                    "father" : "mother", b->name);
            } else if (b->height == 5) {
                printf("%s is the 3rd great-grand%s of %s.\n",
                    a->name, a->gender == MALE ?
                    "father" : "mother", b->name);
            } else if (b->height == 6) {
                printf("%s is the %dth great-grand%s of %s.\n",
                    a->name, b->height-2,
                    a->gender == MALE ? "father" :
                    "mother", b->name);
            }
        } else if (b->height == 0) {
            if(a->height == 1) {
                printf("%s is the %s of %s.\n", a->name,
                    a->gender == MALE ? "son" :
                    "daughter", b->name);
            } else if (a->height == 2) {
                printf("%s is the grand%s of %s.\n", a->name,
                    a->gender == MALE ? "son" :
                    "daughter", b->name);
            } else if (a->height == 3) {
                printf("%s is the great-grand%s of %s.\n",
                    a->name, a->gender == MALE ?
                    "son" : "daughter", b->name);
            } else if (a->height == 4) {
                printf("%s is the 2nd great-grand%s of %s.\n",
                    a->name, a->gender == MALE ?
                    "son" : "daughter", b->name);
            } else if (a->height == 5) {
                printf("%s is the 3rd great-grand%s of %s.\n",
                    a->name, a->gender == MALE ?
                    "son" : "daughter", b->name);
            } else {
                printf("%s is the %dth great-grand%s of %s.\n",
                    a->name, a->height - 2,
                    a->gender == MALE ? "son" :
                    "daughter", b->name);
            }
        } else if (a->height == 1) {
            if(b->height == 2) {
                printf("%s is the %s of %s.\n", a->name,
                    a->gender == MALE ? "uncle" :
                    "aunt", b->name);
            } else if(b->height == 3) {
                printf("%s is the great-%s of %s.\n", a->name,
                    a->gender == MALE ? "uncle" :
                    "aunt", b->name);
            } else if(b->height == 4) {
                printf("%s is the 2nd great-%s of %s.\n", a->name,
                    a->gender == MALE ? "uncle" :
                    "aunt", b->name);
            } else if(b->height == 5) {
                printf("%s is the 3rd great-%s of %s.\n", a->name,
                    a->gender == MALE ? "uncle" :
                    "aunt", b->name);
            } else {
                printf("%s is the %dth great-%s of %s.\n",
                    a->name, b->height - 2,
                    a->gender == MALE ? "uncle" :
                    "aunt", b->name);
            }
        } else if (b->height == 1) {
            if(a->height == 2) {
                printf("%s is the %s of %s.\n", a->name,
                    a->gender == MALE ? "nephew" :
                    "niece", b->name);
            } else if(a->height == 3) {
                printf("%s is the great-%s of %s.\n", a->name,
                    a->gender == MALE ? "nephew" :
                    "niece", b->name);
            } else if(a->height == 4) {
                printf("%s is the 2nd great-%s of %s.\n", a->name,
                    a->gender == MALE ? "nephew" :
                    "niece", b->name);
            } else if(a->height == 5) {
                printf("%s is the 3rd great-%s of %s.\n", a->name,
                    a->gender == MALE ? "nephew" :
                    "niece", b->name);
            } else {
                printf("%s is the %dth great-%s of %s.\n",
                    a->name, a->height - 2,
                    a->gender == MALE ? "nephew" :
                    "niece", b->name);
            }
        } else {
            int m = a->height > b->height ? a->height - b->height :
                b->height - a->height;
            int n = a->height > b->height ? b->height - 1:
                a->height - 1;

            printf("%s is the ", a->name);
            if(n == 2) printf("2nd ");
            if(n == 3) printf("3rd ");
            if(n > 3) printf("%dth ", n);
            printf(" cousin, ");
            if (m == 1) printf("once");
            if (m == 2) printf("twice");
            if (m == 3) printf("thrice");
            if (m > 3) printf("%d times", m);
            printf(" removed, of %s.\n", b->name);
        }
    } else
        printf("%s is not a blood relative to %s.\n", a->name, b->name);

    int i;
    for(i = 0; i < nr_nodes; i++) {
        free(nodes[i]->name);
        free(nodes[i]);
    }

    free(nodes);

    fclose(file);

    return 0;
}

```
> 3 votes

# Answer
# Javascript, 2292

```
for(var r=prompt().split("\n"),n=[{m:"",f:""}],t=1;t<r.length;t++){var e=r[t].split(" ");n[+e[0]]={m:"?"==e[1]?-1:+e[1],f:"?"==e[2]?-1:+e[2],s:e[3],n:e[4]}}var f=function(r,t){return r=n[r],t=n[t],~r.m&&r.m==t.m&&~r.f&&r.f==t.f?"M"==r.s?"brother":"sister":void 0},i=function(r,t){return r=n[r],t=n[t],~r.m&&r.m==t.m||~r.f&&r.f==t.f?"M"==r.s?"half-brother":"half-sister":void 0},o=function(r){var n=("0"+r).slice(-2),t=n[0];return n=n[1],r+(1==t?"th":1==n?"st":2==n?"nd":3==n?"rd":"th")+" "},a=function(r){return 1==r?"once":2==r?"twice":3==r?"thrice":r+" times"},h=function(r,t){var e,f,i=[t],a=[n[t].m,n[t].f];for(e=0;e<n.length&&!~a.indexOf(r);e++){i=a.slice(),a=[];for(var h=0;h<i.length;h++)i[h]>=0&&a.push(n[i[h]].m,n[i[h]].f)}if(!(e>=n.length))return f="M"==n[r].s?"father":"mother",e>0&&(f="grand"+f),e>1&&(f="great-"+f),e>2&&(f=o(e-1)+f),f},u=function(r,t){var e=h(t,r);return e?e.slice(0,-6)+("M"==n[r].s?"son":"daughter"):void 0},s=function(r){for(var t=[],e=1;e<n.length;e++)f(r,e)&&e!=r&&t.push(e);return t},l=function(r){return r=r.slice(0,-6),""==r?r:"grand"==r?"great ":"great-grand"==r?"2nd great ":o(+r.split(" ")[0].slice(0,-2)+1)+"great "},v=function(r,t){for(var e,f=s(r),i=0;i<f.length&&!(e=h(f[i],t));i++);return e?l(e)+("M"==n[r].s?"uncle":"aunt"):void 0},c=function(r,t){var e=v(t,r);return e?(e.split(" ").slice(0,-1).join(" ")+("M"==n[r].s?" nephew":" niece")).trim():void 0},g=function(r,n){for(var t=0;t<r.length;t++)if(~n.indexOf(r[t]))return!0},m=function(r,t){r=n[r],t=n[t];for(var e=[[r.m,r.f]],f=[[t.m,t.f]],i=0;i<n.length;i++){for(var h=e[i],u=f[i],s=[],l=0;l<h.length;l++){var v=0,c=0;-1!=h[l]&&(v=n[h[l]].m,c=n[h[l]].f),v>0&&s.push(v),c>0&&s.push(c)}for(var m=[],l=0;l<u.length;l++){var v=0,c=0;-1!=u[l]&&(v=n[u[l]].m,c=n[u[l]].f),v>0&&m.push(v),c>0&&m.push(c)}if(!s.length&&!m.length)break;e.push(s),f.push(m)}for(var i=1;i<Math.min(e.length,f.length);i++){var h=e[i],u=f[i];if(g(h,u))return(i>1?o(i):"")+"cousin"}for(var i=1;i<e.length;i++)for(var h=e[i],l=1;l<f.length;l++){var u=f[l];if(g(h,u)){var p=Math.min(i,l);return(p>1?o(p):"")+"cousin, "+a(Math.abs(i-l))+" removed,"}}},e=prompt().split(" "),p=+e[0],d=+e[1],M=u(p,d)||h(p,d)||f(p,d)||i(p,d)||c(p,d)||v(p,d)||m(p,d);alert(n[p].n+" is "+(M?"the "+M+" of ":"not a blood relative to ")+n[d].n+".\n"

```

I'm sure it can be golfed much further, all I did was put an ungolfed version through a minifier.

You can run the ungolfed version here on jsFiddle. Here is the output for the example data:

```
1 2 Agatha is not a blood relative to Adam.
8 3 David is the son of Betty.
9 13 Emma is the mother of Grace.
4 5 Bertrand is the brother of Charlotte.
9 4 Emma is the niece of Bertrand.
5 8 Charlotte is the aunt of David.
16 7 Herbert is the grandson of Daisy.
1 9 Agatha is the grandmother of Emma.
12 5 Fred is the great nephew of Charlotte.
4 13 Bertrand is the great uncle of Grace.
16 3 Herbert is the great-grandson of Betty.
6 17 Carl is the great-grandfather of Jane.
19 1 Kate is the 3rd great-granddaughter of Agatha.
2 17 Adam is the 2nd great-grandfather of Jane.
20 4 Larry is the 3rd great nephew of Bertrand.
5 16 Charlotte is the 2nd great aunt of Herbert.
8 9 David is the cousin of Emma.
19 20 Kate is the 4th cousin of Larry.
16 9 Herbert is the cousin, twice removed, of Emma.
12 17 Fred is the 2nd cousin, once removed, of Jane.
21 20 Mary is the half-sister of Larry.

```
> 2 votes

# Answer
# Python 3: 1183

```
def D(i):
 if i==a:return 0
 r=[D(c)for c in t[i][4]]
 if r:return min(x for x in r if x is not None)+1
def A(i):
 if i=="?":return None
 r=D(i)
 if r is not None:return 0,r
 m,f=map(A,t[i][:2])
 return(f[0]+1,f[1])if not m or(f and sum(f)<sum(m))else(m[0]+1,m[1])if f else None
def P(r):print("%s is %s of %s"%(t[a][3],r,t[b][3]))
O=lambda n:"%d%s "%(n,{2:"nd",3:"rd"}.get(n,"th"))
G=lambda n:(O(n-2)if n>3 else"")+("great-"if n>2 else"")
GG=lambda n:G(n)+("grand"if n>1 else"")
f,a,b=input().split()
t={}
for l in open(f):
 i,m,f,g,n=l.strip().split(maxsplit=4)
 t[i]=(m,f,g,n,[])
for i,(m,f,g,n,c)in t.items():
 if m in t:t[m][4].append(i)
 if f in t:t[f][4].append(i)
g=t[a][2]=="M"
r=A(b)
if r:
 u,d=r
 if u==d==1:P("the "+("half-"if t[s][0]!=t[e][0]or t[s][1]!=t[s][1]else"")+["sister","brother"][g])
 elif u==0:P("the "+GG(d)+["daughter","son"][g])
 elif d==0:P("the "+GG(u)+["mother","father"][g])
 elif u==1:P("the "+G(d)+["niece","nephew"][g])
 elif d==1:P("the "+G(u)+["aunt","uncle"][g])
 else:
  n,m=min(u,d)-1,abs(u-d);P("the "+(O(n)if n>1 else"")+"cousin"+(" %s removed"%{1:"once",2:"twice",3:"thrice"}.get(m,"%d times"%m)if m else""))
else:
 P("not a blood relative")

```

The filename and the IDs of the people to be described are are read from standard input on a single line.

The top part of the code is function definitions. The script starts half-way down, and first works on processing the input (parsing the file, then assigning children to their parents in a second pass).

After the data is set up, we call the `A` function once to kick off a recursive search. The result defines the relationship.

The rest of the code is dedicated to describing that relationship in English. Siblings and cousins are complicated (and use long lines), the rest are pretty straight forward.

Example run (the second line is my input):

```
C:\>Python34\python.exe relations.py
relations.txt 20 4
Larry is the 3rd great-nephew of Bertrand

```

Function and variable name key:

* `f`: The filename the family's data is read from.
* `a`: The id of the person who's relationship we're naming.
* `b`: The id of the person the relationship is defined relative to.
* `t`: The family tree itself, as a dictionary mapping from an id to a 5-tuple of mother's id, father's id, sex, name and a list of children.
* `g`: A Boolean value reflecting the gender of person `a`. It is `True` if they are a male.
* `u`: The number of generations from `b` to the common ancestor of `a` and `b` (or 0 if `b` is `a`'s ancestor).
* `d`: The number of generations from `a` to the common ancestor of `a` and `b` (or 0 if `a` is `b`'s ancestor).
* `D(i)`: Recursively search the descendents of person `i` for person `a`. Return the depth `a` was found at, or None if it was not found.
* `A(i)`: Recursively search `i` and `i`'s descendents, but if its not found recursively search `i`'s ancestors (and their descendents) too. Returns a 2-tuple, who's values are `u` and `d` described above. If a relationship is found through both parents, the one with the smallest number of generational steps (`u+d`) is preferred. If person `a` has no blood relationship to person `i`, `A(i)` returns `None`.
* `P(r)`: Print result string `r` bracketed by the names of persons `a` and `b`.
* `O(n)`: Return an ordinal string for the given number `n`. Only supports `1 < n < 21`.
* `G(n)`: Return a prefix string equivalent to `n-1` "greats" (e.g. `"2nd great-"` for n=2\`). Will return an empty string for n \<= 1.
* `GG(n)`: Returns a prefix string with "Nth great-" and "grand", as appropriate for `n` generations. Will return an empty string for n \<= 1.

I took a few shortcuts in the name of shorter code which could be revised for better (or slightly more correct) performance on large genealogies. The `A` function doesn't make any attempt to avoid recursing down child trees that have already been searched, which makes it slower than necessary (though probably still fast enough for reasonable sized families). The `O` function doesn't correctly handle ordinals greater than 20 (it's a bit tricky to get all of `11th`, `21st`, and `101st` right, but in one of my draft versions I did it in about 25 additional bytes). Unless you're dealing with very old and famous families (e.g. some of the royal families of Europe) I'm not sure I'd trust the accuracy of a genealogy that went back that far anyway.

On the other hand, I've also skipped over a few places where I could shave off a few bytes. For instance, I could save 3 bytes by renaming `GG` to a single character name, but basing the name off of `great-grand` seemed more worth while to me.

I believe that all white-space in the code is required, but it's possible that some can be skipped and I've just missed them (I kept finding stray spaces in argument lists as I was typing up this answer, but I think I've gotten them all now).

Because my recursive matching requires a relatively simple rule for which relationships to prefer if there is more than one, I don't give exactly the requested results in some obscure cases involving intergenerational incest. For instance, if person `a` is both person `b`'s uncle and grandfather, my code will prefer the grandfather relationship despite the question saying that the uncle relationship should have higher precedence.

Here's an example dataset that exposes the issue:

```
1 ? ? F Alice
2 1 ? M Bob
3 1 2 F Claire
4 3 ? F Danielle

```

I suspect that for most programs, the relationships between Bob and Claire or between Bob and Danielle will cause trouble. They will either call the first pair half-siblings rather than father/daughter or they'll describe the latter pair as grandfather/granddaughter rather than uncle/niece. My code does the latter, and I don't see any reasonable way to change it to get the requested results without also getting the first pair wrong.
> 2 votes

# Answer
A test suite. Stuff it into t/relation.t and run "prove" or "perl t/relation.t". It currently assumes the program file is "relation.rb".

It's community wiki, so feel free to add tests. If you change it, I think a timestamp (or some other obvious flag) would be in order. Wish list:

1. a "bad boy" test that will punish exhaustive search strategies

```
#
#       S. Leadley, Wed Aug 27 20:08:31 EDT 2014
use strict;
use warnings;
require File::Temp;
use File::Temp qw( tempfile tempdir );

use Test::More qw(no_plan);
# use Test::More tests => 38;

#       solution executable
my $solver='ruby relation.rb';

#       "happy" path
my $dir = tempdir( CLEANUP => 1 );
my ($fh, $filename) = tempfile( DIR => $dir );
my $testData = <<'END_TEST_DATA';
 1  ?  ? F Agatha
 2  ?  ? M Adam
 3  ?  ? F Betty
 4  1  2 M Bertrand
 5  1  2 F Charlotte
 6  ?  ? M Carl
 7  ?  ? F Daisy
 8  3  4 M David
 9  5  6 F Emma
10  ?  ? M Edward
11  ?  ? F Freya
12  7  8 M Fred
13  9 10 F Grace
14  ?  ? M Gerald
15  ?  ? F Hillary
16 11 12 M Herbert
17 13 14 F Jane
18  ?  ? M James
19 15 16 F Kate
20 17 18 M Larry
21  ? 18 F Mary
END_TEST_DATA
print $fh  $testData;
close($fh);

is( `$solver 1  2 $filename 2>&1`, "Agatha is not a blood relative to Adam.\n", 'OP example #1,  1  2');
is( `$solver 8 3 $filename 2>&1`, "David is the son of Betty.\n", 'OP example #2,  8  3');
is( `$solver 9 13 $filename 2>&1`, "Emma is the mother of Grace.\n", 'OP example #3,  9 13');
is( `$solver 4 5 $filename 2>&1`, "Bertrand is the brother of Charlotte.\n", 'OP example #4,  4  5');
is( `$solver 9 4 $filename 2>&1`, "Emma is the niece of Bertrand.\n", 'OP example #5,  9  5');
is( `$solver 5 8 $filename 2>&1`, "Charlotte is the aunt of David.\n", 'OP example #6,  5  8');
is( `$solver 16 7 $filename 2>&1`, "Herbert is the grandson of Daisy.\n", 'OP example #7, 16  7');
is( `$solver 1 9 $filename 2>&1`, "Agatha is the grandmother of Emma.\n", 'OP example #8,  1  9 (amended)');
is( `$solver 12 5 $filename 2>&1`, "Fred is the great-nephew of Charlotte.\n", 'OP example #9, 12  5');
is( `$solver 4 13 $filename 2>&1`, "Bertrand is the great-uncle of Grace.\n", 'OP example #10,  4 13');
is( `$solver 16 3 $filename 2>&1`, "Herbert is the great-grandson of Betty.\n", 'OP example #11, 16  3');
is( `$solver 6 17 $filename 2>&1`, "Carl is the great-grandfather of Jane.\n", 'OP example #12,  6 17');
is( `$solver 19 2 $filename 2>&1`, "Kate is the 3rd great-granddaughter of Adam.\n", 'OP example #13, 19  2 (amended)');
is( `$solver 1 17 $filename 2>&1`, "Agatha is the 2nd great-grandmother of Jane.\n", 'OP example #14,  1 17 (amended)');
is( `$solver 20 4 $filename 2>&1`, "Larry is the 3rd great-nephew of Bertrand.\n", 'OP example #15, 20  4');
is( `$solver 5 16 $filename 2>&1`, "Charlotte is the 2nd great-aunt of Herbert.\n", 'OP example #16,  5 16');
is( `$solver 8 9 $filename 2>&1`, "David is the cousin of Emma.\n", 'OP example #17,  8  9');
is( `$solver 19 20 $filename 2>&1`, "Kate is the 4th cousin of Larry.\n", 'OP example #18, 19 20');
is( `$solver 16 9 $filename 2>&1`, "Herbert is the cousin, twice removed, of Emma.\n", 'OP example #19, 16  9');
is( `$solver 12 17 $filename 2>&1`, "Fred is the 2nd cousin, once removed, of Jane.\n", 'OP example #20, 12 17');
is( `$solver 21 20 $filename 2>&1`, "Mary is the half-sister of Larry.\n", 'OP example #21, 21 20');

#       "sad" path
# none!

#       "bad" path
is( `$solver 1 32 $filename 2>&1`, "person with ID 32 does not exist\n", 'not required, not in the spec');

exit 0;

```
> 0 votes

---
Tags: code-golf, graph-theory
---