Matching finite natural series

Question

How can I match the end number of a natural number with a regular expression?

So, the requirements are:

• the string contains numbers and spaces (as delimiters)
• first number 1
• each number (except the first) is equal to the previous number + 1

Must match :

• 1
• 1 2
• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
• long series of consecutive numbers from 1 to 10 ^ 1000

Do not match :

• ``
• 1 3 4
• 1 2 3 4 5 6 6

In addition, there are some requirements for regular expression:

• it should be a one-time one-time expression, not a set of loop algorithm algorithms
• it can use all the power of perl regular expressions

I'm not sure if regex is actually lazy, so it would be great if they were. Since the natural series of numbers is not finite in it, the initial value from number theory.

And last. Please note that I am not using the wrong tool for this job. This is not a real world programming task.

Answer 1

Here you go. Tested on Perl v5.10 - v5.14. The key is a recursive pattern where we return the rule (?&Sequence) . This is a bit of evidence by induction.

bigint exists just in case you really want to generate a sequence of 1 .. 10**10_000 . It will work much faster if you can limit yourself to a machine of your own int, 32-bit or 64-bit depending on your platform.

 #!/usr/bin/env perl use v5.10; use bigint; # only if you need stuff over maxint my $pat = qr{ ^ (?= 1 \b ) (?<Sequence> (?<Number> \d+ ) (?: \s+ (??{ "(?=" . (1 + $+{Number}) . ")" }) (?&Sequence) )? ) $ }x; # first test embedded data while (<DATA>) { if ( /$pat/ ) { print "PASS: ", $_; } else { print "FAIL: ", $_; } } # now generate long sequences for my $big ( 2, 10, 25, 100, 1000, 10_000, 100_000 ) { my $str = q(); for (my $i = 1; $i <= $big; $i++) { $str .= "$i "; } chop $str; if ($str =~ $pat) { print "PASS: "; } else { print "FAIL: "; } if (length($str) > 60) { my $len = length($str); my $first = substr($str, 0, 10); my $last = substr($str, -10); $str = $first . "[$len chars]" . $last; } say $str; } __END__ 5 fred 1 1 2 3 1 3 2 1 2 3 4 5 1 2 3 4 6 2 3 4 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 6 

As a result of executing this command:

 FAIL: 5 FAIL: fred PASS: 1 PASS: 1 2 3 FAIL: 1 3 2 PASS: 1 2 3 4 5 FAIL: 1 2 3 4 6 FAIL: 2 3 4 6 PASS: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 FAIL: 1 2 3 4 5 6 6 PASS: 1 2 PASS: 1 2 3 4 5 6 7 8 9 10 PASS: 1 2 3 4 5 [65 chars]2 23 24 25 PASS: 1 2 3 4 5 [291 chars] 98 99 100 PASS: 1 2 3 4 5 [3892 chars]8 999 1000 PASS: 1 2 3 4 5 [588894 chars]999 100000 

There is a book at the risk of apparent self-interest that covers such things. See the Fancy Patterns Section in Chapter 5 of Perl Programming, Version 4ᵗʰ. You want to check out the new Named Groups, Recursive Templates, and Grammar Templates sections. The book is with printers and should be available electronically in a day or two.

Answer 2

Try the following regex (in perl ):

 m/\A((??{ our $i += 1 })(?>\s*))+\Z/ 

---

Test

The contents of script.pl :

 use warnings; use strict; while ( <DATA> ) { chomp; our $i = 0; printf qq[%s\n], $_ if m/\A((??{ our $i += 1 })(?>\s*))+\Z/; } __DATA__ 0 2 1 1 3 4 1 2 1 2 3 4 5 6 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 1 1 2 3 4 5 7 1 2 3 

Run the script:

 perl script.pl 

And the result:

 1 1 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 

Answer 3

I do not think there is a possible model to fill your requirements, because regular expressions basically correspond to the text; when calculating

however, you can create your own machine that performs calculations, or simply iterate over numbers, which should be more efficient