RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved list analysis and competition resolution. (Note that this ends today.)

Task 1: Zero Friend

You are given a list of numbers.

Find the number that is closest to zero and return its distance to zero.

(I'm actually following a slightly earlier version of the problem, where the value to return was the number closest to zero, positive on a tie. To answer the problem as stated, just return the candidate positive number and ignore the second part of the problem as I follow it below.)

The candidate positive number is clearly the minimum of the absolute values of the list entries. Then it's just a matter of finding out whether the list contains that positive number.

This could all be done with a custom sorting function (compare abs, positive less than negative) but I liked this approach. (Some languages have a find-by-value; in others I map the input to a set.) Scala:

object Zerofriend {
  def zerofriend(a: List[Int]): Int = {

Candidate positive number:

    val b = a.map(x => x.abs).min

If that candidate is in the input, return it.

    if (a.contains(b)) {
      b

Otherwise return the negative.

    } else {
      -b
    }
  }

Task 2: Champion Team

You have n teams in a tournament. A matrix grid tells you which team is stronger between any two teams:

If grid[i][j] == 1, then team i is stronger than team j If grid[i][j] == 0, then team j is stronger than team iFind the champion team - the one with most wins, or if there is no single such team, the strongest of the teams with most wins. (You may assume that there is a definite answer.)

This one's tricky. The naïve approach is just to count wins, but this can still lead to ties, as in example 4.

And it's possible without that final assumption that there are still degenerate cases: consider three teams, where A beats B, B beats C, and C beats A. But detecting that gets rather more complicated.

So instead step one is simply to count the wins, and step 2 looks as the inter-team scores of those with the joint highest win rate.

Perl, using sum from List::Util:

sub championteam($a) {

Latch counter for the maximum number of wins.

  my $maxw = 0;
  my @teamw;

Look at each team and count its wins.

  while (my ($i, $w) = each @{$a}) {
    my $wins = sum(@{$w});

If that's a new record, wipe the previous list.

    if ($wins > $maxw) {
      @teamw = ();
      $maxw = $wins;
    }

Append to the list, which will thus end up as a list of all the teams with highest number of wins.

    if ($wins == $maxw) {
      push @teamw, $i;
    }
  }

If there's only one in that list, it's the winner.

  if (scalar @teamw == 1) {
    return $teamw[0];
  }

Otherwise, compare each with the next to get the overall winner.

  my $bestt = $teamw[0];
  foreach my $rt (@teamw) {
    if ($a->[$rt][$bestt] == 1) {
      $bestt = $rt;
    }
  }
  $bestt;
}

Full code on github.