Задача с собеседования + идеи проекта: «Время великих учёных»

В новой задаче ответом является алгоритм, а не число. Есть что обсудить. Если вы найдёте алгоритм, то сможете использовать его в предложенных проектах выходного дня.

Эта задача – пятый эпизод нашего сериала головоломок. После описания задачи идёт ответ на вчерашнюю головоломку о фамилии Тьюринга.

Задача об эпохе выдающихся учёных

Собеседование. Редактор издания «История Всемирной науки» нанимает программиста. Тестовое задание: выяснить интервал лет всемирной истории, когда жило наибольшее количество выдающихся учёных. Выдающимися учёными редактор считает тех, кто упомянут в книге с датами их рождения и смерти. Ныне живущие учёные в книгу не включены.

Задание. Предложите редактору программируемый алгоритм решения задачи, если в качестве входных данных используется книжный указатель. Фамилии учёных в указателе отсортированы в алфавитном порядке, содержат годы рождения и смерти. Если человек А умер в том же году, в котором родился человек Б, считайте, что первое событие предшествовало второму.

Идеи и ответы можно обсудить в комментариях. Первого человека, указавшего правильное решение, мы выделим при публикации следующей задачи (см. примеры ниже).

Когда будет ответ? Наши задачи не из простых. Чтобы все успевали решить задачу, и читатели не уставали от формата, мы решили делать головоломки не так часто. Задачи будут выходить в дни недели, начинающиеся на «c»: по средам и субботам. Ответ на задачу и новую головоломку опубликуем в субботу, в 14:00 (она уже опубликована).

Идеи проекта выходного дня

Решение описанной задачи рождает ряд возможностей для увлекательных проектов выходного дня. Найденный алгоритм можно использовать для широкого круга практических и учебных задач.

Алфавитно упорядоченные категории. Алфавитные указатели собраны в Википедии в виде категорий. Есть и категория Учёные по алфавиту, притом с выбором отдельных подкатегорий. Например, можно искать только физиков. Почти на каждой странице, посвящённой персоне, указаны годы жизни. Их можно забрать программно, с помощью парсинга. То есть головоломку можно распространить на круг задач реального мира.

Идеи. Не обязательно останавливаться на учёных. Вот несколько идей более специализированных проектов:

• Карта русской литературы. Временна́я лента, по которой можно визуализировать когда жили разные русские писатели. Кто на кого мог влиять? Можно выбрать конкретный век. Такая идея была реализована в проекте Russian Writers CSV and some graphs (англ.). Есть от чего оттлокнуться, можно сделать по-своему.
• Любите футбол? Можно использовать не годы жизни, а информацию о карьере футболистов, визуализировать переходы из клуба в клуб, участие в чемпионатах.
• Играете в шахматы? Постройте ленту истории игры из годов первых упоминаний и названий каждого из именных видов дебютов, гамбитов, защит. В этом случае даты – одиночные точки, но и они расскажут о развитии шахмат.
• Увлекаетесь фототехникой? Соберите инфографику с годами выпуска и автоматически собранными изображениями фотоаппаратов, покажите развитие отрасли.

Схемы строения парсера и обработки данных будут близки. Но каждая область будет отличаться своей спецификой, например, выбором полей данных и отображением. Найденный в задаче алгоритм позволит находить времена, наиболее насыщенные событиями для выбранной категории.

Это лишь некоторые наводящие мысли. Ваши идеи мы будем рады увидеть в комментариях. Дерзайте!

Решение задачи о фамилии Тьюринга

Ответ: 598.

Решение. Фактически это комбинаторная задача на перестановки. Общее количество слов, составленное из шести букв, равно 6! = 6·5·4·3·2·1 = 720. Удобнее рассматривать те «слова», которые следуют после слова TURING. Потому что их меньше.

Такие слова имеют сначала вид TURN∗∗, потом сменяются словами вида U∗∗∗∗∗. Звёздочка обозначает одну из шести букв, которых ещё нет в слове. Для первой комбинации букв остаётся вариантов: 2!, для второй – 5!. То есть общее количество «слов», следующих за TURING равно 5! + 2! = 120 + 2 = 122.

Номер фамилии это число общих слов минус номер следующих за ней. Таким образом, если нумерация начинается с единицы, номер фамилии равен 720 – 122 = 598.

Программное решение 🌟🐍. Если вы не смогли решить задачу аналитически, можно было решить задачу программно. Ниже представлено простое решение на Python с использованием встроенной библиотеки itertools:

from itertools import permutations


def find_surname_position(surname: str):
    surname = surname.upper()  # если фамилия написана не заглавными буквами
    letters = list(surname)  # список букв, из которых состоит фамилия
    letters_vars = permutations(sorted(letters), len(surname))  # перестановки
    words_vars = [''.join(item) for item in letters_vars]  # "слова" из букв
    position = words_vars.index(surname) + 1  # нумерация начинается с единицы
    return position

input_surname = input('Введите фамилию: ')

req = 'Номер фамилии в списке «слов», составленном из букв фамилии: {}.'
print(req.format(find_surname_position(input_surname)))

Введите фамилию: TURING
Номер фамилии в списке «слов», составленном из букв фамилии: 598.

Первыми решения головоломки дали пользователи NeizeR и rmg7. Поздравляем! Оба ответа правильные. Решение rmg7 в том же ключе, что и описанное нами, а ответ NeizeR наглядно показывает, почему подсчёт от начала списка оказывается дольше. Но и он приводит к правильному положению в списке.

Ниже мы процитировали ответы участников.

Перед первым словом на букву T будет 4x5! слов, поскольку есть 4 буквы перед T(G, I, N, R) и для каждой из них 5! способов переставить между собой 5 оставшихся букв. Дальше мы считаем сколько слов можна сделать из буквы T + букв которые идут перед U в списке оставшихся букв, то есть TG, TI, TN и TR(TT не включаем, потому что второй раз не можем ее использовать); количество таких перестановок будет равно 4x4! исходя из уже описанного алгоритма. Аналогично делаем для остальных комбинаций букв, которые будут находится перед словом TURING( TUG, TUI, TUN, TURG, TURIG). Сделав для этих комбинаций аналогические рассчеты, мы получим число 4x5! + 4x4! + 3x3! + 1x2! + 1x1! = 597. То есть перед словом TURING будет 597 слов, и, соотвественно, само слово TURING будет иметь номер 598.

быстрее будет решать в противоположном направлении Общее количество комбинаций 6!=720, 6!-5!(Uxxxxx)-0(TUxxxx)-0(TURxxx)-2!(TURNxx)-0(TURINx)=6!-5!-2!=720-120-2=598