Pull to refresh
  • by relevance
  • by date
  • by rating

Атомарная группировка, или Ни шагу назад!

Regular expressions *

0. Присказка


В некотором царстве, в некотором государстве жил-был программист. Звали его, как полагается, Иван. Был он настоящим спецом, обладал всеми Тремя Великими Добродетелями Программиста, то есть был ленив, спесив и нетерпелив. Случилась в том царстве печаль великая: кризис. И выгнали Ваню с работы без выходного пособия. Горевал Ваня долго, а потом собрался с духом и разослал резюме по всему белу свету. Долго ли, коротко ли, вызвали Ваню на собеседование. Требований к соискателю было много, но главное — требовалось хорошо владеть регулярными выражениями. До собеседования — почти месяц, готовься — не хочу. Будучи человеком серьёзным, готовиться Иван решил обстоятельно. 3 недели и 3 дня он лежал на печи, почитывал Хабр и думал, как же неслыханно обстоятельно он будет готовиться. До собеседования остался 1 день. Ванюша мысленно обругал работодателей, которые назначают собеседование так скоро, что совсем подготовиться не успеваешь, слез с печи, сдал пивные бутылки и на вырученные деньги купил книжку по регексам. Читал он её до полного изнеможения, пока не отключился. Утром мы найдём сонную физиономию Ванюши лежащей, как на подушке, на этой самой книжке под Хабракатом.
Читать дальше →
Total votes 87: ↑86 and ↓1 +85
Views 13K
Comments 42

Catastrophic backtracking в регулярных выражениях

Programming *
Можно ли простой и вроде невинной регуляркой убить систему? Да, можно.

Например:

>>> r = '(a+)*b'

Просто — да. Невинно — вроде да. Конечно неумно, потому что скобки и звездочка лишние, но должно работать. Попробуем:

>>> re.findall('(a+)*b', 'aaaaaab')
['aaaaaa']

Круто, работает, пошли пить пиво.

А нет…
Читать дальше →
Total votes 83: ↑76 and ↓7 +69
Views 5.3K
Comments 23

Этюд для программиста или головоломка крисс–кросс

Programming *Java *
Sandbox

Думаю многим хабровчанам знакома книга «Этюды для программистов» Чарльза Уэзерелла. Если нет, то здесь можно прочитать интервью с автором и небольшой обзор книги. Мне самому совсем недавно попала данная вещь в руки, и было решено обязательно реализовать одну из задачек.

Итак предлагаю разобрать с вами один из этюдов. Писать будем на Java, поработаем с графикой и GUI + разберем алгоритм перебора с возвратом для нахождения нашего решения. Маловероятно, что статья заинтересует профи, но вот новичкам, а особенно тем, кто только изучает Java, статья может оказаться полезной.
Всем заинтересовавшимся – добро пожаловать!
Читать дальше →
Total votes 38: ↑35 and ↓3 +32
Views 27K
Comments 6

Генератор подземелий на основе узлов графа

Game development *Algorithms *Unity3D *
Translation
image

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

Введение


Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

Алгоритм


Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.
Total votes 51: ↑51 and ↓0 +51
Views 26K
Comments 9

Взламываем Ball Sort Puzzle

Open source *Python *Programming *Image processing *Logic games
✏️ Technotext 2021
Tutorial

Ball Sort Puzzle — это популярная мобильная игра на IOS/Android. Суть её заключается в перестановке шариков до тех пор, пока в колбах не будут шарики одного цвета. При этом шарик можно перетаскивать либо в пустую колбу, либо на такой же шарик.

Так случилось, что я в неё залип. Очнулся примерно через месяц, на 725 уровне. Он мне никак не давался — насколько бы глубоко я ни пытался продумать свою стратегию. В итоге — с этим вопросом я вышел в интернет, и заодно выяснил несколько интересных особенностей головоломки.

Во-первых, — игра бесконечна почти бесконечна. По крайней мере уже сейчас на YouTube есть прохождения всех уровней в плоть до 5350, а в телеграмме гуляют скриншоты 10к+ уровней. Вторая особенность, и вот это уже некрасиво, — не у всех уровней есть решение.

Ну это ни в какие ворота — против нас играет коварный ИИ. Нужно действовать соответственно!

Под катом мы:

• Придумаем алгоритм, решающий эту головоломку (Python)

• Научимся парсить скриншот игры, чтобы скармливать алгоритму задачки (OpenCV)

• Напишем телеграм бота, который будет принимать скриншоты и возвращать решения

• Выстроим CI/CD через GitHub Actions и задеплоим бота на Яндекс.Функции

Погнали!
Total votes 13: ↑12 and ↓1 +11
Views 6.3K
Comments 14