Re^2: Golf: Buying with exact change

[dragonchild]

I'm down to 111 characters at Re^2: Golf: Buying with exact change using Anonymonk's non-regex solution. I think that with the addition of a few characters, you might be able to remove the 999 restriction on the regex solution.

Update: Melding our solutions gives a 79 character solution that doesn't have the 999 restriction.

$"="}|1{";$r=qr/^(1{@_})+$/;for($t=$s=0;$t-$s<$_[0];(1x++$t)=~/$r/ or$ +s=$t){}$s

[blokhead]

Here's a solution that doesn't have the arbitrary restriction on the solution size, although since it uses the same regex trick as above, the inputs must still be <32k. It's 75 characters:

($",$n,$_)="}|1{";while($n++<$_[-1]){$_.=1;/^(1{@_})*$/ or$n=0}length()-pop

But the non-regex ideas are interesting to me, as I wasn't sure it was easily possible without the regex logic.