Ненормальное программирование *

Один из программистов, работающих с Kinect, решил создать некий аналог «русской рулетки», только без пистолета. Никакого риска или угрозы для жизни здесь нет — просто компьютерная игра, или, если хотите, интересный программный эксперимент. Даже пистолета нет — вместо него используется рука играющего. Для «выстрела» достаточно направить два пальца себе в голову, и «нажать на курок», т.е., опустить большой палец.

Год назад уже была новость про запуск чернобелого Doom на калькуляторе. На днях умельцы с Hack a Day портировали DOOM на TI-nspire CX, добившись цветной картинки. Теперь игру не отличить от компьютерной версии:

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

Цель этой статьи — заставить всех, особенно программистов на Си, сказать «я не знаю Си».
Хочется показать, что тёмные углы в Си значительно ближе, чем кажется и даже тривиальные строки кода несут в себе undefined behavior.

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

Один из самых частых отзывов на мои паззлы и загадки — ой, классно, но очень уж сложно, нам бы что попроще… Поэтому первые несколько уровней я старалась делать простыми и/или классическими, чтобы не остужать интерес игроков с самого начала. Затем шло несколько уровней, основанных на моих старых публикациях на Хабре, задуманные как бонус тем, кто внимательно изучит мои труды :-) И наконец, два последних уровня были самыми сложными — к их темам я раньше не обращалась никогда. Мои поздравления тем, кто прошел квест сам или с подсказками — к сожалению, я не заложила никакого способа оценки количества таких людей. Всего скачиваний архива с квестом было более 20000.

Возьмем машину, у которой система команд точно такая же, как в языке brainfuck, но которая работает на ленте, в ячейки которой можно поместить любые целые числа. Переполнения в арифметических операциях не происходит, команда "+", примененная к положительному числу, всегда даст положительный результат, и т.п. Спрашивается: можно ли работать на такой машине, какие возникнут проблемы и как их обойти?

Преимущества очевидны: раз нет переполнений, то нет нужды и в длинной арифметике, можно одинаково работать с массивами любой длины и т.п. Но довольно быстро мы замечаем, что наш любимый способ очистки ячейки ("[-]") не работает: если в ячейке было отрицательное значение, то программа зацикливается. Аналогично, мы не можем свободно использовать команду копирования "[->+<]" — она тоже работает только для неотрицательных чисел.

Получается, что при программировании нам надо внимательно следить за знаками содержимого ячеек (проще всего — не допускать появления отрицательных чисел вообще), а если возникнет число, знак которого неизвестен — работать с ним специальным образом

Здесь мы рассмотрим две задачи: во-первых, запрограммируем оператор «if(a>b) C; else D;» где a и b неотрицательны, а C и D — какие-то действия, а во-вторых, научимся обнулять, копировать и определять знак произвольного числа.

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

Принцип я подсмотрела в квестах Дмитрия Астапова aka _adept_: на каждом уровне дается задание (текст или картинка), решив его, получаем пароль к архиву, в котором лежит следующий уровень. Архив нулевого уровня (quest.zip) без пароля.

Задания получились разные — частично на ненормальное программирование, как я и планировала изначально, частично на догадливость. Поскольку из текстового файла, а тем более из картинки, при должном желании и изобретательности можно выжать очень много вариантов скрытого текста, правильный пароль на всех уровнях отмечен префиксом «pwd:» (вводить пароль нужно без префикса).

Надеюсь, вам понравится. С наступающим!

P.S. Наличие багов не исключено; пишите в личку, исправлю, обновлю.

Update. В паззл уровня 6 закралась ошибка; исправлена, архив quest.zip обновлен (размер архива должен быть 21501 байт). Если у кого-то закешировалась старая версия, скачать его же можно по ссылке tc-alchemy.progopedia.com/quest-patch1.zip

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

Первое поздравление выводит сообщение в виде ASCII-Art.

В этой статье я покажу вам, как отсортировать циферки с помощью Brainfuck.

Вы вводите цифры (каждая цифра не должна встречаться более 255 раз, при 8bit версии интерпретатора), после программа, если ее можно так назвать, выводит их по возрастанию.

Это будет реализация сортировки подсчётом, которая работает следующим образом:
1. Считывается число k.
2. В массиве A увеличиваем A[k] на единицу.
3. Повторяем шаги 1 и 2, пока не закончатся числа на входе.
4. Выводим A[i] раз число i, где i — это возможные значения чисел k.

О системе

Фирма, в которой я работаю, разработала свою трейдинговую платформу типа MTF. В этой системе ежесекундно производятся десятки тысяч торговых операций, и с помощью паттерна Disruptor, средняя скорость выполнения трейда не превышает 20.5 миллисекунд. В проекте задействованы сложнейшие интеграции с третьими сторонами — крупными банками, Лондонским Домом Клиринга LCH и другими корпорациями.

На разработку проекта ушло около 3 лет и команда из примерно 20 инженеров. В проекте нету и не было ни одного руководителя проекта, координатора, планов проекта, диаграмм Гантта, документов архитектуры, спецификаций требований, и планов тестирования.

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

«на русской сцене мы удивляем друг друга тем, что вообще что-то делаем», © manwe
(из статуса SCRIMERS на demoscene.ru/forum)

Пятиминутка мета: в этом тексте вам, котятки, предстоит прочитать о том, как потратить свое время совершенно неэффективно с точки зрения отношения размера полученного продукта к потраченным времени и усилиям.
Предположим, что мы хотим сделать что-нибудь эдакое, например, интру размером до 4кб, но мы нищеброды, и у нас нет денег на виндовс и видеокарту с шейдерами, поддерживающими ветвления. Или мы просто не хотим брать стандартный набор из apack/crinkler/sonant/4klang/боже-что-там-еще-есть, делать очередную «смотрите все! я тоже умею рэймарчинг дистанс филдс!» и теряться среди десятков-сотен таких же. Ну или же мы просто любим выпендриваться как попало в надежде, что девочки на нас наконец-то обратят внимание.

В общем, не важно. Пусть у нас просто есть какой-нибудь линукс со слабой видеокартой и вся юность впереди. Попробуем со всем этим теперь создать запускаемый файл размером не более, скажем, 1024 байт, который при запуске умудрялся бы каким-нибудь образом создавать и показывать пользователю что-нибудь (эдакое).

Захотел я однажды вычислить квадратный корень с помощью нормальных алгоритмов Маркова (НАМ).

Кратко о НАМ:

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

Итак, вроде бы все просто? Однако, как писать программы на НАМ?
Для себя я сделал примерно такой план:

• Пытаемся написать обычный алгоритм использующий только строки
• Следим за тем, чтобы последние замены не пересекались с первыми
• Переворачиваем алгоритм и записываем с конца к началу

Итак, вернемся к вычислению квадратного корня. Мы будем использовать «детский» метод (он же арифметический), который основывается на том простом факте, что квадрат числа — это сумма нечетных чисел от 1 до 2n-1:

• 1 = 1² = 1
• 1 + 3 = 2² = 4
• 1 + 3 + 5 = 3² = 9

Планкалкюль (Plankalkül) — первый в мире язык программирования высокого уровня, разработанный немецким инженером Конрадом Цузе между
1942 и 1946 годами для его компьютера «Z4» (компьютер на снимке ниже, фото взято из «Википедии»).


Шла Вторая Мировая Война, Цузе работал в отрыве от учёных других стран, совершенно самостоятельно. За это время он создал не только язык программирования,
но и написал на нём 49 страниц программ для оценки шахматных позиций. Полностью его работа была опубликована много позже, в 1972.

Рискну рассказать об этом языке программирования, в качестве археологического изыскания. Тем более, что на русском языке об этом языке сказано очень мало.

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

Каждый блинчик в меню Теремка — всего лишь набор из примерно 8ми ингредиентов. С такой простой периодической таблицей элементов компания заработала 1.9 млрд долларов в прошлом году (нет, не Теремок, а всё-таки Taco Bell).
Чем больше я программирую и проектирую системы, тем больше я понимаю, что в множестве случаев можно достигнуть желаемого результата банально сочетая базовый набор инструментов, данный нам Unix. В конце концов, функциональность — это ценность, а код — это задолженность. Это утверждение обратно абсурднму тренду DevOps (разработчико-админов), исходя из которого системные администраторы начинают писать юнит-тесты и прочие вещи, чтобы помочь разработчикам, и гласит что программирование в стиле Теремка это разработчики, которые знают достаточно об администрировании (и Unix в целом) так, что они не изобретают велосипед, и приходят к простым и масштабируемым решениям.

