TASK #1 › Longest Consecutive Sequence
Submitted by: Mohammad S Anwar
You are given an unsorted array of integers @N.
Write a script to find the longest consecutive sequence. Print 0 if none sequence found.
Example 1:
Input: @N = (100, 4, 50, 3, 2)
Output: (2, 3, 4)
Example 2:
Input: @N = (20, 30, 10, 40, 50)
Output: 0
Example 3:
Input: @N = (20, 19, 9, 11, 10)
Output: (9, 10, 11)
Perl Solution
Imperative Approach
I've done the same task with common lisp and golang, then I guess that I naturally follow the same logic I used in both language.
- sort the number
- compare between consecutive member in the list
- concatenate the list if they are right next to each other
- if not, start a new sequence
and I need to add handy dummy member at the tail of the list
here is the code.
use strict; use warnings;
use v5.26;
# note: no sanity check !!
my @sorted = sort { $a <=> $b } @ARGV;
push @sorted, $sorted[-1]+2; # dummy
my @longest_seq_list = ();
my $longest_size = 0;
my $prev = shift @sorted;
my @curr_seq = ($prev);
for my $curr (@sorted) {
if ( $curr - $prev == 1 ) {
push @curr_seq, ($curr); # concat. current seq
} elsif ( $curr == $prev ) { # skip
} else { # update longest
my $curr_size = scalar @curr_seq;
if ( $curr_size > $longest_size ) {
$longest_size = $curr_size;
@longest_seq_list = ( [ @curr_seq ] );
} elsif ( $curr_size == $longest_size ) {
push @longest_seq_list, [ @curr_seq ];
}
@curr_seq = ($curr);
}
$prev = $curr;
}
if ( $longest_size > 0 ) {
say "longest size: ".$longest_size;
say "total ".(scalar @longest_seq_list)." sequencies found.";
for my $seq (@longest_seq_list) {
say "[", join(", ", @$seq), "]";
}
}
It is simple challenge, so I tried learn more about raku today.
Raku Solution
Sorting
Easy!, and we don't need to add 'sort( $^a <=> $^b )' because @n are all already IntStr instance.
unit sub MAIN (*@n where { @n ~~ Int, @n.elems > 0 } );
@n.sort.say
Produce
as we go through the list, we can produce the trace of our data.
the simple example of produce is that maximum value at each step.
> my @n = 3, 2, 4, 5, 9;
[3 2 4 5 9]
> @n.produce( -> \a, \b { max( a, b) } )
(3 3 4 5 9)
but I need some more information to keep at every step and decided to keep a list of numbers as we go.
> @n = -3, 1, 3, 2, -2, 4, 6, 7, -1, 4
> @n.sort.map({[$_]})
([-3] [-2] [-1] [1] [2] [3] [4] [4] [6] [7])
and if a and b is consecutive write down the linked numbers or start over new one.
...
(@n.sort.map({[$_]})).
produce( -> \a, \b {
b.first - a.tail == 1
?? a.append(b.first).clone
!! b.clone
} ).say
...
and result looks like:
([-4] [-4 -3] [-4 -3 -2] [-4 -3 -2 -1] [1] [1 2] [1 2 3] [1 2 3 4] [6] [6 7])
Now classify the number by length and grep the element has maximum size and say!
...
classify( {.elems} ).
max.
value.
map( *.say );
...
Final Code
unit sub MAIN (*@n where { @n ~~ Int, @n.elems > 0 } );
(@n.sort.map({[$_]})).
produce( -> \a, \b {
b.first - a.tail == 1
?? a.append(b.first).clone
!! b.clone
} ).
classify( {.elems} ).
max.
value.
map( *.say );
Happy Coding!!
I spent too much time on common-lisp and golang.
I'm so sorry to say that I'll skip blog about task #2.
May Perl and Raku be with you!!
🐪PWC🦋
Top comments (0)