Алгоритмист
В последний раз мы видели как изменение кода в скопированном коммите создаёт опасность конфликта, который сидит себе тихо пока обе копии где-нибудь не сольются, что может произойти и в очень отдалённом будущем. Но знаете что хуже, чем конфликт слияний?
Отсутствие любого конфликта.
Несмотря на распространённость операции git cherry-pick (копирование коммитов) в Git, обычно это не самое лучшее решение. Иногда это меньшее из двух зол, но я ещё не видел ситуации, где оно было бы целесообразно.
Это первая часть из серии статей, которые начинаются объяснением почему копирование это плохо, продолжаются рассказом почему это ужасно, а затем описывают как получить тот же результат, применяя слияние (merge). Я покажу как применить эту технику в случае, когда вам нужно сделать слияние со старыми коммитами (retroactive merge) и когда вы хотите исправить копирование на слияние пока не случилось чего-нибудь плохого.
На картинке — четверостишье, сгенерированное моей программой.
Оказывается "стихи" писать легко, нужно только знать несколько необходимых ингредиентов: размер, ритм, рифма. "Стихи" в кавычках, потому что в настоящем стихосложении, как и в любом другом искусстве, незыблемых законов нет. Однако в классике (русской силлабо-тонике) очень много правил, при соблюдении которых получается писать неплохие стихи, даже если вы никогда раньше этого не делали. Причём эти правила довольно просто программируются: "в строке должно быть равно N слогов", "нечётные строки должны рифмоваться", "ударные и безударные слоги в строке должны идти в определённом порядке" и т.д. Перечислив все правила, я свёл задачу генерации стихов к простому комбинаторному поиску. Язык Prolog как раз и предназначен для таких задач — описании правил и генерации объектов, выполняющих эти правила.
Кто хочет научится писать стихи и познакомиться с Prolog, прошу под кат.
Изучая программирование я встречаю примеры невозможных алгоритмов. Интуиция говорит, что такого не может быть, но компьютер опровергает её простым запуском кода. Как такую задачу, требующую минимум кубических затрат по времени, можно решить всего за квадрат? А вон ту я точно решу за линию. Что? Есть гораздо более эффективный и элегантный алгоритм, работающий за логарифм? Удивительно!
В этой статье я приведу несколько таких "ломающих шаблоны" алгоритмов, показывающих что интуиция может сильно переоценивать временную сложность задачи.
Интересно? Добро пожаловать под кат!
Я уже давно не студент, но в свободное время изучаю материалы по Computer Science. Мне нравится получать знания и делиться ими. Недавно я наткнулся на любопытную задачу в известном учебнике "Алгоримы: Построение и Анализ". В этой статье я продемонстрирую принципы динамического программирования, используя эту задачу. Она интересная, не очень сложная и для её решения не требуется писать какие-то дополнительные структуры данных или библиотеки. Формулировка умещается в одно предложение:
Найти самую длинную палиндромную подпоследовательность в слове w длиной n.
Кому интересно, прошу под кат.
В этой статье я расскажу как написать свою реализацию известной игрушки Сокобан, а также алгоритм для её решения с нуля. Заодно применю на практике некоторые шаблоны проектирования и принципы SOLID.