Эта история началась с функции “Рядом” в одном из наших мобильных приложений. Мы хотели, чтобы пользователи могли быстро создать групповой чат или добавить находящихся рядом пользователей в друзья. Мы попробовали решить эту задачу при помощи геолокации, Bluetooth, Wi-Fi и ультразвука, но у каждого из способов мы обнаружили критичные в нашем случае недостатки.

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

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

Код этого поста, как и сам пост, выложен на github.

До недавнего времени регулярные выражения казались мне какой-то магией. Я никак не мог понять, как можно определить, соответствует ли строка заданному регулярному выражению. А теперь я это понял! Ниже представлена реализация простого движка регулярных выражений менее чем в 200 строках кода.

Часть 1: Парсинг

Спецификация

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

• . — соответствие любому символу
• | — соответствие abc или cde
• + — соответствие одному или более предыдущего паттерна
• * — соответствие 0 или более предыдущего паттерна
• ( и ) — для группировки

Хотя набор опций невелик, с его помощью можно создать интересные regex-ы, например, m (t|n| ) | b позволяющий найти субтитры к Star Wars без субтитров к Star Trek, или (..)* для нахождения множества всех строк чётной длины.

План атаки

Мы будем анализировать регулярные выражения в три этапа:

1. Парсинг (синтаксический анализ) регулярного выражения в синтаксическое дерево
2. Преобразование синтаксического дерева в конечный автомат
3. Анализ конечного автомата для нашей строки

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

Спешу предупредить читателей: Данная статья написана только для ознакомления, и ни в коем случае не призывает заниматься подделкой проездных билетов, так как это противоречит статье 327 УК РФ. Автор не несет ответственности за любые неправомерные действия совершенные людьми с использованием информации из данной статьи.

Я обычная девушка, сравнительно недавно работающая в сфере ИТ, не имею знаний в хакинге и взломе. Но вдохновленная статьями на Хабре про взлом транспортных карт «Тройка» и «Подорожник» (которые уже не доступны, авторы Ammonia и antoo), я решила рассказать про свой собственный опыт взлома транспортных карт «Ситикарт», которые действуют в Нижнем Новгороде.



Сразу скажу, я не хакер и не взломщица, а простой фронт-энд разработчик, мои знания по работе с ПК, если отбросить знания во фронт-энд разработке, можно охарактеризовать, как «опытный пользователь».

Я не разрабатывала специальные приложения, как делали это авторы упомянутых статей, а покажу, как доступными средствами можно легко взламывать транспортные карты. Методы взлома известны давно (лет 5-7 точно).

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

Но вернусь к взлому. Итак, обо всем по порядку.

«Всякие звания (дворянина, купца, мещанина, крестьянина и пр., титулы — княжеские, графские и пр.) и наименование гражданских чинов (тайные, статские и проч. советники) уничтожаются...»

Об уничтожении сословий и гражданских чинов
Декрет ВЦИК и СОВНАРКОМа от 10.11.1917 года, ст. 2

---

Как-то же я обходился без этого раньше...

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

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

Недавно я натолкнулся на вопрос на Stackoverflow, как восстанавливать исходные слова из сокращений: например, из wtrbtl получать water bottle, а из bsktball — basketball. В вопросе было дополнительное усложнение: полного словаря всех возможных исходных слов нет, т.е. алгоритм должен быть в состоянии придумывать новые слова.

Вопрос меня заинтриговал, и я полез разбираться, какие алгоритмы и математика лежат в основе современных опечаточников (spell-checkers). Оказалось, что хороший опечаточник можно собрать из n-граммной языковой модели, модели вероятности искажений слов, и жадного алгоритма поиска по лучу (beam search). Вся конструкция вместе называется модель зашумлённого канала (noisy channel).

Вооружившись этими знаниями и Питоном, я за вечер создал с нуля модельку, способную, обучившись на тексте "Властелина колец" (!), распознавать сокращения вполне современных спортивных терминов.

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

Давно хотел написать общую статью, содержащую в себе самые основы Image Recognition, некий гайд по базовым методам, рассказывающий, когда их применять, какие задачи они решают, что возможно сделать вечером на коленке, а о чём лучше и не думать, не имея команды человек в 20.

Какие-то статьи по Optical Recognition я пишу давненько, так что пару раз в месяц мне пишут различные люди с вопросами по этой тематике. Иногда создаётся ощущение, что живёшь с ними в разных мирах. С одной стороны понимаешь, что человек скорее всего профессионал в смежной теме, но в методах оптического распознавания знает очень мало. И самое обидное, что он пытается применить метод из близрасположенной области знаний, который логичен, но в Image Recognition полностью не работает, но не понимает этого и сильно обижается, если ему начать рассказывать что-нибудь с самых основ. А учитывая, что рассказывать с основ — много времени, которого часто нет, становится всё ещё печальнее.

В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

Вот полная реализация этого алгоритма:

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;  // представим биты float в виде целого числа
  i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}

Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы



Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

Да, понадобится немного математики, но школьного курса будет более, чем достаточно.

Довольно много плохих вопросов, которые я вижу на StackOverflow, можно описать следующей формулой:

Вот моё решение домашнего задания. Оно не работает.
[20 строк кода]

И… всё.

Прим. пер.: это перевод статьи "How to debug small programs", на которую ссылаются в справочном разделе английского StackOverflow, посвящённом созданию минимальных, самодостаточных и воспроизводимых примеров. Мне кажется, она прекрасно описывает то, что должен знать каждый программист — основы отладки нерабочего кода.

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

