search

exercism / problem-specifications

Shared metadata for exercism exercises.
MIT License
327 stars 541 forks source link

[Book Store] Modified test case to disallow greedy algorithm #2325

Closed Jayitha closed 1 year ago

Jayitha commented 1 year ago

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

  1. The test with ID cf868453-6484-4ae1-9dfc-f8ee85bbde01 prevents passing the greedy algorithm however this test isn't used in the Rust track

  2. 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 a poor job of disallowing an incorrect greedy approach. This test case checks for an important fundamental algorithmic flaw.

github-actions[bot] commented 1 year ago

Hello. Thanks for opening a PR on Exercism. We are currently in a phase of our journey where we have paused community contributions to allow us to take a breather and redesign our community model. You can learn more in this blog post. As such, all issues and PRs in this repository are being automatically closed.

That doesn't mean we're not interested in your ideas, or that if you're stuck on something we don't want to help. The best place to discuss things is with our community on the Exercism Community Forum. You can use this link to copy this into a new topic there.

Note: If this PR has been pre-approved, please link back to this PR on the forum thread and a maintainer or staff member will reopen it.