Debugging basic ruby recursion

Question

This code aims to take an array of integer coin values, an amount of change to be made, and an empty array to pass around for collecting the answer, and should return a set of coins that makes the exact right amount of change (assumes that the problem is possible).

From the puts statement, it seems that the recursion seems to be behaving well and seeking the right answer, but the returned solution isn't a valid answer. Could someone let me know what I'm doing wrong?

My code:

    def brute_solver(coins,amount,answer)
        puts "Coins: #{coins}, Amount: #{amount}, Answer: #{answer}"
        return answer.sort! if amount == 0
        coins.each do |c|
            brute_solver(coins, amount - c, answer.dup << c) unless amount - c < 0
        end 
    end

Sample attempt at running brute_solver:

    1.9.3p194 :001 > require './change_challenge.rb'
     => true 
    1.9.3p194 :002 > brute_solver([1,3,5],7,[])
    Coins: [1, 3, 5], Amount: 7, Answer: []
    Coins: [1, 3, 5], Amount: 6, Answer: [1]
    Coins: [1, 3, 5], Amount: 5, Answer: [1, 1]
    Coins: [1, 3, 5], Amount: 4, Answer: [1, 1, 1]
    Coins: [1, 3, 5], Amount: 3, Answer: [1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [1, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 1, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 1, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 1, 1, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 1, 1, 3]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 1, 3, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [1, 1, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 1, 3, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 3, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 5]
    Coins: [1, 3, 5], Amount: 3, Answer: [1, 3]
    Coins: [1, 3, 5], Amount: 2, Answer: [1, 3, 1]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 3, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 3, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 3, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 5]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 5, 1]
    Coins: [1, 3, 5], Amount: 4, Answer: [3]
    Coins: [1, 3, 5], Amount: 3, Answer: [3, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [3, 1, 1]
    Coins: [1, 3, 5], Amount: 1, Answer: [3, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [3, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [3, 1, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [3, 3]
    Coins: [1, 3, 5], Amount: 0, Answer: [3, 3, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [5]
    Coins: [1, 3, 5], Amount: 1, Answer: [5, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [5, 1, 1]
     => [1, 3, 5]

each returns the array you asked it to iterate over. You're going to have to do something more to actually select the answer you're interested in. For instance, you might want to return whether any solutions exist. Or you might want to select the first solution found. Or you might want to select the "best" solution by some metric. You have to add logic to do one of these. — Jeremy Roman
Thankes @JeremyRoman, I didn't realize that each was returning; the output makes a lot more sense now. — Matthew Du Pont

Ionut Hulub Ionut Hulub · Accepted Answer · 2012-10-14T17:26:39

def brute_solver(coins,amount,answer)

        puts "Coins: #{coins}, Amount: #{amount}, Answer: #{answer}"

        return answer.sort! if amount == 0

        coins.each do |c|
            if amount - c < 0
                break
            end
            result = brute_solver(coins, amount - c, answer.dup << c)
            if result != -1
                return result
            end
        end 
        return -1

end

puts brute_solver([5, 7],26,[])

This way the function returns an array if it finds the correct solution, or -1 otherwise. When you make the recursive call you also return the solution the recursion finds (if the return value is not -1 it means it found a solution)

Your code does not work because the return value for a function in ruby is the last statement executed, and your functions keeps executing commands even after it had found a valid combination of coins. Basically, your function returns the last combination of coins that it had checked to see if they are a solution.

Debugging basic ruby recursion

1 Answers