Как мы делали олимпиаду по SQL

    В самом начале осени 2016 года руководство поставило мне задачу подготовить техническую часть олимпиады по SQL. Обсудив ситуацию с коллегами, в том числе с бывшими, я был ткнут (ткнён?) в статью, где в декларативном стиле на SQL решалась задача по построению кратчайшего выхода из лабиринта. Собрав в одну кучку части запроса и запустив его на настоящей базе, я прошептал "магия!.." и понял, что олимпиаде быть.


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


    Вводная


    Олимпиада 2016/17 гг. проводилась уже в десятый раз, как бы юбилей. Хоть олимпиада и заявлена международной, основной её язык русский, так что лично я бы назвал её скорее Всесоюзной. Я готовил техническую часть конкурса по языку программирования SQL (были ещё и другие номинации). По идее вторым организатором этой номинации являлся Oracle, но их представителей я так и не встретил. Так что единственным следом от Oracle осталось то, что использовалась оракловая база данных со всей соответствующей спецификой SQL.


    Вот отчёт о финале нашей олимпиады 2016/17 на официальном сайте: http://world-it-planet.org/press/news/detail.php?ID=323774


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


    Так как никаких дополнительных указаний мне руководством озвучено не было (полный карт-бланш), основной целью проведения олимпиады я определил популяризацию языка SQL. Кстати говоря, это действительно один из немногих реально используемых в жизни декларативных языков программирования. А если на горизонте появляются базы данных, особенно промышленные, которые с серверами, то альтернатив вообще реально нет — индустриальный стандарт де-факто. Плюс очень многие нишевые решения используют SQL-подобный синтаксис запросов, когда надо чего-то выбрать и сгруппировать или отсортировать. Например, JQL в JIRA или язык запросов в Sphinx Search Engine.


    Да, так вот, основная цель была поставлена — популяризация SQL. Чтобы больше народу про SQL знало и на SQL писать умело. Тогда и у нас с кадровым резервом будет всё в порядке. Попутно мы конечно будем рекламировать себя и искать таланты. Это само собой. Но главное — привлечь внимание к SQL. А раз популяризировать, значит должно быть интересно.


    Организаторы анонсировали следующий расклад проведения конкурса: два заочных тура и очный финал. Общую концепцию определим так. Первый тур отборочный, нужно отсеять как можно больше тех, кто не в теме. Второй тур — самое интересное. Даём задачи типа "а слабо в один запрос SQL сделать что-то-там-такое?" Времени даём побольше, чтобы была возможность поразмыслить, но ограниченно, чтобы рассиживаться было некогда. Очный финал в том же духе провести нельзя, за три (да пусть хоть даже и за все восемь) часа финала придумать что-то эдакое на SQL проблематично. То есть будет блиц, куда ж деваться. Это конечно не лучший способ определять самого сильного программиста, но всё же чуть лучше, чем просто спросить генератор случайных чисел.


    И подготовительная работа закипела.


    Первый тур, отборочный. Декабрь 2016


    Тут я конечно воспользовался наработками своих коллег от того же самого конкурса, но в предыдущем году, за что им отдельное спасибо. У IT-Планеты есть специальный движок, который проводит тестирование. Была собрана база из сотни с лишним вопросов с вариантами ответов, которые требуется выбрать. Участнику выдаётся 30 вопросов. Даже если участник принимал участие в прошлом году, больше одного-двух вопросов вряд ли повторится. И особой погоды это никому не сделает.


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


    Ожидалось, что такое сито хорошо распределит участников по уровню знаний SQL вообще и Oracle SQL в частности, более знающие займут более высокую позицию. Тридцать вопросов на каждого участника статистически нивелируют "особенности" отдельных вопросов. Плюс терапевтический эффект для участников, что всё серьёзно и пощады не будет.


    Практика подтвердила правильность ожиданий, действительно участники достаточно неплохо распределились по Пуассону(?) с семью правильно отвеченными вопросами в среднем. Один участник даже сумел все 30 вопросов правильно ответить (повезло, чего уж там!), 29 правильных ответов уже были у четверых участников. Шесть человек прошли чисто, не угадав ни разу. Короче, то что надо. Такой подход позволил выбрать подходящий проходной балл, чтобы сформировать нужное количество участников второго тура, отобрав лучших. По планам организаторов во второй тур должно было пройти около двух сотен участников с некоторыми вполне разумными ограничениями, максимизирующими разнообразие участников по странам и вузам.


    Второй тур, основной. Март 2017


    Второй тур был несомненно самым интересным событием всей этой олимпиады. Именно в нём можно было попробовать свои силы в хардкорной магии SQL.


    Так как использовать повторно эти задачи всё равно не получится, они уже засветились, приведу их здесь. Отчасти эта публикация и задумывалась как повод поделиться подготовленными задачами для дальнейшей популяризации языка SQL. Каждая задача, образно говоря, начинается словами "В один SQL-запрос..." и далее идёт Something Completely Different © Monty Python. К сожалению в одну фразу уложить задачи было нельзя, приходилось добавлять многословные пояснения для корректной формулировки условия, а также приводить для пояснения тестовые данные и пример решения на этих тестовых данных.


    Я очень старался, чтобы задачи имели выраженный вау-эффект типа "да неужели такое вообще возможно на SQL", и чтобы быть подальше от традиционной олимпиадной тематики, требующей довольно специфических навыков. Сложность каждой задачи заключалась в первую очередь в том, чтобы представить (ну и в дальнейшем реализовать) сам декларативный способ решения вполне себе самостоятельной и нетривиальной даже для классического программирования задачи. Также мы потребовали у участников составить текстовое пояснение к каждой задаче. С одной стороны нам были интересны люди, которые могут внятно излагать свои мысли, и таких хотелось поощрить. С другой стороны, если бы ответы на задачи второго тура прислали все приглашённые участники, то такие пояснения сильно бы нам помогли в проверке. Забегая вперёд скажу, что из 200+ участников второго тура прислали ответы только 34 человека. Что не так много, но (как ни удивительно) приблизительно равно количеству активных участников второго тура в предыдущем году. Это позволило нам тщательно в ручном режиме и на два раза проверить все работы, и позвать на финал действительно самых достойных.


    Второй тур по расписанию организаторов начинался первого марта. На решение пяти задач мы дали полторы недели, даже чуть больше, до 23:59 12 марта. Так чтобы конец периода приходился на выходные после 8 марта. Чтобы участники могли ударно потрудиться в последние два дня и при этом не слишком портить им их личную жизнь. Тестовые испытания на себе и коллегах показывали, что на каждую задачу нужно полдня-день. Плюс какое-то время на оформление, плюс настроиться и раскачаться. То есть времени должно быть достаточно, но без излишка.


    Ну-с, погнали про задачи. Спрячу под спойлер, чтобы места они занимали поменьше.


    Задача №1. Календарь

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


    with param(year, c, r) (…)

    где, соответственно,


    • year – год календаря
    • c – количество столбцов матрицы календаря
    • r – количество строк матрицы.

    Месяцы расположены в клетках матрицы календаря по порядку слева направо и потом сверху вниз. Числа в каждом месяце расположены по дням недели, первый день недели в первом столбце и так далее. Начало недели должно соответствовать настройкам локализации базы на момент запуска запроса. Название месяца берётся тоже из настроек локализации и выводится по центру над числами. Между месяцами нужно оставить промежуток, чтобы числа соседних месяцев «не слипались». Самой первой строчкой должен идти выровненный по центру год. Пустых строк быть не должно.


    Например, при следующих заданных параметрах:


    with param(year, c, r) as (select 2016, 3, 4 from dual)

    должен получиться следующий вывод запроса:


                                      2016
             Январь                 Февраль                   Март
                  1  2  3     1  2  3  4  5  6  7        1  2  3  4  5  6
      4  5  6  7  8  9 10     8  9 10 11 12 13 14     7  8  9 10 11 12 13
     11 12 13 14 15 16 17    15 16 17 18 19 20 21    14 15 16 17 18 19 20
     18 19 20 21 22 23 24    22 23 24 25 26 27 28    21 22 23 24 25 26 27
     25 26 27 28 29 30 31    29                      28 29 30 31
             Апрель                   Май                     Июнь
                  1  2  3                       1           1  2  3  4  5
      4  5  6  7  8  9 10     2  3  4  5  6  7  8     6  7  8  9 10 11 12
     11 12 13 14 15 16 17     9 10 11 12 13 14 15    13 14 15 16 17 18 19
     18 19 20 21 22 23 24    16 17 18 19 20 21 22    20 21 22 23 24 25 26
     25 26 27 28 29 30       23 24 25 26 27 28 29    27 28 29 30
                             30 31
              Июль                   Август                 Сентябрь
                  1  2  3     1  2  3  4  5  6  7              1  2  3  4
      4  5  6  7  8  9 10     8  9 10 11 12 13 14     5  6  7  8  9 10 11
     11 12 13 14 15 16 17    15 16 17 18 19 20 21    12 13 14 15 16 17 18
     18 19 20 21 22 23 24    22 23 24 25 26 27 28    19 20 21 22 23 24 25
     25 26 27 28 29 30 31    29 30 31                26 27 28 29 30
            Октябрь                  Ноябрь                 Декабрь
                     1  2        1  2  3  4  5  6              1  2  3  4
      3  4  5  6  7  8  9     7  8  9 10 11 12 13     5  6  7  8  9 10 11
     10 11 12 13 14 15 16    14 15 16 17 18 19 20    12 13 14 15 16 17 18
     17 18 19 20 21 22 23    21 22 23 24 25 26 27    19 20 21 22 23 24 25
     24 25 26 27 28 29 30    28 29 30                26 27 28 29 30 31
     31

    Задача №2. Переливания

    Имеются два сосуда ёмкостью 3 и 5 литров и кран с водой. Можно переливать воду из одного сосуда в другой (до тех пор, пока один из них не наполнится или не станет пустым), выливать воду (только полностью) и наполнять любой сосуд из крана доверху. Требуется найти все возможные варианты переливаний, которые позволяют отмерить ровно 4 литра. Чтобы исключить зацикливание, отбрасываются варианты, где состояние наполненности сосудов повторяется.


    Запрос SQL должен вывести все возможные варианты переливаний в следующем виде: для каждого из вариантов вывести цепочку переливаний в виде пар чисел, показывающих количество воды в каждом сосуде на соответствующем шаге. Числа отделяются друг от друга минусом, а пары – запятой и пробелом.


    Требуется решить задачу в общем виде, параметрами задаются ёмкость первого v1 и второго v2 сосудов и результат res, который нужно получить в результате переливаний. Пример условий:


    with param(v1, v2, res) as (select 3, 5, 4 from dual)

    Пример вывода:


    PATH
    ---------------------------------------------------------------------------------
    0-0, 3-0, 3-5, 0-5, 3-2, 0-2, 2-0, 2-5, 3-4
    0-0, 3-0, 0-3, 3-3, 3-5, 0-5, 3-2, 0-2, 2-0, 2-5, 3-4
    0-0, 3-0, 0-3, 3-3, 1-5, 0-5, 3-2, 0-2, 2-0, 2-5, 3-4
    ...

    Задача №3. О пути

    Есть неориентированный граф, заданный вершинами и рёбрами. Даны длины рёбер и название начальной и конечной вершины. Требуется одним SQL-запросом найти путь с кратчайшим расстоянием из начальной в конечную вершину. Результат должен быть представлен в виде двух значений:


    1. строка пути, перечислены названия вершин через минус,
    2. длина пути (сумма длин рёбер).

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


    Количество рёбер в графе разумно ограничено, не более 50 рёбер.


    На следующих тестовых данных:


    with edges (from_node, to_node, range) as (
      select 'Москва', 'Санкт-Петербург', 706 from dual union all
      select 'Москва', 'Воронеж', 516 from dual union all
      select 'Москва', 'Екатеринбург', 1793 from dual union all
      select 'Москва', 'Алматы', 3956 from dual union all
      select 'Москва', 'Краснодар', 1345 from dual union all
      select 'Москва', 'Новосибирск', 3356 from dual union all
      select 'Москва', 'Нижний Новгород', 421 from dual union all
      select 'Москва', 'Чита', 6274 from dual union all
      select 'Москва', 'Киев', 856 from dual union all
      select 'Москва', 'Ярославль', 272 from dual union all
      select 'Москва', 'Новокузнецк', 3723 from dual union all
      select 'Москва', 'Красноярск', 4141 from dual union all
      select 'Москва', 'Белгород', 666 from dual union all
      select 'Москва', 'Курск', 524 from dual union all
      select 'Москва', 'Владивосток', 9141 from dual union all
      select 'Воронеж', 'Курск', 237 from dual union all
      select 'Воронеж', 'Белгород', 265 from dual union all
      select 'Курск', 'Белгород', 146 from dual union all
      select 'Ярославль', 'Нижний Новгород', 856 from dual union all
      select 'Екатеринбург', 'Новосибирск', 1598 from dual union all
      select 'Новосибирск', 'Чита', 2923 from dual union all
      select 'Новосибирск', 'Красноярск', 790 from dual union all
      select 'Новокузнецк', 'Красноярск', 751 from dual union all
      select 'Красноярск', 'Чита', 2139 from dual union all
      select 'Чита', 'Владивосток', 2861 from dual )
    , param(begin_node, end_node) as (select 'Краснодар', 'Владивосток' from dual)

    Должен быть получен следующий результат:


    PATH                                                      LEN
    -------------------------------------------------- ----------
    Краснодар-Москва-Чита-Владивосток                       10480
    Краснодар-Москва-Новосибирск-Чита-Владивосток           10485
    Краснодар-Москва-Владивосток                            10486

    Задача №4. Калькулятор

    Задано арифметическое выражение в виде строки. Требуется одним SQL-запросом посчитать значение выражения. Выражение содержит знаки следующих операций: сложение, вычитание, умножение, деление, возведение в степень, унарный минус и скобки. Унарный минус может попадаться только в начале выражения или после открывающей скобки. Числа могут содержать десятичную часть и по формату полностью соответствуют типу NUMBER в текущих языковых настройках БД. Для большей наглядности выражения могут содержать символы пробела. Длина выражения разумно ограничена: не более 50 операндов, глубина вложенности скобок не более 20. Выражение всегда корректное.


    Запрос должен выдать одно значение в формате NUMBER.


    Пример тестовых данных:


    with param(expr) as ( select '(-1 + 5^(1/2) ) / 2' from dual )

    Пример результата работы запроса на этих данных:


                                                  VAL
    -------------------------------------------------
              ,61803398874989484820458683436563811772

    Задача №5. Лабиринт

    Задан лабиринт в виде пронумерованных строк. Стены помечены символами «#», точка входа «s» и выхода «e». За границы выходить нельзя, номера строк идут по порядку, длина всех строк одинаковая. Требуется одним SQL-запросом нарисовать поверх лабиринта символами «*» кратчайший путь от входа к выходу (один из них, если путей несколько).


    Размер лабиринта ограничен так, что возможное количество вариантов прохода по лабиринту (без внутренних петель) не превосходит 10000.


    Пример тестовых данных:


    with maze(linenum, line) as (
      select 01,'##   ###   ######' from dual union all
      select 02,'s  #     #       ' from dual union all
      select 03,'#### ### # ##### ' from dual union all
      select 04,'   #   #   #     ' from dual union all
      select 05,' # ### ######### ' from dual union all
      select 06,' #              e' from dual )

    Пример результата работы запроса на этих данных:


    ##***###   ######
    s**#*    #       
    ####*### # ##### 
       #***#   #     
     # ###*######### 
     #    **********e

    Конечно, будь у нас больше времени, мы бы сделали задачи ещё лучше. Но и так получилось неплохо. По каждой из задач были свои неожиданности и подводные камни.


    Например, внезапно очень нетривиальной оказалась первая задача, про календарь. Сложности у участников вызвала уже динамически формируемая матрица, а также внезапно далеко не все сумели правильно сгенерировать все дни года. С учётом високосности их обычно 365 или 366. Но в 1582 году в нашем григорианском календаре отсутствуют дни с 5 по 14 октября. Корректно обработать 1582 год удалось немногим. Плюс неделя в разных локалях с разного дня начинается. При таком количестве неожиданных засад, никто даже не наступил на грабли с выравниванием названий месяцев. Все, кто до этого добрался, не сломавшись по ходу дела, пользовались функциями, которые выдают неправильную длину слова в кодировке UTF8.


    Задача №3 "о пути" является вариацией на тему задач о коммивояжере. Города взяты те, в которых есть наши представительства, а расстояния реально соответствуют длине автомобильных дорог из атласов. Уже разослав условия мы обнаружили, что не оговорили явно наличие/отсутствие циклов в путях. Как-то даже в голову сходу не пришло рассматривать, что задачу коммивояжера можно решать с циклами. При проверке пришлось считать оба подхода верными. Но только если уж участник допускает циклы, то чтобы все правильные решения в таком подходе были найдены. Проверочные тесты пришлось дорабатывать. Из неожиданного выяснилось, что не все участники знакомы с таким фундаментальным понятием в программировании, как рекурсия. В решении одного упорного человека рекурсия была сделана вручную на вложенность в глубину до 11 уровня. Для тестового примера из условия задачи этого хватило, на другие наши тесты конечно же нет, там мы в том числе и всякой экзотики набрали. Удивительно было это увидеть, я предполагал, что студенты и молодые специалисты, которые пишут на SQL (а это явно не может быть первым языком программирования), про рекурсию должны бы знать и уметь применять её на практике. Без этого в программировании ну совсем никак.


    Задача №5 "лабиринт" является лично для меня самой волшебной, именно ею был навеян весь второй тур олимпиады. Хотя после первых четырёх задач она уже, наверное, не вызывает того эффекта. В условиях специально оговорили, что решение в лоб с перебором всех вариантов сработает. Кстати, долго думали, как это ограничение вообще можно сформулировать. Пустой лабиринт 7х7 без стен уже обсчитывается долго, так как количество вариантов прохода по нему большое. С другой стороны, лабиринт с большим количеством стен (и, соответственно, малым количеством вариантов прохода) решается быстро даже в размерах 60х60. Алгоритмически правильнее было конечно воспользоваться при решении этой задачи волновым алгоритмом. Такой метод работает быстро и оптимально находит кратчайший путь, отбрасывая заведомо более плохие варианты, но сложнее в реализации. Очень приятно было увидеть эти соображения в сопроводительном описании к этой задаче от одного из участников. Но никто волновой алгоритм так и не реализовал. Впрочем, и мы тоже не стали.


    Задача №4 "калькулятор" являлась самой технически сложной. Предполагалась двухходовка: сперва перевести выражение во что-то более удобоваримое (ПОЛИЗ или стековую нотацию), а потом уже посчитать результат. Действительно, решивших её участников оказалось меньше всего. Кое-кто пробовал решать с помощью регулярных выражений, по очереди выхватывая очередное подвыражение, которое можно посчитать, и заменяя его на посчитанное значение, но все такие реализации оказались с ошибками, особенно легко ломаясь на нечеловеческих выражениях типа "(( (-(( ((((( - ( (-(-(-( ( - ((-,0-,0))) ) ))))) ) ) ))))) ) ) ". Наша реализация была тоже неидеальна, реализовать стек на SQL пришлось строками, а это ограничивает глубину вложенности стека техническими ограничениями на длину строковых полей в базе.


    Задача №2 о переливаниях была взята из корпоративной вики, где она когда-то предлагалась нашим программистам от наших же программистов для разминки ума. Наши решили её сперва на разных классических языках программирования, потом на некоторых экзотических и даже эзотерических (например, brainfuck) и, в конце концов, декларативно на SQL, на чём тема и была благополучно закрыта. Грех было не использовать настолько хорошо разобранную задачу на олимпиаде.


    Кстати про brainfuck. В процессе подготовки задач был реализован интерпретатор brainfuck в один SQL-запрос. В задачи мы его выдвигать не стали, избегая двусмысленностей, связанных с названием. Но тем не менее имеем подтверждённый факт, что это реализуемо. Желающие могут повторить.


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


    Оценивались задачи по десять баллов максимально за код и по десять за сопроводительное описание. Код запускался на подготовленных наборах данных, первым из которых всегда шёл тот, который был в условии задачи. То есть правильные результаты на данных из условия задачи давали уже минимум один балл. С документацией было тяжелее, оценить объективно (хотя бы формально объективно) было проблематично. Старались, чтобы при сравнении двух разных решений более хорошая документация оценивалась в большее количество баллов.


    В присланных работах обнаружилось два кластера одинаковых решений. То есть они конечно отличались отдельными символами и где-то даже отдельными словами. И немножко форматированием. Но совершенно очевидно было, что это одно и то же. Я на самом деле думаю, что участники не списывали друг у друга, а просто вместе задачи решали. Но так как мы со свечкой рядом не стояли и не видели, кто там был настоящим автором решения, а кто просто переписал, то пришлось дисквалифицировать все работы со следами плагиата. Зачем они вообще посылали в несколько ответов одно и то же решение? Неужели думали, что никто не заметит? Не в первый раз уже сталкиваюсь с таким странным поведением у людей, когда они совершенно теряют способность к критическому мышлению. Ну неужели организатор олимпиады, отвечающий своей репутацией за проверку, не сумеет понять, что перед ним один и тот же запрос? Ну не могут два разных человека все промежуточные таблицы и поля в них придумать с одинаковыми названиями. И даже с похожими не могут.


    Пара слов о техническом оформлении. Участники должны были приготовить файл для запуска в SQL*PLUS из под нашего скрипта для автоматического тестирования. Подробности под катом, наверное не всем это будет интересно.


    Техническое оформление задач

    Решение должно было оформляться в отдельном файле, который запускался из внешнего скрипта-обёртки. Так было сделано, чтобы разделить параметры задач и решение. Параметры в виде "with params as (select 1,2,3 from dial)" были во внешнем скрипте. Вот пример скрипта-обёртки:


    set pagesize 999 linesize 999 numwidth 50 trimspool on trimout on
    set heading off verify off feedback off
    set serveroutput on size 999999
    whenever sqlerror exit
    
    spool taskX.log
    
    -- test dataset here
    with param(num) as (select 10 from dual)
    @taskX.sql
    /
    
    exit

    Тогда скрипт taskX.sql выполнится и вывод будет в файле taskX.log.


    Вот содержимое скрипта-решения taskX.sql, которое считает факториал от числа, заданного параметром param.num:


    -- = IT Planet, SQL 2016/17 =
    -- = Task X (Sample) =
    --
    -- with param(num) as (select 10 from dual)
    , seq(n, fact) as (
      select 1, 1 from dual
      union all
      select n+1, fact*(n+1)
        from seq, param
       where n < param.num
    )
    select fact as factorial
      from seq, param
     where n = num

    Сформировав таким образом запуск скрипта на всех наших специально подготовленных тестовых данных, можно потом смотреть результаты и сравнивать их с нашими "эталонными" решениями.


    Чтобы уменьшить количество ошибок при оформлении, для участников были заготовлены и разосланы файлы-шаблоны для всех задачек (файлы task[1,2,3,4,5].sql) и соответствующие им "запускалки" вместе с тестовыми данными из условий задач. Также был подготовлен и отправлен тестовый пример решения задачи, чтобы показать, как это всё должно выглядеть. Вот этот самый факториал, который выше.


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


    Итоговый протокол выверяли мы долго, но, на мой взгляд, он полностью отражал правильное ранжирование участников. В финал прошли действительно мега-человеки.


    To be continued! Объём статьи получился большим, продолжение во второй части.


    P.S. Пользуясь случаем, хочу сказать большое человеческое спасибо коллегам, которые вместе со мной участвовали в придумывании, оформлении и проведении этой олимпиады! Егор, Слава, Миша, Артём — вам в первую очередь.

    Поделиться публикацией

    Комментарии 16

      0
      языку программирования SQL

      SQL — это не язык программирования. Язык программирования — это programming language (PL), а SQL — structured query language, т.е. язык структурированных запросов.
      Его реализация в Oracle кстати имеет совмещенное название: PL/SQL, что как бы подчеркивает тот факт, что в язык запросов внесены элементы от языка программирования.
        +3
        Не совсем согласен с Вами.

        Если честно, то для меня язык программирования (ЯП) — это всё, на чём человек может объяснить компьютеру, что тот должен делать. Так что, IMNSHO, SQL — это несомненно язык программирования. Специализированный. И Википедия тоже со мной согласна. Да, если бы язык имел устоявшееся название СЯЗ (Структурированный язык запросов), то с точки зрения русского языка его бы чаще называли языком запросов, как это и происходит в английском. А так, все формальные языки, придуманные для программирования ЭВМ, вполне корректно называть ЯП.

        PL/SQL это как бы не SQL с дополнениями ЯП, а совершенно самостоятельный язык программирования с встроенной возможностью использовать в нём SQL. Тоже, кстати, довольно специализированный. Возможно, название было взято по аналогии с PL/I, который был популярен во время появления на рынке PL/SQL, хотя корнями PL/SQL ближе к ADA.

        У меня просьба к коментаторам: если Вам кажется, что в тексте ошибка, то лучше в личные сообщения.
          +1
          Это не ошибка, а разница подходов к пониманию термина, что вы, собственно, и описали. Я потому и вынес это в комментарий, чтобы озвучить собственное мнение по этому поводу. Я категорически не согласен с формулировкой «язык программирования (ЯП) — это всё, на чём человек может объяснить компьютеру, что тот должен делать». Так у нас и Markdown и HTML превратятся в языки программирования, тогда как это языки разметки.
          Ну и согласна с вами русскоязычная википедия, а вот англоязычная — нет. Да и упоминать Википедию как экспертный источник знаний — вещь сомнительная.
          По анлгоязычной Википедии, есть общий класс «Computer language», к которому относятся языки программирования, запросов, разметки и т.д. и т.п.
          https://en.wikipedia.org/wiki/Computer_language

          Я, собственно, не планирую с жаром отстаивать свое мнение и вести активную дискуссию по поводу, просто небольшая ремарка, не имеющая отношения к смысловому наполнению статьи — статья хорошая и интересная, задачки крутые, на мой взгляд, я может быть даже попробую их порешать, поэтому поддерживаю отсутствие готовых ответов в статье — интереснее решать, не имея искушения в виде возможности подглядеть правильный ответ.
            0
            За конструктивный подход спасибо, так можно и подискутировать. Хотя я несколько опасаюсь Вашего «категорического несогласия» (цитата). Зачем же категорично так?

            Английская Википедия тоже называет SQL специализированным языком
            (DSL), используемым в программировании. По английски просто писать, что query language является ещё каким-то language — это толочь воду в ступе, название самоопредеяющее.

            На самом деле порывшись в Википедии я так понимаю, что Вы различаете компьютерные языки и в них подкласс языков программирования, а я все компьютерные языки называю ЯП. Если честно, не знаю насколько это сложившаяся терминология, даже несморя на профильное образование и десятилетия работы в области ИТ.

            В моём представлении компьютерным языком можно назвать вообще что угодно, связанное с языком и компьютером. Например то, что мне какая-то работающая на компьютере программа покажет на экране. Текстовый вывод любой программы, особенно если он человеко-подобный (типа введите число) можно назвать компьютерным языком. Или все эти текстовые протоколы, на которых общаются сами программы (http, smtp и прочее). Сюда же, кстати, SQL вписывается. Короче слишком общо, мне не нравится. Хотя да, языки разметки в ЯП записывать тоже не совсем корректно. С третьей стороны на том же XML есть XSLT и это уже ЯП в самом что ни на есть программистском понимании. Да и на CSS порой такой интерактив делают, что ой. Так что по крайней мере не всё так однозначно.

            И ещё хочу пару слов в защиту Википедии сказать. Почему-то её принято походу пинать, что она не является авторитетом. Почему ж не является? Ещё как является. Истиной в последней инстанции не является, а энциклопедическим изданием является и весьма неплохим. В Hitchhikers Guide to the Galaxy ляпов куда как больше.
        0
        А решения где-то будут выложены? Хотя бы по одному к каждой задаче)
          +2
          А надо? Если делать разбор задачи, то нужно по статье на каждую. Просто опубликовать ответы, на мой вкус, неинтересно, их никто тогда не будет и пробовать решать. Ну и я не вижу никакой запредельной сложности в этих задачах.
            +1
            Ну и я не вижу никакой запредельной сложности в этих задачах.
            Для олимпиадников — понятно что её нет. А для обычного веб-разработчика, который не сталкивается с такими сложными запросами — вполне интересно было бы посмотреть на код, авось там неизвестное что-то.
              0
              А Вы не скромничайте и попробуйте сами. Это не так сложно, как кажется. Самое сложное, что там есть — это не совсем традиционное использование рекурсии. И уж точно тут нет никакой олимпиадной специфики. Подобные задачки время от времени рассматривают на sql.ru, посмотрите там на примеры разбора.
                0
                Подскажите в какую сторону копать, что читать для решения задачи про кувшины? К остальным даже не пробую пока подходить. На работе Oracle 10.2, рекурсии на практике применять не приходилось (максимум connect by для запроса значений из строки, да построения простеньких деревьев по типу parentID = ID). Почитал про рекурсии на Oracle 11 через WITH, но понимания как применить это по отношению к задаче не пришло. Догадываюсь, что результат собираются через SYS_CONNECT_BY_PATH (wm_concat бы, но он недокументированный =/).

                P.S. Работаю с Oracle SQL/PLSQL несколько лет, но уже второй раз проходя во второй тур понимаю какой я лох.
          0

          Как жаль, что я не знал про это мероприятие… Обязательно бы поучаствовал, и волновой алгоритм очень уважаю… Чего только на SQL не делал… На сайте sql-ex решал похожие задачи, в MSSQL Server, там даже на парсер выражений задачи есть, ага :) С Ораклом на работе дело имею, так что подтянулся бы заодно… Ну вы это, в следующий раз на хабре заранее анонсируйте подобные мероприятия, глядишь народу будет побольше :)

            0
            Анонсировать не могу. Сегодня мне уже на пальцах показали, что с таким только в корпоративных блогах можно, чуть учётку не заблокировали. Но Вы сами почитайте про олимпиаду. В этом году кто-то другой SQL готовит, но я вижу, что даже мою текстовку с правилами не поменяли, только даты другие.
            0
            Такой метод работает быстро и оптимально находит кратчайший путь, отбрасывая заведомо более плохие варианты, но сложнее в реализации.


            Волновой алгоритм в Оракле реализуется довольно тривиально с помощью рекурсивного запроса с «search breadth first».
              0

              Задачки в целом любопытные, но не понятно, почему именно такие. Реализация парсера, например, совершенно нетипична для sql и скорее подходит для императивных языков.


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


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

                +1
                Парсер — это в калькуляторе? Специально так подбирали условие, чтобы от парсера там был один подзапрос с регулярным выражением. Не думаю, что это было проблемой хоть для кого-то, кто взялся за решение задачи.

                А вот как Вы себе представляете задачу по ускорению аналитического запроса? Я без всяких шуток интересуюсь. Просто для меня миграция данных — это как взял лопату и «бери больше, кидай дальше», никаких сложностей сплошная рутина. Что тут оценивать-то?
                  0

                  Ускорения аналитического запроса можно добиться за счет частичной денормализации данных.
                  Допустим приложение живет на одной структуре таблиц, оптимизированной под real-time операции, но по этой структуре неудобно делать аналитику, т.к. нужно множество джойнов и вложенных подзапросов. Если аналитические запросы с джойнами выполняются часто, то будут работать долго. Но при этом данные для них подходят "вчерашние", а значит можно "на ночь" поставить пересчет денормализованных таблиц, по которым выборка будет быстрее. При этом данные за несколько лет каждую ночь пересчитывать будет накладно и нужно суметь выразить дельту за вчерашний день и корректно ее соединить с результатом расчета прошлой ночью.


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

                    +1
                    Ну нет, не годится. Даже мне, человеку довольно далёкому от оптимизации, ясно, что время работы будет зависеть много от чего, включая заполненность кэшей базы и особенности физического распределения данных по дискам (читай: от погоды на луне). То есть объективно сравнить два решения будет совершенно невозможно. Обычно оптимизацию хоть как-то меряют по количеству логических чтений. Это раз. А во-вторых, с точки зрения олимпиады, это уже не задача на SQL получается, а оптимизация работы некоей IT-системы.

                    Плюс, вопросы оптимизации они такие, мягко говоря не совсем простые по критериям. Обычно оптимизация ведётся до приемлемого уровня, планка которого для каждого конкретного случая выставляется в определённую конкретную величину, которую можно померять.

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

                    Вобщем тема оптимизации несомненно интересна и очень востребована, но олимпиада была по SQL. Как в SQL дать задачу на производительность мы придумали, см. задачи 8 и 9 финала. А аналитические хранилищи оптимизировать, это наверное не на олимпиаде, а на производстве с 09 до 18.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое