Design and implement a payment card validation module that supports multiple networks and error scenarios.
Requirements:
-
Luhn checksum
-
Implement the Luhn algorithm: starting from the rightmost non-check digit, double every second digit; if the result > 9 subtract 9; sum all digits; valid if sum % 10 == 0.
-
Card networks
-
VISA: 16 digits, prefix 4
-
MASTERCARD: 16 digits, prefixes 51–55
-
AMEX: 15 digits, prefixes 34 or 37
-
Part 1 — Basic VISA
-
Input: a 16-digit string starting with 4
-
Output: "VISA" if Luhn-valid; otherwise "INVALID_CHECKSUM"
-
Part 2 — Multi-network
-
Input: a 15- or 16-digit string
-
Output: the network name (VISA/MASTERCARD/AMEX) if prefix/length match and Luhn-valid; "INVALID_CHECKSUM" if prefix/length match but Luhn fails; otherwise "UNKNOWN_NETWORK"
-
Part 3 — Redacted cards
-
Input: a card string containing 1–5 asterisks (*) that replace digits
-
Task: count how many concrete completions are valid per network, considering prefix/length rules and Luhn. Output one line per network that has at least one valid completion, sorted alphabetically by network: "AMEX,
<count>
", "MASTERCARD,
<count>
", "VISA,
<count>
".
-
Part 4 — Corrupted cards
-
Input: a card string ending with '?' indicating exactly one error was introduced in an originally valid card, where the error is either
(a) one digit changed to another digit, or
(b) a swap of two adjacent digits
-
Task: enumerate all possible original valid cards consistent with that model (respecting network rules and Luhn). Output each as "<card_number>,
<NETWORK>
", sorted numerically by card number.
General constraints and expectations
-
Treat inputs as strings; use exact output tokens.
-
For Parts 3 and 4, design efficient search with pruning using prefix constraints and Luhn properties; handle large search spaces.
-
Specify data structures, algorithms, and time/space complexity for each part.
-
Describe edge cases (wrong lengths, invalid prefixes, leading zeros in redactions, multiple '*' placement, duplicate reconstructions in Part
-
and how you avoid duplicates and ensure determinism.
-
Provide test strategy and sample cases for each part.