Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6] 7 8   вперед  Ctrl      все
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег

Ты fix тут увидел?

увидел, сдался тестировать

видать в буффере был древний(без фикса) вариант, и я уже не присмотрелся

звиняйте, поспешил

.....
stax
18 ноя 20, 16:30    [22234737]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


Немного изменил условия, интервалы в целых числах, как в предыдущих задачах и добавил немного данных:

0   1   2   3   4   5   6   7   8...9...10...11...12...13...14....20.23...25

|--------------------------------------a------------------------------------|
|---b---|
|---c---|
|---d---|
|---e---|
|-f-|
|---------g--------|
|--h---|
|--i--|
|--j--|
|-k-|


with t (lvl, x1, x2) as
(
select 'a', 0, 25 from dual union all
select 'b', 2, 4 from dual union all
select 'c', 1, 3 from dual union all
select 'd', 4, 6 from dual union all
select 'e', 3, 5 from dual union all
select 'f', 7, 8 from dual union all
select 'g', 9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
)



select *magic* from t;
-- result:
+------+-------------+-----------+
| a | 0 | 0 |
| c | 1 | 1 |
| e | 3 | 5 |
| d | 6 | 6 |
| f | 7 | 8 |
| g | 9 | 9 |
| h | 10 | 11 |
| i | 12 | 12 |
| j | 13 | 14 |
| a | 15 | 19 |
| k | 20 | 23 |
| a | 24 | 25 |
+------+-------------+-----------+


Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).
18 ноя 20, 17:00    [22234770]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Stax
НеофитSQL
Жаль, критерий трудно определить объективно.

У меня получилось так.


должно быть две строки?

.....
stax


Нарушено условие задачи, интервалы одного уровня касаются.
18 ноя 20, 17:38    [22234790]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
graycode
Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).
имхо для больших наборов с большим количеством цветом наиболее эффективное решение было бы unpivot + sort + pl/sql цикл с ассоциативными массивами для не закончившихся интервалов (и удалением закончившихся). Сейчас пока некогда, да и довольно просто реализуется, так что попозже наваяю, если кто-то не сподобится сделать это раньше.
18 ноя 20, 17:45    [22234802]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax,

Пакет под тестирование производительности был сделан, таблица здесь 22233322
create table t(x1 int, x2 int, c varchar2(10), flag varchar2(3));

Сам тест кандидатов на лучшее время выполнения 22233403.
18 ноя 20, 17:46    [22234804]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


Немного изменил условия, интервалы в целых числах, как в предыдущих задачах и добавил немного данных:

0   1   2   3   4   5   6   7   8...9...10...11...12...13...14....20.23...25

|--------------------------------------a------------------------------------|
|---b---|
|---c---|
|---d---|
|---e---|
|-f-|
|---------g--------|
|--h---|
|--i--|
|--j--|
|-k-|


with t (lvl, x1, x2) as
(
select 'a', 0, 25 from dual union all
select 'b', 2, 4 from dual union all
select 'c', 1, 3 from dual union all
select 'd', 4, 6 from dual union all
select 'e', 3, 5 from dual union all
select 'f', 7, 8 from dual union all
select 'g', 9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
)



select *magic* from t;
-- result:
+------+-------------+-----------+
| a | 0 | 0 |
| c | 1 | 1 |
| e | 3 | 5 |
| d | 6 | 6 |
| f | 7 | 8 |
| g | 9 | 9 |
| h | 10 | 11 |
| i | 12 | 12 |
| j | 13 | 14 |
| a | 15 | 19 |
| k | 20 | 23 |
| a | 24 | 25 |
+------+-------------+-----------+


Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).


Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).
18 ноя 20, 17:46    [22234806]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).

Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков.
18 ноя 20, 17:52    [22234813]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL
Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).

Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков.


Зря изменил. Координаты для науки, кубики для детей :)

Теперь на иллюстрации длины отрезков не совпадают, и ответ все равно неверный.

По координатам должно быть: c[1-3] (так в оригинале)
По "кубикам" должно быть: c(1,2)
У тебя в ответе: c(1,1)
18 ноя 20, 18:22    [22234826]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
Почти линейный PL/SQL к 22232077
Кобанчег
задачка посложнее.


+
declare
  type varchars is table of varchar2(10);
  type avarchars is table of varchar2(10) index by varchar2(10);

  a_colors avarchars;
  idx varchar2(10); 
  x number;
  
  cursor c_data is 
      with t (x1, x2, c, flag) as
      (
                select 1, 4, 'red', 'src' from dual
      union all select 7, 10, 'yellow', 'src' from dual
      union all select 13, 16, 'red', 'src' from dual
      --union all select 3, 14, 'black' from dual
      union all select 3, 7, 'black', 'tgt' from dual
      union all select 9, 11, 'black', 'tgt' from dual
      union all select 13, 14, 'black', 'tgt' from dual
      --
      union all select 16, 19, 'blue', 'tgt' from dual
      union all select 18, 22, 'green', 'src' from dual
      union all select 22, 25, 'black', 'tgt' from dual
      union all select 26, 28, 'red', 'src' from dual
      union all select 29, 30, 'red', 'tgt' from dual
      union all select 32, 33, 'black', 'tgt' from dual
      )
      select *
      from t
      unpivot (x for type in (x1 as 1, x2 as 2))
      order by x, type;
      
   function iterate( idx in out nocopy varchar2, arr in out nocopy avarchars) 
      return boolean
   as pragma inline;
   begin
      if idx is null
         then idx:=arr.first; 
         else idx:=arr.next(idx);
      end if;
      return idx is not null;
   end;
 
  function keys(a in out nocopy avarchars) return varchars as
     res varchars:=varchars();
     idx varchar2(10);
     pragma inline;
  begin
     while iterate(idx,a) loop
        res.extend;
        res(res.count):=idx;
     end loop;
     return res;
  end;
begin
   for r in c_data loop
      if r.type=1 then
         a_colors(r.c):=r.c;
         x:=r.x;
      else
         a_colors.delete(r.c);
         x:=r.x+1;
      end if;
      
      dbms_output.put(x||': '||a_colors.count()||' colors:');
      while iterate(idx, a_colors) loop
         dbms_output.put(' '||a_colors(idx));
      end loop;
      dbms_output.put_line('.');
   end loop;
end;

+ output
1: 1 colors: red.
3: 2 colors: black red.
5: 1 colors: black.
7: 2 colors: black yellow.
8: 1 colors: yellow.
9: 2 colors: black yellow.
11: 1 colors: black.
12: 0 colors:.
13: 1 colors: black.
13: 2 colors: black red.
15: 1 colors: red.
16: 2 colors: blue red.
17: 1 colors: blue.
18: 2 colors: blue green.
20: 1 colors: green.
22: 2 colors: black green.
23: 1 colors: black.
26: 0 colors:.
26: 1 colors: red.
29: 0 colors:.
29: 1 colors: red.
31: 0 colors:.
32: 1 colors: black.
34: 0 colors:.
18 ноя 20, 18:41    [22234844]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Есть простое, в четыре строчки, решение для частного случая, когда при закрашивании не формируются дырки.

Общее решение пока не придумал. И по слоям, и по координатам накапливается state.
18 ноя 20, 18:43    [22234848]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
graycode
Немного изменил условия
зачем? в чем смысл?
18 ноя 20, 18:44    [22234849]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
xtender,

В пятничных задачах есть смысл?

На тетрис похоже))
18 ноя 20, 18:48    [22234853]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
graycode
xtender,

В пятничных задачах есть смысл?

На тетрис похоже))
я не понял смысла изменения, если от перевода в целые становится лишь легче, а изменение окончаний вообще странно...
18 ноя 20, 19:05    [22234866]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
По "кубикам" должно быть: c(1,2)
У тебя в ответе: c(1,1)

Да, ошибся должно быть c(1,2).
18 ноя 20, 19:10    [22234868]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Правильный ответ для задачи по отрезкам с координатами:
Также подправил картинку, а то левая часть была отрезками, а правая - "кубиками"


0 1 2 3 4 5 6 7 8...9...10...11...12...13...14...20...23...25

|--------------------------------------a----------------------------------|
|---b---|
|---c---|
|---d---|
|---e---|
|-f-|
|---------g--------|
|--h-|
|--i-|
|--j-|
|--k-|

LVL X1 X2
a 0 1
c 1 3
e 3 5
d 5 6
a 6 7
f 7 8
a 8 9
g 9 10
h 10 11
g 11 12
i 12 13
j 13 14
a 14 20
k 20 23
a 23 25

Исходные данные (от graycode), плюс мое решение "в лоб" для проверки:
with t (lvl, x1, x2) as
(
select 'a',  0, 25 from dual union all
select 'b',  2,  4 from dual union all
select 'c',  1,  3 from dual union all
select 'd',  4,  6 from dual union all
select 'e',  3,  5 from dual union all
select 'f',  7,  8 from dual union all
select 'g',  9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
),
p (lvl,x1,x2) as (
select lvl, x, lead(x) over (order by x) from (
  select * from (
    select x, lvl, lag(lvl) over (order by x) plvl from (
      select x, (select max(lvl) from t where x>=x1 and x <x2) lvl from (
        select level-1 x from dual where level-1 >= (select min(x1) from t) 
          connect by level <= (select max(x2) from t)+2) 
      ) 
    ) where nvl(lvl,'-') != nvl(plvl,'-')
  )
)
select * from p where lvl is not null
18 ноя 20, 19:51    [22234889]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL,

Так если координаты, зачем кубики нагенерил?))

PS: решения с генерацией диапазона не очень интересны даже для кубиков, а для координат не подходят вообще.
18 ноя 20, 21:26    [22234939]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL,

Так если координаты, зачем кубики нагенерил?))

