Как мы делали олимпиаду по SQL02.03.2018 14:48

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

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

В кроличью норку сюда

Вводная

Наша компания AT Consulting (http://www.at-consulting.ru) выступала генеральным спонсором этой крупнейшей на постсоветском пространстве олимпиады в сфере ИТ для студентов и молодых специалистов — IT-Планета. Олимпиада 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 марта. Чтобы участники могли ударно потрудиться в последние два дня и при этом не слишком портить им их личную жизнь. Тестовые испытания на себе и коллегах показывали, что на каждую задачу нужно полдня-день. Плюс какое-то время на оформление, плюс настроиться и раскачаться. То есть времени должно быть достаточно, но без излишка.

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

with param(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

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

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

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

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

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 из под нашего скрипта для автоматического тестирования. Подробности под катом, наверное не всем это будет интересно.

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

-- = 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

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

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

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

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

© Habrahabr.ru