Solve a Smaller Problem First

Day Two focuses on finding patterns in strings.

The Problem

For the first puzzle, we're asked to take a set of strings of letters referred to as "ids" and identify ids that contain duplicate letters. More specifically, count

• how many ids have at least one letter that appears exactly twice, and
• how many ids have at least one letter that appears exactly three times.

For example,

• abcdef has no repeats. (I love explanations that start at that level.)
• abcabc has letters that appear exactly twice. It doesn't matter how many letters appear exactly twice, just that at least one does.
• abcccf has a letter that appears exactly three times - only one, but that's enough to count.
• aabbbc has a letter that appears twice and a letter that appears three times, so this string counts for both categories.

If that was the whole set of ids, the final count would be two "appears exactly twice"s and two "appears exactly three times"s, and we wouldn't need software to deal with it. Fortunately, there are 250 ids, so I can get a blog post out of this.

Since the input data was once again made available as a text file, I was able to reuse some code from yesterday:

const fs = require('fs')
const input = fs.readFileSync(`./input/day2.txt`, 'utf8').trim()
const ids = input.split('\n')

That gets me to a good place on the input side - ids is an array of strings, and I know there are lots of things I can do with a data structure like that. Next I'll take a minute to think about what I want to end up with.

Dealing with Data

A few paragraphs ago I wrote about keeping count for strings with letters that appeared twice, and for strings with letters that appeared three times. That's two independent pieces of data, so I'll need some kind of container. The most fundamental in JavaScript are objects and arrays. Either of those would work here - there will only ever be two pieces of information, so the speed of access that was a concern yesterday doesn't matter in this problem. Even so, if there's not a good reason to choose an array, I prefer to use an object, because objects let me label the data I'm storing. That's the reasoning that led me to this data structure:

let counts = {
  countOfIdsWithDoubles: 0,
  countOfIdsWithTriples: 0,
}

I'm not super happy with the keys in that object; the length makes them a bit tough to read. On the bright side, I nailed the values - the initial counts are zero. Go, me.

Array => Object

OK, now I know where I'm starting (ids, the array of strings) and where I want to end up (counts, an object), so I just need to put in the middle bits. I can get from an array to an object with .reduce(); that method showed up yesterday, as a way to add together all the numbers in an array called sequence:

const sum = sequence.reduce((total, current) => total + current, 0)

There are a few differences between how .reduce() was used for sum and how I need to use .reduce() for this problem. For one thing, I need to keep track of two numbers, not just one, so the initial value will have to be different. For another, I'm not just adding two numbers together to get the return value from the callback function. I'm keeping track of two numbers, and depending on what letters repeat in each id, I might change oe of those numbers or both - or neither. I'll need some kind of conditional logic to decide when to change each of the numbers I'm tracking.

I already have my initial value - it's the counts object. The bigger problem is to figure out what to do with that object in the callback function. The basic outline I have in mind is this:

const result = ids.reduce((total, id) => {
  const hasDouble = // figure out if any letter appears twice in `id`
  if (hasDouble) {
    // increase the count of ids with repeat letters
  }
  const hasTriple = // figure out if any letter appears three times in `id`
  if (hasTriple) {
    // increase the count of ids with letters that appear 3x
  }
  return // an object to use for the next `total`
}, counts)

This use of .reduce() looks a lot different than the use of .reduce() to calculate a sum. That's because the callback function here spreads over several lines, from the first { to the last }. Still, I'm using .reduce() with two arguments, a callback function and an initial value (counts).

Simpler First, Part One

I don't know yet how I'm going to calculate hasDouble or hasTriple, but I do know what to do with my counts object when either of those conditions is met. Since I'm using counts as the initial value, it gets inside the callback function under the name total. I can get each count out of the object with destructuring:

