Perl Weekly Challenge 361 - Zeckendorf Representation and Find Celebrity

Task 1: Zeckendorf Representation

"The Fibonacci Game: Finding the Unique Sum!"

This week's first task involves representing a positive integer as a sum of non-consecutive Fibonacci numbers. This is known as Zeckendorf's theorem.

The Strategy: Generate Fibonacci numbers up to the input. Then greedily select the largest Fibonacci number that fits, ensuring no two consecutive numbers are used.

Perl Implementation

sub zeckendorf {
    my $n = shift;
    my @f = (1, 2);
    push(@f, $f[-1] + $f[-2]) while $f[-1] <= $n;
    pop @f;
    my @r;
    for (my $i = $#f; $i >= 0; $i--) {
        if ($f[$i] <= $n) { push @r, $f[$i]; $n -= $f[$i]; }
    }
    return join ",", @r;
}

Python Implementation

def zeckendorf(n: int) -> str:
    f = [1, 2]
    while f[-1] <= n:
        f.append(f[-1] + f[-2])
    f.pop()
    r = []
    i = len(f) - 1
    while i >= 0:
        if f[i] <= n:
            r.append(f[i])
            n -= f[i]
        i -= 1
    return ",".join(str(x) for x in r)

Task 2: Find Celebrity

"The Party Mystery: Who Does Everyone Know?"

The second task involves finding a celebrity in a binary matrix - someone who is known by everyone but knows nobody.

The Strategy: Use two passes: first to find a potential celebrity candidate, then verify that the candidate is known by everyone and knows nobody.

Perl Implementation

sub find_celebrity {
    my (@party) = @_;
    my $n = scalar @party;
    my $candidate = 0;
    for my $i (1 .. $n-1) {
        if ($party[$candidate][$i]) { $candidate = $i; }
    }
    for my $i (0 .. $n-1) {
        next if $i == $candidate;
        return -1 if !$party[$i][$candidate];
        return -1 if $party[$candidate][$i];
    }
    return $candidate;
}

Python Implementation

def find_celebrity(party):
    n = len(party)
    candidate = 0
    for i in range(1, n):
        if party[candidate][i]:
            candidate = i
    for i in range(n):
        if i == candidate: continue
        if not party[i][candidate]: return -1
        if party[candidate][i]: return -1
    return candidate