Perl Weekly Challenge: Where Everybody Knows Your Name

Posted on by

Perl Weekly Challenge 361‘s tasks are “Zeckendorf Representation” and “Find Celebrity”, where a celebrity is someone everyone knows, so…

Sometimes you wanna go
Where everybody knows your name…

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.

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

Approach

So, the first thing I did was to look up Zeckendorf’s theorem so I could think about how to approach the problem. Generating the Zeckendorf form follows a greedy algorithm; essentially, to find the Zeckendorf form for N we generate all the Fibonacci numbers less than or equal to N, then choose the largest Fibonacci number from that list, subtract that from N, and then repeat the process until we’ve generated a list that sums to N.

Let’s take the last example where N = 100. The Fibonacci numbers ≤ 100 are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. So we pick 89 as our first number, and subtract that from 100 to get a new N of 11. The largest Fibonacci ≤ 11 is 8, so we subtract 8 from 11 to get 3. 3 is itself a Fibanacci number, so we select that, and we’ve arrived at the Zeckendorf form 89 + 8 + 3.

We don’t need to worry about prohibiting consecutive Fibonacci numbers, because each Fibonacci number is the sum of the previous two, so if N – Fx yielded Fx-1, that means that N itself was Fx+1 and that would have been the number selected by the greedy algorithm.

Raku

To find the largest Fibonacci number less than or equal to $int, we’re iterating through a calculation of the sequence, and returning the second-to-last element when the last element becomes larger than $int.

Then we’re using recursion to build the list of numbers in the Zeckendorf form. I’m using the List method .flat on line 20 to avoid getting a list of nested lists as my result.

sub largest_fibo_le($int) {
  my ($x, $y) = (0, 1);
  while ($y <= $int) {
    ($x, $y) = ($y, $x + $y);
  }
  return $x;
}

sub zeckendorf($int) {
  # the largest element is the first number
  # in the Zeckendorf form
  my $largest = largest_fibo_le($int);

  return $largest if $largest == $int;

  # if we need more elements, use recursion to find them
  return ( $largest, zeckendorf( $int - $largest ) ).flat;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $int = 4
Output: 3,1

4 => 3 + 1

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

Perl

The Perl solution is exactly the same, except that zeckendorf() returns a list instead of a list object, so I don’t need to worry about nesting on line 20.

sub largest_fibo_le($int) {
  my ($x, $y) = (0, 1);
  while ($y <= $int) {
    ($x, $y) = ($y, $x + $y);
  }
  return $x;
}

sub zeckendorf($int) {
  # the largest element is the first number
  # in the Zeckendorf form
  my $largest = largest_fibo_le($int);

  return $largest if $largest == $int;

  # if we need more elements, use recursion to find them
  return ( $largest, zeckendorf( $int - $largest ) );
}

View the entire Perl script for this task on GitHub.

Python

In Python, we’re using list.extend() to avoid getting nested lists.

def largest_fibo_le(i):
  x, y = 0, 1
  while y <= i:
    x, y = y, x + y
  return x

def zeckendorf(i):
  # the largest element is the first number
  # in the Zeckendorf form
  largest = largest_fibo_le(i)
  z = [largest]

  if largest == i: return z

  # if we need more elements, use recursion to find them
  z.extend( zeckendorf( i - largest ) )
  return z

View the entire Python script for this task on GitHub.

Elixir

Because Elixir doesn’t really have loops, everything is done through recursion. I simulate the while loop in largest_fibo_le/1 by passing the x and y parameters to a largest_fibo_le/2 function that has two clauses, one with the stopping condition.

def largest_fibo_le(i, x, y) when y > i, do: x
def largest_fibo_le(i, x, y) do
  largest_fibo_le(i, y, x + y)
end
def largest_fibo_le(i), do: largest_fibo_le(i, 0, 1)

def zeckendorf(int) do
  # the largest element is the first number
  # in the Zeckendorf form
  z = [ largest_fibo_le(int) ]
  if hd(z) == int do
    z
  else
    # if we need more elements, use recursion to find them
    z ++ zeckendorf(int - hd(z)) |> List.flatten
  end
end

View the entire Elixir script for this task on GitHub.

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.

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

Approach

Ok, there are two criteria set forth for a celebrity: a) everyone knows them, and b) they don’t know anybody (I guess in this task, you cannot know yourself). So, for an n x n matrix, a celebrity would need to know 0 people and be known by n-1 people.

I figure I’ll loop through the matrix and add up two array accumulators for each of the party attendees: knows and known_by. If knows[i] == 0 and known_by[i] == n-1, then i is the celebrity.

Raku

The Raku implementation is fairly straightforward from the approach: we set up the @knows and @known_by arrays to track the counts, then do a nested loop to examine each element in the @party matrix, then finally do one more loop over the counts in @knows and @known_by arrays to see if any of the entries match the celebrity criteria.

