celeb.rb

class Celebrity
  attr_reader :matrix

  def initialize(rows)
    @matrix = rows
  end

  def knows?(from, to)
    @matrix[from][to] == 1
  end

  def find
    _find (0...@matrix.size).to_a
  end

  private

  def _find(candidates)
    if candidates.size <= 1
      candidates.first
    else
      recognize(*candidates)
    end
  end

  def recognize(first, second, *rest)
    no_celeb, candidate = (knows? first, second) ? [first, second] : [second, first]
    next_candidates = [candidate] + rest

    possible_one = _find(next_candidates)
    return nil unless possible_one

    if knows?(no_celeb, possible_one) && !knows?(possible_one, no_celeb)
      possible_one
    else
      nil
    end
  end
end

@sample1 = Celebrity.new [
  #0  1  2  3  4
  [1, 0, 0, 1, 0],  # 0
  [0, 1, 0, 1, 0],  # 1
  [0, 0, 1, 1, 0],  # 2
  [0, 0, 0, 1, 0],  # 3
  [0, 0, 0, 1, 1],  # 4
]

@sample2 = Celebrity.new [
  #0  1  2  3  4
  [1, 1, 1, 1, 1],  # 0
  [0, 1, 1, 1, 0],  # 1
  [0, 0, 1, 1, 1],  # 2
  [0, 0, 0, 1, 0],  # 3
  [0, 0, 0, 1, 1],  # 4
]

@sample3 = Celebrity.new [
  #0  1  2  3  4
  [1, 1, 1, 1, 1],  # 0
  [1, 1, 1, 1, 1],  # 1
  [1, 1, 1, 1, 1],  # 2
  [0, 0, 0, 1, 0],  # 3
  [1, 1, 1, 1, 1],  # 4
]

@sample4 = Celebrity.new [
  #0  1  2  3  4
  [1, 0, 0, 1, 0],  # 0
  [0, 1, 0, 1, 0],  # 1
  [0, 0, 1, 1, 0],  # 2
  [0, 0, 0, 1, 0],  # 3
  [0, 0, 0, 0, 1],  # 4
]

@sample5 = Celebrity.new [
  #0  1  2  3  4
  [1, 0, 1, 1, 0],  # 0
  [0, 1, 1, 1, 0],  # 1
  [0, 0, 1, 1, 0],  # 2
  [0, 0, 1, 1, 0],  # 3
  [0, 0, 1, 1, 1],  # 4
]