Compiling Meta Hacker Cup Inputs

Правка en1, от arknave, 2024-10-20 15:04:15

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?

Теги cpp, compilation, hacker cup

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский arknave 2024-11-05 05:23:53 147
en3 Английский arknave 2024-10-20 15:11:49 0 (published)
en2 Английский arknave 2024-10-20 15:09:57 2685
en1 Английский arknave 2024-10-20 15:04:15 3792 Initial revision (saved to drafts)