Курочка
"Одному моему знакомому очень не нравилась сказка "Курочка ряба". Он не понимал ее. Поступки героев этой сказки казались ему дикими выходками. Рассуждал он примерно так.
"Жили себе дед да баба. Была у них курочка ряба" — это нормально: деды и бабы действительно живут на свете, и у них обычно водится какая–нибудь живность. "Снесла курочка яичко — яичко не простое, а золотое" — что же, предположим. Примем это как допущение… А вот дальше… Дальше начинаются совершенно не мотивированные действия героев. Посудите сами: "Дед бил, бил — не разбил". Зачем, спрашивается, он это яичко бил, если понял, что оно золотое? Золотые яйца не бьются — каждому ясно. "Баба била, била — не разбила" — экая глупая баба! Мало ей, что яйцо золотое, так ее и печальный пример деда ни в чем не убедил… Идем дальше: "Мышка бежала, хвостиком махнула — яичко упало и разбилось". Как же оно, интересно, разбилось, когда золотые яйца (см. выше) не бьются? Ладно, примем это как второе допущение. Но что ж потом? А потом — "Плачет дед". С чего бы это? Ведь за минуту до разбиения яйца мышью сам он стремился к тому же результату! Очень непоследовательный получается дед… Или этот дед настолько мелочен, что ему важно, кто именно разбил яйцо? Непонятно. "Плачет баба" — опять же глупая баба! Механически повторяет все, что делает дед. "А курочка кудахчет: "Не плачь, дед…" — Стоп! Если курочка ряба умеет говорить, то почему же раньше она молча следила за бессмысленными поступками деда и бабы, почему не возмутилась, не объяснила ситуации? Подозрительная курица… Так вот, она говорит: "Не плачь, дед, не плачь, баба, снесу я вам яичко другое — не золотое, а простое!" Тоже мне, утешение: плакали–то они о золотом!.. И вообще — будь яичко с самого начала простым, никакой трагедии не произошло бы: дед благополучно разбил бы его с первого раза без посторонней помощи. И даже баба бы разбила. Но на этом сказка кончается. Что ж это за сказка такая? " (с)

(1 Comment |Comment on this)

Что делать на Новый год
Мне не спалось и я написал угадатор подарков =)
Идея в том, что внутри виджета спрятано слово, каждая буква которого находится на кнопке. При нажатии на кнопку буква проявляется. Цель - угадать название подарка, открыв наименьшее количество букв =)

С ключевым словом "present" это выглядит так:


Ключевое слово задается при запуске программы:
usage example: present "some key phrase"

Скачать код (он кросплатформенный) можно отсюда

Сборка:
cd <path to present>
cmake .
make

Запуск:
bin/present "some text"

(Comment on this)

Для тех, кто читал мои предыдущие посты про кодинг
Я тут сейчас посмотрел на свой плюсовый код полугодовой давности, и даже мне самому стало страшно. Если использовать что-то из них, то надо быть очень осторожным!

P.S. Под впечатлениям от опасности я даже немного порефакторил свою двухгодовалую дипломную поделку

(Comment on this)

Кластеризация статей
Достаточно долго получалось обходиться твиттером, но, вдруг, оказалось, что то, что я хочу написать сейчас, туда явно не поместится.

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

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

Так как в наличии у меня имелось лишь пара вечеров, то я решил не писать html-парсер и не возиться с кодировками, а взять набор подготовленных (т.е. таких, где тело статьи копировано в отдельный файл) статей на английском языке. Всего их 10 штук и лежат они тут.

После того, как мой кластеризатор скачивает и анализирует их, получается следующий результат:

claster #0
http://share.auditory.ru/2010/Vasily.Matveev/articles/syria3.txt
claster #1
http://share.auditory.ru/2010/Vasily.Matveev/articles/wedding3.txt
http://share.auditory.ru/2010/Vasily.Matveev/articles/wedding.txt
http://share.auditory.ru/2010/Vasily.Matveev/articles/wedding2.txt
claster #2
http://share.auditory.ru/2010/Vasily.Matveev/articles/tornado.txt
claster #3
http://share.auditory.ru/2010/Vasily.Matveev/articles/syria.txt
http://share.auditory.ru/2010/Vasily.Matveev/articles/syria2.txt
claster #4
http://share.auditory.ru/2010/Vasily.Matveev/articles/syria4.txt
claster #5
http://share.auditory.ru/2010/Vasily.Matveev/articles/japan.txt
http://share.auditory.ru/2010/Vasily.Matveev/articles/japan2.txt

В целом приемлимо: статьи о свадьбе в семье британских монархов попали в 1 кластер, новости о Японии тоже. Единственная статья о торнадо в США тоже попала в свой кластер, и лишь 4 новости о Сирии раскидало на 3 штуки.

Самое интересное во всем этом - подбирать коэффициенты и улучшать кластеризацию разными сторонними алгоритмами. К примеру, изначально слова Cat и cats - совсем разные. Но если привести их к одному регистру и воспользоваться, скажем, рассчетом расстояния Хемминга, то качество кластеризации существенно возрастает.

Интересно, повысится ли точность, если вместо расстояния Хэмминга взять расстояние Левенштейна?
И точно повысится, если изымать из текста стоп-стова: предлоги, союзы, артикли, но я не успел пока это сделать, попробую позже.

Кстати! При рассчете расстояния между 2мя статьями, я сначала пытался воспользовать коэффициентом Пирсона, реализовал его методом, описанной в книге "Программируем коллективный разум", но он, иногда выдает отрицательные значения. Не понимаю почему и бага не нахожу. Если кто-то будет смотреть мой код, гляньте на всякий случай) В итоге воспользовался своим методом рассчета, он чем-то похож на эвклидово расстояние, и тоже необесценивающий =(

Сам код залит в свн тут. Для сборки понадобится библиотека curl.

(3 Comments |Comment on this)

Фракталы - это просто
Фрактал — это бесконечно самоподобная геометрическая фигура, каждый фрагмент которой повторяется при уменьшении масштаба. Пожалуй, самый известный фрактал - множество Мандельброта. Выглядит он примерно так:

Давайте запрограммируем фрактал так, чтобы его можно было удобно рассматривать: приближать, отдалять и перемещать. Плюс можно добавить немного анимации. В итоге получим такуие картинки:




( Как же это сделать?Collapse )

(Comment on this)

Високосный взрыв мозга
Мне тут понадобилось посчитать номер сегодняшнего дня с момента началы нашей эры. Думаете просто? Это полный взрыв мозга. Оказалось, что в течение времен никто так и не мог толком договориться про високосные годы. А вы знаете как они считаются?

Продолжительность тропического года (время между двумя весенними равноденствиями) составляет 365 суток 5 часов 48 минут 46 секунд. Различие в продолжительности тропического года и среднего юлианского календарного года (365,25 суток) составляет 11 минут 14 секунд. Из этих 11 минут и 14 секунд приблизительно за 128 лет складываются одни сутки.

По истечении столетий было замечено смещение дня весеннего равноденствия, с которым связаны церковные праздники. К XVI веку весеннее равноденствие наступало примерно на 10 суток раньше 21 марта, используемого для определения дня Пасхи.

Чтобы компенсировать накопившуюся ошибку и избежать подобного смещения в будущем, в 1582 году римский папа Григорий XIII провёл реформу календаря. Чтобы средний календарный год лучше соответствовал солнечному, было решено изменить правило високосных лет. По-прежнему високосным оставался год, номер которого кратен четырём, но исключение делалось для тех, которые были кратны 100. Отныне такие годы были високосными только тогда, когда делились ещё и на 400.

Иными словами, год является високосным, если он кратен 4 и при этом не кратен 100, либо кратен 400. Год не является високосным, если он не кратен 4, либо кратен 100 и не кратен 400.

Последние годы столетий, оканчивающиеся на два нуля, в трёх случаях из четырёх не являются високосными. Так, годы 1700, 1800 и 1900 не были високосными, так как они кратны 100 и не кратны 400. Год 2000 — високосный, так как он кратен 400. 2100, 2200 и 2300 — невисокосные. В високосные годы вводится дополнительный день — 29 февраля.

После нескольких мозговых взрывов, я вывел-таки формулу:

номер_дня = номер_дня_в_тек_году + (год-1)*365 + (год-1)/4 - (год-1)/100 + (год-1)/400

Уф.

(Comment on this)

Олимпиадная задачка по программированию
Наткнулся на интересную задачку и решил размять мозг =)
Вот условие:

В Новую Зеландию прибыла технология сбора мусора Kerbside. Пять мусорных корзин разных цветов: красный (red), оранжевый (orange), желтый (yellow), зеленый(green) и синий (blue), в которые определены 5 видов отходов: пластиковые отходы (Plastic), стеклянные (Glass), алюминиевые (Aluminium), стальные(Steel) и бумажные (Newspaper). К сожалению, никакой координации между городами не было, поэтому каждый город поставил в соответствие цветным корзинам произвольный вид отходов. Теперь, когда правительство смогло решить все маловажные задачи (вроде реорганизации здравоохранения, соц. обеспечения и образования), оно решило заняться другими проблемами. Министр охраны окружающей среды представил в парламент документ о регулировании соответствия видов отходов цветными корзинами, но для этого ему необходимо выбрать собственное распределение отходов по цветам. Будучи сторонником демократии, он исследовал все города, которые используют Kerbside. С помощью полученных данных он хочет выбрать город, чья схема соответствия видов отходов цветным корзинам (будучи распространенной по всей стране) вызовет наименьшее количество изменений. Размер города не имеет значения, согласно демократии: 1 город — 1 голос.

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

Входные данные: серия блоков. Каждый блок будет содержать несколько строк, выражающих распределение видов отходов по цветам, по 1 строке на каждый город. Городов может быть до 100. Каждый блок оканчивается строкой, начинающийся с символа «e». Конец входных данных ознаменуется строкой из одного символа "#".

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

Пример входящих данных:
r/P,o/G,y/S,g/A,b/N
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
e
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
r/P,o/G,y/S,g/A,b/N
ecclesiastical
#

Результат:
1
4

Я решил искать оптимальное решение через вычисление коэффициента корреляции Пирсона.
Под катом само решение

( Read more...Collapse )

(Comment on this)

Ubuntu на MacBook
Я тут попробовал поставить Убунту на свой Мак. Это был провал. То есть встать-то она встала. Но обнаружилась куча проблем.

1) Время работы от батарейки чудесным образом упала с 5 часов до двух
2) Ноут ужасно греется. Проблема решается заданием в конфигах числа оборотов куллера в минуту, но тогда он немного шумит. На Макоси все работает бесшумно.
3) Какие-то непонятные проблемы с отрисовкой страниц внутри Файрфокс. Там появляются непонятные артефакты.

Это то, что я успел заметить за полчаса. В общем грустно это. При том, что Каноникал уверяет, что на Маках все работает отлично. Учитывая, что модели довольно незначительно отличаются по железу, это выглядит как осознанная ложь.

Мне до сих пор непонятно, как решать проблему совмещения двух систем: удобной для жизни и удобной для работы. В Макоси есть куча нужного софта (и не надо говорить, что Гимп аналог Фотошопа), причем маковский софт очень умно проинтегрирован вдоль и поперек и зверско удобен. TimeMachine - это просто чудо вообще.

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

В общем, нет в мире совершенства. Видимо надо собирать себе 2й комп, ориентированный именно на кодинг и системные эксперименты.

(1 Comment |Comment on this)

Языки программирования и платформы
Давно наблюдается стремление разработчиков некоторых платформ иметь свой нативный язык программирования. В случае с ПК это разделение выглядит так:
-Linux (C/C++)
-OS X (Obj-C)
-Windows (C#)

Причем Apple и MS решения выглядят несколько искусственными. Но речь не об этом. Речь о том, что нативный для платформы язык получает дополнительные преференции: выскороуровневые апи, куча документации и прочее. Тот же Apple близок к тому, чтобы пропускать в свои магазинные приложений только софт, написанный на их sdk (для айфонов это уже так), следовательно на их языках.

Отсюда следует возникновение еще большей, чем раньше, дифференсации программистов по платформам. И, тк бОльшая часть серверов - Линуксы, то бОльшая часть Вин и Мак программистов по сути обречены на очень типовые разработки прикладного софта. В ТОПовых ИТ конторах (Google, FB, даже Яндекс) такие кадры как раз не нужны. В общем, программисты, подумайте, какого рода задачи вам было бы интересно заниматься в будущем.

P.S. Я решил, что мои твиты больше не буду дублироваться в ЖЖ, если интересно их читать - заходите в twitter.

(Comment on this)

My tweets

• Thu, 14:26: В МИЭМе возникла первая в России команда, целиком состоящая из лиц нетрадиционной сексуальной ориентации http://bit.ly/9OJZw1
• Thu, 16:19: RT @shurupov Про МИЭМ ;-) «Один из главных ИТ-вузов России хотела поглотить Финакадемия» — http://bit.ly/d8pNub
• Thu, 18:56: Несмотря на огромное количество упоминаний, поста Навального про Транснефть нет в ТОПе блогов Яндекса. Не такие уж они и независимые, видимо
• Fri, 11:00: Посмотрел 3ю серия ходячих мертвецов. До Лоста и Хауса не дотягивает, но в целом норм

(Comment on this)

My tweets

• Wed, 12:56: Президент обещал разобраться в ДТП на Ленинском. Виновными названы убитые женщины. Президент разобрался в смерти Магнитского.Убийц наградили
• Wed, 12:57: Теперь президент будет разбираться в нападении на Олега Кашина. =)
• Thu, 07:52: Глава ВВС России запретил "Русским витязям" выполнять фигуру высшего пилотажа "Кобра": "Самолеты у нас подержанные, им уже 20 лет". Мда...
• Thu, 11:01: Дописал для #XBMC модуль, собирающий курсы валют с сайта ЦБ.

(Comment on this)

My tweets

• Tue, 14:08: Я получил военный билет
• Tue, 17:03: Путин демонстративно наградил Транснефть. Это после всех доказательств воровства. Пилю, пилил и буду пилить, мол.
• Tue, 20:39: Подключил себе на мобильник анлимный интернет. Зверски удобная штука
• Wed, 10:02: Такими темпами я скоро перепишу пол-XBMC

(Comment on this)

My tweets

• Mon, 18:46: Во второй раз играл в FIFA 2011. На этот раз против Ромы Комкова. Команды те же ЦСКА - Локомотив. Я вновь победил! 1-0 гол Хонды
• Tue, 08:09: В военкомате
• Tue, 08:53: Адские очереди тут

(Comment on this)

My tweets

• Mon, 10:46: Я закончил разработку поддержки управления жестами с тачпада для #xbmc
• Mon, 11:12: Как пилят в компании #Транснефть - http://navalny.livejournal.com/526563.html

(Comment on this)

My tweets

• Fri, 16:44: В кружке
• Fri, 20:35: Общаться с людьми, от которых только неприятности и головная боль - неправильно
• Sat, 08:40: Первый раз за неделю выспался

(Comment on this)

My tweets

• Thu, 17:14: Я знал, что с нашим Хантом что-то не так http://bit.ly/a44atz

(Comment on this)

My tweets

• Wed, 17:42: Новозеландский программист создал бота-потребителя http://bit.ly/b7MHXj
• Wed, 18:17: Есть проблема в кодинге крутых open-source штук - все уже сделано или есть в транках. А сделать что-то совсем новое - надо быть адским гуру
• Thu, 08:29: LCD дисплей привинчен к нашему HTPC http://bit.ly/cdRTeT

(Comment on this)

My tweets

• Tue, 19:20: Даже 10 мбит не хватает, чтобы нормально смотреть ютуб

(Comment on this)

My tweets

• Mon, 20:04: Голосуем за Дзагоева в голосовании за звание лучшего молодого игрока года по версии Tuttosport http://bit.ly/cJYU2f
• Tue, 08:47: Дзагоев вышел на первое место в рейтинге на приз лучшему игроку мира до 21 года. Свои голоса за россиянина отдали 34,3 % участников опроса.

(Comment on this)

My tweets

• Mon, 09:54: Посмотрел "Социальную сеть". Рекомендую
• Mon, 11:18: Мой вклад в XBMC - выпадающий при наведении на дату календарик http://image.auditory.ru/images/8693Screenshot-1.png

(Comment on this)