Build the concatenation A·B of two finite languages.
What to build
A program that prints every string of A·B once, shortest first.
Requirements
- Treat the token ε as the empty string.
- Sort by length, then alphabetically; print ε for the empty string.
- Finish with
size K, the number of distinct strings.
Input
Line 1: the words of A, separated by spaces. Line 2: the words of B.
Output
The strings of A·B, one per line, then size K.
Constraints
Each language has at most 6 words of at most 5 symbols.
Example
Input:
a ab
b ε
Output:
a
ab
abb
size 3
Why it works
A·B pairs every word of A with every word of B, and a set keeps each resulting string once.
Examples
Example 1 · Input
a ab b ε
Expected output
a ab abb size 3
Example 2 · Input
ε ε
Expected output
ε size 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use a set comprehension: {x + y for x in A for y in B}.
Hint 2
Read ε as "" and sort with key=lambda w: (len(w), w).
Solution
Show one correct solution (try it yourself first)
def words(line):
return {"" if w == "ε" else w for w in line.split()}
A = words(input())
B = words(input())
result = sorted({x + y for x in A for y in B}, key=lambda w: (len(w), w))
for w in result:
print(w or "ε")
print("size", len(result))