Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: The greedy change-making problem using regexes

by japhy (Canon)
on Mar 10, 2005 at 01:47 UTC ( #438131=note: print w/ replies, xml ) Need Help??


in reply to The greedy change-making problem using regexes

I'd approach it inside out. I'd make my regex try to match like so:

("1" x $money) =~ /^(1{10}|1{6}|1{5}|1{1}){1,}?$/
Then I'd add to that regex code blocks that store the "winning" combination. The concept is, it tries to match the string using only one coin. Once that fails, it tries to match it using two coins. Etc. This is probably slow.

Hrm, this probably won't work easily with Perl's regexes. My first efforts have proved fruitless.

_____________________________________________________
Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart


Comment on Re: The greedy change-making problem using regexes
Download Code
Re^2: The greedy change-making problem using regexes
by blokhead (Monsignor) on Mar 10, 2005 at 02:00 UTC
    Ooh, that is quite elegant indeed. One of my lessons here was "Know in which order thine regex engine tries things" but I completely missed this little optimization. ;) It really matches up temporaly with the spirit of the problem.

    I suppose I could also use (?>pattern) to prevent backtracking and perform the greedy match without the negative lookaheads?

    (1 x $money) =~ /^(?>(1{10})*)(?>(1{6})*)(?>(1{5})*)(?>(1{1})*)$/
    Although I can't say I've ever really used (?>pattern)...

    Anyway, the pain in the butt is counting the number of coins. I like my little (?{$^R+1}) idiom!

    blokhead

Re^2: The greedy change-making problem using regexes
by demerphq (Chancellor) on Mar 10, 2005 at 07:46 UTC

    Personally I would avoid the 1{10} stuff. For two reasons, first is that 1{10} is less efficient to match than "1" x 10, and second reason is that the speed of the regex once my trie patch gets applied will be massively faster as without the curlies it will be optimised and with them it wont. :-)

    ---
    demerphq

      ...which suggests that the RE engine should convert a trivial match with a trivial curly in to the equivlent $match x $curly atoms. Of course, somehow I suspect that wouldn't really be a help for /x{2047}/.


      Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).

Re^2: The greedy change-making problem using regexes
by Anonymous Monk on Mar 10, 2005 at 10:45 UTC
    No need for code blocks, and it works very fast as well (as you'd expect from a greedy algorithm).
    my $dime = '(?:' . ('1' x 10) . ')'; my $halfdozen = '(?:' . ('1' x 6) . ')'; my $nickel = '(?:' . ('1' x 5) . ')'; my $cent = '(?:' . ('1' x 1) . ')'; sub greedy_change { my $change = shift; my ($c10, $c6, $c5, $c1) = ('1' x $change) =~ /^($dime*)($halfdozen*)($nickel*)($cent*)$/; return (length ($c10 || "") / 10, length ($c6 || "") / 6, length ($c5 || "") / 5, length ($c1 || "") / 1); }
      No, that doesn't work: it ends up using three coins (a dime and two pennies) for 12 cents, instead of two six-cent coins.
      _____________________________________________________
      Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
      How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
        Which is the correct answer for the greedy algorithm. But see my posting elsewhere in this thread for a more general solution.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://438131]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2014-12-29 02:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (184 votes), past polls