Google Code Jam 2011 Qualification Round

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(", ")}]"
end

Candy 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