Filenames From a Brace Pattern

A batch-rename tool writes many filenames with one pattern. Curly braces hold a group of choices; everything outside braces is copied as it is. Given pattern, return every filename it describes.

A group is one of:

• a range {A..B}, where A and B are non-negative whole numbers written in digits: the numbers from A to B, counting down if A > B. If either endpoint is written with a leading zero (it is longer than one character and starts with 0), every number is padded with zeros to the length of the longer endpoint;
• otherwise a list of options separated by commas; options may be empty ({,s} has the options "" and "s"), and a group with no comma has a single option.

The order of the results: the first group changes slowest and the last group fastest, as when reading a mileage counter. Duplicates are kept. A pattern with no groups gives a one-item list.

Examples

Input:  pattern = "photo_{a,b}{1..3}.jpg"
Output: ["photo_a1.jpg", "photo_a2.jpg", "photo_a3.jpg",
         "photo_b1.jpg", "photo_b2.jpg", "photo_b3.jpg"]

Input:  pattern = "log{,.old}"
Output: ["log", "log.old"]

Input:  pattern = "v{08..11}_{3..1}"
Output: ["v08_3", "v08_2", "v08_1", "v09_3", ..., "v11_1"]   (12 names)

Constraints

• 0 <= len(pattern) <= 200; braces are never nested, every { has a matching }, and } never appears outside a group
• Range endpoints have at most 5 digits; the answer has at most 10**4 names

Goals

• Cut a pattern into literal text and option groups in one scan
• Grow the list of results one group at a time instead of nesting loops
• Expand counting ranges in either direction with zero padding