Coding Challenge: Return N serial numbers given list of valid chars in each position

CodingChallenge_SerialNumbers.py

"""Coding challenge: Serial numbers | Chris Brozdowski, January 28th 2023

Goal: Create N serial numbers given N and a list of valid characters for each position 
    in the resulting serial. 

Assumptions:
    1. Each item in the list will be a string.
    2. If a provided string is empty, there are no valid characters for this position. 
        Output should exclude this position.
    3. If N exceeds the number of unique serials, only report unique serials.

Example:
    params: ["!@#", "abc"]
    n_requested: 4
    return ['!a', '!b', '!c', '@a']

Results: I landed on 3 different implementations.
    1. Itertools.product provides an iterator 
    2. Physical carry-over mechanisms on clocks inspired a counter approach
    3. Memory allocation inspired a repetition-based approach: each position repeats
       N times where N is the product of all posibilities from positions to the right.
"""
from typing import Callable, List


def clean_params(params: List[str]) -> List[str]:
    """Return the set of params with non-empty strings

    Arguments:
        params (List[str]): list of strings

    Returns:
        List[str]: provided params without empty strings
    """
    return [p for p in params if p]


def max_params(params: List[str]) -> int:
    """Return N of combinations of individual characters across provided list of strings"""
    from numpy import product as np_product

    return np_product([len(p) for p in params])

    """Use built-in itertools to report serial numbers"""


def _via_itertools(params: List[str], n_requested: int) -> List[str]:
    """Use built-in itertools to report serial numbers"""
    from itertools import product as iter_product

    params = clean_params(params)
    output = []
    full_product = iter_product(*[[*p] for p in params])
    for _ in range(min(n_requested, max_params(params))):
        output.append("".join(next(full_product)))
    return output


def incriment_clock(clock: List[int], maxes: List[int]):
    """Given a clock, add one and check for carry-over based on maxes

    Note: Clock resets to zeros when first position reaches maximum

    Args:
        clock (List[int]): List of numbers for clock positions
        maxes (List[int]): Maximum value of each position

    Returns:
        List[int]: Clock after adding 1, implementing carry-overs
    """
    clock[-1] += 1
    carry = 0
    for instance, max, index in zip(
        clock[::-1], maxes[::-1], range(len(clock) - 1, -1, -1)
    ):
        instance += carry
        carry, instance = (1, 0) if instance >= max else (0, instance)
        clock[index] = instance
    return clock


def _via_clock(params: List[str], n_requested: int, start=0) -> List[str]:
    """Use clock-like counter where each position clicks a carry-over"""
    output = []
    params = clean_params(params)
    clock, maxes = [0 for _ in params], [len(p) for p in params]
    for _ in range(start):
        _ = incriment_clock(clock, maxes)
    n_requested = min(n_requested, max_params(params))
    while n_requested > start:
        this_serial = ""
        for index, param in enumerate(params):
            this_serial += param[clock[index]]
        output.append(this_serial)
        clock = incriment_clock(clock, maxes)
        n_requested -= 1
    return output


def _via_allocation(params: List[str], n_outputs: int) -> List[str]:
    """Repeat characters based on params index. Add to pre-allocated list"""
    params = clean_params(params)
    n_outputs = min(n_outputs, max_params(params))
    output = [""] * n_outputs
    len_previous_params = 1

    for param in reversed(params):
        repeated_string = "".join([char * len_previous_params for char in param])
        repeated_string *= (n_outputs // len(repeated_string)) + 1
        for output_index in range(n_outputs):
            output[output_index] = repeated_string[output_index] + output[output_index]
        len_previous_params *= len(param)
    return output


def provide_serials(
    params: List[str], n_outputs: int, method: Callable = _via_itertools
) -> List[str]:
    """Returns a list of n_outputs given list of characters for each position

    Args:
        params (List[str]): List of valid characters for each output position
        n_requested (int): Number of requested outputs
        method (Callable): Means of generating serials. Default _via_itertools

    Returns:
        List[str]: Valid output strings
    """
    return method(params, n_outputs)


def run_content_check(
    param_list: List[List[str]] = [
        ["!@#", "abc"],
        ["abcdefghij", "abcdefghij", "-/", "0123"],
        ["", "1", "ab"],
    ],
    n_requested: int = 4,
    expected_outcomes: List[List[str]] = [
        ["!a", "!b", "!c", "@a"],
        ["aa-0", "aa-1", "aa-2", "aa-3"],
        ["1a", "1b"],
    ],
):
    for params, expected_outcome in zip(param_list, expected_outcomes):
        assert (
            _via_itertools(params, n_requested)
            == _via_clock(params, n_requested)
            == _via_allocation(params, n_requested)
            == expected_outcome
        )
    return True


def run_equivalence_checks(
    param_list: List[List[str]] = [
        ["!@#", "abc"],
        ["abcdefghij", "abcdefghij", "-/", "0123"],
        ["", "1", "ab"],
    ],
    n_requested_list: List[int] = [0, 5, 20, 100, 1000],
):
    for params in param_list:
        for n_requested in n_requested_list:
            assert (
                _via_itertools(params, n_requested)
                == _via_clock(params, n_requested)
                == _via_allocation(params, n_requested)
            )
    return True