Google Code Jam Qualification Round Africa 2010

February 15, 2011

Today’s three programming exercises come from the Google Code Jam Qualification Round Africa 2010:

Store Credit: You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first). For instance, with C=100 and L={5,75,25} the solution is 2,3; with C=200 and L={150,24,79,50,88,345,3} the solution is 1,4; and with C=8 and L={2,1,9,4,4,56,90,3} the solution is 4,5.

Reverse Words: Given a list of space separated words, reverse the order of the words. Each input string contains L letters and W words. An input string will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words. For instance, the reverse of “this is a test” is “test a is this”, the reverse of “foobar” is “foobar”, and the reverse of “all your base” is “base your all”.

T9 Spelling: The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as 2=ABC, 3=DEF, 4=GHI, 5=JKL, 6=MNO, 7=PQRS, 8=TUV, 9=WXYZ. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character should be printed to indicate a pause. For example “2 2″ indicates AA whereas “22” indicates B. Each message will consist of only lowercase characters a-z and space characters. Pressing zero emits a space. For instance, the message “hi” is encoded as “44 444″, “yes” is encoded as “999337777”, “foo  bar” (note two spaces) is encoded as “333666 6660022 2777″, and “hello world” is encoded as “4433555 555666096667775553″.

Your task is to solve the three Code Jam exercises. 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.

About these ads

Pages: 1 2

