Loops I Did It Again

The second puzzle is shorter to describe, both for the problem and the solution.

The Problem

The problem is to find two ids that are identical except for one letter, and then print out the letters those two ids have in common.

Just Loop It

I couldn't see an elegant way to do this. Because I need to compare pairs of ids, I need to have two nested iterations, one inside the other (a for loop inside another for loop or a .forEach() inside another .forEach()). I don't want to compare every pair, though; when I find the two ids I want, I can stop. That's easier to do from inside a for loop than from inside a call to .forEach(). I also don't want to compare any pair twice; once I compare the first to the second, I don't need to compare the second to the first. I have to make sure the second, inner for loop doesn't look at any elements that have already been looked at in the outer for loop. To do that, I can have the inner loop's index start at the next number after whatever the outer loop's index's value is:

for (let outerIndex = 0; outerIndex < ids.length; outerIndex += 1) {
  for (
    let innerIndex = outerIndex + 1;
    innerIndex < ids.length;
    innerIndex += 1
  ) {
    // compare one id to another
  }
}

The point of having those indexes is to identify two id values I want to compare:

for (let outerIndex = 0; outerIndex < ids.length; outerIndex += 1) {
  for (
    let innerIndex = outerIndex + 1;
    innerIndex < ids.length;
    innerIndex += 1
  ) {
    const [first, second] = [ids[outerIndex], ids[innerIndex]]
    // compare first to second
  }
}

Now I want to compare the letters in first and second. Since I want to compare the letters at the same position in both ids, I need one more for loop:

for (let outerIndex = 0; outerIndex < ids.length; outerIndex += 1) {
  for (
    let innerIndex = outerIndex + 1;
    innerIndex < ids.length;
    innerIndex += 1
  ) {
    const [first, second] = [ids[outerIndex], ids[innerIndex]]
    for (let sharedIndex = 0; sharedIndex < first.length; sharedIndex += 1) {
      // compare a letter in first to the letter at the same index in second
    }
  }
}

I'm interested in finding the two id values that are different at only one position. That means (a) I need to keep track of how many positions are different, and (b) once a pair is different at two positions, I can go on to the next pair. I can take care of (b) by adding to the innermost for loop's condition:

for (let outerIndex = 0; outerIndex < ids.length; outerIndex += 1) {
  for (
    let innerIndex = outerIndex + 1;
    innerIndex < ids.length;
    innerIndex += 1
  ) {
    const [first, second] = [ids[outerIndex], ids[innerIndex]]
    let differenceCount = 0
    for (
      let sharedIndex = 0;
      sharedIndex < first.length && differenceCount < 2;
      sharedIndex += 1
    ) {
      if (first[sharedIndex] !== second[sharedIndex]) {
        differenceCount += 1
      }
    }
  }
}

Now the innermost for loop will continue only as long as sharedIndex < first.length AND differenceCount < 2. OK, we're comparing each pair of ids in the ids array, and counting how many letters are different in each pair. If the pair is different in more than one position, we bail out of the comparison and move on. What if we make it all the way to the end of one pair of ids and they're different in only one position? We should break out of the loop. A break statement by itself isn't enough, because that will only break out of the inner loop. Something I learned while solving this is that you can give a block a label, which looks like an object key. Then break can be given the label of the block to break out of. Here's what that looks like, with the label outerLoop added to...the outer loop:

outerLoop: for (let outerIndex = 0; outerIndex < ids.length; outerIndex += 1) {
  for (
    let innerIndex = outerIndex + 1;
    innerIndex < ids.length;
    innerIndex += 1
  ) {
    const [first, second] = [ids[outerIndex], ids[innerIndex]]
    let differenceCount = 0
    for (
      let sharedIndex = 0;
      sharedIndex < first.length && differenceCount < 2;
      sharedIndex += 1
    ) {
      if (first[sharedIndex] !== second[sharedIndex]) {
        differenceCount += 1
      }
    }
    if (differenceCount === 1) {
      console.log('found them!', first, second)
      break outerLoop
    }
  }
}

Getting close! In a pinch, you could look closely at that console output and type out one of the ids without the letter that's different between the two. That's actually how I submitted my solution to Advent of Code. To be thorough, here are the last steps to get the whole problem solved by software. We'll need to identify the position at which the two ids are different, then log out one of the ids with that position removed:

    let differenceCount = 0
    let position
    for (let sharedIndex = 0; sharedIndex < first.length && differenceCount < 2; sharedIndex += 1) {
      if (first[sharedIndex] !== second[sharedIndex]) {
        differenceCount += 1
        position = sharedIndex
      }
    }
    if (differenceCount === 1) {
      console.log(first.slice(0, position - 1) + first.slice(position + 1))
      break outerLoop
    }

Tada!

BTW to be completely thorough, I should mention that with the fairly small amount of data involved in this problem, none of the optimizations I added matter. Running the code as above takes ~20ms. Changing innerIndex to start at 0 instead of outerIndex + 1, changing the sharedIndex conditional to not look at differenceCount, and removing the break statement slows it down to...~60ms.