Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Requiring backtracking a certain number of times

by dragonchild (Archbishop)
on Apr 04, 2002 at 15:43 UTC ( #156690=perlquestion: print w/ replies, xml ) Need Help??
dragonchild has asked for the wisdom of the Perl Monks concerning the following question:

Is it possible to force a regex to backtrack and re-match a character a certain number of times based on what the character is? An application for this might be taking the number "123" and adding it to be 6. The trick here is using a regex to match against this number and return 6 "matches". Any thoughts?

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Comment on Requiring backtracking a certain number of times
Re: Requiring backtracking a certain number of times
by RMGir (Prior) on Apr 04, 2002 at 16:08 UTC
    Ouch. As your sig says, "Don't go borrowing trouble." :)

    I don't think you can ever guarantee how the engine is going to backtrack. Sure, you could for a given point version of perl, but then japhy's going to submit a batch of patches, or Ilya Z will delurk on p5p, and the internal behaviour will get optimized. Or study will start working, and the backtracking will be different.

    Besides, backtracking is internal behaviour; I don't think there's anything externally visible, apart from how long the regex takes, to indicate that backtracking is taking place. Well, apart from code blocks in the regex.

    Even if you can come up with a way to do this, I don't think you really want to. Do you? I'm trying to come up with an application for this outside of golf, obfuscated code, or other JAPHs, and nothing springs to mind :)
    --
    Mike

Re: Requiring backtracking a certain number of times
by Juerd (Abbot) on Apr 04, 2002 at 17:35 UTC

    Backtracking is something internal, and to mess with that, you ugly hacks. It would probably involve a new implementation of the regex engine to do what you want with backtracking.

    To add the digits, you need to evaluate some code. With (??{}) it is almost impossible to evaluate and rematch, because when you try recursion, you can't easily use $1 over and over, because it'll be $2 (if you have a single set of parentheses) the second time. And you can't even use $1 within its own parentheses. Forget recursive regexes for now.

    As I said, you need to evaluate some code, and you could try doing that with /e, and wrapping it in a loop. However, it's still nasty and there are better ways to do it.

    Mathematics may be the answer to this problem. If you have a number, and add all digits and repeat until you have a single digits left, you're going through a lot of trouble to implement $digit = $number % 9 || 9 (figure out how that works yourself).

    Illustation:

    #!/usr/bin/perl -w use strict; sub sum { my $sum = 0; $sum += $_ for @_; return $sum; } for (1..10) { my $copy = my $number = int rand 1e4; print "=== Test: $_ - Number: $number ===\n"; print "Brute force:\n"; while ($copy > 9) { my @digits = split //, $copy; $copy = sum(@digits); print "\t", join(' + ', @digits), " = $copy\n"; } print "Maths:\n"; print "\t$number % 9 || 9 = ", $number % 9 || 9, "\n\n"; }
    === Test: 1 - Number: 5943 === Brute force: 5 + 9 + 4 + 3 = 21 2 + 1 = 3 Maths: 5943 % 9 || 9 = 3 === Test: 2 - Number: 3630 === Brute force: 3 + 6 + 3 + 0 = 12 1 + 2 = 3 Maths: 3630 % 9 || 9 = 3 === Test: 3 - Number: 3309 === Brute force: 3 + 3 + 0 + 9 = 15 1 + 5 = 6 Maths: 3309 % 9 || 9 = 6 === Test: 4 - Number: 8085 === Brute force: 8 + 0 + 8 + 5 = 21 2 + 1 = 3 Maths: 8085 % 9 || 9 = 3 === Test: 5 - Number: 117 === Brute force: 1 + 1 + 7 = 9 Maths: 117 % 9 || 9 = 9 === Test: 6 - Number: 8474 === Brute force: 8 + 4 + 7 + 4 = 23 2 + 3 = 5 Maths: 8474 % 9 || 9 = 5 === Test: 7 - Number: 8132 === Brute force: 8 + 1 + 3 + 2 = 14 1 + 4 = 5 Maths: 8132 % 9 || 9 = 5 === Test: 8 - Number: 1518 === Brute force: 1 + 5 + 1 + 8 = 15 1 + 5 = 6 Maths: 1518 % 9 || 9 = 6 === Test: 9 - Number: 6491 === Brute force: 6 + 4 + 9 + 1 = 20 2 + 0 = 2 Maths: 6491 % 9 || 9 = 2 === Test: 10 - Number: 2170 === Brute force: 2 + 1 + 7 + 0 = 10 1 + 0 = 1 Maths: 2170 % 9 || 9 = 1
    There is a minor problem: 0 % 9 || 9 is of course 9, and you want 0. A simple && can fix it, I'll leave its placement to you.

    I hope I've recognised the problem correctly. If this is not what you're trying to do (obfu? golf?), please forgive me :)

    U28geW91IGNhbiBhbGwgcm90MTMgY
    W5kIHBhY2soKS4gQnV0IGRvIHlvdS
    ByZWNvZ25pc2UgQmFzZTY0IHdoZW4
    geW91IHNlZSBpdD8gIC0tIEp1ZXJk
    

      In what I'm trying to do, 6491 would turn into 20, not 2. I just want the result of adding the numbers. But, what I really want is some way of addressing all the characters in a string/number, apply some function to it that returns a number, then add those numbers up. Ideally (because this is something that's useful in golfing), it would be something really small.

      And, yes, I remember TPR(0,1) and magic numbers. :-)

      ------
      We are the carpenters and bricklayers of the Information Age.

      Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

        what I really want is some way of addressing all the characters in a string/number, apply some function to it that returns a number, then add those numbers up.

        $_=6491; sum(some_function(split//));
        Use your favourite sum(), and your favorite some_function() ;)

        These things are very hard, and I think completely impossible with regexes.
        Although...
        s/(\d)/$s+=$1/ge; # $s is the sum... # Which leaves garbage in $_, but is a single stroke shorter than: $s+=$_ for split//; # But thenagain, this is even shorter: $s+=$_ for/./g;

        U28geW91IGNhbiBhbGwgcm90MTMgY
        W5kIHBhY2soKS4gQnV0IGRvIHlvdS
        ByZWNvZ25pc2UgQmFzZTY0IHdoZW4
        geW91IHNlZSBpdD8gIC0tIEp1ZXJk
        

        unpack"%32C*",pack "C*",split//

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://156690]
Approved by dragonchild
Front-paged by demerphq
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (10)
As of 2014-09-19 20:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (145 votes), past polls