While going through the community solutions to the Book Store problem on the Rust track, I noticed most solutions adopted a greedy algorithm to solve the Book Store problem, which I believe is incorrect.
The greedy algorithm scans the list of books and adds the book to a suitable set whose increase in cost is minimized. This approach happens to coincidentally work since the order of the books in the input in all the tests so far in the Rust track happen to be favourable to the greedy approach.
There are one of two ways to solve this issue
The test with ID cf868453-6484-4ae1-9dfc-f8ee85bbde01 prevents passing the greedy algorithm however this test isn’t used in the Rust track
The second approach is to modify this test case slightly. We can just reorder the input.
I chose the second approach and reordered the input data. Of the first 10 community solutions, 7 (which use the greedy approach) fail the modified test case.
I understand not all edge cases are checked for. However, I believe this change is important because the current test cases (at least in the Rust track) do not disallow an incorrect greedy approach. This test case checks for an important fundamental algorithmic flaw.
Here’s a link to my PR
Thanks for bringing this up.
Tests in problem-specifications are considered immutable. We sometimes deprecate a test if it’s actually incorrect. Otherwise, we always add new tests.
Luckily I just got done writing a test generator for the Rust track. This makes it very easy to add the existing test case from problem-specifications to the Rust track. Every exercise still requires some manual work on the template though. I will do this exercise next. Should be a matter of days.
Since a test already exists in the specification that solves this issue, your test generator should do the trick. Thank you for letting me know. I’ll be mindful of tests being immutable in the future.
There’s little reason to add a new test to the spec when the spec already has a test which exercises that property
I think my thought process was - “it wouldn’t hurt to do both” i.e. have more than one test that discouraged the greedy solution which seemed like a good idea. I thought it could help improve the overall quality of the test case since the only thing you’d be changing was the order of the input, the answer would remain the same. The test would continue testing whatever it was testing before and more. But this is a small thing.
I understand your point and it makes sense.
Thank you for your interest and willingness to help improve Exercism and the tests! While this specific test may not make sense, I do appreciate the effort
When it comes to unit tests, more is not better. Each and every additional unit test should have clear value. If there is no clear value add to a test, it should not be added.