суббота, 31 декабря 2011 г.

С Новым 2012 годом!

Друзья! Вот и подходит к концу 2011 год. В этом году, возможно, не все у нас получалось так, как нам бы хотелось. Что-то мы успели сделать, а что-то так и осталось незавершенным.
Наступает новый 2012 год - год Дракона. Хочется пожелать всем вам, чтобы в новом году вам сопутствовала удача, пожелать вам крепкого здоровья и успехов во всех ваших благих начинаниях. С Новым 2012 годом!

вторник, 20 декабря 2011 г.

Задача о движущихся точках и её решение на языке Haskell

В блогах на сайте free-lance.ru не так давно один человек разместил задачу, условие которой в чуть облагороженном (мной :) виде звучит следующим образом:
===
Имеется N вершин, между ними есть ребра (длину ребер мы задаем сами целым числом). По ребрам ездят точки, которые могут ехать в обе стороны. При нахождении двух точек в одной вершине происходит столкновение. Соответственно, если точки едут по одному ребру навстречу друг другу, тоже произойдет столкновение. Движение точек задано списком вершин, через которые они проходят. Скорости точек равны единице. При
достижении конечной вершины точка исчезает. По заданной конфигурации сети и точек
определить, будет ли столкновение.

===
Попробуем написать решение этой задачи на Haskell.

вторник, 6 декабря 2011 г.

Задача о составлении математических выражений на Хаскеле

В ЖЖ Романа Душкина не так давно был проведен конкурс на самое хорошее решение следующей задачи:
==
Даны числа 1, 5, 6 и 7. При помощи произвольного числа арифметических операций и
скобок необходимо составить такое математическое выражение из этих чисел, чтобы его
значение было равным 21. Данные числа можно использовать в выражении только по одному разу. Числа нельзя «склеивать» друг с другом (то есть из 1 и 5 получить 15).
==
Так как на конкурс я опоздал, да и решение у меня получилось наверняка не особо приятное :), опубликую его тут. Итак, в качестве языка выбираем Haskell.

пятница, 2 декабря 2011 г.

Старый советский фильм "Коммунист"

Недавно пересмотрел старый советский фильм "Коммунист", вышедший в 1957 году. Помню, что в детстве смотрел этот фильм несколько раз. Лет мне тогда было мало, и кульминационную сцену фильма, в которой убивают главного героя - коммуниста Василия Губанова - я вообще смотрел с закрытыми глазами.

Ну так вот. Пересмотрел этот фильм на днях. Смотрится на одном дыхании. Евгений Урбанский был действительно великим актером. Жаль, что он трагически погиб в достаточно молодом возрасте.

понедельник, 14 ноября 2011 г.

Интересное об отступах в Haskell

Недавно тут меня в комментах один человек спрашивал на тему ошибки, связанной с неправильными отступами в Haskell. Загуглив на эту тему, нашел кое-что интересное. Haskell нормально проглатывает символы табуляции в исходном коде, но интерпретирует их как пробельные строки длиной 8 символов. Так как у меня в редакторе выставлен размер "таба" в 4 пробельных символа, то это дает некоторые интересные эффекты.

Рассмотрим следующий пример бестолкового кода:

f x y =
    let g = 
        x + 1 
    in g + y

Если отступы внутри тела функции f были получены применением символов табуляции, никакого сообщения об ошибке синтаксиса мы не увидим. Хотя должны были бы, так как строка "x + 1" должна быть сдвинута минимум на 1 символ вправо относительно "g" в предыдущей строке кода. Но так как символы табуляции Хаскелем разворачиваются в строки
пробелов длины 8, у нас "x+1" "уедет" значительно правее, и исходник будет обработан корректно.

Если же отступы в том же исходном тексте были честно получены при помощи пробельных символов, то при попытке его запуска мы получим сообщение "possibly incorrect indentation".

То есть, визуально одинаковый исходный код (при определенных настройках редактора) может быть и ошибочным, и нет. В любом случае, следует быть аккуратным и осторожным :)

пятница, 30 сентября 2011 г.

Ужас PHP, летящий на крыльях ночи

Всех с наступающей ночью )

