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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
9 Comments »

9 Responses to “Exercise 2-4”

  1. James Curtis-Smith said
    January 20, 2017 at 12:12 PM

    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. James Curtis-Smith said
    January 20, 2017 at 12:14 PM

    Perl golf would get it down to 

    sub squeeze{return$_[0]=~s/[@{[quotemeta$_[1]]}]//gr}
  3. matthew said
    January 20, 2017 at 12:40 PM

    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
    January 20, 2017 at 12:44 PM

    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. Michael Vehrs said
    January 20, 2017 at 12:55 PM

    Guile:

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

  6. Jussi Piitulainen said
    January 20, 2017 at 1:04 PM

    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
    January 21, 2017 at 5:33 AM

    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
    January 22, 2017 at 11:33 AM

    @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
    January 24, 2017 at 4:12 AM

    @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 comment