sub celebrity(@party) {
  my (@knows, @known_by);
  my $n = @party.end;
  for 0..$n -> $i {
    for 0..$n -> $j {
      @knows[$i]    += @party[$i][$j];
      @known_by[$j] += @party[$i][$j];
    }
  }
  for 0..$n -> $i {
    next unless @knows[$i] == 0; # knows nobody
    next unless @known_by[$i] == $n; # eveyone knows
    return $i;
  }
  return -1;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @party = [
                  [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, 0]
                ]
Output: 4

Example 2:
Input: @party = [
                  [0, 1, 0, 0],
                  [0, 0, 1, 0],
                  [0, 0, 0, 1],
                  [1, 0, 0, 0]
                ]
Output: -1

Example 3:
Input: @party = [
                  [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]
                ]
Output: 0

Example 4:
Input: @party = [
                  [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]
                ]
Output: 3

Example 5:
Input: @party = [
                  [0, 1, 1, 0],
                  [1, 0, 1, 0],
                  [0, 0, 0, 0],
                  [0, 0, 0, 0]
                ]
Output: -1

Example 6:
Input: @party = [
                  [0, 0, 1, 1],
                  [1, 0, 0, 0],
                  [1, 1, 0, 1],
                  [1, 1, 0, 0]
                ]
Output: -1

Perl

Things are the same under Perl, except the sigil for accessing array variables is $ and not @.

sub celebrity(@party) {
  my (@knows, @known_by);
  my $n = $#party;
  for my $i (0 .. $n) {
    for my $j (0 .. $n) {
      $knows[$i]    += $party[$i][$j];
      $known_by[$j] += $party[$i][$j];
    }
  }
  for my $i (0 .. $n) {
    next unless $knows[$i] == 0; # knows nobody
    next unless $known_by[$i] == $n; # eveyone knows
    return $i;
  }
  return -1;
}

View the entire Perl script for this task on GitHub.

Python

The big difference in Python is that we need to initialize the knows and known_by arrays to have 0 in them, because Python doesn’t autovivify the elements.

def celebrity(party):
  n = len(party)
  knows    = [0] * n # init all elements to 0
  known_by = [0] * n
  for i in range(n):
    for j in range(n):
      knows[i]    += party[i][j]
      known_by[j] += party[i][j]
  for i in range(n):
    if knows[i] == 0 and known_by[i] == n-1:
      return i
  return -1

View the entire Python script for this task on GitHub.

Elixir

Initially, I had re-written the Elixir solution to use recursion for the double looping because I’m still really uncertain about doing loops in Elixir:

def celebrity(_, n, i, _, knows, known_by) when i == n,
  do: {knows, known_by}

def celebrity(party, n, i, j, knows, known_by) when j == n,
  do: celebrity(party, n, i+1, 0, knows, known_by)

def celebrity(party, n, i, j, knows, known_by) do
  val      = party |> Enum.at(i) |> Enum.at(j)
  knows    = Map.update(knows,    i, val, &(&1 + val))
  known_by = Map.update(known_by, j, val, &(&1 + val))
  celebrity(party, n, i, j+1, knows, known_by)
end

def celebrity(party) do
  n = length(party)
  {knows, known_by} = celebrity(party, n, 0, 0, %{}, %{})
  Enum.reduce(0..n-1, -1, fn i, def ->
    if Map.get(knows,i) == 0 and Map.get(known_by,i) == n-1,
      do:   i,
      else: def
  end)
end

But at the end I tried using a Enum.reduce/3 call on lines 20-24 to determine the final result. I realized that it just needed to make one loop though the numbers 0 .. n-1, and it could return either the partygoer that met the criteria or -1… and then I realized I could be using a pair of reduce calls to do the nested loops I was using in my other implementations.

def celebrity(party) do
  n = length(party)
  {knows, known_by} =
  Enum.reduce(0..n-1, {%{}, %{}}, fn i, {k, kb} ->
    Enum.reduce(0..n-1, {k, kb}, fn j, {k, kb} ->
      val = party |> Enum.at(i) |> Enum.at(j)
      k   = Map.update(k,  i, val, &(&1 + val))
      kb  = Map.update(kb, j, val, &(&1 + val))
      {k, kb}
    end)
  end)
  Enum.reduce(0..n-1, -1, fn i, def ->
    if Map.get(knows,i) == 0 and Map.get(known_by,i) == n-1,
      do:   i,
      else: def
  end)
end

I switched from using a list to using a map for the knows/known_by accumulators because I could use Map.update/4 to update them out of order (in Elixir, lists really aren’t arrays, and you need to jump through more hoops to simulate random-access updates).

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-361/packy-anderson

Leave a Reply