This Saturday Google Code Jam 2011 Qualification Round took place. I didn't have much time to spend on the problems, but still have solved a couple and proceeded to Round 1.
The ones that I solved are Magicka and Candy Splitting.
Magicka
First I tried to solve it with some cunning string substitution involving regular expressions. But in the end the simple simulation did the trick. I actually was a little bit disappointed after the official solutions were announced, because I thought that there should be some trick in here.
#!/usr/bin/ruby
lines = ARGF.readlines
t = lines.first.to_i
(1..t).each do |test_id|
arr = lines[test_id].split " "
c = arr[0].to_i
combines = arr[1..c].inject({}){|memo, e| memo[e[0..1]]=e[2]; memo[e[1]+e[0]]=e[2]; memo }
d = arr[c+1].to_i
opposed = arr[c+2..c+1+d]
n = arr[c+2+d].to_i
elems = arr[c+3+d] #.split("").collect {|i| i.to_sym }
result = []
elems.split("").each do |elem|
result << elem
if result.length > 1
last2 = result[-2..-1].join
if combines.key?(last2)
result.pop(2)
result = result << combines[last2]
end
opposed.each do |o|
if result.include?(o[0]) && result.include?(o[1])
result = []
break
end
end
end
end
puts "Case ##{test_id}: [#{result.join(", ")}]"
endCandy Splitting
This one was a little bit more tricky and the author's solution is much more simpler and clear than mine. I made it using old school brute force, just like Goro (strength is my strength :) )
#!/usr/bin/ruby
def s( candies, pile1, pile2 )
#p "c:#{candies}, 1:#{pile1}, 2:#{pile2}"
if candies.empty?
if !pile1.empty? && !pile2.empty? && pile1.inject(0){|memo, i| memo ^ i} == pile2.inject(0){|memo, i| memo ^ i}
return pile1
else
return false
end
end
x = candies.shift
p1 = pile1.clone
return s( candies, p1 << x, pile2) || s( candies, pile1, pile2 << x)
end
lines = ARGF.readlines
t = lines.first.to_i
(1..t).each do |test_id|
n_candies = lines[test_id*2-1]
candies = lines[test_id*2].split(" ").collect{|i| i.to_i }
r = s( candies.sort.reverse, [], [] )
r = !r ? "NO" : r.inject(:+)
puts "Case ##{test_id}: #{r}"
end