Grabscrab

Here are solutions to Andrew Ho’s “detecting grabscrab steals” interview problem. Perl

#!/opt/local/bin/perl

use warnings;
use strict;

use Test;

BEGIN { plan tests => 4 }

ok(is_steal('quiet', 'quit'));
ok(!is_steal('strip', 'strep'));
ok(!is_steal('quit', 'quiet'));
ok(is_steal('proud', 'rod'));

sub is_steal {
    my ($steal, $base) = @_;
    my %letterhash;
    foreach (split //, $steal) {
        $letterhash{$_}++;
    }

    foreach (split //, $base) {
        return 0 unless $letterhash{$_};
        $letterhash{$_}--;
     }

    return 1;
}

# really short version; logically same as above
sub is_steal {
    my %d;
    $d{$_}++ for split //, $_[0];
    for (split //, $_[1]) {
        return if !$d{$_}--;
    }
    1;
}

PHP

#!/opt/local/bin/php
<?php
$test_count = 0;

ok(is_steal('quiet', 'quit'));
ok(!is_steal('strip', 'strep'));
ok(!is_steal('quit', 'quiet'));
ok(is_steal('proud', 'rod'));

function is_steal($steal, $base) {
    $letterhash = array();
    foreach (str_split($steal) as $_) {
        if (array_key_exists($_, $letterhash)) {
            $letterhash[$_]++;
        } else {
            $letterhash[$_] = 1;
        }
    }

    foreach (str_split($base) as $_) {
        if (!array_key_exists($_, $letterhash)) {
            return false;
        }
        $letterhash[$_]--;
        if ($letterhash[$_] < 0) {
            return false;
        }
    }

    return true;
}

function ok($test) {
    global $test_count;
    $test_count++;
    if ($test) {
        print "ok $test_count\n";
    } else {
        print "NOT ok $test_count\n";
    }
}
?>

C


#include <stdio.h>

int test_count = 0;

int is_steal(const char *steal, const char *base) {
    int letterhash[26] = {0};
    int i;

    while(*steal) {
        i = *steal++ - 'a';
        if (i < 26 && i >= 0) {
            letterhash[i]++;
        }
    }

    while(*base) {
        i = *base++ - 'a';
        if (i < 26 && i >= 0) {
            if (!letterhash[i]) return 0;
            letterhash[i]--;
        }
    }

    return 1;
}

void ok (int test) {
    printf(test ? "ok %d\n" : "NOT ok %d\n", ++test_count);
}

int main() {
    ok(!is_steal("strip", "strep"));
    ok(!is_steal("quit", "quiet"));
    ok(is_steal("proud", "rod"));
    ok(is_steal("devil", "live"));
    ok(is_steal("smash", "mass"));
    return 0;
}

Javascript

var test_count = 0;

ok(is_steal('quiet', 'quit'));
ok(!is_steal('strip', 'strep'));
ok(!is_steal('quit', 'quiet'));
ok(is_steal('proud', 'rod'));

function is_steal(steal, base) {
    var letterhash = new Object();
    var i = steal.length;
    while (i--) {
        var c = steal.charAt(i);
        if (letterhash[c])
            letterhash[c]++;
        else
            letterhash[c] = 1;
    }

    i = base.length;
    while (i--) {
        var c = base.charAt(i);
        if (!letterhash[c]) return false;
        letterhash[c]--;
    }

    return true;
}

function ok(test) {
    test_count++;
    if (test) {
        print("ok " + test_count);
    } else {
        print("NOT ok " + test_count);
    }
}

Java

import java.util.*;
import java.text.*;

public class GrabScrab {
    static int test_count = 0;
    public static void main (String[] args) {
        ok(is_steal("quiet", "quit"));
        ok(!is_steal("strip", "strep"));
        ok(!is_steal("quit", "quiet"));
        ok(is_steal("proud", "rod"));
    }

    private static boolean is_steal(String steal, String base) {
        HashMap<Character,Integer> letterHash =
            new HashMap<Character,Integer>();

        for (char c : steal.toCharArray()) {
            if (letterHash.containsKey(c))
                letterHash.put(c, letterHash.get(c) + 1);
            else
                letterHash.put(c, 1);
        }

        for (char c : base.toCharArray()) {
            if (!letterHash.containsKey(c)) return false;
            int newVal = letterHash.get(c).intValue() - 1;
            if (newVal < 0) return false;
            letterHash.put(c, newVal);
        }

        return true;
    }

