[ЗВУК] Итак, напишем достаточно сложную задачу в чисто функциональном стиле. Задача будет звучать так. У нас есть n людей, они разъезжаются с какого-нибудь праздника, и для каждого известно количество километров, сколько километров ему нужно проехать до дома. А также у нас есть n такси, причем стоимость поездки за один километр в разных такси разная. Требуется сопоставить каждому человеку определенную машину такси, так, чтобы суммарное количество потраченных денег было минимально. Решение задачи опирается на идею, что тот, кому далеко ехать, должен ехать на дешевом такси, а тот, кому близко — на дорогом, потому что кто-то же должен ехать на дорогом. С помощью такой идеи можно минимизировать количество денег. Так давайте упорядочим людей по возрастанию, например, расстояния, такси — по убыванию, и сопоставим их один к одному. Вывести нужно в этой задаче данные в таком порядке. Мы для каждого человека, в том порядке, как они перечислялись, должны вывести номер такси, в том порядке, как они перечислялись. Давайте начнем писать, пока что используя переменные, но с таким ограничением: никаких if, никаких циклов, ничего. То есть только одна длинная линейная программа пока что с сохранением людей. Итак, пусть у нас в первой строке задан список людей, в нем гарантировано n чисел, и потом список такси следующий. Итак, давайте покороче. Значит, наши пассажиры... Мы просто пользуемся стандартным способом чтения списка чисел. Хорошо. Дальше мы хотим упорядочить их по возрастанию, мы знаем, как это делать с помощью функции sorted, но сопоставляя номера, то есть мы хотим запомнить, как пассажиры располагались у нас во входных данных. Мы знаем, что у нас для этого существует enumerate, который как раз позволяет решить эту задачу. Значит, давайте попробуем это все написать и сразу проверим. Если где-то ошиблись, сразу исправим ошибку, и все будет хорошо. Итак, что мы хотим сделать? Мы сейчас несколько шажков сделаем уже. Мы хотим отсортить последовательность, состоящую из чего? Из занумерованных людей. Для этого пользуемся enumerate. Кто у нас сортируется? Пассажиры. Давайте, начиная... Да пусть будет с нуля. Если что, потом исправим. Итак, мы сортируем пассажиров с ключом. С каким ключом? Что у нас возвращает enumerate? enumerate возвращает список кортежей. На нулевом месте — номер, на первом месте — значение из нашего списка. Мы хотим брать это самое значение из нашего списка. Добывать мы его будем с помощью lambda-функции. Вот она, наша lamba-функция получает x — это кортежик из двух элементов, и возвращает x[1] — собственно, расстояние, которое нужно проехать человеку. Давайте напечатаем, что у нас там получилось. Значит, пока что мы ждем одну строку, наша программка хочет считать, просто с числами, с расстояниями, которые нужно проехать людям. Пусть первому человеку нужно проехать два километра, второму — три километра, а третьему — всего один километр. Итак, вот они упорядочены по первому элементу кортежа, первому при нумерации с нуля. Значит, второй человек едет один километр, нулевой человек едет два километра, и первый человек едет три километра. Похоже на правду. Все, теперь эта сортировка работает, мы проверили, отладочный вывод убираем, переходим к такси. С такси все очень похоже. Мы людей упорядочили по возрастанию расстояния, такси упорядочим по убыванию. Зачем? Чтобы сопоставлять их один к одному. Близкий человек на дорогом такси, дорогой человек — на дешевом такси, дальний человек. Итак, [ЗВУК] Исправляем наши опечаточки, нумеруем людей. Что нам нужно еще сделать? Развернуть эту последовательность. [ЗВУК] Будем надеяться, что все работает, потому что мы только что проверяли людей, изменения минимальны, и, допустим, так сойдет. Итак, что нужно сделать дальше? Дальше нужно сопоставить людей и такси. Что у нас есть для сопоставления? Для сопоставления у нас есть замечательная функция zip. Как... Архивы так называются. На самом деле zip берет две последовательности, поочередно достает из них элементы и объединяет их в кортеж. На самом деле последовательностей может быть больше, чем две, в общем-то, может сколько угодно, тогда кортежи будут получаться длиннее. Там есть разные интересные случаи, когда, например, последовательности разной длины или еще что-то, но у нас пока что все просто, и мы имеем две последовательности одинаковой длины. Давайте мы наших пассажиров с такси объединим и посмотрим, как это все выглядит. Отсортированных, естественно. Отсортированные последовательности уже состоят из кортежей, то есть у нас есть кортежи из двух элементов, и они объединяются еще в кортеж. Вот что-то такое мы надеемся увидеть. Давайте я совсем маленькие входные данные введу, пусть у нас всего два человека и два такси будет. Конечно, по-хорошему надо было их в файл положить и читать оттуда, но ладно, уже отладим так. Итак, два человека, первому два километра, второму один километр, и такси, например, по 10 рублей и по 20 рублей. Значит, смотрите, на reversed опять все... Вместо reverse написал reversed — ничего страшного, исправляем. Хорошо, что входные данные были маленькие. Итак, вот звездочка нам понадобится. Как вы видите, я ленился и очень напрасно это делал. Наконец, он вывел нам с третьей попытки. Что здесь есть что? Давайте пытаться теперь в этом разобраться, что оно вывело. Оно вывело два кортежа, каждый из которых, в свою очередь, состоит из двух кортежей. Первый из них описывает человека. Человек имеет номер ноль и хочет проехать расстояние один. Второй кортеж описывает такси. Оно имеет номер ноль и стоит по 20 рублей за километр. Человек мало едет в дорогом такси, все ОК. Ну и второй кортеж, соответственно: человек номер один хочет ехать два километра на такси номер один с ценой за километр 10. Он едет далеко, он едет на дешевом такси. Отлично. Давайте куда-нибудь теперь, вместо того чтобы печатать, это сохраним все безобразие. Но это уже почти ответ, нам осталось его красиво вывести. Как красиво вывести ответ? Нам нужно что сделать? В общем-то, сопоставить каким-то образом, то есть просортировать теперь вот этот вот ответ по номерам людей. И для каждого номера человека вывести номер машины, на которой он едет. Давайте я создам sortedAns, отсортированный ответ — это будет результат применения sorted функции к ans списку, iterable, с нашими кортежами. А в качестве key, ключа сравнения, будет выступать номер человек. Где же он у нас лежит? Опять же с помощью lambda-функции мы его выковыриваем. Значит, у нас номер человека лежит в [0] [0]. Нулевой кортеж описывает человека, нулевой элемент в нем описывает номер этого человека. И что мы теперь должны сделать? Мы должны вывести результат применения функции map. Казалось бы, зачем нам тут map? А map нам нужно, чтобы выковырять номер такси теперь. Мы будем применять lambda-функцию по доставанию номера такси. Напомню, опять у нас передается этот кортеж из пары кортежей. Где у нас лежит номер такси? В первом элементе, в первом кортеже при нумерации с нуля и в нулевом элементе в нем. Вот такая lambda-функция. И, наконец, sortedAns. Вот к чему она применяется. Давайте проверять, что все это работает. Кажется, что должно, но мало ли. Итак, двое людей, один километр и два километра, и два такси: по 10 рублей и по 20 рублей. Ну и говорится, что человек номер ноль должен ехать на первом такси, а человек номер один должен ехать на нулевом такси. Действительно. Если хочется нумерацию с единицы сделать, то нет ничего проще: в lambda-функции прибавляем единицу. Вот такая программа. Теперь давайте ее постепенно превращать в нечитаемое функциональное нечто. Пока что, благодаря названиям переменных, пока еще понятно, что в ней происходит. Давайте напишем в чисто функциональном стиле. Как это делать? Я даже старый текст не буду удалять, я его оставлю, потому что без него мы сами запутаемся. Итак, вот мы потихонечку-полегонечку начинаем красиво расставлять отступы. И на место наших переменных подставлять, давайте я скопирую, подставлять то, что у нас было написано в программе. Вот смотрите, теперь у нас переменная ans на очереди. А она что такое? Это zip. Делаем zip, параметры и так далее, продолжаем весь этот процесс, то есть на место каждого, каждого, каждого параметра подставляем то, что у нас записано сейчас в программе. И расставляем эти переводы строк, ну хотя бы чтобы оно в одну длинную колбасу не слиплось. Так, на чем я остановился? На такси. Осталось немного, но уже ничего абсолютно не понятно. [ЗВУК] Совсем чуть-чуть, у нас остался, в zip'е у нас остались отсортированные пассажиры. Отлично, вот они, отсортированные пассажиры. [ЗВУК] Еще мгновение, последний шаг — это подставить вместо списка пассажиров опять же функцию чтения и сделать кучу строчек. Все, теперь убираем старый код, который был понятен, и получаем огромную-огромную программу из 29 строк, которая, надеюсь, будет работать. [ЗВУК] Да, она по-прежнему выдает то, что нужно, но мы добавили прибавление единички. Написано в чисто функциональном стиле, поэтому если хотите похвастаться перед кем-то, что знаете функциональное программирование и можете написать программу, то вот такая сложная штука, которую очень сложно написать с нуля, делается тем несложным методом, который я вам показал. [ЗВУК] [ЗВУК]
