Abstract Nonsense

Posts tagged with "Algorithms"

Can a regex match valid card numbers?

Sometimes the mere existence of a question is dangerous. A colleague recently asked me whether it’s possible to validate credit card numbers in regex using the Luhn algorithm, and, well, I was thoroughly nerd-sniped. I’ll outline the problem briefly and we’ll try to explicate a solution together.

For what follows, it’ll be helpful if you’ve encountered concepts such as Deterministic Finite Automata (DFA), Regular languages and modular arithmetic before. If you haven’t, I think a quick skim at the Wikipedia pages should be sufficient to follow. I’ll also pair the mathematical formalisms with Python code in the exposition to make it easier to follow.