158 lines
4.0 KiB
C++
158 lines
4.0 KiB
C++
#include "AdventHelpers/AdventOfCodeSolution.h"
|
|
|
|
#include <iostream>
|
|
#include <cassert>
|
|
#include <string>
|
|
#include <cstring>
|
|
#include <sstream>
|
|
|
|
#ifdef _MSVC
|
|
#define _OPENMP 1
|
|
#endif
|
|
|
|
#ifdef _OPENMP
|
|
#include <omp.h>
|
|
#endif
|
|
|
|
class Range {
|
|
public:
|
|
using range_t = long long;
|
|
|
|
Range(range_t minValue, range_t maxValue)
|
|
: mMinValue(minValue)
|
|
, mMaxValue(maxValue)
|
|
{
|
|
}
|
|
|
|
inline range_t left() const { return mMinValue; }
|
|
inline range_t right() const { return mMaxValue; }
|
|
|
|
private:
|
|
const range_t mMinValue;
|
|
const range_t mMaxValue;
|
|
};
|
|
|
|
class Day02Solution : public AdventHelpers::AdventOfCodeSolution
|
|
{
|
|
public:
|
|
using RangeList = std::vector<Range>;
|
|
|
|
static RangeList ParseLine(std::string line) {
|
|
size_t index = 0;
|
|
|
|
RangeList ranges;
|
|
|
|
while (line.length() > 0) {
|
|
std::string left, right;
|
|
|
|
size_t start = 0;
|
|
size_t leftEnd = line.substr(start).find('-');
|
|
|
|
size_t rightEnd = line.substr(leftEnd).find(',');
|
|
if (rightEnd == std::string::npos) rightEnd = line.length() - 1;
|
|
|
|
left = line.substr(start, leftEnd);
|
|
right = line.substr(leftEnd+1, rightEnd-1);
|
|
|
|
ranges.push_back(Range(std::stoll(left), std::stoll(right)));
|
|
|
|
line.erase(0, leftEnd + rightEnd + 1);
|
|
}
|
|
|
|
return ranges;
|
|
}
|
|
|
|
// An ID is invalid if the first half and the second half match.
|
|
// It necessarily must be even.
|
|
static bool isValidPart01(const std::string number) {
|
|
if (number.length() % 2 == 0) {
|
|
const size_t halfLength = number.length() / 2;
|
|
|
|
std::string left = number.substr(0, halfLength);
|
|
std::string right = number.substr(halfLength);
|
|
|
|
if (left.compare(right) == 0) {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
// In part 2, an id is invalid if it has some sequence repeated at least twice.
|
|
// 111 = 1 three times, invalid
|
|
// 121212 = 12 three times, invalid
|
|
// 123123 = same as above, 123 twice
|
|
static bool isValidPart02(const std::string number) {
|
|
// Once we hit half the length, it must be the same on both sides
|
|
const size_t halfLen = number.length() / 2;
|
|
|
|
// Start from one character and work up
|
|
for (int i = 0; i < halfLen; i++) {
|
|
const auto substr = number.substr(0, i + 1);
|
|
std::string temp(number);
|
|
|
|
while (temp.substr(0, substr.length()).compare(substr) == 0) {
|
|
temp.erase(0, substr.length());
|
|
}
|
|
|
|
if (temp.length() == 0) return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
virtual std::string SolveProblem01(AdventHelpers::InputFileHelper& inputFile) override {
|
|
std::string line = inputFile.getLine(0);
|
|
|
|
auto ranges = ParseLine(line);
|
|
Range::range_t sum = 0;
|
|
|
|
for (const auto& range : ranges) {
|
|
auto left = range.left();
|
|
auto right = range.right();
|
|
|
|
#ifdef _OPENMP
|
|
#pragma omp parallel for reduction(+ : sum)
|
|
#endif
|
|
for (Range::range_t i = left; i <= right; i++) {
|
|
if (!isValidPart01(std::to_string(i)))
|
|
sum += i;
|
|
}
|
|
}
|
|
|
|
return std::to_string(sum);
|
|
}
|
|
|
|
virtual std::string SolveProblem02(AdventHelpers::InputFileHelper& inputFile) override {
|
|
std::string line = inputFile.getLine(0);
|
|
|
|
auto ranges = ParseLine(line);
|
|
Range::range_t sum = 0;
|
|
|
|
for (const auto& range : ranges) {
|
|
auto left = range.left();
|
|
auto right = range.right();
|
|
|
|
#ifdef _OPENMP
|
|
#pragma omp parallel for reduction(+ : sum)
|
|
#endif
|
|
for (Range::range_t i = left; i <= right; i++) {
|
|
if (!isValidPart02(std::to_string(i)))
|
|
sum += i;
|
|
}
|
|
}
|
|
|
|
return std::to_string(sum);
|
|
}
|
|
};
|
|
|
|
int main()
|
|
{
|
|
Day02Solution solution;
|
|
solution.SolveAll();
|
|
|
|
return 0;
|
|
}
|
|
|