This is my response to The Weekly Challenge #294.
@ints.
O(n)
time.
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.
Input: @ints = (0, 6, 1, 8, 5, 2, 4, 3, 0, 7)
Output: 9
Input: @ints = (10, 30, 20)
Output: -1
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int && @ints.elems > 0, # [1]
:v(:$verbose));
my @sorted = @ints.sort; # [2]
my @unique = @sorted.unique; # [3]
say ": Sorted: @sorted[]" if $verbose;
say ": Unique: @unique[]" if $verbose;
my $current = @unique.shift; # [4]
my $count = 1; # [5]
my $max = 1; # [6]
for @unique -> $next # [7]
{
$count++ if $current +1 == $next; # [8]
$max = $count if $count > $max; # [9]
$current = $next; # [10]
}
say $max == 1 ?? -1 !! $max; # [11]
[1] Ensure that we get integers only, and at least one of them.
[2] Sort the values (lowest first).
[3] Getting rid of duplicates (with unique) allows
us to simply check that the next value is one higher than the current
one. The duplicates are useless anyway.
See docs.raku.org/routine/unique for more information about unique.
[4] Start with the first value.
[5] We have one consecutive value by now. (The challenge does not consider that a sequence, but we will fix that in [11].)
[6] The longest consecutive sequence we have found so far is also 1.
[7] Iterate over the remaining values (in the sorted list).
[8] Increase the counter if the next number literally is the next integer.
[9] Do we have a new maximum? If so, update it.
[10] Prepare for the next iteration of the loop.
[11] Print the maximum, except if the value is 1; then we print -1.
Running it:
$ ./consecutive-sequence 10 4 20 1 3 2
4
$ ./consecutive-sequence 0 6 1 8 5 2 4 3 0 7
9
$ ./consecutive-sequence 10 30 20
-1
Looking good.
With verbose mode:
$ ./consecutive-sequence -v 10 4 20 1 3 2
: Sorted: 1 2 3 4 10 20
: Unique: 1 2 3 4 10 20
4
$ ./consecutive-sequence -v 0 6 1 8 5 2 4 3 0 7
: Sorted: 0 0 1 2 3 4 5 6 7 8
: Unique: 0 1 2 3 4 5 6 7 8
9
$ ./consecutive-sequence -v 10 30 20
: Sorted: 10 20 30
: Unique: 10 20 30
-1
@ints.
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)
Input: @ints = (2, 1, 3)
Output: (2, 3, 1)
Input: @ints = (3, 1, 2)
Output: (3, 2, 1)
The challenge does not say what to do if we are given the highest
possible permutation. I have chosen to print -1 (in [2a] and [8]) in
that case, inspired by the program above.
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int && @ints.elems > 1, # [1]
:f(:$fast-fail), # [2]
:v(:$verbose));
my @a = @ints>>.Int; # [3]
if $fast-fail && [>=] @a { say -1; exit } # [2a]
my $end = @a.end; # [3]
for $end ... 1 -> $i # [4]
{
for $i -1 ... 0 -> $j # [4a]
{
if @a[$i] > @a[$j] # [5]
{
say ": index:$i -> @a[$i], index:$j -> @a[$j] (swap)" if $verbose;
my $n = @a[$i]; # [5a]
@a[$i] = @a[$j]; # [5a]
@a[$j] = $n; # [5a]
say "({ @a.join(", ") })"; # [6]
exit; # [6a]
}
elsif $verbose
{
say ": index:$i -> @a[$i], index:$j -> @a[$j] (skip)" if $verbose;
}
}
}
say "-1"; # [7]
[1] Ensure that we get integers, and at least 2 of them (as it is difficult to permutate one element).
[2] Use the -f option to fail faster, using the
Reduction Metaoperator [] with the Equal or Greater operator >=
to check that the list is sorted (highest value first).
See
docs.raku.org/language/operators#Reduction_metaoperators for more
information about the Reduction Metaoperator [].
[3] Get the index of the last element in the array.
See docs.raku.org/routine/end for more information about end.
[4] We are looking for one value that is greater than one to the left of it (so that we can sweap them). We do this with a double loop and the comparison in [5].
[5] Have we found two values to swap? If so, swap them [5a].
[6] Pretty print the modified array, and exit [6b].
[7] Unable to find anything swappable (and not alredy catched by [2a])? Report the error..
Running it:
$ ./next-permutation 1 2 3
(1, 3, 2)
$ ./next-permutation 2 1 3
(2, 3, 1)
$ ./next-permutation 3 1 2
(3, 2, 1)
Looking good.
With verbose mode:
$ ./next-permutation -v 1 2 3
: index:2 -> 3, index:1 -> 2 (swap)
(1, 3, 2)
$ ./next-permutation -v 2 1 3
: index:2 -> 3, index:1 -> 1 (swap)
(2, 3, 1)
$ ./next-permutation -v 3 1 2
: index:2 -> 2, index:1 -> 1 (swap)
(3, 2, 1)
Then we can look at a permuatation that we cannot get the better of (i.e. the next permutation):
$ ./next-permutation -v 3 2 1
: index:2 -> 1, index:1 -> 2 (skip)
: index:2 -> 1, index:0 -> 3 (skip)
: index:1 -> 2, index:0 -> 3 (skip)
-1
$ ./next-permutation -v -f 3 2 1
-1
This one shows that the loops do not actually do the right thing:
$ ./next-permutation -v 1 3 2
: index:2 -> 2, index:1 -> 3 (skip)
: index:2 -> 2, index:0 -> 1 (swap)
(2, 3, 1)
The correct sequence is (2, 1, 3).
Let us fix that.
File: next-permutation-sort
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int && @ints.elems > 1,
:f(:$fast-fail),
:v(:$verbose));
my @a = @ints>>.Int;
if $fast-fail && [>=] @a { say -1; exit }
my $end = @a.end;
for $end ... 1 -> $i
{
for $i -1 ... 0 -> $j
{
if @a[$i] > @a[$j]
{
say ": index:$i -> @a[$i], index:$j -> @a[$j] (swap)" if $verbose;
my $n = @a[$i];
@a[$i] = @a[$j];
@a[$j] = $n;
@a[$j+1 .. *] = @a[$j+1 .. *].sort if $i > $j +1; # [1]
say "({ @a.join(", ") })";
exit;
}
elsif $verbose
{
say ": index:$i -> @a[$i], index:$j -> @a[$j] (skip)" if $verbose;
}
}
}
say "-1";
[1] If we swap two adjacent numbers, we are good. But if they are not adjacent, we must sort the part of the array coming after the first swapped value.
Some examples:
$ ./next-permutation-sort 1 2 3
(1, 3, 2)
$ ./next-permutation-sort 2 1 3
(2, 3, 1)
$ ./next-permutation-sort 3 1 2
(3, 2, 1)
$ ./next-permutation-sort 3 2 1
-1
$ ./next-permutation-sort 1 3 2
(2, 1, 3)
$ ./next-permutation-sort 1 10 9 8 7 6 5 4 3 2 1 0
(2, 0, 1, 1, 3, 4, 5, 6, 7, 8, 9, 10)
$ ./next-permutation-sort 1 0 10 9 8 7 6 5 4 3 2 1
(1, 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10)
And that's it.