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
- The job to be done
- Solving one way: summing each letter count
- 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
- 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!
Top comments (1)
Useful, thanks! Inventory Management System helps optimize inventory levels, streamline processes, and improve overall efficiency. BTW, if you're interested in improving your inventory management practices, Cleveroad has a helpful guide on yard management solutions. While the guide primarily focuses on yard management, it offers insights that can be applied to inventory management as well.