Who is the rightful ruler?

Question

Who will rule the realm?

You are given a family tree which contains: name, sex, date of birth, date of death and a list of heirs, for each family member. You may use any convenient (nested) list format to represent the tree. The following examples will use JSON. Determine who will rule the realm and in which order. The succession rules are the following:

1. When a king dies the realm goes to its oldest legit male child.
2. If there is none it passes to the oldest legit female child.
3. In case the king had no heirs the realm goes to the oldest legit king's brother
4. If there are no male brothers the realm will go to the oldest legit king's sister
5. If all legit relatives are dead the realm goes to the closest bastard, applying the above rules
6. If no legit nor bastard relatives are alive print LINE EXTINCT

We define a legit son as one who has the same "house" name as its father.

Examples:

Input {}

Output LINE EXTINCT

Input

{
    "name" : "Maegor",
    "house" : "Targaryen",
    "birth" : 12,
    "death" : 48,
    "sex" : "male",
    "heirs" : []
}

Output 12-48: Maegor, LINE EXTINCT

Input

{
    "name" : "Jaehaerys",
    "house" : "Targaryen",
    "birth" : 34,
    "death" : 103,
    "sex" : "male",
    "heirs" : [
        {
        "name" : "Viserys",
        "house" : "Targaryen",
        "birth" : 77,
        "death" : 129,
        "sex" : "male",
        "heirs" : []
        }
    ]
}

Output 34-103: Jaehaerys, 103-129: Viserys, LINE EXTINCT

Input

{
        "name" : "Eddard",
        "house" : "Stark",
        "birth" : 263,
        "death" : 299,
        "sex" : "male",
        "heirs" : [
            {
            "name" : "Robb",
            "house" : "Stark",
            "birth" : 283,
            "death" : 300,
            "sex" : "male",
            "heirs" : []
            },
            {
             "name" : "Jon",
             "house" : "Snow",
             "birth" : 284,
             "death" : 384,
             "sex" : "male",
             "heirs" : []
            },
            {
             "name" : "Sansa",
             "house" : "Stark",
             "birth" : 286,
             "death" : 320,
             "sex" : "female",
             "heirs" : []
            },
            {
             "name" : "Arya",
             "house" : "Stark",
             "birth" : 289,
             "death" : 350,
             "sex" : "female",
             "heirs" : []
            },

            {
             "name" : "Brann",
             "house" : "Stark",
             "birth" : 290,
             "death" : 315,
             "sex" : "male",
             "heirs" : []
            },
            {
             "name" : "Rickon",
             "house" : "Stark",
             "birth" : 295,
             "death" : 319,
             "sex" : "male",
             "heirs" : []
            }

        ]
    }

Output: 263-299: Eddard, 299-300: Robb, 300-315: Brann, 315-319: Rickon, 319-320: Sansa, 320-350: Arya, 350-384: Jon, LINE EXTINCT

Note that the output can be formatted in any way you wish, its only requirements is that it contains the time of reign and the name of the reigning king during those years. I've used kings from the ASOIAF as demonstrative example, however the code needs to be valid for all input.

You may assume that no twins will be born.

This is a code golf challenge, so the shortest code in bytes wins

Good luck!!!

Answer 1

PHP, 664 bytes

I'm not sure if 664 bytes fit for code golfing, but here it is:

$k=json_decode($argv[1]);$s=[];$f='array_shift';$r='heirs';$e='death';$y='year';function s
($k,&$e){uasort($e,function($a,$b)use($k){$c=$a->{$h='house'};$d=$b->$h;$e=$k->$h;if($c==$e
&&$d!=$e)return-1;elseif($c!=$e&&$d==$e)return 1;elseif($a->sex<$b->sex)return 1;elseif($a
->sex>$b->sex)return -1;else return$a->birth-$b->birth;});}function d(&$e,$y){foreach($e 
as$i=>$h)if($h->death<=$y)unset($e[$i]);};($x=(array)$k)&&$k->$y=$k->birth;$l=[];while($x)
{$l[]=$k;$z=$k->$e;s($k,$k->$r);d($k->$r,$k->$e);if($k->$r){$s=$k->$r;$k=$f($s);}else{s($k
,$s);d($s,$k->$e);$k=$f($s);}if(!$k)break;$k->$y=$z;}foreach($l as$k)
echo"{$k->$y}-{$k->$e}: $k->name, ";echo"LINE EXTINCT";

