Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
Updated to latest test fwk
Related to the issue below: the minimal
people
size that forms non-trivial counterexamples is at least 9, so with a limit ofpeople <= 8
the kata becomes a much easier version of the actual problem.This is definitely not intended (as author solution can handle non-trivial counterexamples just fine), so
people
should definitely go higher. I'd even say go up to12
or so. Potential performance requirements would be a necessary sacrifice for this, since graph complexity in these kinds of graph problems go exponentially as the input size; for low input sizes you can't test anything meaningful.Original Python version is fine, but JohanWiltink's reference solution used for Haskell and JS translation contains a wrong algorithm that will fail against certain inputs.
The problem is, the input size has been (arbitrarily) constrained to
people <= 8
due to performance concerns, and I believe the minimal counterexample that can be created is at least9
:So the reference solution in these two language versions needs to be fixed.
(More preferably, they should use the same algorithm as the original reference solution, precisely to prevent issues like this.)
already raised as issue
And Java.
Not applicable in description since it will make it language-dependent, hence hard to maintain
Reraised as issue by akar
In python 3.6 version there is 'weight' attribute in Node class which has no effect in solution.
You are not alone....
After
-O2
got introduced to C++ runner, some kata started timing out on compilation. It turned out that large amounts of strings initialized with literals take forever to compile. Large LUTs or precomputed answers or large string inputs used by tests made compilation times skyrocket.I can't remember the exact conclusion but I think that using std::string_view or c-strings helped in such cases.
A lot of assembly code is produced thanks to the inclusion of
std::string
literals andstd::map
usage.Using Clang 8 and
O2
optimization level (same environment as CW) my solution produces 515 lines of assembly, hundreds of which are just setting up the program state. Switching from strings to enums reduces it to 136 lines of assembly, half of which, again, simply create a(State, Event) -> State
mapping.Note that terse code does not always translate to good performance. Compare this code at:
https://godbolt.org/
with fx my code that uses char const* inside the FSM with a simple if / else.
The difference in assembly lines is:
370 vs >1800.
(Though this does not necessarily mean the same scaling in performance).
I like the fact that how stupid I feel after seeing other people's solution after solving the kata. One liner against my bare minimum required logn.
Half of the time spent was on understanding the description. I do not propose any suggestion to improve it because sometimes trying to figure out a little bit of unknown in this website was something we appreciated.
And CS + crystal + TS + C#
Loading more items...