Beta

Master Puppeteer

9bholmes
Description
Loading description...
Performance
Algorithms
View
AllIssues6Questions1Suggestions1Show Resolved
  • Please sign in or sign up to leave a comment.
  • LanXnHn Avatar

    For me, to understand the logic of this kata is 4 kyu, but coding is 6 kyu.

    It is dufficult to choose...

    • bholmes Avatar

      I understand. But I have also heard the opposite.

      My opinion would be that if the act of formulating a solution from the problem is considered X-kyu, then the kata should be rated X-kyu.

      But I guess, it is not for me to decide.

  • monadius Avatar

    This comment has been hidden.

    • bholmes Avatar

      Thanks for hinting that!

      Letting you know, that I am currently working on a fix.

      However, it turns out that it is not that trivial to do. If you have any suggestions, I am eager to hear what you propose.

    • monadius Avatar

      A simple idea is the following:

          mat = np.random.randint(0, 2, size=(n, n, n))
    k = np.random.randint(0, n)
    mat[k] = np.ones(n)

      Several (or zero) random persons (k) may be assigned np.ones(n).

    • bholmes Avatar

      Of course, way easier than what I was building. Thank you!

      I am satisfied to inform you, that your solution now fails successfully ;)

      Closing this.

      Issue marked resolved by bholmes 3 years ago
  • Blind4Basics Avatar

    Exceeded time limit of 0.001 seconds

    what are you doing in that test, exactly?

    because the current setup suggests that there are huge tests in there, but I cannot even print the length of the inputs, so it seems my function isn't even called, there.

    => ???

    edit: you need to say in the description that you provides a numpy array, not a regular python object. Btw, is taht a np.matrix or nested np.arrays?

    • bholmes Avatar

      This comment has been hidden.

    • bholmes Avatar

      This comment has been hidden.

    • Blind4Basics Avatar

      ah right, I forgot the ouput isn't shared when using the timeout utility... :/ (note: I was printing the length only, not the full input)

      in any case, 1ms is way too short. you cannot guarantee there won't be an overhead somewhere that will make the test fail.

      What is the size of those matrices? (about that, see my edit above)

    • Blind4Basics Avatar

      in the first line of the reference solution does not cause any issues: All tests pass and length is printed.

      no, it doesn't show up in the huge tests.

    • bholmes Avatar

      Something that is new to me also, good to know!

      Ok, I agree. Since you are more experience, what would you suggest out of the following choices: 10ms, 50ms, 100ms ?

      Size of the matrices is n^3 many integers. The type of the input is np.ndarray as the inputs are easier to generate using numpy and I can add this to the kata description.

      I see that there will be a discrepancy since the fixed example test cases are fed nested Python lists.

      However, finalizing the generation process with numpy's .tolist() causes even more time overhead which would require to reduce test case numbers if the input should always be a Python list.

      Any thoughts?

    • Blind4Basics Avatar
      • the difference in inputs is a bit unfortunate, but that can be handled easily by converting the fixed tests to np arrays before sending them to the user (but still add the info in the description)
      • timeout: I cannot tell, since I don't know:
        • the typical size of the inputs
        • the number of tests
        • the expected time complexity
        • do you run your solution alongside the one of the user in the measure time?
        • what the timing your solution is currently acheiving
    • bholmes Avatar

      This comment has been hidden.

    • Blind4Basics Avatar

      note: if you put a spoiler flag on your answer, I don't get notifications.

    • Blind4Basics Avatar

      yeah, 50ms is ok. My "microoptimized" O(n^3) solution (that must be arround N² on average, I guess) takes way longer than that, so it's ok against the expected time complexity.

      About that, I don't know if this is that a spoiler. Even with that info, I have so far no idea about how to do that. x)

      OK, closing. And I guess I'll never solve it. x)

      Issue marked resolved by Blind4Basics 3 years ago
  • LanXnHn Avatar

    In the sample test, some cases when y == z got 1

    So can a person attempt to hide a secret from self in this test?

    Also when x == y != z got 0

    Did it mean that a person not knowing what himself wish to hide from another?

    • Blind4Basics Avatar

      Did it mean that a person not knowing what himself wish to hide from another?

      that part makes sense, I beleive. Tho, it stretches the logic of this sentence in the description:

      Further, nobody has knowledge of any secrets of the master puppeteer himself.

      it's logically incorrect (but contextually understandable, I guess) => "nobody but himself"

    • LanXnHn Avatar

      I think I got some kind of idea:

      Change Secrets to Secrets on cards; y attempts to hide from z to At the back of the card written "From y to z"

      So a person may not know what the secret on the card is, when it wrote "From 1 to 1" at the back

      Maybe I am wrong...

    • bholmes Avatar

      Thank you for your feedback!

      The kata description has been augmented by a section that addresses this logical edge case:

      Any entries in mat where x == y or y == z are logically irrelevant and may hold a random value.

      resolved.

      Question marked resolved by bholmes 3 years ago
  • Blind4Basics Avatar

    the kata is currently totally undebuggable: the small random tests are already too big: if the user tries to print the input, here is what he's facing:

    11