It receives the JSON string input as the first command line argument.

The algorithm follows the steps described in the challenge (starts from the king, then sorts the heirs and then the siblings to find the next king).

Demo

Answer 2

jq, 429..410 392bytes

def s(x;y):sort_by(.sex,-.birth)[]|select(.death>x.death and(.house==x.house|y));def i:index([[.[1:][]|select(.!=[])][0]]);def b(z;x;y):[.[i+z][:z+length-1]|s(x;y)];def h(x;y):[x.heirs|s(x;y)];[[],[],[],[],sort_by(-.birth)?]|until(i|not;.[i][-1]as$r|[.[0]+[$r+{t:(.[0][-1].death//$r.birth)}],h($r;.),h($r;not),b(0;$r;.),b(i%2;$r;not)])|[.[0][]|"\(.t)-\(.death):\(.name)"]+["LINE EXTINCT"]|.[]

Try it online!

Explanation:

def s(x;y):sort_by(.sex,-.birth)[]                          #Function: sorts by sex lexicographically, then by birth date in descending order [youngest female -> oldest male]
            |select(                                        and selects those who
                .death > x.death                            did not die before the previous ruler
                and (.house == x.house|y)                   and have the same house (if y := not, selects those with a different house)
            );                                              
def i:index([[.[1:][]|select(.!=[])][0]]);                  #Function: returns index of the first not-empty array (ignoring first array)
def b(z;x;y):[.[i+z][:z+length-1]|s(x;y)];                  #Function: drops the last z (0 or 1) elements of the (i+z)th array and applies s on the resulting array
def h(x;y):[x.heirs|s(x;y)];                                #Function: takes the heirs of x and applies s
                                                            
[                                                           An array containing five bins:
    [],                                                         0. Result
    [],                                                         1. Heirs from same house
    [],                                                         2. Heirs from another house
    [],                                                         3. Siblings from same house
    sort_by(-.birth)?                                           4. Siblings from another house (initial: sorted input (The ? is necessary for empty inputs)) 
                                                            
|until(                                                     Until
        i|not                                               there is no such index i
    ;                                                       
        .[i][-1]as$r                                        set the last element of the ith array as the current ruler
        |[                                                  Update the array:
            .[0]+[$r+{t:(.[0][-1].death//$r.birth)}],       Add the current ruler + new attribute (the beginning time of reign) to the result array
            h($r;.),                                        Heirs from same house
            h($r;not),                                      Heirs from another house
            b(0;$r;.),                                      Siblings from same house
            b(i%2;$r;not)                                   If the ruler is heir from the same house as the previous one, store the heirs from a different house here 
                                                            else siblings from a different house
        ]                                                   
)                                                           
|                                                           
    [                                                       
        .[0][]                                              Takes the result array
        |"\(.t)-\(.death):\(.name)"                         Writes time of reign and ruler
    ]                                                       
    +["LINE EXTINCT"]                                       Writes "LINE EXTINCT"
|.[]                                                        Prints on seperated lines

Answer 3

JavaScript (Node.js), 294 248 244 245 bytes

t=>{for(s(t),o(t.b,t);t;)o(t.d,t=n(t,0))}
s=(r,p)=>r.c.sort((a,b)=>a.s-b.s||a.b-b.b,r.g=p?(r.u=p.h!=r.h,p.c):[]).map(h=>s(h,r))
n=(k,b,j)=>[...k.c,...k.g].map(h=>j=j||h.u==b&h.d>k.d&&h)&&j||b?j:n(k,1)
o=(f,h)=>alert(h?[f,h.d,h.n]:'LINE EXTINCT')

Try it online!

-82 bytes thanks to Shaggy!