Попробуйте решить эту головоломку. Посмотрите, сможете ли вы пройти по всем мостам ровно один раз.

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

Есть четыре разных места: два острова и две части материка. И семь мостов. Интересно узнать, существует ли какая-либо закономерность в отношении количества мостов, связанных с островами или материком (мы будем использовать термин “земля” для обозначения четырех различных мест)?

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

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

Если вы попытаетесь обобщить это рассуждение для одного участка земли, то увидите, что в случае чётного количества мостов всегда можно покинуть землю, а в случае нечётного – нет.

Изменим условие

Давайте добавим новый мост, чтобы узнать, как изменится количество общих соединённых мостов, и решит ли он проблему:

Теперь, когда у нас есть два четных (4 и 4) и два нечетных (3 и 5) числа мостов, соединяющих четыре части земли, давайте нарисуем новый маршрут с добавлением этого нового моста.

Завтра рассмотрим это на граффах!👍

Искусственный интеллект с примерами на Python
Автор книги: Джоши П.
Год издания: 2019

Переходим к графам

Мы увидели, что число чётных и нечётных мостов сыграло свою роль в определении возможного решения. Возникает вопрос. Количество мостов решает проблему? И должно ли это работать во всех случаях? Оказывается, это не так. Вот что сделал Эйлер. Он нашёл способ показать, что количество мостов имеет значение. Что более интересно, также имеет значение количество участков земли с нечётным количеством соединённых мостов. Именно тогда Эйлер начал преобразовывать земли и мосты в то, что мы знаем как графы. Вот как может выглядеть граф этой задачи (обратите внимание, что временно добавленного моста нет).

Важно отметить обобщение/абстрагирование задачи. Всякий раз, когда вы решаете определённую задачу, самое главное – обобщить решение. Конкретно в этом случае задача Эйлера состояла в том, чтобы обобщить эту задачу для решения подобных в будущем. Визуализация также помогает рассматривать проблему под другим углом. Изображения ниже – различные представления одной и той же задачи Кёнигсбергского моста.

itertools.combinations

itertools – впечатляющий модуль. У него так много разных методов, позволяющих экономить время. Есть даже репозиторий GitHub, содержащий ещё больше подобных инструментов.

#полезностьдня

Давайте посмотрим на метод combinations. Он принимает в качестве аргументов итерируемый объект и целое число. В результате получаем генератор, состоящий из всех возможных комбинаций итерируемого объекта. Максимальная длина последовательности равна указанному целому числу. Сочетания не дублируются:

import itertools

list(itertools.combinations([1, 2, 3, 4], 2))

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

Рекомендую к прочтению👆

100+ крутых проектов, созданных с помощью Python

https://proglib.io/p/great-python-projects/

​​​Flask Web Development
Автор: Мигель Гринберг

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

В книге рассматриваются следующие темы:
- структура микрофреймворка;
- шаблоны;
- базы данных;
- веб-формы;
- система аутентификации, публикации и комментирования;
- тестирование и многое другое.

#книгадня

Примеры кода на github https://github.com/miguelgrinberg/flasky

Скачать книгу:
 https://t.me/progbook/2715