Skip to content

Instantly share code, notes, and snippets.

@CBroz1
Last active January 28, 2023 17:18
Show Gist options
  • Save CBroz1/39be3125b609ed4b41b27e31986bb9c7 to your computer and use it in GitHub Desktop.
Save CBroz1/39be3125b609ed4b41b27e31986bb9c7 to your computer and use it in GitHub Desktop.
Coding Challenge: Return N serial numbers given list of valid chars in each position
"""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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment