Fun With Regular Expressions

This is a fun puzzle that was dropped in one of the discord servers, I'm part of (thanks to Anthony - do checkout their channel). This puzzle revolved around regular expressions (regex).

Regex is widely used in programming, data processing, and system administration for tasks like:

• Validating user input (e.g., email addresses, phone numbers).
• Searching and extracting information from text files or databases.
• Replacing or modifying parts of a string.
• Parsing log files or large datasets.

But this was a puzzle which required use of regex to do something not so trivial but a lot of fun

Given two positive integers 'a' and 'b', one as an integer, and one as a string, use regex to find if the 'a' is greater than 'b'. So, we have to generate a regex pattern from a which when matched to b should give a match of b if the comparison would've return true otherwise it shouldn't match. Note that b can be provided with padded 0s, example - b = "023"

Before we move ahead with the solution, take some time and try to think about it.

So, let's take an example. Let's say we have a = 12. So, we know that for something to be greater than a, it can have

• 2 digits with constraint that first digit is 1 and second digit has to be greater than 2; or
• 2 digits with constraint that first digit is greater than 1 and second digit can be anything; or
• more than 2 digits with constraint that first digit cannot be 0

So, we have 3 conditions here, let's try to formulate each into it's own regex pattern.

1. r"^1[3-9]$"

2. r"^[2-9]\d$"

3. r"^[1-9]\d{2,}$"

So, our final regex would be r"^1[3-9]$|^[2-9]\d$|^[1-9]\d{2,}$". Let's try this with some values of "b".

$ python
>>> import re
>>> p = r"^1[3-9]$|^[2-9]\d$|^[1-9]\d{2,}$"
>>> re.match(p, "2") is not None
False
>>> re.match(p, "15") is not None
True
>>> re.match(p, "33145") is not None
True

Great! But we need to auto-generate this regex based on value of a, and it can be quite large. We have to do above exercise logically for each digit position. If a had 3 digits, then for something to be greater than a, it can

• have 3 digits
  • fix 1st two digits, and allow 3rd digit to vary (should be greater than that of a)
  • fix 1st digit, and allow 2nd digit to vary (should be greater than that of a), and then 3rd digit can be anything
  • allow 1st digit to vary (should be greater than that of a), and then 2nd and 3rd digits can be anything.
• have more than 3 digits given first digit shouldn't be 0

We do have a edge case here when we enounter a 9, example - a = 291. For something to be greater than a, we can generate regex patterns based on above conditions

• 3 digits
  • 1st and 2nd digits fixed -- r"^29[2-9]$"
  • 1st digit fixed -- ??
  • no digits fixed -- r"^[3-9]\d{2}$"
• more than 3 digits -- r"^[1-9]\d{3}$"

So for ??, you'll notice that what we have to do is bump up the digit to the left of 9 by 1, and replace 9 with 0, and 3rd digit can be anything. So, it becomes a subset of r"^[3-9]\d{2}$".

>>> import re
>>> def gt(n: int) -> str:
        digits = list(map(int, str(n)))
        s = ""
        num_digits = len(digits)
        for i, digit in enumerate(digits):
            prefix = "".join(map(str, digits[:i]))
            if digit == 9:
                continue
            else:
                s += f"^{prefix}[{digit + 1}-9]"
                if num_digits - i - 1 > 0:
                    s += f"[0-9]{{{num_digits - i - 1},}}"
                s += "$|"
        s += f"^[1-9][0-9]{{{num_digits},}}$|"
        return s[:-1]

>>> gt(291)
'^[3-9][0-9]{2,}$|^29[2-9]$|^[1-9][0-9]{3,}$'
>>> p = re.compile(gt(291))
>>> for b in range(1, 1000000):
        if b <= 291:
            assert re.match(p, str(b)) is None
        else:
            assert re.match(p, str(b)).string == str(b)

Here's an exercise for you. Try to implement a lt method which mimics the "less than" functionality.

def lt(n: int) -> str:
    if n == 0:
        return "^$"
    digits = list(map(int, str(n)))
    s = ""
    num_digits = len(digits)
    for i, digit in enumerate(digits):
        prefix = "".join(map(str, digits[:i]))
        if digit == 0:
            if i > 0:
                prev_digit = digits[i - 1]
                if prev_digit > 0:
                    prev_digit -= 1
                else:
                    prev_digit = 9
                s += f"^{prefix[:-1]}{prev_digit}[0-9]{{0,{num_digits - i - 2}}}$|"
        else:
            s += f"^{prefix}[0-{digit - 1}]"
            if num_digits - i - 1 > 0:
                s += f"[0-9]{{0,{num_digits - i - 1}}}"
            s += "$|"
    if num_digits > 2:
        s += f"^[1-9][0-9]{{0,{num_digits - 2}}}$|"
    return s[:-1]

Hope you enjoyed it as much as I did!