Weekly Challenge 087

Challenge

TASK #1 › Longest Consecutive Sequence

Task

You are given an unsorted array of integers @N.

Write a script to find the longest consecutive sequence.

My solution

Print 0 if none sequence found
This was relatively straight forward. Once I checked that we have one or more integer values, I then loop through a sorted list of numbers.

I have an array @current that stores the current run. This gets reset if the last number is not one less than the current number. I then set @largest to store the largest sequence of integers.

If @largest contains at least two numbers I print that array, otherwise I print zero.

On a programming note, I know that I can use if (@a < @b) {, but I still prefer to use if (scalar(@a) < scalar(@b) {. That way it is pretty clear want I meant, rather than Perl novices needed to know Perl will return the size of an array in a scalar context.

Examples

» ./ch-1.pl 100 4 50 3 2
Output: (2, 3, 4)

» ./ch-1.pl 20 30 10 40 50
Output: 0

» ./ch-1.pl 20 19 9 11 10
Output: (9, 10, 11)

TASK #2 › Largest Rectangle

Task

You are given matrix m x n with 0 and 1.

Write a script to find the largest rectangle containing only 1. Print 0 if none found.

My solution

This is similar to the 'Find Square' task of challenge 084.

I probably over comment my code in PWC tasks. Mainly as it helps others follow my logic. So using nothing other the comment lines, here's how I solved this task:

    # Process the input
    # Sanity check
    # Go through each rows and column
    # The top left of a square cannot be on the right or bottom row (hence -2)
            # No rectangle if this row has < 2 zeros
            # Find the maximum rectangle size
                # No more rectangles can be made from this starting point
                # Update the largest rectangle if this one is bigger
    # Display the output

Examples

» ./ch-2.pl '[ 0 0 0 1 0 0 ]' '[ 1 1 1 0 0 0 ]' '[ 0 0 1 0 0 1 ]' '[ 1 1 1 1 1 0 ]' '[ 1 1 1 1 1 0 ]'
[ 1 1 1 1 1 ]
[ 1 1 1 1 1 ]

» ./ch-2.pl '[ 1 0 1 0 1 0 ]' '[ 0 1 0 1 0 1 ]' '[ 1 0 1 0 1 0 ]' '[ 0 1 0 1 0 1 ]'
Output: 0

» ./ch-2.pl '[ 0 0 0 1 1 1 ]' '[ 1 1 1 1 1 1 ]' '[ 0 0 1 0 0 1 ]' '[ 0 0 1 1 1 1 ]' '[ 0 0 1 1 1 1 ]'
[ 1 1 1 1 ]
[ 1 1 1 1 ]