Find all pairs of natural numbers whose sum is 12

Question

I have been given the following task to complete. I am not sure if my solution is the most efficient. Are you able to take a look and suggest any changes?

task:

An application that finds all pairs of natural numbers whose sum is 12. Once a number is used to create a pair it cannot be part of another pair.

Input values:

Set of N natural numbers with values from 0 to 12

[1,12,4,6,8,5,7,12,11,6,7,5,0]

Output Values:

Pairs of numbers that add up to 12. The pair can be returned in any order. The first number of the pair should be no greater than second. example:

[0,12],[1,11],[4,8],[6,6],[5,7],[6,6]

There are some technical requirements for solution:

• Remember about clean code.
• Think about the computational and memory complexity of the proposed solution.
• Try to solve the task in accordance with the object-oriented programming paradigm.
• data should be read and written from/to a text file. The file format is arbitrary.

my solution:

I would like to start by describing my solution. Due to the unknown number of elements in the input file, I wanted to avoid nested loops because I don't know if this will be a quick solution with several million elements. So all works as follows:

1. Reading data from .txt files and converting values to int.
2. Create a list containing all possible pairs that can occur. Here is the condition that the first number must be no greater than the second number.
3. Based on the created pattern of pairs and counted elements from the input file count_pairs function creates a dictionary, where the key is the pair and the value is the number of occurrences of that pair.
4. expand the grouped elements to a form that will be saved in the file.
5. save to file Everything works fine, but I'm afraid I've overthought this solution and there is the easiest way to do it.

from collections import Counter
import re

def read_data_to_list(file_name: str) -> list:
    file = open(file_name, "r")
    file_content = file.read()
    result = re.findall(r"\d+", file_content)
    result = [int(element) for element in result]
    return result


def possible_pairs(input_data: list, target_num: int) -> list:
    input_set = set(input_data)
    result = []
    for element in list(input_set):
        if target_num - element in input_set:
            if element <= target_num - element:
                result.append((element, target_num - element))
    return result


