Ad
  • Custom User Avatar

    how does that work?

  • Custom User Avatar

    First time to see a bfs implemented with while-loop and queue and the code is very delicate, Thanks.

  • Default User Avatar

    std::stack is a standard container like std::vector or std::list. It is a "stack", so a last-in-first-out (LIFO) container.
    For offline use if you want to compile it, you need to #include <stack> header (and #include <string> too).
    The Kata tests already have these headers included so I gracefully left those includes. (after years thinking about this, maybe it was a little confusing choice...)

  • Custom User Avatar

    What do you mean by "std::stack op" ? It doesn't compile for me

  • Custom User Avatar

    Great solution: a nice way to get the median!

  • Custom User Avatar

    I tried both solutions (numeric and with string) and the string seems to be 10 times slower than the numeric one. But could be my setup. Still your explanation was pretty good.

  • Default User Avatar

    Thanks for the heads up! I've recoded it to check balance as well as counts. :)

  • Default User Avatar

    This solution seems wrong.
    In your isPerfect() you are only checking whether the nodes in the tree equal to 2^n-1 or not.
    This will result true in case of non-perfect trees with proper nodecount.
    Simple example:


    O
    /
    O
    /
    O

    nodeCount = 3; log2(count)+1 == log2(count+1), but it's obviously not perfect.
  • Default User Avatar

    In C++ after you create an array of arrays you can use [][] for multidimensional indexing.
    But you can not declare an array of array by writing [][]!
    In C++ the mentioned int ans[4][4] is just one array: int *ans. Meaning that it's equivalent with int ans[16] and the compiler is nice enough to do the reindexing for you.
    It is used to make sure that every sub-array's dimension is equal, or to ensure that the allocation of the n x n element is contiguous, hence it is one (contiguous) array.

    True multidimensional arrays on the other hand can be "anywhere" in memory, only sub-arrays will be contiguous, not the whole.
    And to hell: even every sub-array can have different dimension!

    The functions are expecting int **, so you have to create an array of int * first, then the sub-arrays in that.
    Many solution used the new[] allocation... but I really hate the idea to using new without delete, so I went with static (aka globals :) ).

  • Default User Avatar

    Thanks for looking at my solution and giving some feedback!

    I agree that it might be overkill for the problem as stated. But when time permits, I always try to go for the solution that is easiest to maintain/update over time (e.g. low code churn, only having to make changes in one spot).

    The lambda isn't really required for my solution. I could just hard code it to 2 and then update it if new operators are ever added. But then again, that violates my goal of only having to make a change in one spot.

    The stringstream I thought was the fastest way of doing string concatenation, but Google searching shows that I'm probably wrong. So I could easily have just used a string instead.

    The precedence offset was simply my way of handling parentheses (especially nested parentheses). Too bad it looked like a jigsaw puzzle. I strive for readability as well.

  • Default User Avatar

    However your solution might be more universal if there would be a need to expand for more operators, in my opinion using structs + map + lambda + stringstream + some jigsaw-puzzle with offsets is a little bit overshoot to the current problem's size.

    Although my appreciation for the not copy-paste-from-somewhere solution.

  • Default User Avatar

    Reading the description again and again... there's already a bold "at most one operation" in it, so not really neccessary to change it.
    Although a note might be healpful, like: If you intend to not do any operation on the number, return [n, 0, 0].
    Also it might be just my opinion. Seems many had no issue with this. :)

  • Default User Avatar

    Strictly speaking maybe it's not another place but 949 guys passed the kata so I can't change it. Do you have a better description?

  • Default User Avatar

    I found an error in the tests:
    Input number: 3447799
    Expected: equal to [ 3447799, 0, 0 ]
    Actual: [ 3447799, 1, 2 ]

    Citation from Kata description:
    "Choosing the index of a digit in the number, remove this digit at that index and insert it back to another place in the number."
    I think from 0 to 0 is not another place.

  • Default User Avatar

    After completed this Kata, I've looked upon the previous solutions and hell...
    The test cases are not adequate! Almost everybody is using recurse and totally forgets about big numbers!

    Using recursive algorithm with big numbers may be a suicide way (as may kill your stack).
    A recurse modulo-GCD can go into a 127-deep recurse-chain. (which can cost 24000 CPU-tick vs. iterative version's 490 tick worst case)
    I highly discourage using that, in particular if there are more ways to avoid the recurse!

    Also if you can't be sure that numbers will always be small enough, then you really should: first divide then multiply!
    (a * b / gcd() can overflow eg. a = 2^64-2, b > 1)

    Note for strings:
    repeately building the exact same string from a non-changing "constant" (least common multiplier) in every step in the result-building loop... well you should avoid that too.
    (always pre-occupy memory (reserve) if you can estimate the usage)

  • Loading more items...