It's common for people to turn to functions like map, filter, and reduce when working with data, but sometimes the outcome doesn't quite fit the problem at hand.
map might not be suitable because it always produces a one-to-one result; if you have 4 types of coins, you will always get 4 types of change, which may not be what you need. Using filter often requires additional processing to achieve the desired output.reduce can help eliminate intermediate values from combinations of map and filter, but there are cases where the desired result is reached even before analyzing every coin in the list. For example, consider the function fn(100) returning [ [25, 4] ]; further reduction would be unnecessary since the result has already been obtained.
To me, functional programming is all about convenience. If I don't have a function that fits my needs, I create one myself, ensuring that my code clearly expresses its purpose. Sometimes this involves using constructs more suited to the data being processed -
const change = (coins = [], amount = 0) =>
loop
( ( acc = []
, r = amount
, [ c, ...rest ] = coins
) =>
r === 0
? acc
: c <= r
? recur
( [ ...acc, [ c, div (r, c) ] ]
, mod (r, c)
, rest
)
: recur
( acc
, r
, rest
)
)
Unlike traditional methods such as map, filter, and reduce, our solution won't continue iterations once the result is determined. Here's how you can use it -
const coins =
[ 25, 20, 10, 5, 1 ]
console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]
console.log (change (coins, 100))
// [ [ 25, 4 ] ]
You can check the results in your browser below -
const div = (x, y) =>
Math .round (x / y)
const mod = (x, y) =>
x % y
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let acc = f ()
while (acc && acc.recur === recur)
acc = f (...acc.values)
return acc
}
const change = (coins = [], amount = 0) =>
loop
( ( acc = []
, r = amount
, [ c, ...rest ] = coins
) =>
r === 0
? acc
: c <= r
? recur
( [ ...acc, [ c, div (r, c) ] ]
, mod (r, c)
, rest
)
: recur
( acc
, r
, rest
)
)
const coins =
[ 25, 20, 10, 5, 1 ]
console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]
console.log (change (coins, 100))
// [ [ 25, 4 ] ]
Ramda users may opt for R.until, yet readability takes a hit due to its purely functional nature. Personally, I find the flexibility of loop and recur more appealing -
const change = (coins = [], amount = 0) =>
R.until
( ([ acc, r, coins ]) => r === 0
, ([ acc, r, [ c, ...rest ] ]) =>
c <= r
? [ [ ...acc
, [ c, Math.floor (R.divide (r, c)) ]
]
, R.modulo (r, c)
, rest
]
: [ acc
, r
, rest
]
, [ [], amount, coins ]
)
[ 0 ]
Another approach is to implement it as a recursive function -
const div = (x, y) =>
Math .round (x / y)
const mod = (x, y) =>
x % y
const change = ([ c, ...rest ], amount = 0) =>
amount === 0
? []
: c <= amount
? [ [ c, div (amount, c) ]
, ...change (rest, mod (amount, c))
]
: change (rest, amount)
const coins =
[ 25, 20, 10, 5, 1 ]
console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]
console.log (change (coins, 100))
// [ [ 25, 4 ] ]