кажется те двое, что недавно до хрипоты спорили, что перл не сдох, справятся с этой задачей лучше всех

На Perl задача решается легко. Так же, как на PHP, на котором её я лепил :)

..

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

и это, а можно сделать тестовый текст, на котором время замерять?

быстрее будет на асме, если конечно это вопрос скорости а не практическая реализация.

тов. Очевиднев, в данном случае под быстротой корректнее понимать сложность алгоритма.

Почему — на асме?

Функция сложности существенно зависит от языка реализации? Утверждение как минимум весьма сомнительное. Ну, на константу помножить…

>и это, а можно сделать тестовый текст, на котором время замерять?

Ну, для начальной оценки можно использовать тот вариант, что я закинул. Одна строка, которая размножается N раз для оценки.

>быстрее будет на асме, если конечно это вопрос скорости а не практическая реализация.

Интересуют, естественно, практические решения :)

Традиционно, сперва обмениваемся информацией что вышло, после окончания конкурса - раскрываем сорцы и сравниваем.

>Функция сложности существенно зависит от языка реализации?

Ну да. У автора темы зависимость вышла уровня o(n)=3n+n*n!

У меня, вроде, ~n² (хотя оценка не точная, а на глазок по росту затрат времени с увеличением n).

Начиная с какого-то значания n, мой вариант на PHP слепленный за час с отладкой, будет явно быстрее варианта на ассемблере с n²!, на который и на написание точно не меньше нескольких дней бы ушло :)

...

В принципе, можно мой вариант переложить на Java почти 1:1 и получить ускорение в несколько десятков раз. Думаю, отлаженный вариант перепишется с тестированием за полчаса-час где-нибудь.

На Си/Си++ переписать не возьмусь, геморроя будет вагон. День ковыряться. STL, правда, наверняка поможет, но я с ним не работал, с Си++ свалил раньше, чем STL обрёл популярность :)

Могу сделать на Perl, быстро и просто, но мне лень.

Могу парсить входной текст в уме, но мне лень.

1) Это несколько облегчённый вариант задачи с одного из ICFP. Там, правда, не требовалась именно минимальность решения, нужно было, чтобы результат получился меньше, чем у других.

2) Товарисч явно очень хреново умеет формулировать задачи.

>Могу сделать на Perl, быстро и просто, но мне лень.

Лень == не можешь :) По определению.

>Там, правда, не требовалась именно минимальность решения

А это очень усложняет задачу. Я, вот, честно таже не стал пытаться на PHP решить, ресурсоёмкость нужна при лобовом решении страшная. Сделал костыльное решение, которое, вроде, работает и достаточно быстро. Но гарантии на все случаи нет :)

>2) Товарисч явно очень хреново умеет формулировать задачи.

Ну, главное, в итоге задание стало понятно :)

А как оценивается сложность алгоритма? n я так понимаю количество "тегов", а не элементов в строке. Так? Если так, то сложность получается O(n + K), где K некое число, зависящее от количества перекрывающихся зон и от их вложенности.

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

http://ru.wikipedia.org/wiki/Сложность_алгоритма

Вот я решительно не понимаю, как решение на автоматах может быть медленнее, чем O(n). Оне же _конечные_.

> Вот я решительно не понимаю, как решение на автоматах может быть медленнее, чем O(n). Оне же _конечные_.

Считай, что n=3x+x*x =).

O-O

>o(n)=3n+n*n

Мне кажется, или это чепуха? Величина малая по сравнению с n вдруг стала равна 3n+n*n. Может имелось в виду O(3n+n^2)?