Weekly Challenge 196

Challenge, My solutions

Oh dear. I was about to commit my code for this weeks solution, and realized at that moment I didn't commit and push my code for last week!

Task 1: Pattern 132

Task

You are given a list of integers, @list. Write a script to find out subsequence that respect Pattern 132. Return empty array if none found.

Pattern 132 in a sequence (a[i], a[j], a[k]) such that i < j < k and a[i] < a[k] < a[j].

My solution

So there are two concerns I have with this task:

• In the second sentence, there doesn't seem to be a definition of what a actually is. I'm taking an educated guess that a is an alias of @list.
• In the examples "if more than one subsequence found then return the first". First is a very subjective term when it comes to returning a list.

For this task I used the combinations method from itertools (Python) or Algorithm::Combinatorics (Perl) to generate all combinations of positions (not values) from 0 to one less than the length of the array.

For each iteration, I (numerically) sort the numbers to ensure i < j < k. If a[i] < a[k] < a[j], then I print the result and exit. If there is no solution, I print ().

Examples

$ ./ch-1.py 3 1 4 2
(1, 4, 2)

$ ./ch-1.py 1 2 3 4
()

$ ./ch-1.py 1 3 2 4 6 5
(1, 3, 2)

$ ./ch-1.py 1 3 4 2
(1, 3, 2)

Task 2: Range List

Task

You are given a sorted unique integer array, @array.

Write a script to find all possible Number Range i.e [x, y] represent range all integers from x and y (both inclusive).

Each subsequence of two or more contiguous integers.

My solution

For this task, I iterate over a list (an array in Perl) until it is empty. For each iteration, I pop the first value off the list, and store this as start and end. I have an inner loop that adds one to end if the next value in the array is one more than the current end. If start and end are different, I store this in the solutions list.

Then it's just a mater of print the solutions list, or a message if no subsequences is found.

Examples

$ ./ch-2.py 1 3 4 5 7
[3,5]

$ ./ch-2.py 1 2 3 6 7 9
[1,3], [6,7]

$ ./ch-2.py 0 1 2 4 5 6 8 9
[0,2], [4,6], [8,9]