(no subject)

[vdas.livejournal.com]

Мля... Совсем поломал голову. Тупая, простейшая задача, но я уже вообще ничего не соображаю. Есть список <50, <100, >=100, >200 итд итп - надо преобразовать его в пары (с-до): 1-49, 50-99, 100-200, 201-MAX

Тетки дают такие списки.
А нужны пары "С-До" .Сегодня (больше некому было) пришлось ручками это все раскладывать. [...] Тарифы, мля...[...]

Я - тупой :( Мне не приходит в голову простой и эффективный алгоритм. Все время монстры какие-то рисуютсо... Некрасивые... Хелп.

Comments

[meanab.livejournal.com]

Что-то в таком духе: два прохода. Каждый интервал представлен парой (from, to), где from и to — либо число, либо NIL. При первом проходе заполняем указанные в явном виде части интервала. При втором проходе заменяем NIL в поле from на to предыдущего интервала, а NIL в поле to — на from следующего. В реальности алгоритм будет чуть сложнее, так как нужно учитывать граничные условия и, возможно, открытость/закрытость интервала (если речь идет о целых числах, то можно просто заменять '<100' на '<=99').

[meanab.livejournal.com]

Ну, разумеется, добавить всякие проверки, на то, что при замене NIL мы не наткнемся на другой NIL, на то, что в интервале поле to должно быть больше, чем from и т.д. В этих случаях сразу signal a condition (raise an exception или как это называется в вашем языке). Можно, конечно, сделать и в один проход, но, насколько я понимаю, вопроса эффективности здесь возникать не должно, только чистоты и простоты кода.

[vdas.livejournal.com]

Язык совершенно неважен - я напишу такую задачу на абсолютно любом языке. Важен алгоритм. Простота кода необязательна. Код может быть сложен для чтения, но красив :)

[vdas.livejournal.com]

именно "в реале это будет чуть сложнее..." и интересует. Ибо совсем не "чуть сложнее".
Что в какой последовательности делать "в принципе" - и коню понятно.
А вот каков алгоритм оптимален?

Можно делать два прохода с созданием "модификаторов" для учета '<', '<=', '>', '>=' (+1, -1 итд)
Можно разложить на множества и искать пересечения (типа <100 это от -бесконечности до 99 и т.д.)
...
Вариантов много, но они громоздки и некрасивы. Задача-то не совсем экзотическая - может кому попадалась.

[urvin.livejournal.com]

SELECT id,tname,tcost
FROM tariffs
WHERE tcost<100
AND tcost>50

[vdas.livejournal.com]

не все так очевидно :) фишка как раз в том, чтобы получить эти самые 100 и 50

т.е. у меня есть
<50 - 1 лит,
<=100 - 2 лита
<=200 - 2.5 лита
>200 - 3 лита

для импорта в систему надо получить список, скажем, вида:
1 - 49 - 1 лит
50-100 - 2 лита
101-200 - 2,5 лита
201-MAX - 3 лита

[a-bronx.livejournal.com]

Всё в целых числах?

Сортируем список и начинаем создавать интервалы. Все интервалы - полуоткрытые. Первый интервал - [1, null). Бежим по списку. Каждый шаг закрывает один интервал и создаёт новый.
- Если встречаем "<N" - текущий интервал закрывается числом N-1, и открываем новый интервал [N, null).
- Если "<=N" - число N закрывает текущий интервал, создаём новый интервал [N+1, null).
- Если ">=N" - число N-1 закрывает текущий интервал, создаём [N, null).
- Если ">N" - число N закрывает текущий интервал, создаём [N+1, null).
По окончании закрываем последний интервал числом MAX.

[a-bronx.livejournal.com]

Да, сортировать список нужно по-хитрому:

"<=N" == ">N" == "<N+1" == ">=N+1" < "<=N+1" == ">N+1" == ...

Вообще говоря, эквивалентных элементов в списке быть не должно, т.к. они сгенерят одинаковые интервалы, а это исключительная ситуация.

[vdas.livejournal.com]

не только в целых, но это не суть - вопрос реализации :)
дело вот в чем:
<100
>150

создадутся:
1-99
100-150 - этого интервала нет. ошибка.
150-max


<=100
>=100
неверно создадутся. неоднозначность. ошибка.

Проблема скорее в реализации "защиты от дурака" - заполнить интревалы и отметить ошибки.

[a-bronx.livejournal.com]

А, если допускаются разрывы, то их можно поймать во время генерации интервалов по типичным паттернам в последовательности, например, отлавливать смежные пары ("<", ">") и т.п. Простой автомат с запоминанием предыдущего шага.

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

[a-bronx.livejournal.com]

Тьфу, на свежую голову вижу косяк: я сначала написал, что все интервалы полуоткрытые, а на деле генерирую закрытые. Ну да фигня, в общем-то, чуть упростятся выражения при генерации (и чуть усложнятся при выводе):

"<N", ">=N" ==> [_, N), [N, null)
"<=N", ">N" ==> [_, N+1), [N+1, null)

[vdas.livejournal.com]

спасибо - я уже вроде как оклемался немного - завтра займусь :)

[sam-buddy.livejournal.com]

select * from table sort by id :)

[vdas.livejournal.com]

drop table nax; / :)