Implement Luhn-based card validation and inference

Question

Implement a set of utilities for credit-card validation and inference using the Luhn checksum algorithm and standard brand patterns.

Brand patterns:

• VISA — 16 digits, starts with 4
• MASTERCARD — 16 digits, starts with 51, 52, 53, 54, or 55
• AMEX — 15 digits, starts with 34 or 37

Tasks:

1. Given a digit-only card-number string, return whether it passes the Luhn checksum and, if valid, which brand it belongs to. Possible outputs: ["INVALID_CHECKSUM", "VISA", "MASTERCARD", "AMEX"].
2. Extend task 1 so that a number passing the Luhn check but matching none of the three known brand patterns is labeled "UNKNOWN".
3. Allow the input to contain * wildcards, each standing for any single digit (e.g., "****424242424242"). Return the count of possible valid card numbers per brand, formatted as a list of "BRAND,count" pairs (e.g., ["VISA,1", "MASTERCARD,10"]). A single pattern may be consistent with more than one brand, so report a count for every brand it could represent. Note: once a brand is fixed, the number of valid completions equals 10^(number_of_asterisks - 1), because Luhn fixes one degree of freedom.
4. Error-correction: given an observed string whose trailing ? indicates that exactly one error occurred to the preceding digits — one of {changed digit, removed digit, added digit, or transposition of two adjacent digits} (e.g., "4333220284765319?") — enumerate every original card number (and its brand) that was valid before the error and that could have produced the observed string.

Luhn Card Validation + Brand Identification

Given a digit-only card-number string, return whether it passes the Luhn checksum and, if it passes, which of the three known brands it belongs to.

Brand patterns:

• VISA: 16 digits, starts with 4
• MASTERCARD: 16 digits, starts with 51, 52, 53, 54, or 55
• AMEX: 15 digits, starts with 34 or 37

Luhn checksum: walking the digits right-to-left, double every second digit; if a doubled value exceeds 9, subtract 9. The number is valid iff the total is divisible by 10.

Return one of: "INVALID_CHECKSUM", "VISA", "MASTERCARD", "AMEX". A number that fails Luhn, OR passes Luhn but matches none of the three brand patterns, returns "INVALID_CHECKSUM" in this task.

Constraints

• Input contains only ASCII digit characters 0-9.
• Length is not guaranteed to be 15 or 16; non-matching lengths simply fail the brand check.
• Empty string is Luhn-valid (sum 0) but matches no brand -> INVALID_CHECKSUM.

Examples

Example 1

Input: ('4242424242424242',)
Output: 'VISA'

Explanation: 16 digits, starts with 4, Luhn-valid -> VISA (a real Visa test card).

Example 2

Input: ('5555555555554444',)
Output: 'MASTERCARD'

Explanation: 16 digits, starts with 55, Luhn-valid -> MASTERCARD.

Hints

1. Write a reusable luhn_ok(t) helper first; tasks 2-4 all reuse it.
2. Process digits right-to-left and double every second one, subtracting 9 when the doubled digit exceeds 9.
3. Brand identification only happens AFTER Luhn passes. A Luhn-valid number with an unknown prefix/length is still INVALID_CHECKSUM in this first task.

Card Validation with UNKNOWN Fallback

Extend the previous classifier: a number that PASSES the Luhn checksum but matches none of the three known brand patterns (VISA / MASTERCARD / AMEX) should be labeled "UNKNOWN" rather than rejected.

Return one of: "INVALID_CHECKSUM", "VISA", "MASTERCARD", "AMEX", "UNKNOWN".

• Fails Luhn -> "INVALID_CHECKSUM".
• Passes Luhn and matches a brand -> that brand.
• Passes Luhn but matches no brand -> "UNKNOWN".

Constraints

• Input contains only ASCII digit characters 0-9.
• The only behavioral change from task 1 is the final fallthrough: UNKNOWN instead of INVALID_CHECKSUM when Luhn passes but no brand matches.

Examples

Example 1

Input: ('4242424242424242',)
Output: 'VISA'

Explanation: Brand match takes precedence over the UNKNOWN fallback.

Example 2

Input: ('5555555555554444',)
Output: 'MASTERCARD'

Explanation: Starts with 55, 16 digits, Luhn-valid -> MASTERCARD.

Hints

1. This is task 1 with a single line changed: the final return becomes 'UNKNOWN' instead of 'INVALID_CHECKSUM'.
2. INVALID_CHECKSUM is reserved exclusively for numbers that FAIL the Luhn check.
3. A 16-digit Luhn-valid number starting with 6 (e.g. a Discover card) is UNKNOWN here, since only VISA/MASTERCARD/AMEX patterns are recognized.

Wildcard Card Counting (Analytic, Not Brute Force)

