Pretty elegant and classic kata about dynamic programming.

Looks good.

In JS, you are using lots of global and var variables where I would prefer to see const and let - the undeclared ones may be overwritten somewhere. In JS ( as opposed to Python I think ) undeclared variables are implicitly declared as global, and you really should not let that happen. White-coloured names ( in the CW environment ) are always suspect in JS sources. And var should not be used for for-loop counters.

The original issue has been solved, so closing. But try to update variable declarations for JS sometime, if only for future maintainability.

Good point. I added return messages in JS and Python to give back an optimal route and cost vs user provided route and cost.

Unless someone actually finds a kata this is a duplicate of, this might get approved someday in the not too distant future. Note that this comment is not an Issue.

I expect the twist with the asymmetric travel costs is actually enough to make it not a duplicate anyway.

@dfhwze, brute force permutation, DFS, and BFS all seem to do the same thing at the same time complexity. For an EXP task, I don't see that as a problem actually; you don't want to ask for micro-optimisations and you can't ask for any lesser optimisation ( unless there's some DP magic possible, but AFAIK current theory says that can't be done for a TSP ).

Failing random tests will give a message expected $COST to be equal to $COST - that's not helping solver; you're not testing what he's actually returning.

The failure message could give the actual user output, its cost, a possible solution, and its cost. That would take away much possible confusion. Explain what each item is!

See also the discourse on Least larger - that allows multiple solutions as well, and many people were very confused. Maybe they didn't read the description, maybe they were just stupid, but you do not want to deal with the fallout. :S Give good failure messages!

( This was written for the JS tests. I presume it's applicable to the Python tests. )

I actually did not mean the production random tests should be boosted, sorry. 100 random tests is enough. But in that kumite, boosting it to 10 000 was useful for finding a failing case.

Nice work on the multiple solutions. You also adjusted the description - good. I'll see if the problem is fixed and close this, or if I have any remarks yet.

Per your suggestion, I've changed the random tests to check equality on solution costs rather than route (JS and Python).
Upped random test count to 1000.

( JS, possibly others )

  it("custom test",()=>{
    chai.assert.deepEqual(
      bestRoute( ['Kiev', 'Notgnihsaw', 'Beijing', 'Santo Domingo'],
                 [[    0, 6654, 3378, 1864],
                  [ 3466,    0, 5703, 9277],
                  [ 7820, 2874,    0, 1771],
                  [ 4062, 9079, 9490,    0]] ),
      ['Kiev', 'Beijing', 'Santo Domingo', 'Notgnihsaw'],
      `bestRoute ${ JSON.stringify(['Kiev', 'Notgnihsaw', 'Beijing', 'Santo Domingo']) } ${ JSON.stringify([[0,6654,3378,1864],[3466,0,5703,9277],[7820,2874,0,1771],[4062,9079,9490,0]]) }`
    );

This randomly generated test shows the specs are ambiguous.

When I take the first lowest cost of permutations of cities, I fail the test with a result of [ 'Kiev', 'Santo Domingo', 'Beijing', 'Notgnihsaw' ]. If I take the last lowest cost, I succeed. Cost in both cases is 17 694. See this fork. Tracing of cost of all possible itineraries has been provided ( may have to expand the header ).

Description does not specify which result to return in case of multiple possible answers, and the random tests do not allow for the possibility. It would be possible to calculate a reference cost instead of a reference answer, and check the user answer costs the reference amount.

Random tests normally number 50, but there is time to run 10 000, which greatly increases the chances of generating a failing test.

Yep!

Thank you; I've added random tests for Python and Javascript.

Thanks for the feedback, I've updated the code.

Is a performance version possible? Is this problem susceptible to dynamic programming?

( My theoretical background is lacking here - I actually don't know if this problem can be solved faster than O(n!) )

JS version of the kata is using legacy test framework and legacy version of Node JS.

You correctly import chai, but then use Test.assertDeepEquals when you should be using chai.assert.deepEqual. Using that should make Node 14.x selectable.

Cleaning up the unapplicable comments from the initial code would also be nice. Currently, it looks a bit lovelessly slapped together.

current tests are so weak that any strategy passes -> brute force permutations and BFS included