Только что чуть еще не добавил себе седых волос по причине программирования на PHP. В общем, ситуация. Имеется большой по размеру PHP-файл, где-то в середине которого присутствует регулярка вот такого вида:
===
...'#(<(?:img|a).*?(?:src|href)\s*=\s*["\']\s*)(.*?)(\s*["\'].*?>)#i'...
===
Всё нормально работает. Я потихоньку себе что-то там удаляю, добавляю комментарии, провожу изменения в коде и на каком-то этапе замечаю (вдруг!), что мой скрипт перестает выполняться вообще. PHP сообщает, что, мол, присутствует "unexpected $end" и указывает куда-то на последнюю строку скрипта.

В общем, методом проб и ошибок нашел я то место, из-за которого весь сыр-бор приключился. Разумеется, тут не обошлось без регулярки выше (а иначе зачем бы я её приводил, верно ? :) В общем, когда я эту строку закомментировал вот так:
==
// ... '#(<(?:img|a).*?(?:src|href)\s*=\s*["\']\s*)(.*?)(\s*["\'].*?>)#i'...
==
, то произошло страшное следующее. Как я понимаю, интепретатор PHP попытался проигнорировать всё, что дальше '//', включая кавычки, и не воспринимая сам литерал регулярки как строчную переменную, которую не нужно парсить. И в этой строке он обнаруживает последовательность "?>", которая говорит ему, что код PHP закончился. Ну и понятно, что это послужило причиной того, что его перекосило, если можно так сказать.
В общем, закомментировал я эту строку через /* и */, и всё заработало.
Но было весело )

вторник, 13 сентября 2011 г.

Решение задачи о подсчете количества подчисел числа, на которые оно делится без остатка

Снова на Хабре проскочила статья-конкурс, посвященная Дню Программиста, который отмечается сегодня (кстати, с праздником всех причастных к сему событию :) В статье приводится самая простая задача, собственное решение которой на Хаскеле я и хочу привести ниже.
Итак, условие задачи:
==
Напишите код, который находит количество подчисел числа n, на которые это число делится без остатка. Для числа n, подчисло — это такое число, запись которого является подстрокой записи числа n. К примеру, если n равняется 1938, то его подчислами будут являться: 1, 9, 3, 8, 19, 93, 38, 193 и 938. Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 19 и 38. Соответственно, результатом работы программы должно быть число 4. Если подчисла повторяются, каждое из них считается. Например, 101 делится без остатка на 1, 1 и 01, значит, ответ — 3.
==

Мое решение, не претендующее на какую-либо оптимальность:

вторник, 6 сентября 2011 г.

Решение головоломки с хабра на Haskell

На днях на хабре проскочила заметка с одной простой, но изящной головоломкой.
Суть вкратце такова. Имеется автомат с пятью барабанами, где каждый барабан может принимать значение одной из карточных мастей (то есть, всего 4 положения). Каждый барабан руками можно вращать только в одну сторону на один шаг, при этом автоматически также могут вращаться остальные 4 барабана. Матрица таких вращений-сдвигов представлена ниже:
===
     1  2  3  4  5
    --------------
1:  +1 -1 +1  0  0
2:  +1 +1  0  0 -1
3:   0 -1 +1 -1  0
4:  -1  0  0 +1 +1
5:   0  0 -1 +1 +1
===
То есть, например, при вращении барабана N1 на один шаг (примем это направление за положительное), барабан N2 автоматически будет повернут на 1 шаг в обратном направлении, барабан N3 - так же как и барабан N1 - будет повернут на 1 шаг вперед, а положения барабанов N4 и N5 не изменятся.

Задача в следующем. Имеется начальное положение всех барабанов - 0 2 0 3 1, то есть, первый барабан в положении 0, второй - в 2, третий - в 0 и т.д.
Требуется найти такую последовательность поворотов барабанов, чтобы в итоге их положения приняли значения 0 0 2 0 0. Мы эту задачу чуть усложним и будем искать не просто последовательность, а последовательность минимальной длины.

Для решения будем использовать Haskell.

понедельник, 29 августа 2011 г.

Особенности GET-запросов в IE6

Давеча чуть было не тронулся рассудком ) Написал на javascript с использованием jQuery некий простой фрагмент кода, который работал в Firefox 6, но категорически не работал в IE6. Собственно, вот рабочий пример:
$(document).ready(function(){
     alert(1);
     $.getJSON('/test.php', function(d) {
	alert(2);	
     });
 });
