Алгоритмы *

Попалась мне одна интересная задача ,суть которой - найти наибольший отрезок в массиве единиц и нулей ,где суммы их кол-ва равны друг другу. Например ,имеем массив [0, 1, 0, 1, 0]. Длина наибольшего подмассива ,где кол-во нулей равно кол-ву единиц = 4. Под этот критерий подходит подмассив [{0, 1, 0, 1}, 0] ,а так же [0, {1, 0, 1, 0}]. В обоих случаях сумма всех нулей = 2 ,а сумма всех единиц равна тоже 2. Длина такой последовательности = 4 ,и это должно быть ответом.

Сперва можно немного поработать над данными ,чтобы в будущем можно было проще вычислять такие отрезки ,где суммы 1 и 0 равны друг другу. Например ,для отрезка [0, 1, 0, 1] общая сумма значений равна 2 (0 + 1 + 0 + 1). Можно сделать вывод ,что сумма 1 и 0 равна в этом отрезке ,если сумма значений равна половине длины подмассива. Для нашего случая получается ,что (0 + 1 + 0 + 1) = 2 = 4/2 (половина длины подмассива). Но гораздо проще было бы проводить расчеты ,если бы необходимая сумма значений была бы константой ,например 0. В таком случае мы можем заменить все нули на -1 ,и таким образом получим [-1, 1, -1, 1] ,где сумма таких элементов будет равна 0.

На JavaScript это можно сделать следующим образом: arr.map(x => x || -1).

Далее нам потребуется цикл по длине arr:

В ходе обсуждения с товарищем docent2007 статьи о сортировке «Милосердный Сталин» у нас сами собой родились дополнительные, весьма полезные методы сортировки. Эти методы определённо могут пригодиться каждому.

Либеральная сортировка

Либеральная сортировка уважает каждое значение и его "право" на место.

def liberal_sort(arr):
    # Каждый элемент остается на своём месте, потому что все равны
    return arr

То есть массив возвращается таким, какой он есть, без изменений, поскольку "у каждого элемента своё уникальное место, которое нельзя нарушить".

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

from collections import defaultdict

def liberal_sort_with_groups(arr, key_func=lambda x: x):
    # Группируем элементы по ключу, но внутри групп порядок сохраняется
    groups = defaultdict(list)
    for item in arr:
        groups[key_func(item)].append(item)

    result = []
    for group in groups.values():
        result.extend(group)
    return result

arr = [5, 3, 8, 3, 1, 8, 5]
sorted_arr = liberal_sort_with_groups(arr, key_func=lambda x: x % 2)
print(sorted_arr)
# нечетные и затем четные, но порядок в группах сохранен
# -> [5, 3, 3, 1, 5, 8, 8]

Моя основная деятельность — конфиденциальная обработка данных. Это такая развивающаяся область науки и техники, в которой часто возникает что-то новое, поэтому терминология ещё не устоялась. То, чем я занимаюсь, по-английски называется Secure Multi-Party Computation, а на русский переводят как совместные или многосторонние вычисления. Однажды я видел перевод: «многопартийные вычисления», – но, надеюсь, это единичный случай. Лично мне нравится вариант: «конфиденциальные вычисления», который использует википедия. Его буду использовать и я.

Представьте, вы собрали какие-то ценные данные, зашифровали их и сохранили на диске. Таким образом, вы защищаете данные во время хранения (data-at-rest). Далее, предположим, вам нужно передать данные по сети с одного сервера на другой. Серверы устанавливают защищённое соединение и обмениваются данными – снова зашифрованными. Так серверы защищают данные во время передачи (data-in-transit). Пока всё знакомо и понятно. Далее вы собираетесь делать то, ради чего вы эти данные собирали, хранили и передавали: использовать их. Что-нибудь посчитать, агрегат какой-нибудь, статистику или даже модельку обучить. Анализировать зашифрованные данные —, затруднительно, поэтому вы их расшифровываете и… делате беззащитными.

Во-первых, это странно: вы старательно защищали данные, когда хранили и передавали, и вдруг почему-то перестали. Во-вторых, это опасно: атаки, утечки, несанкционированный доступ, всё, что угодно может случиться, когда данные уязвимы. Ну, и в-третьих, расшифровывать не обязательно: существуют методы, защищающие данные, когда они используются (data-in-use). Совместные конфиденциальные вычисления – один из них.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

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

В прошлой заметке я коснулся принципа работы некоторых популярных алгоритмов неточного решения задачи коммивояжера (TSP). Материал получился объемным и сунуть туда еще одно описание алгоритма было бы чрезмерностью. Тем не менее, считаю важным рассказать еще об одном решении, которое носит название - Алгоритм Кристофидеса-Сердюкова. Причины, по которым мне хочется об этом поговорить следующие:

1. Речь идет про алгоритм, который часто используется в качестве бенчмарка при оценке эффективности поиска решений сетками с использованием трансформеров, например в работе TranSPormer: A Transformer Network for the Travelling Salesman Problem и не только

2. Несмотря на то, что алгоритм назван в честь русского математика в русскоязычном сегменте интернета не так много публикаций на эту тему, можно отметить статью Сердюкова от 1978 и упоминание в Википедии

3. Наконец, алгоритм просто красив. Понимаю, что математическая эстетика – это нечто скрытое в глубине вещей и недоступное суетливому взору, но верю, что и такая категория красоты найдет своего читателя.

Это еще одна статья про демосцену, сайзкодинг, ассемблер, MS‑DOS и ретрокодинг. То есть, о том, как ночами напролет добровольно и бесплатно писать бесполезный и очень трудоемкий код, и получать от этого массу удовольствия (и седую бороду). Даже если вы уже пробовали и вам не понравилось, вам все равно стоит почитать. Возможно, вы что‑то делали не так. Например, использовали не те буквы и цифры. А еще тут есть подборка «демок» размером в 256 байт!

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

А теперь мы с командой разрабатываем PIM-систему, это инструмент по управлению информацией о товарах. Среди задач в беклоге я нашел задачу себе по душе: попробовать реализовать массовую генерацию инфографики для маркетплейсов. А в этой статье я хочу рассказать о подходе, который я использовал.

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

Но генерация текста не всегда имеет однородную сложность, так же как мы во многом мыслим идеями, а слова произносим «на автомате». В статье обсудим алгоритмы, позволяющие использовать эту неоднородность для ускорения.

«Виселицу» — популярную игру на угадывание слов — кто‑то упомянул в комментариях к предыдущему посту, о задаче про игру в «Гонки». Не очень в тему, конечно — но я подумал «а чего это у нас задачи про виселицу нет?»

Теперь есть!

Обычно под программированием этой игры подразумевается написать код который загадывает слово — а пользователь предлагает буквы (и это пользователь будет повешен в случае неудачи). Здесь же наоборот — нужно написать программу которая угадывает слово по правилам данной игры. И теперь уже программист старается избежать «повешенья».

Задача интерактивная — сервер загадывает слово — а наша программа должна HTTP‑запросами предлагать ему буквы и смотреть что получается. Я покажу как можно «поиграть» вручную прямо из командной строки, используя curl но сдать задачу «вручную» не получится, поскольку присутствует ограничение по времени — так что без программы не обойтись.

У нас есть 3 "теории всего" - научная картина мира (все сводится к законам физики), информатика (все сводится к битам) и фундамент математики (все сводится к логике). Именно фундамент математики представляет особый интерес, так как он является фундаментом для двух других фундаментов и имеет глубокий философский смысл. Последние 2 года я сильно им увлекся и проделал довольно большую работу по углубленному изучению теории типов (Calculus of Constructions), и готов поделиться результатами, а также рассказать о девяти направлениях, где можно применить это на практике. Очень многое получилось лучше, чем я планировал. Изначально перспективы были не очень понятными, и поэтому я не рассказывал друзьям и коллегам про мою работу в этом направлении и называл это «Секретный Проект». Но теперь, когда многое прояснилось и получилось, можно поделиться успехом. Собственно, в этой статье я расскажу вам не только про сам фундамент математики, а еще его связь с ежедневной работой программиста, а также с Computer Science/Data Science и AI/ML. Я вам нарисую большую и красивую картину, на которой все понятно и логически следует из маленького набора правил выведений типов (11 штук) и аксиом теории множеств (9 штук).

