# Google Code Jam 2014 Qualifiers

Google Code Jam has always been a competition I have cherished, simply because the problems they post are brilliant and the closest to reality as compared to problems of other competitions. They’re always fun to read, disect & solve, more often than not, the solutions are reasonably trivial (1)Especially for the qualifiers yet extremely subtle & deceptive.

Today I want to share the solutions of 3 problems I was able to solve, the code should pretty much speak for itself because none of it is very complex.

## Magic Trick #

This one was the easiest of all, more of a warmup I suppose. Here’s the solution :

```
def get_ans
gets.to_i
end
def get_arr
arr = []
4.times do
arr << gets.split.map(&:to_i)
end
arr
end
def get_ans_arr
[get_ans, get_arr]
end
def pout(x, y)
puts "Case ##{x}: #{y}"
end
def solve(a1, arr1, a2, arr2)
int = arr1[a1-1] & arr2[a2-1]
case int.size
when 0
'Volunteer cheated!'
when 1
int[0]
when 2..4
'Bad magician!'
end
end
gets.to_i.times do |i|
a1, arr1 = get_ans_arr
a2, arr2 = get_ans_arr
pout(i+1, solve(a1, arr1, a2, arr2))
end
```

## Cookie Clicker Alpha #

Based on Cookie Clicker game developed by Orteil, this one was slightly trickier, and required a little bit of math. I solved it with a recursive algorithm first, then optimized it into an iterative one to pass for the large input. Here’s my solution with both recursive and iterative parts :

```
RATE = 2.0
def trunc(y)
return y.round(7)
end
def pout(x, y)
puts "Case ##{x}: #{trunc(y)}"
end
def solve_rec(c, f, x, r, t)
return t + (x/r) if x <= c || (t + c/r + x/(r+f)) >= (t + x/r)
t += c/r
r += f
solve_rec(c, f, x, r, t)
end
def solve_itr(c, f, x)
t, r = 0.0, RATE
return x/r if x <= c
while (t + c/r + x/(r+f)) < (t + x/r)
t += c/r
r += f
end
t + x/r
end
gets.to_i.times do |i|
c, f, x= gets.split.map(&:to_f)
# pout(i+1, solve_rec(c, f, x, RATE, 0.0))
pout(i+1, solve_itr(c, f, x))
end
```

## Deceitful War #

This one was really subtle, easy enough to understand but hard to implement. It took me a while to put my understanding of how much being deceitful at the game called War translated to my points. Here too I solved both the normal game War and Deceitful War recursively first (2)It’s just easier to think recursively thanks to Lisp , then translated those to their iterative counterparts. Here is my solution with both recursive & iterative parts :

```
def pout(i, x, y)
puts "Case ##{i}: #{x} #{y}"
end
def pick_kn(kb, nbs)
kb.find do |kbi|
kbi > nbs
end || kb.first
end
def solve_war_rec(nb, kb, s)
return nb[0] > kb[0] ? s + 1 : s if nb.size == 1 && kb.size == 1
nbs = nb.shift
kbs = kb.delete(pick_kn(kb, nbs))
s += nbs > kbs ? 1 : 0
solve_war_rec(nb, kb, s)
end
def solve_war_itr(nb, kb)
return nb[0] > kb[0] ? 1 : 0 if nb.size == 1 && kb.size == 1
s = 0
while nb.size > 0 && kb.size > 0
nbs = nb.pop
kbs = kb.delete(pick_kn(kb, nbs))
s += nbs > kbs ? 1 : 0
end
s
end
def pick_dkn(kb, nbs)
kb.select do |kbi|
kbi < nbs
end.last || kb.first
end
def solve_dwar_rec(nb, kb, s)
return nb[0] > kb[0] ? s + 1 : s if nb.size == 1 && kb.size == 1
nbs = nb.pop
kbs = kb.delete(pick_dkn(kb, nbs))
s += nbs > kbs ? 1 : 0
solve_dwar_rec(nb, kb, s)
end
def solve_dwar_itr(nb, kb)
return nb[0] > kb[0] ? 1 : 0 if nb.size == 1 && kb.size == 1
s = 0
while nb.size > 0 && kb.size > 0
nbs = nb.pop
kbs = kb.delete(pick_dkn(kb, nbs))
s += nbs > kbs ? 1 : 0
end
s
end
gets.to_i.times do |i|
gets.to_i
nb = gets.split.map(&:to_f).sort
kb = gets.split.map(&:to_f).sort
# pout(i+1, solve_dwar_rec(nb.clone, kb.clone), solve_war_rec(nb.clone, kb.clone))
pout(i+1, solve_dwar_itr(nb.clone, kb.clone), solve_war_itr(nb.clone, kb.clone))
end
```