const result = ids.reduce((total, id) => {
  let {
    countOfIdsWithDoubles,
    countOfIdsWithTriples
  } = total
  ...

Then I can increment them as appropriate:

const hasDouble = // TODO
if (hasDouble) {
  countOfIdsWithDoubles += 1
}
const hasTriple = // TODO
if (hasTriple) {
  countOfIdsWithTriples += 1
}

Once I have decided whether or not each of those variables should be incremented, I can recombine them into an object to return as the new value of total:

const result = ids.reduce((total, id) => {
  let {
    countOfIdsWithDoubles,
    countOfIdsWithTriples
  } = total
  const hasDouble = // TODO
  if (hasDouble) {
    countOfIdsWithDoubles += 1
  }
  const hasTriple = // TODO
  if (hasTriple) {
    countOfIdsWithTriples += 1
  }
  return {
    countOfIdsWithDoubles,
    countOfIdsWithTriples
  }
}, count)

Even though there are parts I skipped over at first, I managed to write several steps of my solution. Whether my next step is to ask someone for help, or set the problem aside for a while, or even continue on, it's very useful to be able to see how the logic of the overall solution works and how the missing pieces fit in. Now all that's left is calculating what hasDouble and hasTriple are.

Simpler First, Part Two

Figuring out if any letter in an id repeats is a bit hard, so I don't want to do it. ¹ I think I can sneak up on the problem by solving a related but simpler problem, like...does the first letter in the id repeat?

Well, how can I figure that out?

String => Boolean (eventually)

I have an id, which is a string. I want to get an answer to "does it repeat", which will be a boolean (true or false). Hmmm. Before I get to the boolean, I could try to find an answer to "how many times does this letter appear". The answer to that question will be a number. (I can get to the boolean from there by asking whether the number equals two.) Starting with my string, id, I want to get to a number. I don't know exactly how to do that. I do know how to turn an array into a number. I mean, I've done it before. And I can get an array out of my string:

String => Array

const letters = id.split('')

Then I can get the first letter easily enough

const firstLetter = letters[0]

I can use it to turn the array into a number, by going through all the letters, and keeping count of how many times I see firstLetter. To be excruciatingly specific, I'll start my total at zero, look at every letter in letters one at a time, and if I see a letter that's the same as firstLetter, I'll add one to the total. Otherwise, I'll leave the total where it was.

Array => Number

const count = letters.reduce(
  (current, total) => (current === firstLetter ? total + 1 : total),
  0
)

Getting from the number to a boolean is easier:

Number => Boolean

const firstLetterAppearsTwice = count === 2

Putting that all together,

const letters = id.split('')
const firstLetter = letters[0]
const count = letters.reduce(
  (current, total) => (current === firstLetter ? total + 1 : total),
  0
)
const firstLetterAppearsTwice = count === 2

And that solves the problem! Or at least, it solves what I called the simpler problem of finding if the first letter repeats.

The Harder Problem's Simpler Once the Simpler Problem's Solved

I still have the problem of finding if any letter repeats. That means I have to take the logic I used to turn letters[0] into a boolean, and apply it to every letter in letters. Then, if any letter ends up with a boolean of true, I can say that some letter repeats. I can do that with the array method called some, which looks like this:

const letters = id.split('')
const hasDouble = letters.some(letter => {
  const count = letters.reduce(
    (current, total) => (current === letter ? total + 1 : total),
    0
  )
  return count === 2
})

Checking if a letter appears three times is almost exactly the same:

const hasTriple = letters.some(letter => {
  const count = letters.reduce(
    (current, total) => (current === letter ? total + 1 : total),
    0
  )
  return count === 3
})

Let's see how to use those in the callback for .reduce(), in the place that was marked //TODO:

const result = ids.reduce((total, id) => {
  let { countOfIdsWithDoubles, countOfIdsWithTriples } = total
  const letters = id.split('')
  const hasDouble = letters.some(letter => {
    const count = letters.reduce(
      (current, total) => (current === letter ? total + 1 : total),
      0
    )
    return count === 2
  })
  if (hasDouble) {
    countOfIdsWithDoubles += 1
  }
  const hasTriple = letters.some(letter => {
    const count = letters.reduce(
      (current, total) => (current === letter ? total + 1 : total),
      0
    )
    return count === 3
  })
  if (hasTriple) {
    countOfIdsWithTriples += 1
  }
  return {
    countOfIdsWithDoubles,
    countOfIdsWithTriples,
  }
}, counts)

That works! Now I can tidy up a bit.

A Bit of Refactoring

There's a lot of duplication between hasDouble and hasTriple; they're identical except for the number. I can pull that out into a function:

const appearNTimes = n =>
  letters.some(
    const count = letters.reduce(
      (current, total) => (current === letter ? total + 1 : total),
      0
    )
    return count === n
  )

That's a function that takes a single argument, n, and returns all of the code that hasDouble and hasTriple had in common. I can use the function to create those expressions:

const hasDouble = appearNTimes(2)
const hasTriple = appearNTimes(3)

That slims things down:

const result = ids.reduce((total, id) => {
  let { countOfIdsWithDoubles, countOfIdsWithTriples } = total
  const letters = id.split('')
  const appearNTimes = n =>
    letters.some(letter => {
      const count = letters.reduce(
        (current, total) => (current === letter ? total + 1 : total),
        0
      )
      return count === n
    })
  const hasDouble = appearNTimes(2)
  if (hasDouble) {
    countOfIdsWithDoubles += 1
  }
  const hasTriple = appearNTimes(3)
  if (hasTriple) {
    countOfIdsWithTriples += 1
  }
  return {
    countOfIdsWithDoubles,
    countOfIdsWithTriples,
  }
}, counts)

This could be refactored some more, but I tend to obsess over that kind of thing, and I haven't started on the day's second puzzle.

² And he ended the blog forever.