Google Code Jam Qualification Round Africa 2010
February 15, 2011
Solving the store credit exercise involves two nested loops i=0..len−1 and j=i+1..len−1, where len is the length of the list of items. The two items selected each time through the loop are summed and the solution reported (adding 1 to each index because the Google lists are one-based). Note the use of a Scheme idiom to conflate the two loops into one:
(define (store-credit c l)
(define (s i j)
(+ (vector-ref l i)
(vector-ref l j)))
(let ((len (vector-length l)))
(let loop ((i 0) (j 1))
(cond ((= i len) #f)
((= j len) (loop (+ i 1) (+ i 2)))
((= (s i j) c) (list (+ i 1) (+ j 1)))
(else (loop i (+ j 1)))))))
The reverse words exercise uses functions string-split
and string-join
from the Standard Prelude:
(define (reverse-words str)
(string-join #\space
(reverse
(string-split #\space str))))
In the T9 spelling exercise, the main loop indexes through the input string. The prev
variable keeps the previous output, so that two consecutive letters from the same family can be separated by a space, and is initialized to “0” which doesn’t require a space. When a space occurs,a “0” is added to the accumulating output and prev
is reset. When two consecutive letters from the same family occur in the input, a space is output and prev
is reset to “0”, but the input isn’t advanced, and the next input character is handled in the same way as any other input character:
(define (t9-spelling str)
(define (letter c) (- (char->integer c) 97))
(let ((letters #("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")))
(let loop ((ss (string->list str)) (prev "0") (cs '()))
(cond ((null? ss) (apply string-append (reverse cs)))
((char-whitespace? (car ss))
(loop (cdr ss) "0" (cons "0" cs)))
((string=? (substring prev 0 1)
(substring (vector-ref letters (letter (car ss))) 0 1))
(loop ss "0" (cons " " cs)))
(else (let ((next (vector-ref letters (letter (car ss)))))
(loop (cdr ss) next (cons next cs))))))))
You can run the program at http://programmingpraxis.codepad.org/qfH2FyIH.
for first one , i think we can use hash table.
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.
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)
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):
A pretty ugly ruby version …
;; 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))))
Link to C program to reverse words (Exercise 2)
http://codepad.org/7BoFTaIL
Here are Java functions for each exercise:
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]
Yet another set of Python solutions.
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:
In F#…
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:
T9 number :
my Python implementation:
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.