Статья является логическим и практическим продолжением статьи про алгоритм вывода черепахи из лабиринта. Автор @demitryy сформулировал идею, но не описал практического её воплощения и в ходе оживлённой дискуссии появилось два подхода к реализации алгоритма. Один представил и воплотил на C++ пользователь @wataru, а второй, с разными видами оптимизаций, озвучил ваш покорный слуга. В статье мы увидим результат тестирования обоих подходов на C# и какие открытия для себя сделал автор.
Занимательные задачки
Разминаем мозги
Новости
Флаттер крыла самолёта
Флаттер‑ это загадочное явление в аэродинамике, которое есть, но объяснения которого до сих пор нет.
Про «флаттер» я уже писал отдельную «главу № 4» в первой своей большой статье про «Подъёмную силу крыла без „закона Бернулли“.
Недавно попытался перечитать снова эту главу, и оказалось, что её надо дописывать и публиковать отдельной статьёй, так как в ней всё не очень наглядно и совершенно непонятно написано.
В рамках большой статьи та куцая глава про «флаттер» была вполне уместна. Но вот оказалось, что само явление «флаттера» также плохо определено, как не определено в общепринятой «Аэродинамике» базовое понятие «подъёмная сила крыла».
SQL HowTo: Black and White (Puzzle Hunt 2010)
Некоторые головоломки можно решать на SQL just for fun, а часть получается выразить на этом декларативном языке даже эффективнее других, императивных.
Попробовать сделать более наглядное решение, а заодно познакомить с некоторыми нетривиальными возможностями PostgreSQL меня натолкнул пост о решении на Python задачи Black and White.
Разбираетесь в IT и технологиях? Попробуйте решить кроссворд и выиграть мерч Selectel
Привет, Хабр! На связи команда Selectel. Помните IT-кроссворд, который мы проводили в прошлом году? В течение 4 дней вы разгадывали более 128 вопросов. Это было круто, но нам показалось, что недостаточно. Кроссворд оказался проще, чем мы думали.
Самое время это исправить и прибавить единицу к степени двойки! Мы запускаем второй сезон IT-кроссворда — новый виток онлайн-соревнования среди всех, кто интересуется технологиями и не только. В этот раз все интереснее: вам предстоит решить более 256 вопросов, проверить знания в разработке, истории IT, ИБ, мобильных девайсах, инфраструктуре и ML. А еще — показать свои Soft Skills!
Под катом — кроссворд и вопросы. Знатоки, которые наберут за ответы большее количество баллов, получат эксклюзивный мерч Selectel. Готовы принять участие? Тогда начинаем!
Истории
Решение головоломки из университетского квеста с помощью Python
Black and White — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2010 года. По сюжету игры вы преследуете загадочного участника ТВ‑шоу в надежде раскрыть его личность. Вам удается пробраться сначала на студию, а затем и в его гримерку. Там в его одежде вы находите клочок бумаги. Одну из его сторон занимает сообщение, другую — головоломка и набор инструкций к ней.
«Разложите каждую из диаграмм ниже на полоски размером 1×1, 1×2 или 1×3 таким образом, чтобы ни одна сетка не содержала полосок с одинаковым черно‑белым паттерном, включая повороты».
Стек с поиском максимума
Несколько раз мне попадалась задача из разряда «собеседование в Google»:
нужно реализовать стек, хранящий целые числа, в котором дополнительно должна существовать операция max()
, возвращающая максимальный элемент за O(1)
времени и с использованием O(1)
дополнительной памяти (в сравнении со стеком без этой операции).
Предполагаю, что многие тоже о ней слышали, а может даже знакомы с каким-либо решением. Про решения я и предлагаю поговорить, там всё очень интересно.
Прогнозируем солнечные затмения с помощью ~100 строк кода Python
8 апреля 2024 года автор статьи, основатель и СЕО компании Modal Labs, Эрик Бернхардссон планировал посмотреть свое первое полное солнечное затмение. За день до этого ему пришла в голову идея — что, если попробовать рассчитать периодичность этого явления в прошлом и будущем, используя Python? Несмотря на незначительные сложности с системой координат, автору удалось создать работоспособное решение всего за несколько часов.
Под катом читайте, как с помощью ~100 строк кода удалось вычислить и проследить путь каждого солнечного затмения в период с 2020 по 2030 год.
*Обращаем ваше внимание, что позиция автора может не всегда совпадать с мнением МойОфис.
Моделирование атмосферного «циклона» и «смерча» в лабораторных условиях
Эксперимент по натурному моделированию вихревых структур «циклонов» и «смерчей» на лабораторной установке комнатной размерности.
Ранее я написал несколько статей про предполагаемые механизмы работы циклонов и смерчей в атмосфере планеты Земля.
Какими силами закручиваются в вихри разрушительные смерчи и тропические ураганы? / Хабр
Зачем нужен «глаз» тропическому циклону и как дуют ветры под облачным покровом циклона? Часть-2
Механизмы образования антициклонов над континентами. А причём тут роса на траве по утрам?
После написания этих статей у меня возник вопрос :
А можно ли построить мелкомасштабную действующую модель циклона и смерча, чтобы на практике проверить теоретические предположения?
Порывшись в интернете на тему натурных экспериментов со смерчами я выяснил, что во всех действующих «макетах» смерчей основное внимание уделяется закручиванию шнура смерча.
В моей модели «смерча» роль вращения «шнура смерча» имеет второстепенное значение, а основное значение имеет обжатие осевого шнура встречными потоками воздуха, направленными к оси.
Именно такой макет встречных потоков воздуха к общему центру на плоскости я и решил построить.
Для этого нужен высоконапорный вентилятор и само плоское кольцевое распределительное устройство для воздуха.
Всё это я собрал в единую установку из подручных материалов и доступных по цене бытовых устройств (см.рис.1.)
ARCHI.TECH ВТБ: как проверить более 70 решений за несколько часов или что под «капотом» у архитектурного хакатона
Добрый день, дорогие хаброчитатели. Меня зовут Алексей Прутик, я архитектор платформенных решений ВТБ. А по совместительству эксперт и один из судей архитектурного хакатона ARCHI.TECH ВТБ, про который я расскажу в этой статье. Вы прочитали заголовок и вам хочется узнать, как научиться делать невозможное? Очень скоро это станет понятно. Начнем с краткой информации по хакатону, ведь он уже закончился и можно подвести итоги.
Как Выигрывать в Игре Быки и Коровы
Существует старинная народная логическая игра. Называется быки и коровы. Её ещё называют mastermind.
В этом тексте я представил мой алгоритм для поиска решения в этой игре. Я назвал этот метод: Матрица возможных решений.
Суть алгоритма покажу в частном виде, то есть на примере.
Пространство двумерного времени
Мало того что наше восприятие искажено строго трёхмерным пространством (точнее не искажено, а работает только в нём), так ещё и это воспринимаемое нами трёхмерное пространство неоднородно — одно из измерений строго направлено (верх и низ) и задано гравитацией. Если вперёд и назад, влево и вправо зависит от нашего положения и, когда мы разворачиваемся, легко переходит одно в другое без каких‑либо когнитивных усилий и проблем в восприятии — то с верхом и низом так не происходит. Подвесь нас вниз головой, направь куда угодно в любом положении — верх останется верхом, а низ — низом. Мы будем двигаться именно вверх, стоя в поднимающемся лифте, и будем спускаться именно вниз, ныряя с аквалангом, хотя в обоих случаях мы движемся головой вперёд )
Понятно от чего так и зачем — мозг эволюционировал и родился в гравитации, но речь не об этом.
Говорят, есть ещё четвертое недо‑ или пере‑ измерение — время. Его мы воспринимаем ещё более направленным и постоянно в нём движемся.
В попытках порассуждать о восприятии только в трёхмерном пространстве, можно предположить о том, что в одномерном пространстве мы тоже мыслим, и привести в качестве примера как раз время. Но пространство предполагает возможности покоя и движения вдоль измерений в любом направлении (даже если измерение направлено в восприятии, например, гравитацией). С движением обратно во времени у нас всё сложно, с остановкой времени — ещё гораздо сложнее. Но пока закроем на это г̶л̶а̶з̶а̶ мозг и предположим, что ок — у нас есть в восприятии примеры трехмерного и одномерного (время) пространств. Но как быть с двумерным? Можете себе представить 2 разных ортогональных друг другу направления времени? Я — нет 🙂
Полный разбор экзамена в ШАД 2024 года
Перед тем, как смотреть решение обязательно попробуйте одолеть самостоятельно!
Автор решений: телеграм канал "Поступашки — ШАД, Стажировки и Магистратура".
Задача 1 (Линейность)
Рассмотрим линейное пространство многочленов степени не выше 3 над полем На нём задано отображение
где - многочлен наивысшей степени, являющийся одновременно делителем и , и , у которого старший коэффициент совпадает со старшим коэффициентом . Дополнительно доопределим .
Пример:
Является ли данное отображение линейным?
Разбор тестового варианта 2024 года на магистерскую программу «Программное обеспечение высоконагруженных систем» в ИТМО
Чтобы получить допуск на экзамен при поступлении на магистерской программе «Программное обеспечение высоконагруженных систем», которую ИТМО делают вместе с Яндекс Образованием, для начала нужно пройти онлайн тест. Здесь представлен тест 2024 года, а также мое личное решение к нему.
Сразу хочу сказать, что автор (то есть я) публикую это решение как абитуриент и ни сколько не претендую на полную корректность и строгость решения. И так как это онлайн тест и на него никто не накладывает никаких ограничений, помимо того, что его должен решать я, а не кто-то другой, то оставляю за собой полное право пользоваться онлайн “помощниками” такими, как сервисы построения графиков и вычисления производных. Допускаю, что многие задачи можно решить аналитически и без использования кода. Но зачем, когда время сильно ограничено :)
Публикую это, потому что нашел задачи довольно интересными, а также специально для следующих поколений абитуриентов.
Ближайшие события
Винтик и Шпунтик возвращаются из сказочной страны и решают задачу в мире самой обычной математики
Теперь когда награда обещанная уважаемым @vvvphoenixв исходной статье здесь нашла своего героя, можно рассмотреть действительный способ решения задачи, а заодно посмотреть как красивые картинки и умные слова уводят нас в сторону от настоящего решения задачи.
Полный цикл отбора на стажировку в Яндекс (Аналитика, МЛ, Бэкенд)
Наше сообщество в телеграм "Поступашки — ШАД, Стажировки и Магистратуры" в частности специализируется на подготовке к стажировкам. В этой статье наши выпускники трех самых популярных направлений расскажут, как они проходили отбор. Далее представлен слегка отредактированный текст наших выпускников.
Аналитика
Сначала ждал контест. Мне и моему другу хватило всего 3 из 6 задач, чтобы позвали дальше на собеседования.
Аналитическая секция проходила так. Была одна алгоритмическая задача: есть массив целых чисел отсортированный, надо у всех отрицательных чисел знак поменять и снова отсортировать. Потом была стандартная задача на формулу Байеса: вычислить вероятность болезни, если тест показал положительный результат. В конце был бизнес кейс в духе как оценивать качество работы службы поддержки Яндекс такси. Поговорили про метрики, пользователей и тд. Прошел без каких-либо трудностей и напрягов. На все ушел час.
Алгоритмическая секция проходила так. Всего было две задачи. Первая задача: есть строка из Х, У, О наподобие "O,O,O,O,X,X,OY,O,O,X" найти минимальное расстояние между Х и У.
Вторая задача: есть массив целых чисел надо вывести границы отрезка с заданной суммой чисел, или если такого отрезка нет, то вывести (-1,-1). Опять же прошел собес без каких-либо трудностей. На все ушел час.
Интервью с командами прошли так. На финалах в основном были беседы за жизнь и спрашивали всякую фигню типо бизнес кейсов.
На первом финале были разговоры за жизнь и кейс: придумать метрики оценки системы рекомендаций фильмов на умных телевизорах.
На другом финале дали простейшую задачу на sql, которую я даже не запомнил, ибо на столько элементарная она была. Еще был бизнес кейс по оценке работы пуш уведомлений Яндекс лавки.
Но прям норм задачи были на финале в команде, которую я по итогу и выбрал. Было несколько задач по теор веру типо рассчитать оптимальный размер гардеробов в театре с двумя входами, если известно что приходят 400 человек (мы даже такую задачу решали на семинарах). Потом спросили: у тебя десять А/Б экспериментов проводится (цвета кнопки тестируются, ну 10 разных цветов ) и один из тестов показал значимый результат (ошибка первого рода 0.1) , так вот приходит дизайнерша и говорит что её цвет кнопки показал значимый результат, что ей стоит ответить. Более типичный вопрос про множественное тестирование, я немного потупил, но решил. Ещё две задачи чисто были на теор вер, но там длинные условия и я их не понял и особо не запомнил.
Об особенностях электротехнических (и не только) сообществ: параллельные IT‑миры задают каверзные вопросы про JTAG
Несколько мыслей (и одно смелое предложение) о малозаметных парадоксах экспертности в инженерно-технических сообществах.
Решаем судоку на pytorch
Решаем судоку на pytorch. Можно ли делать нейросети без обучения? Без кучи тестовых примеров? Попробую ответить на этот вопрос.
Решение головоломки из университетского квеста с помощью Python
Треки — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2008 года. Это задание было частью пятого акта игры, и ему предшествовало небольшое повествование, которое продолжало ее сюжет. В соответствии с ним ночь в стране выдалась неспокойная; и вместо того, чтобы спать, вы провели ее в ужасе наблюдая по телевизору за уличными беспорядками. С наступлением дня ситуация несколько улучшилась, и вы решаете выйти из дома, чтобы подышать свежим воздухом. На улице вы замечаете детей, беззаботно играющих в классики на дороге. Когда вы подходите к ним поближе в надежде на то, что часть их безмятежности передастся и вам, то ваше внимание переключается на очертания классиков, небрежно нарисованных мелом на дороге. Они совершенно не соответствуют ни одним классикам, в которые вам когда-либо доводилось играть...
Ниже можно было видеть эти «классики».
Механизмы образования антициклонов над континентами. А причём тут роса на траве по утрам?
В каких случаях мы видим росу на траве по утрам?
Каждый с детства из классической литературы знает про «туман над речкой после заката» и про «росу на траве по утру».
Для примера приведу фотографии реальных пейзажей к этим пасторальным литературным штампам (см.рис.1-3)
Решение головоломки из университетского квеста с помощью Python
Cat Walk — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2012 года. Это задание было частью второго акта игры, и ему предшествовало небольшое повествование, которое продолжало ее сюжет. В соответствии с ним вы получаете от вашего странного компаньона небольшой сверток. Развернув его, вы находите внутри флешку, после чего выше внимание переключается на обертку: она, кажется, представляет собой страницу, которая была вырвана из книги с головоломками для детей. Вы долго и упорно разглядываете головоломку, изображенную на странице, и, похоже, вам удается ее решить. После этого вы обращаетесь к вашему компаньону, чтобы проверить свою догадку. Тот смотрит на вас в изумлении, быстро вставляет флешку в ноутбук, а затем радостно сообщает: «Это потрясающе! Ты разгадал пароль — это же всё, что нам требовалось...» Как оказалось, флешка содержала чрезвычайно важную информацию, а разгадка «детской» головоломки служила паролем для ее получения...
Сама же головоломка располагалась ниже. Она представляла собой лабиринт прямоугольной формы с разноцветными переходами между его частями: серого, красного, синего и зеленого цвета. Внизу лабиринта, около двух входов в него, сидел Кот Саймона, который показывал жестом, что хочет есть. Корм для кота находился на противоположном конце лабиринта, к которому вели 7 разноцветных выходов.
Вклад авторов
AKlimenkov 860.0OsipovRoman 842.8samsergey 775.0NWOcs 627.0alizar 621.5itmo 610.0haqreu 577.0iMonin 495.0Kelbon 457.0