Bag it up 💰 Greedy Algorithms in Javascript
Tags: javascript, node, webdev, discuss
Published: 2018-09-17 16:10:25

---
title: Bag it up 💰 Greedy Algorithms in Javascript
published: true
tags: javascript,node,webdev,discuss
canonical_url: http://www.albertywu.com/2018/09/13/greedy/
---

* * *

#### Overview

One less understood idea among javascript engineers (unless you happen to be studying up for interviews) is the use of greedy algorithms. A [greedy algorithm](https://en.wikipedia.org/wiki/Greedy_algorithm) makes whatever choice seems best at the moment, and solves the subproblems that arise later. To use a visual metaphor, we put the result of each subproblem in a “bag” and then repeat with successively smaller subproblems. When the subproblem is empty (nothing left to do), we return the contents of the bag.

As it turns out, this strategy can lead to some very elegant solutions to practical problems. In the rest of this article, we’ll explore four seemingly different problems that have almost identical solutions (hint: they all use a greedy algorithm). In closing, we’ll take a closer look at the structure common to all four problems. Let’s dive in!

* * *

#### Example: coin change problem

```
You are given coins of different denominations and a total amount of 
money. Write a function that returns the smallest set of coins that 
sums to that amount.
```

Take a moment to consider how you’d do this before continuing… (answer is right below)

* * *

```javascript
function makeChange(amount, coins, bag = []) {
  if (amount === 0) return bag
  let largestCoin = getLargestCoin(amount, coins)
  return makeChange(amount - largestCoin, coins, bag.concat([largestCoin]))
}

function getLargestCoin(amount, coins) {
  let sortedCoins = coins.sort((a, b) =\> a - b)
  for (let i = sortedCoins.length - 1; i \>= 0; i--) {
    if (sortedCoins[i] \<= amount) return sortedCoins[i]
  }
  throw new Error('no coin that divides amount')
}

console.log(
  makeChange(42, [1, 5, 10, 25])
)
// [25, 10, 5, 1, 1]
```

We keep a “bag” of coins and recursively add coins to the bag that matches our selection criteria `(pick largest coin denomination that is < amount)`. If the largest coin has value `C`, we add `C` to the bag and call `makeChange` with `amount - C`. This continues until the `amount` is 0, and the bag of coins is returned.

A quick note on the expression `{ ...bag, ...{ [fn(array[0])]: matches } }` since there’s a lot going on there. First of all, what does `{ ...a, ...b }` mean? This is called [object spreading](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_syntax#Spread_in_object_literals). Think of it as smooshing together objects a and b to create a new object. So `{ ...bag, ...somethingElse }` will combine the object `bag` with object `somethingElse`. In this case, `somethingElse` is the object `{ [fn(array[0])]: matches }` which is the new group we’re inserting into the bag.

I’ll also explain the difference between `{ [key]: value }` and `{ key: value }`. Those square braces signify [computed properties](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Object_initializer#Computed_property_names). You can stick any expression between the square braces, and the value of that expression will become the value of the key. So for example `{ [1 + 1]: 2}` would be the same as `{ 2: 2 }`.

* * *

#### Example: groupBy

```
Implement the "groupBy" function which takes an array A and a function F,
and returns an object composed of keys generated from the results of 
running each element of A through F. The corresponding value of each key 
is an array of elements responsible for generating the key.
```

Take a moment to consider how you’d do this before continuing… (answer is right below)

* * *

```javascript
/*
  input: [6.1, 4.2, 6.3]
  function: Math.floor
  output: { '4': [4.2], '6': [6.1, 6.3] }
*/

function groupBy(array, fn, bag = {}) {
  if (array.length === 0) return bag
  let matches = array.filter(x =\> fn(x) === fn(array[0]))
  let rest = array.filter(x =\> fn(x) !== fn(array[0]))
  return (
    groupBy(
    rest,
    fn,
    { ...bag, ...{ [fn(array[0])]: matches } }
    )
  )
}

console.log(
  groupBy([6.1, 4.2, 6.3], Math.floor)
)
// { '4': [4.2], '6': [6.1, 6.3] }
```

Keep a “bag” of groups and recursively add groups to the bag that match our selection criteria `fn(x) === fn(array[0])`. Then call `groupBy` on the remaining elements, with the updated bag. This continues until the original array is empty, and the bag is returned.

* * *

#### Example: activity selection problem

Another classic problem is the [activity selection problem](https://en.wikipedia.org/wiki/Activity_selection_problem).

```javascript
Imagine you are trying to schedule a room for multiple competing events, 
each having its own time requirements (start and end time). How do you 
schedule the room such that you can host the maximum number of events 
with no scheduling conflicts?
```

Take a moment to consider how you’d do this before continuing… (answer is right below)

* * *

```javascript
class Appointment {
  constructor(name, from, to) {
    this.name = name
    this.from = from
    this.to = to
  }
}

// push new appointments onto bag one-by-one until no more appointments are left
function getMaxAppointments(appointments, bag = []) {
  if (appointments.length === 0) return bag
  let selectedAppointment = appointments.sort((a, b) =\> a.to - b.to)[0] // sort from earliest end to latest end
  let futureCandidates = appointments.filter(a =\> a.from \> selectedAppointment.to)
  return getMaxAppointments(
    futureCandidates,
    bag.concat([selectedAppointment])
  )
}

let a1 = new Appointment('brush teeth', 0, 2)
let a2 = new Appointment('wash face', 1, 3)
let a3 = new Appointment('make coffee', 3, 5)
let a4 = new Appointment('blowdry hair', 3, 4)
let a5 = new Appointment('take shower', 4.5, 6)
let a6 = new Appointment('eat cereal', 7, 10)

console.log(
  getMaxAppointments([a1, a2, a3, a4, a5, a6]).map(a =\> a.name)
) 
// ['brush teeth', 'blowdry hair', 'take shower', 'eat cereal']
```

* * *

#### Example: collect anagrams

For our final example, we’ll consider the problem of [grouping anagrams](https://leetcode.com/problems/group-anagrams/description/).

```
Given an array of strings, group anagrams together.

For example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
```

Take a moment to consider how you’d do this before continuing… (answer is right below)

* * *

```javascript
function collectAnagrams(words, bag = []) {
  if (words.length === 0) return bag
  let matches = words.filter(w =\> isAnagram(w, words[0]))
  let rest = words.filter(w =\> !isAnagram(w, words[0]))
  return collectAnagrams(
    rest,
    bag.concat([matches])
  )
}

function stringSorter(a, b) { return a.localeCompare(b) }

function isAnagram(a, b) {
  let aSorted = a.toLowerCase().split('').sort(stringSorter).join('')
  let bSorted = b.toLowerCase().split('').sort(stringSorter).join('')
  return aSorted === bSorted
}

let x = ['bag', 'gab', 'foo', 'abg', 'oof', 'bum']
console.log(collectAnagrams(x))
// [['bag', 'gab', 'abg'], ['foo', 'oof'], ['bum']]
```

* * *

#### The Common Structure

So what do all of these problems have in common? For every iteration through the loop, we select a subset of items from the input and add it to the bag. The remaining items feed through to the next iteration of the loop as the next input. When the input is empty, we return the bag.

The following diagram might help clarify things, using our groupBy example:

![visualization](https://user-images.githubusercontent.com/1920766/45563508-693f4680-b802-11e8-9891-1879d832b4ff.jpg)

If you’re more comfortable with pseudocode, here is the pattern we used in all of the previous examples:

```javascript    
function bagItUp(things, bag = []) {
  if (things is empty) return bag
  let thingsToPutInBag = ...
  let restOfThings = ...
  return bagItUp(
    restOfThings,
    bag + thingsToPutInBag
  ) 
}
```

#### Connect

What do you think? Have you solved similar problems at work or personal projects using greedy algorithms? Let me know in the comments below, or on [twitter](https://twitter.com/albertywu)!