Robbie Hatley's Solutions, in Perl, for The Weekly Challenge #294 ("Consecutive Sequence" and "Next Permutation")

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

The Weekly Challenge for the week of 2024-11-03 through 2024-11-09 is #294.

The tasks for challenge #294 are as follows:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 294-1: Consecutive Sequence
Submitted by: Mohammad Sajid Anwar
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

I could first sort the array, but that would be O(n*log(n)), not O(n). Faster will be to make a hash and look for subsequences in that.

Robbie Hatley's Perl Solution to The Weekly Challenge 294-1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 294-2: Next Permutation
Submitted by: Mohammad Sajid Anwar
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 the decimal
representations of its integers.

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)

After doing some researching, I found a method of finding "the lexicographically 'next' permutation" of a list of strings which doesn't need to generate all of the permutations, just the "next". It goes like this:

1. Find the "pivot", which is the rightmost index i such that array[i] lt array[i-1].
2. Find the "successor", which is the rightmost index j such that array[j] gt array[i].
3. Swap the pivot and the successor.
4. Reverse the "suffix", which is the part to the right of the pivot.

Note that in the above I use "lt" and "gt" instead of "<" and ">". This is because the problem specifies the "lexicographical" next permutation, as opposed to the "numerical" next permutation which would have used "<" and ">" instead. Note, for example, that 123 is lexicographically less than 34 (because "1" is less than "3"), and "Robbie" is lexicographically less than "girl" (because "R" is less than "g", because the capital letters have lower ASCII/iso-8859-1/Unicode codepoints than the small letters). If the problem had specified "numerical" or "natural" or "Unicode collation", those would have resulted in different collation orders. But I'm interpreting "lexicographical" as meaning "Unicode codepoint order", which is what "lt" and "gt" do.

Robbie Hatley's Perl Solution to The Weekly Challenge 294-2

That's it for challenge 294; see you on challenge 295!