5 kyu

Multidimensional Neighbourhood

38sgerodes
Description
Loading description...
Algorithms
Logic
Data Structures
Arrays
Performance
View
AllIssues4Questions1Suggestions2Show Resolved
  • Please sign in or sign up to leave a comment.
  • LKchemposer Avatar

    This comment has been hidden.

    • FArekkusu Avatar

      Yes, the Docker version used on CW was updated a year or so ago, and the random generation inside Docker containers became twice as slow. With the current test setup the kata is impossible to complete.

      Question marked resolved by FArekkusu 5 years ago
    • sgerodes Avatar

      You are right. My solution that had a time score of less than 4 secs get a TLE as well...

    • sgerodes Avatar

      Even dividing the number of test by two gives my solution a runtime of 10 secs... What the hell they did to the system that slowed it down to this level?

    • sgerodes Avatar

      Ive scaled the tests 6-10 times down. My Solution scores about 4 secs. It should give room for a variety of solutions. Try it out

  • Ching Ching Avatar

    Kata description:

    Typo: "could be a depp list or a deep tuple" <- depp?

    N-dimensional and N-length: implying that dimension and length must be the same (N)? matrix a N-dimensional matrix. N >= 0 coordinates of the cell. It is a N-length tuple.

    Please clarify the test description. There will be one Tests with a very deep matrix <- one "Test" or more than one "Tests"? There will be 300 Tests with 9 <= distance <= 12 There will be 1000 Tests with N == 4, Dimension size == 5 <- What's "N"? What's "dimension size"? Do you mean 4-dimensional and tuple length of 5? There will be 400 Tests with N == 8, Dimension size == 3 <- What's "N"? What's "dimension size"? Do you mean 8-dimensional and tuple length of 3?

    Suggestion: State the same details (e.g. dimension, tuple length, distance) for all four types of random tests.

    • sgerodes Avatar
      1. Yes, N is always the same. Thats why the same letter is used. To signilise that the NUmber of dimensions is equal to length of the coordinates-tuple.
      2. "deep" - I wanted just singnalise that they could have very big dimensions. But I will cut this word if it is irritating.
      3. Sorry, but it should be obvius... the N is the amount of dimensions, as already mentioned in the description. Every dimension has a size. I dont think it should be changed. Please let me know what you think. If you disagree please make a suggestion for the change, because I think it is the best was to describe what is happening.
    • Ching Ching Avatar

      OK, thanks for your clarification. The issue was that I confused myself by mixing up the tuple length of the centre coordinates and the tuple length of a dimension in the matrix ("dimension size")... Not sure if any rewording is possible.

      No, "deep" is not irritating. Just that "depp" is a typo. You may add the word back in the description.

      Just caught another typo, please correct it: "apllied".

      Thanks again!

  • Voile Avatar

    In the random tests the elements in your matrix are tuples, not lists.

    If both lists and tuples has to be supported it should be mentioned in the description.

  • Voile Avatar

    The random tests are too big. It's virtually impossible to compare results from them ourselves (for debug purposes, for example).

    Can we have small random tests, and then big random tests?

  • sgerodes Avatar

    WORK IN PROGRESS. Accidentally published

    • sgerodes Avatar

      Is it okay if I use one of your solutions guys to put in in the _reference?

    • FArekkusu Avatar

      I haven't seen anybody arguing about such things at least ¯\_(ツ)_/¯

      If you're going to do that, you should choose B4B's top solution as it's currently the fastest one.

      At the same time, you could try using my for testing purposes(!) because it's not as optimized but uses the same idea and should not time out too easily (B4B may disagree with me, but IMO this would be an indication that you're pushing the constraints of a non-performance-oriented kata too hard).

    • Blind4Basics Avatar

      no problem, you can use mine if you want. Note: don't set up a tests suite that takes 11s with that solution though: let some margin for various but still fast implementations. ;)

    • sgerodes Avatar

      So, guys, I have composed a solution that is more performant that both yours.) Sory, i will take mine.))) But anyway thanks for the support! B4B scores 4.4-4.5s Mine 3.5-3.8 ^^.

    • sgerodes Avatar

      I did it harder, so my old not performant solution is now not surviving and the best by now has about 8 seconds. I think there is enough span to build performant solutions. what do you think?

  • FArekkusu Avatar

    I think you should make this kata harder.

    I've played with your tests replacing your reference with mine and changing the setup to this (quick generation of similar tests, small exec time):

    MAX_DISTANCE = 5

TEST_COUNT_SMALL = 150
MAX_MATRIX_DIMENSION_SMALL = 5
MIN_DIMENSION_SIZE_SMALL = MAX_DIMENSION_SIZE_SMALL = 2

