25
\$\begingroup\$

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

\$\endgroup\$
22
  • 1
    \$\begingroup\$ How are "bastards" represented? \$\endgroup\$ Aug 27 '15 at 17:54
  • \$\begingroup\$ In itself they are not indicated as an attribute, one would need to check if their family name is different from the father's. \$\endgroup\$ Aug 27 '15 at 17:55
  • 1
    \$\begingroup\$ @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? \$\endgroup\$
    – Kamehameha
    Aug 28 '15 at 11:29
  • 1
    \$\begingroup\$ @kamehameha yes, I'll edit it now \$\endgroup\$ Aug 28 '15 at 11:53
  • 1
    \$\begingroup\$ @WizardOfMenlo Can you provide an example case where it will reach the king's brother/sister's realm? \$\endgroup\$
    – JNV
    Aug 30 '15 at 10:22
6
\$\begingroup\$

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

\$\endgroup\$
7
  • \$\begingroup\$ That was quick! \$\endgroup\$ Aug 27 '15 at 20:33
  • \$\begingroup\$ while loop are prohibited when golfing in PHP :). \$\endgroup\$
    – Blackhole
    Aug 27 '15 at 20:52
  • \$\begingroup\$ 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 \$\endgroup\$ Aug 28 '15 at 6:41
  • \$\begingroup\$ 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. \$\endgroup\$
    – Razvan
    Aug 28 '15 at 11:01
  • \$\begingroup\$ You are absolutely right, my fanboysm got the best of me \$\endgroup\$ Aug 28 '15 at 11:55
5
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ amazing! I chickened out of trying to do this since the spec was a bit wordy. very nicely done! \$\endgroup\$
    – Razetime
    Sep 9 at 4:42
  • \$\begingroup\$ @Razetime thank you very much! \$\endgroup\$ Sep 9 at 10:24
  • \$\begingroup\$ You can save 53 bytes by using one character names for the keys, "N": "Eddard", "H" : "Stark"... \$\endgroup\$ Sep 9 at 16:59
  • \$\begingroup\$ @JohanduToit can I? It says I can choose the data format but nothing about the content or even the naming of the keys. \$\endgroup\$ Sep 9 at 20:08
  • \$\begingroup\$ This part is a bit vague: You may use any convenient(nested) list format to represent the tree. I'm assuming that something like this will also be valid input TIO \$\endgroup\$ Sep 10 at 13:34
3
\$\begingroup\$

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!

\$\endgroup\$
13
  • \$\begingroup\$ A few quick golfs to get you down to 300 bytes \$\endgroup\$
    – Shaggy
    Sep 7 at 16:29
  • \$\begingroup\$ @Shaggy Thanks, I had to add +r.b else it does not sort correctly by age. \$\endgroup\$ Sep 7 at 16:51
  • \$\begingroup\$ 260 \$\endgroup\$
    – Shaggy
    Sep 8 at 9:06
  • \$\begingroup\$ I think that works, at least; with so few test cases it's hard to tell. \$\endgroup\$
    – Shaggy
    Sep 8 at 9:06
  • 1
    \$\begingroup\$ 248 \$\endgroup\$
    – Shaggy
    Sep 8 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.