Solve in cubic time

2 files changed, 79 insertions, 4 deletions

diff --git a/misc/cards/README.md b/misc/cards/README.md
index 39d1c49..08dc244 100644
--- a/misc/cards/README.md
+++ b/misc/cards/README.md
@@ -6,6 +6,7 @@ cards that for each of three different properties are
 either all the same or all different.
 
 The properties of a card are:
+
 1. Prefix: "+", "-", or "="
 2. Letter: "A", "B", or "C"
 3. Number of letters: 1, 2, or 3 (e.g. A, AA, AAA)
@@ -28,9 +29,7 @@ there are two possible hands:
 
 Specifications:
 - You only need to find one hand
-- The cards should be read from STDIN,
-each card is separated by a space
-- Print the hand you find to STDOUT,
-space separated (trailing space is ok)
+- The cards should be read from STDIN, each card is separated by a space
+- Print the hand you find to STDOUT, space separated (trailing space is ok)
 - Cards may appear in any order in the input
 - Cards may be output in any order
diff --git a/misc/cards/main.rb b/misc/cards/main.rb
new file mode 100644
index 0000000..a44fcc4
--- /dev/null
+++ b/misc/cards/main.rb
@@ -0,0 +1,76 @@
+def assert_equal(x, y)
+  raise [x, y].inspect unless x == y
+end
+
+class Card
+  attr_reader :raw, :prefix, :letter, :number
+
+  def initialize(raw)
+    @raw = raw
+    @prefix = raw[0]
+    @letter = raw[1]
+    @number = raw[1..-1].size
+  end
+
+  def match?(y, z)
+    prefix_count = [self.prefix, y.prefix, z.prefix].uniq.count
+    if prefix_count == 1 || prefix_count == 3
+      letter_count = [self.letter, y.letter, z.letter].uniq.count
+      if letter_count == 1 || letter_count == 3
+        number_count = [self.number, y.number, z.number].uniq.count
+        return true if number_count == 1 || number_count == 3
+      end
+    end
+
+    false
+  end
+
+  def to_s
+    raw
+  end
+end
+
+class Solution
+  # time: O(n^3)
+  # space: O(n) ?
+  def run(row)
+    cards = row.split
+
+    for i in (0...cards.size)
+      x = Card.new(cards[i])
+      for p in (i+1...cards.size)
+        y = Card.new(cards[p])
+        for q in (p+1...cards.size)
+          z = Card.new(cards[q])
+          if x.match?(y, z)
+            return [x, y, z].map(&:to_s).join(' ')
+          end
+        end
+      end
+    end
+
+    ""
+  end
+
+  private
+
+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!"