1<<-DOC
  2Consider a special family of Engineers and Doctors. This family has the following rules:
  3
  4Everybody has two children.
  5The first child of an Engineer is an Engineer and the second child is a Doctor.
  6The first child of a Doctor is a Doctor and the second child is an Engineer.
  7All generations of Doctors and Engineers start with an Engineer.
  8We can represent the situation using this diagram:
  9
 10                E
 11           /         \
 12          E           D
 13        /   \        /  \
 14       E     D      D    E
 15      / \   / \    / \   / \
 16     E   D D   E  D   E E   D
 17Given the level and position of a person in the ancestor tree above, find the profession of the person.
 18Note: in this tree first child is considered as left child, second - as right.
 19
 20Example
 21
 22For level = 3 and pos = 3, the output should be
 23findProfession(level, pos) = "Doctor".
 24
 25Input/Output
 26
 27[time limit] 4000ms (rb)
 28[input] integer level
 29
 30The level of a person in the ancestor tree, 1-based.
 31
 32Guaranteed constraints:
 331 ≤ level ≤ 30.
 34
 35[input] integer pos
 36
 37The position of a person in the given level of ancestor tree, 1-based, counting from left to right.
 38
 39Guaranteed constraints:
 401 ≤ pos ≤ 2(level - 1).
 41
 42[output] string
 43
 44Return Engineer or Doctor.
 45http://www.geeksforgeeks.org/find-profession-in-a-hypothetical-special-situation/
 46DOC
 47
 48describe "#find_profession" do
 49  # [e]
 50  # [e,d]
 51  # [e,d,d,e]
 52  # [e,d,d,e,d,e,e,d]
 53  # [e,d,d,e,d,e,e,d,d,e,e,d,e,d,d,e]
 54  # [e,d,d,e,d,e,e,d,d,e,e,d,e,d,d,e,d,e,e,d,e,d,d,e,e,d,d,e,d,e,e,d]
 55  def find_profession(level, position)
 56    return :Engineer if level == 1
 57
 58    parent_position = position.odd? ? (position + 1) / 2 : position / 2
 59    parent = find_profession(level - 1, parent_position)
 60    position.odd? ? parent : parent == :Doctor ? :Engineer : :Doctor
 61  end
 62
 63  def bits_for(n)
 64    #count = 0
 65    #while n > 0
 66      #n &= n - 1
 67      #count += 1
 68    #end
 69    #count
 70    n.to_s(2).count('1')
 71  end
 72
 73  # [1]
 74  # [1,0]
 75  # [1,0,0,1]
 76  # [1,0,0,1,0,1,1,0]
 77  # [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]
 78  # [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]
 79  def find_profession(level, position)
 80    bits_for(position - 1).odd? ? :Doctor : :Engineer
 81  end
 82
 83  def find_profession(level, position)
 84    (position - 1).to_s(2).count('1').odd? ? :Doctor : :Engineer
 85  end
 86
 87  [
 88    { level: 3, pos: 3, x: "Doctor" },
 89    { level: 4, pos: 2, x: "Doctor" },
 90    { level: 1, pos: 1, x: "Engineer" },
 91    { level: 8, pos: 100, x: "Engineer" },
 92    { level: 10, pos: 470, x: "Engineer" },
 93    { level: 17, pos: 5921, x: "Doctor" },
 94    { level: 20, pos: 171971, x: "Engineer" },
 95    { level: 25, pos: 16777216, x: "Engineer" },
 96    { level: 30, pos: 163126329, x: "Doctor" },
 97  ].each do |x|
 98    it do
 99      expect(find_profession(x[:level], x[:pos])).to eql(x[:x].to_sym)
100    end
101  end
102end