Este es uno de los varios desafíos que Calvin's Hobbies dejó para la comunidad .

Tome un archivo de "árbol genealógico que describa" con líneas del formulario:

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

como este que describe el primer árbol genealógico en 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

Escriba un programa o función que tome el nombre del archivo y dos ID y muestre cómo esas personas están relacionadas con la sangre en términos simples, utilizando los nombres comunes en inglés para las relaciones. La entrada puede ser a través de STDIN, ARGV o argumentos de función, pero la salida debe ser a STDOUT.

Notas

• Los ID son enteros positivos.
• ? se usa cuando se desconoce la paternidad.
• Suponga que el gráfico estará conectado y no tiene ciclos.
• Es posible que no asumir que los padres de cada persona se enumeran antes de esa persona (por lo de una persona Identificación padre podría ser mayor que su propio ID).
• Suponga que todos son hombres o mujeres y que todos tienen exactamente una madre y exactamente un padre (del género correcto), aunque pueden ser desconocidos.
• Asuma que los nombres son únicos.
• Los nombres pueden tener espacios en ellos.

Relaciones de sangre

Las siguientes definiciones de relaciones R determinar si la persona A es la R o persona B . Si se enumeran dos variantes de R , la primera es para A hembra y la segunda para A macho . Todo esto necesita ser implementado. Si coinciden varias definiciones, se utilizará la anterior. Los términos entre paréntesis son términos neutrales al género, que no necesitan ser implementados pero serán reutilizados en definiciones adicionales. En las definiciones que involucran N y M , suponga N> 1 y M> 0 .

• hija / hijo: A enumera a B como padre o madre.
• madre / padre (padre): B enumera A como padre o madre.
• hermana / hermano (hermano): A y B enumeran la misma madre y padre.
• media hermana / medio hermano (hermano): A y B enumeran la misma madre o el mismo padre.
• sobrina / sobrino: A las listas de un padre que es el hermano de B .
• tía / tío: B es sobrina o sobrino de A.
• nieta / nieto (nieto): A enumera a un padre que enumera a B como su padre.
• abuela / abuelo (abuelo): B es el nieto de A.
• sobrina nieta / sobrino nieto: Una es el nieto de C , que es el hermano de B .
• tía abuela / tío abuelo: B es la sobrina nieta o sobrino nieto de A.
• bisnieta / hijo (1er bisnieto): A es un nieto de C que enumera a B como su padre.
• bisabuela / padre (1er bisabuelo): B es el 1er bisnieto de A.
• Enésima bisnieta / hijo (enésimo bisnieto): A es un (N-1) nieto de C que enumera a B como su padre.
• Enésimo bisabuela / padre (enésimo bisabuelo): B es el enésimo bisnieto de A.
• N-ésimo gran-sobrina / sobrino: A es el (N-1) -ésimo bisnieto de C que es el hermano de B .
• Enésima tía / tío: B es A 's enésima sobrina nieta del enésimo sobrino-nieto.
• primo: Una es el nieto de C que es el abuelo de B .
• Primo N-ésimo: A es el (N-1) -ésimo nieto de C que es el (N-1) -ésimo abuelo de B .
• primo, M veces eliminado: A es el nieto de C que es el abuelo Mes de B o A es el nieto Mes de C que es el abuelo de B .
• Primo enésimo, M veces eliminado: A es el enésimo bisnieto de C que es el enésimo bisabuelo de B , donde N = min(P,Q) + 1y M = |P-Q|.

Para Nth, escritura 2nd, 3rd, 4th, 5thetc.

Para M times, escritura once, twice, thrice, 4 times, 5 timesetc.

Ejemplos

Suponga que se usa el siguiente archivo (no tiene que ser capaz de lidiar con múltiples espacios, pero los agregué para legibilidad):

 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

Luego, las ID de entrada deben correlacionarse con las salidas de la siguiente manera:

 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.

Los escribí a mano, así que avíseme si detecta algún error.

Otro conjunto de datos de prueba (proporcionado por Scott Leadley, cualquier error es mío y no de Martin)
Árbol genealógico de Ptolomeo
La imagen es ilustrativa; los datos a continuación provienen del artículo de Wikipedia " Dinastía ptolemaica ".

 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

ECMAScript 6, 886

La división por cero es algo maravilloso.

Utiliza cuasi-literales una vez (que no se implementan en Firefox 33 o node.js, pero están disponibles en las versiones nocturnas de Firefox). El cuasi literal utilizado:

`
`

puede ser reemplazado por "\n"si lo que está utilizando carece de soporte para estos.

Este script construye un árbol a partir de la lista de personas, almacenando padres e hijos. Se prueba cada ruta de la persona A a la persona B, y se guarda la ruta óptima. Una ruta se considera válida si solo cambia de subir a bajar del árbol una vez. El cambio opuesto no está permitido: si uno necesita ir a un niño y regresar con otro padre para encontrar un camino, las dos personas no son parientes consanguíneos. ( UUUUUDDDes válido, UUDUUUno lo es. Usignifica subir (a un padre),D significa bajar (a un hijo)).

Tipo de golf:

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]+'.')}

Sin golf (tipo de):

// 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]+'.')
}

Notas:

• La lista de personas debe colocarse en una variable I(como una cadena, con espacios individuales y líneas nuevas).
• Para llamar: R(a,b)dónde ay dónde bestán las identificaciones de las dos personas que se comparan.

Cobra - 932

De todos los desafíos que he respondido en Cobra, este es, con mucho, uno de los mejores ejemplos de lo que puede hacer.

EDITAR: ahora es una función, pero debe ir precedida de la firma de Z (incluida en el recuento de caracteres).

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]."

Comentado: (desactualizado, pero sigue siendo el mismo flujo de código)

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')] ','')

