Solution of GCJ's Magicka problem

magicka.rb

RUN_TEST = false

require 'set'
require 'test/unit' if RUN_TEST

class Magicka
    def initialize(combines, opposes)
        @combs = build_combs(combines)
        @opps = build_opps(opposes)
        @counts = Hash.new(0)
        @items = []
    end
    
    def build_combs(combs)
        ans = Hash.new
        combs.each do |str|
            x, y, z = str.split('')
            add_comb(ans, x, y, z)
            add_comb(ans, y, x, z)
        end
        ans
    end
    
    def add_comb(hash, x, y, z)
        hash[x] ||= Hash.new
        hash[x][y] = z
        hash
    end

    def build_opps(opps)
        ans = Hash.new
        opps.each do |str|
            x, y = str.split('')
            add_opp(ans, x, y)
            add_opp(ans, y, x)
        end
        ans
    end

    def add_opp(hash, x, y)
        hash[x] ||= Set.new
        hash[x] << y
        hash
    end
    
    def add(item)
        if @items.empty?
            @items << item
            @counts[item] = 1
            return
        end
        last = @items.last
        combined = combination(last, item)
        if combined
            @items[-1] = combined
            @counts[last] -= 1
            @counts.delete(last) if @counts[last] == 0
            @counts[combined] += 1
            return
        end
        if explodes?(item)
            reset
            return
        end
        @items << item
        @counts[item] += 1
    end
    
    def combination(x, y)
        @combs[x][y] if @combs[x]
    end
    
    def explodes?(item)
        opps = @opps[item]
        return false unless opps
        opps.any? {|opp| @counts.include?(opp)}
    end
    
    def reset
        @items.clear
        @counts.clear
    end
    
    def solve(str)
        reset
        str.each_char do |item|
            add(item)
        end
        @items
    end
end

class TestMagicka < Test::Unit::TestCase
    def test_builds_combs
        m = Magicka.new(['ABC', 'BDA', 'XYZ'], ['AB', 'AD'])
        assert_equal 'C', m.combination('A', 'B')
        assert_equal 'C', m.combination('B', 'A')
        assert_equal 'A', m.combination('B', 'D')
        assert_equal 'A', m.combination('D', 'B')
        assert_equal 'Z', m.combination('X', 'Y')
        assert_equal 'Z', m.combination('Y', 'X')
        assert_nil m.combination('A', 'A')
        assert_nil m.combination('B', 'B')
        assert_nil m.combination('D', 'D')
        assert_nil m.combination('A', 'D')
        assert_nil m.combination('D', 'A')
    end
    
    def test_solve1
        m = Magicka.new(['QFT'], ['RF'])
        assert_equal ['T'], m.solve('QF')
        assert_equal ['Q', 'E', 'F'] , m.solve('QEF')
        assert_equal ['E'] , m.solve('RFE')
        assert_equal [] , m.solve('REF')
        assert_equal ['R', 'T'] , m.solve('RQF')
        assert_equal ['Q'] , m.solve('RFQ')
    end

    def test_solve2
        m = Magicka.new([], [])
        assert_equal ['E', 'A'], m.solve('EA')

        m = Magicka.new(['QRI'], [])
        assert_equal ['R', 'I', 'R'], m.solve('RRQR')

        m = Magicka.new(['QFT'], ['QF'])
        assert_equal ['F', 'D', 'T'], m.solve('FAQFDFQ')

        m = Magicka.new(['EEZ'], ['QE'])
        assert_equal ['Z', 'E', 'R', 'A'], m.solve('QEEEERA')

        m = Magicka.new([], ['QW'])
        assert_equal [], m.solve('QW')
    end
end if RUN_TEST

unless RUN_TEST
    n = gets.to_i
    1.upto(n) do |test_no|
        a = gets.chomp.split(' ')
        c = a[0].to_i
        combs = a[1..c]
    #    d = a[c+1].to_i
        opps = a[c+2..-2]
        invokes = a[-1]
        m = Magicka.new(combs, opps)
        ans = m.solve(invokes)
        puts "Case ##{test_no}: [#{ans.join ', '}]"
    end
end