PS: решения с генерацией диапазона не очень интересны даже для кубиков, а для координат не подходят вообще.


Не кубики, а пробные значения :-Р

Интервалы пространства и времени имеют практическую ценность для произвольной точности, кубики упрощают задачу до целых чисел.

Кубики в постановке задачи элементарно переводятся в отрезки:
Х1-х2. -> [х1,х2+1)

Если отрезки целочисленные, обратное преобразование также есть, вычесть единичку.

Для работы с данными отрезки лучше, для распечатки можно перевести в кубики, в зависимости от того кто читать будет.
18 ноя 20, 22:36    [22234975]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL,

Не, тут уж или крестик или трусы)))
18 ноя 20, 22:39    [22234978]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode,


Лол, хорошо. +0.5 для подобных.


В pl/sql решается просто вдоль Х через стэк глубиной lvl.
В sql нащупывается рекурсивное решение, но пока не сделал
18 ноя 20, 22:55    [22234987]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
Нарушено условие задачи, интервалы одного уровня касаются.
Перечитай условие. Подумай ещё. Посмотри в чем фикс. Всё же было обсуждено.
graycode
Сам тест кандидатов на лучшее время выполнения 22233403.
Я конечно рад, что ты так проникся моим тестом 9-ти летней давности, но ты видимо так и не понял про сортировки и темп.
В той задаче были совсем другие объемы и поэтому не было надобности в alter session которые имеются в новом тесте.
19 ноя 20, 08:52    [22235082]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set
Смотря в чем измерять сложность. Однозначно это более общий вариант, но "общесть" отрубает многие приёмы которые можно было бы применять в частном случае.
xtender
Почти линейный PL/SQL к 22232077
Кобанчег
задачка посложнее.
Но ведь это абсолютный overkill когда число "слоёв" фиксировано.
+ output
select *
from
(
select x1,
       decode(src_active, 1, src_c) || decode(src_active+tgt_active, 2, ', ') || decode(tgt_active, 1, tgt_c) colors
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
/

        X1 COLORS
---------- --------------
         1 red
         3 red, black
         5 black
         7 yellow, black
         8 yellow
         9 yellow, black
        11 black
        12
        13 red, black
        13 red, black
        15 red
        16 red, blue
        17 blue
        18 green, blue
        20 green
        22 green, black
        23 black
        26 red
        26 red
        29 red
        29 red
        31
        32 black
        34

24 rows selected.
19 ноя 20, 09:03    [22235086]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

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

Ну и без завязывания на частные случаи. То есть
- границы не обязательно целочисленные - никакой генерации
- число приоритетов неограничено - никакого хардкодига
итд

У меня более одного варианта.
19 ноя 20, 09:09    [22235090]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

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

Ну и без завязывания на частные случаи. То есть
- границы не обязательно целочисленные - никакой генерации
- число приоритетов неограничено - никакого хардкодига
итд

У меня более одного варианта.


и
1) а,b и b,c не пересекаются? соприкасаются? можно/надо слить в один a,c?
2) возможен ли диапазон a,a (зависит от ответа на п1)
3) одного цвета соприкасающиеся обьеденяем?
4) "чистый" sql или/и pl/sql?
итд

ps
у Неофита больше интервальчиков, мож и на его with тестировать
pss
жаль graycode забанили от публикаций

.....
stax
19 ноя 20, 09:57    [22235107]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
1) а,b и b,c не пересекаются? соприкасаются? можно/надо слить в один a,c?
Соприкасаются (но не пересекаются) и сливаются.
Мы тут говорим про действительные числа уже.
Stax
2) возможен ли диапазон a,a (зависит от ответа на п1)
Я думаю это некорректные данные. По логике подразумевается что отрезки типа [start..end) то есть конец не входит.
Stax
3) одного цвета соприкасающиеся обьеденяем?
Да
Stax
4) "чистый" sql или/и pl/sql?
Чистый эксуэль конечно же!

Stax
жаль graycode забанили от публикаций
Да, совершенно непонятно за что забанили. Никаких предупреждений.
Более того это вообще может быть рандомный модератор любого форума.
Ну наверное самому забаненому что-то ясно.
19 ноя 20, 10:48    [22235134]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax,

Я тестировал на этом наборе
with ranges (name, range_start, range_end) as
(
select 'a', 0, 7 from dual
union all select 'b', 2, 4 from dual
union all select 'c', 1, 3 from dual
union all select 'd', 4, 6 from dual
union all select 'e', 3, 5 from dual
--
union all select 'x', 3, 3.1 from dual
union all select 'y', 3.5, 3.7 from dual
union all select 'z', 3.9, 5.1 from dual
union all select 'a', 8, 9 from dual
)

Последний отрезок ломает решения икстендера потому что до него дырка, но легко допиливается.
19 ноя 20, 10:50    [22235137]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6] 7 8   вперед  Ctrl      все
Все форумы / Oracle Ответить