Skip to content

Instantly share code, notes, and snippets.

@ryanguill

ryanguill/puzzle-20170419.md

Last active April 20, 2017 15:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ryanguill/06ec5681ecff5ea2497f8ebcbcab3e33 to your computer and use it in GitHub Desktop.
Save ryanguill/06ec5681ecff5ea2497f8ebcbcab3e33 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
puzzle-20170419.md

Challenge:

Write a function that accepts an array of numbers and a number and returns all combinations of the numbers in the array that sum to the provided number. The result will be an array of arrays. The output arrays should be in order with the fewest numbers required to make the sum first. Each number in the input array can only be used once; if the same number is present in the input array multiple times it can be used once per occurrance. The goal is to find all combination of numbers from the input to reach the total, if the same combination could occur multiple times, you can decide if you return that combination more than once or not, whichever is easier for your implementation.

Expectations:

  • the function should be of the form f(number[], number) => number[][]

Examples:

f([1,2,3,4,5], 5) => [[5],[1,4],[2,3]]
f([1,2,3,4,5,6,7,8,9,10], 9) => [[9],[1,8],[2,7],[3,6],[4,5],[1,2,6],[1,3,5],[2,3,4]]

Judging

  • Correctness of the result. The solution must address the problem as specified.
  • Readability. This is not code golf - conciseness is good, but readable/understandable/maintainable is the goal.
  • You should include unit tests.
  • Bonus points for sharing your unit tests in the comments on the gist so that others can use them.

Rules

  • Original work only - feel free to research the problem and see if there are accepted algorithms to the solution, but dont just copy and paste an answer from stack overflow.
  • Submissions should be licensed under a permissive license (MIT/BSD/Apache 2.0/etc.)
  • You can use any language.
  • This is for fun and learning. There are no prizes except pride, knowledge and maybe karma.
  • Submit answers in the comments of the gist as a link Gist/PasteBin/Online REPL, not in slack.
  • Feel free to discuss the problem and solutions in cfml-slack in #friday-puzzle.
  • If you need to clarify something about the problem or rules, do it here in the comments on the gist, or at least copy the clarification here for posterity

Extra Credit Challenge

Take the same function but add another number to the input which is a percentage offset from the target that is acceptable. So 0 would be the same as the first function, a target of 10 with an offset percentage of 10 would find numbers that add up to anything between 9 and 11.

@iwburns
Copy link

iwburns commented Apr 19, 2017 •
edited

Here's my solution: https://play.rust-lang.org/?gist=06bf19f1fb9891dc2f4e55b2c0153ef2
(no "Extra Credit Challenge" attempted here)

@yogidevbear
Copy link

A Clojure solution (not mine) https://gist.github.com/madstap/a01600d9243a6229e6689d24d9deb275
Someone in the Clojure slack group was kind enough to give this a try. I believe there may be some optimised versions to follow :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment