def assert_equal(x, y)
  raise [x, y].inspect unless x == y
end

class Card
  attr_reader :raw, :prefix, :letter, :number
  BITS = {
    "+" => 256,
    "-" => 128,
    "=" => 64,
    "A" => 32,
    "B" => 16,
    "C" => 8,
    "1" => 4,
    "2" => 2,
    "3" => 1,
  }

  def initialize(raw)
    @raw = raw
    @prefix = raw[0]
    @letter = raw[1]
    @number = raw[1..-1].size
  end

  def <=>(other)
    self.score <=> other.score
  end

  def score
    @score ||= begin
      score = 0
      score += BITS[prefix]
      score += BITS[letter]
      score += BITS[number.to_s]
      score
    end
  end

  def match?(*others)
    others << self
    [:prefix, :letter, :number].each do |property|
      x = others.map(&property).uniq.count
      return false if x != 1 && x != others.size
    end

    true
  end

  def to_s
    raw
  end
end

class Solution
  # time: O(n^3)
  # space: O(n) ?
  def run(row)
    cards = row.split
    cache = Hash.new do |hash, key|
      hash[key] = Card.new(key)
    end

    for i in (0...cards.size)
      x = cache[cards[i]]
      for p in (i+1...cards.size)
        y = cache[cards[p]]
        for q in (p+1...cards.size)
          z = cache[cards[q]]

          if x.match?(y, z)
            return [x, y, z].join(' ')
          end
        end
      end
    end

    ""
  end

=begin
|4|2|1|
|+|-|=|

|4|2|1|
|A|B|C|

123

|256|128| 64| 32| 16|  8|  4|  2|  1|
|  +|  -|  =|  A|  B|  C|  1|  2|  3|

-A: 128 + 32 + 3
-B: 128 + 16 + 3

=end
  def run(row)
    cards = row.split.map { |x| Card.new(x) }
    for i in (0...cards.size)
      x = cards[i]
      for p in (i+1...cards.size)
        y = cards[p]
        for q in (p+1...cards.size)
          z = cards[q]
          return [x, y, z].join(' ') if x.match?(y, z)
        end
      end
    end

    ""
  end
end

assert_equal(true, Card.new("+C").match?(Card.new("-CC"), Card.new("=CCC")))
assert_equal(true, Card.new("-A").match?(Card.new("-B"), Card.new("-C")))
assert_equal(false, Card.new("-A").match?(Card.new("-B"), Card.new("-BB")))
assert_equal(false, Card.new("-A").match?(Card.new("-BBB"), Card.new("-CCC")))

solution = Solution.new
result = solution.run("-A -B -BB +C -C -CC =CCC")
assert_equal(true, result == "+C -CC =CCC" || result == '-A -B -C')
assert_equal("", solution.run("-A +B -BB +C -C -CC +CCC"))
assert_equal("", solution.run("-A"))
assert_equal("", solution.run("-A +B"))
assert_equal("", solution.run("-A +B +C"))
assert_equal("-A +B =C", solution.run("-A +B =C"))
assert_equal("-A +BB =CCC", solution.run("-A +BB =CCC"))
assert_equal("", solution.run("-A -BB =CCC"))
assert_equal("+A +A +A", solution.run("+A +A +A"))
assert_equal("", solution.run("+A +A +B"))
puts "Yay!"