Beta

One Line Task - Travelling Salesman Problem

6encrypted-oreo
Description
Loading description...
Restricted
Algorithms
View
AllIssues3Questions1Suggestions1Show Resolved
  • Please sign in or sign up to leave a comment.
  • Blind4Basics Avatar

    ok, look here, please: https://www.codewars.com/kumite/67928fddb47458a990ee6388?sel=67991f05b3e3da841ece0758

    • full cost of a path is on average around 4400, for 150 tests.
    • both implementations are yielding close values in any case, since the max diff is generally less than 500
    • the score is computed using score += expected_cost / actual_cost, which seems wrong to me, because an accidental huge diff will weight more on the final value while, in the end, what you actually want to test is that both solutions are randomly behaving "the same" (aka, sometimes exp is bigger, sometimes it's smaller).
    • note that on 150 tests, there are generally like 140 where both approaches give the same result. That seems to me a way more efficient measurment to try to guess if both approaches are compatible or not.
    • If I'm not mistaken, since score += exp_cost /actual_cost, the value increases when exp is worse than actual. Funny thing is that the test is (t-score) <= 0.925 * t which means the actual solution has to be better than the expected one to pass the test. No? Nope, that part is ok, I'm just too much tired.

    In the end:

    1. The testing process is just totally wrong not lax enough, as far as I can tell. A better measurment would be imo to do the following:
      • score += 0 when both costs are equal
      • score += 1 when actual is worse than exp
      • score -= 1 when actual is better
      • at the end, check that score/number of tests in the batch is low enough. The big question being "how much?", but at least, here, accidental huge differences between results won't wheight on the score.
      • make sure solutions that give better results consistently may never fail the tests.
    2. The score value in the assertion messages is not very informative for the user, since it's never explained what the value actually means.
    • Blind4Basics Avatar

      Well, I didn't realize I was working on an updated version of the tests. My solution consistently passes, now, so in the end, I guess the tolerance is actually lax enough.

      Issue marked resolved by Blind4Basics last month
    • encrypted-oreo Avatar

      The reason I do tests like this is such that if your solution does worse on some tests, but does better on others, it can cancel out.

    • Blind4Basics Avatar

      Yes, I got that part. The problem was that with a not large enough tolerance, accidental "not optimal cases" could sometimes weight too much. But now it looks ok, so "anyway".

  • Blind4Basics Avatar

    this assertion is incorrect:

    test.expect(len(path) == 6, "Your solution goes through the same point at least twice" if len(path) < 4 else "Your solution doesn't go through all the points")

    Messages are swapped.

    (you should aslo use a dedicated function to do all the fixed tests, rather than duplicate the code in the sample tests and the full test suite several times. You'd need to define the function twice, tho: once in preloaded (for the sample tests), and once again at the beginning of the full test suite, so that the user cannot override it easily).

  • Blind4Basics Avatar
    • Give the current char count in a test.it message, so that the user always know "where he is" about that.
    • Also, you should standardize the batches of random tests, calling a single function with different arguments for each batch.
  • Blind4Basics Avatar

    ok, I got the char limit, but I think your cost function is too much strict: I get these in the random tests:

    Your solution got 49.87 points, which is less than the expected number of points (50).

    while I definitely implemented what was asked for.

    => ?

    • encrypted-oreo Avatar

      I see you have already solved the kata, so I cannot see the code that should work but doesn't. Could you please send it here?

    • Blind4Basics Avatar

      it's the very same code. It fails roughly 70% of the time, I'd say (maybe even more)

      edit: the main diff is that yours uses kind of a randomized order to explore the decision tree, because of the set, while mine explores the decision tree always in the same deterministic order. Not sure how it affects your testing process, but that's the only meaningful diff I can see.

      edit²: it got invalidated because you changed something. If ever you need the link, it's here

    • encrypted-oreo Avatar

      Weird. Your code should pass, but it's not. I'll add a little bit of tolerance, such that you can pass with 49.95 points at least for a test suite of 50 tests.

      EDIT: I won't do this, for those who can't see my spoilered comment below.
      EDIT 2: I will add a 50/50 chance of this happening actually, just for fun. What could possibly go wrong?

    • encrypted-oreo Avatar

      This comment has been hidden.

      Question marked resolved by encrypted-oreo last month
    • Blind4Basics Avatar

      What's this cost "exactly"? if you just add tolerance, you'll need to add a bit more. iirc, I got some lower values, also

    • Blind4Basics Avatar

      why did you close the issue question? The tests are still wrong.

    • Blind4Basics Avatar

      EDIT 2: I will add a 50/50 chance of this happening actually, just for fun. What could possibly go wrong?

      What are you talking about...? It's not about chances, it's about the cost function not behaving properly. => don't rely on luck, fix the tests.

    • encrypted-oreo Avatar

      I closed the question as the problem is in your key parameter.

    • Blind4Basics Avatar

      Prove it?

      How the output would be wrong?

      To be clear: either my code is wrong and it shouldn't pass consistently, or my output is valid considering the specs and the cost function is wrong. Afaik, it's option 2. In any case, this is actually an issue.

    • encrypted-oreo Avatar

      It might be to do with tuple comparison. But I don't know. I have added a tolerance anyway, that's not a 50/50.

    • Blind4Basics Avatar

      You're not answerig my questions/problem.

      1. What are you actually testing with the cost function? As in, what property of the path are you testing?
      2. Reading again the description, I'm wondering about something: are we supposed to find an actually optimal path, or an apprximation of it? Afaik it's an approximation. In that case, my output looks valid to me and it should never fail the tests.

      => ?

    • encrypted-oreo Avatar

      The cost function traverses the path and calculate the total distance cover by the path. Your task is not to find an optimal path (in 120 characters, it is impossible AFAIK), it is to implement the nearest neighbour algorithm.

    • Blind4Basics Avatar

      But that algorithm doesn't garantee actual optimality. So the testing process definitely looks wrong to me. Unless you can prove otherwise.

  • Blind4Basics Avatar

    Hi,

    • Don't EVER use test.expect without providing a useful error message to the user.
    • According to the description, I'd guess the output must end with [0], though, the sample tests do not raise any error when it's not the case. So, what's the actual ouput format? => an actual example should be given in the description.
    • EDIT: nice... Sample tests work, but not a single test of the full test suite => !?? / Edit²: looks like it's the missing trailing 0 => both test suites are inconsistent.

    (damn it, Iget 120 124 chars... x/ )