Celebrity Representation
with Raku

by Arne Sommer

Celebrity Representation with Raku

[385] Published 22. February 2026.

This is my response to The Weekly Challenge #361.

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

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
File: zeckendorf-representation 
! /usr/bin/env raku

unit sub MAIN (Int $int where 1 <= $int <= 100, # [1]
              :v(:$verbose));

my $fib := (1, 1, * + * ... Inf);               # [2]

my @rev;                                        # [3]

for $fib -> $f                                  # [4]
{
  last if $f > $int;                            # [4a]
  @rev.unshift: $f;                             # [4b]
}

sink @rev.pop;                                  # [5]
      
say ": Reverse fib: { @rev.join(", ") }" if $verbose;

recurse( (), @rev);                             # [6]
      
sub recurse(@zeckendorf is copy, @rev is copy)  # [6a]
{
  say ": Z:{ @zeckendorf.join(",") } R:{ @rev.join(",") }" if $verbose;

  if @zeckendorf.sum == $int                    # [7]
  {
    say @zeckendorf.join(",");                  # [7a]
    exit;                                       # [7b]
  }

  return if @zeckendorf.sum > $int;             # [8]
  return unless @rev.elems;                     # [9]

  my $next = @rev.shift;                        # [10

  recurse(@zeckendorf, @rev);                   # [110]

  @zeckendorf.push: $next;                      # [121]
  sink @rev.shift if @rev.elems;                # [132]

  recurse(@zeckendorf, @rev)                    # [143]
}

[1] Ensure an integer in the range 1 .. 100, both included.

[2] The lazy Fibonacci sequence, in Raku fashion.

The Fibonacci sequence usually starts with 0,1,1,2,3 (A) or 1,1,2.3 (B). Both of these give the same result for us, as zero does not add up to anything. The sequence may alternatively start with 1,2,3 (C), though this is more unusual, according to en.wikipedia.org/wiki/Fibonacci_sequence. I had to choose the (C) version, as the Zeckendorf Representation is unique and the number 3 would cause both 3 (correct) and 1+2 (as in 1,1,2) (wrong) as solutions for the (A) and (B) sequence variations.

[3] The reverse Fibonacci sequence will end up here, up to (and including) the input integer.

[4] Iterate over the lazy sequence, until we reach the input number itself [4a]. Add the current value to the front of the reversed list with unshift.

See docs.raku.org/routine/unshift for more information about unshift.

[5] Get rid of the first 1, by removing the last element with pop. sink is there to explicitly throw it away.

See docs.raku.org/routine/pop for more information about pop.

See docs.raku.org/routine/sink for more information about sink.

[6] Off we go, recursively. The first argument is the partial result, and the second is the values not done so far.

[7] Do we have the value? If so, print the list [7a] and exit [7b].

[8] Abandon this recursion if we have a too high sum,

[9] or we have no more values to consider.

[10] Get the next value to consider.

[11] Ignore it for now, and recursively go on.

[12] Add the value we ignored above, and go on.

[13] Get rid of the next value (with shift), as non-consecutive values are illegal.

See docs.raku.org/routine/shift for more information about shift.

unshift (add at start), (remove at end) and shift (remove at start) are three of the four possibilites. The missing one is push (add at end).

See docs.raku.org/routine/push for more information about push.

[13] Recursively go on, with the previously ignored value.

Running it: 

$ ./zeckendorf-representation 4
3,1
$ ./zeckendorf-representation 12
8,3,1

$ ./zeckendorf-representation 20
13,5,2

$ ./zeckendorf-representation 96
89,5,2

$ ./zeckendorf-representation 100
89,8,3

Looking good.

The two first ones only with verbose mode: 

$ ./zeckendorf-representation -v 4
: Reverse fib: 3, 2, 1
: Z: R: 3,2,1
: Z: R: 2,1
: Z: R: 1
: Z: R: 
: Z:1 R: 
: Z:2 R: 
: Z:3 R: 1
: Z:3 R: 
: Z:3,1 R: 
3,1

$ ./zeckendorf-representation -v 12
: Reverse fib: 8, 5, 3, 2, 1
: Z: R: 8,5,3,2,1
: Z: R: 5,3,2,1
: Z: R: 3,2,1
: Z: R: 2,1
: Z: R: 1
: Z: R: 
: Z:1 R: 
: Z:2 R: 
: Z:3 R: 1
: Z:3 R: 
: Z:3,1 R: 
: Z:5 R: 2,1
: Z:5 R: 1
: Z:5 R: 
: Z:5,1 R: 
: Z:5,2 R: 
: Z:8 R: 3,2,1
: Z:8 R: 2,1
: Z:8 R: 1
: Z:8 R: 
: Z:8,1 R: 
: Z:8,2 R: 
: Z:8,3 R: 1
: Z:8,3 R: 
: Z:8,3,1 R: 
8,3,1

The third example gives 43 rows of output, the fourth gives 199 and the fifth and last one gives 206. Too much to print here I think.

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

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
File: find-celebrity 
#! /usr/bin/env raku

unit sub MAIN ($string = "1 0 0 | 0 0 1 | 1 0 0",         # [1]
               :v(:$verbose));

my $matrix = $string.split("|")>>.words>>.Numeric>.Array; # [2]
my $rows   = $matrix.elems;                               # [3]
my $cols   = $matrix[0].elems;                            # [4]

die "The rows must have the same size"
  unless [==] $matrix>>.elems;                            # [5]

die "The matrix must have the same number of rows and columns"
  unless $rows == $cols;                                  # [6]

die "Must contain 0s and 1s only"
  unless all($matrix[*;*]) ~~ one(0,1);                   # [7]