[[[0 1 1 ... 0 0 0]
  [1 1 1 ... 1 1 1]
  [1 1 1 ... 1 1 1]
  ...
  [1 1 1 ... 1 1 1]
  [1 1 1 ... 1 1 1]
  [1 1 1 ... 1 1 1]]

 [[0 0 0 ... 0 0 0]
  [0 1 0 ... 1 1 1]
  [0 0 0 ... 1 0 1]
  ...
  [0 1 0 ... 0 1 0]
  [0 1 0 ... 1 0 0]
  [1 0 0 ... 1 1 0]]

 [[0 0 0 ... 0 0 0]
  [0 1 0 ... 0 0 1]
  [1 0 1 ... 0 1 1]
  ...
  [1 0 0 ... 1 0 1]
  [1 1 0 ... 1 1 0]
  [1 1 0 ... 1 1 1]]

    alongside of the above, the sample tests do not cover enough situations: I currently have a version that fails on one of those undebuggable thing.

    So:

    • more fixed tests with tiny matrices (but I cannot tell you of what kind so far...), both in sample tests and the full test suite.
    • easy random tests should be of sze up to... dunno, but no more than 5 for sure (they may go higher as long as the full input is visible when printed in the console)
    • as pointed below, there is no use for 1000 small tests. A batch of 100-200 should be enough. The perf constraint should be enforced with the big tests only.

    Cheers

    • bholmes Avatar
      • more fixed test cases
      • test groups sizes (w.r.t n) updated to a better fit
      • easy random test cases are now all fully printable
      • number of test cases in all groups adjusted to reasonable numbers
      • big tests now have performance constraint enforced via test timeout instead of number of test cases

      resolved.

      Issue marked resolved by bholmes 3 years ago
  • Blind4Basics Avatar

    unpublishing, until the author can clarify the points below

  • Blind4Basics Avatar

    (True), if x has knowledge of a secret that y attempts to hide from z

    tho, in the sample tests, there are cases where x y y is true, so "x knows a secret that y attempts to hide from himself" => that doesn't make sense x)

    => something is wrong

    • bholmes Avatar
      • Kata Description has been augmented by a section clarifying logical edge cases and how to handle / interpret them

      resolved.

      Issue marked resolved by bholmes 3 years ago
  • Blind4Basics Avatar

    Hi,

    the master puppeteer is somebody who, for all pairs of persons (P_i, P_j), knows at least one secret of P_i that he or she does not wish to disclose to P_j (obviously i!=j).

    This sentence is ambiguous: he or she does not wish to disclose to who that "he or she" is referring? the master, or P_i?

    Cheers

    • bholmes Avatar

      Thank you for all your feedback!

      • kata description is adjusted to clarify that.

      resolved.

      Issue marked resolved by bholmes 3 years ago
  • sid114 Avatar
    • your own solution times out half the time
    • 1000 tests is a bit overkill, even for a performance kata
    • speaking of which, you should add the performance tag for this kata
    • bholmes Avatar

      Thank you for your feedback!

      • performance tests are now timed and the reference solution does not time out anymore due to random test case sizes
      • number of test cases adjusted
      • performance tag added

      resolved.

      Suggestion marked resolved by bholmes 3 years ago