Perl Weekly Challenge: Points? What’s the diff?

Posted on by

With Perl Weekly Challenge 339 being “Max Diff” and “Peak Point”, I started to think that “Point” was my hook into a musical theme, and that made me think of one of my favorite artists, David Wilcox. So please enjoy his song Turning Point while we solve this week’s tasks…

Task 1: Max Diff

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).

Example 1

Input: @ints = (5, 9, 3, 4, 6)
Output: 42

Pair 1: (9, 6)
Pair 2: (3, 4)
Product Diff: (9 * 6) - (3 * 4) => 54 - 12 => 42

Example 2

Input: @ints = (1, -2, 3, -4)
Output: 10

Pair 1: (1, -2)
Pair 2: (3, -4)

Example 3

Input: @ints = (-3, -1, -2, -4)
Output: 10

Pair 1: (-1, -2)
Pair 2: (-3, -4)

Example 4

Input: @ints = (10, 2, 0, 5, 1)
Output: 50

Pair 1: (10, 5)
Pair 2: (0, 1)

Example 5

Input: @ints = (7, 8, 9, 10, 10)
Output: 44

Pair 1: (10, 10)
Pair 2: (7, 8)

Approach

After looking at the examples, it became obvious that the maximum difference comes from multiplying the two values with the largest absolute values and the two values with the smallest absolute values, and then computing their difference.

Raku

At first, I was thinking about using Raku’s max routine’s ability to have a function to determine the maximum value, but then I would have to tackle how to extract the value from the list, and I decided to just be lazy and use sort instead.

