search

exercism / problem-specifications

Shared metadata for exercism exercises.
MIT License
320 stars 539 forks source link

Add a test for which a greedy algorithm fails #2385

Closed blakelewis closed 4 months ago

blakelewis commented 5 months ago

All of the existing tests can be satisfied with a greedy algorithm along the following lines:

for each coin value in descending order: use the maximum number of coins such that the reduced problem omitting this value is still solvable

This test demonstrates that this algorithm is not optimal, since it gives a solution of 11 + 9 * 1, instead of 10 + 10.

This change was discussed in the forum in https://forum.exercism.org/t/a-new-test-for-change/8891.

github-actions[bot] commented 5 months ago

Hello. Thanks for opening a PR on Exercism 🙂

We ask that all changes to Exercism are discussed on our Community Forum before being opened on GitHub. To enforce this, we automatically close all PRs that are submitted. That doesn't mean your PR is rejected but that we want the initial discussion about it to happen on our forum where a wide range of key contributors across the Exercism ecosystem can weigh in.

You can use this link to copy this into a new topic on the forum. If we decide the PR is appropriate, we'll reopen it and continue with it, so please don't delete your local branch.

If you're interested in learning more about this auto-responder, please read this blog post.

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.

BNAndras commented 4 months ago

I believe you just need to rebase the PR to get the schema validation to pass.

blakelewis commented 4 months ago

I think that it is OK now?