Обход графа в ширину в задаче

Question

Есть такое интересное задание. Надумал делать через обход графа в ширину. Но из-за ключей-значений словаря совсем запутался. Компилятор вечно жалуется. Помогите с решением или направьте в нужную сторону, пожалуйста

Мой код:

import collections
def get_child(graph, k, N):
   root = 0
   visited, queue = set(), collections.deque([root])
   visited.add(root)
   i = k + N

   while i:
     top = queue.popleft()
     for node in graph[top]:
        if node not in visited:
            visited.add(node)
            queue.append(node)
            child = node
     i -= 1
  return child

graph = {
  "M" : ["M", "F"],
  "M" : ["M", "F"],
  "F" : ["F", "M"]
}

child_number = input("Введите номер ребенка: ")
generation = input("Введите номер поколения: ")

try :
   child_number = int(child_number)
   generation = int(generation)
except :
   print("Ошибка, пожалуйста, введите числовые данные")
   quit()

if (1 <= child_number <= min(10**15, 2**(generation - 1))) and (1 <= generation <= 10000):
   result = get_child(graph, child_number, generation)                   
   print(result)
else :
   print("Пожалуйста, введите корректный номер ребенка или номер поколения")

Answer 1

Примерный алгоритм на C#, для первых 4 рядов по крайней мере работает.

char getGender(int N, long K)
{
    if (N == 1) return 'M';
    char parentGender = getGender(N - 1, (K + 1) / 2);
    bool isFirstChild = K % 2 != 0;
    var otherGender = parentGender == 'M' ? 'F' : 'M';
    return isFirstChild ? parentGender : otherGender;
}

Проверка

Console.WriteLine(getGender(1, 1));

Console.WriteLine();

Console.WriteLine(getGender(2, 1));
Console.WriteLine(getGender(2, 2));

Console.WriteLine();

Console.WriteLine(getGender(3, 1));
Console.WriteLine(getGender(3, 2));
Console.WriteLine(getGender(3, 3));
Console.WriteLine(getGender(3, 4));

Console.WriteLine();

Console.WriteLine(getGender(4, 1));
Console.WriteLine(getGender(4, 2));
Console.WriteLine(getGender(4, 3));
Console.WriteLine(getGender(4, 4));
Console.WriteLine(getGender(4, 5));
Console.WriteLine(getGender(4, 6));
Console.WriteLine(getGender(4, 7));
Console.WriteLine(getGender(4, 8));

Вывод

M

M
F

M
F
F
M

M
F
F
M
F
M
M
F

Answer 2

Где-то я уже это видел:

k = input("Введите номер ребенка: ")
s = 'F' if bin(int(k)-1).count('1') & 1 else 'M'
print(s)

БЛОГ НА HUSL

Обход графа в ширину в задаче

Ответы (2 шт):