Exercise 2-4

January 20, 2017

I’m enjoying these small exercises from The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie. We’ll do another one today.

In Section 2.8, Kernighan and Ritchie give a function squeeze that deletes all characters c from a string s:

/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
    int i, j;
    for (i = j = 0; s[i] != '\0'; i++)
        if (s[i] != c)
            s[j++] = s[i];
    s[j] '\0';
}

Then, in Exercise 2-4, they ask the reader to “Write an alternate version of squeeze(s1,s2) that deletes each character in s1 that matches any character in the string s2.”

Your task is to write both versions of squeeze in your favorite language; if you choose C, half the work is already done. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

9 Responses to “Exercise 2-4”

  1. As a perl user I would do this a perl way…

    sub squeeze {
      my $r = quotemeta $_[1];
      return my $y = $_[0] =~ s/[$r]//gr
    }
    
    print squeeze(@ARGV),"\n";
    
  2. Perl golf would get it down to

    sub squeeze{return$_[0]=~s/[@{[quotemeta$_[1]]}]//gr}
    
  3. matthew said

    Here’s some C++:

    #include <stdio.h>
    template <typename T, typename PRED>
    void filter(T *p, PRED pred) {
       for (T *q = p; *q != T(0); q++) {
          if (!pred(*q)) *p++ = *q;
       }
       *p = 0;
    }
    template <typename T>
    bool member(T a, T *p) {
       for ( ; *p != T(0); p++) {
          if (a == *p) return true;
       }
       return false;
    }
    void squeeze(char *s, char *t) {
       filter(s,[=](char c) { return member(c,t); });
    }
    
    int main(int argc, char *argv[]) {
       squeeze(argv[1],argv[2]);
       printf("%s\n", argv[1]);
    }
    
  4. matthew said

    Or some more traditional C:

    #include <stdio.h>
    #include <stdbool.h>
    void f(char *s, const char *t) {
       int i = 0, j = 0, k = 0;
       while (true) {
          if (t[i] == 0) {
             i = 0; s[k++] = s[j++];
          } else if (s[j] == 0) {
             s[k++] = 0; break;
          } else if (t[i] == s[j]) {
             i = 0; j++;
          } else {
             i++;
          }
       }
    }
    
    int main(int argc, char *argv[]) {
       f(argv[1],argv[2]);
       printf("%s\n", argv[1]);
       return 0;
    }
    
  5. Guile:

    (define (squeeze str chars) (string-delete (string->char-set chars) str))

  6. Jussi Piitulainen said

    Python strings have translation-table methods.

    >>> x = str.maketrans('','','aeiouyäö')
    >>> 'Pidä pää kylmänä ja lopeta twiittailu'.translate(x)
    'Pd p klmn j lpt twttl'
    
  7. Globules said

    Here’s a Haskell version. It also works on any list whose elements support equality testing.

    -- Return a list consisting only of elements not contained in the first
    -- argument.
    squeeze2 :: Eq a => [a] -> [a] -> [a]
    squeeze2 del = filter (`notElem` del)
    
    main :: IO ()
    main = do
      putStrLn $ squeeze2 "pM" "Mississippi"
      print $ squeeze2 [2, 4] [1..5]
    
    $ ./squeeze 
    ississii
    [1,3,5]
    
  8. matthew said

    @Globules: I was going to suggest

    import Control.Monad
    squeeze :: (Eq a, MonadPlus m) => [a] -> m a -> m a
    squeeze t = join . fmap nullset where
      nullset c
        | c `elem` t = mzero
        | otherwise = return c
    main = print $ squeeze "ace" "abcde"
    

    but really that is just your solution with mfilter instead of filter.

  9. Globules said

    @matthew Your MonadPlus suggestion made me wonder what was the “most general” type I could give it. But then I got lost in a maze of twisty little typeclasses (Foldable, Alternative, etc.) and now I will just go to bed… :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: