Preface

I was discussing Sum Pair problem among our friends and after few minutes, I bragged that this problem is so easy, it can be done in one line. ‘What is so confusing about it?’. Others were not convinced. I then challenged myself to write it in one line.

This is how I achieved it.

The problem

In Sum Pair (or Pair Sum), we have to find 2 numbers in a list such that their sum is highest among all possible combinations in that list.

eg. Take the list: [1, 0, -1, -2, 5]. the sum of 1 & 5 (=6) is the highest. So, our result will be (1,5). Note that we have to return the pair of numbers, not their sum.

The solution is simple. We just have to iterate over all possible combinations and find the pair with highest sum.

Their combinations would be

(1,0), (1,-1), (1,-2), (1,5), (0,-1), (0,-2), (0,5), (-1,-2), (-1,5), (-2,5)

Their sums would be

[1, 0, -1, 6, -1, -2, 5, -3, 4, 3]

And as 6 is the highest, we print/return (1,5)

Limitations:

  1. Any built-in language functions are prohibited. This eliminates functions such as max, min, sum etc.
  2. Sorting of the list is not allowed.

These are the restrictions which those nasty recruiters go for.

The naive approach

We can simply iterate using two for loops and maintain a variable for maximum pair at each iteration.

# Declare a tuple with negative infinity.
# This will help us compare with other tuples
# without declaring values such as (-9999, -9999).
# Ain't Python nice!

maximum = (float('-inf'), float('-inf'))

for i in range(len(l) - 1):
    for j in range(i+1, len(l)):
        if l[i]+l[j] > maximum[0]+maximum[1]:
            maximum = (l[i], l[j])

print(maximum)

Can we write this in one line? 🤔

I tried my best but I wasn’t able to find any way to rewrite the above in a single line. I then tried a different approach.

The composable functions approach

I have been learning functional programming and I am quite fascinated with the pattern of composability of functions in FP. Maybe this will help me write it in one line.

So lets try this out in Python!

The approach would be to divide the problem into multiple composable functions. The logical steps for this would be:

Find pair with max sum < get all pairs < input list

We can use combinations function in python to get all possible non repeating 2-pair combination of a list

from itertools import combinations
l = [1, 0, -1, -2, 5]

# This function returns a generator with all combinations
all_combn = lambda lst: combinations(lst, 2)

Then we just need to find out max among the list of combinations. For this, we use reduce function.

from functools import reduce
compare = lambda a, b: a if sum(a) > sum(b) else b
max_pair = lambda lst: reduce(compare, lst)

We will get our answer by composing the above functions.

print(max_pair(all_combn(l)))

And to write it in one line, we will just put the functions inline and use some import statement trickery

import functools, itertools; functools.reduce(lambda a, b: a if sum(a) > sum(b) else b, itertools.combinations([1, 0, -1, -2, 5], 2))

We did it! 🎉 🥳

But, you said to not use any builtin functions! Right.

The composable functions approach (without using builtin functions)

To achieve this, we just have to rewrite reduce, combinations and sum functions by ourselves.

We can sum up a list using recursion. Recursion is basically bread and butter in FP. We take first element in list and go on recursing until list is empty.

list_sum = lambda lst: lst[0] + list_sum(lst[1:]) if lst else 0

Rewriting combinations is a bit tricky. To find combinations, we take first element and pair it with the rest of the elements in the list. Then we repeat this with second element and so forth until only single element is left in the list. That is when we stop.

We split this approach in 2 parts/functions. One will pair up an element to each element in a list. The other will take an element and a list, and send it to the previous function.

# We do not need recursion as list comprehension is simple enough.
# This will return a list of pairs. Here a is paired up with all elements
# in lst
pair = lambda a, lst: [(a, i) for i in lst] if lst else []

Next to generate all pairs, we do a recursive approach similar to list_sum

all_pair = lambda lst: pair(lst[0], lst[1:]) + all_pair(lst[1:]) if lst else []

We can write the above two statements in a single line

all_pair = lambda lst: [(lst[0], i) for i in lst[1:]] + all_pair(lst[1:]) if lst else []

Reduce can also be rewritten in 2 parts. One will compare 2 elements and return the one with max sum and other will iterate over the list passing 2 elements to the former function.

# To compare 2 pairs
max_pair = lambda a,b: a if list_sum(a) > list_sum(b) else b

max_sum_pair = lambda lst: max_pair(lst[0], max_sum_pair(lst[1:])) if lst else []

Our functions are ready. To get answer, do as follows:

max_sum_pair(all_pair(l))

Now we just have to rewrite it in single line

list_sum can be inlined as below. The problem here that we have is list_sum is a recursive function. So, inline will be a problem as we have to declare and use it in a single line. Here, walrus operator comes to our rescue:

max_pair = lambda a,b: a if ((list_sum := lambda lst: lst[0] + list_sum(lst[1:]) if lst else 0), list_sum(a) > list_sum(b))[1] else b

The trick here is that we have created a tuple in if condition block. First value in tuple declares a function with walrus := operator which allows us to use it immediately. Second value in tuple uses that function to compare and get a boolean value. The [1] after the tuple gets the second value to be evaluated by the if block.

Similarly, max_sum_pair can be rewritten as below. Another trick up our sleeve is we can directly call a lambda function by wrapping lambda in () and directly passing parameters. This is useful if we only want to use our function once. (Unlike above where list_sum is called twice) eg. (lambda ...)(...params)

max_sum_pair = lambda lst: (lambda a,b: a if ((list_sum := lambda lst: lst[0] + list_sum(lst[1:]) if lst else 0), list_sum(a) > list_sum(b))[1] else b)(lst[0], max_sum_pair(lst[1:])) if lst else []

Now in the final step, we inline all_pair function in max_sum_pair function. As max_sum_pair is recursive, we use the walrus := operator.

(max_sum_pair := lambda lst: (lambda a,b: a if ((list_sum := lambda lst: lst[0] + list_sum(lst[1:]) if lst else 0), list_sum(a) > list_sum(b))[1] else b)(lst[0], max_sum_pair(lst[1:])) if lst else [])((all_pair := lambda lst: [(lst[0], i) for i in lst[1:]] + all_pair(lst[1:]) if lst else [])([1, 0, -1, -2, 5]))

If this above line is readable to you, give yourself a pat on your back. 😅

Here is a block separated version. Hope this is more readable.

(
    max_sum_pair := lambda lst: (     # max_sum_pair function
        lambda a,b: a if              # max_pair function & ternary if
        (                             # a tuple
            (                         # 1st element in tuple, list_sum function
                list_sum := lambda lst: lst[0] + list_sum(lst[1:]) if lst else 0
            ),
            list_sum(a) > list_sum(b) # 2nd element, a boolean expression
        )[1]                          # Get 2nd element from tuple
        else b                        # else block of ternary if
    )                                 # max_pair definition ends
    (                                 # immediately call the max_pair function
        lst[0], max_sum_pair(lst[1:]) # and pass 2 parameters w/ recursion
    ) if lst else []                  # Recursion guard
)(                                    # max_sum_pair definition ends & immediately call it
    (                                 # all_pair definition starts
        all_pair := lambda lst: [(lst[0], i) for i in lst[1:]] + all_pair(lst[1:]) if lst else []
    )
    ([1, 0, -1, -2, 5])               # immediately call all_pair with the list
)                                     # the result of all_pair is sent to max_sum_pair

# wrap everything in print if not using interactive notebook

Have a good day! 🙃