Ruby - "Vending Machine" returning Change

Question

In ruby, I'm trying to make a simple financial script to return a group of numbers [i] that represents the amount [n] inputed by the user.

My array holds "pieces" of an payment: [5.0, 1.5, 0.5, 2, 1] into installments of the total amount.

Example: In a arr = [5.0, 1.5, 0.5, 2, 1] the total amount is equal to 10.0.

If the user inputs 4.5, the method should return [i] as [1.5, 2, 1].

Anyone could help me building the [i] method?

Are you looking for a subset of `arr` that sums to the desired value? If so, do the values have to be contiguous? How do you know that the sum is always achievable? I think you need to edit your question, it's currently quite ambiguous. — pjs, Aug 11 '18 at 16:59
Why would input of `4.5` return `[1.5, 2, 1]`? That doesn't explain any pattern. What happens with `9.4`? `-0.1`? `9834455.0`? — ForeverZer0, Aug 11 '18 at 17:36
If the result is well-defined, then what's the logic? You didn't explain this at all in your question. (Even if you need to choose values from the original `arr`, it's srtill ambiguous -- Should `2` be represented as `[1.5, 0.5]`, or `[1, 1]`, or `[2]`?) If the result is random, then what are the constraints? (Are we limited to that `arr`? Can we repeat values? What if there's no solution?) Again, you didn't specify this at all in your question. — Tom Lord, Aug 11 '18 at 19:44
I am voting to close this question, as it's unclear what you are asking. You need to give precise requirements; this is ambiguous and open to interpretation. — Tom Lord, Aug 11 '18 at 19:46
I've a amount of values that represents a full payment, in this case, the full amount is equal to `10`. My array holds "pieces" of this payment, into **installments** of the total amount. So if someone pays me `3.5`, I know in my array should return `2` and `1.5` values! — gbs0, Aug 11 '18 at 22:22

score 0 · Answer 1 · answered Aug 11 '18 at 20:46

0

If you're using Ruby 2.4 or higher, you can just do arr.sum, to find the sum of an array containing only numbers.

https://ruby-doc.org/core-2.4.0/Array.html#method-i-sum

answered Aug 11 '18 at 20:46

Nate

2,364
1
10
16

Nondv · Accepted Answer · 2018-08-12T07:34:39.960

As @pjs said, your question looks quite ambigious.

If you want to get a sum of array just use: array.reduce(0.0, &:+) or even array.sum.

If you want to get an array that will sum into given N then you didnt give us sufficient details. What are limits? Can't you just do something like 4.5 -> [1, 1, 1, 1, 0.5] ?

upd

Author gave us a details. We have the array [5.0, 1.5, 0.5, 2, 1] and by given number N we should find a sum consisted of numbers from this array that equals N. Basically it is like vending machine change problem (what coins should it give to customer).

You can google it just like that "vending machine change algorithm". For example: Java Algorithm to solve vendor machine 'change giving' problem

Here's my simple dynamic programming solution:

ALLOWED_NUMBERS = [5.0, 1.5, 0.5, 2, 1].sort.freeze

def into_sum_of_allowed_numbers(n)
  return [] if n == 0
  @cache ||= {}
  return @cache[n] if @cache[n]

  ALLOWED_NUMBERS.reverse_each do |x|
    next if n - x < 0
    lesser_sum = into_sum_of_allowed_numbers(n - x)
    next unless lesser_sum
    @cache[n] = lesser_sum + [x]
    return @cache[n]
  end
  nil
end

into_sum_of_allowed_numbers(4.5) # ==> [0.5, 2, 2]

Basically, the idea is simple. With allowed numbers a, b, c sum for number n is [*sum_for(n - a), a] or [*sum_for(n - c), c] or [*sum_for(n - c), c].

You can do this without @cache though it will be much slower.

I guess there're better solutions but recursive one looks most simple to me.

I've a amount of values that represents a full payment, in this case, the full amount is equal to 10. My array holds "pieces" of this payment `[5.0, 1.5, 0.5, 2, 1]` into installments of the total amount. So, if someone pays me 3.5, I know in my array should return `2` and `1.5` values — gbs0, Aug 12 '18 at 00:47
@gbs0 ah, so, basically, you have a problem close to vending machine change problem — Nondv, Aug 12 '18 at 06:10
Thanks a lot for the answer!! Gives me a light for keep going! — gbs0, Aug 12 '18 at 13:44

Ruby - "Vending Machine" returning Change

2 Answers2

upd