Так вот, первый алерт в IE6 срабатывает, а второй - нет, хотя файл test.php исправно лежит в корне сайта и честно выдает корректный json на выход. То есть, такое впечатление, что просто не срабатывает вызов getJSON(). Думал, уже поседею )
Короче, в чем суть. IE6 каким-то образом (в отличие от других браузеров) по дефолту кэширует такого рода запросы. Возможно, это и всем известная вещь, но как-то я её совсем упустил из вида. В общем, радикальный способ решения проблемы следующий: указать для всех ajax-запросов из jQuery отключение кэширования на стороне клиента, например, вот так:
$.ajaxSetup ({ cache: false});
После этого всё работает (вроде бы :).

ps. Важное дополнение. Для IE6 имеет также большое значение правильное указание кодировки для возвращаемых данных. В случае, если данные в JSON находятся в utf-8, то в test.php следует прописать нечто типа такого перед выводом самих данных:
header('Content-Type: text/html;charset=utf-8');

воскресенье, 31 июля 2011 г.

Решение еще некоторых задач на Haskell

Недавно на free-lance.ru в одном из заказов обнаружил вот такое тестовое задание на определение базовых навыков в области программирования:

1) Find the largest palindrome (a palindrome is a number that reads the same in either direction, e.g. 1221) formed by the product of two three-digit numbers.
{Correct answer: 906609}

2) Find the sum of the digits in the number 100! (i.e. 100 factorial)
{Correct answer: 648}

3) Given a list of pairs of numbers e.g. [(1,4), (2,5), (7,3), (4,6), (7,7)] find the longest sub-list that has the pairs sorted by the first entry in ascending order by the second in descending order, [(2,5), (7,3)].

пятница, 1 июля 2011 г.

Решение задачи J финальной части конкурса ACM ICPC 2011

Всем привет. Давно не брал я в руки шашек (в смысле, не писал ничего полезно-тематического). Сегодня мы с вами попробуем решить одну из задач, представленных в финальной части чемпионата мира по программированию среди студентов ACM ICPC 2011. С условиями задач вы можете ознакомиться здесь http://cm.baylor.edu/digital/icpc2011.pdf

Решать будем задачу J (problem J), потому как она мне сразу понравилась своей простотой )) В качестве языка программирования будем использовать Haskell (вообще, насколько я понял, на конкурсе принимались решения только на C++ или Java, но так как мы с вами в конкурсе не участвуем, позволим себе такую вольность).

понедельник, 9 мая 2011 г.

С Днем Победы!

Всем привет.
Давно вообще ничего не писал, но вот сегодня появился повод, святой, как минимум, для каждого жителя бывшего Советского Союза. Именно в этот день 66 лет назад наша страна одержала победу в Великой Отечественной войне.

От всей души поздравляю сегодня всех ветеранов, которых с каждым днем, к сожалению, остается всё меньше. Хочется пожелать вам здоровья, мирного неба над головой.
И низко вам поклониться до самой земли.

понедельник, 4 апреля 2011 г.

Фильм "Молодая Гвардия"

Посмотрел на днях художественный фильм "Молодая Гвардия", снятый в 1948 году. Вроде бы, когда-то смотрел его раньше, но то ли смотрел не очень внимательно, а скорее всего, просто в силу своего тогда юного возраста как-то не воспринимал его адекватно, что ли... В общем, тогда я не обратил на него внимания, к сожалению.

А недавно вот пересмотрел. Замечательный фильм. Кто не в курсе - фильм Сергея Герасимова по роману Александра Фадеева "Молодая Гвардия". Две серии смотрятся на одном дыхании. Отличная работа оператора (крупные планы в нужные моменты), музыка Дмитрия Шостаковича, отменная игра актеров - тут вообще удивительно, так как большая группа молодых актеров фильма на тот момент являлась студентами, но зато какими: Нонна Мордюкова, Вячеслав Тихонов, Георгий Юматов. Будущие звезды! Обратил внимание, что в роли Геннадия Почепцова снимался Евгений Моргунов. Также в фильме роль тетки Марины играет небезызвестная Клара Лучко. Ну а самое большое впечатление на меня произвела игра Владимира Иванова, исполняющего роль Олега Кошевого. По сути дела, эта роль сыграла с ним злую шутку, так как после съемок в этом фильме народ уже просто не воспринимал его в других ролях. Кроме того, с интересом узнал, что настоящая бабушка Олега Кошевого ходатайствовала за принятие в Коммунистическую Партию Владимира Иванова, как человека, который очень хорошо и правдоподобно исполнил роль её внука в фильме "Молодая Гвардия".

