SQLでolympiadをどのように実行しましたか

2016年の秋の初めに、リーダーシップは私にSQLオリンピアードの技術的な部分を準備するタスクを設定しました。 私の元を含む同僚と状況について話し合った後、私は突かれました（突かれましたか？）、SQLの宣言的なスタイルで、迷路からの最短出口を構築するタスクが解決された記事に。 要求の1つのヒープ部分に集まり、それを実際のベースで実行した後、「魔法！..」とささやいて、オリンピックがあることに気付きました。

オリンピックでのHabrの典型的な読者は少なくとも一度はいると思いますが、むしろ主催者ではなく参加者の役割でした。 私はまた別のものに行きましたが、なぜそれがいくつかのオリンピアードで面白いのか、そして他の人の必死の憧れなのかはいつも驚きでした。 この劇場がカーテンの向こう側にどのように見えるか、そしてどのようにこのオリンピアードを興味深いものにしようとしたかを示すことができます。 陰謀、スキャンダル、調査-これは起こりません。 しかし、タスクがどのように準備されたか、それらに何が期待され、何が結果であったかを説明します。

入門

2016/17オリンピック それは記念日のように、10回開催されました。 オリンピアードは国際的に宣言されていますが、その主要言語はロシア語であるため、個人的にはオールユニオンと呼んでいます。 私はコンテストの技術的な部分をSQLプログラミング言語で準備していました（他にもノミネートがありました）。 理論的には、この指名の2番目の主催者はOracleでしたが、私は彼らの代表者に会ったことがありません。 したがって、Oracleからの唯一のトレースは、関連するすべてのSQLの詳細を備えたOracleデータベースを使用したことです。

オリンピアード2016/17決勝の公式ウェブサイトでのレポートは次のとおりです。http ： //world-it-planet.org/press/news/detail.php？ID = 323774

これについては、クレジットが完了したとみなし、偵察を提供しました。 もう少し一般的な言葉と私は行動に移ります。

経営陣（フルカルテブランシュ）から追加の指示は与えられなかったため、オリンピックの主な目標はSQL言語を普及させることでした。 ところで、これは実際に実際に使用されている数少ない宣言型プログラミング言語の1つです。 また、データベース、特にサーバーを備えた産業用データベースが地平線上に登場する場合、代替手段はまったくありません。産業標準は事実上です。 さらに、多くのニッチソリューションでは、何かを選択してグループ化または並べ替える必要がある場合、SQLのようなクエリ構文を使用します。 たとえば、JIRAのJQLまたはSphinx Search Engineのクエリ言語。

はい、それで、主な目標が設定されました-SQLを普及させること。 より多くの人がSQLを知っており、SQLを上手に書くことができるように。 それから、私たちの人員予備で、すべてが大丈夫です。 道に沿って、私たちは確かに自分自身を宣伝し、才能を求めます。 言うまでもない。 しかし、主なことはSQLに注意を引くことです。 そして一度普及したら、それは興味深いはずです。

主催者は、次のコンテストのレイアウトを発表しました。2つの通信ツアーとフルタイムの決勝です。 一般的な概念は次のように定義されます。 最初のラウンドは予選です。トピックに参加していない人の多くを除外する必要があります。 2回目のラウンドは最も興味深いものです。 「しかし、1つのSQLクエリで弱くて、そういうことをしますか？」 振り返る機会があるように、より多くの時間を与えますが、座って時間がないように制限します。 同じ精神でフルタイムの決勝戦を開催することはできません。決勝戦の3時間（たとえ8時間であっても）は、SQLのようなものを思い付くのは問題です。 つまり、どこに行くべきか、電撃があります。 これは確かに最も強力なプログラマーを決定するための最良の方法ではありませんが、それでも乱数ジェネレーターに尋ねるよりも少し良いです。

そして、準備作業が沸騰し始めました。

最初のラウンド修飾子。 2016年12月