У нас есть 3 фундамента математики — теория множеств (удобна для человека), теория типов (удобна для компьютера) и теория категорий (не знаю, зачем она вообще нужна). Они примерно одинаковой мощности и одну можно выразить внутри другой. Особый интерс представляет именно теория типов, тк ее довольно легко можно запрограммировать внутри компьютера и использовать как строгий фундамент для других теорий, который не дает совершить ошибку и проверяет каждое ваше действие.

Привет Сегодня мы рассмотрим, заключительный в цикле материалов, Российский шифр «Кузнечик».

«Кузнечик» — это современный стандарт шифрования в России и за рубежом. Опубликован был в 19 июня 2015 года. В наступающем 2025 году будем отмечать его юбилей.

Среди игр на тетрадном листочке из школьной поры была такая Гонки — вы тоже помните? На удивление, похожую игру предлагает в своей старинной книжке Жак Арсак — машина «в пошаговом режиме» мчится по извилистой трассе на целочисленной плоскости — и нужно варьируя вектор скорости умудриться не вылететь — но и доехать не черепашьим шагом.

Задача на основе этой игры добавлена на сайт к новогодним праздникам — вдруг кто‑то устанет от оливье раньше времени :-) Здесь в качестве входных данных вы получаете описание профиля всей трассы целиком — и нужно предложить последовательность ходов которые позволят безопасно проехать весь маршрут притом со средней скоростью не хуже 3 клеток за ход (считая только продольную компоненту скорости).

Чтобы легче было понять принцип (вдруг кто‑то не играл в детстве) — добавлена небольшая демонстрашка, в которой можно управлять прохождением по трассе кликая или тапая в нужные участки экрана.

Честно говоря планировалось что в задаче будет спрашиваться наиболее быстрый маршрут — но составляя её я немного усомнился в собственном решении — поэтому она стала чуточку проще.

Конечно, из‑за того что вся трасса видна сразу, отсутствует интрига — но на днях планируется добавить версию игры в которой нужно играть против HTTP‑сервера — и там «видимость» трассы будет ограниченной, так что если не хватает интриги — просто чуть‑чуть подождите :-)

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

Всем привет! На связи команда аналитиков X5 Tech. Мы продолжаем исследовать подходы Reinforcement Learning для ценообразования. В этой статье мы рассмотрим применение контекстных многоруких бандитов на примере модельной задачи, опишем несколько реализаций и сравним их.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части научимся применять разные условия в зависимости от состояния рекурсивного "цикла" и отлавливать его "зацикливание".

Привет, Хабр! Я Денис Логашов, инженер-исследователь отдела автоматической обработки результатов моделирования и визуализации YADRO. В этой статье я расскажу о решении основной задачи в соревновании Micromouse: как роботу пользоваться сохраненной картой лабиринта для передвижения по нему и поиска кратчайшего пути. Это продолжение предыдущего материала, где мы учили робота карту составлять.

Оказывается Хабр доброжелательно предоставляет возможность завести бесплатный «корпоративный» блог для опенсорсного проекта. Какое‑то время назад я подал заявку — и недавно обнаружил что она была удовлетворена. Начинать программисты любят с «тестового» поста, но т.к. речь идёт о публичном пространстве, пусть он будет хоть немного содержательным:)

На сайт CodeAbbey сегодня добавилась задачка про поиск Белого Прямоугольника. Речь идёт о матрице в которой есть чёрные и белые клетки — расставленные достаточно хаотично — и хочется найти прямоугольник без чёрных клеток максимальной площади (со сторонами параллельными сторонам матрицы, конечно).

Про сам сайт мы ещё расскажем в отдельно (иначе зачем блог было заводить) — а сейчас всё же про саму задачку.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части воспользуемся обширными возможностями поиска в массивах и реализуем рекурсивную сортировку «пузырьком».