TEST_COUNT_BIG = 100
MAX_MATRIX_DIMENSION_BIG = 7
MIN_DIMENSION_SIZE_BIG = MAX_DIMENSION_SIZE_BIG = 4

    from it I got the following results:

     Author | time (sec)
---------------------
  me    |     1
  B4B   |     1
  you   |  2 - 2.5
  ZED   |  timeout

    With the following constraints you can use a slow algo and still pass (that's why ZED assesed it as 7 kyu). Either improve the test suite or simply resolve the issue (and remove mathematics tag as well, as you'd allow solutions which don't use math at all).

    (Raising as an issue to let the author decide what to do with the kata before somebody suddenly approves it.)

    • Blind4Basics Avatar

      This comment has been hidden.

    • FArekkusu Avatar

      My solution is okay (I'll still get the points even if it dies :D, and after I made the RNG "fixed" the difference in time was pretty small (run a couple of tests, maybe for some high enough values my solution may become a lot slower than yours, idk)). Moreover, I'm proposing to make the tests harder, not overkill. Ideally, for Von Neumann neighborhood solutions should iterate only over the elements which will be the part of the result, and not the whole N-dimensional cube with the volume of (distance * 2 + 1)**(dimensions) - which is what I'd like to see as the requirement.

    • Blind4Basics Avatar

      nope, your new solution would still chock to death for what I'm suggesting (you didn't get the idea behind apparently. Unless the solution showing up under your message isn't the good one). But the validity or invalidity of your solution is not the point of my suggestion, here.

      EDIT: mmm... Or rather, I didnt' get your message... x) (first part of my answer. The second still applies)

    • sgerodes Avatar

      Added performance. Try it out guys. My solution gets 8-9 secs

    • Blind4Basics Avatar
       
      MIN_DISTANCE_HUGE = 3
MAX_DISTANCE_HUGE = 4

      Mmmmh... that short... ;p

    • Blind4Basics Avatar

      ok, about performances, we have a problem. I timed the different functions of interest during the random tests, using my soluiton as the user's one (butI did it in that fork of your solution, to be sure I use the last version of the test suite):

      Time: 5853ms Passed: 433 Failed: 0

Test Results:
Fixed Tests
1D Matrix (3 of 3 Assertions)
2D Matrix (4 of 4 Assertions)
3D Matrix (4 of 4 Assertions)
Completed in 0.42ms
Edge Cases
Cutted Neighbourhood (4 of 4 Assertions)
Index Out Of Matrix (4 of 4 Assertions)
Distance Zero (2 of 2 Assertions)
Empty Matrix (2 of 2 Assertions)
Completed in 0.16ms
Random Tests
Random Test Cases Small (200 of 200 Assertions)
Random Test Cases Big (150 of 150 Assertions)
Random Test Cases Huge (60 of 60 Assertions)
Completed in 5323.93ms

Log
('_reference', 2.9078891277313232)         -> yours
('get_neighbourhood', 0.5193781852722168)  -> mine
('random_hyperrectangular_matrix_and_random_coordinates_within', 1.7909765243530273)

      So, two things: your solution is very slow, the random generation takes a huge part of the time too.

      • About the last point, you can speed up a lot the things by reusing several times the same array, with different coordinates/distances, for example. But to do that, you have to ensure that the user doesn't mutate the inputs (just double check the first tests, to be sure that you get the same output after the second call.
      • about your solution, well... if you wanna push further, you'll either have to rewrite it or to use another one.
    • FArekkusu Avatar

      You should change the way you're creating matrices. The tests are TOO random because the same code may pass the tests in 4-6 sec depending on how the matrix is generated (i.e. how many dimensions there're, how long the arrays are).

      I also tested my code using B4B's fork:

      ('_reference', 3.8665924072265625)
('get_neighbourhood', 0.6458971500396729)
('random_hyperrectangular_matrix_and_random_coordinates_within', 2.835817575454712)

      You are enforcing more optmized solutions now (though still very slightly, as I noted above) but not because tests are intensive, but because your own solution is taking up lots of time. As B4B said, you should either replace your reference altogether or rewrite your solution because instead of using math (again, you have added mathematics tag), you're using lots of useless and slow functions which you have written during creating previous katas.

    • sgerodes Avatar

      @FArekkusu You think I should make the random span smaller?

      @Blind4Basics "you have to ensure that the user doesn't mutate the inputs (just double check the first tests, to be sure that you get the same output after the second call." Do you mean I should do the first test twice? like this 

      def test()
  expected = mine()
  assert(his(),expected)
  assert(his(),expected)
    • sgerodes Avatar

      The idea of reusing the array is great. Probably I can use tuples instead of lists in the generator to ensure the user does not mutate the input. So the matrix will be a N-deep tuple. I hope it will not affect the times so much.

    • sgerodes Avatar

      The idea of reusing the array is great. Probably I can use tuples instead of lists to ensure the user does not mutate the input. So the matrix will be a N-deep tuple.

    • Blind4Basics Avatar

      yes to your two "three" answers above. ;) And about the first of them:

      • provide a specific error message for the second check "if you fail this test, might be you're mutating the input. Don't do that." or something like that
      • then you can resue the same input, varying the cordinates and the distance at each call.
    • FArekkusu Avatar

      You think I should make the random span smaller?

      Yes, you could break up each set of tests (small, big, huge) into smaller randomized subsets to minimize the difference in generated sizes/dimensions.

      Alternatively, a good solution would be to create a few fixed matrices (as tuples of tuples) gradually increasing their size/dimensions count, and then randomize only the central coordinate and distance.

    • sgerodes Avatar
      • To prevent mutating the input matrices are now deep tuples
      • Added a deep matrix test
      • Added a big distance performance test
      • Test are on random values, but fixed sizes
    • FArekkusu Avatar

      Okay. Close the issue when you think you're done with your changes.

    • FArekkusu Avatar

      In fact, it should be okay now. Closing.

      Issue marked resolved by FArekkusu 7 years ago
    • Blind4Basics Avatar

      @FArekkusu; what about the ranking? still 5?

    • sgerodes Avatar

      Cmon, i think it is at least 4. Not obvious programming rutine, , Performance. I would give myself a 3 if you ask.:D

    • FArekkusu Avatar

      I've changed my vote to 4 kyu (still feels kinda 5 kyu to me but whatever).

      Nah, neither the algorithm required nor its implementation are hard, and this "performance requirement" is only a method to reject inefficient trash solutions (and to not allow this kata to be rated as 6 kyu at most, which is ZED's vote on a human difficulty scale). 4 kyu would be WAY too generous.

    • Blind4Basics Avatar

      hard 5 it is, then.

  • Blind4Basics Avatar

    This comment has been hidden.

  • Blind4Basics Avatar

    Another thing: you should provide the inputs of the random edit: SAMPLE tests in a readable fashion. It's already enough mind numbing to deal with the mutlidimensionality, no need to force the user to think about what actually are the data in the input (and honestly, apart from the first one, I have no lcue of what your computing with the formula you use. So just paste the full input arrays... ;p )

    • Blind4Basics Avatar

      I just read this message again... 'made sort of a mistake in it, ofc I was thinkgin about the sample tests, not the random ones... x)

    • sgerodes Avatar

      " you should provide the inputs of the random tests in a readable fashion" How can i do it? The inputs are massive! or do you mean messages like this "Type: 'moore'; Indexes: (1,2,3); Distance: 3" without the input array.

    • Blind4Basics Avatar

      not the ranodm, I told you, the SAMPLE test! ;) (those visible by the warrior in the trainer. Not all of them, but at least all the 1D and 2D arrays)

    • sgerodes Avatar

      changed

      Suggestion marked resolved by sgerodes 7 years ago
  • Blind4Basics Avatar

    damn, that was something, this time... x)

    EDIT: btw, you have to tell in the description that negative indexes are considered invalid, here.

    • FArekkusu Avatar

      I didn't get "completed from first attempt" because none of the previous 3 katas used this vile trick...

      @B4B, the kata is still not very hard, IMO. I think 4 kyu is a bit too much considering how it's not a big step from his previous katas (ZED even assesed it as 7 kyu, lmao).

    • Blind4Basics Avatar

      you found it easy, perfect, choose your rank suggestion. I find it harder than you? whatever! (And you perfectly know that ZED ranking is... well, ZED ranking...)

      (and I did it while being tired to death so that surely didn't help :p )

      EDIT: btw, you still did choose 5 kyu, though... Not so far...

    • FArekkusu Avatar

      I chose 5 kyu because it's definitely harder than the previous katas but not much. If it was a standalone kata, I'd probably agree with you, but after doing the 2/3-D versions it doesn't look like a big challenge...

      I can see why ZED chose 7 kyu, though. Apart from his passive ability "vote every kata 2 ranks easier than it really is" his code passes the tests despite being terribly slow.

    • sgerodes Avatar

      @Blin4Basics

      "negative indexes are considered invalid"

      ...you should return an empty array if any of these conditions is true:
* Index is outside the matrix
...

      This should be enough, dont you agree?

    • Blind4Basics Avatar

      not enough specific for python since (-1,-1) is perfectly valid index. That's why I suggested that. But that's my opinion on the subject, ofc.

    • sgerodes Avatar
      • added info in the description about negative indexes