Привет ! Меня зовут Ксавье Жувено, и вот третья часть длинной серии о Пришествии кода. Предыдущую часть можно найти здесь
В этом новом посте мы собираемся решить вторую задачу от 3 декабря 2015 года под названием «Идеально сферические дома в вакууме». Решение я предложу на C++, но рассуждения можно применить и к другим языкам.
Часть 1
Проблема
Полную версию этой проблемы можно найти непосредственно на сайте Пришествие кода, здесь я опишу лишь суть проблемы:
Санта доставляет подарки бесконечной двумерной сетке домов. Он начинает с доставки подарка в дом в его стартовой точке, а затем эльф на Северном полюсе сообщает ему по радио, куда двигаться дальше. Он перемещается на один дом за раз на север (^
), юг (v
), восток (>
) или запад (<
). Каждый раз, когда Санта посещает дом, он доставляет один подарок, но эльф, дающий инструкции Санте, выпил слишком много яичного гоголя и заставил Санту посещать дома более одного раза. Итак, нам нужно выяснить, сколько домов получили хотя бы один подарок.
Например:
>>
заставляет Санту доставить по одному подарку3
домам, тому, в котором он начинает игру, и 2 домам к востоку от него.^v^v^v^v^v
заставляет Санту доставить кучу подарков в2
дома.
Решение
Здесь я опишу мыслительный процесс, который я использовал, чтобы прийти к решению.
Во-первых, нам нужно знать местоположение Санты в сетке домов, а значит, нам нужны его координаты.
struct Coordinate { int x{0}; int y{0}; }; Coordinate santaPosition;
Теперь, когда у нас есть местоположение Санты, мы должны сохранить путь, по которому идет Санта. Самый простой способ описать этот путь — это список из Coordinates
.
#include <vector> using Path = std::vector<Coordinate> Path santaPath;
Наконец-то у нас есть все структуры для решения этой проблемы. Теперь нам нужно найти путь, по которому прошел Санта.
// Adds the house where Santa start to deliver presets santaPath.emplace_back(santaPosition); for(auto direction : input) { // Modify Santa's location switch (direction) { case '^': ++santaPosition.y; break; case '>': ++santaPosition.x; break; case '<': --santaPosition.x; break; case 'v': --santaPosition.y; break; } // Adds the new location to Santa's path santaPath.emplace_back(santaPosition); }
Наконец, у нас есть путь, по которому идет Санта. Все, что нам нужно сделать сейчас, это выяснить, сколько разных домов есть на пути Санты. Для этого мы будем использовать 2 стандартных алгоритма: std::sort и std::unique.
#include <algorithm> std::sort(std::begin(santaPath), std::end(santaPath)); auto it = std::unique(std::begin(santaPath), std::end(santaPath)); const auto numberOfHousesVisited = std::distance(std::begin(santaPath), it);
Обратите внимание, чтобы иметь возможность использовать эти алгоритмы, мы должны указать операторы ==
и <
структуры Coordinate
.
Я рекомендую вам посмотреть полное решение, используемое в этом образце кода, на моем GitHub.
Часть 2
Проблема
Эта проблема такая же, как и в первой части, за исключением того, что теперь есть два «курьера», Санта и Робо-Санта. Оба начинают с одной и той же позиции и по очереди двигаются в соответствии с инструкциями эльфа. Нам еще предстоит выяснить, сколько домов получили хотя бы один подарок.
Например:
Решение
Большая часть исходного кода очень похожа на часть 1, поэтому мы сосредоточимся только на различиях. Для начала мы можем интегрировать в Санту и Робо-Санту общую структуру, которую я назвал DeliveryMan
.
struct DeliveryMan { Coordinate position; Path path; }; DeliveryMan santa, roboSanta;
При сборе инструкции мы можем переключаться между доставщиком, получающим инструкцию, и троичной инструкцией.
DeliveryMan deliveryMan; deliveryMan = deliveryMan == &santa ? &roboSanta: &santa;
И, наконец, после того как мы отсортировали пути Санты и Робо-Санты, мы должны объединить их перед использованием std::unique.
std::vector<Coordinate> mergedPath; std::merge(std::begin(santa.path), std::end(santa.path), std::begin(roboSanta.path), std::end(roboSanta.path), std::back_inserter(mergedPath));
И это все об интересном моменте этой части. Вы можете проверить полное решение этого кода на моем GitHub.
Вывод
Вы можете заметить, что решения, написанные в этом посте, включают не все исходники для запуска программ, а только интересную часть исходников для решения этой проблемы. Если вы хотите увидеть программы от начала до конца, вы можете зайти на мою [учетную запись GitHub] https://github.com/Xav83/AdventOfCode/tree/2015.03/2015/Day3), изучить полное решение, добавить комментарии или задавайте вопросы, если хотите.
Вот список std-методов и контейнеров, которые мы использовали, я не могу убедить вас взглянуть на их определения:
Спасибо, что читаете, надеюсь, вам понравилось 😃
И до следующей части, получайте удовольствие, учась и развиваясь.
Первоначально опубликовано на http://10xlearner.com 17 июня 2019 г.