Что такое HashCode?

HashCode - это командное соревнование по программированию, ежегодно организуемое Google. Оно позволяет вам делиться своими навыками и общаться с другими программистами, работая вместе над решением проблемы, смоделированной на основе реальной инженерной задачи Google! В небольших командах от двух до четырех программисты со всего мира будут решать первую задачу через квалификационный онлайн-раунд. Хотя этот раунд проводится онлайн, команды могут собираться вместе, чтобы соревноваться бок о бок в локально скоординированных хабах хэш-кода. Лучшие команды этого раунда приглашаются присоединиться к нам в международном офисе Google на нашем ежегодном финальном раунде хэш-кода.

Кто имеет право участвовать?

Вы не имеете права участвовать в этом конкурсе:

  1. Если вы проживаете в этих странах: Крым, Северная Корея, Квебек, Сирия. В указанных странах по закону запрещено участвовать в этом конкурсе, если вы там проживаете.
  2. Если вы попадаете под ограничения применимыми программами экспортного контроля и санкций
  3. Если вы в настоящее время являетесь сотрудником (включая стажера), подрядчиком, должностным лицом или директором компании Google или ее аффилированных лиц, это, однако, не применяется, если вы участвуете в программе Google Student Innovator.
  4. Однако, если на момент регистрации для участия в конкурсе вам не исполнилось 16 лет, чтобы иметь право участвовать в финальном раунде этого конкурса, вы должны быть не ниже минимального возраста на момент регистрации для участия в таком конкурсе. «Минимальный возраст» означает возраст старше восемнадцати (18) лет или возраст совершеннолетия в стране вашего проживания.

Что такое HashCode JudgeSystem?

Система судей HashCode позволяет вам делать следующее после регистрации:

  • формировать команды
  • получить постановку задачи для решения
  • проверять правильность и подсчитывать баллы за свои решения

Мое решение

Постановка проблемы: вы можете найти проблему с пиццей здесь.

Примечание. Прежде чем продолжить работу с этой статьей, убедитесь, что вы полностью понимаете вопрос.

Язык программирования: Java (я использовал концепции ООП)

Структура решения:

  • Разобрать входной файл
  • Симулировать
  • Файл вывода на печать

Объекты ООП:

  • Ячейка - представляет собой ячейку на пицце со следующими свойствами: позиция x (целое число) в сетке, положение y (целое число) на сетка, ингредиент (символ) "T", представляющий помидор, или "M", представляющий гриб, cutOut (логическое значение), представляющий, была ли ячейка вырезана в ломтике, по умолчанию значение ложно.
  • Пицца - содержит общую информацию о пицце: строк (целое число) количество строк в пицце, столбцов (целое число) число. столбцов пиццы, minIngredientEachPerSlice (целое число) минимальное количество ингредиентов, каждый из которых требуется для каждого фрагмента, maxCellsPerSlice (целое число) максимальная площадь фрагмента, ячейки (HashMap) сохраняет пару "ключ-значение" всех ячеек, устанавливая ключ (stringValue of x, объединенный со stringValue y ячейки) по отношению к его значению (объект Cell), rowLength (целое число) - количество цифр, составляющих самую высокую строку, оно используется для генерации неконфликтующего хеш-ключа для ячейки аналогично colsLength, как показано в getCellHashKey.
  • PizzaCutter - обрабатывает все, что связано с нарезкой пиццы, и зависит от объекта Pizza, который нужно разрезать. Он сохраняет все фрагменты в списке cutSlices.
  • Slice - содержит структуру фрагмента: startX (целое число) начальная x позиция фрагмента, endX (целое число) конечная x позиция фрагмент, startY (целое число) начальная позиция y фрагмента, endY (целое число) конечная позиция y фрагмента.
  • Симулятор. Задача симулятора заключается в анализе ввода, имитации каждого набора данных и создании соответствующего выходного файла. Он зависит от двух сущностей: Pizza и PizzaCutter. объекты.

Формулировки проблем в системе судей поставляются с наборами входных данных обычно в форматах файлов (a_example. in, b_small. in , c_medium. in и d_big. in). Ваша задача - запустить решение для каждого набора входных данных и создать соответствующий выходной файл. Поэтому для указанных выше входных файлов я создал соответствующие выходные файлы (a_example.out, b_small.out, c_medium.out и d_big.out)

Я реализовал это в начальной точке моей программы, как показано ниже:

Анализ ввода:

Я проанализировал ввод, как показано в методе parseInput в классе Simulator, используя различные объекты, как показано ниже.

Имитация ввода:

Мой алгоритм:

  • Пройдитесь по пицце слева направо, сверху вниз.
  • Возьмите пару ячеек для мини-ломтика. По одной ячейке из каждой строки. Все под одним индексом. Принятие miniSlice как целочисленного деления максимального количества ингредиентов на 2. Это означает, что 2 miniSlice всегда будут удовлетворять правилу максимального количества ингредиентов.
  • Для каждого miniSlice проверьте, соответствует ли он каждому условию, чтобы называться срезом.
  • Если он проходит, и следующий miniSlice также проходит, то текущий miniSlice добавляется как срез в список cutSlices. Если следующий miniSlice не соответствует требованию среза, то его ячейки добавляются к текущему miniSlice, и он добавляется как срез в список cutSlices.
  • В противном случае, если он не проходит как срез, но следующий miniSlice проходит как срез, текущие ячейки miniSlice добавляются к следующему miniSlice, и он добавляется как срез в список cutSlices. Но если следующий miniSlice также не соответствует условию, двум miniSlices предоставляется последний шанс.
    Два miniSlices складываются и проверяются вместе как срез, если они соответствуют условиям. Если они это сделают, срез добавляется в cutSlices. В противном случае текущий miniSlice считается непригодным для использования и игнорируется.

Затем в методе simulate в классе Simulator я создал экземпляр PizzaCutter, вставил Pizza объект и вызвал метод cutPizza, как показано ниже:

Печать вывода:

Я распечатал результат, как указано в задаче, как показано ниже:

Отправка решений:

Перейдите в систему судей, ей нужны 5 файлов для оценки вашего решения, выходные файлы и сжатая папка, содержащая все ваши исходные файлы.

Мне удалось получить в общей сложности 753 583 баллов. Это неплохое решение, но его можно очень хорошо улучшить. Я бы хотел, чтобы вы, ребята, попробовали это и поделились своим подходом и мнениями.

Подтверждение

Спасибо команде разработчиков @ Cotta & Cush, которая помогла в проверке идей для этого решения. Особая благодарность Олавале Лавалю и Отару Бабатунде.

Заключение

Квалификационный раунд hashCode начнется 28 февраля 2019 года, а регистрация завершится 27 февраля 2019 года. Вы можете зарегистрироваться здесь, если вы еще не сделали этого, и, по крайней мере, попытаться принять участие в этом году, и кто знает, возможно, вы участвуете Ваш путь в штаб-квартиру Google на финал.

Вы можете оставить свои вопросы в комментариях, и я с радостью отвечу на них.

Спасибо за ваше время.