Perl Weekly Challenge: No music, only numbers

Posted on by

I was able to work on task 1 on Monday, but I haven’t been able to focus since. Here’s three solutions for task 1 of Perl Weekly Challenge 294.

Task 1: Consecutive Sequence

You are given an unsorted array of integers, @ints.

Write a script to return the length of the longest consecutive elements sequence. Return -1 if none found. The algorithm must runs in O(n) time.

Example 1

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

The longest consecutive sequence (1, 2, 3, 4).
The length of the sequence is 4.

Example 2

Input: @ints = (0, 6, 1, 8, 5, 2, 4, 3, 0, 7)
Output: 9

Example 3

Input: @ints = (10, 30, 20)
Output: -1

Approach

Ok, the requirement that the algorithm run in O(n) time immediately had me looking to see if there were any O(n) sorting algorithms, and I wound up finding the Counting Sort. Basically you do three loops: once through the input values to find the max value, then a second loop through the input values to set a counting array where the index corresponds to the value from the input array. Then you loop through the indexes of the counting array (0 .. max value in input array) to build an output array in order. I realized that if you didn’t care about sizing the counting array because you didn’t need to initialize all the values to 0, you could combine the first two loops and find the max value while you were counting the occurrences of the values.

But as I was whipping up a Raku implementation, my propensity to print intermediate results made me notice something else: with the input array
@ints: [10, 4, 20, 1, 3, 2]
the counting array wound up looking like this after the first loop:
@count: [Any, 1, 1, 1, 1, Any, Any, Any, Any, Any, 1, Any, Any, Any, Any, Any, Any, Any, Any, Any, 1]
All I had to do to get the length of the longest sequence was to loop once more through the array and count the longest number of consecutive non-Any (read: defined) elements.

Because this has two loops through arrays, one loop from 0 .. n (where n is the number of integers) and another loop from 0 .. k (where k is the maximum integer in the input array), the number of steps in the algorithm is O(n + k).

Raku

sub consecutiveSequence(@ints) {
  my @count;
  my $max = @ints.shift; # start with the first value as max
  @count[ $max ]++; # count that occurence
  for @ints -> $val { # count remaining value occurrences
    @count[ $val ]++; 
    $max = $val if $val > $max; # find the max value
  }
  my $maxSeq = 1;
  my $seq = 0;
  for 0 .. $max -> $i {
    if (@count[$i].defined && @count[$i] > 0) {
      $seq++; # we've found a consecutive value
      if ($seq > $maxSeq) {
        $maxSeq = $seq; # keep track of the longest
      }
    }
    else {
      $seq = 0; # the sequence broke
    }
  }
  # we want sequences longer than one value
  return $maxSeq > 1 ?? $maxSeq !! -1;
}

View the entire Raku script for this task on GitHub.

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

Example 2:
Input: @ints = (0, 6, 1, 8, 5, 2, 4, 3, 0, 7)
Output: 9

Example 3:
Input: @ints = (10, 30, 20)
Output: -1

BUT… there’s a less verbose way to count the values: using a Bag. This makes us go back to getting the maximum value from the @ints array in what is essentially another loop, but even though this makes the number of steps O(n + n + k), that’s still linear and essentially O(n).

sub consecutiveSequence(@ints) {
  my %count = @ints.Bag; # count the occurences
  my $max   = @ints.max; # find the max value
  my $maxSeq = 1;
  my $seq = 0;
  for 0 .. $max -> $i {
    if (%count{$i}.defined && %count{$i} > 0) {
      $seq++; # we've found a consecutive value
      if ($seq > $maxSeq) {
        $maxSeq = $seq; # keep track of the longest
      }
    }
    else {
      $seq = 0; # the sequence broke
    }
  }
  # we want sequences longer than one value
  return $maxSeq > 1 ?? $maxSeq !! -1;
}

Perl

However, for Perl I’m sticking with the longer version using arrays.

sub consecutiveSequence(@ints) {
  my @count;
  my $max = shift @ints; # start with the first value as max
  $count[ $max ]++; # count that occurence
  foreach my $val ( @ints ) { # count remaining value occurrences
    $count[ $val ]++; 
    $max = $val if $val > $max; # find the max value
  }
  my $maxSeq = 1;
  my $seq = 0;
  foreach my $i ( 0 .. $max )  {
    if (defined($count[$i]) && $count[$i] > 0) {
      $seq++; # we've found a consecutive value
      if ($seq > $maxSeq) {
        $maxSeq = $seq; # keep track of the longest
      }
    }
    else {
      $seq = 0; # the sequence broke
    }
  }
  # we want sequences longer than one value
  return $maxSeq > 1 ? $maxSeq : -1;
}

View the entire Perl script for this task on GitHub.

Python

In Python, however, I’m letting its equivalent to a Bag (the Counter class) do the heavy lifting.

from collections import Counter

def consecutiveSequence(ints):
  count  = Counter(ints) # count the values
  maxVal = max(ints) # find the max value
  maxSeq = 1
  seq = 0
  for i in range(maxVal + 1): # because range(n) goes from 0 to n-1
    if (count[i] > 0):
      seq += 1 # we've found a consecutive value
      if seq > maxSeq:
        maxSeq = seq # keep track of the longest
    else:
      seq = 0 # the sequence broke

  # we want sequences longer than one value
  return maxSeq if maxSeq > 1 else -1

View the entire Python script for this task on GitHub.

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