Re: Golf: Buying with exact change

[blokhead]

As the other monks observed, the most concise solutions will probably use regular expressions. When looking only at the length of strings, the set of amounts you can represent using $6, $9, and $20 bills is /^(.{6})*(.{9})*(.{20})*$/, or equivalently for our purposes, /^(.{6}|.{9}|.{20})*$/. Now, to get the function arguments into such a regex and find the longest string that doesn't match is the creative part...

Here are my two 48-character solutions:

$"="}|1{";$_=1x999;chop while/^(1{@_})*$/;length $"="}|1{";(grep{(1x$_)!~/^(1{@_})*$/}1..999)[-1]

And if it weren't for a bug I just found in alternations within negative lookaheads, I'm pretty sure this would be equivalent, giving me 46 characters:

$"="}|1{";1x999=~/(1*?)(?!(1{@_})*$)/;length$'

They all use basically the same idea, can you think of a different approach? As I mentioned in the original post, these work for all instances where (a) the solution is 999 or less, and also (b) the arguments are each less than 32k (because they are used in regex quantifiers).

[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.