23 Responses to “Google Code Jam Qualification Round Africa 2010”

  1. Veer said

    for first one , i think we can use hash table.

    (define (index credit lst)
      
      (define hash (make-hash))
      
      (let loop ([i 1] [lst lst])
        (cond
          [(empty? lst) #f]
          [else (let ([diff (- credit (first lst))])
                  (let ([exist (hash-ref hash diff #f)])
                    (if exist
                        (list exist i)
                        (begin
                          (hash-set! hash (first lst) i)
                          (loop (+ i 1) (rest lst))))))])))
      
      
    (index 100 '(5 75 25))
    (index 200 '(150 24 79 50 88 345 3))
    (index 8 '(2 1 9 4 4 56 90 3))
    
  2. Graham said

    I’m sure there’s a cleverer way to solve the store credit question, but it
    eludes me this morning. Although my solutions look very similar to the official
    ones, I didn’t look ahead this time, scout’s honor.

    #!/usr/bin/env python
    
    
    # Problem 1
    def store_credit(C, L):
        for i in xrange(len(L) - 1):
            try:
                i2 = L.index(C - L[i], i + 1)
                return [i + 1, i2 + 1]
            except ValueError:
                pass
        return None
    
    
    # Problem 2
    def reverse_words(in_str):
        return ' '.join(w for w in in_str.split(' ')[::-1])
    
    
    # Problem 3
    t9_dict = {'a': '2', 'b': '22', 'c': '222', 'd': '3', 'e': '33', 'f': '333',
                'g': '4', 'h': '44', 'i': '444', 'j': '5', 'k': '55', 'l': '555',
                'm': '6', 'n': '66', 'o': '666', 'p': '7', 'q': '77', 'r': '777',
                's': '7777', 't': '8', 'u': '88', 'v': '888', 'w': '9', 'x': '99',
                'y': '999', 'z': '9999'}
    
    
    def t9_spelling(message):
        t9_message, prev = '', ' '
        for char in message:
            if char == ' ':
                t9_message += '0'
                prev = '0'
            elif prev in t9_dict[char]:
                t9_message += (' ' + t9_dict[char])
                prev = t9_dict[char][0]
            else:
                t9_message += (t9_dict[char])
                prev = t9_dict[char][0]
        return t9_message
    
  3. Kevin Fletcher said

    I came up with the same solution as above. This plays on the fact that there is only one solution to the problem (so repeat numbers don’t matter) and the number of items we are looking for is always 2. A change to either of these prerequisites would need a different solution.

    def store01 (credit, items):
    lookup = {}
    for (elem, cost) in enumerate(items):
    find = credit – cost
    if find in lookup: return lookup[find], elem + 1
    lookup[cost] = elem + 1

    print store01(100, [5, 75, 25])
    print store01(200, [150, 24, 79, 50, 88, 345, 3])
    print store01(8, [2, 1, 9, 4, 4, 56, 90, 3])

    # =>
    # (2, 3)
    # (1, 4)
    # (4, 5)

  4. def credit_ops(C, L):
        """
        Optimise purchase to a credit
        >>> credit_ops(100,[5,75,25])
        (2, 3)
        >>> credit_ops(200, [150,24,79,50,88,345,3])
        (1, 4)
        >>> credit_ops(8, [2,1,9,4,4,56,90,3])
        (4, 5)
        """
        for i,v in enumerate(L):
            for j, w in enumerate(L):
                if i == j:
                    continue
                if (v + w) == C:
                    return i+1,j+1
    
    def reverse_words(S):
        """
        >>> reverse_words("this is a test")
        'test a is this'
        >>> reverse_words("foobar")
        'foobar'
        >>> reverse_words("all your base")
        'base your all'
        """
        words = S.split(" ")
        words.reverse()
        return " ".join(words)
    
    def t9_spelling(S):
        """
        “hi” is encoded as “44 444″, “yes” is encoded as “999337777″, “foo  bar” (note two spaces) is encoded as “″, and “” is encoded as “4433555 555666096667775553″.
        >>> t9_spelling("hi")
        '44 444'
        >>> t9_spelling("yes")
        '999337777'
        >>> t9_spelling("foo  bar")
        '333666 6660022 2777'
        >>> t9_spelling("hello world")
        '4433555 555666096667775553'
        """
        t9_dict = {'a': '2', 'b': '22', 'c': '222', 'd': '3', 'e': '33', 'f': '333',
                'g': '4', 'h': '44', 'i': '444', 'j': '5', 'k': '55', 'l': '555',
                'm': '6', 'n': '66', 'o': '666', 'p': '7', 'q': '77', 'r': '777',
                's': '7777', 't': '8', 'u': '88', 'v': '888', 'w': '9', 'x': '99',
                'y': '999', 'z': '9999', ' ':'0'}
        retstr=""
        for c in S:
            if len(retstr) > 1 and c != " " and t9_dict[c][-1] == retstr[-1]:
                retstr+=" "
            retstr += t9_dict[c]
        return retstr
    
    if __name__ == "__main__":
        import doctest
        doctest.testmod()
    
  5. My Haskell solution (see http://bonsaicode.wordpress.com/2011/02/15/programming-praxis-google-code-jam-qualification-round-africa-2010/ for a version with comments):

    import Data.List
    
    storeCredit :: Num a => a -> [a] -> (Int, Int)
    storeCredit c xs = head [ (i, j) | (i, a) <- zip [1..] xs
                            , (j, b) <- drop i $ zip [1..] xs, a + b == c]
    
    reverseWords :: String -> String
    reverseWords = unwords . reverse . words
    
    t9 :: String -> String
    t9 s = unwords =<< groupBy (\(a:_) (b:_) -> a == b && a > '0') (map f s)
        where f c = maybe "0" id . lookup c . concat $ zipWith zip
                        (words "abc def ghi jkl mno pqrs tuv wxyz")
                        [[replicate n d | n <- [1..]] | d <- ['2'..]]
    
  6. slabounty said

    A pretty ugly ruby version …

    def store_credit(c, l)
        l.each_with_index do |v1, i|
            l.each_with_index do |v2, j|
                return i, j if v1+v2 == c
            end
        end
    end
    
    class String
        def reverse_words
            self.split(/ /).reverse.join(" ")
        end
    
        def t9_encode
            letters = {
                " " => "0",
                "a" =>"2", "b" =>"22", "c" =>"222",
                "d" =>"3", "e" =>"33", "f" =>"333",
                "g" =>"4", "h" =>"44", "i" =>"444",
                "j" =>"5", "k" =>"55", "l" =>"555",
                "m" =>"6", "n" =>"66", "o" =>"666",
                "p" =>"7", "q" =>"77", "r" =>"777", "s" =>"7777",
                "t" =>"8", "u" =>"88", "v" =>"888",
                "w" =>"9", "x" =>"99", "y" =>"999", "z" =>"9999"}
            s = ""
            self.each_char do |c|
                s << " " if s[s.length-1] == letters[c][0] and s[s.length-1] != "0"
                s << letters[c]
            end
            s
        end
    end
    
    
    puts store_credit(100, [5, 75, 25])
    puts store_credit(200, [150, 24, 79, 50, 88, 345, 3])
    
    puts "this is a test".reverse_words
    
    puts "hi = #{"hi".t9_encode}"
    puts "yes = #{'yes'.t9_encode}"
    puts "foo  bar = #{'foo  bar'.t9_encode}"
    puts "hello world = #{'hello world'.t9_encode}"
    
  7. Axio said

    ;; I apologize in advance if this is posted thrice. Even though I refresh the page, my post doesn’t show up…

    (defun shop (val l)
      (maplist (lambda (x)
                 (let ((x (car x)) (xs (cdr x)))
                   (mapcar (lambda (r) (if (= val (+ x r))
                                         (return-from shop (cons (position x l) (position r l)))))
                           xs)))
               l))

    (defun rev (str)
      (let (l w)
        (loop for c across str
              if (char= #\space c)
              do (when w
                   (push (reverse w) l)
                   (setf w nil))
              else do (push c w))
        (reduce (lambda (x y) (concatenate ‘string x ” ” y))
                (mapcar (lambda (x) (concatenate ‘string x))
                        (if w
                          (cons (reverse w) l)
                          l)))))

    (defun t9 (str)
      (let ((h (make-hash-table))
            res
            (last #\Nul))
        (mapcar (lambda (letter code)
                  (setf (gethash letter h) code))
                (loop for l across “abcdefghijklmnopqrstuvwxyz ” collect l)
                (list “2” “22” “222” “3” “33” “333” “4” “44” “444”
                      “5” “55” “555” “6” “66” “666” “7” “77” “777” “7777”
                      “8” “88” “888” “9” “99” “999” “9999” “0”))
        (loop for c across str
              for now = (gethash c h)
              if (and (not (char= last #\0))
                      (char= (aref now 0) last))
              do (push (concatenate ‘string ” ” now) res)
              else do
              (setf last (aref now 0))
              (push now res))
        (reduce (lambda (x y) (concatenate ‘string x y)) (reverse res))))

  8. Mike said
    def store_credit(credit, items):
        d = {}
        for item,price in enumerate(items,1):
            if price in d:
                return d[price], item
            else:
                d[credit-price] = item
    
    
    def reverse_words(phrase):
        return ' '.join(reversed(phrase.split()))
    
    
    keymap = " ,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz".split(',')
    
    code = {char:str(key)*repeat
    	    for key,label in enumerate(keymap)
    	    for repeat,char in enumerate(label,1)}
    
    def pad(lt, rt):
        if '0' != rt[:1] == lt[-1:]:
            lt += ' '
        return lt + rt
    
    def T9(s):
        return reduce(pad, map(code.get, s))
    
    # 
    # Or just for fun, lets use a regular expression:
    #
    import re
    
    # The pattern uses Python's regular expression extensions to match superfluous spaces in the encoded string.  That is, the pattern
    # matches a digit followed by a space, but only if the digit is '0' or the digit is different than what comes after the space.
    # So the pattern will match '0 ' in "210 012" and '1 ' will match in '21 21', but not in '21 12'.
    
    def T9(s):
        return re.sub(r"(0|([1-9])) (?(2)(?!\2))", r"\1", ' '.join(map(code.get, s)))
    
  9. Rainer said
    
    
    1. Store Credit
    --------------
    
    say 'Credit    Items                                   Result'
    say copies('-', 60)
    zeile = ''; zahl = 100; liste = '5 75 25'
    say format_zeile(zahl, liste)
    zeile = ''; zahl = 200; liste = '150 24 79 50 88 345 3'
    say format_zeile(zahl, liste)
    zeile = ''; zahl = 8; liste = '2 1 9 4 4 56 90 3'
    say format_zeile(zahl, liste)
    
    exit
    
    
    format_zeile: procedure
        arg zahl, liste
        zeile = ''
        zeile = overlay(format(zahl,8), zeile, 1, 10)
        zeile = overlay(liste, zeile, 11, 50)
        zeile = overlay(sc(zahl, liste), zeile, 51, 10)
        return zeile
    
    sc: procedure
        arg credit, itemsstr
        aus = ''
        items. = ''
        i = 0
        do while length(itemsstr) > 0
    	parse value itemsstr with first itemsstr
            i = i + 1
            items.0 = i
            items.i = first
        end
        do a = 1 to items.0
            do b = 1 to items.0
                if b == a then iterate
                    if (items.a + items.b) == credit then do
                        if a < b then aus = a||','||b
    		    				 else aus = b||','||a
                        leave a
    		        end
    	    end b
        end a
        return aus
    
    
    2. Reverse Words
    ----------------
    
    lire = 'this is a test'
    say 'Die Umkehrung von <'lire'> = <'reverse_words(lire)'>'
    lire = 'foobar'
    say 'Die Umkehrung von <'lire'> = <'reverse_words(lire)'>'
    lire = 'all your base'
    say 'Die Umkehrung von <'lire'> = <'reverse_words(lire)'>'
    
    exit
    
    reverse_words: procedure
        parse arg lr
        rl = ''
        do while words(lr) > 0
            rl = rl word(lr,words(lr))
            lr = delword(lr,words(lr),1)
        end
        return strip(rl)
    
    
    3. T9 Spelling
    --------------
    
    codes = '2=ABC 3=DEF 4=GHI 5=JKL 6=MNO 7=PQRS 8=TUV 9=WXYZ'
    
    say '"hi"' 'wird codiert als ' aufber('hi')
    say '"yes"' 'wird codiert als ' aufber('yes')
    say '"foo  bar"' 'wird codiert als ' aufber('foo  bar')
    say '"hello world"' 'wird codiert als ' aufber('hello world')
    
    exit
    
    aufber:
        parse arg nachricht
        return encode(nachricht)
    
    encode:
        parse arg msg
        aus = ''
        prv = ''
        do i = 1 to length(msg)
            z = substr(msg, i, 1)
    	    /* Blanks werden als '0' codiert */
            if z == ' ' then ncode = '0'
    	                else ncode = num_code(z)
            if ncode \= '0' & left(ncode,1) == prv then
                aus = aus' '
            aus = aus||ncode
            prv = left(ncode,1) 	
        end
        return aus
    
    num_code:
        arg zeichen
        p = pos(zeichen, codes)
        p1 = lastpos('=', codes, p)
        p2 = p1-1
        return copies(substr(codes, p2, 1),(p-p1))
    
    
    
  10. Ramakrishna Chikkala said

    Link to C program to reverse words (Exercise 2)

    http://codepad.org/7BoFTaIL

  11. Here are Java functions for each exercise:

        public int[] storeCredit(int credit, int... items){
            for(int i = 0; i < items.length; i++){
                for(int j = i + 1; j < items.length; j++){
                    if(items[i] + items[j] == credit)
                        return new int[]{i + 1, j + 1};
                }
            }
            return null;
        }
    
        public String reverseWords(String words){
            String[] w = words.split(" ");
            String reversed = "";
            for(int i = w.length - 1; i >= 0; i--){
                reversed += w[i] + " ";
            }
            return reversed.trim();
        }
    
        public String T9Spelling(String message) {
            message = message.toUpperCase();
            String encodedMsg = "";
            for (int i = 0; i < message.length(); i++) {
                if(message.charAt(i) == ' '){
                    encodedMsg += "0";
                    continue;
                }
                for (int key = 2; key <= 9; key++) {
                    String group = keypad.get(key);
                    
                    if (group.contains(message.charAt(i) + "")) {
                        int reps = group.indexOf(message.charAt(i) + "") + 1;
                        for (int j = 1; j <= reps; j++) {
                            encodedMsg += key + "";
                        }
    
                        // Lookahead for space insertion
                        if ((i + 1) < message.length() && group.contains(message.charAt(i + 1) + "")) {
                            encodedMsg += " ";
                        }
                    }
                }
            }
            return encodedMsg;
        }
    

    The source code in its entirety, which includes the definition of the hash map that’s used for exercise 3, can be read here.

  12. s=str(raw_input(‘Enter something’))
    set1=s.split()
    list1=[]
    rev=[]
    s4=”
    for s1 in set1:
    list1.append(s1)
    while list1:
    s3=list1.pop()
    s4+=s3
    s4+=’ ‘

    print s4
    [/source code]

  13. s=str(raw_input('Enter something'))
    set1=s.split()
    list1=[]
    rev=[]
    s4=''
    for s1 in set1:
        list1.append(s1)     
    while list1:
        s3=list1.pop()    
        s4+=s3
        s4+=' '
      
    print s4   
    
  14. Jebb said

    Yet another set of Python solutions.

    #!/usr/bin/python
    
    ## Store Credit
    def storeCredit(C, L):
    	assert type(C) == int
    	assert type(L) == list
    	return [(i,j) for (i,x) in enumerate(L)
    	              for (j,y) in enumerate(L)
    	              if x + y == C
    	              if i != j][0]
    
    ## Reverse words
    def reverseWords(text):
    	return ' '.join(text.split().__reversed__())
    
    ## T9 spelling: decoding
    T9toAlpha = {'0':' ',
                 '2':'A', '22':'B', '222':'C',
                 '3':'D', '33':'E', '333':'F',
                 '4':'G', '44':'H', '444':'I',
                 '5':'J', '55':'K', '555':'L',
                 '6':'M', '66':'N', '666':'O',
                 '7':'P', '77':'Q', '777':'R', '7777':'S',
                 '8':'T', '88':'U', '888':'V',
                 '9':'W', '99':'X', '999':'Y', '9999':'Z'}
    
    def decodeT9(Num):
    	import re
    	matches = re.findall(r'(([0-9])\2*)', Num)
    	T9_codes = [x for (x,y) in matches]
    	return ''.join([T9toAlpha[code] for code in T9_codes])
    
    ## ...and encoding
    AlphaToT9 = {' ': '0', 'A': '2', 'C': '222', 'B': '22', 'E': '33', 'D': '3', 'G': '4', 'F': '333', 'I': '444', 'H': '44', 'K': '55', 'J': '5', 'M': '6', 'L': '555', 'O': '666', 'N': '66', 'Q': '77', 'P': '7', 'S': '7777', 'R': '777', 'U': '88', 'T': '8', 'W': '9', 'V': '888', 'Y': '999', 'X': '99', 'Z': '9999'}
    
    def encodeT9(text):
    	from itertools import imap
    	number_groups = []
    	for letter in text.upper():
    		number_groups.append(AlphaToT9[letter])
    	def helper(A, B):
    		if A[0]==B[0]: return A + ' '
    		else: return A
    	return ''.join(imap(helper, number_groups, number_groups[1:] + [' ']))
    
  15. Jebb said

    I had to have a go at the Reverse Words exercise in C, in-place. I’d imagine this is a classic of programming interviews; first reverse the letters in each of the words, then reverse the whole string:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define is_word_char(A) \
    	(((A) >= 'a' && (A) <= 'z') || \
    	 ((A) >= 'A' && (A) <= 'Z') || \
    	 ((A) >= '0' && (A) <= '9'))
    	
    /* ----------------------------- 
     * Ugly macro implementation of swap, just for fun. 
     * Careful when reusing, 
     * definitely not threadsafe 
     * (because of the global variable) */
    #define swapchar(A,B) \
    	do { \
    		tmp_swap_char = *(A); \
    		*(A) = *(B); \
    		*(B) = tmp_swap_char; \
    	} while (0)
    char tmp_swap_char;
    /* ----------------------------- */
    
    void reverse_from_to(char *from, char *to)
    {
    // Reverses part of a string, between *from and *to
    	int i;
    	for (i = 0; i < (to - from + 1) / 2; i++)
    		swapchar(from + i, to - i);
    }
    
    char* reverse_words_in_string(char *str)
    {
    	char *cp;	//points to character within a word
    	char *wp = str;	//points to the start of a word
    	while (*wp != '\0') {
    		if (is_word_char(*wp)) {
    			cp = wp;
    			while (is_word_char(*(cp + 1)))
    				cp++;
    			reverse_from_to(wp, cp);
    			wp = cp;	//now jump to the end of the word
    		}
    		wp++;
    	}
    	reverse_from_to(str, str + strlen(str) - 1);
    	return str;
    }
    
  16. Khanh Nguyen said

    In F#…

    
    let store_credit (L: int list) (C: int) =
        let n = List.length L
        [for i in 0 .. n-1 do
            for j in i+1 .. n-1 do
                if L.[i] + L.[j] = C then yield (i+1,j+1)]
        |> List.head
    store_credit [5;75;25] 100
    store_credit [150;24;79;50;88;345;3] 200
    store_credit [2;1;9;4;4;56;90;3] 8
    
    
    let reverse_words (s: string) =
        s.Split() |> Array.rev |> Array.toSeq |> String.concat " "
        
    reverse_words "this is a test"    
    reverse_words "foobar"
    reverse_words "all your base"
    
    let data = [(2,"ABC"); (3,"DEF"); (4,"GHI"); 
                (5,"JKL"); (6,"MNO"); (7,"PQRS"); 
                (8,"TUV"); (9,"WXYZ")]
    let decode_T9 (c: char) =          
        let cc = (string c).ToUpper()
        let map (code:int, s:string) =
            String.replicate (s.IndexOf(cc)+1) (string code)
        List.filter (fun (_,s:string) -> s.Contains(cc)) data |> List.head |> map
    
    let same_key (a:char) (b:char) = 
        let aa = (string a).ToUpper()
        let bb = (string b).ToUpper()
        data |> List.exists (fun (_, s:string) -> s.Contains(aa) && s.Contains(bb)) 
    
    let T9_spelling (s:string) = 
        s.ToCharArray() |> List.ofArray 
                        |> List.fold (fun (prev, res) c -> 
                                            if   c = ' ' then (c, res + "0")
                                            elif same_key c prev then (c, res + " " + (decode_T9 c))
                                            else
                                                (c, res + (decode_T9 c))
                                      )               
                            (' ',"")
                        |> snd
                            
    T9_spelling "foo  bar"
    T9_spelling "yes"
    T9_spelling "hi"
    
    
  17. Tony said

    I would like to be on the mailing list for new posts.

    Thank you,
    Tony

  18. programmingpraxis said

    There is an RSS icon on the About page. Or you can subscribe via WordPress.

  19. Vikas Tandi said

    C implementation of reverse words:

    static void reverse_char(char *s, char *delm);
    
    void reverse_word_improved(char *s)
    {
    	char *p, *q;
    
    	for(p = s; *p == ' '; p++);
    
    	for(q = p; ; q++)
    	{
    		if(*q == ' ')
    		{
    			reverse_char(p, q);
    			p = q+1;
    		}
    
    		if(*q == '\0')
    		{
    			reverse_char(p, q);
    			break;
    		}
    	}
    
    	reverse_char(s, q);
    }
    
    /* reverse non-empty string */
    static void reverse_char(char *s, char *delm)
    {
    	char *p, *q;
    
    	for(q = s; (q+1) != delm; q++);
    
    	for(p = s; p < q; p++, q--)
    	{
    		char t;
    
    		t = *p;
    		*p = *q;
    		*q = t;
    	}
    }
    
  20. homanhduc said

    T9 number :

    #include <iostream>
    #include <string>
    using namespace std;
    
    string T9[] = {"0", "0", "abc", "def", "ghi",
    	         "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int main()
    {
    	string input;
    	cout << "Please enter your text: ";
    	getline(cin,input);
    	
    	int i = 0, j, k, l;
    	while (i < input.length())
    	{
    		if (input[i] == ' ')
    		{
    			++i;
    			continue;
    		}	
    		//j = counter variable to iterate T9 string arr
    		for (j = 0; j < 10; ++j)
    		{
    			//find the position of the char
    			//within the mapped pad[T9]
    			l = T9[j].find(input.substr(i,1));
    			//break point
    			if (l != -1)
    				break;
    		}
    		
    		//print out the number to press
    		//l = how many times to press to get a j key
    		for (k = 0; k <= l; ++k)
    			cout << j;
    		cout << " "; 
    		i++;
    	}
    
    	return 0;
    }
    
  21. my Python implementation:

    def credits(C, L):
    	return [(i+1,j+1) for i in range(len(L)) for j in range(i+1, len(L)) if L[i] + L[j] == C] 
    	
    def reverse(s):
    	s = s.split()
    	s.reverse()
    	return ' '.join(s)
    
    def spell(s):
    	code = []
    	for char in s:
    		if char == ' ':
    			code.append(str(0))
    		else:	
    			value,index = findValueIndex(char)
    			if code:
    				if str(value) == code[-1]:
    					code.append(' ')
    			for i in range(index):
    				code.append(str(value))
    	print ''.join(code)
    	
    def findValueIndex(c):
    	map = {'abc': 2, 'def': 3, 'ghi':4, 'jkl':5, 'mno':6, 'pqrs':7, 'tuv':8, 'wxyz':9}
    	return [(map[key], key.index(c)+1) for key in map.keys() if c in key][0]
    	
    
  22. AlexR said

    Here is a Python program for the store credit problem. The basic idea is to store the prices and indices in a dictionary and iterate over the dictionary, where at each step we look for the complementary price. Since dictionary look-up is constant time on average, this is a linear-time algorithm in the average case. It is also linear-space.

    def find_pair(credit, prices):
        # Make a dictionary with items of the form
        # (price, set of indices of items with that price).
        # Note that the price list could contain duplicate prices.
        d = dict()
        for (i, p) in enumerate(prices):
            d[p] = d.get(p, set())
            d[p].add(i + 1)  # + 1 to index from 1 instead of 0.
        for price in d.keys():
            if price <= credit:
                # Remove price index from d.
                i = d[price].pop()
                # Check whether there's a complementary price in d.
                if credit - price in d:
                    # This works even if price == credit - price.
                    j = d[credit - price].pop()
                    return min(i, j), max(i, j)
                # Reinsert price index into d.
                d[price].add(i)
        return "Sorry, no pair of item costs sum to %s" % credit
    

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

Follow

Get every new post delivered to your Inbox.

Join 622 other followers

%d bloggers like this: