| 13 March 2026 | Challenge 361 |
Zeckendorf's Party
Task 1: Zeckendorf Representation
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: $int = 4
Output: 3,1
4 => 3 + 1 (non-consecutive fibonacci numbers)
Example 2
Input: $int = 12
Output: 8,3,1
12 => 8 + 3 + 1
Example 3
Input: $int = 20
Output: 13,5,2
20 => 13 + 5 + 2
Example 4
Input: $int = 96
Output: 89,5,2
96 => 89 + 5 + 2
Example 5
Input: $int = 100
Output: 89,8,3
100 => 89 + 8 + 3
Solution
Take the largest Fibonacci number not exceeding $int and proceed with $int reduced by the found number
Perl
use strict;
use warnings;
use experimental 'signatures';
use List::Gather;
sub zeckendorf_representation ($n) {
gather { # 1
while () { # 2
my ($f1, $f2) = (1, 1); # 3
($f1, $f2) = ($f2, $f1 + $f2) while $n >= $f2; # 4
take $f1; # 5
$n -= $f1; # 6
last unless $n; # 7
} # 8
} # 9
}
See the full solution to task 1.
J
The logic in J is almost identical to the Perl implementation.
maxfib =. {.@(] (({:@] , +/@])^:([ >: {:@])^:_) (1 1)"_) NB. 1
getnext =. {{
1 Z: 0&=@{. y NB. 2
{: y NB. 3
}}
getfib =. (maxfib ([ ,~ -~) ])@{. f. NB. 4
zr =: getnext F: getfib f. NB. 5
echo zr 20
NB. 1 corresponds to # 3 and # 4.
It finds the Fibonacci number.
NB. 2 terminates the loop like # 7
NB. 3 picks an intermediate result like # 5
NB. 4 actually performs getfib and reduces the current number like # 6
NB. 5 glues everything together with F: as the endless loop # 2 gathering intermediate results,
getfib as the loop body and getnext combining the loop exit and picking the results.
See the full solution.
Task 2: Find Celebrity
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: @party = (
[0, 0, 0, 0, 1, 0], # 0 knows 4
[0, 0, 0, 0, 1, 0], # 1 knows 4
[0, 0, 0, 0, 1, 0], # 2 knows 4
[0, 0, 0, 0, 1, 0], # 3 knows 4
[0, 0, 0, 0, 0, 0], # 4 knows NOBODY
[0, 0, 0, 0, 1, 0], # 5 knows 4
);
Output: 4
Example 2
Input: @party = (
[0, 1, 0, 0], # 0 knows 1
[0, 0, 1, 0], # 1 knows 2
[0, 0, 0, 1], # 2 knows 3
[1, 0, 0, 0] # 3 knows 0
);
Output: -1
Example 3
Input: @party = (
[0, 0, 0, 0, 0], # 0 knows NOBODY
[1, 0, 0, 0, 0], # 1 knows 0
[1, 0, 0, 0, 0], # 2 knows 0
[1, 0, 0, 0, 0], # 3 knows 0
[1, 0, 0, 0, 0] # 4 knows 0
);
Output: 0
Example 4
Input: @party = (
[0, 1, 0, 1, 0, 1], # 0 knows 1, 3, 5
[1, 0, 1, 1, 0, 0], # 1 knows 0, 2, 3
[0, 0, 0, 1, 1, 0], # 2 knows 3, 4
[0, 0, 0, 0, 0, 0], # 3 knows NOBODY
[0, 1, 0, 1, 0, 0], # 4 knows 1, 3
[1, 0, 1, 1, 0, 0] # 5 knows 0, 2, 3
);
Output: 3
Example 5
Input: @party = (
[0, 1, 1, 0], # 0 knows 1 and 2
[1, 0, 1, 0], # 1 knows 0 and 2
[0, 0, 0, 0], # 2 knows NOBODY
[0, 0, 0, 0] # 3 knows NOBODY
);
Output: -1
Example 6
Input: @party = (
[0, 0, 1, 1], # 0 knows 2 and 3
[1, 0, 0, 0], # 1 knows 0
[1, 1, 0, 1], # 2 knows 0, 1 and 3
[1, 1, 0, 0] # 3 knows 0 and 1
);
Output: -1
Solution
Presuming a square matrix as anything else doesn’t seem to make sense.
Take the logical nor over the rows to identify those that know nobody and the logical and over the columns to identiy those that are known by everybody.
The diagonal elements have to be ignored or set to 1 in the second step.
A celebrity can be identified by a 1 in both results.
An empty result shall be converted to -1.
Perl
Using PDL for the matrix operations.
Set the diagonal to BAD.
sub find_celebrity {
my $party = long(@_)->copy;
$party->badflag(1);
$party->diagonal(0, 1) .= $party->badvalue;
my $celeb = which !$party->orover * $party->xchg(0, 1)->andover;
$celeb->isempty ? -1 : $celeb->sclr;
}
See the full solution to task 2.
J
Set the diagonal to 1 for the and operation.
diag =. [`(,.~@i.@#@])
FindCelebrity =: (1&$@_1:^:(-.@*@#))@I.@(-.@(+./)@|: *. *./@(1&(diag }))) f.
See the full solution.