arknave's blog

By arknave, history, 3 weeks ago, In English

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 Round 2 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 are allowed, but the input/output parsing is luckily very straightforward for this problem.

The code is a bit long (118 lines), so I've included it in the link below. It appears to work on the three major compilers: https://godbolt.org/z/cYG1rTfWr (v1) https://godbolt.org/z/3GdPKxrcj (v2).

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. On my 2,3GHz Intel i5 laptop CPU from 2018, clang compiles the full data set in .5 seconds.

Does anyone know a nicer way of ensuring that ANS is not discarded by the compiler for not being used? EDIT: Thanks to EnDeRBeaT for the volatile recommendation, this is much simpler.

  • Vote: I like it
  • +123
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

That's incredibly cool

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know a nicer way of ensuring that ANS is not discarded by the compiler for not being used?

Just volatile works for clang and gcc, of course msvc has to be a special kid.

https://godbolt.org/z/nxbsxnoaz

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice, that with a void cast placates MSVC. Updated the link in the main post.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arknave (previous revision, new revision, compare).