Sum Pair Algorithm in One Line of Python

Preface

I was discussing the Sum Pair problem among our friends and a random train of thought got me thinking if it can be done in single line of python.

The Problem

The goal is to find 2 numbers in a list such that their sum is highest among all possible combinations in that list.

For [1, 0, -1, -2, 5], the answer is (1, 5) with a sum of 6.

This can simply be done in a few operations but to one up the challenge, I decided to use no max, min, sum, or any other builtins.

First Approach: Naive

This is with two loops which track the maximum pair:

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)

This works perfectly but it is not in one line.

Second Approach: Composable Functions

In this we generate all the pairs and reduce to the best one via lambdas.

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

Now this is a single line approach.

Third Approach: Without any built-ins

I would reimplement everything from scratch in the second approach:

# Find the sum of the list
list_sum = lambda lst: lst[0] + list_sum(lst[1:]) if lst else 0

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

# Find the max sum in a list of pairs
max_pair = lambda a, b: a if list_sum(a) > list_sum(b) else b

To collapse these into a single expression, each function needs to be defined inline where it’s used. The walrus operator (:=) lets you assign a name to a lambda right inside the expression that calls it:

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 []

Final one-liner:

(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, congratulations! You are a python expert!

Here is a bit more readable version.

(
    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 repl or notebook