Skip to content

Instantly share code, notes, and snippets.

@cesare
Created February 3, 2016 03:32
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save cesare/0afa3fe99441f79bb19c to your computer and use it in GitHub Desktop.
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
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment