Inventory Management System

Advent of Code 2018 Day 2

Task: Solve for X where...

Part 1

X = the checksum for my list of box IDs

Part 2

X = the letters that are common between the two correct box IDs

Example input

abcdef
bababc
abbcde
abcccd
aabcdd
abcdee
ababab

It represents:

• A list of box IDs

Part 1

1. The job to be done
2. Solving one way: summing each letter count
3. Trying to solve another way: regular expressions

The job to be done

I must separately identify the IDs that have:

• exactly two of any letter
• exactly three of any letter

Caveats:

• One ID may fulfill both categories. If it does, count it once in both.
• An ID may fulfill one category multiple times. If it does, count it once for that category.

Solving one way: summing each letter count

Create a 2-element tracker array to store the number of two- and three-letter IDs
  Initialize both values to 0
Create a dictionary to sum up each letter count

For each ID
  For each letter
    If the letter is not a key in the dictionary, make it one and initialize it to 1
    Increment the letter's associated integer value by 1

  Generate a list of the values from the dictionary
    If there are any 2s, increment the first element in the tracker array
    If there are any 3s, increment the second element in the tracker array

Return the product of both elements in the tracker array

What that algorithm looks like for a single ID:

The JavaScript I wrote to generate a correct answer:

input.split('\n')
  .reduce((a,c) => {
    let tallies = Object.values(c.split('').reduce((a,c) => {
      (!(c in a)) ? a[c] = 1 : a[c] += 1
      return a
    }, {}))
    a[0] += tallies.includes(2) ? 1 : 0
    a[1] += tallies.includes(3) ? 1 : 0
    return a
  }, [0,0])
  .reduce((a,c) => a * c)

• A few split()s
• Three reduce()s
• Three ternaries
• And two includes()

I'm proud of how concise it is.

However, I sense there is a more performant way to solve this part of the puzzle.

Trying to solve another way: regular expressions

For each box ID string
  Match exactly two of any letter
  Match exactly three of any letter

This feels perfectly suited for a regular expression.

Could I write one that works?

To match exactly two of any letter

• I'll start by matching some letter
• There could be 0 or more letters between that matched letter and the next instance of it
• I must then match a second instance of the same letter
• I must then ensure that there are no further instances of that same letter

Pseudocode for the regular expression might be:

/ (LETTER), other letters?, LETTER, no more LETTERs/g

The first three parts come easy for me:

/(\w)\w*\1/g

• Match any letter
• Match 0 or more letters
• Match the same letter

The trouble comes when attempting to match the non-existence of any more instances of the initially matched letter.

• Can I use a set to negate the backreference? [^\1]
• Can I use a negative lookahead? (?!\1)

After some Googling, I found what seemed like a solution in a commenter's answer on Stack Overflow:

((?!\1).)*

I incorporated it into my regular expression:

/(\w)\w*\1((?!\1).)*/g

But noticed it didn't generate the results I hoped.

I'm still stumped as to how I could solve Part 1 using a regular expression.

I feel like it's possible.

But I'm done exploring.

Part 2

1. Solving one way: compare all the strings

Solving one way: compare all the strings

What I must find:

IDs which differ by exactly one character at the same position in both strings

My proposed algorithm:

Set the matching box ID as null
For each box ID string except the last
  Do until all other strings have been compared, or a match was found
    Set the tally of different characters as 0
    Set the character as null
    Do until two characters are different
      Compare the current character in the current string with the current character in the next string
        If they are different
          Increment the tally
          Set the current character as the new different character
    Set the matching box ID as the current box ID string with the single differing character replaced with an empty string
    Escape the loops

Return the matching box ID with the differing character removed

An animation showing how it works:

I intended to use while loops in my algorithm.

My goal was to boost performance at a micro level by breaking each while loop as soon as two characters were different.

I wound up writing for loops with conditions toward the end that had a single break statement...checking whether a match was found.

So, no big performance gains.

But the algorithm still runs near-instantly and generates the correct answer!

I did it!!

• I solved both parts!
• I made a few GIFs that demonstrate how my algorithms work!
• I'm proud of how I solved Part 1

Bummers:

• I'm disappointed I couldn't solve Part 1 with a regular expression
• I am not happy with how I solved Part 2: all of the loops and comparisons that likely weren't necessary

I need to solve at least Part 1 of Day 1 to match my personal low score of 34.

I'm confident I can do that, as I haven't had trouble solving any Day 1s thus far.

Let's go!