В этой статье я расскажу о компонентах, из которых состоят приложения под Android, и об идеях, которые стоят за этой архитектурой.

Большинство литературы посвященной паттернам в ООП (объектно-ориентированном программировании), как правило, объясняются на примерах с самим кодом. И это правильный подход, так как паттерны ООП уже по-умолчанию предназначаются для людей, которые знают что такое программирование и суть ООП. Однако порой требуется заинтересовать этой темой людей, которые в этом совершенно ничего не понимают, например «не-программистов» или же просто начинающих «компьютерщиков». Именно с этой целью и был подготовлен данный материал, который призван объяснить человеку любого уровня знаний, что такое паттерн ООП и, возможно, привлечет в ряды программистов новых «адептов», ведь программирование это на самом деле очень интересно.
Статья предназначена исключительно для новичков, так что «старожилы» ничего нового для себя не узнают. В основном статья описывает известные паттерны из книги «Приемы объектно-ориентированного программирования. Шаблоны проектирования.», но более популярным и простым языком.

Привет, Хабр! С этого выпуска мы начинаем хорошую традицию: каждый месяц будет выходить набор рецензий на некоторые научные статьи от членов сообщества Open Data Science из канала #article_essence. Хотите получать их раньше всех — вступайте в сообщество ODS!
Статьи выбираются либо из личного интереса, либо из-за близости к проходящим сейчас соревнованиям. Если вы хотите предложить свою статью или у вас есть какие-то пожелания — просто напишите в комментариях и мы постараемся всё учесть в дальнейшем.

Приветствую всех. Сегодня расскажу вам как я проходил собеседования в Москве на позицию .Net Developer. Усиленно готовился к собеседованиям месяц, целыми днями сидел и смотрел вопросы и пытался отвечать на них, а также читал книжки по С#. В статье привожу интересные задачки и вопросы, которые мне задавали в разных компаниях в Москве. Заранее скажу, что я попал в ту компанию, в которую хотел. Я прошел 4 собеседования в этой компании и меня наконец то взяли! Много статей было прочитано в частности здесь и надеюсь, что эту статью тоже будут читать начинающие Net разработчики и спрашивать все в комментариях.

Кому интересна тема прохождения собеседований, прошу под кат!

Чтобы сходу понимать материалы об инфраструктуре открытых ключей, сетевой безопасности и HTTPS, нужно знать основы криптографической теории. Один из самых быстрых способов изучить их — посмотреть или прочитать лекцию Владимира ivlad Иванова. Владимир — известный специалист по сетям и системам их защиты. Он долгое время работал в Яндексе, был одним из руководителей нашего департамента эксплуатации.


Мы впервые публикуем эту лекцию вместе с расшифровкой. Начнём с первой части. Под катом вы найдёте текст и часть слайдов.

Привет, хабраюзер! В этом посте я расскажу, как можно сделать свой код на Хабре более «живым» благодаря простому способу сохранения его оригинальной цветовой схемы. А также предлагаю сравнить различные варианты расцветки кода.

Во вторник в Интернете появились сообщения об утечке 3.887.882 учетных записей iTunes. Базу с аккаунтами и паролями неизвестные выложили на Pastebin.com и ряде других сайтов. В настоящее время эти записи уже удалены, однако нам доступна некоторая статистика, которая приводится ниже.

Прекрасная возможность учиться в Германии появилась у желающих со всего мира. С нового учебного года 2014/2015 высшее образование в Германии стало бесплатным на всей территории страны. Последней из семи федеральных земель об отмене платы за обучение распорядилась Нижняя Саксония в декабре 2013 года. Доротея Штапельфельдт, сенатор Комитета по науке в Гамбурге, назвала платное образование «социальной несправедливостью», пишет «Таймс» (via). Сенатор по науке считает, что ключевой задачей политики является предоставление молодёжи в Германии возможности учиться и получать качественное высшее образование бесплатно.


Фото Шона Гэллапа, Getty Images

Заголовок получился слишком громким — и ключ не такой и универсальный, и домофон поддастся не любой. Ну да ладно.
Речь пойдет о домофонах, работающих с 1-wire таблетками DS1990, вот такими:



В интернете можно найти множество материалов о том, как читать с них информацию. Но эти таблетки бывают не только read-only. Человеку свойственно терять ключи, и сегодня ларёк с услугами по клонированию DS1990 можно найти в любом подземном переходе. Для записи они используют болванки, совместимые с оригинальными ключами, но имеющие дополнительные команды. Сейчас мы научимся их программировать.

Зачем это нужно? Если отбросить заведомо нехорошие варианты, то самое простое — это перепрограммировать скопившиеся и ставшие ненужными клонированные таблетки от старого домофона, замененного на новый, от подъезда арендованной квартиры, где больше не живете, от работы, где больше не работаете, и т.п.

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

У каждого оператора поста радиоперехвата (таковыми мы числились) был в распоряжении компьютер с подключенными к нему радио-приемными устройствами. На компьютере стоял спецсофт + Excel. Все остальное было заблочено. После N-ного дежурства я стал скучать… Зачесались руки.

IT-интерфейсы часто растут из физических. Например, вот аппаратные чекбоксы:



Вообще, лучший же пример правильного инженерного интерфейса – это гранёный стакан.

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

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