jam Archives - Thought Provoking

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 (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

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

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

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 (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

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

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

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

M	T	W	T	F	S	S
« Jul
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Thought Provoking

iThinks

Tag Archives: jam

Google Code Jam 2014 Qualifiers

Magic Trick

Cookie Clicker Alpha

Deceitful War

Magic Trick

Cookie Clicker Alpha

Deceitful War

Share :