Что такое HashCode?
HashCode - это командное соревнование по программированию, ежегодно организуемое Google. Оно позволяет вам делиться своими навыками и общаться с другими программистами, работая вместе над решением проблемы, смоделированной на основе реальной инженерной задачи Google! В небольших командах от двух до четырех программисты со всего мира будут решать первую задачу через квалификационный онлайн-раунд. Хотя этот раунд проводится онлайн, команды могут собираться вместе, чтобы соревноваться бок о бок в локально скоординированных хабах хэш-кода. Лучшие команды этого раунда приглашаются присоединиться к нам в международном офисе Google на нашем ежегодном финальном раунде хэш-кода.
Кто имеет право участвовать?
Вы не имеете права участвовать в этом конкурсе:
- Если вы проживаете в этих странах: Крым, Северная Корея, Квебек, Сирия. В указанных странах по закону запрещено участвовать в этом конкурсе, если вы там проживаете.
- Если вы попадаете под ограничения применимыми программами экспортного контроля и санкций
- Если вы в настоящее время являетесь сотрудником (включая стажера), подрядчиком, должностным лицом или директором компании Google или ее аффилированных лиц, это, однако, не применяется, если вы участвуете в программе Google Student Innovator.
- Однако, если на момент регистрации для участия в конкурсе вам не исполнилось 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 на финал.
Вы можете оставить свои вопросы в комментариях, и я с радостью отвечу на них.
Спасибо за ваше время.