Unittests.test_tsp_medium_graph fails at grading process

Course Q&A Generative AI for Software Development Introduction to Generative AI for Software Develop
1

Hi folks,

I’m facing an issue with passing the grading process for the “Week 3 - Programming Assignment”. I can pass unittest when I work in the Jupyter Notebook (restart the kernel and re-run all cells), but when I submit my assignment for grading, it fails with the following messages:

Failed test case: Failed to achieve 85% of success in test cases. Examples of failed tests will be provided.
Expected:
At least 85% of success tsp_medium_graph running below 1.3s and achieving the correct distance,
but got:
Success rate: 97%.

Failed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 65).
Expected:
Solution no greater than 65% of Nearest Neighbor.,
but got:
For the graph starting at node 0, the target path distance to beat is 2911. Your algorithm returned a distance of 8001, greater than 76%.

May I kindly ask you to check what’s going on? Happy to share the code if needed.

Screenshot:

2024-09-26_08-19-27
2024-09-26_08-19-271920×701 102 KB

2

Hi! Thanks for your issue. The autograder peforms different test cases from the unittests, so it may be the case where you pass the unittests but fails in the autograding.

The success rate though looks weird as you passed indeed. I will investigate it. In the meantime, to on your second failed test case, you can investigate the graph where it failed by writing graph = generate_graph(nodes = 300, complete = True, seed = 65) and debugging it.

3

Could you please send me your jupyter notebook privately?

4

Done.

5

Just for visibility, this issue is now fixed.

2 Likes
6

Hello everyone,
I am also having weird results with both unittests.test_tsp_large_graph(Graph_Advanced) and unittests.test_tsp_medium_graph(Graph_Advanced).

For example, when I run a 300-nodes graph in the playground, I get a timing that is below 400ms and a distance that is always equal to 3855.0.

graph_example = generate_graph(nodes = 300, complete = True, seed = 42)

%%timeit
dist_med, _ = graph_example.tsp_medium_graph(0,T=3000, T_min=1e-3, alpha=0.995,k=2,nruns=1)
print(f'dist_med = {dist_med}')

dist_med = 3855.0
dist_med = 3855.0
dist_med = 3855.0
dist_med = 3855.0
dist_med = 3855.0
dist_med = 3855.0
dist_med = 3855.0
dist_med = 3855.0
388 ms ± 25.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

I then checked test_tsp_medium_graph in the unittests.py module and I found that the expected result for that particular graph is 3855.

        # Exeuction time limit (seconds)
        time_limit = 1.3
        solutions = [3855, ...]

If I run the test, it fails because my timing exceeded 1.3s.

unittests.test_tsp_medium_graph(Graph_Advanced)
Failed test case: Exceeded time execution limit for a tour starting in node 0. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 42).
Expected: tsp_medium_graph method must run in less than 1.3 seconds
Got: Time execution exceeded 1.3 seconds

Moreover, assuming that the timing issue is solved, my test would fail again because the success condition is that the ratio of the distance calculated by my code with respect to the expected value must be larger than 0.76 (it is equal to 1 in my case).

dist, path = q.get()
if round(dist/solutions[i],2) > 0.76:
          t.failed = True

Is there anything wrong in the test_tsp_medium_graph method? Or, what could explain such a difference in timing between the playground the the unit test environment?

Thank you for your help!

Kind regards,
Raffaele

7

A search of the Forum for “tsp_medium_graph” turned up several links - including this one:

8

@TMosh, yes I have found several other topics related to “tsp_medium_graph”. However most metion “issue fixed”, while other seem unaddressed.

@lucas.coutinho, did you have any chance to have a look?

Thank you,
Raffaele

9

Hi @Raffaele_Bolliger,

Yes, you are right, the unittests had an error in computing wether the test failed or not. It is fixed in the autograder but not in the unittests, I will update it.

10

@Raffaele_Bolliger

The unittest is fixed now, you may need update your environment to see the changes. Were you able to pass in this exercise after submitting?

11

@Raffaele_Bolliger,

Regarding your issue with the time execution. Could you please restart your kernel and try it again?

If this does not help, please send me your notebook in private so I can have a look.

12

it is broken now…
I get a NameError: name ‘dist’ is not defined for the function unittests.test_shortest_path(Graph_Advanced) which was working properly and my code passing before the unittest.py update

13

@marcobarbosa,

This is weird as I haven’t changed this function. Can you send my your unittests.py file?

Thanks
Lucas

14

@marcobarbosa I was getting the same error no matter what code I added to shortest_path but I was able to submit the assignment this morning and all tests passed. I cleared the output on all cells and then hit restart kernel and run all cells. The variables get “stuck” somehow :man_shrugging:

15

@lucas.coutinho, thank you.

There was a small error in the initial checks, but it was quickly fixed:

if  edges > nodes:
        raise ValueError("number of edges must be less than number of nodes")

should be

if not complete and edges > nodes:
        raise ValueError("number of edges must be less than number of nodes")

Now, my implementation of the tsp_medium_graph() method is good enough to pass the unit tests. I am still struggling to find a fast method for the test_tsp_large_graph, but this is another story, probably nothing to do with unittest.

Thank you for your support!

16

Good catch! I already implemented this fix.

Thanks!

17

I solved the medium graph, but the large graph seems impossible for me, after trying several algorithms and optimizations. It is a pain in the ass.

18

Hi @miguel.ossa,

Have you tried to get the code that fails and ask the LLM to find possible bottlenecks in it, then ask it to suggest any improvement?

19

I will try with bottlenecks, asking for improvements has been a continuous task.
What I don’t understand is that the time limit for large graphs is 0.5 and 1.3 for medium graphs, it doesn’t sound logic.