Advent of Code 2018

#include <algorithm>
#include <numeric>
#include <cstring>
#include <fmt/format.h>
#include <limits>
#include <sstream>
#include <string>
#include <vector>

// const vector<std::string|int> input = {...};
#include "input.hpp"

bool sameType(char a, char b)
    {
    return toupper(a) == toupper(b);
    }

bool samePolarity(char a, char b)
    {
    return isupper(a) == isupper(b);
    }

std::string synthesis(std::string polymer, char unit)
    {
    if (polymer.size() > 0
        && sameType(polymer.back(), unit)
        && !samePolarity(polymer.back(), unit))
        {
        polymer.pop_back();
        }
    else
        {
        polymer += unit;
        }

    return polymer;
    }

size_t react(std::string polymer)
    {
    return std::accumulate (polymer.begin(),
                            polymer.end(),
                            std::string(""),
                            synthesis).size();
    }

std::string distinctTypes()
    {
    auto types = input.front();

    std::transform(types.begin(), types.end(), types.begin(), ::tolower);
    std::sort(types.begin(), types.end());
    types.erase(std::unique(types.begin(), types.end()), types.end());

    return types;
    }

unsigned part1()
    {
    return react(input.front());
    }

unsigned part2()
    {
    auto originalPolymer = input.front();
    auto shortestLen = std::numeric_limits<size_t>::max();

    for (auto typeToRemove: distinctTypes())
    {
        std::stringstream reducedPolymer;

        std::remove_copy_if(originalPolymer.begin(), originalPolymer.end(),
                            std::ostream_iterator<char>(reducedPolymer),
                            [=](char t) { return sameType (t, typeToRemove); });

        auto polymerLen = react(reducedPolymer.str());
        if (polymerLen < shortestLen)
        {
            shortestLen = polymerLen;
        }
    }

    return shortestLen;
    }

int main()
    {
    fmt::print("Part 1: {}\n", part1());
    fmt::print("Part 2: {}\n", part2());
    }

library(readr)

polymer <- gsub("[\r\n]", "", read_file("input"))

isUpper <- function(c) grepl("[[:upper:]]", c)

sameType <- function(a,b) toupper(a) == toupper(b)

samePolarity <- function(a, b) isUpper(a) == isUpper(b)

stringAsList <- function(s) unlist(strsplit(s, ""))

# Part 1

removeLast <- function(s) substr(s, 1, nchar(s) - 1)

lastChr <- function(s) if (nchar(s) > 0) stringAsList(s)[nchar(s)] else s

synthesis <- function(result, unit) {
    lastUnit <- lastChr(result)
    if (sameType(unit, lastUnit) & !samePolarity(unit, lastUnit)) {
        removeLast(result)
    } else {
        paste(result, unit, sep="")
    }
}

react <- function(polymer) Reduce(synthesis, stringAsList(polymer), "")

cat(sprintf("Part 1: %d\n", nchar(react(polymer))))

# Part 2

uniqueUnits <- levels(factor(sapply(stringAsList(polymer), toupper)))

# This will take a while...
cat("Working with part 2 ")
reducedPolyLen <- sapply(uniqueUnits,
                         function (unitToRemove) {
                             p <- stringAsList(polymer)
                             cat(".")
                             r <- react(p[!sameType(p, unitToRemove)])
                             nchar(r)
                          })

cat(sprintf("\nPart 2: %d\n", min(reducedPolyLen)))

#include <algorithm>
#include <fmt/format.h>
#include <iterator>
#include <map>
#include <optional>
#include <queue>
#include <regex>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include <iostream>

// const std::vector<std::string|int> input = {...};
#include "input.hpp"

using Step   = char;
using Prereq = std::set<char>;
using Steps  = std::map<char, Prereq>;
struct Work {
    Work(Step s, unsigned c)
        : step(s)
        , completedSec(c)
    {
    }
    bool operator<(const Work & a) const
    {
        return this->completedSec > a.completedSec;
    }
    Step     step;
    unsigned completedSec;
};
using WorkQ  = std::priority_queue<Work>;
using Result = std::pair<std::string, unsigned>;

Steps stepsGet()
{
    std::regex re(
        "Step ([A-Z]) must be finished before step ([A-Z]) can begin.");
    std::smatch matches;
    Steps       steps;

    for (auto line : input) {
        std::regex_search(line, matches, re);
        Step pre  = matches[1].str()[0];
        Step step = matches[2].str()[0];
        steps[pre];
        steps[step].insert(pre);
    }

    return steps;
}

unsigned workCost(Step step, unsigned latency)
{
    return (step - 'A' + 1) + latency;
}

std::optional<Step> nextStep(Steps & steps, const Prereq & fulfilled)
{
    auto it = std::find_if(steps.begin(), steps.end(), [&](auto & step) {
        return std::includes(fulfilled.begin(),
                             fulfilled.end(),
                             step.second.begin(),
                             step.second.end());
    });
    if (it == steps.end()) {
        return std::nullopt;
    }
    return std::optional<Step>(it->first);
}

Result compute(Steps steps, unsigned numWorkers = 1, unsigned latency = 0)
{
    Prereq      fulfilled;
    std::string done;
    unsigned    elapsedSec   = 0;
    unsigned    availWorkers = numWorkers;
    WorkQ       workQ;

    do {
        auto step = nextStep(steps, fulfilled);

        if (step && availWorkers > 0) {
            // Schedule more work
            Step s = step.value();
            availWorkers--;
            steps.erase(s);
            workQ.push(Work(s, elapsedSec + workCost(s, latency)));
        }
        else {
            // Move to closest second where work is commited, commit all work
            // for that second
            do {
                auto work = workQ.top();

                fulfilled.insert(work.step);
                done += work.step;
                elapsedSec = work.completedSec;
                availWorkers++;
                workQ.pop();
            } while (!workQ.empty() && elapsedSec == workQ.top().completedSec);
        }
    } while (!steps.empty() || !workQ.empty());

    return std::pair(done, elapsedSec);
}

auto part1()
{
    return compute(stepsGet()).first;
}

auto part2()
{
    return compute(stepsGet(), 5, 60).second;
}

int main()
{
    fmt::print("Part 1: {}\n", part1());
    fmt::print("Part 2: {}\n", part2());
}

auto clockwiseMove(auto & circle, auto it, unsigned n)
{
    while (n-- > 0) {
        ++it;
        if (it == circle.end()) {
            it = circle.begin();
        }
    }
    return it;
}

auto counterClockwiseMove(auto & circle, auto it, unsigned n)
{
    while (n-- > 0) {
        if (it == circle.begin()) {
            it = circle.end();
        }
        --it;
    }
    return it;
}

unsigned winningScore(unsigned numPlayers, unsigned finalMarble)
{
    std::list<unsigned>   circle{ 0 };
    std::vector<unsigned> scores(numPlayers);
    unsigned              player   = 0;
    unsigned              marbleNr = 0;
    auto                  cur      = circle.begin();

    while (++marbleNr != finalMarble) {
        if (marbleNr % 23 == 0) {
            cur = counterClockwiseMove(circle, cur, 7);
            scores[player] += (marbleNr + *cur);
            cur = circle.erase(cur);
        }
        else {
            cur = clockwiseMove(circle, cur, 2);
            cur = circle.insert(cur, marbleNr);
        }

        if (++player == numPlayers) {
            player = 0;
        }
    }
    return *std::max_element(scores.begin(), scores.end());
}

#include <fmt/format.h>
#include <memory>
#include <numeric>
#include <optional>
#include <sstream>
#include <tuple>

// const std::vector<std::string|int> input = {...};
#include "input.hpp"

using Tracks = std::vector<std::string>;
using Path   = char;

enum class Turn { Left, Straight, Right };
enum class Dir { N, E, S, W };

struct Coord {
    Coord(int x_, int y_)
        : x(x_)
        , y(y_)
    {
    }

    std::string str() const
    {
        std::stringstream ss;
        ss << x << ',' << y;
        return ss.str();
    }

    unsigned x, y;
};

Turn nextTurn(Turn turn)
{
    switch (turn) {
    case Turn::Left:
        return Turn::Straight;
    case Turn::Straight:
        return Turn::Right;
    default:
        return Turn::Left;
    }
}

Dir turnLeft(Dir dir)
{
    switch (dir) {
    case Dir::N:
        return Dir::W;
    case Dir::E:
        return Dir::N;
    case Dir::S:
        return Dir::E;
    default:
        return Dir::S;
    }
}

Dir turnRight(Dir dir)
{
    switch (dir) {
    case Dir::N:
        return Dir::E;
    case Dir::E:
        return Dir::S;
    case Dir::S:
        return Dir::W;
    default:
        return Dir::N;
    }
}

struct Cart {
    Cart(Coord locStart, Dir dirStart, const Tracks & tr)
        : coord(locStart)
        , dir(dirStart)
        , lastIntersection(Turn::Right)
        , tracks(tr)
    {
    }

    void followTrack(Path path)
    {
        Turn turn(Turn::Straight);

        switch (path) {
        case '-':
        case '|':
            break;
        case '+':
            turn             = nextTurn(lastIntersection);
            lastIntersection = turn;
            break;
        default:
            if (dir == Dir::N || dir == Dir::S) {
                turn = (path == '/' ? Turn::Right : Turn::Left);
            }
            else {
                turn = (path == '/' ? Turn::Left : Turn::Right);
            }
            break;
        }

        switch (turn) {
        case Turn::Straight:
            break;
        case Turn::Left:
            dir = turnLeft(dir);
            break;
        case Turn::Right:
            dir = turnRight(dir);
            break;
        }
    }

    void step()
    {
        switch (dir) {
        case Dir::W:
            coord.x--;
            break;
        case Dir::E:
            coord.x++;
            break;
        case Dir::N:
            coord.y--;
            break;
        case Dir::S:
            coord.y++;
            break;
        }

        followTrack(tracks[coord.y][coord.x]);
    }

    Coord          coord;
    Dir            dir;
    Turn           lastIntersection;
    const Tracks & tracks;
};

using CartPtr = std::shared_ptr<Cart>;
using Carts   = std::vector<CartPtr>;

bool cartLt(CartPtr a, CartPtr b)
{
    return ((a->coord.y < b->coord.y)
            || (a->coord.y == b->coord.y && a->coord.x < b->coord.x));
}

bool cartEq(CartPtr a, CartPtr b)
{
    return (a->coord.x == b->coord.x) && (a->coord.y == b->coord.y);
}

Tracks tracksGet()
{
    Tracks tracks = input;

    for (auto & row : tracks) {
        for (Path & path : row) {
            if (path == '<' || path == '>') {
                path = '-';
            }
            if (path == '^' || path == 'v') {
                path = '|';
            }
        }
    }

    return tracks;
}

Carts cartsGet(const Tracks & tracks)
{
    Carts carts;

    for (unsigned y = 0; y < input.size(); y++) {
        auto & row = input[y];
        for (unsigned x = 0; x < row.size(); x++) {
            Path path = row[x];
            Dir  dir;

            switch (path) {
            case '^':
                dir = Dir::N;
                break;
            case '<':
                dir = Dir::W;
                break;
            case '>':
                dir = Dir::E;
                break;
            case 'v':
                dir = Dir::S;
                break;
            default:
                continue;
            }

            carts.push_back(std::make_shared<Cart>(Coord(x, y), dir, tracks));
        }
    }
    return carts;
}

std::optional<Coord> collision(Carts & carts)
{
    std::sort(carts.begin(), carts.end(), cartLt);
    auto it = std::adjacent_find(carts.begin(), carts.end(), cartEq);
    if (it == carts.end()) {
        return std::nullopt;
    }
    return std::optional((*it)->coord);
}

void removeCollidingCarts(Carts & carts, Coord collisionAt)
{
    auto it = std::adjacent_find(carts.begin(), carts.end(), cartEq);
    carts.erase(it, it + 2);
}

auto part1()
{
    Tracks               tracks = tracksGet();
    Carts                carts  = cartsGet(tracks);
    Carts                stepOrder;
    std::optional<Coord> collisionAt;

    while (!(collisionAt = collision(carts))) {
        if (stepOrder.empty()) {
            stepOrder = carts;
            std::sort(stepOrder.rbegin(), stepOrder.rend(), cartLt);
        }
        stepOrder.back()->step();
        stepOrder.pop_back();
    }

    return collisionAt.value().str();
}

