I know, it’s been a while since the last time I published something on my blog. The main reason is that in my spare time – apart from private life – I’ve been committed to organize events and activities in Italy and also to work on a personal project with a great friend of mine. Anyway, I found some time to share a new blog post I hope you will like.

This article is also part of my series C++ in Competitive Programming.

In the very first installment of this series, I showed an example whose solution amazed some people. Let me recall the problem: we have to find the **minimum difference between any two elements in a sorted sequence of numbers**. For example:

[10, 20, 40, 100, 200, 300, 1000]

The minimum difference is 10, that is 20-10. Any other combination is greater. Then, I showed an unrolled solution for such problem (not the most amazing one!):

Imagine there is always at least one element in the sequence. Note that we calculate **elems[i+1]-elems[i]** for each i from 0 to length-1, meanwhile, we keep track of the maximum of such differences. I see a pattern, do you?

Before getting to the point, let me show you another example. **We want to calculate the number of equal adjacent characters in a string**:

ABAAACCBDBB

That is 4:

ABA**AA**C**C**BDB**B**

Again, here is a solution:

We compare **s[i]** with **s[i-1]** and, meanwhile, we count how many **true**s we get. Careful readers will spot a little difference from the previous example: at each step, we access s[i] and s[i-1], not s[i+1] and s[i]. I’ll develop this subtlety in a moment. Now, please, give me another chance to let you realize the pattern yourself, before I elaborate more.

This time we have two vectors of the same size, containing some values and we want to calculate the maximum absolute difference between any two elements. Imagine we are writing a test for a numerical computation, the first vector is our baseline (expectation) and the second vector is the (actual) result of the code under test. Here is some code:

Here we access the ith-elements of both the vectors at the same time. Is that similar to the other examples?

It’s time to get to the point, although you are already there if you have read the intro of this series – if you have not, please stay here and don’t spoil the surprise yourself!

Actually, there is not so much difference among the examples I showed. They are all obeying the same pattern: given two sequences, the pattern combines every two elements from input sequences at the same position using some function and accumulates these intermediate results along the way.

Actually, in functional programming, this pattern is the composition of three different patterns:

zip | map | fold

**zip** makes “pairs” from input sequences, **map** applies a function to each pair and returns some result, **fold** applies an operation to reduce everything to a single element. A picture is worth a thousand words:

For simplicity, imagine that zip and map are combined together into a single operation called **zipWith**.

Now we have two customization points:

- which function
*zipWith*uses to combine each pair, and - which function
*fold*uses to reduce each result of*zipWith*to a single element.

The general case of this pattern operates on any number of sequences, making a *tuple* for each application of zip (e.g. imagine we zip the rows of a matrix, we get its columns).

In C++ we have an algorithm that (partially) implements this pattern: inner_product. I said “partially” just because it accepts only two ranges and for this reason I say “pairs of elements”, not tuples – as in the general case. In C++17’s parallel STL, *inner_product* is made in parallel by transform_reduce (be aware of the additional requirements).

In the future we’ll do such things by using new tools that will be incorporated into the standard: *ranges*. For now, *inner_product* is an interesting and (sometimes) understimated tool we have. Regardless you are going to use such pattern in real-world code, I think that understanding when this pattern applies is mindblowing. If you regularly practice competitive programming as I do, you have the opportunity to recognize many patterns to solve your problems. In the last years I have found several cases when this pattern worked smoothly and I am sharing here a few.

The simplest form of *inner_product* takes two ranges of the same length and a starting value, and it calculates the sum of the products of each pair. It’s literally an inner product between two vectors. *inner_product* has two additional customization points to replace “product” and “sum” as we wish.

Let’s have some fun.

It’s time to code the solutions to the previous challenges in terms of *inner_product*. I start from the latter.

I recall that we want to find the maximum absolute difference of two vectors of double. In this case we replace “product” with “absolute difference” and “sum” with “max”. Or, we combine each pair by calculating the absolute difference and we keep track of the maximum along the way. I stress the fact that we reduce the combined pairs along the way and not at the end: *inner_product* is a single-pass algorithm (e.g. it works on stream iterators).

Here is the code:

I tend to use standard function objects as much as possible. They are just clearer, shorter and (should be) well-known. Thinking a bit more we come up with:

Better than the other? It’s debatable, I leave the choice to you.

The other two challenges are on a single sequence, aren’t they? Does the pattern still apply?

It does.

