An even simpler javascript tokenizer

Albert Wu — Sun, 16 Sep 2018 02:51:30 +0000

What’s the easiest way you know of to tokenize an arithmetic expression in javascript? Let’s say you’re building a calculator application, and want this to happen:

console.log(
 tokenize('100-(5.4 + 2/3)*5')
)
// ['100', '-', '(', '5.4', '+', '2/3', ')', '*', '5']

Before you reach into your npm module bag-o-tricks, realize that this can be done in one line of javascript using a secret feature of the string split method. Behold:

'100-(5.4+2/3)*5'
  .split(/(-|\+|\/|\*|\(|\))/)
  .map(s => s.trim())
  .filter(s => s !== '')
// ['100', '-', '(', '5.4', '+', '2/3', ')', '*', '5']

Excuse me? What’s that hot mess inside the split function? Let’s break it down step by step using a few examples of increasing complexity:

Example 1: `s.split(/-/)`

Pretty obvious: this splits the string s anywhere it sees the minus sign symbol -.

'3-2-1'.split(/-/)
// ["3", "2", "1"]

Example 2: `s.split(/(-)/)`

The only difference from the previous example is the enclosing parens in the regex, which creates a capturing group. Here’s the key point of the entire article: If the regular expression contains capturing parentheses around the separator, then each time the separator is matched, the results of the capturing group are spliced into the output array.

'3-2-1'.split(/(-)/)
// ["3", "-", "2", "-", "1"]

Example 3: `s.split(/(-|\+)/)`

This builds off the previous example by adding support for the addition symbol \+. The backslash \ is required to escape the regex. The vertical pipe | acts as an OR statement (match - OR +).

'3-2-1+2+3'.split(/(-|\+)/)
// ["3", "-", "2", "-", "1", "+", "2", "+", "3"]

The Final Boss (tying everything together)

Hopefully, you now have all tools needed to understand .split(/(-|\+|\/|\*|\(|\))/). Hope that made sense! Let me know in the comments if you liked this article, or ping me on twitter!

Bag it up 💰 Greedy Algorithms in Javascript

Albert Wu — Thu, 13 Sep 2018 20:43:10 +0000

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 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)

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. 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. 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)

/*
  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.

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)

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.

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)

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:

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

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!

DEV Community: Albert Wu

An even simpler javascript tokenizer

Example 1: s.split(/-/)

Example 2: s.split(/(-)/)

Example 3: s.split(/(-|\+)/)

The Final Boss (tying everything together)

Bag it up 💰 Greedy Algorithms in Javascript

Overview

Example: coin change problem

Example: groupBy

Example: activity selection problem

Example: collect anagrams

The Common Structure

Connect

Example 1: `s.split(/-/)`

Example 2: `s.split(/(-)/)`

Example 3: `s.split(/(-|\+)/)`