def count_pairs(counted_elements: dict, possible_pairs_list: list) -> dict:
    result = {}
    for pair in possible_pairs_list:
        if pair[0] == pair[1]:
            occurring_pairs = int(counted_elements[pair[0]] // 2)
            result.update({pair: occurring_pairs})
        else:
            occurance_first_element = counted_elements[pair[0]]
            occurance_second_element = counted_elements[pair[1]]
            occurring_pairs = min(occurance_first_element, occurance_second_element)
            result.update({pair: occurring_pairs})
    return result


def create_output_list(input_dict: dict) -> list:
    result = []
    for key, value in input_dict.items():
        for each in range(value):
            result.append(list(key))
    return result


if __name__ == "__main__":
    input_list = read_data_to_list("test.txt")
    possible_pairs_list = possible_pairs(input_list, target_num=12)
    count_elements = Counter(input_list)
    all_pairs = count_pairs(count_elements, possible_pairs_list)
    output = create_output_list(all_pairs)

    with open("output.txt", "w") as file:
        file.write(str(output))
```

Answer 1

Reading the input. The format of the input file is not clarified in great detail, but it looks like the same format one would get from printing a Python list of integers. Which means that its format is also the same as JSON.

import json

def read_input_values(file_path):
    with open(file_path) as fh:
        return json.load(fh)

Writing the output. Why not stick with JSON?

def write_output_pairs(file_path, pairs):
    with open(file_path, 'w') as fh:
        json.dump(pairs, fh)

Calculating the pairs with a Counter. The code you wrote in possible_pairs() is reasonable. In fact, something quite similar can do all of the work, allowing us to delete count_pairs() entirely. Here's the key: rather than flattening the input values down to a set, as your current code does, we can accurately represent the inventory of values using a Counter. Once we have that inventory, we just iterate over each value and its corresponding count, determine how many of its mate we have, and then add the pairs to the result, deducting from the inventory as we go.

from collections import Counter

def compute_pairs(values, target):
    pairs = []
    c = Counter(values)
    for v1, n1 in c.items():
        # How many of the mate do we have?
        v2 = target - v1
        n2 = c.get(v2, 0)
        # Store the pairs, deducting them from the inventory.
        # If either n1 or n2 are less than 1, the loop does nothing.
        for _ in range(min(n1, n2)):
            pairs.append(sorted([v1, v2]))
            c[v1] -= 1
            c[v2] -= 1
    return pairs

Usage illustration. You should get in the habit of putting all code inside of functions, leaving only a main() call after the main-guard, as shown below. Even better than what I've done here would be to take the file paths and target value from the user via command-line arguments (from args), rather than hardcoding them. Parameterizing the script in that way gives you much more flexibility, allowing you to easily switch among different inputs and scenarios as you work on the script.

import sys

def main(args):
    values = read_input_values('test.txt')
    pairs = compute_pairs(values, 12)
    write_output_pairs('output.txt', pairs)
    print(pairs)

if __name__ == '__main__':
    main(sys.argv[1:])

Answer 2

The spec is wrong, at least in its example data. There's one too many [6,6] and one too few [5,7].

The spec asks you to think about the computational and memory complexity of the proposed solution but I don't see any evidence of that. Unless I've missed something sneaky, your solution is O(n) in both time and space, disregarding your re.findall which may throw a wrench in that. It's easy to avoid regular expressions since the file format is yours to define, so you can do simple newline splitting.

As @Mast pointed out, you've entirely missed the request to try to solve the task in accordance with the object-oriented programming paradigm. A grain of salt: I probably wouldn't use OOP here if it weren't specifically asked for.

for pair in possible_pairs_list: should be tuple-unpacked to something like for a, b in possible_pairs_list so that you don't have to repeatedly write pair[0].

occurance is spelled occurrence.

Suggested

from typing import Iterable, Iterator
from collections import Counter


class SumPairs:
    def __init__(self, numbers: Iterable[int], total: int) -> None:
        self.counts = Counter(numbers)
        self.total = total

    def __iter__(self) -> Iterator[tuple[int, int]]:
        # Inspired by FMc:
        # https://codereview.stackexchange.com/a/276411/25834

        # This method is non-destructive to the instance
        counts = self.counts.copy()

        while counts:
            a, n_a = counts.popitem()
            b = self.total - a
            if a == b:
                n = n_a//2
            else:
                n_b = counts.pop(b, 0)
                n = min(n_a, n_b)
                if a > b:
                    a, b = b, a
            yield from ((a, b),) * n


class SumPairReader:
    def __init__(self, filename: str) -> None:
        self.filename = filename

    def __enter__(self) -> 'SumPairReader':
        self.file = open(self.filename)
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        self.file.close()

    def __iter__(self) -> Iterator[int]:
        for line in self.file:
            yield int(line)


class SumPairWriter:
    def __init__(self, filename: str) -> None:
        self.filename = filename

    def __enter__(self) -> 'SumPairWriter':
        self.file = open(self.filename, 'w')
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        self.file.close()

    @staticmethod
    def format(pairs: Iterable[tuple[int, int]]) -> Iterable[str]:
        for a, b in pairs:
            yield f'{a} {b}\n'

    def write(self, pairs: Iterable[tuple[int, int]]) -> None:
        self.file.writelines(self.format(pairs))


def main() -> None:
    with SumPairReader('in.txt') as reader:
        pairs = SumPairs(reader, total=12)
    with SumPairWriter('out.txt') as writer:
        writer.write(pairs)


if __name__ == '__main__':
    main()

Depending on how much your teacher cares about memory complexity, it is possible to replace the above with a streamed version that has a best-case memory complexity of O(1) and a lower average complexity:

class SumPairs:
    def __init__(self, numbers: Iterable[int], total: int) -> None:
        self.numbers = numbers
        self.total = total

    def __iter__(self) -> Iterator[tuple[int, int]]:
        counts = defaultdict(int)

        for a in self.numbers:
            b = self.total - a
            if counts[b]:
                counts[b] -= 1
                if a > b:
                    a, b = b, a
                yield a, b
            else:
                counts[a] += 1