Because it's fun :)
Inspired by SecondThread's comment above, I thought I'd see how hard it would be to solve a Meta Hacker Cup problem at compile time. I chose to start with A1, since the input is quite small. This is probably trivial since C++20 and above allow you to allocate memory in constexpr functions, so I gave it a whirl using C++17. This means no allocations allowed, but the input/output parsing is luckily very straightforward for this problem.
#include <array>
#include <cstdint>
#include <string_view>
#include <tuple>
constexpr std::string_view DATA = R"MHC2024(6
121 121 11
0 100 2
0 132 1
121 132 1
121 131 1
22322 22322 1
)MHC2024";
constexpr auto isWhiteSpace(char c) -> bool {
return c == ' ' || c == '\r' || c == '\t' || c == '\n';
}
constexpr auto isDigit(char c) -> bool {
return '0' <= c && c <= '9';
}
constexpr auto parse(std::string_view s, int64_t& res) -> std::string_view {
auto it = s.begin();
while (isWhiteSpace(*it)) ++it;
res = 0;
while (isDigit(*it)) {
res = 10 * res + (*it++ - '0');
}
return s.substr(it - s.begin());
}
constexpr auto genPeaks() {
std::array<int64_t, 45> ans{};
auto it = ans.begin();
char buf[20]{};
for (int32_t k = 0; k < 9; ++k) {
for (int32_t center = k + 1; center <= 9; ++center) {
buf[k] = center + '0';
for (int32_t i = 1; i <= k; ++i) {
buf[k - i] = buf[k + i] = center + '0' - i;
}
buf[k + k + 1] = '\0';
parse(buf, *it++);
}
}
return ans;
}
constexpr auto PEAKS = genPeaks();
template <typename It>
constexpr auto writeStr(It p, const char* q) -> It {
while (*q) {
*p++ = *q++;
}
return p;
}
// assumes positive, <= 3 digits
template <typename It>
constexpr auto writeNum(It p, int64_t x) -> It {
if (x < 10) {
*p++ = '0' + x;
} else if (x < 100) {
*p++ = '0' + (x / 10);
*p++ = '0' + (x % 10);
} else {
*p++ = '0' + (x / 100);
*p++ = '0' + (x / 10) % 10;
*p++ = '0' + (x % 10);
}
return p;
}
constexpr auto run(std::string_view s) {
constexpr size_t OUTPUT_LEN = 1 << 15;
int64_t t{};
s = parse(s, t);
std::array<char, OUTPUT_LEN> res{};
auto p = res.begin();
for (int64_t tc = 1; tc <= t; ++tc) {
int64_t ans = 0;
int64_t a{}, b{}, m{};
s = parse(s, a);
s = parse(s, b);
s = parse(s, m);
for (auto peak : PEAKS) {
ans += a <= peak && peak <= b && peak % m == 0;
}
p = writeStr(p, "Case #");
p = writeNum(p, tc);
p = writeStr(p, ": ");
p = writeNum(p, ans);
*p++ = '\n';
}
return res;
}
constexpr auto ANS = run(DATA);
int main() {
// ensure ans is not discarded.
return (int)((uintptr_t)(void*)&ANS & 0xffff);
}
And it appears to work on the three major compilers: https://godbolt.org/z/cYG1rTfWr.
Note that the compiled binary returns a random value, To actually view the answer, you can view the compiled binary in a hex editor, or do what I did:
$ strings a.out | grep Case
Case #1: 1
Case #2: 4
Case #3: 10
Case #4: 1
Case #5: 1
Case #6: 0
This code is also sufficient to pass the full data set (136 cases) without running into the default constexpr-ops limit.
Does anyone know a nicer way of ensuring that ANS
is not discarded by the compiler for not being used?