ここでは、もちろん、同じコンペティションの同僚の業績を活用しましたが、前年には、彼らに個別に感謝しています。 IT Planetには、テストを実行する特別なエンジンがあります。 100を超える質問のデータベースが、選択する回答オプションとともに収集されました。 参加者には30の質問があります。 昨年参加者が参加したとしても、1つまたは2つ以上の質問が繰り返されることはほとんどありません。 そして、それは誰にとってもあまり天気をしません。

そのため、質問を根本的に変更したり、既存の質問を揺さぶったり、気付いたいくつかの間違いを修正したり、将来の世代と離婚するために何かを残したりしました。 このような質問は、典型的なプロメトリックオンラインテストのレベルである元気なものであることがわかりました。 さらに、各質問ですべての正しいオプションを選択する必要がありましたが、それらのどれだけが正しく示されなかったかという問題が意図的に作成されました。 この場合、すべての正解が示されている質問のみがカウントされました。 つまり、単にマウスでつついて、いくつかのテストのように、平均25％が一度でもうまくいかないということです。 その結果、私自身、質問/回答の読み込みの正確性を確認しながら、すべての質問を完全に通過しながら、定期的にいくつかの質問に誤って回答しました。

このようなふるいは、SQL全般、特にOracle SQLの知識レベルに応じて参加者を適切に分散させることが期待されており、より知識のあるものがより高い地位を占めます。 各参加者の30の質問は、個々の質問の「機能」を統計的に平準化します。 さらに、すべてが深刻であり、容赦ないという参加者への治療効果。

練習は期待の正しさを確認しました;実際、参加者はポアソン（？）に従ってかなりよく分布し、平均で7つの質問に正しく答えました。 1人の参加者が30の質問すべてに正しく答えることさえできました（そこに幸運でした！）、4人の参加者はすでに正しい答えを持っています。 一度も推測せずに、6人がきれいに合格しました。 要するに、必要なもの。 このアプローチにより、2回目のラウンドで必要な数の参加者を形成するために適切な合格スコアを選択し、最適なものを選択することが可能になりました。 主催者の計画によると、約200人の参加者がかなり合理的な制限を持って第2ラウンドに参加する必要があり、国や大学ごとの参加者の多様性を最大限に高めました。

第2ラウンド、メインラウンド。 2017年3月

2回目のラウンドは、間違いなくこのオリンピアード全体で最も興味深いイベントでした。 その中で、ハードコアなSQLマジックを試すことができました。

とにかくこれらのタスクを再利用することは不可能なので、それらはすでに点灯しているので、ここに持ってきます。 部分的に、この出版物はSQL言語のさらなる普及のために準備されたタスクを共有する機会として考えられました。 比fig的に言えば、各タスクは「Into one SQL query ...」という言葉で始まり、その後、何かが完全に異なります©Monty Python。 残念ながら、タスクを1つのフレーズにまとめることは不可能でした。条件の正しいステートメントについて詳細な説明を追加し、テストデータとこれらのテストデータの解決例を明確にするために提供する必要がありました。

「SQLでこれは本当に可能か」などのタスクに顕著なワウ効果があることを確認し、非常に特殊なスキルを必要とする従来のオリンピアードのトピックから離れるように、私は一生懸命努力しました。 各タスクの複雑さは、最初に、問題の古典的なプログラミングに対しても完全に独立していて自明ではない宣言的メソッド自体を想像することで構成されていました。 また、参加者に各タスクの説明文を作成するよう要求しました。 一方で、私たちは自分の考えを明確に述べることができる人々に興味があり、そのような人々を奨励したかったのです。 一方、第2ラウンドのタスクに対する回答が招待されたすべての参加者から送信された場合、そのような説明は検証に非常に役立ちます。 今後、第2ラウンドの200人以上の参加者のうち、回答を送信したのは34人だけでした。 これはそれほどではありませんが、（驚くべきことに）前年の第2ラウンドのアクティブな参加者の数とほぼ同じです。 これにより、すべての作業を徹底的に手動で再確認し、最終的に最も価値のあるものを呼び出すことができました。

主催者のスケジュールに関する2回目のツアーは、3月1日に始まりました。 5つの問題を解決するために、3月12日23時59分まで1週間半、さらにそれ以上を与えました。 そのため、期間の終わりは3月8日以降の週末になります。 参加者が最後の2日間で一生懸命働くことができ、同時に個人の生活をあまり損なうことがないようにします。 自分と同僚のテストでは、各タスクに半日から1日かかることが示されました。 さらに、設計のための時間を加えて、調整してスイングします。 つまり、十分な時間があるはずですが、過剰ではありません。

まあ、私たちはタスクについて運転しました。 スポイラーの下に隠して、スペースを取りませんようにします。

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年には、グレゴリオ暦で10月5日から10月14日までの日はありません。 1582年を正しく処理できたのはごく少数です。 さらに、異なるロケールの週は別の日に始まります。 予想外の待ち伏せが非常に多かったため、月の名前を揃えてレーキを踏む人さえいませんでした。 途中で故障することなくこれに到達したすべての人は、UTF8エンコーディングで間違った語長を与える関数を使用していました。

「進行中」の問題番号3は、巡回セールスマン問題のテーマのバリエーションです。 撮影された都市は、当社の代表的なオフィスがある都市であり、距離はアトラスからの道路の長さに実際に対応しています。 すでに条件を送信したので、パスのサイクルの有無を明示的に規定していないことがわかりました。 どういうわけか、巡回セールスマンの問題はサイクルで解決できると考えることはすぐには起こりませんでした。 検証中に、両方のアプローチが正しいと見なされる必要がありました。 ただし、参加者がサイクルを許可している場合のみ、このアプローチで適切なソリューションがすべて見つかります。 検証テストを完了する必要がありました。 予想外のことから、すべての参加者が再帰のようなプログラミングの基本概念に精通しているわけではないことが判明しました。 1人の永続的な人の決定では、レベル11まで深くネストすることにより、再帰が手動で行われました。 問題の状態からのテスト例としてはこれで十分でした。もちろん、他のテストは一切行わず、あらゆる種類のエキゾチックなテストを採点しました。 これを見るのは驚くべきことでした。SQLで書く学生や若い専門家（そして、これが明らかに最初のプログラミング言語になることはできません）は、再帰について知って、それを実践できると思いました。 これがなければ、プログラミングにはまったく方法がありません。

問題番号5の「ラビリンス」は個人的に私にとって最も魔法のようです。オリンピアードの第2ラウンド全体からインスピレーションを受けたのは彼女でした。 ただし、最初の4つのタスクの後で、おそらく既にその結果は発生していません。 条件では、すべてのオプションを列挙した額の解決策が機能することを明確に規定しました。 ところで、私たちはこの制限を一般にどのように定式化できるかを長い間考えていました。 壁のない空の迷路7x7は、それを通過するためのオプションの数が多いため、すでに長い間計算されています。 一方、多数の壁を持つ迷路（および、それに応じて少数の通路オプション）は、60x60のサイズであっても迅速に解決されます。 もちろん、この問題を解決するためにウェーブアルゴリズムを使用する方がより適切です。 この方法は迅速に機能し、最短パスを最適に見つけ、明らかに悪いオプションを破棄しますが、実装はより困難です。 参加者の一人からのこのタスクの付随する説明でこれらの考慮事項を見るのは非常に楽しかったです。 しかし、Waveアルゴリズムを実装した人はいません。 しかし、私たちもそうしませんでした。

タスク番号4の「計算機」は、技術的に最も困難なものでした。 2段階のアプローチが想定されていました。まず、式をより消化しやすいもの（POLIZまたはスタック表記）に変換してから、結果を計算します。 実際、それを決定した参加者は最も少なかった。 一部の人々は、正規表現を使用して解決を試み、数えられる別の部分式を順番に取り出して計算値に置き換えましたが、そのような実装はすべて誤って、 "(( (-(( ((((( - ( (-(-(-( ( - ((-,0-,0))) ) ))))) ) ) ))))) ) ) " 実装も不完全で、文字列を使用してSQLスタックを実装する必要がありました。これにより、データベース内の文字列フィールドの長さに関する技術的な制限により、スタックのネストの深さが制限されます。

