pattern-matching sequence code-golf
Find all matches for the digit pattern
In an older challenge, you were tasked with finding numbers which, in base-ten, matched this specific digit pattern:
(n)(x)(n+1)(x)(n+2)(x)(n+3) etc...
Meaning any number between 4 and 18 digits long such that the digits could be considered as a string of increasing single digits interlaced with (at most) a constant single digit number.
For example, 19293949 would fit the pattern, with n being 1 and x being 9.
In this challenge, instead of deciding whether a given number fits one fixed pattern, you will be given a pattern as input, and are tasked with outputting the sequence of numbers which match the pattern.
Patterns
This section is a definition of what the patterns are and what they represent. A format similar to the one used in the original post will be used for these examples. More clarification on I/O rules will come afterward.
A pattern consists of one or more clearly delimited tokens, each matching a single base-ten digit.
(token)(token)(token)
Tokens can either be constants, accumulators, or a loop.
Constants are each marked with a single token, and there can be up to ten different constants, as each distinct constant represents a distinct digit from each other constant. Here it is represented as a single character from a to j in parenthesis ()
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)
This pattern, for example, could match the number 1234567890, but not the number 1111111111.
Important note: Numbers cannot have leading 0s, so the pattern would not match 0123456789.
(a)(a)(a)
This pattern would match 111, 222, etc. all the way up to 999. It would not match 000, as it contains leading 0s, and it would not match 123, as all of the digits marked with the same constant must be the same.
Accumulators are marked with a single fixed symbol. The first instance of an accumulator represents any digit from 0 to 9, and each successive instance represents a digit that is one more than the previous instance. Here it is represented as (n+)
(n+)(n+)(n+)(n+)(n+)
For example, this pattern matches 12345, 23456, 34567, 45678, and 56789.
Combining constants and accumulators is allowed, giving us access to patterns similar to that of the original challenge:
(a)(n+)(a)(n+)(b)(n+)(b)
Constants can't match the same digits as other constants, but they are allowed to match the same digits as accumulators. This pattern matches, for example, 9192838, but it also matches 1112333.
This isn't enough to support the pattern given in the original problem, so finally we introduce the loop token. This token can only appear at the end of the pattern, or not at all. Here it is represented as ...
(a)(b)(c)(n+)(n+)...
A pattern with the loop token matches all numbers that the pattern would if it did not have the loop, as well as all numbers matched by the pattern repeated twice, as well as three times, as well as four times etc. This pattern matches 78901, but it also matches 7890178923, as well as 789017892378945, etc. all the way up to 7890178923789457896778989.
(a)(a)(a)...
Beware: A pattern with no accumulators but having constants and a loop matches infinitely many numbers. This one matches 111, 111111, 111111111, etc.
Rules
Input can be given in any reasonable format, so long as each token type is clearly distinct, clearly delimited, and consistent. This includes lists of characters, lists of strings, lists of numbers, a single string, curried arguments, etc.
The loop token in particular can be taken anywhere in the input convenient, including separate from all of the other tokens. e.g. you could take it as a separate boolean input, or a command line argument, or at the beginning of the string instead, etc.
Standard sequence rules apply, so you can either output all matches, or take another number n as input and return the nth matching number, etc. Whatever the rules in the tag allow is fine with me.
You may assume any/all of the following:
- All patterns given have at least a single valid match.
- When given a pattern with finitely many matches,
you will not be given an input asking you to exceed that amount of
matches (so you wont be asked to generate the 11th number that
matches
(a)).
- Constant variable names first appear in some specific order. So you could, for example, accept
(a)(b)(c)(a)(c) but ignore (x)(y)(z) and (c)(b)(a). So long as at least one equivalent form is allowed, it's fine. I doubt this helps anyone, just covering my bases.
- Not strictly an assumption, but you are allowed to ignore
0 as an output number or assume no input will ask for it, as it technically breaks the "no leading zeros" rule. Edge cases wouldn't add much to the challenge :P
Finally, this is code-golf, so shortest code in bytes wins.
Examples
Examples will be given as a pattern, followed by a natural n, followed by the nth matching number (including 0), 0 indexed, all delimited with |.
Still work in progress, the ?s are temporary,
(a) | 1 | 1
(a) | 9 | 9
(a)(b)(c) | 0 | 102
(a)(b)(c) | 1 | 103
(a)(b)(c) | 7 | 109
(a)(b)(c) | 8 | 120
(a)(b)(c) | 9 | 123
(a)(b)(c) | ? | 987
(a)(b)(c)... | ? | 987
(a)(b)(c)... | ?+1 | 102102
(n+) | 1 | 1
(n+) | 9 | 9
(n+)... | 1 | 1
(n+)... | 9 | 9
(n+)... | 10 | 12
(n+)... | 11 | 23
(n+)... | 17 | 89
(n+)... | 18 | 123
(n+)... | 19 | 234
(n+)... | 24 | 789
(n+)... | 25 | 1234
(n+)... | 26 | 2345
Meta
Should I allow leading zeroes in interest of reducing edge cases?
For rendering to screen, some extensions are needed. You should use the minimal number of extensions and layers necessary.
