# Who is the rightful ruler?

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!!!

• How are "bastards" represented? – ASCIIThenANSI Aug 27 '15 at 17:54
• In itself they are not indicated as an attribute, one would need to check if their family name is different from the father's. – WizardOfMenlo Aug 27 '15 at 17:55
• @WizardOfMenlo So is their house name their family name? – ASCIIThenANSI Aug 27 '15 at 17:57
• @WizardOfMenlo Point 3 is a bit unclear - In case the king had no sons the realm goes to the oldest legit king's brother. It seems to conflict with point 2(If no legit son, then oldest legit daughter is crowned). Do you mean heirs instead of sons in point 3? – Kamehameha Aug 28 '15 at 11:29
• @kamehameha yes, I'll edit it now – WizardOfMenlo Aug 28 '15 at 11:53

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

• That was quick! – WizardOfMenlo Aug 27 '15 at 20:33
• while loop are prohibited when golfing in PHP :). – Blackhole Aug 27 '15 at 20:52
• I think there is a mistake, I've tested it here and it link goes correctly down the line, however after it doesn't go back up to give Jon Snow it's rightful throne – WizardOfMenlo Aug 28 '15 at 6:41
• It's not a mistake. It actually follows the rules that were defined in the challange. As you can see, the last king is Tyrion which is the son of Arya. This means that the next king should be among the heirs of Tyrion or one of his brothers. But he has no brothers, nor heirs. Please note that, as per the JSON in your example, Jon Snow is the uncle of Tyrion. – Razvan Aug 28 '15 at 11:01
• You are absolutely right, my fanboysm got the best of me – WizardOfMenlo Aug 28 '15 at 11:55