    private static void ok(boolean test) {
        test_count++;
        String s;
        if (test)
            s = String.format("ok %d", test_count);
        else
            s = String.format("NOT ok %d", test_count);
        System.out.println(s);
        return;
    }
}

Java (without using generics and for-each)

import java.util.*;
import java.text.*;

public class GrabScrab {
    static int test_count = 0;
    public static void main (String[] args) {
        System.out.println("Hello, world!\n");
        ok(is_steal("quiet", "quit"));
        ok(!is_steal("strip", "strep"));
        ok(!is_steal("quit", "quiet"));
        ok(is_steal("proud", "rod"));
    }

    private static boolean is_steal(String steal, String base) {
        HashMap letterhash = new HashMap();

        StringCharacterIterator steal_iter =
            new StringCharacterIterator(steal);
        for (char c = steal_iter.first();
             c != CharacterIterator.DONE;
             c = steal_iter.next())
        {
            if (letterhash.containsKey(c)) {
                Integer oldVal = (Integer)letterhash.get(c);
                letterhash.put(c, oldVal.intValue() + 1);
            } else {
                letterhash.put(c, 1);
            }
        }

        StringCharacterIterator base_iter =
            new StringCharacterIterator(base);
        for (char c = base_iter.first();
             c != CharacterIterator.DONE;
             c = base_iter.next())
        {
            if (!letterhash.containsKey(c)) return false;
            Integer oldVal = (Integer)letterhash.get(c);
            int newVal = oldVal.intValue() - 1;
            if (newVal < 0) return false;
            letterhash.put(c, newVal);
        }

        return true;
    }

    private static void ok(boolean test) {
        test_count++;
        String s;
        if (test)
            s = String.format("ok %d", test_count);
        else
            s = String.format("NOT ok %d", test_count);
        System.out.println(s);
        return;
    }
}

Clojure (with changes suggested in the comments by rnewman).


(defn steal? [steal base]
  (let [map-update (fn [m i f]
                     (assoc! m i (f (get m i 0))))
        steal-map    (reduce #(map-update %1 %2 inc)
                             (transient {}) steal)
        combined-map (persistent!
                       (reduce #(map-update %1 %2 dec)
                               steal-map base))]
    (not (some #(< (int %) (int 0))
         (vals combined-map)))))

(defn ok [test] (println (if test "ok" "NOT ok")))

(ok (not (steal? "proud" "rrod")))
(ok (steal? "proud" "rod"))
(ok (steal? "devil" "live"))
(ok (not (steal? "foo" "bar")))

(update 2010-12-23) Ruby


require 'test/unit'

class GrabScrab < Test::Unit::TestCase

  def steal?(steal, base)
    letters = steal.each_byte.inject(Hash.new(0)){ |h, c| h[c] += 1; h}
    base.each_byte { |c| return false if letters[c] == 0; letters[c] -= 1 }
    true
  end

  def test_grabscrab
    assert(!steal?("strip", "strep"))
    assert(!steal?("quit", "quiet"))
    assert(steal?("proud", "rod"))
    assert(steal?("devil", "live"))
    assert(steal?("smash", "mass"))
  end

end

Scala

def isSteal(str1: String, str2: String): Boolean = 
  !str2.foldLeft( str1.foldLeft( Map[Char, Int]() ){ 
    (m, c) => m + (c -> (m.getOrElse(c, 0) + 1)) 
  } ){ 
    (m, c) => m + (c -> (m.getOrElse(c, 0) - 1))
  }.values.exists(_<0)

assert(isSteal("quiet", "quit"))
assert(!isSteal("strip", "strep"))
assert(!isSteal("quit", "quiet"))
assert(isSteal("proud", "rod"))

