advent2016_day19.cpp

// g++ -std=c++17 -O2 advent2016_day19.cpp -o advent2016_day19

#include <iostream>
#include <vector>

// Each elf points to the next in a circular linked list. We don't need to store an index number,
// because that is implicitly given by the location in the std::vector container where they all
// reside.
struct Elf {
    Elf* next{};
};

auto makeElfCircle(size_t numElves) -> std::vector<Elf> {
    // create all the elves
    auto elves = std::vector<Elf>(numElves);

    // create a linked list
    for (auto& elf : elves) {
        elf.next = &elf + 1;
    }
    // finish the circle
    elves.back().next = &elves.front();
    return elves;
}

auto advent2016_day19_part1(size_t numElves) -> size_t {
    auto elves = makeElfCircle(numElves);

    // Start at the first elf
    auto currentElf = &elves.front();

    // unlink the next elf until only a single elf left in the circle (thus, the elf points back to
    // itself)
    while (currentElf->next != currentElf) {
        currentElf->next = currentElf->next->next;
        currentElf = currentElf->next;
    }

    // Find out the number of this particular elf
    return std::distance(&elves.front(), currentElf) + 1;
}

auto advent2016_day19_part2(size_t numElves) -> size_t {
    auto elves = makeElfCircle(numElves);

    // Point to right before the opposite elf (so that we can unlink it)
    auto* preOpposite = &elves[elves.size() / 2 - 1];

    auto numElvesRemaining = numElves;

    // loop until only one elf is left
    while (preOpposite->next != preOpposite) {
        // remove the opposite elf
        preOpposite->next = preOpposite->next->next;
        --numElvesRemaining;

        // the stealing elf forwards by one. When the number of elves left in the circle is even,
        // that means that the opposite is now forwarded by one.
        if (numElvesRemaining % 2 == 0) {
            preOpposite = preOpposite->next;
        }
    }

    // Find out the number of this particular elf
    return std::distance(&elves.front(), preOpposite) + 1;
}

int main(int argc, char** argv) {
    std::cout << advent2016_day19_part1(3014603) << " part1" << std::endl
              << advent2016_day19_part2(3014603) << " part2" << std::endl;
}