sub maxDiff(@ints is copy) {
  my ($a, $b, $c, $d) =
    @ints.sort({ abs($^a) cmp abs($^b) })[0, 1, *-2, *-1];
  abs(($a * $b) - ($c * $d))
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @ints = (5, 9, 3, 4, 6)
Output: 42

Example 2:
Input: @ints = (1, -2, 3, -4)
Output: 10

Example 3:
Input: @ints = (-3, -1, -2, -4)
Output: 10

Example 4:
Input: @ints = (10, 2, 0, 5, 1)
Output: 50

Example 5:
Input: @ints = (7, 8, 9, 10, 10)
Output: 44

Perl

Using sort also worked well for the Perl solution.

sub maxDiff(@ints) {
  my ($A, $B, $C, $D) =
    +(sort { abs($a) <=> abs($b) } @ints)[0, 1, -2, -1];
  abs(($A * $B) - ($C * $D))
}

View the entire Perl script for this task on GitHub.

Python

In Python, sorted lets you specify a function that is used to extract a comparison key from each element in the list.

def max_diff(ints):
  ints = sorted(ints, key=abs)
  a, b = ints[0:2]
  c, d = ints[-2:]
  return abs((a * b) - (c * d))

View the entire Python script for this task on GitHub.

Elixir

And the Elixir solution looks very much like the Python one. Enum.sort/2 takes a function that can be used to order the list and returns a sorted list, which we then save to extract the first two and last two elements from. And because abs is in Kernel, we don’t have to prefix it with a module name.

def max_diff(ints) do
  ints = Enum.sort(ints, &(abs(&1) <= abs(&2)))
  {a, b} = {Enum.at(ints,  0), Enum.at(ints,  1)}
  {c, d} = {Enum.at(ints, -2), Enum.at(ints, -1)}
  abs((a * b) - (c * d))
end

View the entire Elixir script for this task on GitHub.

Task 2: Peak Point

You are given an array of altitude gain.

Write a script to find the peak point gained.

Example 1

Input: @gain = (-5, 1, 5, -9, 2)
Output: 1

start: 0
1st change:  0 + (-5) = -5
2nd change: -5 + 1    = -4
3rd change: -4 + 5    = 1
4th change:  1 + (-9) = -8
5th change: -8 + 2    = -6

max(0, -5, -4, 1, -8, -6) = 1


Example 2
Input: @gain = (10, 10, 10, -25)
Output: 30

start: 0
1st change:  0 + 10    = 10
2nd change: 10 + 10    = 20
3rd change: 20 + 10    = 30
4th change: 30 + (-25) = 5

max(0, 10, 20, 30, 5) = 30

Example 3

Input: @gain = (3, -4, 2, 5, -6, 1)
Output: 6

start: 0
1st change:  0 + 3    = 3
2nd change:  3 + (-4) = -1
3rd change: -1 + 2    = 1
4th change:  1 + 5    = 6
5th change:  6 + (-6) = 0
6th change:  0 + 1    = 1

max(0, 3, -1, 1, 6, 0, 1) = 6

Example 4

Input: @gain = (-1, -2, -3, -4)
Output: 0

start: 0
1st change:  0 + (-1) = -1
2nd change: -1 + (-2) = -3
3rd change: -3 + (-3) = -6
4th change: -6 + (-4) = -10

max(0, -1, -3, -6, -10) = 0

Example 5

Input: @gain = (-10, 15, 5)
Output: 10

start: 0
1st change:   0 + (-10) = -10
2nd change: -10 + 15    = 5
3rd change:   5 + 5     = 10

max(0, -10, 5, 10) = 10

Approach

First, a bit of background: my wife refers to these blog entries as my “recipe blog”, because I don’t just write the solution and be done with it. I write about how I’m thinking about the solution, I write about the music that the solution makes me think of, I write about how the solution makes me feel about my mother, without whom I wouldn’t even be writing these solutions. It’s like those recipe blogs where you have to scroll through a bunch of stuff you don’t care about to get to “what are the ingredients and what temperature should my oven be set to, and for how long?”

So last night I was prepping to work on these solutions by reading through the tasks on my phone. I had been puzzling over how to interpret “You are given an array of altitude gain” and looking in particular at example 4, when I just suddenly mumbled to myself “Oh, it’s a reduction.”

My wife perked up and said “What?”

“Oh, uh, I’m working on the recipe blog. I just realized this is a reduction.”

“Yeah,” she replied. “That doesn’t help. You know what a reduction is, right? I still don’t know if you’re talking about cooking or not.”

“Oh, right! No, in programming you reduce a list of values by repeatedly applying an operator to the list until you only have one value. For instance, if you reduce 1, 2, 3, 4, 5 by addition, you wind up with the value 15.”

“Ah! Ok, that makes sense,” she said and then went back to editing video of actors portraying The Drifters…

But, yes, this is a reduction: we start out with the “altitude” 0 and we then add each of the values in @gain to it repeatedly, and keep track of what the maximum value is. We could produce the explanatory text from the examples, but that will just make the code bigger.

Raku

For the Raku solution, I’m taking advantage of the List routine reduce taking a function as an argument, not just an operator, so I’m able to sum the values and keep track of the max value all at once…

sub peakPoint(@gain) {
  my $max = 0; # we start at 0
  @gain.reduce({ my $s = $^a + $^b; $max = max($max, $s); $s });
  $max;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @gain = (-5, 1, 5, -9, 2)
Output: 1

Example 2:
Input: @gain = (10, 10, 10, -25)
Output: 30

Example 3:
Input: @gain = (3, -4, 2, 5, -6, 1)
Output: 6

Example 4:
Input: @gain = (-1, -2, -3, -4)
Output: 0

Example 5:
Input: @gain = (-10, 15, 5)
Output: 10

Perl

But in Perl, the List::AllUtils module has a routine reductions that returns the intermediate values along with the final result. This means we could just use List::AllUtils’ max to grab the maximum value from that list.

But when I first ran my solution, I got the result -1 from example 4. I realized immediately that the first value returned by reductions was the first value in the input list, which was supported by the example in the documentation:

reduce     { "$a-$b" }  "a".."d"    # "a-b-c-d"
reductions { "$a-$b" }  "a".."d"    # "a", "a-b", "a-b-c", "a-b-c-d"

Fortunately, all I had to do to fix it was put a 0 at the beginning of the list. The value won’t affect the end result (since we’re starting from 0 anyway), and it means we get the maximum value of 0 if all the altitude gains are negative.

use List::AllUtils qw( max reductions );

sub peakPoint(@gain) {
  max reductions { $a + $b } 0, @gain;
}

View the entire Perl script for this task on GitHub.

Python

Python, however, had a wrinkle: the reduce function in functools takes either a function or a lambda as a first argument, and modifying a variable from inside a lambda is a tricky proposition, so I punted and defined a function with a global variable so we could maintain the maximum altitude across calls.

from functools import reduce

def add_max(x, y):
  global max_alt
  max_alt = max(max_alt, x+y)
  return x+y

def peak_point(gain):
  global max_alt
  max_alt = 0 # initialize global to 0
  reduce(add_max, gain)
  return max_alt

View the entire Python script for this task on GitHub.

Elixir

In Elixir, I was able to go back to the maximum value being stored in a value passed into and out of the Enum.map_reduce/3, but I kept it calling a function like I did in Python so the code would be more readable.

def add_max(x, {sum, max}) do
  sum = sum + x
  max = Enum.max([max, sum])
  { x, {sum, max} }
end

def peak_point(gain) do
  {_, {_, max}} = Enum.map_reduce(gain, {0, 0}, &add_max/2)
  max
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-339/packy-anderson

Leave a Reply