Theory: Concatenating two languages

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))

Lesson: Alphabets, strings and languages →