[codeFights] FindProfession

Consider a special family of Engineers and Doctors. This family has the following rules:

• Everybody has two children.
• The first child of an Engineer is an Engineer and the second child is a Doctor.
• The first child of a Doctor is a Doctor and the second child is an Engineer.
• All generations of Doctors and Engineers start with an Engineer.

We can represent the situation using this diagram:

                E
           /         \
          E           D
        /   \        /  \
       E     D      D    E
      / \   / \    / \   / \
     E   D D   E  D   E E   D

Given the level and position of a person in the ancestor tree above, find the profession of the person.
Note: in this tree first child is considered as left child, second - as right.

Example

For level = 3 and pos = 3, the output should be
findProfession(level, pos) = "Doctor".

Input/Output

• [time limit] 4000ms (py)

• [input] integer level
  The level of a person in the ancestor tree, 1-based.
  Guaranteed constraints:
  1 ≤ level ≤ 30.

My first thought is to use BFS. Why? Because when you know the last level, the next level is known. However, given how large the input might be ($2^{30}$) , it is gonna blow up the memory. My next thought is to find the pattern: it should be doable, but it turns out to be overwhelming. 

But another way, the most important way to think about a tree problem, is recursion. There is a nice relationship between last level and current level's professions: last level 1, 2, 3, 4, ... will be copied to the current level position: 1, 3, 5, 7, ... . As for 2, 4, 6, 8 ... positions in my current level, it is just the opposite. Hence the code:

def findProfession(level, pos):
    if level == 1:
        return 'Engineer'
    if level == 2:
        if pos == 1:
            return 'Engineer'
        else:
            return 'Doctor'
    if pos % 2 == 1:
        return findProfession(level - 1, (pos+1)/2)
    else:
        if findProfession(level - 1, pos/2) == 'Doctor':
            return 'Engineer'
        else:
            return 'Doctor'