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

[Gypsy]

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

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

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

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

[Gypsy]

Originally Posted by knightmare

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

А еще можно просто отсортировать строку
Никаких тебе рандов, и никто обратно не соберет

[knightmare]

Originally Posted by Gypsy

Есть ограничения:
- максимальная глубина (вложенность) < 16.
- максимальная глубина отдельно взятого типа скобок <= 8

Не хочу оставить впечатление ****звона, но не слишком ли строгие ограничения? На коде, написанном на Lisp-е, не применишь...

Originally Posted by Gypsy

char pOC[] = "{([})]";
 #define NUM_BRACKETS (sizeof(pOC)>>1)

Функция проверки баланса:

int CheckBalance(char* p)
 {
     int i, c, b = 1, m = 0, n[NUM_BRACKETS], s = NUM_BRACKETS;
     while (i=0, (c=*p++) && b)
         while ((pOC[i]==c) && ((n[i]<<=4)|=++m),
               (pOC[s+i]==c) && (b=((n[i]&0xF)==m--), n[i]>>=4), ++i-s);
 
     return b && (m==0);
 }

У нас в Ереване газовые трубы проводят примерно в этом же стиле

Кстати, предложение shuffle было inspired by текстом, опубликованным в топике Исследование одного университета. (текстом, а не топиком - см. даты постов).

[Gypsy]

Originally Posted by knightmare

У нас в Ереване газовые трубы проводят примерно в этом же стиле

Это потому что я для них пишу и код и спецификации

[Gypsy]

Originally Posted by knightmare

Не хочу оставить впечатление ****звона, но не слишком ли строгие ограничения? На коде, написанном на Lisp-е, не применишь...

Вообще-то собственный source эта функция запросто проверит (там глубина = 5 кажется).

Если серьезно, то ограничения можно тривиально расширить до любых констант. Использовать несколько int-ов вместо одного, к примеру, или просто 64-битные int-ы. Суть не в этом, а в самом алгоритме

[knightmare]

Вообщем идея хорошая - избавились от самой строки (хоть как нибудь)...

[Ablertus]

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

[Ablertus]

[quote=Gypsy]Если A и B даны как массивы, и их можно модифицировать на месте,
то можно решить задачу используя постоянное количество памяти (всего несколько переменных).

OK, ya napishu svoe, ono gorazdo koroche, no prosto potomu chto na Pythone :

PHP Code:


def Dist(A, B):
     unilen, sectlen = len(A) + len(B), 0
     
     for el in A:
          if el in B:
               unilen -= 1
               sectlen += 1

     return 1 - (float) sectlen / unilen 


[knightmare]

Originally Posted by Ablertus

PHP Code:

if el in B: 


Не смешно...

[Ablertus]

Originally Posted by knightmare

Не смешно...

A kto prosil smejatsja? Eto Python - i bezo vsjakih shutok. Vse kogda to byli arrogantnymi C-istami.

[Agregat]

так ведь решение в лоб

[Ablertus]

Originally Posted by Agregat

так ведь решение в лоб

Nu ladno, prosto zahotel prodemonstrirovat krasotu yazyka, a to ego tut vrode kak nedoocenivayut. Est reshenie luchshe? Esli net, poslozhnee zadachku vylozhu

[knightmare]

Originally Posted by Ablertus

A kto prosil smejatsja? Eto Python - i bezo vsjakih shutok. Vse kogda to byli arrogantnymi C-istami.

Не имею ничего против Python (даже наоборот - за), просто 80% задачи решились встроенными возможностями языка. Это как если задачу про перемешку строки решить на PHP так: <?php $shuffled=str_shuffle($str); ?>

[Ablertus]

Originally Posted by knightmare

Не имею ничего против Python (даже наоборот - за), просто 80% задачи решились встроенными возможностями языка. Это как если задачу про перемешку строки решить на PHP так: <?php $shuffled=str_shuffle($str); ?>

A tut ya ne soglasen. Ved zadacha (gromko skazano - zadachka, zadachka!) byla ne o poiske identichnyh elementov v posledovatelnostyax, a o tom kak vychislit sootnoshenie komplementov k unionu. Python kak raz tem i xorosh, chto pozvolyaet skoncentrirovatsa na sobstvenno celi, ne tratya vremeni na rutinnye i nabivshie oskominu kuski koda. Mozhete predlozhit druguyu zadachu, poslozhnee, i my sravnim reshenie, skazhem, na C, na Jave i na Pythone.

[Gypsy]

Originally Posted by Ablertus

Mozhete predlozhit druguyu zadachu, poslozhnee, i my sravnim reshenie, skazhem, na C, na Jave i na Pythone.

Хорошая идея. Допустим такая задача:

Найти значение арифметического выражения
(только положительные числа, скобки, и +-*/)


Скажем: (5 + 3) * (5 + 4 - 1) --> 64

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

[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.