RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved Fibonacci numbers and set filtering. (Note that this ends today.)

Task 1: Zeckendorf Representation

You are given a positive integer (<= 100).

Write a script to return Zeckendorf Representation of the given integer.

Every positive integer can be uniquely represented as sum of non-consecutive Fibonacci numbers.

It turns out from the Wikipedia page that one can do this greedily: i.e. given all the Fibonacci numbers less than or equal to N, the highest will form part of N's Zeckendorf representation, and one can do this repeatedly.

This in JavaScript:

function zeckendorfrepresentation(a) {

Build a Fibonacci sequence.

    let fib = [0, 1];
    while (fib[fib.length - 1] <= a) {
        fib.push(fib[fib.length - 1] + fib[fib.length - 2]);
    }
    fib.pop();

The last number in fib will be no higher than a.

Set up the output list and a working copy of a.

    let res = [];
    let aw = a;

While there are any numbers left,

    while (aw > 0) {

pop the last one off the fib list, add it to the output, and subtract it from the working copy.

        const fl = fib.length - 1;
        res.push(fib[fl]);
        aw -= fib[fl];
        fib.pop();

Also pop the next highest, because we can't have consecutive numbers in the output.

        fib.pop();

Finally, keep pruning the list until the highest number is no higher than the working a.

        while (fib[fib.length - 1] > aw) {
            fib.pop();
        }
    }

And return the output.

    return res;
}

I'm rather fond of the PostScript method of generating the list:

    /fib [ 0 1
           {
               dup a gt {
                   exit
               } if
               2 copy add
           } loop
           pop
    ] def

Task 2: Find Celebrity

You are given a binary matrix (m x n).

Write a script to find the celebrity, return -1 when none found.

A celebrity is someone, everyone knows and knows nobody.

I lacked enthusiasm for the fiddly code needed in multiple languages, so I just did it in the core group (Perl, Raku, Rust and PostScript).

The fiddly bit is that there's an entry indicating whether the person knows themselves, which strictly would have to be both true and false. I explicitly ignore it.

In Raku:

sub findcelebrity(@a) {

Initialise the sets for "knows nobody" and "everybody knows them".

    my %knowsnobody = SetHash.new;
    my %everybodyknows = SetHash.new;

Run through the individuals.

    for 0 ..@a.end -> $i {

Generate a list of people who might know them.

        my @ek = @a.map({$_[$i]});

Remove the entry that indicates whether they know themselves.

        splice @ek, $i, 1;

If everyone (else) knoes them, put them in the list.

        if (all(@ek) == 1) {
            %everybodyknows{$i}++;
        }

Similarly, build a list for everyone they might know. (Making sure I don't alter the original.)

        my @kn = @a[$i].clone;

Remove the reflexive entry.

        splice @kn, $i, 1;

Check that all the rest are zero.

        if (all(@kn) == 0) {
            %knowsnobody{$i}++;
        }
    }

Then take the intersection of the two sets, and if there's a single entry return it. (There can't be more than one.)

    my %celebs = %everybodyknows (&) %knowsnobody;
    if (%celebs.elems != 1 ) {
        return -1;
    }
    %celebs.keys[0];
}

In Perl, with no set semantics, I use hashes:

sub findcelebrity($a) {
  my %knowsnobody;
  my %everybodyknows;
  foreach my $i (0 ..$#{$a}) {
    my @ek = map {$_->[$i]} @{$a};
    splice @ek, $i, 1;
    if (all {$_ == 1} @ek) {
      $everybodyknows{$i}++;
    }
    my @kn = @{dclone($a->[$i])};
    splice @kn, $i, 1;
    if (all {$_ == 0} @kn) {
      $knowsnobody{$i}++;
    }
  }
  my %celebs;
  foreach my $k (keys %everybodyknows) {
    if (exists $knowsnobody{$k}) {
      $celebs{$k} = 1;
    }
  }
  if (scalar %celebs != 1 ) {
    return -1;
  }
  (keys %celebs)[0];
}

Full code on codeberg.