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