Perl Weekly Challenge: One Challenge, Twice Large

Posted on by

You didn’t know what the Weekly Challenge was / Until you met a hacker on a Github bus / I got there in the nick of time / Before he got his code across your git commit line…

Yeah, yeah, it’s a stretch, but it’s an excuse to pull out Ian Hunter’s Once Bitten, Twice Shy (yes, Ian Hunter).

So you got the rhythm, you got the speed, you got Perl Weekly Challenge 292.

(sorry I’m only doing one challenge this week; it’s been a rough week)

Task 1: Twice Largest

You are given an array of integers, @ints, where the largest integer is unique.

Write a script to find whether the largest element in the array is at least twice as big as every element in the given array. If it is return the index of the largest element or return -1 otherwise.

Example 1

Input: @ints = (2, 4, 1, 0)
Output: 1

The largest integer is 4.
For every other elements in the given array is at least twice as big.
The index value of 4 is 1.

Example 2

Input: @ints = (1, 2, 3, 4)
Output: -1

The largest integer is 4.
4 is less than twice the value of 3, so we return -1.

Approach

Part of me wants to do this in a single pass through the array. To do that, I think I’d need to maintain two variables besides the index: a largest value (largest) and a second largest (second) value. There’s a trivial case where the array is one element long, which cannot meet the “at least twice as big as every [other] element in the given array” part of the criterial.

So if there’s more than 1 element in the array, we start with largest equal to the index of the first element and second equal to -1 (which can’t be an array index). Then we process the rest of the list; if the value at the current index is larger than the value at index largest, we push the index in largest down to second and put the current index in largest, if the value at the current index is smaller than the value at index largest but larger than the value at index second (or the index of second is -1), just replace second with the current index. Then, once we’ve processed all the values in the array, if ints[largest] >= 2 * ints[second], we return largest, otherwise we return -1.

Raku

This is pretty much what I wrote above, except in Raku.

sub twiceLargest(@ints) {
  return -1 if @ints.elems <= 1;
  my $largest = 0;
  my $second = -1;
  for 1 .. @ints.end -> $i {
    if (@ints[$i] > @ints[$largest]) {
      $second  = $largest;
      $largest = $i;
    }
    elsif ($second < 0 || @ints[$i] > @ints[$second]) {
      $second = $i;
    }
  }
  return @ints[$largest] >= 2 * @ints[$second] ?? $largest !! -1;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @ints = (2, 4, 1, 0)
Output: 1

Example 2:
Input: @ints = (1, 2, 3, 4)
Output: -1

Example 3:
Input: @ints = (1)
Output: -1

Example 4:
Input: @ints = (4, 2, 1)
Output: 0

Perl

Translating to Perl doesn’t change much.

sub twiceLargest(@ints) {
  return -1 if @ints <= 1;
  my $largest = 0;
  my $second = -1;
  for my $i ( 1 .. $#ints ) {
    if ($ints[$i] > $ints[$largest]) {
      $second  = $largest;
      $largest = $i;
    }
    elsif ($second < 0 || @ints[$i] > @ints[$second]) {
      $second = $i;
    }
  }
  return $ints[$largest] >= 2 * $ints[$second] ? $largest : -1;
}

View the entire Perl script for this task on GitHub.

Python

And translating into Python doesn’t change much.

def twiceLargest(ints):
  if len(ints) <= 1:
    return -1
  largest = 0
  second = -1
  for i in range(1, len(ints)):
    if ints[i] > ints[largest]:
      second  = largest
      largest = i
    elif second < 0 or ints[i] > ints[second]:
      second = i
  return largest if ints[largest] >= 2 * ints[second] else -1

View the entire Python script for this task on GitHub.

Elixir

I’m using a recursive traverseList/5 function to simulate looping over the list of ints by index, and having it return values for largest and second.

  def traverseList([], _, _, largest, second), do:
    {largest, second}

  def traverseList([val | rest], i, ints, largest, second) do
    {largest, second} = cond do
      val >= Enum.at(ints, largest) ->
        second  = largest
        largest = i
        {largest, second}

      second == -1 || val > Enum.at(ints, second) ->
        second = i
        {largest, second}

      true -> {largest, second}
    end
    traverseList(rest, i+1, ints, largest, second)
  end

  def twiceLargest(ints) when length(ints) <= 1, do: -1

  def twiceLargest(ints) do
    {_, rest} = List.pop_at(ints, 0) # remove the first element
    {largest, second} = traverseList(rest, 1, ints, 0, -1)
    if Enum.at(ints, largest) >= 2 * Enum.at(ints, second) do
      largest
    else
      -1
    end
  end

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-292/packy-anderson