Theory: Do two expressions agree?

Search for a string that tells two regular expressions apart.

What to build

A program that compares two expressions on every string over {a, b} up to length k.

Requirements

  • If they agree on all of them, print same up to k.
  • Otherwise print the first string where they differ, shortest first in product order, as differ on W: first yes|no, second yes|no (ε for the empty string).

Input

Line 1: the first expression. Line 2: the second. Line 3: k.

Output

One line.

Constraints

0 ≤ k ≤ 8.

Example

Input:

(a|b)*
(a*b*)*
5

Output:

same up to 5

Why it works

Two expressions describe different languages exactly when some string is in one and not the other; the shortest such string is found first.

Examples

Example 1 · Input
(a|b)*
(a*b*)*
5
Expected output
same up to 5
Example 2 · Input
a*b*
(ab)*
3
Expected output
differ on a: first yes, second no

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Try every string over {a, b} up to length k, shortest first, and compare the two fullmatch answers.

Hint 2

Stop at the first string where they disagree.

Solution

Show one correct solution (try it yourself first)
import re
from itertools import product

first = input()
second = input()
k = int(input())


def find():
    for length in range(k + 1):
        for letters in product("ab", repeat=length):
            w = "".join(letters)
            x = bool(re.fullmatch(first, w))
            y = bool(re.fullmatch(second, w))
            if x != y:
                return w, x, y
    return None


found = find()
if found:
    w, x, y = found
    print(f"differ on {w or 'ε'}: first {'yes' if x else 'no'}, second {'yes' if y else 'no'}")
else:
    print("same up to", k)

Lesson: Regular expressions →