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.

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")
"""
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)}

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)

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)]
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.