Алгоритмы *

Вам нравятся старые Legend of Zelda времён SNES и GBA? Может быть, вам пришлась по вкусу Dark Souls? А, возможно, вы ещё и фанат Quake? Но что объединяет все эти игры? Для меня это в первую очередь дизайн уровней. Головоломки, удобные шорткаты и нелинейность исследования - вот то, что делает карту игры частью общего игрового процесса и вдыхает жизнь в процесс исследования мира.

В наше время расцвета жанра rogue-lite вопрос генерации игровых уровней актуален как никогда. Однако по-настоящему интересные уровни в жанре - большая редкость, я бы даже сказал, феноменальная. Чаще всего уровни представляют собой просто наборы заранее заготовленных комнат-коробок, случайным образом приставленных друг к другу, без какой-либо логичной высокоуровневой картины. Но, всё же, я знаю одну игру, которая взяла принципиально другой подход: Unexplored. На мой взгляд, она пересмотрела устоявшийся стереотип об ограничениях левелдизайна в рогаликах. Всё, что для этого понадобилось - циклическая генерация подземелий (Cyclic dungeon generation).

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

TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

Может показаться, что на самом деле просто не было существенного прогресса с 60х годов, так как Дейкстра предоставил почти асимптотически оптимальный алгоритм решения задачи. На самом деле нет, прогресс был и придумали много чего интересного, хоть и действительно с того времени фокус сместился на другие задачи. Приглашаю под кат если интересно узнать что такого напридумывали, что используется в современных логистических системах, почему меня огорчает отсутствие учёта флага единства в HOMM3 при расчёте пути, ну и наконец, что за мужики на картинке выше рядом с Дейкстрой?

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

Небольшая заметка студента о том, как самостоятельно реализовать алгоритмы SHA256 и SHA512 на Rust.

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

WebGPU — это мощный GPU-API для веба, поддерживает продвинутые рендеринговые конвейеры и вычислительные конвейеры GPU. WebGPU ключевым образом отличается от WebGL своей поддержкой вычислительных шейдеров и буферов хранения данных. В WebGL такие возможности отсутствуют, а WebGPU, в свою очередь, позволяет целиком выполнять в браузере мощные приложения, требующие вычислений на GPU. Речь может идти о самых разных приложениях, от GPGPU (напр., симуляции, обработка/анализ данных, машинное обучение, т.д.) до конвейеров рендеринга на основе GPU-вычислений — а также о многих других приложениях в этом спектре.

В этой статье мы оценим вычислительную мощность WebGPU, сравнив её с показателями Vulkan. Для этого мы реализуем классический алгоритм «марширующие кубы» (Marching Cubes) для WebGPU. Алгоритм марширующих кубов почти без оговорок относится к чрезвычайно параллельным, в составе этого алгоритма выполняется два глобальных шага редукции, необходимых для синхронизации местоположений рабочих элементов и вывода потоков. Поэтому данное решение — отличный вариант GPU-параллельного алгоритма, который стоит первым делом попробовать на новой платформе. Дело в том, что он достаточно сложен, чтобы API испытал давление сразу по нескольким направлениям сверх элементарных параллельных операций диспетчеризации в ядре. При этом он не столь сложен, чтобы на его реализацию требовалось существенное время, а также он не превращается в узкое место из-за ограничения производительности ЦП.

В 2018 году в androidx появился новый пакет collection, который содержал несколько специфичных структур данных, переписанных на Kotlin, таких как LongSparseArray, SimpleArrayMap и SparseArrayCompat.

На тот период Kotlin только начинал набирать обороты в Android разработке и добавление новых более эффективных коллекций, полностью написанных на нём было одним из шагов по внедрению языка.

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

На примере 32-битных целых чисел рассматривается масштабируемый алгоритм деления, использующий числа с двукратно меньшей (16 бит) разрядностью. Для иллюстрации работоспособности алгоритма приведен код тестового приложения на языке С++.

Постановка задачи:

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

Сделаем небольшое отступление. Многие уже на этом моменте могут сказать, что подобные задачи решаются методом коллаборативной фильтрацией. И в целом они будут правы. Но есть случаи, когда фильтрация не подходит или ее недостаточно. Для примера давайте представим себя в роли продавца автомобилей, который думает, какой новой маркой / моделью авто ему начать торговать. Допустим у него есть выбор из 1000 вариантов. И тут уже становится понятно, что идея коллаборативный фильтрации не очень хорошо вписывается в этот случай. Продавцу хочется сделать выбор, не основываясь на предпочтениях других продавцов, а исходя из неких характеристик, определяющих выгоду объекта.

В сухом остатке имеем n признаков. Что с ними нужно сделать, чтобы достичь желаемого? Можно суммировать значение всех признаков для объекта и получить итоговую оценку, которая отражает совокупный итог всех знаний об объекте. Но что не так в таком простом подходе?

