203: Quads and directory enquiries

Special quads

We are given an array of integers and asked to write a script to find the special quadruplets within the array. Special Quadruplets satisfy the following 2 rules:
--  nums[a] + nums[b] + nums[c] == nums[d]
--  a < b < c < d

The obvious way to do this is with 4 nested loops:

$last = scalar(@nums) - 1;
for $a (0 .. $last - 3) {
    for $b ($a + 1 .. $last - 2) {
        for $c ($b + 1 .. $last - 1) {
            for $d ($c + 1 .. $last) {
                if ($nums[$a] + $nums[$b] + $nums[$c] == $nums[$d]) {
                     ... we have an answer

The specification does not state whether the integers in the array are positive integers, but the examples contain only positive numbers. If negative numbers are to be allowed then I see no obvious way of optimising the above logic, but if we can assume that only positive integers are allowed then the task can be considerably speeded by:

- finding $max = the largest member of @nums
- abandoning the $b and $c searches if the sum so far exceeds $max:

for $a (0 .. $last - 3) {
    for $b ($a + 1 .. $last - 2) {
        next if $nums[$a] + $nums[$b] > $max;
        for $c ($b + 1 .. $last - 1) {
            next if $nums[$a] + $nums[$b] + $nums[$c] > $max;
            for $d ($c + 1 .. $last) {
                if ($nums[$a] + $nums[$b] + $nums[$c] == $nums[$d]) {
                 ... we have an answer

I tried this with @nums populated with 150 random numbers in the range 0 .. 50000 and the version without the $max optimisation took 7.81 seconds to find 65 quadruplets, and the optimised version took only 1.62 seconds.

You could possibly do even better by updating $max in the $a loop to be the largest remaining number (ie to the right of $a) , but that will take time and I doubt it would significantly speed things up.

<> My solution

Copy folder structure

We are given paths to two folders, $source and $target and are asked to write a script that recursively copies the directories in $source to $target, without copying any contained files.

Although this seems straightforward, the example leaves a few doubts. Firstly, I have assumed that $target already exists. Secondly, given the example, it's hard to see where recursion comes in as the example simply has 5 directories in $target, none of which has any subdirectories.

My script assumes that $target exists, and my script does recurse. I have illustrated that by adding $target/x/y/2/2m and $target/x/y/2/2n to the example.

I have a sub copy_dirs($source, $target) that creates a like-named directory in $target for any that exist in $source, and if any of these contain subdirectories it recurses with copy_dirs("$source/$subdir", "$target/$subdir").

Note that it would be very easy - one extra line - to copy the contained files as well.

<> My solution

202: Three odd things in the valleys

Three odd things

We are given an array of integers and asked for a script that prints 1 if there are three consecutive odd numbers in the given array, or otherwise print 0.

Perl can do that in one line:

say (join('', map({ $_ & 1 } @$test)) =~ m|111| ? 1 : 0);

The map converts @array to another array containing 1 for an odd entry and 0 for an even one. The join concatenates the elements of the resulting array into a string, and then it's just a case of looking for 111 in the string.

I often prefer not to use such a deeply nested statement as it's hard unravel what's happening, but this one isn't so hard.

• My solution

Find the valleys

Given a profile as a list of altitudes, we are asked to return the leftmost widest valley. A valley is defined as a subarray of the profile consisting of two parts: the first part is non-increasing and the second part is non-decreasing.  Either part can be empty.

The supplied profile is going to have one or more highs and one or more lows, where a high is defined as a point from which you can't reach another high without first going down and a low similarly is one where you can't reach another low without first ascending.  Any profile will therefore comprise an alternating sequence of highs and lows.

Note that highs and lows may be more than one point wide if two or more successive points are at the same height.

The phrase 'Either part can be empty' bears some thought.  Consider the sequence 6, 5, 4. If we take the phrase literally, the 5 can be considered as a valley with its second part empty. However, we are looking for the widest valley, and unless the profile only contains a single point, there will always be a valley with a width more than 1. 

So the only places where the phrase does have an impact is at the edges of the profile. Consider the sequence 1, 2, 3, 4, 3, 2.  This contains two valleys: 1, 2, 3, 4 with an empty first part, and 4, 3, 2 with an empty second part.

This also illustrates the fact that the highs - 4 in this case - may be part of 2 valleys, one to its left and one to its right. This is true even if the high is more than one point wide, eg 1, 2, 3, 4, 4, 4, 3, 2 where the valleys are 1, 2, 3, 4, 4, 4 and 4, 4, 4, 3, 2.

So having though about all that I decided the best way to proceed was to look for all the lows, and for each one stretch to the left and the right to determine its extent. I kept track of the widest valley seen so far and only updated that when I found a wider one, thus ensuring that I reported on the leftmost widest one.

This is a good example of a problem that is easy to describe, easy to solve by looking at the supplied profile, but not that easy to solve algorithmically.

• My solution