Привет ! Меня зовут Ксавье Жувено, и вот третья часть длинной серии о Пришествии кода. Предыдущую часть можно найти здесь

В этом новом посте мы собираемся решить вторую задачу от 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 г.