輸血に関する問題＃2は企業のwikiから取ったもので、ここではかつて私たちのプログラマーから私たちのプログラマーに心を温めるために提供されていました。 最初にさまざまな古典的なプログラミング言語で解決し、次にエキゾチックで難解なもの（たとえばBrainfuck）で解決し、最後に宣言的にSQLで解決しました。 オリンピックでそのようなよく考えられた仕事を使わないのは罪だった。

Brainfuckといえば。 タスクを準備する過程で、brainfuckインタープリターは単一のSQLクエリに実装されました。 名前に関連するあいまいさを避けて、タスクでそれを提示し始めませんでした。 それでも、これが実現可能であるという確認された事実があります。 希望する人は繰り返すことができます。

タスクを考え出すことは、解決することよりももっと楽しいと思います。 発明の過程でそれらを解決することも必要でした。 まず、問題の解決策が存在することを確認する必要がありました。 第二に、魅力的なコンポーネントを可能な限り残し、可能であれば不要なルーチンを削除するために、条件を解決するプロセスで指定されました。 その後、参加者が定年まで産業用プログラミングのルーチンに参加できるようにします。 さらに、途中で、あらゆる種類の非自明性が浮上しました。 そして第三に、検証中に参加者の決定を比較するための参照ソリューションが必要でした。

タスクは、最大コードで10ポイント、付随する説明で10ポイントで評価されました。 コードは準備されたデータセットで実行され、最初のデータセットは常にタスクの状態にあったものでした。 つまり、問題の状態からのデータに関する正しい結果は、少なくとも1つのポイントを与えました。 文書化は難しく、客観的に（少なくとも正式に客観的に）評価することには問題がありました。 2つの異なるソリューションを比較するときに、より多くのポイントでより良いドキュメントが評価されるように試みました。

提出された作品では、同一のソリューションの2つのクラスターが見つかりました。 それはもちろん、それらは個々のシンボルとどこか別の単語でさえ異なっていました。 そして、少し書式設定します。 しかし、それらが同一であることが明らかでした。 実際、参加者はお互いを相殺せず、単に問題を一緒に解決したと思います。 しかし、私たちはろうそくのそばに立っておらず、ソリューションの本当の作者が誰で、誰が単に書き直したのかわからなかったので、盗作の痕跡ですべての作品を失格にしなければなりませんでした。 なぜ彼らはいくつかの答えで同じ解決策を送ったのですか？ 誰も気付かないと本当に思った？ 人が批判的に考える能力を完全に失うときに、人々にそのような奇妙な行動に出会ったのはこれが初めてではありません。 さて、彼の評判を確認する責任があるオリンピアードの主催者は、彼が同じ要求に直面していることを理解できないでしょうか？ さて、2人の異なる人がすべての中間テーブルとその中のフィールドを同じ名前で見つけることはできません。 そして、同様のものであってもできない。

技術設計に関するいくつかの言葉。 参加者は、自動テストのためにスクリプトの下から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 

前述したように、2回確認しました。 最初のテスト実行と結果の分析の後、タスクのテストのいくつかを明確にする必要があることが判明しました。 そして、私たちが下さなかった決定の分析中に明らかになったいくつかの驚きをカバーするために、新しいものを作ることの一部。 その後、2人が独立して意思決定の完全なチェックを行い、その後、すべての不一致の分析と完全に調整しました。

最終プロトコルは長い間検証されましたが、私の意見では、参加者の正しいランキングを完全に反映していました。 本当に巨大な人間が決勝に進出しました。

続く！ 記事のボリュームは大きくなり、第2部で続きました 。

PSこの機会を利用して、このオリンピアードの作成、設計、および行動に参加してくれた同僚に感謝します。 エゴール、栄光、ミシャ、アルチョーム-あなたが最初。