January 18, 2012
Как-то, почти 3 года назад, я уже писал небольшой пост про эзотерические языки программирования.
А на днях наткнулся на прекрасное — спецальный wiki-проект Esolangs.org, посвященный этой теме.
Там собранно примерно 700 разных языков и среди них много интересного.
Вот что порадовало лично меня:
Entropy от Danil Temkin
Язык, в котором все данные (включая символы строк) хранятся как float-ы, и, по мере обращения к ним, они понемногу эм… портятся.
Результат работы классической программы-примера про 99 бутылок пива выглядит примерно так:
99 bottles of beer on the wall, 99 bottles of beer.
Take one doym, pass it around, 98.14841 bottles of beer on the wall.
98.14841 bottles of beer on the wall, 98.14841 bottles of beer.
Takd one doym, pass it around, 97.14841 bottles of beer on the wall.
97.14841 bottles of beer on the wanl, 97.14841 bottles of!beer.
Takd one doym, pasr it around, 96.14841 bottles of bber on the wall.
…
73.73677 bnqtgft▼oe bjeq po▼she wbnl)”73.73677!gotsheh of!bees-
Uane ome fowo,!oasr kt aqound,%72.73677 `ourles oh edeq!pn she▼waml.
…
1.998256▼antseev▼nf▲begp↑pr↔the wanl(”1.998256″lrxtieh of!ddfs/♂S_ph←ore”ejxr3″m _xo!jr▬bqozmc- 1.096296 `luoldu pf ecgm▼pv!sgd▼wamn- 0.9982563▼antseev▼ng▼beg p↑ps↔the wanl(”0.9982563″lrxtieh of!ddfs/♂S_ph←ore”ejxr3″m_xo!jr▬bqozmc-
no more bottles og beer on the wall.
А в посте “Drunk-Eliza” автор приводит пример общения с Элизой, написанной на этом языке.
2DP от iconmaster
Если мне не изменяет память, это — один в один язык, который мы с Гевором и Горынычем придумывали для нашей двумерной версии REDCODE пятнадцать лет назад. Хорошо проработаны все операции, прямо хоть сейчас садись и пиши компилятор (которого, кстати, пока нет).
Petrovich от David Morgan-Mar
Язык программирования “Петрович” назван в честь академика Ивана Павлова (того, который издевался над собаками).
Исполнение программы построенно в форме коммуникации с интерпретатором-Петровичем, при этом в языке есть всего четыре операции:
* “сделай что-нибудь”
* “сделай что-нибудь с файлом <имя файла>” (единственная операция с параметром)
* “похвалить Петровича”
* “наказать Петровича”
Пример работы с Петровичем:
Petrovich> do something with HalleBerry001.jpg
file deleted
Petrovich> punish
Petrovich> do something with HalleBerry002.jpg
searching web for similar images…
downloading…
Petrovich> reward
Petrovich>
Идея языка состоит в том, что за несколько небольших сеансов можно научить Петровича делать именно то, чего вам хочется. Автор также предлагает идею интеграции интерпретатора с интерфейсом ОС MS Windows.
Прочее
Из других языков мне приглянулись квантовый brainfuck, Network Headache (где все программы, работающие с одним сервером имеют общие переменные), Spiral (с, вы не поверите, спиральной траекторией исполнения кода) и просто крутой Anemone.
Filed under: Почитать |
Comments (0)
January 16, 2012
Товарищ Gevor подкинул ссылку на очередной интересный железячный проект — Raspberry Pi.
В двух словах, это — полноценный ARM-компьютер размером с кредитку. 700МГц ARM11, до 256Mb памяти, порты USB2.0, microUSB, SD slot, ethernet, audio, HDMI и т.п.. ОС по умолчанию — Linux (Debian/Fedora/ArchLinux). Питание, wifi, клава, мышь — через USB-хаб. Весит 45 грамм. Ожидаемая цена в такой комплектации — 35$. В продаже ожидаются чуть ли не к февралю 2012.
Происхождение проекта тоже интересно: группа преподавателей Кембриджа затеяла его, чтобы поднять заметно, по их словам, снижающийся уровень технической грамотности учащихся. Среди прочих участников проекта затесался некто Дэвид Брэбен — один из двух авторов игры Elite.
Filed under: Почитать |
Comments (0)
December 24, 2011
Примерно с середины лета мы с товарищем gevor-ом неторопливо проходим по переписке Zork-ов, начиная с первого. На данный момент мы заканчиваем последнюю часть первой трилогии (я уже прошёл, Gevor — почти прошёл ;).
По этой причине приглашаются желающие присоединиться к данному процессу — начиная с Enchanter-а (первой игры второй трилогии).
Правила кооперации простые:
* требуется хотя бы базовой опыт в таких играх.
* требуется некоторая сила воли, т.к. это действительно непросто и тянется продолжительное время.
* мы принципиально не пользуемся солюшенами (но внимательно читаем официальные мануалы).
* в переписке мы не спойлерим друг другу решения головоломок, но тизеры и легкие подсказки разрешаются.
* если человек наглухо застрял и явным образом просит подсказать — только тогда разрешаются спойлеры.
Сам Enchanter, 1983 года выпуска, нынче найти не очень просто, ищите на абандонвейрах, например, тут. В архиве будет досовская версия, нужно взять файлик enchante.dat из папки data и переименовать его в enchante.z5, после чего можно скармливать любому современному интерпретатору (я пользуюсь горгульей).
Желающие присоединиться, пишите в личку — altsoph (на) gmail.com. Буде надо, подниму форум, а пока по почте.
PS. “Слово винтаж даже приблизительно не может описать наши планы” (с) Шелдон Купер о Zork-е (s2e20)
Filed under: Почитать |
Comments (0)
December 20, 2011
Давненько я не писал, а случилось так потому, что в свободное от работы время я занимаюсь различной бессмысленной, но интересной фигнёй. Ну и по мере того, как фигню буду заканчивать, я постараюсь понавыкладывать разных постов по мотивам.
Вот, например, намедни ломали мы китайскую капчу.
Предвосхищая вопросы, сразу отмечу три факта:
- на всё про всё было потрачено 3 или 4 вечера, не считая разметки капч, которая занимала по 5 минут в день в течение 2-3 недель,
- нет, я не ломаю капчу на заказ и не планирую этим заниматься в будущем 
- целей никаких не преследовалось, это было for fun.
А дело было так:
Пришел ко мне как-то товарищ s0me0ne (с которым мы как-то раз делали 3d-ландшафты соли под микроскопом) и жалуется: я, говорит, постоянно что-то у наших заморских братьев с доставкой заказываю, всё время несколько заказов висят в процессинге. Ну и написал скрипт для мониторинга статусов заказов, делов то. Но с одной китайской службой промашка вышла — там, чтобы узнать статус, надо капчу решить. И непростую, а настолько суровую, что я даже глазами её не всегда разбираю:
Мне любопытно стало, и решил я её поломать.
О том и рассказ.
0. Дискляймер
Я, натурально, ненастоящий сварщик. Раньше капч я не ломал, да и в будущем не планирую. Некоторые навыки в ML и ImageProcessing, вообще говоря, у меня имеются, но скорее теоретический багаж, нежели жизненный опыт. Посему, я явно прошелся по нескольким классическим граблям, и результат вышел не слишком оптимальным, но зато вполне рабочим, чего мне в данном проекте вполне достаточно. В конце поста, однако, я постараюсь какие-то мысли в формате работы над ошибками написать, на тот случай, если кому-то понадобится.
И, да, кода я не выложу. Не потому, что жадный, а потому что код так себе по качеству, а алгоритмы я всё равно все опишу словами.
1. Знакомство с ChiCa
После первого приступа естественного изумления удалось сформулировать следующие впечатления.
Плюсы:
- Число символов постоянно.
- Фоновый градиент фиксирован.
- Положение букв по вертикали более-менее стабильно.
- Шрифт один и тот же.
Минусы:
- Добавлен мелкий шум (вроде, не страшный)
- Букв в алфавите около сорока (английские буквы + цифры + символы доллара, собачки и т.п.)
- Положение букв по горизонтали колбасит страшно. В частности, нередки случаи когда буквы сильно перекрываются.
- Буквам рэндомно меняется кегль, болд, италик.
2. Базовая чистка
Первым делом решил я капчу почистить от фонового градиента и шума.
Для извлечения градиента оказалось достаточным заметить, что буквы в основном написаны в grayscale-палитре, а фон существенно разноцветный. Соответственно, качаем сотню капч и усредняем цвет каждой точки по всем сэмплам, где каналы достаточно различаются между собой. Получаем вот такой вот эталонный градиент:
дальше картинки буду зумить
Имея такую радость, несложно её вычесть, дабы получить что-то вроде:
Ну и цвет нам совершенно не нужен больше. А кроме того, для дальнейших плясок нам пригодится две картинки — контрастная ч/б-версия и серая с полутонами (не важно, черным по белому, или наоборот):
По первой мы будем определять границы букв, а саму букву в конце будем угадывать по более информативной картинке с полутонами. Контраст, если что, я делал по на глаз подобранной константе в 160.
3. Вертикальная сегментация
Поскольку буквы у нас хоть и немного (и к счастью, все вместе), но прыгают по вертикали, неплохо бы определить границы интересной нам области сверху и снизу. Для этого достаточно построить гистограмму построчной плотности — посчитать, сколько в какой строке точек на нашей ч/б-версии картинки:
я буду менять картинки периодически, чтобы не скучно было
Поскольку дырявых на просвет по горизонтали букв в нашем алфавите нет, то это надёжный способ выявить нужную нам область:
Порог можно было бы взять и константым, но я почему-то воткнул адапативный, равный половине средней плотности линии.
4. Горизонтальная сегментация
Тут начинаются песни и пляски с бубном, ибо китайцам всё равно, налезли буквы друг на друга, или нет; и даже в случаях, когда просвет между буквами имеется, он не обязательно строго вертикальный (т.к. буквы бывают написаны италиком), например:
Поэтому, пришлось вспомнить дедушку Брезенхэма и пробивать каждую вертикаль несколькими линиями под разными углами (я проверял 4 угла с шагом dx в 1 пиксель, исходя из максимального наклона италика). Опять-таки, считаем плотность, но на самом деле нам интересно только, нулевая она или нет. Ну и, конечно, плотность мы смотрим по вертикали уже только в пределах зоны, ограниченной желтыми линиями, т.е. там где буквы живут.
Получаем местами вполне неплохой себе результат:
Но бывают и упячки разного рода:
Визуальный анализ упячек позволил придумать следующий набор правил:
- одиночные (изолированные с обоих сторон) красные точки — убираем, т.к. это скорее-всего шум,
- скользящим окном в 5 точек ищем случаи вида Х0ХХ00, доставляем точку, преобразуя их в ХХХХ00
- и, симметрично, 00ХХ0Х в 00ХХХХ.
В результате выходит значительно лучше:
Если же всё-таки сегментов оказалось более 4, то сортируем их по размеру и берем 4 самых больших.
Что же, однако, делать, если сегментов оказалось меньше 4? Есть некоторые шансы, что сегменты у нас склеились или сразу, или в процессе работы предыдущей эвристики:
Этому горю несложно помочь, если внимательно рассмотреть возможные случаи:
- У нас на выходе 3 сегмента — значит, слиплись какие-то 2 буквы. Режем самый большой из имеющихся сегмент пополам.
- У нас на выходе 2 сегмента — если один из них сильно (более чем в 2 раза) второго, значит, считаем, что в него слиплись 3 буквы и пилим его на 3 части. Иначе — каждый из 2 сегментов пилим пополам.
- У нас на выходе 1 сегмент — значит, нам повезло, и все 4 буквы склеились в 1. Делим наш сегмент на 4 равные части, т.к. больше нам тут поделать нечего.
Ну и потом, когда мы по сегментам вычленяем символы, делаем нахлёсты, т.к. буквы у нас всё-таки бывают разной ширины.
5. Обучающая выборка
По причине того, что каждая буква в данной капче имеет больше десятка различных возможных написаний (с учётом болда, италика и кегля) решено было стрелять из перспетрона. Благо у меня как раз осталась его реализация под Octave после прохождения стенфордского ML-курса. Но персептрону нужно обучаться, и тут пришлось поработать неграм (в лице меня и s0me0ne).
Я наваял несложный десятистрочный веб-скриптик, выкачивающий chica пачками и сохраняющий результаты разметки. Выглядело это примерно так:
Мы решали капчи (по паре-тройке десятков в день каждый) недели три. С учётом разнообразия символов было решено набрать 1000 размеченных капч (т.е. 4000 сэмплов), попробовать на них обучиться, а дальше действовать по обстоятельствам.
И тут… по всем законам жанра, в тот день, когда мы набрали 1000 сэмплов, КИТАЙЦЫ ПОМЕНЯЛИ КАПЧУ.
Хорошие новости:
- все буквы стали одного кегля,
- цифры и спецсимволы убрали,
- наложений букв стало, кажется, поменьше,
- градиент и шум остались прежними.
Плохие новости:
- все сэмплы пошли псу под хвост.
Сокращая историю, скажу, что мы не сдались и набрали базу заново (благо под новую версию сэмплов потребовалось гораздо меньше).
6. Персептрон
Дальше всё было несложно. Я порезал сэмплы описанным выше алгоритмом на “буквы”, снабдил их метками, которые мы расставили вручную, когда решали капчи, и выгрузил всю эту радость в Octave. Там я обучил стандартный персептрон с одним скрытым слоем — на входном слое было 195 нейронов (по числу пикселей в окне буквы 13х15). На скрытом я от балды поставил 30 нейронов, на выходном вышло 26, по числу распозноваемых букв. Обучение заняло минут 10.
Точность определения 1 символа на тестовой выборке получилась чуть больше 90% — т.е. если считать что точность определения 4 букв в капче независима (что не совсем правда, т.к. иногда гадит сегментация, а значит, портятся сразу несколько соседних букв), то вероятность корректного решения целой капчи вышла около 70%. На практике оценка подтвердилась.
Из обученного персептрона я выгрузил две матрицы параметров и зашил их в php-код. Кодить матричную арифметику с нуля самому было лень, PEAR я не люблю, в итоге я дернул пару полезных функций, кажется, отсюда. Собрал всё в кучку и наваял несложный единый скрипт. Работает он примерно так:
7. Мысли напоследок
Тут я хочу просто перечислить тонкие места и очевидные допущенные промашки:
* Начать сбор обучающей выборки можно было еще до того, как садиться за сегментацию — это хорошо распараллеливаемые процессы.
* После смены китайцами капчи нейросеть для распознавания символов в данном случае явно была оверкиллом. По идее, поиска по маске со словарём из двух масок (обычная и италик) на каждую букву должно было хватить. Просто я уже как-то настроился из персептрона пошмалять
* По результатам кажется, что сегментация на символы, может быть гораздо более эффективно и универсально решена той же нейросетью. А так, это, конечно, заход солнца вручную получился 
* Для того, чтобы не решать тысячи капч руками, по уму надо было подобрать шрифт (скажем, с помощью этого или этого сервисов), потом воспроизвести генератор и нагенерировать нужное количество сэмплов.
Вот такая история.
Filed under: Почитать |
Comments (0)