6 Responses to Grabscrab

  1. robstar says:

    here’s a simplistic translation of your Clojure into scheme. it runs under guile 1.6, guile 1.8, and mzscheme. i suspect there are functions to update an a-list that i didn’t know about that would simplify map-update a bit.

    –Rob*

    (define (filter test lis)
      (if (null? lis)
          lis
          (let ((head          (car lis))
                (filtered-rest (filter test (cdr lis))))
            (if (test head)
                (cons head filtered-rest)
                filtered-rest))))
    
    (define (reduce op seed lis)
      (if (null? lis)
          seed
          (op (reduce op seed (cdr lis))
              (car lis))))
    
    (define (1+ x) (+ x 1))
    (define (1- x) (- x 1))
    
    (define (is-steal steal-s base-s)
      (let  (( steal (string->list steal-s) )
             ( base  (string->list base-s)  ))
        (let* (( map-update   (lambda (m i func default)
                                (let ((prev (assoc i m))
                                      (rest (filter (lambda (p)
                                                      (not (equal? (car p) i)))
                                                    m)))
                                  (cons (list i (if prev
                                                    (func (cadr prev))
                                                    default))
                                        rest))))
               ( steal-map    (reduce (lambda (m i) (map-update m i 1+ 1))
                                      '() steal) )
               ( combined-map (reduce (lambda (m i) (map-update m i 1- -1))
                                      steal-map base) )
               ( missings     (filter (lambda (x) (< x 0))
                                      (map cadr combined-map)) ))
          (null? missings))))
    
    (define (ok test) (display (if test "ok" "NOT ok")) (newline))
    
    (ok (not (is-steal "proud" "rrod")))
    (ok (is-steal "proud" "rod"))
    (ok (is-steal "devil" "live"))
    (ok (not (is-steal "foo" "bar")))
  2. robstar says:

    sort&zipper.
    –Rob*

    
    (define (extras super sub)
      (if (null? sub) super
          (if (null? super) #f
              (let ((fsup (car super))
                    (fsub (car sub)))
                (if (char=? fsup fsub) (extras (cdr super) (cdr sub))
                    (if (char< ? fsup fsub) (extras (cdr super) sub)
                        #f))))))
    
    (define (is-steal steal base)
      (let ((steal (sort (string->list steal) char< ?))
            (base  (sort (string->list base) char< ?)))
        (extras steal base)))
    
    (define (ok test) (display (if test "ok" "NOT ok")) (newline))
    
    (ok (not (is-steal "proud" "rrod")))
    (ok (is-steal "proud" "rod"))
    (ok (is-steal "devil" "live"))
    (ok (not (is-steal "foo" "bar")))
    (ok (is-steal "bananas" "bans"))
    (ok (not (is-steal "bananas" "babs")))
    
    
  3. rnewman says:

    This version of the Clojure code is shorter, more idiomatic, and takes 2/3 the time to run.

        (defn steal? [steal base]
          (let [map-update (fn [m i f]
                             (assoc! m i (f (get m i 0))))
                steal-map    (reduce #(map-update %1 %2 inc)
                                     (transient {}) steal)
                combined-map (persistent!
                               (reduce #(map-update %1 %2 dec)
                                       steal-map base))]
            (not (some #(< (int %) (int 0))
                 (vals combined-map)))))
    
  4. rnewman says:

    Wow, it’d be awesome if you could fix the code layout in that comment. Did I mention I hate WordPress?

  5. nohat says:

    I’m discovering that WordPress isn’t very good at code snippets. All the comments have been fixed. I am researching things that can be done to improve things…

  6. cpaez26 says:

    ColdFusion solution

    
    <cffunction name="is_steal" returntype="boolean">
        <cfargument name ="bigword">
        <cfargument name="littleword">
     
    <cfset matches = 0>
    <cfloop from ="1" to="#len(littleword)#" index="i">
        <cfif findnocase("#mid(littleword,i,1)#", bigword)>
            <cfset matches++>
    		<cfset bigword=#replace(bigword,mid(littleword,i,1),"")#>
        </cfif>
    </cfloop>
    
        <cfif matches eq #len(littleword)#>
            <cfreturn true>
        <cfelse>
            <cfreturn false>
        </cfif>
    </cffunction>
    
    <cfoutput>
    is_steal("test","tes")
    #is_steal("test","tes")# <br />
    is_steal("test","abc")
    #is_steal("test","abc")# <br />
    is_steal("deevvil","devil")
    #is_steal("deevvil","devil")#<br />
    is_steal("aaaab","abb")
    #is_steal("aaaab","abb")#<br />
    </cfoutput>

    -Carlos

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 
To comment, click below to log in.