say ":Matrix: { $matrix.raku }" if $verbose;

for ^$cols -> $col                                        # [8]
{
  my @col = $matrix[*;$col];                              # [9]

  say ":Column $col: @col[]" if $verbose;

  if @col.sum == $cols -1                                 # [10]
  {
    say ":Column $col is a match" if $verbose;

    # my $index = @col.grep(0, :k);                       # [11]

    if $matrix[$col;*].sum == 0                           # [12]
    {
      say $index;                                         # [12a]
      exit;                                               # [12b]
    }
  }
}

say '-1';                                                 # [13]

[1] Note my «matrix as a string» input format, as the default value.

[2] Turn the string into a two dimentional array. Coerce (all) the values into numeric values (as verbose mode would expose the IntStr or NumStr types), and unlazify the result by turning it into an array (from a sequence). The integer check will be done later on (in [7]).

[3] The number of rows.

[4] The number of columns, taken from the first row.

[5] All the rows must have the same size (length).

[6] The number of rows and columns must be the same.

[7] Flatten the matrix with [*;*] and make sure that all the values are one of 0 or 1.

[8] Iterate over the column indices.

[9] Get the column data.

[10] Do everybody except one row know this one?

[11] Get the cell with the zero, with grep. The normal behaviour is to return the value, but the :k (key) adverb gives the index instead. But we do not actually need this index, as we already have it in $col and that one will ensure that the value at this index is zero (as the whole row must be zero) in [12].

See docs.raku.org/routine/grep for more information about grep.

[12] Then we check that this cell does not know anybody. If so, print the index [12a] and and exit [12b].

[13] No match? Print the error message -1.

Running it: 

$ ./find-celebrity "0 0 0 0 1 0 | 0 0 0 0 1 0 | 0 0 0 0 1 0 | 0 0 0 0 1 0 | \
    0 0 0 0 0 0 | 0 0 0 0 1 1"
4

$ ./find-celebrity "0 1 0 0 | 0 0 1 0 | 0 0 0 1 | 1 0 0 0"
-1

$ ./find-celebrity "0 0 0 0 0 | 1 0 0 0 0 | 1 0 0 0 0 | 1 0 0 0 0 | 1 0 0 0 0"
0

$ ./find-celebrity "0 1 0 1 0 1 | 1 0 1 1 0 0 | 0 0 0 1 1 0 | \
   0 0 0 0 0 0 | 0 1 0 1 0 0 | 1 0 1 1 0 0 "
3

$ ./find-celebrity "0 1 1 0 | 1 0 1 0 | 0 0 0 0 | 0 0 0 0"
-1

$ ./find-celebrity "0 0 1 1 | 1 0 0 0 | 1 1 0 1 | 1 1 0 0"
-1

Looking good.

With verbose mode: 

$ ./find-celebrity -v "0 0 0 0 1 0 | 0 0 0 0 1 0 | 0 0 0 0 1 0 | \
    0 0 0 0 1 0 | 0 0 0 0 0 0 | 0 0 0 0 1 1"
:Matrix: $([0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0], \
  [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1])
:Considering column 0: 0 0 0 0 0 0
:Considering column 1: 0 0 0 0 0 0
:Considering column 2: 0 0 0 0 0 0
:Considering column 3: 0 0 0 0 0 0
:Considering column 4: 1 1 1 1 0 1
:Everybodey knows 4
:and 4 does not know anybody
4

$ ./find-celebrity -v "0 1 0 0 | 0 0 1 0 | 0 0 0 1 | 1 0 0 0"
:Matrix: $([0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0])
:Considering column 0: 0 0 0 1
:Considering column 1: 1 0 0 0
:Considering column 2: 0 1 0 0
:Considering column 3: 0 0 1 0
-1

$ ./find-celebrity -v "0 0 0 0 0 | 1 0 0 0 0 | 1 0 0 0 0 | \
   1 0 0 0 0 | 1 0 0 0 0"
:Matrix: $([0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], \
   [1, 0, 0, 0, 0], [1, 0, 0, 0, 0])
:Considering column 0: 0 1 1 1 1
:Everybodey knows 0
:and 0 does not know anybody
0

$ ./find-celebrity -v "0 1 0 1 0 1 | 1 0 1 1 0 0 | 0 0 0 1 1 0 | \
   0 0 0 0 0 0 | 0 1 0 1 0 0 | 1 0 1 1 0 0 "
:Matrix: $([0, 1, 0, 1, 0, 1], [1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 1, 0], \
  [0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 0])
:Considering column 0: 0 1 0 0 0 1
:Considering column 1: 1 0 0 0 1 0
:Considering column 2: 0 1 0 0 0 1
:Considering column 3: 1 1 1 0 1 1
:Everybodey knows 3
:and 3 does not know anybody
3

$ ./find-celebrity -v "0 1 1 0 | 1 0 1 0 | 0 0 0 0 | 0 0 0 0"
:Matrix: $([0, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 0], [0, 0, 0, 0])
:Considering column 0: 0 1 0 0
:Considering column 1: 1 0 0 0
:Considering column 2: 1 1 0 0
:Considering column 3: 0 0 0 0
-1

$ ./find-celebrity -v "0 0 1 1 | 1 0 0 0 | 1 1 0 1 | 1 1 0 0"
:Matrix: $([0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0])
:Considering column 0: 0 1 1 1
:Everybodey knows 0
:Considering column 1: 0 0 1 1
:Considering column 2: 1 0 0 0
:Considering column 3: 1 0 1 0
-1

And that's it.

Links
 About me
 Keyword Index
 Beginning Raku (book)
 RSS Feed
 Code (zip)
Reddit Comments