# Coin Change Kata in ImmutableJS

I'm preparing for a job as a junior/intermediate JS developer. I'm comfortable with my ability to think in higher-order functions, but less confident in my syntax and style (I have more experience in Clojure, ClojureScript). This is simple but I welcome your comments.

import { Map } from 'immutable';

const coinChanger = (d, m) => { // d for denominations, m for money
const denoms = d.sort((a,b) => b-a)
const coinCounter = (coin, amount) => {
const coins = Math.floor(amount / coin);
const remainder = amount % coin;
return Map({}).set(coin, coins).set("remainder", remainder);
};
const coinMap = denoms.reduce((result, coin) => {
const amount = result.get("remainder");
const coinCount = coinCounter(coin, amount);
return result.merge(coinCount);
}, Map({"remainder": m}));
return coinMap;
};

console.log(coinChanger([1, 5], 11));
console.log(coinChanger( [25, 10, 5, 1], 192 ));
console.log(coinChanger([25, 2], 105));

• Watch out for comments like that // d for denominations, m for money this means you actually have to rename d with denominations and m with money and get rid of the comment to make the code more readable – Fanis Despoudis Feb 21 '17 at 22:46
• @FanisDespoudis Please write all critiques, even simple ones, as answers, not comments. – 200_success Feb 21 '17 at 23:40

It looks like a nice implementation, but I don't think that using immutable.js is terribly necessary. JS already has a Map, which, while not immutable, could work too. However, a plain object might also be enough.

The slightly ironic bit is that despite choosing to use immutable data structures, your function actually has side-effects: sort modifies the receiver in-place, meaning that the d argument is mutated as a side-effect.

Inside the function itself, i.e. for local variables, I'd be less concerned about mutability. So for instance, a vanilla-JS solution using a plain object (since Map's API of get/set gets tiresome in a hurry) could be:

const coinChanger = (denominations, amount) => {
return denominations
.slice() // copy array before sorting
.sort((a, b) => b - a)
.reduce((result, value) => {
result.coins[value] = (result.remainder / value) | 0; // bitwise trick to floor the result
result.remainder %= value;
return result;
}, { remainder: amount, coins: {} });
};


Edit/sidenote: The | 0 trick, while neat, does have some very notable limitations. See the comments for a discussion (thanks, Thriggle!). Essentially, all numbers in JS are 64-bit floats, but behind the scenes, bitwise operations are performed on 32-bit ints. So the trick causes an unsafe cast to int, performs a pointless OR'ing with zero, and casts the result back to a float. So again: It's a trick. Here, given a large enough amount value, you will get weird results. So use with caution.

I've simplified it somewhat (removed the coinCounter function), and yes, the memo object for reduce is mutated. The effects are however contained within the reduce call, so... eh. The coin denominations are also coerced to strings when used as keys in the object, which a proper Map wouldn't do, but the coercion works both ways, so the keys can transparently be used as numbers later.

Of course, once the object is returned, only the caller holds a reference, and then it's the caller's responsibility – so that's where an immutable data structure might be better. But for the purposes of a quick alternative implementation, I'll leave things as-is.

Style-wise, your code looks fine. You're missing a semi-colon after sort (JS mostly works without semi-colons, but it looks like you're using them elsewhere, so stay consistent), and you could do with a little more whitespace here and there, but otherwise it's pretty good.

The only thing to wag a finger at, which Fanis Despoudis pointed out in a comment, is that d and m should be spelt out, rather than be explained in a comment. Especially because they're arguments, and they form the interface of the function, they should be readable. In general, all names should of course be clear and descriptive, but parameter and function names should be especially easy to parse, as that's what others will see first and make use of.

• @FanisDespoudis Thanks! I hope you don't mind me using your observations in my answer – Flambino Feb 22 '17 at 17:30
• "The slightly ironic bit is that despite choosing to use immutable.js, your function actually has side-effects: sort modifies the receiver in-place, meaning that the d argument is mutated as a side-effect." Ah-ha! This is exactly the kind of thing I needed to read, because I've written enough code with immutable structures that I forget that sending a message to an object has an effect in what I think of as "the past." Thank you for taking the time. – tom Feb 22 '17 at 22:37
• As far as bitwise tricks go, at the price of two extra characters, unsigned bitwise right shifting (x >>> 0) can accommodate somewhat larger numbers before JavaScript explodes. 4000000000.25 >>> 0 returns 4,000,000,000 while 4000000000.25 | 0 returns -294,967,296. ...Of course, at that scale you're probably better off with the slower but sturdier Math.floor since even >>> breaks before you reach 5 billion. – Thriggle Feb 23 '17 at 22:05
• @Thriggle True, it's not a safe thing to do. When in doubt about a value's range, I do stick to Math.floor for exactly such reasons. Admittedly, this could actually be one of those cases, since someone might want change for several billion... the input's not bounded by anything. I should probably add a note to the answer. – Flambino Feb 23 '17 at 22:22

Flambino's answer really hits the nail on the head. However, I'll still provide this solution just for a syntax comparison.

This solution differs in a few areas but the logic is almost identical. The main differences being:

• Taking advantage of more ES6 features
• Not modifying the result object
• Still using Math.floor. The bitwise trick is definitely worth mentioning in an interview but I prefer to be explicit and use code rather than comments where possible.

Solution:

const coinChanger = (denominations, amount) =>
[...denominations]
.sort((a, b) => b - a)
.reduce(({ coins, remainder }, value) => ({
coins: {
...coins,
[value]: Math.floor(remainder / value)
},

remainder: remainder % value
}), { remainder: amount, coins: {} })


Explanation:

[...denominations]: The spread operator (...) is used to make a copy of denominations

=> ({ ... }): Arrow function expression bodies allow the braces and return to be removed since the entire body is now just an expression. Note that the parentheses are required around the returned object.

{ coins, remainder }: Object destructing allows coins and remainder to be used instead of result.coins and result.remainder (which is used twice)

...coins: Also uses the spread operator, but this time it is used so that the newly reduced object's coin property has all of the previous coin properties. You can find some more examples here

[value]:: Computed property names allow you to assign inline without having to do result.coins[value] = ... etc.

• Very nice! And yeah, the bitwise-floor is a trick more than anything. Usually it's the sort of thing I'd avoid (like I avoid !~foo.indexOf(bar) sorcery in favor of a regular old strict comparison). But the floor trick is my weakness; I can't help but use it :P – Flambino Feb 23 '17 at 12:24