Re: 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,}?$/
[download]

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

Replies are listed 'Best First'.
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}))$/` [download] 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	[reply] [d/l]
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	[reply]
Re^3: The greedy change-making problem using regexes by theorbtwo (Prior) on Mar 10, 2005 at 11:02 UTC
...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).	[reply]
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); }` [download]	[reply] [d/l]
Re^3: The greedy change-making problem using regexes by japhy (Canon) on Mar 10, 2005 at 12:32 UTC
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	[reply]
Re^4: The greedy change-making problem using regexes by Anonymous Monk on Mar 10, 2005 at 13:14 UTC
Which is the correct answer for the greedy algorithm. But see my posting elsewhere in this thread for a more general solution.	[reply]


XP is just a number
	PerlMonks