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.
Programming Praxis 
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))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_messageI 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)
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()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'..]]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}";; 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))))
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)))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))Link to C program to reverse words (Exercise 2)
http://codepad.org/7BoFTaIL
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.
My Python Solution for second problem
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]
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 s4Yet 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:] + [' ']))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; }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"I would like to be on the mailing list for new posts.
Thank you,
Tony
There is an RSS icon on the About page. Or you can subscribe via WordPress.
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; } }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; }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]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