auto part2()
{
    Tracks tracks = tracksGet();
    Carts  carts  = cartsGet(tracks);
    Carts  stepOrder;

    while (carts.size() > 1 || !stepOrder.empty()) {
        if (stepOrder.empty()) {
            stepOrder = carts;
            std::sort(stepOrder.rbegin(), stepOrder.rend(), cartLt);
        }

        stepOrder.back()->step();
        stepOrder.pop_back();

        auto collisionAt = collision(carts);
        if (collisionAt) {
            removeCollidingCarts(carts, collisionAt.value());
        }
    }

    return carts.front()->coord.str();
}

int main()
{
    fmt::print("Part 1: {}\n", part1());
    fmt::print("Part 2: {}\n", part2());
}

#include <algorithm>
#include <fmt/format.h>
#include <list>
#include <tuple>

// const std::vector<std::string|int> input = {...};
#include "input.hpp"

#define NUM_MEASURING_RECIPIES 10

using Score         = unsigned;
using Scoreboard    = std::list<Score>;
using CurrentRecipe = Scoreboard::const_iterator;

void recipesMake(Scoreboard & scoreboard, Score a, Score b)
{
    Score sum = a + b;

    if (sum > 9) {
        scoreboard.push_back(sum / 10);
    }
    scoreboard.push_back(sum % 10);
}

CurrentRecipe recipePick(const Scoreboard & scoreboard, CurrentRecipe cur)
{
    auto steps = *cur + 1u;

    while (steps-- > 0) {
        ++cur;
        if (cur == scoreboard.end()) {
            cur = scoreboard.begin();
        }
    }
    return cur;
}

std::string scoresGet(const Scoreboard &          scoreboard,
                      Scoreboard::difference_type fromIdx,
                      Scoreboard::difference_type toIdx)
{
    CurrentRecipe it  = std::next(scoreboard.begin(), fromIdx);
    CurrentRecipe end = std::next(scoreboard.begin(), toIdx);
    std::string   scores;

    while (it != end) {
        scores.push_back('0' + *it);
        ++it;
    }
    return scores;
}

Scoreboard patternMake(unsigned digits)
{
    Scoreboard pattern;

    while (digits > 0) {
        pattern.push_back(digits % 10);
        digits /= 10;
    }
    std::reverse(pattern.begin(), pattern.end());
    return pattern;
}

std::tuple<CurrentRecipe, bool> matchCheck(const Scoreboard & scoreboard,
                                           const Scoreboard & pattern,
                                           CurrentRecipe      it)
{
    while ((unsigned)std::distance(it, scoreboard.end()) >= pattern.size()) {
        if (std::mismatch(pattern.cbegin(), pattern.cend(), it).first
            == pattern.cend()) {
            return std::make_tuple(it, true);
        }
        ++it;
    }
    return std::make_tuple(it, false);
}

auto part1()
{
    Scoreboard    scoreboard{ 3, 7 };
    CurrentRecipe elf1                = scoreboard.begin();
    CurrentRecipe elf2                = std::next (scoreboard.begin());
    auto          numTrainingRecipies = input[0];

    while (scoreboard.size() < numTrainingRecipies + NUM_MEASURING_RECIPIES) {
        recipesMake(scoreboard, *elf1, *elf2);
        elf1 = recipePick(scoreboard, elf1);
        elf2 = recipePick(scoreboard, elf2);
    }

    return scoresGet(scoreboard,
                      numTrainingRecipies,
                      numTrainingRecipies + NUM_MEASURING_RECIPIES);
}

auto part2()
{
    Scoreboard    scoreboard{ 3, 7 };
    CurrentRecipe elf1    = scoreboard.begin();
    CurrentRecipe elf2    = std::next(scoreboard.begin());
    Scoreboard    pattern = patternMake(input[0]);
    CurrentRecipe it      = scoreboard.begin();
    bool          match   = false;

    while (!match) {
        recipesMake(scoreboard, *elf1, *elf2);
        elf1 = recipePick(scoreboard, elf1);
        elf2 = recipePick(scoreboard, elf2);
        std::tie(it, match) = matchCheck(scoreboard, pattern, it);
    }

    return std::distance(scoreboard.cbegin(), it);
}

int main()
{
    fmt::print("Part 1: {}\n", part1());
    fmt::print("Part 2: {}\n", part2());
}