The input may contain '*' wildcards, each standing for any single digit (e.g. "****424242424242"). Return the count of possible Luhn-valid card numbers per brand, as a list of "BRAND,count" pairs (e.g. ["VISA,1", "MASTERCARD,10"]).

A single pattern may be consistent with more than one brand, so report a count for every brand it could represent. Emit brands in the order VISA, MASTERCARD, AMEX, skipping any brand with a count of 0.

Do NOT brute-force 10^k completions. Count analytically:

• A pattern can only be a given brand if its length matches and every FIXED prefix digit is compatible with that brand's prefix rule.
• A wildcard in a prefix position is constrained to the allowed prefix values (e.g. VISA's leading '*' has exactly 1 choice: '4'); multiply those choices together.
• Among the remaining FREE wildcard positions, the Luhn constraint fixes one degree of freedom: the number of completions = (product of prefix-wildcard choices) * 10^(free_wildcards - 1), provided at least one wildcard is free.
• If there are zero free wildcards, the count is the number of prefix-wildcard fills whose fully-determined number is Luhn-valid (1 if the single completion is valid, else 0).

Constraints

• Input contains digits 0-9 and '*' wildcards only.
• Number of wildcards can be large; 10^(free-1) must be computed analytically, never enumerated.
• Counts can exceed 32-bit range; Python ints are unbounded, but Java/C++ solutions would need BigInteger for very large patterns.
• Brands are emitted in fixed order VISA, MASTERCARD, AMEX; zero-count brands are omitted.

Examples

Example 1

Input: ('****424242424242',)
Output: ['VISA,100', 'MASTERCARD,50']

Explanation: 16-long, 4 leading stars. VISA: pos0 star -> 1 choice (4), 3 free -> 110^2=100. MASTERCARD: pos0 -> 1 (5), pos1 -> 5 (1-5), 2 free -> 510^1=50. AMEX needs length 15, excluded.

Example 2

Input: ('4*4242424242424*',)
Output: ['VISA,10']

Explanation: Fixed first digit 4 -> only VISA. 2 stars, pos0 fixed; one star is a free non-prefix position -> 10^(2-1)=10. Only the last star is free (the second char is a non-prefix position too) so f=2 -> 10.

Hints

1. Treat each brand independently: first check the length matches, then check every fixed prefix digit is compatible.
2. A wildcard inside the prefix region is NOT free: it is limited to the brand's allowed prefix values (VISA leading '' -> 1 choice; MasterCard second '' -> 5 choices).
3. Luhn is a single linear (mod-10) constraint, so it removes exactly one degree of freedom: with f free wildcards the valid completions number 10^(f-1). With zero free wildcards, just enumerate the (tiny) prefix-wildcard fills and Luhn-check each.

Single-Error Card Reconstruction

An observed string ends with a trailing '?' meaning exactly one error happened to the preceding digits. The error is one of: changed digit, removed digit, added digit, or transposition of two adjacent digits (e.g. "4333220284765319?").

Enumerate every ORIGINAL card number that (a) was Luhn-valid and matched a real brand (VISA / MASTERCARD / AMEX) before the error, and (b) could have produced the observed string via exactly one such error.

Invert each operation against the observed digits (drop the trailing '?'):

• Changed digit: at each position, try the other 9 digits.
• Removed digit (original was one longer): insert each of 10 digits at every gap.
• Added digit (original was one shorter): delete each position.
• Adjacent transposition: swap each adjacent pair back.

Deduplicate the candidates, keep only those that are Luhn-valid AND map to a brand, and return them sorted ascending as "NUMBER,BRAND" strings.

Constraints

• The observed string ends with a single trailing '?'.
• Exactly one error occurred; the candidate generator inverts all four edit types and deduplicates (different edits can yield the same original).
• Only Luhn-valid candidates that map to a real brand (VISA/MASTERCARD/AMEX) survive; UNKNOWN-shaped numbers are discarded.
• Results are sorted ascending by the numeric string and formatted as "NUMBER,BRAND".

Examples

Example 1

Input: ('4242424242424252?',)
Output: ['4242424242424242,VISA', '4242424242424259,VISA', '4242424242424952,VISA', '4242424242427252,VISA', '4242424242494252,VISA', '4242424242724252,VISA', '4242424249424252,VISA', '4242424272424252,VISA', '4242424942424252,VISA', '4242427242424252,VISA', '4242494242424252,VISA', '4242724242424252,VISA', '4249424242424252,VISA', '4272424242424252,VISA', '4942424242424252,VISA']

Explanation: A near-valid 16-digit observed string; the true original 4242424242424242 is recovered by a single changed-digit inversion, alongside other VISA originals one edit away.

Example 2

Input: ('371449635398431?',)
Output: ['371449635398431,AMEX']

Explanation: The observed (minus '?') is already a valid 15-digit AMEX; the only branded Luhn-valid reconstruction within one edit is itself.

Hints

1. Strip the trailing '?' first, then generate candidates for all four inverse operations into a set so duplicates collapse.
2. Insertion (to undo a removed digit) and deletion (to undo an added digit) change the length by one - that is how a 15-digit AMEX or 16-digit VISA original can emerge from an off-by-one observed string.
3. Re-validate each candidate with the SAME Luhn + brand rules from tasks 1-2; keep only the ones that are both Luhn-valid and brand-matched.

Solution

The grader is checking a reusable Luhn + brand-pattern core, then four layered behaviors: exact classification, the UNKNOWN fallback, an analytic (non-brute-force) wildcard count that respects prefix constraints and the single Luhn degree of freedom (count = prefix_choices × 10^(free_wildcards-1)), and a complete single-error inversion that re-validates every reconstructed candidate against Luhn and the brand rules.

Core building blocks

Luhn checksum. Walk the digits from right to left. Double every second digit; if a doubled value exceeds 9, subtract 9 (equivalently, sum its two digits). The number is valid when the total sum is divisible by 10.

def luhn_ok(s: str) -> bool:
    total, alt = 0, False
    for ch in reversed(s):
        d = ord(ch) - 48
        if alt:
            d *= 2
            if d > 9:
                d -= 9
        total += d
        alt = not alt
    return total % 10 == 0

def brand(s: str):
    n = len(s)
    if n == 16 and s[0] == '4':
        return 'VISA'
    if n == 16 and s[:2] in {'51','52','53','54','55'}:
        return 'MASTERCARD'
    if n == 15 and s[:2] in {'34','37'}:
        return 'AMEX'
    return None

Task 1 — validate + identify brand

def classify(s: str) -> str:
    if not luhn_ok(s):
        return 'INVALID_CHECKSUM'
    b = brand(s)
    return b if b else 'INVALID_CHECKSUM'  # task 1 only knows the three brands

Return INVALID_CHECKSUM if the checksum fails. If it passes, return the matching brand.

Task 2 — add UNKNOWN

Same as task 1, but a Luhn-valid number that fits none of the three patterns is UNKNOWN rather than rejected:

def classify2(s: str) -> str:
    if not luhn_ok(s):
        return 'INVALID_CHECKSUM'
    return brand(s) or 'UNKNOWN'

Task 3 — wildcard counting (do NOT brute-force)

Naively filling k asterisks is 10^k candidates — too slow for large k. Count analytically per brand:

1. Filter by length and prefix. A pattern can only be a given brand if its length matches and every fixed (non-*) prefix digit is compatible with that brand's prefix rule. If a prefix position is a *, it must be filled by an allowed prefix value, which constrains the count (e.g., VISA's first digit must be 4: that * has exactly 1 choice, not 10).
2. Count Luhn-valid completions. Among the remaining free wildcard positions, the Luhn constraint fixes the residue of the digit sum mod 10. Exactly one residue class works, so for each brand, the number of valid completions = (product of the choices for prefix-constrained wildcards) × 10^(free_wildcards - 1) — provided at least one wildcard is free to absorb the checksum. (If a brand is already fully determined and there are a asterisks all free, this reduces to 10^(a-1).) If there are zero free wildcards, count is 1 iff the single fully-specified completion is Luhn-valid, else 0.
3. Emit "BRAND,count" for every brand with a non-zero count; a single pattern may yield multiple brands.

