Perl Weekly Challenge: Week 294
Challenge 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 run 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
An easy way to solve this problem would be to sort @ints and then check them one by one to find sequences
but that would take longer than O(n) time. The fastest way to randomly access a set of elements is via a Hash.
So the first step is to create one from @ints. (The values can be anything; all that matters is that a key exists
for every element.)
my %nums = @ints.map({ $_ => True });
We need to store the longest sequence found so far.
my $longest = 0;
Now for each element of @ints...
for @ints -> $i {
...we check if there is an element before it. If there was, we are in the middle of a sequence, not the start so we can skip to the next element.
unless %nums{$i - 1} {
If this is a new sequence, we store the current element we are on and the current length of the sequence.
my $current = $i;
my $length = 1;
While the next element is one greater than the current one, we make it the current element and increment the length of the sequence.
while %nums{$current + 1} {
$current++;
$length++;
}
At the end of the sequence we compare its' length to $longest and if it is longer it becomes the new value of $longest
$longest = ($longest, $length).max;
}
}
After going through all elements of @ints if we have managed to find a sequnce longer than 1, we print its length otherwise -1.
say $longest > 1 ?? $longest !! -1;
my %nums = map { $_ => 1 } @ints;
my $longest = 0;
foreach my $i (@ints) {
unless ($nums{$i - 1}) {
my $current = $i;
my $length = 1;
while ($nums{$current + 1}) {
$current++;
$length++;
}
if ($length > $longest) {
$longest = $length;
}
}
}
say $longest > 1 ? $longest : -1;
Challenge 2:
Next Permutation
You are given an array of integers,
@ints.Write a script to find out the next permutation of the given array.
The next permutation of an array of integers is the next lexicographically greater permutation of its integer.
Example 1
Input: @ints = (1, 2, 3)
Output: (1, 3, 2)
Permutations of (1, 2, 3) arranged lexicographically:
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Example 2
Input: @ints = (2, 1, 3)
Output: (2, 3, 1)
Example 3
Input: @ints = (3, 1, 2)
Output: (3, 2, 1)
This challenge couldn't be easier in Raku as it has a .permutations() method that does all the work. We get
the list of integers from the command-line then run .permutations() on it and select the next (i.e. second) permutation
calculated by it. The rest of the code is just so the output can be printed out nicely in the same style as in the spec.
say q{}, @*ARGS.permutations[1].join(q{, }), q{)}
Perl, alas, doesn't have a standard permutations() function. In previous challenges I used some code which I originally got
from perlfaq4 but it is awkward to use and
doesn't use more modern feeatures of Perl. So I updated it like this:
sub permute(@arr) {
my @permutations;
my @idx = keys @arr;
while ( push @permutations, [@arr[@idx]] ) {
my $p = scalar @idx - 1;
while ($idx[$p-1] >= $idx[$p]) {
--$p;
}
my $q = $p;
if (!$q) {
last;
}
push @idx, reverse splice @idx, $p;
while ($idx[$p-1] > $idx[$q]) {
++$q;
}
@idx[$p-1,$q]=@idx[$q,$p-1];
}
return @permutations;
}
Now it is more like the Raku equivalent.
my @permutations = permute @ints;
And the rest of the code is just as simple as in Raku.
say q{(}, (join q{, }, @{ $permutations[1] }), q{)};