This is derived from some C code I wrote to take a string (representing a set of characters) and return a string (also a set) of all the characters not found in that source string. (The NULL character is ignored.) 
char *complement (char *set) {
  int limit = 255;
  char *table = (char *) malloc((1+limit) * sizeof(char));  /* FIXED *
+/
  int i;

  /* populate table with all non-null characters */
  for (i = 0; i < limit; i++) table[i] = i+1;
  table[limit] = 0;

  /* for characters in 'set',
     make their value in the table NULL */
  while (*set) table[*set++ - 1] = 0;

  /* now, swap NULLs in the table with the last element
     in the table, to condense the table */
  for (i = 0; i < limit; i++)
    if (! table[i])
      table[i] = table[--limit], table[limit] = 0;

  return table;
}

[download]
So, the golf is, write this as Perl. The concept is basically, you have a string representing the characters in a character class, and you need to invert that class (ignoring the NULL character).

UPDATE: thanks to blokhead, I'm correcting my answer. I optimized and failed to test my optimization. My function body is 39 characters long. 
sub complement {
#        1         2         3
#23456789012345678901234567890123456789
join"",grep$_[0]!~/\Q$_/,map chr,1..255
#also
pack'C*',grep$_[0]!~/\Q@{[chr]}/,1..255
}

[download]

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

Replies are listed 'Best First'.
Re: Golf: string complement
by kvale (Monsignor) on May 15, 2004 at 15:52 UTC
    It seems as if your C code has a bug. You allocate an array of limit == 255 elements for table array. These elements would be indexed from 0 to 254. But you set 
    table[limit] = 0;

    [download]
    which stomps on the memory location just after the end of the array. The bug would be fixed by mallocing an extra element: 
    char *table = (char *) malloc( (limit + 1) * sizeof(char) );

    [download]
    Happily, Perl does not have these sorts of problems.

    -Mark

[reply]
[d/l]
[select]
      Oh. Oops. Thanks.
      _____________________________________________________
      Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
      s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;
[reply]
Re: Golf: string complement
by tachyon (Chancellor) on May 15, 2004 at 04:43 UTC

    39 strokes 

    sub invert{
    #23456789012345678901234567890123456789
    $_=pack'C*',1..255;eval"tr/$_[0]//d";$_
}
print invert('just Another Edge Case Waiting to Crash!');

    [download]

    Update

    Updated invert text as per below :-)

    cheers

    tachyon

[reply]
[d/l]
      You need to wrap $_[0] in \Q...\E, because if it contains a hyphen or a forward-slash, you'll get unexpected results.
      _____________________________________________________
      Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
      s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;
[reply]
[d/l]

        You gotta hate those edge cases! Having just had a look at your example you are passing an array not a string so it looks like a different problem.

        38 strokes with fix in 35 strokes. 

        sub invert{
    #2345678901234567890123456789012345678
    $_=pack'C*',1..255;s/[\Q$_[0]\E]//g,$_
}
print invert('/just Another Bug to Fix!/');

# 35 strokes using @_ hack

sub invert{
    #2345678901234567890123456789012345
    $_=pack'C*',1..255;s/[\Q@_\E]//g,$_
}
print invert('/just Another Bug to Fix!/');

        [download]

        cheers

        tachyon

[reply]
[d/l]
Re: Golf: string complement
by davido (Cardinal) on May 15, 2004 at 06:38 UTC
    40 strokes (after fixing the \Q \E bug) 
    my $string = 'abcde';
sub invert {
    #234567890123456789012345678901234567890
    join"",grep/[^\Q$_[0]\E]/,map{chr}1..255
}
print invert($string);

    [download]

    UPDATE: Finally, I did it! 37 strokes. :) 

    my $string = 'defg';

sub invert {
    #234567890123456789012345678901234567890
    join'',grep/[^\Q@_\E]/,map{chr}1..255
}

print invert($string);

    [download]

    Dave

[reply]
[d/l]
[select]
      How about we lose another 7 characters :) 
      sub invert {
    #23456789012345678901234567890
    grep/[^\Q@_\E]/,map{chr}1..255
}

      [download]

      cLive ;-)

      updare - to summarize response to BrowserUK's comment - calling the sub in scalar context will automatically join the list into a scalar. Is that cheating? maybe :) - never mind, I was running the wrong test script lol :)

[reply]
[d/l]

        Problem: That will return a list of characters, not a string.

        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
[reply]
[d/l]
Re: Golf: string complement
by bsb (Priest) on May 29, 2004 at 05:38 UTC
[reply]

Back to Meditations