Build a small machine

1 files changed, 158 insertions, 4 deletions

diff --git a/misc/subsequence/main.rb b/misc/subsequence/main.rb
index 8d56457..d4c3995 100644
--- a/misc/subsequence/main.rb
+++ b/misc/subsequence/main.rb
@@ -1,5 +1,9 @@
 def assert_equal(x, y)
-  raise [x, y].inspect unless x == y
+  if x == y
+    puts 'PASS!'
+  else
+    puts "FAIL!: expected `#{x.inspect}` got `#{y.inspect}`"
+  end
 end
 
 =begin
@@ -41,6 +45,158 @@ class Solution
 
     index
   end
+
+  class Input
+    attr_reader :position
+
+    def initialize(string)
+      @string = string
+      @position = 0
+    end
+
+    def seek(position)
+      @position = position
+    end
+
+    def previous
+      @string.chars[position - 1]
+    end
+
+    def current
+      @string.chars[position]
+    end
+
+    def peek
+      @string.chars[position + 1]
+    end
+
+    def advance(n)
+      @position += n
+    end
+
+    def eos?
+      @position == @string.size
+    end
+  end
+
+  class Atom
+    attr_accessor :next
+
+    def parse(string)
+      match?(Input.new(string))
+    end
+
+    def match_next?(input)
+      self.next.match?(input)
+    end
+
+
+    def to_s
+      self.class.to_s
+    end
+
+    def inspect
+      "#{self}->#{self.next&.inspect}"
+    end
+  end
+
+  class Start < Atom
+    def match?(input)
+      result = nil
+
+      until input.eos?
+        result = input.position
+        break if match_next?(input)
+
+        input.seek(result + 1)
+        result = nil
+      end
+
+      result
+    end
+
+    def to_s
+      "start"
+    end
+  end
+
+  class Wildcard < Atom
+    def initialize(lookahead)
+      @lookahead = lookahead
+    end
+
+    def match?(input)
+      return true if input.eos?
+
+      if input.peek == @lookahead
+        input.advance(1)
+        match_next?(input)
+      else
+        input.advance(1)
+        match?(input)
+      end
+    end
+
+    def to_s
+      "*"
+    end
+  end
+
+  class Final < Atom
+    def match?(*)
+      true
+    end
+
+    def to_s
+      "final"
+    end
+  end
+
+  class Literal < Atom
+    attr_reader :value
+
+    def initialize(value)
+      @value = value
+    end
+
+    def match?(input)
+      if value == input.current
+        input.advance(1)
+        match_next?(input)
+      else
+        false
+      end
+    end
+
+    def to_s
+      @value
+    end
+  end
+
+  def self.build_machine(pattern)
+    initial = Start.new
+    machine = initial
+
+    for i in 0...pattern.size
+      atom = case pattern[i]
+      when '*'
+        Wildcard.new(pattern[i + 1])
+      else
+        Literal.new(pattern[i])
+      end
+
+      machine.next = atom
+      machine = atom
+    end
+    machine.next = Final.new
+
+    initial
+  end
+
+  def self.run(sequence, pattern)
+    machine = build_machine(pattern)
+    machine.parse(sequence)
+  end
 end
 
 assert_equal 0, Solution.run('abcdef', 'a*d*f')
@@ -49,8 +205,6 @@ assert_equal 1, Solution.run('abcd', 'b*d')
 assert_equal 2, Solution.run('abacd', 'ac*')
 assert_equal 0, Solution.run('abcdefg', 'a*d*f')
 assert_equal 3, Solution.run('xyzabcdef', 'a*d*f')
-assert_equal nil, Solution.run('abcdefxyz', 'a*d*f')
+assert_equal 0, Solution.run('abcdefxyz', 'a*d*f')
 assert_equal 0, Solution.run('mo is the best', 'm* is the ****')
 assert_equal 7, Solution.run('Phone: +1(403)-555-5555', '+*(***)-***-****')
-
-puts "YAY!"