Конкурс по программированию: Торговля (итоги)

    Большое спасибо всем участникам конкурса по программированию! Мы рады объявить окончательные результаты конкурса.

    В конкурсе участвовали 186 решений. Мы провели между ними турнир в два раунда, как объявляли ранее. Поздравляем победителей:

    1. Asta — приз 3000 USD.
    2. Silent Bob — приз 2000 USD.
    3. Robert Speed — приз 1000 USD.

    Специальный приз 400 USD получает участник под псевдонимом indutny за разработку альтернативной арены для онлайн-тестирования решений с большей пропускной способностью, чем у предоставленной нами. Спасибо!

    Официальную таблицу результатов вы найдёте на GitHub.

    Решения


    Все решения опубликованы в директории submissions. В каждой поддиректории находится скрипт solution.js, который участвовал в тестировании. Если участник прислал архив с исходными текстами, то его содержимое помещено в поддиректорию src. Рассмотрено (и опубликовано) только последнее из решений, присланных каждым участником.

    Затравочные значения


    Как и обещали, мы взяли первый твит из @SpringerTV, появившийся после окончания приёма решений, и поместили его в ранее опубликованный скрипт. Этот скрипт с текстом твита, немного модифицированный для раздельного вывода двух подпоследовательностей, опубликован как seeds.js.

    Первые 500 нечётных членов последовательности помещены в файл round1.txt и использованы в первом раунде.

    Первые 500 чётных членов последовательности помещены в файл finals.txt и использованы в финале.

    Статистика


    Участвовавшие в первом раунде 186 решений образовали 34 410 упорядоченных пар. Именно столько сеансов было проведено с каждым из 500 затравочных значений. Общее число сеансов в первом раунде составило 17 205 000. Каждое решение участвовало в 185 000 сеансах.

    В 13 868 284 сеансах (80,6%) было достигнуто соглашение. Средний результат сеанса составил 5,8728 очков, а средний результат среди сеансов, в которых было достигнуто соглашение — 7,2858 очков.

    Переговоры были прерваны в 626 779 сеансах (3,64%) по различным причинам (недопустимые предложения, исключения, истечение времени).

    В финал вышли 50 решений. Они образовали 2 450 упорядоченных пар, и мы протестировали их дополнительно на других 500 затравочных значениях. Для ранжирования финалистов мы использовали также результаты сеансов между ними из первого раунда (но не результаты сеансов с участием решений, не прошедших в финал). Таким образом, места среди 50 лучших решений были определены на основе тестирования на 1000 затравочных значениях. Общее число сеансов составило 2 450 000, а каждое решение поучаствовало в 98 000 сеансах.

    В финале соглашение было достигнуто в 2 358 913 сеансах (96,28%). Средний результат сеанса составил 7,0275 очков, а средний результат среди сеансов, в которых было достигнуто соглашение — 7,2989 очков. Впечатляет, насколько хорошо 50 лучших решений используют почти каждую возможность заключить сделку.

    В финале переговоры были прерваны в 1 272 сеансах (0,05%).

    Протоколы сеансов


    Полные протоколы всех 17 205 000 сеансов первого раунда опубликованы в архиве round1.tar.bz2 (2,1 ГБ), а протоколы 2 450 000 сеансов финала — в архиве finals.tar.bz2 (322 МБ). Содержимое этих архивов частично перекрывается, так как некоторые сеансы принадлежат и к первому раунду, и к финалу.

    В этих архивах в каждом файле вида S/A-B.json находится протокол сеанса с затравочным значением S, где решение A было первым участником, а решение B — вторым.

    Для «воспроизведения» протокола сеанса в удобном для чтения формате можно использовать команду haggle.js --replay=LOG.json.

    Нам будет интересно увидеть в комментариях интересные подходы к анализу этого массива данных.

    Таблицы результатов


    Условные обозначения к официальным таблицам результатов:

    • S: Сумма набранных очков (это и есть предмет соревнования)
    • S/N: Средний результат сеанса
    • A: Число сеансов с достигнутым соглашением
    • A/N: Процент сеансов с достигнутым соглашением
    • S/A: Средний результат сеанса с достигнутым соглашением
    • X: Число сеансов, прерванных данным участником (по причине исключений или некорректных результатов)

    В первой таблице приведены результаты финалистов, во второй — результаты решений, не прошедших в финал.

    Ещё раз благодарим всех участников!

    Hola

    47,00

    Компания

    Поделиться публикацией
    Комментарии 24
      0
      Алексей, спасибо ещё раз за конкурс!
      И ждём нового (хорошо бы игрового) в следующем году! ;)
        +1
        Спасибо! Это мой последний конкурс для Hola, так как я решил покинуть компанию. Я напишу по итогам пост о том, как я делал эти конкурсы, что оказалось важным, как придумывались задачи и т.п.
          0
          Мы будет рады конкурсам и в твоём статусе не как сотрудника Hola. Поскольку, имхо, бесспорно, что у тебя такие эвенты отлично получаются. И кмк и тебе самому это по душе, а значит не могло быт ничего иного кроме успеха. С большим уважением!
            0
            Мне хотелось бы продолжать, но это зависит в первую очередь от спонсоров. Ведь компания выделяла призовой фонд, а без ценных призов желающих участвовать будет куда меньше.
              0
              Как уже говорил, наверняка многим большим и чуть поменьше компаниям будет интересен такой формат спонсирования конкурса, получения положительного пиара своего имени и мозгов на вакансии. Просто перекинуться парой словечек с нужными людьми и наверняка продолжение конкурсов будет ещё лучше чем было!

              Даже той же Hola какая разница её штатный сотрудник конкурс делает, или она просто спонсирует и так же получает то что и раньше получала. А вокруг ещё куча интересных компаний. ;)
            0
            Спасибо за конкурсы. Надеюсь, Дерри продолжит старую добрую традицию. I hope Derry will continue the good ole tradition.
          +1
          Спасибо за конкурс!
          Я тут все никак с дублями не успокоюсь :) Написал программку. Вот что получилось по таблице с предварительными результатами (место, хэш, список дублей: место-коэффициент совпадения):
          Список дублей
          — 4 5b6194d9adb0280402fd774d
          7 — 305
          6 — 305
          — 6 5b6194f3adb0280402fd774e
          7 — 2615
          4 — 305
          — 7 5b6194a3adb0280402fd774c
          4 — 305
          6 — 2615
          — 17 5b64e7f2adb0280402fd77ea
          27 — 3403
          71 — 308
          39 — 308
          35 — 3403
          26 — 2750
          — 19 5b61aac7adb0280402fd774f
          20 — 1172
          — 20 5b61b487adb0280402fd7751
          19 — 1172
          — 26 5b64eb06adb0280402fd77f3
          27 — 2750
          17 — 2750
          71 — 321
          39 — 321
          35 — 2750
          — 27 5b64e7baadb0280402fd77e8
          17 — 3403
          71 — 321
          39 — 321
          35 — 5518
          26 — 2750
          — 31 5b646257adb0280402fd779e
          66 — 3639
          — 35 5b64eaabadb0280402fd77f2
          27 — 5518
          17 — 3403
          71 — 321
          39 — 321
          26 — 2750
          — 36 5b64575dadb0280402fd7794
          63 — 1737
          — 39 5b64e9c6adb0280402fd77ef
          138 — 535
          27 — 321
          17 — 308
          71 — 3187
          35 — 321
          26 — 321
          — 46 5b649223adb0280402fd77b3
          62 — 609
          51 — 609
          58 — 609
          — 51 5b649339adb0280402fd77b5
          62 — 6180
          46 — 609
          58 — 2352
          — 58 5b64b128adb0280402fd77c8
          62 — 2352
          46 — 609
          51 — 2352
          — 62 5b5f368eadb0280402fd7705
          46 — 609
          51 — 6180
          58 — 2352
          — 63 5b648f06adb0280402fd77af
          36 — 1737
          — 66 5b645263adb0280402fd7790
          31 — 3639
          — 71 5b64e93badb0280402fd77ee
          27 — 321
          17 — 308
          39 — 3187
          35 — 321
          26 — 321
          — 88 5b60d89dadb0280402fd7748
          115 — 567
          — 91 5b6495abadb0280402fd77b9
          127 — 2336
          — 94 5b6493ebadb0280402fd77b8
          125 — 628
          137 — 628
          140 — 628
          — 115 5b637fdfadb0280402fd7778
          88 — 567
          — 125 5b648ef2adb0280402fd77ae
          137 — 5507
          140 — 5507
          94 — 628
          — 127 5b64ba6aadb0280402fd77ce
          91 — 2336
          — 137 5b64910fadb0280402fd77b1
          125 — 5507
          140 — 5507
          94 — 628
          — 138 5b64c086adb0280402fd77d2
          39 — 535
          — 140 5b649190adb0280402fd77b2
          125 — 5507
          137 — 5507
          94 — 628

          Пусть это будет на совести участников.
          Но мне теперь не дают покоя первое и второе итоговые места. Чем больше смотрю их код, тем больше убеждаюсь, что это одно и тоже решение. Например, вот
          sort_offers из первого
          this.sort_offers = (a, b) =>
          this.value(b) — this.value(a) ||
          sum( ((this.vals.length && this.vals) || this.vals_copy).map(v => this.value2(a, v))) — sum( ((this.vals.length && this.vals) || this.vals_copy).map(v => this.value2(b, v))) ||
          things(b) — things(a) ||
          a — b;
          и
          offerSortFn из второго
          offerSortFn(a, b) {
          const c1 = this.value(b) — this.value(a);
          if (c1 !== 0) {
          return c1;
          }

          const vs = this.possibleValuations.length
          ? this.possibleValuations
          : this.allPossibleValuations;
          let sum1 = 0;
          let sum2 = 0;
          for (const v of vs) {
          sum1 += this.hisValue(a, v);
          sum2 += this.hisValue(b, v);
          }
          const c2 = sum1 — sum2;
          if (c2 !== 0) {
          return c2;
          }

          const c3 = cnt(b) — cnt(a);
          if (c3 !== 0) {
          return c3;
          }

          return a — b;
          }

          Это одна и та же функция, переписанная разными способами. И так весь остальной код. Интересно, сделано это вручную, или каким-то генератором?
            0
            Выглядит просто как два человека, реализовавшие одну и ту же идею. Такое и в других конкурсах было. Например, в JSDash многие делали просчёт вперёд на несколько ходов, то есть один и тот же алгоритм, и каждый записывал его «своими словами».
              +1
              Да нет, выглядит как очень умело замаскированное решение. Количество мест, из которых вызываются эти функции (sort) совпадает.
              Можно взять один код и каждой его строке сопоставить строку из второго. Это не тоже самое о чем вы говорите.
                +1
                Я понимаю, что это несколько неприятно, но правилами такое не запрещено. Мы только проверим, что это реально разные люди, а не подставные адреса электронной почты.
            0
            Предлагаю победителю написать небольшую статью про свой алгоритм и как он дошел до него. Не в рамках того, что первые два места выглядят похожими, а просто интересно посмотреть на ход мыслей человека, сумевшего занять первое место.
              0
              Судя по графику ниже интересными будут 6 первых мест.
              +1
              image
                0
                Честно говоря, не разделяю ваших восторгов.
                1. Возможность отправки нескольких решений.
                а) одно решение, но с разными коэффициентами, увеличивает шансы выиграть в лотерею.
                б) наиболее удачливый лотерейщик может забрать все призы. (В данном конкретном конкурсе сюда же относится возможность наводнить арену игроками с предсказуемым поведением. Почему вы ловите только ботов которые поддаются? А как же боты, которые договариваются по «правильному» алгоритму?)
                На других ресурсах, например, во время регистрации просят приложить CV. (компания ведь проводит конкурс не потому что бабки некуда девать, а с целью поиска новых рекрутов). Чем не вариант способа отлова клонов?
                2. Реферальная система.
                Первый раз мне кто-то показал конкурс. Но на последующие конкурсы я уже сам поглядываю. Мне перед каждым конкурсом нужно снова просить чтобы мне прислали приглашение? Почему компания не ведет постоянную базу участников с сохранением первичного приглашения?
                [я вот сейчас сохраню список участников, поскольку предполагаю что все они будут участвовать и в следующем конкурсе, и со стартом следующего конкурса всем разошлю приглашения :) класс? :))) ].
                3. Переносы конечной даты.
                Честно говоря, утомляет. Если компания хочет привлечь больше участников, то логично было бы сделать анонс — за месяц до начала конкурса просто написать, что будет новый конкурс, стартует такого-то числа. Люди как-то скорректируют свои планы, если хотят принять участие.
                4. Специальный приз.
                Многие считают, что победа в конкурсе — это лотерея (выигрыш зависит от многих тонких настроек и коэффициентов — угадал/не угадал). Но специальный приз — это другое. На мой взгляд, это приз, который должен присуждаться за интересное решение, которое по стечению обстоятельств в лотерею не выиграло. А тут как-то непонятно. Что стимулирует выдача специального приза в данном конкурсе? Или вы преследуете цель, чтобы в следующем конкурсе все думали не над решением, а ваяли разного рода утилиты для конкурса? Наверное, indutny — хороший программист, ну так пригласите его на работу. Но отдавать приз не за конкурсное решение, а за помощь в проведении тестирования… Непонятно.
                  +1
                  Жаль, что конкурс не оправдал ваших ожиданий. Надеюсь, тот, кто будет проводить новые конкурсы после меня, сделает лучше.
                    0
                    Организация такого рода конкурса это всегда геморрой, и всегда можно к чему-то придраться. Соглашусь про первый пункт, ну да бог с ним, и предупреждать за месяц тоже хорошо, но если на работе куча работы никуда она и через месяц не денется ;)
                    В любом случае, спасибо за конкурс!
                    +1
                    Нет смысла что-то предъявлять, т.к. все сводится к тому, что никто никому ничего не должен. Да и простые конкурсы с 6к $ призовых на дороге не валяются.

                    п.с. Почитайте как в почтовом конкурсе победителей переобъявили, там один из участников даже обещал в суд подать — вот это экшн! :)
                      0
                      Я ничего не предъявляю. И не бубню что-то обиженно. Я конкретно говорю что мне не понравилось, и предлагаю вариант как это можно было бы улучшить.
                      А так, деньги компании — раздаёт их как хочет.
                    0
                    Странно, мой алгоритм был 25 в первом раунде и 108 в финале, такое возможно?
                      0
                      Невозможно. Какой ID вашего решения?
                      0
                      .
                        0
                        5b4766a3b7c31b3cc179d16c Здесь 25 место

                        и после того как нужно было пересубмить 5b615af3adb0280402fd774a

                        под первым — я имел ввиду preliminary
                          0
                          Так это вы сравниваете промежуточные результаты с окончательными, а не первый раунд с финалом.
                          +1

                          На основе логов первого раунда сделал альтернативные рейтинги: участники из конца рейтинга удаляются по одному, рейтинг пересчитывается, и т.д. пока не останутся двое. В таком варианте побеждает IFG, что интересно — он не попал в top 50 "Final Standings". Посмотреть можно здесь: Там сначала нужно закрыть мешающий toolbar от archive.org, затем — кнопка "Repeat"

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

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