The 10^(asterisks-1) shortcut comes from Luhn being a single linear (mod-10) constraint on the digits: fixing all but one free position leaves exactly one valid value for the last.

Task 4 — single-error correction

The observed string contains exactly one corruption of one of four kinds. Invert each operation to reconstruct candidate originals, then keep only those that are both Luhn-valid and match a brand:

• Changed digit: for each position, try the other 9 digit values.
• Removed digit (observed is one short): for each insertion gap, insert each of the 10 digits.
• Added digit (observed is one long): for each position, delete that digit.
• Adjacent transposition: for each adjacent pair, swap them back.

Generate all candidates from these inversions, dedupe them (different operations can yield the same original), and for each surviving candidate run task-2 classification — keep it only if it is Luhn-valid AND maps to a real brand (VISA/MASTERCARD/AMEX). Output each surviving original together with its brand. Note the candidate set is small (O(L) per operation type), so brute-forcing the inversions is fine here — the expensive enumeration is only in task 3.

Why this is the right shape

The four tasks build on each other: a clean luhn_ok + brand pair is reused by all of them. The interview is really testing (a) a correct Luhn implementation, (b) careful prefix/length brand rules, (c) the insight that wildcard counting must be combinatorial not brute-force, and (d) systematic enumeration of single-edit inversions with correct validity re-checking.