TWC361

Challenge Link

Task1

We calculate the zeckendorf representation of the given number:

#!/usr/bin/env perl
use strict;
use warnings;
use Data::Show;

sub zeckendorf_representation{
  my ($n) = @_;
  my @fibs = (1,2);
  push @fibs,$fibs[-1] + $fibs[-2] while($fibs[-1] + $fibs[-2] <= $n);
  
  my ($i,$rem,@parts) = ($#fibs,$n);
  while($rem) {
    if($fibs[$i] <= $rem) {
      push @parts,$fibs[$i];
      $rem -= $fibs[$i];
      $i -= 2;
    } else {
      --$i
    }
  }
  @parts
}

show zeckendorf_representation(4);
show zeckendorf_representation(12);
show zeckendorf_representation(20);
show zeckendorf_representation(96);
show zeckendorf_representation(100);

Task2

We find person who doesn't know anybody else:

#!/usr/bin/env perl
use strict;
use warnings;

sub find_celebrity{
  my ($party) = @_;
  my $n = @$party;
  return -1 if $n == 0;

  my $cand = 0;
  foreach my $i(1..$n-1) {
    $cand = $i if($party->[$cand][$i]);
  }
  
  foreach my $i(0..$n-1) {
    next if $i == $cand;
    return -1 if($party->[$cand][$i] || !$party->[$i][$cand]);
  }
  $cand
}

printf "%d\n",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,0]]);
printf "%d\n",find_celebrity([[0,1,0,0],
			      [0,0,1,0],
			      [0,0,0,1],
			      [1,0,0,0]]);
printf "%d\n",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]]);
printf "%d\n",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]]);
printf "%d\n",find_celebrity([[0,1,1,0],
			      [1,0,1,0],
			      [0,0,0,0],
			      [0,0,0,0]]);
printf "%d\n",find_celebrity([[0,0,1,1],
			      [1,0,0,0],
			      [1,1,0,1],
			      [1,1,0,0]]);