Минимальные, оптимальные, красивые решения простых задач :)

[Gypsy]

Навеяно соседним топиком "Шедевры". Но здесь пишем только свои задачи и решения

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

Начну я сам. В тот день, после поста про незакрытые скобки, я задумался как можно оптимально (быстро и/или с минимальным кодом)
реализовать функцию проверки балланса различных скобок (фигурных, круглых, и т.п.) в заданной строке текста.

У кого какие предложения? У меня есть одно довольно короткое и быстрое решение, выложу потом после ваших версий.

[Ablertus]

PHP Code:

import string

def Calx(str):

    operators = {
        '+' : lambda a, b : a + b,
        '-' : lambda a, b : a - b,
        '*' : lambda a, b : a * b,
        '/' : lambda a, b : a / b
    }

    def tonum(tok):
        try: return string.atof(tok)
        except: return tok

    def CalcExpr(toks):
        rv = toks[:]
        for op in ['*', '/', '+', '-']:
            while op in rv:
                i = rv.index(op)
                rv [i - 1 : i + 2] = [operators[op](rv[i - 1], rv[i + 1])]

        return rv[0]

    for sign in ['(', ')'] + operators.keys():
        str = str.replace(sign, ' %s ' % sign)      

    toks = map(tonum, str.split())

    start, end =  len(toks) - 1, 0  

    while  '(' in toks:

        while toks[start] != '(':
            start -= 1

        end = start

        while toks[end] != ')':
            end += 1

        toks[start : end + 1] = [CalcExpr(toks[start + 1 : end])]
        

    return CalcExpr(toks) 


Rabotaet na floatax, nalichie probelov mezhdu chislami, operatorami i skobkami, a takzhe skobok vokrug vsego vyrazhenia ne trebuetsa.

[knightmare]

Мое решение.
Ограничения: корректность строки не проверяется, не должно быть пробелов, из чисел только неотрицательные целые,
число с точностью unsigned int, всё выражение с точностью double, деление на ноль не отслеживается.

double eval(char *str, unsigned int end, unsigned int start=0){
    unsigned int v=0, brk=0, hi=0, i;
    for(i=start; i<end; i++){
        if(str[i]=='('){brk++;}
        else if(str[i]==')'){if(i==end-1 && !hi){return eval(str, --end, ++start);}brk--;}
        else if(!brk && (((str[i]=='*' || str[i]=='/') && (str[hi]!='+' && str[hi]!='-')) || (str[i]=='+' || str[i]=='-'))){hi=i;}
        else v=v*10+str[i]-'0';
    }
    if(!hi){return v;}
    double l=eval(str, hi, start), r=eval(str, end, hi+1);
    return str[hi]=='+' ? l+r : str[hi]=='-' ? l-r : str[hi]=='*' ? l*r : l/r;
}

Для (12*3+6-73/3)*23+(21)/3+3*(12+1)+12+((1+1)*(2+4)) ответ 476.333(~). Вроде, верно.

Cамый короткий вариант - javascript:eval(str);

========

Originally Posted by Ablertus

А давайте я задачку задам. Как посчитать дистанцию Марчевского-Стеинхауса, задействовав минимальный обьем памяти? Для тех кто не знает речь идет о доле симметричного комплемента в обьединении: d = |(A/B) U (B/A)| / |A U B|.

Если множества заданы как массивы и их нельзя изменять, и заданы:
функиция, нумерующая элементы множества (от 0 по ++),
количество всевозвожных элементов n,
и уменьшить нужно ТОЛЬКО расход памяти, то элементарно и грубо решается в среднем
расходуя n*sizeof(bool) (может лучше использовать char) плюс 3-4 инта.
Можно даже меньше в несколько раз, если использовать массив битов. Тогда код возрастет.

Что-то вроде этого... но, опять таки, решение в лоб...

template<class T, unsigned int n, unsigned int (*nE)(T)> double dist(T *A, unsigned int nA, T *B, unsigned int nB){
    unsigned int nU=0, nD=0, i; bool b[n];
    for(i=0; i<n; b[i++]=0);
    for(i=0; i<nA; b[nE(A[i++])]^=1);
    for(i=0; i<nB; b[nE(B[i++])]^=1);
    for(i=0; i<n; nD+=b[i++]);        //можно(?) включить в два предыдущих
    for(i=0; i<nA; b[nE(A[i++])]=1);
    for(i=0; i<nB; b[nE(B[i++])]=1);
    for(i=0; i<n; nU+=b[i++]);        //можно(?) включить в два предыдущих
    return (double)nD/nU;
}

