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