четверг, 17 марта 2011 г.

Firefox 4 и новые графические возможности

Тут в последнее время на хабре стали проскакивать тесты, в которых исследуются новые возможности HTML5. Ну и стало мне интересно, а как у меня с этим обстоит дело на Firefox 4 RC1 под Windows XP.

Запустил тест Canvas'а, и что я вижу ? Вижу, что производительность у меня ровно такая, какая характерна для Firefox третьей версии. Который, вроде бы, не имеет многих фич версии 4, позволяющих существовать более комфортно, если я правильно понимаю. Короче, на тесте FPS что-то в районе 30 максимум.

Загуглив, нашел (внезапно! :), что можно через about:support посмотреть текущее положение дел с настройками. Для блока "Графика" увидел, что Direct2D "заблокирован для вашего драйвера видеокарты. Попытайтесь обновить его до версии 257.21 или более новой". Материнка у меня на работе от Asus, видео встроенное на базе GeForce 8200.
Скачал свежие дрова под него (266.58_desktop_winxp_32bit_english_whql, то есть, версии 266.58), установил, снова полез в about:support. Теперь для Direct2D выводится скромное "false". Полез в about:config. Все настройки, касающиеся использования Direct2D включены... Загадки да и только.

Загуглив еще раз, выяснил, что этот самый Direct2D мало того, что доступен только начиная с Висты и дальше, так еще и для его использования в 4-ом Firefox-е нужна видеокарта с аппаратной поддержкой DirectX версии 10.

В общем, плюнул я на всё это дело и решил жить как и прежде )

воскресенье, 27 февраля 2011 г.

Сказ о том, как я пробовал собирать Ocaml'ом нативные виндовые экзешники

Итак. Имеется машина под управлением MS Windows XP SP3. Есть желание собирать native executables под эту платформу с помощью системы функционального программирования Ocaml.

Как следует из информации на сайте, существуют 2 базовых порта Окамла под Windows: один на основе MS Visual C++, другой - MinGW/Cygwin. Я поначалу использовал первый.
До тех пор, пока не заинтересовался генерацией нативных exe-файлов. А тут-то и выясняется, что для этого в первом случае требуется установить сам MS Visual C++ и какой-то MASM. Официально рекомендуется скачивать с сайта Майкрософта версию Visual C++ 2005 Express. Полазив же по сайту MS нашел только какой-то веб-инсталлятор под Visual C++ 2010 Express. Вроде бы как Express-версии бесплатны в использовании (хотя, может, я просто чего-то не понял:). Но в любом случае, тянуть много чего, да еще и сильно проприетарного, не очень хотелось. Так что наш выбор - порт на основе MinGW/CygWin, версию 3.11 которого в виде виндового инсталлятора можно скачать по ссылке: http://caml.inria.fr/pub/distrib/ocaml-3.11/ocaml-3.11.0-win-mgw.exe. Размер инсталлятора - чуть более 40 мегабайт.

суббота, 15 января 2011 г.

Видеоурок "Вычисление конечной цепной дроби на Haskell"

Всем привет.
Продолжаем выпускать видеоуроки )
Сегодня записал небольшой видеоурок по решению упражнения N1.37 из SICP ("Структура и интерпретация компьютерных программ" Абельсона и сотоварищи) на тему вычисления конечной цепной дроби.

Сначала вкратце рассказываю, что такое бесконечная и конечная цепная дробь, каким образом с помощью неё можно вычислить коэффициент золотого сечения theta, а затем привожу решение задания на хаскеле - привести 2 варианта реализации функции вычисления конечной цепной дроби, порождающие рекурсивный и итеративный процессы,
и определить минимальное количество членов конечной цепной дроби, которая даст точность нахождения коэффициента золотого сечения в 4 знака после запятой.

Снова в видео есть некоторые огрехи, но зато они придают определенную живость повествованию ) Само видео, залитое на ютьюб, ниже:

суббота, 8 января 2011 г.

Видеоурок "Функции высших порядков" (на примере Haskell)

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