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

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

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; 

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. 

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.

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;