Originally Posted by Ablertus

Ya tolko otmechu, chto samoe glavnie vse taki ne kompaktnost koda, a skorost raboty programmista. Naprimer, kod na Jave izvestna svoej mnogoslovnostyu, mozhet zanimat gorazdo bolshe mesta, chem na C, no pisat na ney vse taki poluchaetsa bystree.

Вообщем то верно... Еще Эрик Раймонд писал, что время машины намного дешевле времени программиста.

...Но иногда хочется расслабиться.

[Ablertus]

Originally Posted by knightmare

...

Interesno, chto ya i sam v svoe vremya reshil etu zadachu na C++ recursivno. I tolko Python spodvig menya na vozmozhno menee effectivnoe (s tochki zrenia skorosti), no gorazdo bolee legko realizuemoe iterativnoe reshenie. Okazyvaetsa, vozmozhnosti jazyka inogda podskazyvajut samu logiku reshenia Kod knightmare vrode kak bolee kompakten, zato moy gorazdo bolee chitabelen (po moemu) i napisan byl na sutki bystree, tak chto Python rulez!

[knightmare]

2Ablertus: Всё то, о чем ты говоришь, безусловно верно, и к этому приходят опытные программисты...
и потом, иногда, в свободные минуты, с ностальгией пишут программы, соответствующие названию темы,
чисто для эстетического наслаждения. А написав, быстро удаляют код, не соответствующий
никаким правилам "хорошего тона", правилам переносимости и разным другим ограничением мира...
(о.. как загнул!)

...Ждем новых задач!

[knightmare]

Кстати, о задаче про дистанцию...
Кокого это решение? Чисто исходя из практики?
2*(n+An+Bn) обычно бывает больше nA*nB (плюс расход на сравнение при прямом решении)?
И всегда ли можно легко реализовать быструю/маленькую нумерующую функцию?
Если, конечно, кто-либо вообще сталкивался с этим на практике...

[Ablertus]

Originally Posted by knightmare

Кстати, о задаче про дистанцию...
Кокого это решение? Чисто исходя из практики?
2*(n+An+Bn) обычно бывает больше nA*nB (плюс расход на сравнение при прямом решении)?
И всегда ли можно легко реализовать быструю/маленькую нумерующую функцию?
Если, конечно, кто-либо вообще сталкивался с этим на практике...

Chestno govorya, sam ne ponyal tvoe reshenie (mozhet, nachinayu zabyvat C? ) Ty sozdaesh massiv bitov dopolnitelno k uzhe sushestvujushim v pamjati massivam mnozhestv? Zachem?

[knightmare]

b[i]=1 если i-ый элемент присутствует и т.д. (при XOR - исключается двойное вхождение, в оба массива), ну а потом просто считаем 1-ы.
Это всё оправданно, если тип T ооочень большой + элементы дорого сравнивать + но легко индексировать.

[Ablertus]

Ponjatno, znachit vse taki imela mesto optimizacija s maksimizaciej skorosti. Ladno, togda chto nibud sam predlozhi

[knightmare]

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

[Ablertus]

Originally Posted by knightmare

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

nu obyasni mne, bud dobr. v moem variante v pamyati (vo vsyakom sluchae explicitly) voobshe ne sozdaetsa nichego novogo krome dvux integerov.

[knightmare]

Ну ладно, понятно с памятью всё уже... я просто про скорость не забывал...

Есть еще задачи???

[Ablertus]

ladno, ya ne xotel sporit, prosto bylo interesno net, ya sam zhdu

[knightmare]

Вот проблема (лучше что-нибудь, чем ничего).
Дан двумерный массив NxM с булев. значениями.
Нужно выбрать случайный элемент со значением true - выбрать пару (x, y).
С оптимизацией во все стороны.

Доступна rand(), ну или что там еще бывает.

[AvDav]

при чтении массива в память дзери хет ншел которые тру и псевдослучайно их тыкать.

[knightmare]

Originally Posted by AvDav

при чтении массива в память дзери хет ншел которые тру и псевдослучайно их тыкать.

Выбрать нужно только одну пару...

...или я чего-то не понял?

Т. е. создавать еще один массив пар координат элементов, значения которых в главном массиве true? А лучше?