in reply to Golf: Buying with exact change

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

blokhead

Replies are listed 'Best First'.
Re^2: Golf: Buying with exact change
by dragonchild (Archbishop) on Feb 22, 2005 at 17:52 UTC
    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

    [download]

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

[reply]
[d/l]
      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.

      blokhead

[reply]

In Section Meditations