Речь в основном будет идти...: мая 2008

пятница, 30 мая 2008 г.

Project Euler, problem 191

Давно не заходил на Project Euler, успел опуститься до 3й сотни.
Проблема оказалась простой. Как обычно просмотр решений был гораздо интереснее.
Больше всего понравилось одно из решений на С++. Это было самое быстрое решение. Понравилось настолько что приведу его...

int euler_191()
{
    int O,Oa,Oaa,L,La,Laa,SO,SL,Result;
    O=1;
    Oa=1;
    L=1;
    SO=2;
    SL=1;
    for (i=2, i<=30,i++)
    {
       Oaa=Oa;
       Oa=O;
       O=SO;
       Laa=La;
       La=L;
       L=SL+SO;
       SO=O+Oa+Oaa;
       SL=L+La+Laa;
    }
    return SO+SL;
}

Думаю оно не очень понятно...поэтому обьяснение.

here are only 6 states in which strings can exist, divided into two groups. Three of those states are those where the strings don't contain any LATE occurence. The other three are those where the strings already contain one LATE occurence. Within each group, one state is when the string does not end with an absence, another when the string ends with only one absence, and the third when the string ends with two absences. Let's denote them as O, Oa, Oaa, L, La and Laa. Let's denote the sums of these two groups as SO and SL.

The initial states after the first day would be O=1, Oa=1 and L=1(all other states =0). The initial sums would be SO=2 and SL=1.
a) If absent on the following day, all strings in state Oa would become Oaa strings and all strings in state O would become Oa strings. Similarly, all strings in state La would become Laa strings and all strings in state L would become La strings.
b) If late on the following day, all strings in group O would become L strings.
c) If neither late nor absent on the following day, all strings in group O would become O strings (O=SO), and all strings in group L would become L strings in addition to (b) above such that L=SL+SO.

The following algo should produce the answer within 1 ms with most (if not all) programming languages. zeycus and logopetria have already posted similar algos in their own programming language.

Также понравилось рекурсивное решение.

int blah(int d, int a, bool l)
{
    return d == 0 ? 1 : (blah(d - 1, 0, l) + (a >= 2 ? 0 : blah(d - 1, a + 1, l)) + (l ? 0 : blah(d - 1, 0, true)));
}

вторник, 27 мая 2008 г.

Первые шесть месяцев продаж неплохого приложения...

A Look Back at HelpSpot’s First 6 Months of Sales

October - $3,277.96
November - $626.50
December - $4,163.00
January - $1,253.00
February - $3,967.46
March - $8,703.03

понедельник, 26 мая 2008 г.

C++ интересный трюк с приведением типов

Нагло сперто с RSDN.

Возьмём простенький пример:

enum colors {red, green, blue};
 
struct proxy
{
    operator colors () const
    {
        return red;
    }
};
 
proxy f()
{
    return proxy();
}
 
int main()
{
    colors c = f(); // хорошо
    int i = f(); // спорно, но компилируется
    std::cout << f(); // спорно, но компилируется
    unsigned u = f() + 1; // совсем спорно, но компилируется
    if (f()) // совсем спорно, но компилируется
        std::cout << "if\n";
}

Теперь немного допилим напильником:

struct proxy
{
    operator colors () const
    {
        return red;
    }
 
    private: template<typename T> operator T () const;
};
 
int main()
{
    colors c = f(); // хорошо
    int i = f(); // не компилируется
    std::cout << f(); // не компилируется
    unsigned u = f() + 1; // не компилируется
    if (f()) // не компилируется
        std::cout << "if\n";
}

Получается что-то типа explicit conversion operator. Автоматически приводится только, если тип полность совпадает, в противном случае надо писать явный каст:

int main()
{
    std::cout << (colors)f(); // ок
}

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

class proxy
{
    public: operator char const* () const
    {
        return "hello from proxy";
    }
 
    public: operator wchar_t const* () const
    {
        return L"hello from proxy";
    }
 
    private: template<typename T> operator T () const;
};

красота...

пятница, 30 мая 2008 г.