Вот конкретный пример: представьте, вам нужно скачать и записать на диск миллионы веб-страниц для дальнейшей обработки. Как это сделать? Детки-крутышки скажут, что нужно написать распределённый паук на Clojure и запустить на EC2, коммуницируя с помощью SQS или 0MQ.

В процессе работы с XenServer можно менять его конфигурацию разными способами.
Начиная от графической утилиты XenCenter и консольной команды xe заканчивая прямым вмешательством в XML конфиг.
Вот о последнем и хотелось бы с вами поговорить.

Далеко не все желаемые действия можно произвести штатными утилитами. Но меняя конфигурацию напрямую, можно сделать все.
Проанализировав содержимое файла /var/xapi/state.db вы сможете вносить даже изменения, не предусмотренные производителем или лицензией.

Введение

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

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

HTA-приложения уже описывались на хабре. Теперь же рассмотрим конкретный пример использования технологии в мирных целях.

Для чего?

Иногда хочется сделать красивую открытку, но при этом не заморачиваться с FLASH, Silverlight и т.п. А ведь зная только HTML и немного JavaScript можно сделать превосходные открытки в виде приложения одним файлом! Тот кто пролистает статью не вчитавшись может отметить что это не совсем просто. Но сделав один раз каркас (который я предоставляю в конце статьи на суд и свободное использование), вы будете легко и быстро делать новые и новые открытки. И даже вполне можно автоматизировать процесс создания персональных интерактивных открыток.

IOCCC возвращается! Знаменитый конкурс на самый запутанный код призван «проверять компиляторы на стресс, демонстрировать тонкости языка программирования Си и важность соблюдения стиля программирования (делая обратное)».

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

Международный конкурс на самый запутанный код проходил ежегодно с 1984 года, но с 2006-го мероприятие удалось организовать впервые.

Сегодня 11 ноября 2011 года; в формате DD.MM.YY получается исключительно красивая бинарная запись (последняя, кстати, за следующие 88 лет — до 1 января 2100). Это замечательный повод объявить этот день Nerd New Year, с каковым я вас и поздравляю.


Хотя стоп, поздравление с таким днем в plaintext — это нонсенс. Я уже писала о необычных поздравлениях с днем программиста (2010, 2011), но здесь нужно что-то особенное… Лично у меня термин nerd ассоциируется с чем-нибудь бинарным; как насчет поздравлений, основанных на 0 и 1?

Spoon

Начнем с классики. Brainfuck — язык на все случаи жизни; и бинарный диалект у него тоже есть. В Spoon команды BF заменяются на последовательности нулей и единиц, составляющие префиксно-свободный код, так что их даже не нужно разделять пробелами. Следующий код на BF, выводящий «Happy Nerd New Year!»,

++++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++>+++++++++>++++++++++>+++++++++++>+++++++++++
+>+++++++++++++<<<<<<<<<<<<<-]>>>>>>>>--------.>>---.>>--------..>---------.<<<<<<<<<--------.>>>>++
++++.>>>---------.>++.<-.<<<<<<<.>>>>.>>>+.>+++++.<<<<<<<<.>>>>>-.>>.<.>>-----.<<<<<<<<+.

эквивалентен коду на Spoon

1111111111001000101010110101110101111010111110101111110101111111010111111110101111111110101111111111
0101111111111101011111111111101011111111111110110110110110110110110110110110110110110000011010010010
0100100100100100000000000000000000000000010100100100000000000010100100100000000000000000000000000010
1000101001000000000000000000000000000000101001101101101101101101101101100000000000000000000000000101
0010010010010111111001010010010010000000000000000000000000000001010010110010100110000010100110110110
1101101101100101001001001001000101001001001010010100101111100101001101101101101101101101100101001001
00100100100000010100100100010100110010100100100000000000000000010100110110110110110110110111001010

но, согласитесь, последний выглядит гораздо бинарнее.