DasKoldir

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

Жил значит мой сосед, пусть будет Витек, в нашей деревеньке не тужил. Перебивался случайными заработками, жрал водочку, женился на девахе из соседней деревни. В общем все бы ничего, но фактически он в деревне оставался одним из последних молодых, моего поколения. Загибалась деревня, ни работы ни людей, таких деревень сейчас тысячи и тысячи уже умерших.

Как то раз позвонили Витьку спамеры с предложением мегакредита, не то в 20 тысяч, не то в 30. Ну а у него в кроме дырки в кармане ничего и не было. Витек радосно согласился, и поехал в рай центр за 100 км. К не малому удивлению супруги, вечером он вернулся пьяненький, но с деньгами. А на 20 тысяч по тем временам можно было месяц жить вполне нормально. Пенсия у многих и сейчас ниже.

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

Видимо где то в этот момент у Витька созрел бизнес-план. Он уже сам подавал заявки на кредиты, выплачивал предыдущий, на разницу жил. Иногда кредит давали не сразу, но Витек аккуратно вносил очередной минимальный платёж и все было в порядке, ну не считая суммы долга.

Кредитная история улучгалась, кредитный лимит все поднимался... В общем года через 3 от начала событий сумма долгов по всем кредитам перевалила за сумасшедшие 800 тысяч. Естественно на очередном витке безработному отказали в очередном кредите и пузырь благополучия Витька лопнул.

Дальше всё как полагается, суд, приставы, которые даже не побоялись съездить к нам в деревню. А толку? Имущества на Витьке нет, официальной работы нет, доходов нет. Зато есть жена и двое детей...

Морали не будет. Осуждать Витька, тоже как то язык не поворачивается. Не только его вина, в том, что образования у него нет, что его родина уничтожена, а сбежать, как я, он не осилил. Как безработному выдавали такие суммы мне не понятно, но в общем то это все, что нужно знать о "проверках в банке".

З. Ы. Похоже со справками он тоже что-то намутил, т. к. не банкротится.

Листая пикабу в очередной раз глаз зацепился за утверждение от учителя математики о том, что в группе из 40 детей почти наверняка у двух будет день рождения в один день. Интуиция сигнализировала, что в интернете кто-то не прав и я ринулся в бой.

Ну а так как я теперь считаю себя программистом я написал простенькую программу, которая посчитает вероятности такого исхода за меня. B Первый прогон для групп из 10 человек показал вероятность больше 10 процентов, что посеяло во мне сомнения.

Три раза перероверенная программа и запуски для 20, 40 и 60 детей в группе убедили меня в том, что интуиция моя заблуждается.

Откровенно говоря я не придумал, как считать такую вероятность, но все оказывается популярно разложено до меня(видимо эхо просвещения от Савватеева) докатилось и до пикабу.

Ну и похожий пост с названием видео я нашел тут на пикабу. Алексей Савватеев - Парадокс дней рождения

Как всегда я решил задать задачку chatGTP:

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

По опыту прошлых задачек стало ясно, что надо бы подтянуть общие знания по ядру Python, для чего было решено купить что-нибудь из питоновской классики. Выбор пал на Лутца:

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

Суть задачки достаточно проста: по заданному набору цифр надо вернуть все возможные комбинации букв, соответсвующие этим цифрам. Из сложностей: нам заранее не известно количество цифр, и каждой цифре у нас может соответствовать разное количество букв( 3 или 4).

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

digits = "23"

Значит на первой итерации цикла в результат запишем только буквы, соответствующие цифре 2 - это ["a","b","c"], затем срезом просто отбросим первую цифру.

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

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

И так до тех пор, пока цифра не закончатся...

Собственно и получился цикл, где мы перебираем цифры. А внутри на первой итерации(когда переменная результата пуста) задаем результат через генератор с единственным циклом, а когда не пуста задаем генератор с двумя циклами: один по текущим значениям результата, второй по буквам, соответствующим текущему значению цифры по словарю.

Результат получился быстрым и элегантным, самому понравилось.

А решение от главного конкурента оказалось слабее, по крайней мере первое рабочее решение:

Набравшись смелости и определив изрядно времени на сегодня, я решил взять задачу, помеченную как сложная. А вот собственно и она:

https://leetcode.com/problems/substring-with-concatenation-o...

На первый взгляд задачка показалась достаточно простой и смутно знакомой. Есть текст (s) и список из текстовых переменных(words). Сначала из списка текстовых переменных составляем словарь всех возможных значений, а потом пробегаемся по значениям и ищем всех их в тексте, чего же тут hard?

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

