messages.rb

def validate_messages(message)
  message.split(' ').each do |msg|
    if valid? msg
      puts msg + " VALID"
    else
      puts msg + " INVALID"
    end
  end
end

def valid?(string)
  if string.length == 1 && string.match(/[a-j]/)
    return true
  end

  remaining_string = string[1..-1]
  if string[0] == "Z" && valid?(remaining_string)
    true
  elsif %w(M K P Q).include?(string[0])
    string_to_pairs(remaining_string).any? do |pair|
      valid?(pair[0]) && valid?(pair[1])
    end
  else
    false
  end
end

# returns array of substrings of a string
def string_to_pairs(string)
  (0..string.length-2).inject([]) do |mem, i|
    first, second = string[0..i], string[i+1..-1]
    mem << [first, second]
  end
end

validate_messages 'ZZZa'   # => ZZZa VALID