Всем привет! Я реализовал, похоже, собственный алгоритм поиска кратчайшего пути с отрицательными ребрами графа.

Почему собственный? Я искал подобное решение, но не нашел, возможно, оно уже было реализовано, просто плохо поискал. Жду Нобелевскую премию =)

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

Многие задачи, с которыми мы имеем дело при цифровизации производства (неважно какого), – это задачи оптимизации: оптимизация производственного расписания, оптимизация цепочек поставок и размещения объектов, оптимизационное планирование и прочее. Многие из них сводятся к проблемам смешанного линейно-целочисленного типа (MILP – Mixed Integer Linear Problem). Конечно же мы хотим их решать быстрее и эффективнее, поэтому год назад начали разработку ML-модулей для этого. В этой статье мы познакомим вас с концептом одного такого модуля – для упрощения MILP методом обнуления переменных – и расскажем о том, насколько нам удалось с его помощью сократить время работы решателя.

Что такое конечные автоматы?

Простое .NET решение для четких фото: избавьтесь от дымки или тумана на изображениях всего за несколько шагов!

Представьте большой отель с собственным сайтом. Огромное число клиентов: старых, новых и потенциальных. Менеджеров атакуют с вопросами от «а можно забронировать двухместный номер на 5-е число» до «а когда будет завтрак».

Новые клиенты, которые хотят заехать в отель, не могут дозвониться и выбирают другое место.

Всем известна простая истина бизнеса: теряется клиент = теряются деньги.

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

В чем заключалась проблема?

Рассмотрим дело в разрезе чисел. Собрали статистику и выяснили, что недополученная прибыль составила порядка 1 миллиона рублей. Из-за отвлечения на типичные вопросы менеджеры не успевают обрабатывать 30% заказов. С технологической точки зрения процесс не меняется: отель работает в том же режиме, затраты на оплату труда не стали больше или меньше. Но без обработки 100% потока желающих гостиница не получила миллион рублей. Отчет аналитика показал неутешительные выводы: конверсия падает, отель теряет деньги. Было два пути решения этой проблемы: найти новых сотрудников или оптимизировать труд уже нанятых. Искать и обучать новых людей было затратно по времени и финансам, поэтому решили сделать более эффективной работу менеджеров.

Что мы сделали?

Так как вся система отеля находилась в Битрикс24, и там же была установлена связь с виджетом от ChatApp, нам оставалось только настроить автоматизированные ответы на часто задаваемые вопросы - что мы и сделали!

Современные томографы позволяют получать высокоточные трехмерные изображения внутренней структуры большого размера, предоставляя ценную информацию о геометрии, составе и дефектах исследуемых образцов. Размеры одной реконструкции обычно колеблются от 512 мегабайт до 1 терабайта. Для анализа таких данных используются специализированные инструменты, но традиционная визуализация трёхмерного объема реконструкции до сих пор является важным этапам оценки качества реконструкции и её интерпретации специалистом.

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

Нежданно ни гадано, затеяли значит высшие "итишные" силы включить новые заморские очереди Кафка в уже выполненный на 4/3 проект и слава богу, что только для внешних взаимодействий и передачи всякой информации туды-сюды. Главный архитектор дал благословение и понеслось, да не туда, так как нести то некому это невиданное заморское чудо. Что делать, в обозримые сроки не впихнуть и перед боярами чин и обязательства не сдержать. Посидел РП, погоревал, да сдул пыль со знаний древних и ранее опробованных и тут понеслось.

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

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

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

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

Мы попросили Самсонова Ивана рассказать о его критериях оценки кандидатов, а также поделиться советами по подготовке. На видео Иван выступал в роли тимлида, а в обычной жизни он разработчик со степенью в Computer Science и наставник курса «Алгоритмы и структуры данных».

Приветствую. Речь в статье пойдёт про мой опыт реверсинга и написания ботнета для $NotCoin.

Дело было вечером, делать было нечего, подружка села на заборе — и скинула мне ссылку на ноткоин в альфе.
Посмотрел, потыкал, недолго думая, я забыл про него на месяц.
И вот он уже набрал аудиторию и я подумал, что всё же стоит посмотреть что там да как.

Суть игры в одном слове: кликер.

И что же нужно делать?
— У тебя есть монетка, на неё нужно кликать, чем больше монет - тем лучше.

Привет, Хабр! Меня зовут Илья Ненахов, я руковожу разработкой платформы для продвижения товаров на Яндекс Маркете. Предлагаю взглянуть на площадку немного с другой стороны, а именно — как на механизм, который пытается найти оптимальную точку в пространстве с тремя измерениями:  интересы пользователя, интересы магазинов и интересы самого сервиса.

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