Zipping two distinct ranges is probably more intuitive, but what about zipping a sequence with itself? We only have to pass correct iterators to *inner_product*. We want to combine **s[i]** with **s[i-1]**. **zipWith** should use **operator==** and fold **operator+**. For the first sequence we take S from the second character to the last character. For the second sequence we take S from the first character to the second last character. That is:

- S.begin() + 1, S.end()
- S.begin(), S.end()-1

We have to pass the first three iterators to *inner_product*:

We zip with **equal_to** which uses **operator==** under the hood and we fold with **plus<>** which applies **operator+**. As you see, not having to specify the second sequence’s boundary is quite handy. If the solution is not clear, I hope you will find this picture useful:

When **equal_to** is called, the left hand side is S[i] and the right hand side is S[i-1]. In other words, the first range is passed as the first parameter to *zipWith* and the second range as the second parameter.

Careful readers will spot a subtle breaking change: **the solution is not protected against an empty string anymore**. Advancing an iterator that is not incrementable (e.g. *end*) is undefined behavior. We have to check this condition ourself, if we need. This example on HackerRank never fall into such condition, so the solution is just fine.

Finally, in the first exercise we are requested to calculate the minimum difference between any two elements in a sorted sequence of numbers. I intentionally wrote **elems[i+1]-elems[i]** and not **elems[i]-elems[i-1]**. Why? Just to show you another form of the same pattern. This one I like less because the call to *inner_product* is more verbose:

We can apply the other pattern by (mentally) turning the loop into **elems[i] – elems[i-1]**:

As before, the solution is not protected against an empty sequence. You understand that zipping a sequence on itself (by shifting it) is never protected against an empty range.

This pattern works in all the examples above just because **the stride between two elements is 1**. If it was greater, it would have failed – I know, we can use boost::strided or such but I don’t mind here. Basically, we have processed adjacent elements in a “window” of size 2. There are scenarios where this window can be larger and *inner_product* still applies.

As an example we take Max Min on HackerRank. This problem is very close to calculating the minimum difference between any two elements in a sorted sequence of numbers. It states: **Given a list of N non-unique integers, your task is to select K integers from the list such that its unfairness is minimized. **If

*(x1,x2,…,xk)*are

*K*numbers selected from the list, the

**unfairness**is defined as

**:**

*max(x1, x2, …, xk) – min(x1, x2,…, xk)*

A possible solution to this problem consists in sorting the sequence and applying *zipWith | fold* as we did in the very first example. The only difference is that **the distance between the two elements we zip together is K-1**:

Do not misunderstand: *inner_product* still steps by one every time and still combines elements in pairs. It’s just that we zip the sequence with itself by shifting it by *K-1* positions and not by just 1. Here is what I mean:

As you see, although the size of the window is K, *inner_product* still works in the same way as before. The pairs that it conceptually creates (remember that the first sequence is shifted by *K-1* positions) are depicted below:

**This works only if K is less than or equal to N **(and N has to be at least 1).

The pattern fits this problem because we turn the sequence in a particular structure: we **sort **it. We have to select K elements and we know that *min(x1,…,xk)* is **x1** and *max(x1,…,xk)* is **xk**. This is just an effect of sorting. So we just check all these possible windows, incrementally, by using only **x1** and **xk**. We may ignore erverything inside the window. Another interesting property is that the first range passed to *inner_product* is always greater (the problem states that all elements are distinct) than the second, for each iteration. This is why we can use *minus<>* for *zipWith*. If we wanted the opposite, we would have changed the order of the iterators or we would have iterated backwards. Using algorithms make variations simpler than rolling a for loop.

Recap for the pragmatic C++ competitive coder:

- In C++,
**(zip | map | fold)**on**two**ranges is implemented by**inner_product:**- set the first callable to customize
*fold*(*plus*by default); - set the second callable to customize (
*zip | map)*– combined in a single operation (*multiplies*by default); - the order of the iterators matter: the first range is the left hand side of
*zipWith*, the second range is the right hand side;

- set the first callable to customize
- zipping a sequence on itself is just the same pattern;
- be aware it won’t work with ranges shorter than the number of positions we shift the sequence by (e.g. 1 in the first 3 examples);

- praciting recognizing and understanding coding patterns is food for the brain.

Reblogged this on josephdung.

I enjoyed this article. Although I knew inner product before, I only used it for real inner products.

But hell, there are even more obscure functions like valarray.

Thanks! Yes valarray is quite undocumented but sometimes can be very powerful.