puzzles/puzzles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Задача о двойных фамилиях\n",
    "\n",
    "<img src=\"img/1-0.png\" width=\"75%\" />\n",
    "\n",
    "В [первой задаче](https://proglib.io/p/zadacha-o-dvoynyh-familiyah-2020-01-11) нужно дополнить цитату:\n",
    "\n",
    "> «Если до брака супруги носили составную фамилию, то они сами решают, какие части их фамилий и в каком порядке будут использованы в их общей фамилии. Например, если браком сочетаются Мария Склодовская-Кюри и Никита Миклухо-Маклай, то вариантов у четы ...».\n",
    "\n",
    "Исходя из описания, сколько вариантов фамилии у этой гипотетической четы?\n",
    "\n",
    "**Учтите**. Фамилия может состоять не более, чем из двух.\n",
    "\n",
    "**Вариант со звёздочкой** 🌟. Если задача слишком лёгкая, то как бы вы реализовали решение для общего случая на любимом языке программирования? На входе функции – фамилии молодожёнов. Любые: и составные, и обычные. На выходе – все варианты фамилии новой семьи."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Задача о спрятанном решении\n",
    "\n",
    "<img src=\"img/2-0.png\" width=\"75%\" />\n",
    "\n",
    "Школьник перемножил два числа в столбик, а потом закрасил звездочками все цифры кроме одной девятки. Получилось как на картинке выше. Какие цифры стояли на месте звёздочек?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Задача об острове хамелеонов\n",
    "\n",
    "<img src=\"img/3-0.png\" width=\"75%\" />\n",
    "\n",
    "Восстанавливая популяцию хамелеонов, зоолог разместил на острове 10 коричневых, 14 серых и 15 черных. Когда два хамелеона разных цветов встречаются, оба меняют свой цвет на третий. Удастся ли всем хамелеонам стать одного цвета?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Задача о фамилии Тьюринга\n",
    "\n",
    "Cледующая задача посвящена [Алану Тьюрингу](https://ru.wikipedia.org/wiki/%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3,_%D0%90%D0%BB%D0%B0%D0%BD) – английскому математику и криптографу, который, помимо других замечательных достижений, сыграл ведущую роль в развитии теоретической информатики.\n",
    "\n",
    "<img src=\"img/4-0.png\" width=\"75%\" />\n",
    "\n",
    "Если мы сгенерируем список всех «слов», составленных из букв `G`, `I`, `N`, `R`, `T` и `U` в лексикографическом порядке, начиная с `GINRTU` и заканчивая `UTRNIG`, какую позицию в списке займёт `TURING`?\n",
    "\n",
    "**Альтернативный подход**🌟. Если вы не знаете, как подступиться к задаче аналитически, но можете решить программно, предложите в комментариях вариант решения общего случая с помощью кода. На входе – строка фамилии, на выходе – её номер в списке «слов», составленных из букв фамилии."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Задача об эпохе выдающихся учёных\n",
    "\n",
    "<img src=\"img/5-0.png\" width=\"75%\" />\n",
    "\n",
    "Редактор издания «История Всемирной науки» хочет выяснить, когда жило наибольшее количество выдающихся учёных. Выдающимися учёными редактор считает тех людей, что упомянуты в книге с датами их рождения и смерти. (Живые учёные в книгу не включены).\n",
    "\n",
    "Предложите редактору программируемый алгоритм решения задачи, если в качестве входных данных используется книжный указатель. Фамилии ученых в указателе отсортированы в алфавитном порядке, содержат годы рождения и смерти. Если человек А умер в том же году, в котором родился человек Б, считаем, что первое событие предшествовало второму.\n",
    "\n",
    "**Подсказка**. Обратите внимание на последнее предложение задания. Зачем дано такое уточнение?\n",
    "\n",
    "Решение описанной задачи рождает ряд возможностей для увлекательных проектов выходного дня. Найденный алгоритм можно использовать для широкого круга практических и учебных задач.\n",
    "\n",
    "**Алфавитно упорядоченные категории**. Алфавитные указатели собраны в Википедии в виде категорий. Есть и категория Учёные по алфавиту, притом с выбором отдельных подкатегорий. Например, можно искать только физиков. Почти на каждой странице, посвящённой персоне, указаны годы жизни. Их можно забрать программно, с помощью парсинга. То есть головоломку можно распространить на круг задач реального мира.\n",
    "\n",
    "**Идеи**. Не обязательно останавливаться на учёных. Вот несколько идей более специализированных проектов:\n",
    "\n",
    "* **Карта русской литературы**. Временна́я лента, по которой можно визуализировать когда жили разные [русские писатели](https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A0%D1%83%D1%81%D1%81%D0%BA%D0%B8%D0%B5_%D0%BF%D0%B8%D1%81%D0%B0%D1%82%D0%B5%D0%BB%D0%B8). Кто на кого мог влиять? Можно выбрать [конкретный век](https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A0%D1%83%D1%81%D1%81%D0%BA%D0%B8%D0%B5_%D0%BF%D0%B8%D1%81%D0%B0%D1%82%D0%B5%D0%BB%D0%B8_%D0%BF%D0%BE_%D0%B2%D0%B5%D0%BA%D0%B0%D0%BC). Такая идея была реализована в проекте [Russian Writers CSV and some graphs](https://boorstat.github.io/lit/russian/2017/03/25/russian-writers-csv.html). Есть от чего оттлокнуться, можно сделать по-своему.\n",
    "* **Любите футбол?** Можно использовать не годы жизни, а информацию о карьере [футболистов](https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A4%D1%83%D1%82%D0%B1%D0%BE%D0%BB%D0%B8%D1%81%D1%82%D1%8B), визуализировать переходы из клуба в клуб, участие в чемпионатах.\n",
    "* **Играете в шахматы?** Постройте ленту истории игры из годов первых упоминаний и названий каждого из именных видов [дебютов, гамбитов, защит](https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%94%D0%B5%D0%B1%D1%8E%D1%82%D1%8B_%D0%BF%D0%BE_%D0%B0%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82%D1%83). В этом случае даты – одиночные точки, но и они расскажут о развитии шахмат.\n",
    "* **Увлекаетесь фототехникой?** Соберите инфографику с годами выпуска и автоматически собранными изображениями [фотоаппаратов](https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A4%D0%BE%D1%82%D0%BE%D0%B0%D0%BF%D0%BF%D0%B0%D1%80%D0%B0%D1%82%D1%8B_%D0%BF%D0%BE_%D0%B0%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82%D1%83), покажите развитие отрасли.\n",
    "\n",
    "Схемы строения парсера и обработки данных будут близки. Но каждая область будет отличаться своей спецификой, например, выбором полей данных и отображением. Найденный в задаче алгоритм позволит находить времена, наиболее насыщенные событиями для выбранной категории."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ответы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Решения задачи о двойных фамилиях\n",
    "\n",
    "**Ответ**: 16.\n",
    "\n",
    "### Математическое решение\n",
    "\n",
    "Обозначим буквами: `A`, `B`, `C`, `D` «простые» фамилии внутри составных. Эти фамилии уже могут являться их общей фамилией.\n",
    "\n",
    "Остальные фамилии – размещения из четырех по двум. Число размещений равно\n",
    "\n",
    "`4! / (4−2)! = 4! / 2! = 4 ⋅ 3 = 12`.\n",
    "\n",
    "Действительно, эти 12 вариантов можно и перебрать:\n",
    "\n",
    "`AB AC AD BA BC BD CA CB CD DA DB DC`\n",
    "\n",
    "Таким образом, суммарное число фамилий равно шестнадцати.\n",
    "\n",
    "### Программное решение 🌟🐍\n",
    "\n",
    "Решим ещё и программно – на Python. Попрактикуемся в применении [библиотеки itertools](https://proglib.io/p/iteriruemsya-pravilno-20-priemov-ispolzovaniya-v-python-modulya-itertools-2020-01-03) (есть также версия этой статьи в [Jupyter](https://github.com/matyushkin/lessons/blob/master/itertools/common.ipynb) и [Colab](https://colab.research.google.com/github/matyushkin/lessons/blob/master/itertools/common.ipynb)):\n",
    "\n",
    "**Решение**. Обозначим «простые» фамилии внутри составных буквами: `A, B, C, D`.\n",
    "\n",
    "Эти фамилии уже могут являться их общей фамилией. Остальные фамилии – [размещения](https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0) из четырех по двум. Число размещений равно $4!/(4-2)! = 4!/2! = 4\\cdot3 = 12$. Действительно, эти 12 вариантов можно и перебрать: \n",
    "\n",
    "`\n",
    "AB AC AD\n",
    "BA BC BD\n",
    "CA CB CD\n",
    "DA DB DC\n",
    "`\n",
    "\n",
    "Таким образом, суммарное число фамилий равно 16.\n",
    "\n",
    "**Программное решение** 🌟🐍. Решим еще и программно – на Python. Мы как раз недавно рассматривали применение [библиотеки itertools](https://proglib.io/p/iteriruemsya-pravilno-20-priemov-ispolzovaniya-v-python-modulya-itertools-2020-01-03). Попрактикуемся в использовании:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Общее число фамилий равно 16. Вот их список без учёта пола:\n",
      "- Склодовская\n",
      "- Кюри\n",
      "- Миклухо\n",
      "- Маклай\n",
      "- Склодовская-Кюри\n",
      "- Склодовская-Миклухо\n",
      "- Склодовская-Маклай\n",
      "- Кюри-Склодовская\n",
      "- Кюри-Миклухо\n",
      "- Кюри-Маклай\n",
      "- Миклухо-Склодовская\n",
      "- Миклухо-Кюри\n",
      "- Миклухо-Маклай\n",
      "- Маклай-Склодовская\n",
      "- Маклай-Кюри\n",
      "- Маклай-Миклухо\n"
     ]
    }
   ],
   "source": [
    "from itertools import chain, permutations\n",
    "\n",
    "\n",
    "def find_all_surnames(surnames):\n",
    "    # разбиваем составные фамилии по дефису\n",
    "    surnames = [surname.split('-') for surname in surnames]\n",
    "    \n",
    "    # преобразуем в плоский список, получаем список \"обычных\" фамилий\n",
    "    surnames = list(chain.from_iterable(surnames))\n",
    "    \n",
    "    # остальные варианты соответствуют перестановкам обычных фамилий\n",
    "    perm_surnames = list(permutations(surnames, 2))\n",
    "    \n",
    "    # объединяем составные фамилии через дефис\n",
    "    perm_surnames = ['{}-{}'.format(i, j) for (i, j) in perm_surnames]\n",
    "    \n",
    "    # соединяем два списка\n",
    "    surnames.extend(perm_surnames)\n",
    "    \n",
    "    return surnames\n",
    "\n",
    "\n",
    "# проверим работу функции на практике\n",
    "surnames = find_all_surnames(['Склодовская-Кюри', 'Миклухо-Маклай'])\n",
    "\n",
    "print('Общее число фамилий равно {}. Вот их список без учёта пола:'.format(len(surnames)))\n",
    "for surname in surnames:\n",
    "    print('- '+surname)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Если вам понравилось решать задачу**. Это решение использует две эффективные функции встроенной библиотеки itertools. Чтобы попрактиковаться в алгоритмах, решите ту же задачу, не задействовав библиотек. Сравните [время](https://proglib.io/p/nazad-v-budushchee-prakticheskoe-rukovodstvo-po-puteshestviyu-vo-vremeni-s-python-2019-12-01) выполнения кода."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Решение задачи о спрятанном решении\n",
    "\n",
    "Эта говоломка – арифметический ребус. При решении задач такого типа требуется внимательность к очевидным арифметическим действиям и умение вести нить лоrических рассуждений.\n",
    "\n",
    "<img src=\"img/2-1.png\" width=\"75%\" />\n",
    "\n",
    "Множимое примера – число, большее 90. Действительно, если бы множимое было меньше 90, то, умножая ero на двузначное число (множитель), меньшее 100, получили бы число, меньшее 9000.\n",
    "\n",
    "<img src=\"img/2-2.png\" width=\"75%\" />\n",
    "\n",
    "Но если множимое больше 90, то вторая цифра множителя 1 (третья строка – двузначное число).\n",
    "\n",
    "<img src=\"img/2-3.png\" width=\"75%\" />\n",
    "\n",
    "Первая цифра можителя 9. Если допустить, что она меньше 9, например, 8, то, умножая 81 на двузначное число (множимое), меньшее 100, получим в произведении число, меньшее 8100.\n",
    "\n",
    "<img src=\"img/2-4.png\" width=\"75%\" />\n",
    "\n",
    "Итак, множитель примера равен 91. В качестве множимоrо возьмем число 98: 98 х 91 = 8918, не подходит. Следовательно, множимое примера двузначное число, большее 98, т. е. 99.\n",
    "\n",
    "<img src=\"img/2-5.png\" width=\"75%\" />\n",
    "\n",
    "Окончательный результат 99 х 91 = 9009.\n",
    "\n",
    "<img src=\"img/2-6.png\" width=\"75%\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Решение задачи об острове хамелеонов \n",
    "\n",
    "После каждого обмена между двумя хамелеонами, количество хамелеонов соответствующих цветов изменяется следующим образом: `-1`, `-1`, `+2`. То есть остатки при делении кол-ва хамелеонов на 3 меняются одинаково. Исходный набор `{10, 14, 15}` соответствует набору остатков `{1, 2, 0}`, а желаемый финальный набор `{0, 0, 39}` (в любом порядке) соответствует набору остатков `{0, 0, 0}`. Из набора разных остатков мы не можем получить набор одинаковых, так что вывод: нет, нельзя добиться единого цвета для всех."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Решение задачи о фамилии Тьюринга\n",
    "\n",
    "**Ответ**: 598.\n",
    "\n",
    "**Решение**. Фактически это комбинаторная задача на [перестановки](https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0). Общее количество слов, составленное из шести букв, равно `6! = 6·5·4·3·2·1 = 720`. Удобнее рассматривать те «слова», которые следуют после слова `TURING`. Потому что их меньше.\n",
    "\n",
    "Такие слова имеют сначала вид `TURN∗∗`, потом сменяются словами вида `U∗∗∗∗∗`. Звёздочка обозначает одну из шести букв, которых еще нет в слове. Для первой комбинации букв остается вариантов: `2!`, для второй – `5!`. Таким образом, общее количество «слов», следующих за `TURING` равно `5! + 2! = 120 + 2 = 122`.\n",
    "\n",
    "Номер фамилии это число общих слов минус номер следующих за ней. Таким образом, если нумерация начинается с единицы, номер фамилии равен `720 – 122 = 598`.\n",
    "\n",
    "**Программное решение** 🌟🐍. Если вы не смогли решить задачу аналитически, можно было решить задачу программно. Ниже представлено простое решение на Python с использованием встроенной библиотеки [itertools](https://proglib.io/p/iteriruemsya-pravilno-20-priemov-ispolzovaniya-v-python-modulya-itertools-2020-01-03):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Введите фамилию: TURING\n",
      "Номер фамилии в списке «слов», составленном из букв фамилии: 598.\n"
     ]
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "\n",
    "def find_surname_position(surname: str):\n",
    "    surname = surname.upper()  # если фамилия написана не заглавными буквами\n",
    "    letters = list(surname)  # список букв, из которых состоит фамилия\n",
    "    letters_vars = permutations(sorted(letters), len(surname))  # перестановки\n",
    "    words_vars = [''.join(item) for item in letters_vars]  # \"слова\" из букв\n",
    "    position = words_vars.index(surname) + 1  # нумерация начинается с единицы\n",
    "    return position\n",
    "\n",
    "input_surname = input('Введите фамилию: ')\n",
    "\n",
    "req = 'Номер фамилии в списке «слов», составленном из букв фамилии: {}.'\n",
    "print(req.format(find_surname_position(input_surname)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Решение задачи о Времени великих учёных\n",
    "\n",
    "В общем виде проблема может быть сформулирована следующим образом. Задано $n$ интервалов ($b_1$, $d_1$), ... , ($b_n$, $d_n$). В нашем случае $b_i$, $d_i$ – даты рождения и смерти $i$-го человека в указателе ($1$ ≤ $i$ ≤ $n$). Нужно найти интервал, который является пересечением наибольшего количества данных интервалов.\n",
    "\n",
    "Последнее условие указывает на то, что все интервалы открыты, то есть не включают их конечные точки. Если $d_i = b_j$, закрывающая скобка $i$-го интервала предшествует открывающей скобке $j$-го интервала. Если несколько интервалов имеют одну и ту же открывающую скобку, она должна учитываться для каждого из этих интервалов, то же самое верно для совпадающих закрывающих скобок.\n",
    "\n",
    "Полезно визуализировать интервалы, изображённые на реальной временно́й шкале, как это сделано ниже на рисунке. Последовательность круглых скобок содержит ключ к эффективному решению проблемы. При сканировании последовательности слева направо число персон увеличивается на 1 на каждой открывающей скобке и уменьшается на 1 на закрывающей.\n",
    "\n",
    "<img src=\"img/5-1.png\" width=\"75%\" />\n",
    "\n",
    "Таким образом, искомый интервал лежит между открывающей скобкой с максимальным значением счётчика и следующей за ней закрывающей скобкой."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}