C - sin golf

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

Rubí - 1892 1290 1247

Corre como 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}."

Versión sin golf - 5251 3416 (mismo árbol de llamadas, solo hice un montón de plegado de código)

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

Pasa el siguiente conjunto de pruebas:

#!/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;

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"

Estoy seguro de que se puede jugar mucho más, todo lo que hice fue poner una versión sin golf a través de un minificador.

Puede ejecutar la versión sin golf aquí en jsFiddle . Aquí está la salida para los datos de ejemplo:

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.

Pitón 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")

El nombre de archivo y las ID de las personas que se describirán se leen desde la entrada estándar en una sola línea.

La parte superior del código son las definiciones de funciones. El script comienza a mitad de camino, y primero trabaja en el procesamiento de la entrada (analizando el archivo, luego asignando hijos a sus padres en una segunda pasada).

Después de configurar los datos, llamamos a la Afunción una vez para iniciar una búsqueda recursiva. El resultado define la relación.

El resto del código está dedicado a describir esa relación en inglés. Los hermanos y primos son complicados (y usan líneas largas), el resto es bastante sencillo.

Ejemplo de ejecución (la segunda línea es mi entrada):

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

Función y clave de nombre de variable:

• f: El nombre de archivo del que se leen los datos de la familia.
• a: La identificación de la persona cuya relación estamos nombrando.
• b: El ID de la persona con la que se define la relación.
• t: El árbol genealógico en sí mismo, como un mapeo de diccionario de una identificación a una tupla de 5 de la identificación de la madre, identificación del padre, sexo, nombre y una lista de hijos.
• g: Un valor booleano que refleja el género de la persona a. Es Truesi son hombres.
• u: El número de generaciones desde bhasta el ancestro común de ay b(o 0 si bes ael ancestro de).
• d: El número de generaciones desde ahasta el ancestro común de ay b(o 0 si aes bel ancestro de).
• D(i): Recursivamente busca a los descendientes de persona ipor persona a. Devuelve la profundidad aencontrada en, o Ninguno si no se encontró.
• A(i): Búsqueda recursiva iy idescendientes de, pero si no se encuentra recursivamente, busque también a ilos antepasados ​​(y sus descendientes). Devuelve una tupla de 2, cuyos valores son uy se ddescriben anteriormente. Si se encuentra una relación a través de ambos padres, u+dse prefiere el que tenga el menor número de pasos generacionales ( ). Si la persona ano tiene una relación de sangre con la persona i, A(i)regresa None.
• P(r): Imprimir cadena de resultados rentre corchetes por los nombres de personas ay b.
• O(n): Devuelve una cadena ordinal para el número dado n. Solo apoyos 1 < n < 21.
• G(n): Devuelve una cadena de prefijo equivalente a n-1"grandes" (por ejemplo, "2nd great-"para n = 2`). Devolverá una cadena vacía para n <= 1.
• GG(n): Devuelve una cadena de prefijo con "Nth great-" y "grand", según corresponda para ngeneraciones. Devolverá una cadena vacía para n <= 1.

Tomé algunos atajos en nombre de un código más corto que podría revisarse para un mejor rendimiento (o un poco más correcto) en genealogías grandes. La Afunción no hace ningún intento de evitar la recurrencia de árboles secundarios que ya se han buscado, lo que lo hace más lento de lo necesario (aunque probablemente sea lo suficientemente rápido para familias de tamaño razonable). La Ofunción no controla correctamente los ordinales mayor de 20 (que es un poco difícil de conseguir todos 11th, 21sty 101stla derecha, pero en uno de mis proyectos de versiones lo hice en unos 25 bytes adicionales). A menos que se trate de familias muy antiguas y famosas (por ejemplo, algunas de las familias reales de Europa), no estoy seguro de confiar en la precisión de una genealogía que se remonta a esa distancia de todos modos.

Por otro lado, también he omitido algunos lugares donde podría reducir algunos bytes. Por ejemplo, podría ahorrar 3 bytes cambiando el nombre GGa un solo nombre de personaje, pero basar el nombre en algo me great-grandpareció más valioso.

Creo que se requieren todos los espacios en blanco en el código, pero es posible que se puedan omitir algunos y simplemente los he omitido (seguí encontrando espacios vacíos en las listas de argumentos mientras escribía esta respuesta, pero creo que ' los tengo todos ahora).

Debido a que mi correspondencia recursiva requiere una regla relativamente simple para qué relaciones preferir si hay más de una, no doy exactamente los resultados solicitados en algunos casos oscuros que involucran incesto intergeneracional. Por ejemplo, si la persona aes btío y abuelo de la persona, mi código preferirá la relación del abuelo a pesar de la pregunta que dice que la relación del tío debería tener mayor prioridad.

Aquí hay un conjunto de datos de ejemplo que expone el problema:

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

Sospecho que para la mayoría de los programas, las relaciones entre Bob y Claire o entre Bob y Danielle causarán problemas. Llamarán al primer par de medio hermanos en lugar de padre / hija o describirán al último par como abuelo / nieta en lugar de tío / sobrina. Mi código hace lo último, y no veo ninguna forma razonable de cambiarlo para obtener los resultados solicitados sin también obtener el primer par incorrecto.

Un conjunto de pruebas. Rellenarlo en t / relacion.t y ejecutar "probar" o "perl t / relacion.t". Actualmente se supone que el archivo del programa es "relacion.rb".

Es una wiki comunitaria, así que siéntase libre de agregar pruebas. Si lo cambia, creo que una marca de tiempo (o alguna otra marca obvia) estaría en orden. Lista de deseos:

1. una prueba de "chico malo" que castigará las estrategias de búsqueda exhaustivas

#
#       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;