def assert_equal(x, y)
  if x == y
    puts 'PASS!'
  else
    puts "FAIL!: expected `#{x.inspect}` got `#{y.inspect}`"
  end
end

=begin
 x
|a|b|c|d|e|f|

 y
|a|*|d|*|f|
=end

class Solution
  def self.run(sequence, pattern)
    p = 0
    index = nil

    0.upto(sequence.length - 1) do |n|
      x = sequence[n]
      y = pattern[p]

      if y == '*'
        index = n if p.zero?
        l = pattern[p + 1]

        p += 2 if l == x
      elsif x == y
        index = n if p.zero?

        p += 1
      else
        index = nil unless p >= pattern.size
        p = 0
      end
    end

    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

  def self.state_for(token)
    return :final if token.nil?

    case token
    when '*'
      :wildcard
    else
      :literal
    end
  end

  def self.debug(state, sequence_pos, pattern_pos, sequence, pattern)
    return unless ENV['DEBUG']

    puts [state].inspect
    puts "  " + (" " * sequence_pos) + "v"
    puts "  " + sequence
    puts "  " + (" " * pattern_pos) + "v"
    puts "  " + pattern
  end

  # start, literal, wildcard, final
  def self.run(sequence, pattern)
    state = :start
    sequence_pos = 0
    pattern_pos = 0
    result = nil

    while pattern_pos < pattern.size && sequence_pos < sequence.size
      debug(state, sequence_pos, pattern_pos, sequence, pattern)

      case state
      when :start
        pattern_pos = 0
        result = sequence_pos
        state = state_for(pattern[pattern_pos])
      when :literal
        if sequence[sequence_pos] == pattern[pattern_pos]
          pattern_pos += 1
          state = state_for(pattern[pattern_pos])
        else
          state = :start
          result = nil
        end

        sequence_pos += 1
      when :wildcard
        lookahead = pattern[pattern_pos + 1]
        if sequence[sequence_pos] == lookahead
          state = state_for(lookahead)
          pattern_pos += 1
        else
          sequence_pos += 1
        end
      when :final
        break
      end
    end

    result
  end

  def self.run(sequence, pattern, index = 0)
    puts [sequence, pattern, index].inspect if ENV['DEBUG']
    return index if pattern.nil? || pattern.empty?
    return index if sequence.nil? || sequence.empty?

    case (atom = pattern[0])
    when '*'
      if sequence[1] == pattern[1]
        run(sequence[1..-1], pattern[1..-1], index)
      else
        run(sequence[1..-1], pattern, index)
      end
    else
      if sequence[0] == atom
        run(sequence[1..-1], pattern[1..-1], index)
      else
        run(sequence[1..-1], pattern, index + 1)
      end
    end
  end

  def self.run(sequence, pattern, index = 0)
    return index if pattern.empty?
    return index if sequence.empty?

    atom = pattern[0]
    if atom != '*'
      if sequence[0] == atom
        run(sequence[1..-1], pattern[1..-1], index)
      else
        run(sequence[1..-1], pattern, index + 1)
      end
    else
      if sequence[1] == pattern[1]
        run(sequence[1..-1], pattern[1..-1], index)
      else
        run(sequence[1..-1], pattern, index)
      end
    end
  end
end
=begin
 x
|a|b|c|d|e|f|

 y
|a|*|d|*|f|

=end

assert_equal 0, Solution.run('abcdef', 'a*d*f')
assert_equal 0, Solution.run('abcdefg', '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 1, Solution.run('abcd', 'b*d')
assert_equal 1, Solution.run('abcddef', 'bc*de')
assert_equal 2, Solution.run('abacd', 'ac*')
assert_equal 3, Solution.run('xyzabcdef', 'a*d*f')
assert_equal 7, Solution.run('Phone: +1(403)-555-5555', '+*(***)-***-****')