Weekly Challenge: Maximum climb

Weekly Challenge 339

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Max Diff

Task

You are given an array of integers having four or more elements.

Write a script to find two pairs of numbers from this list (four numbers total) so that the difference between their products is as large as possible.

In the end return the max difference.

With Two pairs (a, b) and (c, d), the product difference is (a * b) - (c * d).

My solution

This task has really challenged me. I've come up with a solution that works, but am not happy with it. Mohammad praised me last week with not "just brute-forcing an answer". This week I have failed :-/

The objective is to find the pairs that represent the lowest and highest product. If I take the list -4 -10 2 0, the lowest value is -8 (-4 × 2) and the highest value is 40 (-4 × -10). However this uses the -4 value twice, and thus is not going to work. I was thinking of ways to solve this, but haven't thought of any that are good. I'm going to be interested in reading how other Team PWC members solved this.

The approach I took is to find all combinations of 4 digits from the input list. In Python, this is done with the combinations function from itertools. The Algorithm::Combinatorics module provides the same functionality in Perl.

For each combination I calculate the maximum absolute difference between the three possible combinations of pairs (1 2, 3 4; 1 3, 2 4; and 1 4, 2 3). If this is higher than any previous maximum, I update the solution variable.

def max_diff(ints: list) -> int:
    solution = 0

    # Compute all combinations of 4 integers
    for c in combinations(ints, 4):
        # Calculate the maximum difference for this combination
        diff = max(
            abs((c[0] * c[1]) - (c[2] * c[3])),
            abs((c[0] * c[2]) - (c[1] * c[3])),
            abs((c[0] * c[3]) - (c[1] * c[2])),
        )
        if diff > solution:
            solution = diff

    return solution

Maybe this is the best solution. Even with a list of 100 items, there are less than 4 million combinations, which can be computed pretty quickly.

Examples

$ ./ch-1.py 5 9 3 4 6
42

$ ./ch-1.py 1 -2 3 -4
10

$ ./ch-1.py -3 -1 -2 -4
10

$ ./ch-1.py 10 2 0 5 1
50

$ ./ch-1.py 7 8 9 10 10
44

Task 2: Peak Point

Task

You are given an array of altitude gain.

Write a script to find the peak point gained.

My solution

This is relatively straight forward so doesn't need much explanation. I have two variables current_altitude records the current altitude while the peak records the highest altitude. Both values start at 0.

I then loop over the input list with a variable gain. For each iteration, I increment the current_altitude value with gain. If this is higher than the current peak variable, I update peak with the new altitude.

Finally, I return the peak value.

def peak_point(gains: list) -> int:
    current_altitude = 0
    peak = 0

    for gain in gains:
        current_altitude += gain
        if current_altitude > peak:
            peak = current_altitude

    return peak

Examples

$ ./ch-2.py -5 1 5 -9 2
1

$ ./ch-2.py 10 10 10 25
55

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

$ ./ch-2.py -1 -2 -3 -4
0

$ ./ch-2.py -10 15 5
10