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:
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.
19293949 would fit the pattern, with
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.
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.
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
j in parenthesis
This pattern, for example, could match the number
1234567890, but not the number
Important note: Numbers cannot have leading 0s, so the pattern would not match
This pattern would match
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
For example, this pattern matches
Combining constants and accumulators is allowed, giving us access to patterns similar to that of the original challenge:
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
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 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
Beware: A pattern with no accumulators but having constants and a loop matches infinitely many numbers. This one matches
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
- Constant variable names first appear in some specific order. So you could, for example, accept
(a)(b)(c)(a)(c) but ignore
(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 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
Should I allow leading zeroes in interest of reducing edge cases?