Day 1, part 2

Introduction

If you haven't already, please first take a look at Day 1, part 1 as this article is a continuation of the Advent of Code day 1 puzzle. This part of the challenge is available only when you successfully finished the part 1. The second part of the challenge is described under section here.

What is the new problem?

Now we are asked to look at the test data again.

Before we were looking for the first and last digit, taking into consideration only numeric characters (characters from 0 to 9), but the strings of text we are given are built also with numbers written as a words (, , etc.). Lets take a look at the word . If we feed our algorithm from part 1, we will get as a result (reading from the beginning and from the end results in finding both times), which in turn is the calibration value for this string as we only have one string so the final sum is built out of this one calibration value. But with the new information, the correct calibration value is as we first replace the words with digits getting and then we proceed with the steps we already know.

Solution

To be able to read the word written digits, we first have to find them and then replace them with the corresponding digit. We have to do it looking from the beginning of the given string as well as looking from the end. Also, as we know that we later look only for the first and last digit in the string, when replacing the words with numbers, we have to only replace the first word we met and the last word we met.

Lets start, again, by defining the variable for input data and set it to the test data for which we know the results and in general the amount of data is so small that we can easily keep track of it.

Let's figure out what the strings will look like if we replace the first and last spelled number with a digit:

Find first number word in the string

Now, how can we find out the first spelled number in a string? We can use string method to look for a word occurrence in the string. This method returns the index at which the word starts and if it hasn't found the word. We can do this operation for all the words from to , find the one with the lowest index and replace that word, leaving all the rest as is.

this piece of code returns array with indexes for each spelled number which looks like this:

Analyzing the results we can see that if found words with indexes and at positions and respectively. These of course are the words and . We store the spelled digits in an array like this for a simple reason: the index of each word corresponds to it digit what might be useful later. But now, how can we find the index of the word which appeared first? We can find the smallest number in the array using , but because of the values in the array, the answer is going to be wrong, so before we use the lets first filter out all the s. New version of our function looks now like this:

and it gives us following information:

Thanks to that information we know what digit is first both spelled and as a number and where it starts in the given string.

Replace word with a digit

The data we were able to gather so far is enough for us to be able to replace the written digit with the number. Here is the code after few modifications.

Now we introduced the general purpose function which can take an input string, start position, the amount of characters we want to replace and the replacement string, which in our case is just the digit as a number. Running this code gives us:

Find and replace the last word

So far so good, we successfully found and replaced the first spelled number with the corresponding digit. We can try to do the same for the last one by analogy.

and thanks to that we get the expected result which is . Lets now do it for all the test values and see the results. I will also use the expected values we did figured out manually to see if the results we get are the results we expect.

This unfortunately throws an error after few successful lines:

What happened here is us being silly and assuming that we always have two words to replace, where we shouldn't expect any word to be present. Lets add some checks to our first and last words replacing functions. Let's see that on the exapmle.

Here we have added the statement which checks if we found any words in the string and if not we simply return the string as is, without any further calculations (see short circuiting). Lets try one more time to run the code on the whole test data.

It looks that our effort paid off, lets now try feed our main algorithm with data processed by what we have now. But first would be good to commit the changes.

Using our word replacer in the main program

First lets build the function that performs the replacing functionalities for a given string and returns the result.

This function is build based on the testing code we wrote above. It just returns the built string instead of logging it. And in the main function we will update the code to utilize this new function.

And after running the script with the test data passed to we get:

And this is the correct value. So we can now do a bit of cleaning up and commit the changes, before we run the whole thing on the real input data. The final code looks like this:

Real input data

If you looked at the provided code carefully, to run this whole thing with the real data we simply have to uncomment the input file reading and delete the test data. The result we get is . Submitting this result unfortunately is wrong. Now lets think of why is that.

The intersecting words problem

So the problem we encounter is the following: With our word replacing algorithm, every word like which in turn has digit and will in our code result in as we do the second replacing operation on the string we get after the first word replacing. Lets analyze how can we overcome this obstacle. First question we can ask is if we really need to replace the whole words by the corresponding digits? Should we at all do the replacement at the first place?

The solution

What if instead of searching for words and replacing them in the strings, and then searching for first and last digits in these strings, omitting all the other characters, we could first prepare the new dataset by extracting just the numbers written in digits and numbers written in words replaced by the digits? Lets have a look at the following function:

This function is building the new output string which will be build out of digit characters only. It goes in the loop from the starting index of the string and each time creates a sub-string starting at the current index till the end of the string. If the first digit of this sub-string is a digit then it appends it to the result. If its not a digit then it finds where each spelled number occurs in the sub-string. Now, if any of the indexes is , it means that our sub-string starts with a number-word. In that case we append the corresponding digit to the result, otherwise we do nothing. Checking only for the starting word of each sub-string assures that even words that are overlapping will be catched in the next loop iteration. For example string will be translated to . Now thanks to that our first and last digit searching algorithm can be simplified to just taking the first and the last character of that string. Take a look at the code after all the changes.

Final result

Running this code now gives us:

And after submitting this answer we are getting the following window. The final step is to commit our final code.

Conclusion

When I was writing this post, I was doing so alongside with solving the puzzle to show you how does the process looks like. I could have first figured out the whole thing and afterwards describe only the final working solution but that's not how it works in real life. I wanted to show you all that the normal thing of solving problems is to make mistakes and try different solutions to get the expected results. So the next time when you find yourself struggling with a problem, remember - we all do and even the most experienced developer makes mistakes. The true key to being better is to try.

I hope you all enjoyed this challenge as much as I did and see you in Day 2, part 1