Ad
  • Custom User Avatar

    Updated to latest test fwk

  • Custom User Avatar

    Related to the issue below: the minimal people size that forms non-trivial counterexamples is at least 9, so with a limit of people <= 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 to 12 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.

  • Custom User Avatar

    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 least 9:

    You found a better solution than the reference implementation.
    Please raise an Issue with the following information:
    
    language: JavaScript
    input: [[1,0,1],[2,1,1],[3,2,1],[4,3,1],[5,4,1],[6,5,1],[7,6,1],[8,7,1],[0,8,1],[4,3,13],[4,0,37],[6,5,32],[6,1,68],[8,7,44],[8,2,61]]
    actual output: [[3,4,13],[0,4,37],[5,6,32],[1,6,68],[7,8,44],[2,8,61]]
    expected output: [[0,8,37],[1,8,68],[3,4,13],[5,4,32],[2,4,5],[7,6,44],[2,6,56]]
    
    Thanks in advance!
    

    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.)

  • Custom User Avatar

    already raised as issue

  • Custom User Avatar
  • Custom User Avatar

    Not applicable in description since it will make it language-dependent, hence hard to maintain

  • Custom User Avatar

    Reraised as issue by akar

  • Default User Avatar

    In python 3.6 version there is 'weight' attribute in Node class which has no effect in solution.

  • Custom User Avatar

    You are not alone....

  • Custom User Avatar

    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.

  • Custom User Avatar

    A lot of assembly code is produced thanks to the inclusion of std::string literals and std::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.

  • Default User Avatar

    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).

  • Default User Avatar

    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.

  • Default User Avatar

    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.

  • Custom User Avatar

    And CS + crystal + TS + C#

  • Loading more items...