Про именование координатных осей

В двумерном случае оси ординат обычно обозначаются X и Y. Соответственно в 3хмерном пространстве нужна еще одна ось - Й.

Задачка на вероятность.

Практическая.

Интервал движения автобуса 30 минут. Ехать от моей остоновки до следующей 5 минут. Идти пешком - 30 минут. Вопрос - сколько ждать автобус прежде чем пойти пешком?

Теоретическая.

Взять DVD посмотреть стоит 4$. Купить - 16$. Вопрос - сколько раз брать DVD посмотреть перед тем как купить?

Теоретической эта задача является в том смысле что "да я лучше из инета скачаю".

Подзадача - стоит ли в решении учитывать обратную связь? Т.е. даже не глядя фильм можно сделать некоторые предположения о том сколько раз этот фильм будет просматриваться. После первого простотра эти предполажения становятся уже почти уверенностью...

И где же свобода слова!!!???

Вот видео, на нем видно как полиция арестовывает человека в футболке с надписью McCain & Palin на праздновании избрания Б.Обамы президентом США.
Какой кошмар и ужас...какое попрание свободы...если бы не...

Ну во первых приходить к фанатам Спартака после первой за 8 лет победы над Зенитом в футболке "Зенит - чемпион!" само по себе не самая лучшая идея. Чтобы так сделать нужно сильно не дружить с головой.

А во вторых смотрим тут. На 3:33 видно что у чудика за спиной что-то типа меча. Не ну может быть там конечно безопасный вибратор, но этого не видно.

так что неплохая попытка мистер провокатор...

но с другой стороны - "осадочек остался". как же я это терпеть ненавижу...

кстати...при всей моей нелюбви к подобным массовым гуляниям то что чудика не взгрели - жирный плюсик Обамавским фанам.

Nemerle+Project Euler2 - продолжение.

Окозалось что нужные мне операторы есть!
В результате удалось написать вот такое:

SC.WriteLine(

    (1,1)

    |> F.unfold(_,(a,b)=>(a+2*b,2*a+3*b))

    |> F.takewhile(_,(a,b)=>(a+b)<4000000)

    |> F.fold(_,0,(v,x)=>v[0]+v[1]+x)

А можно было извратиться и дальше и написать вот так:

def write = SC.WriteLine:int -> void;

 

(1,1)   |> F.unfold(_,(a,b)=>(a+2*b,2*a+3*b))

        |> F.takewhile(_,(a,b)=>(a+b)<4000000)

        |> F.fold(_,0,(v,x)=>v[0]+v[1]+x)

        |> write(_);

дальше - забавы с pattern matching

Nemerle - что это и где...

Наконец-то решил изучить поподробнее...

Итак, что мы имеем. Nemerle это язык для платформы .NET. Гибридный. С кучей современных возможностей.

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

0. Привычный мейнстрим синтаксис. Т.е. это не хаскел, нет. Рядовой C#/C++/Java разработчик может перейти на Nemerle прочитав пару статей.

1. Tuples (это которые кортежи). Очень сложно обьяснить тем кто не пользовался насколько часто это удобно и насколько это упрощает некоторые вещи.
Тем кто знаком с Python - ага, те самые.
В терминах C#3.0 это будет "анонимные гетерогенные массивы" или как-то так. Но с правильной типизацией и очень удобные в использовании.

2. Pattern Matching (сопостовление по образцу). Если по простому - это "switch on steroids". Опять таки...после некоторого времени писанины на языке у которого есть поддержка pattern matching возврат к "старым добрым" if и switch вызывает ломку.

3. Type Inference (вывод типов). Правильнее чем в C#3.0, мощнее, удобнее. Вообщем код начинает питоновский напоминать. Хотя не хаскел конечно, но это и не нужно. К слову - фанаты динамических языков часто упрекают языки со статеческой типизацией в излишней многословности. Так вот - благодаря этому самому type inference это не так. Опять же - после использования языка с развитым type reference возврат в привычную песочницу вызывает ломку.

4. List Comprehensions (как это будет по русски - затрудняюсь). Фича присутствует в Python/Ruby/Haskell/Groovy и возможно где-то еще, не знаю. Фича удобная, когда ее отнимают ломка не возникает но все равно с ней приятнее чем без нее.

5. Функциональные типы (functional types). Я в этом разбираюсь достаточно поверхностно. Но даже моего уровня хватает чтобы понять - делегаты зло, функциональные типы это правильно. Делегаты в C# это некоторое подобие именнованных функциональных типов. Усложненное и с недостатками. Также функциональные типы напоминают Func<A,B>, но все равно их реализация в Nemerle намного правильнее.
Например функцию которая принимает в качестве параметра фукнцию принимающую int и string и возвращающую int можно описать вот так

some_func(f:int*string->string):void

6. Алгебраические типы. Есть отличия от "классических" алгебраических типов, но как по мне только в лучшую сторону. Опять же по простому для знающих С++ "алгебраические типы" это "union on steroids". Обобенно мощно себя проявляют в связке с pattern matching.

дальше просто лень писать ибо долго и много, но еще есть
...матапрограммирование (и огого-го какое. Например linq из С# реализуется макросами языка)...лямбды(ну куда ж без них в наше то время)...closures...да много чего. Причем большенство - прямо от рождения. Т.е. Nemerle таким умным родился, а не эволюционировал к пятой версии.

Вообщем по фичам языка вот тут интересная табличка. Сделайте скидку на то что составлялась евангелистом (читай - фанатом) языка. Но как по мне у него есть все основания фанатствовать.

Для знакомства с языком решил поиграться с первыми задачами из ProjectEuler...

Итак задача 2.

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million

Понятно что задача простая (хотя и тут можно кое-что...), суть не в ней.
Написав (точнее переписав) несколько extension methods для удобной работы с перечисляемыми типами (IEnumerable) я в первоначально пришел вот к такому решению:

        WriteLine(

            (1,1)

            .unfold((a,b)=>(b,a+b))

            .takewhile((_,b)=>b<4000000)

            .filter((a,_)=>a%2==0)

            .fold(0,(v,x)=>v[0]+x)

            );

теперь немного о простоте задачи. простая-то она простая, но и в ней можно оптимизировать решение.
рассмотрим первые числа последовательности, но следить будем только за четностью...
o(1),o(1),e(2),o(3),o(5),e(8),o,o,e,o,o,e,....

ну думаю заметно о чем идет речь...
и тогда наш код преобразуется в:

     WriteLine(

            (1,1)

            .unfold((a,b)=>(a+2*b,2*a+3*b))

            .take((a,b)=>(a+b)<4000000)

            .fold(0,(v,x)=>v[0]+v[1]+x)

            );

Попытался сделать макрос для функциональной композиции, чтобы код можно было записать так (идея честно украдена в F#):

     WriteLine(

            (1,1) |> unfold((a,b)=>(b,a+b)) |> take((_,b)=>b<4000000) |> filter((a,_)=>a%2==0) |> fold(0,(v,x)=>v[0]+x)

            );

пока не получилось...(

зато обнаружилось несколько "шероховатостей", явно связанных с тем что некоторые конструкции являющиеся в других языках частью языка в Nemerle являются макросами.

А вообще ситуация выглядит так:
- отдать бы Nemerle в хорошие руки (читать - микрософт. там к слову авторы языка уже обитают), и чтобы эти руки выделили человек 10 на разработку и еще несколько раз по столько на доки/примеры/т.д.
И чтобы эти руки добавили dynamic и какой-нибудь оператор для функциональной композиции. Ну и так...по мелочам.
И через полгода-год у нас бы был прекрасный язык, и еще через полгода все бы забыли про C#.

Выводы -
1. Nemerle это язык которым C# дай бог станет лет через пять. А то и все десять. И то - с ограничениями...
2. Если хорошие руки не найдутся - there is no future for Nemerle in this stupid and cruel world(.

А пока попробую всякие поделки клепать на Nemerle.

много интересного за последние дни...

Мартин Флауэр рассказывает об Oslo.
Саттер Милл представил очередной драфт С++
На Microsoft PDC была представлена Windows 7.
Марк Руссинович на Channel 9 рассказывает о внутренностях Windows 7 (если кому интересны только внешние рюшечки - об этом тоже много новостей)

Anders Hejlsberg (папа турбопаскаля, дельфинов и шарпа) рассказывает о C# 4.0 (Dymanic! Dymanic! Dymanic! - вот она новая струя. Ну и заодно параметры по умолчанию добавили, не прошло и 10 лет. Ко- и Контр Вариантность. Куча приятных плюшек при работе с COm. И в перспективе (C# 5.0) метапрограммирование.)

Google Treasure Hunt 2008

Смотреть тут...
Вот...хотелось задачки порешать.
После ProjectEuler оказалось - ни о чем. Самое сложное - ждать 10 минут проверки решения...

Разве что задачка про робота неплоха, требует немного подумать, вполне может подойти для интервью.
Вот решение на питоне :

def google_test_robot():

    d={}

    d[(0,0)]=1

    def helper_(a,b):

        if a<0 or b<0:

            return 0;

        if not d.has_key((a,b)):

            d[(a,b)] = helper_(a-1,b)+helper_(a,b-1)

        return d[(a,b)]

    print helper_(41,44)

несмотря на "меморизацию" :) решение далеко не самое оптимальное как с точки зрения используемой памяти так и с точки зрения скорости. Правильнее было бы идти по диагонали...но так писать дольше.
И уж совсем правильнее было бы использовать так называемые Catalan numbers (ну это если повезло и поле квадратное)

Перевести число в строку...прописью. На русском.

Просто вот такая простая но полезная задача на интервью.

Project Euler 201 - не выходит

Почему вообще заинтересовала эта проблема? Во первый мне показалось что итеративный подход намного красивее и понятнее функционального.
А во вторых...написав в принципе правильный алгоритм я получил неправильный результат. И довольно долго не мог понять в чем собственно дело.
Задача:
Пусть у нас есть массив S={1*1,2*2,...100*100}
Найти сумму чисел которые являются уникальной ссуммой 50-элементного подмассыва S.
Более подробно на сайте...

Код (неправильный)

    char* total = new char[300000*50];

    memset(total,0,300000*50);

 

    for(int i=1;i<=100;++i){

        for(int j=299999;j>0;--j)

            for(int p=0;p<49;++p)

                if(total[j*50+p])

                    if(total[j*50+p])

                        total[(j+i*i)*50 + p + 1] += total[j*50+p];

        total[i*i*50]=1;

    }

 

    LONGLONG res = 0;

    for(int j=49;j<300000*50;j+=50)

        if(total[j]==1)

            res+=(j-49)/50;

    delete total;

    return res;

Самая длинная общая подпоследовательность

Опишу-ка я некоторые алгоритмы которые "я всегда знал но забыл".
Начнем с длины самой длинной общей подпоследовательности.
Пусть у нас есть два массива A=(a1...ai) и B=(b1...bj)
Тогда LCS(A,B)=:
1. 0 если i==0 или j==0;
2. LCS((a1...ai-1) ,(b1...bj-1))+1, если ai==bj
3. MAX(LCS((a1...ai-1) ,(b1...bj)),LCS((a1...ai) ,(b1...bj-1))), если ai!=bj

Это достаточно очевидные утверждения, и по ним уже можно составить алгоритм.
Алгоритм просто напрашивается:

int lcs(int* a,int N1,int* b,int N2)

{

    if(N1==0 && N2==0)

        return 0;

    if(a[N1-1) == b[N2-1])

        return 1+lcs(a,N1-1,b,N2-1);

    return max(lcs(a,N1,b,N2-1),lcs(a,N1-1,b,N2))

}

красотища...если бы не одно но. очень медленно.
И в целом почти сразу понятно почему. Мы не храним промежуточные вычисления а каждый раз делаем их заново.
Класический пример такой проблемы - вычесление чилес Фибоначчи по рекурсии:

int F(int N)

{

    return (N<2)?1:F(N-2)+F(N-1);

}

Улучшить это можно, сохраняя промежуточные результаты вычислений. Этот прием называется "меморизация". Т.е. вообще-то он называется "Memoization", но надо же как-то по русски сказать.

В данном случае для меморизации нам понадобится массив размером [i*j].
Но тут возникает интересный вопрос - а зачем нам тогда рекурсия здалась?
И возникает примерно такой код (пробывать не советую, не тестировал, могу ошибиться с индексами)

int lcs_array(int* a,int N1,int* b,int N2)

{

    int* c = new int[N1*N2];

    memset(c,0,N1*N2*sizeof(int));

    for(int i=0;i<N1;++i)

        for(int j=0;j<N2;++j)

            c[i*N2+j]=(a[i]==b[j])?c[(i-1)*N2+j-1]+1:max(c[i*N2+j-1],c[(i-1)*N2+j]);

    int res = c[N1*N2-1];

    delete[] c;

    return res;

}