Если бы хотя бы примерно представлять размер словарика при имеющихся ограничениях на входные данные:

Как всегда перетащил тесткейс на локальную машину, и приложение сожрав 32 Гб памяти сказало кря, даже не сгенерировав словарь до конца. От словарика отказываемся....

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

LeetCode День 2 Longest Substring Without Repeating Characters [Medium]

А тут же нам надо просто подсчитать количество подстрок в строке. Длина подстроки известна заранее - это сумма длин всех слов в words, значит ее и возьмем за длину кадра(среза строки). Т.е. задачка опять на скользящий кадр. Значит осталось сравнить кадр с имеющимися словами в words и записать результат для каждого кадра, а затем вернуть общий результат.

Собственно получилось, но результат проверки меня несколько удивил: все 178 кейсов выполнены успешно, но задача не зачтена, т.к. общее время выполнения вышло за рамки допустимого. Оооокееей, уже ближе, думаем дальше.

Очевидно, что тройной вложенный цикл, это как раз то, что надо как то оптимизовать, чтобы ускорить обработку. Еще одно съеденное яблочко, дало мне идею: если кадр - соответствует искомому, значит его можно разбить на равные части, количество которых будет равно размерности словаря words. Собственно, если составить список из этих частей кадра, мы и получим список words, только со значениями в произвольном порядке. Значит достаточно сортировать список words и полученный список из частей кадра и сравнить. Если сортированный words и этот сортированный новый список идентичны, значит этот кадр мы и ищем, если нет, значит пропускаем.

Решение вышло уже вполне приемлемым по скорости выполнения. На этом стоп.

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

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

В общем было познавательно, на решение мной вбито 2+ часа. На решение ботом + оптимизация 2+ минуты.

На этот раз будем считать аквариумы объем плоских аквариумов, а значит будет много воды.

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

https://leetcode.com/problems/container-with-most-water/desc...

Собственно организуем вложенный цикл, где внешний перебирает все возможные левые стенки аквариума(т.е. кроме крайней правой), а внутренний перебирает все правые стенки аквариума(кроме крайней левой). Вуаля, и все с первого раза...

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

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

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

Но что же это значит? А значит это, что сдвигать надо всегда только меньшую по высоте сторону аквариума, потому что объем воды меряется как произведение меньшей по высоте стороны на ширину. Зафиксируем мысль, что если мы сдвигаем большую сторону аквариума, его объем точно уменьшиться, потому что ширина уменьшиться, и не важно что произойдет с высотой большей стороны, потому что считать объем мы все равно будем по меньшей. А этот расчёт для нас просто лишний, т.к. мы ищем максимальный объем аквариума. А это значит, что такой расчёт объема просто не нужно выполнять. Вот тут мы и сэкономим количество итераций.

Обратите внимание на картинку ниже, для обхода всех вариантов понадобилось всего 8 обсчётов объема, тогда когда как для первого решения это было бы 36 обсчётов(8 + 7 + 6 + 5 + 4 + 3 + 2 + 1). Да и увеличение числа границ на единицу для последнего решения увеличивает количество обсчётов всего на 1(линейная зависимость), тогда как для первого решения получается арифметическая прогрессия.

Все рассуждения выше подтвердились результатами:

От ChatGpt узнал, что это называется подход с двумя указателями решение в общем то идентично:

Сегодня было не сложно, пользоваться гайдами не стыдно, все уже изобретено до нас =)

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

https://leetcode.com/problems/longest-substring-without-repe...

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

Очевидное решение в лоб - это перебрать все возможные подстроки внутри данной строки и оценить эти подстроки на уникальность символов. Значит нам нужна функция для определения строки из уникальных символов и какой-то цикл обхода.

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

Действительно это будет работать для относительно коротких строк, но я не обратил внимание на мелкий шрифт в конце:

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

Съев яблочко, мне пришла в голову мысль. А что если зайти с другой стороны. Т.е. предположить, что все символы в строке уникальные. Т.е. нам нужно взять строку целиком, потом и проверить на уникальность символов, потом взять все подстроки входящие в эту строку длинной на один символ меньше и проверить на уникальность символов. Потом взять все строки длиной на два символа меньше и зациклить.

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

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

Ну и таки да, сначала подсчитали максимально возможный размер подстроки в отдельной функции и все тесты прошли успешно.

Ну и бонусом решение от chatGpt, которое оказалось намного лучше моего:

В целом собой доволен, но решение от chatGpt опять вгоняет меня в уныние. Мало того, что бот сделал быстрее чем я, он сделал сильно лучше, чем я.