Day 3, part 1

Introduction

Welcome to day 3 of Advent of Code. The whole description of the problem we are going to solve today can be found here. Please read it carefully to get a good understanding of what we are asked to do today. This time we are given the "schematic" describing the engine parts. This schematic is built out of numbers and symbols. The numbers which are adjacent to any symbol (even diagonally) are the numbers of the engine parts. All the other numbers that are not touching any of the symbols does not matter to us. The sign is not considered a symbol, it is just a spacer in the schematic. After getting all the engine part numbers, we are asked to return a sum of those numbers.

Understanding the problem

Let's analyze the test data:

If we look closely, we can see that all the numbers on the schematic, except from and are touching to a symbol character (we consider symbol as any special character other than a dot). These numbers which are touching one or more symbols are considered to be part numbers and these are the numbers we are looking for. These numbers summed up are the result to this puzzle.

Creating files for the challenge

We are going to start by creating the new directory in or project's root directory. We also create new file inside the folder, which will be our main entry for the code for this puzzle. Let's also already place the test data in the .

Solution

Preparing the input data

To be able to easily operate on the input data, we have to first parse the data to some more useful structure than a bunch of text. The good candidate seems to be a 2D array where the outer array is a collection of lines and each of the inner arrays is a collection of characters in each line. We can reuse the function we was using for example in Day 2, part 1#Preparing the input data. We will then add some more code to further split each line into separate characters.

Now we can run this code and see the results in the terminal.

This seems to me correct. We can now start to making use of these information.

How should we do the search?

So now we have to find the numbers and only those numbers which are adjacent to any symbol. When I was thinking about how to handle this problem, I was looking at the problem from two sides:

1. find all symbols and then only check if those symbols are touching any of the numbers and if so, find the whole number.
2. search for numbers and then check their neighbors if any of them is a symbol It might seem like a good idea to search for the symbols first and only find the numbers that are touching any of these symbols, but

• if one number touches more than one symbol, how do we check if we already have this number in our search results?
  As you can see the number will be found as a neighbor of both symbols in this example
• if any part of the number can touch the symbol, how do we handle parsing this whole number
  So we can see that number is touching the symbol from the side and has to be parsed looking at the next characters in the map. The number is touching the symbol diagonally and has to be searched backwards in the array to find the whole number. The most problematic case is the number which takes 3 neighbor cells and if not handled carefully, might end up being 3 separate numbers. This leaves us with the second solution, where we first find all the numbers and then check there are symbols in their neighborhood.

Searching for numbers

Thankfully, all the numbers are horizontally placed in our grid of numbers, which means for us that we need to look only each individual line in search for numbers. Our searching function needs to go through each character in the line and if it finds a digit, it has to start building the number. In the next iteration it checks again if there is another digit on the way, and if so, it appends it to the number created in previous step. If the next character is not a digit, we finalize parsing the number and we push it to the fond numbers array.

In the function, we start by creating an empty array of found numbers and an empty string that will collect the digit characters building the final number. In case the character we are currently looking at is a digit, we append it to the output number. In case its not a digit and our current number is not an empty string, that means we already found a number and now we finalized building it, so we push it to the array of results and we clear the , the same we do in case the char we found is a digit and it is the last character in the current input array. This is the result we get now for the first line of test input:

This is what we wanted, but is this enough for us to proceed? Well no. Right now we have an array with found numbers but how do we know where is this placed in the initial grid, so we can check if any of the neighbors is a symbol?

Keep track of numbers position

So we have the numbers, but what next? Now we need to check the numbers neighborhood for symbols to filter out only those numbers which are part numbers. To designate the neighborhood, we need to keep track of the start and end position of the numbers we have found. To do so we have to modify the way we store the found numbers. Instead of just storing the number itself, we construct an object with the number, but also with start and end index of the number in the input grid. We also want to store the line index in each the number was found. This is the new version of our numbers finding function:

As you can see, now it takes a new parameter which is the the current line index in the grid. Now it might look silly that we are passing the line by indexing the with the same index we pass as a second argument, but this will actually be useful when we will be using this function inside the method, going through the whole grid. Actually lets do it and confirm that it works as expected.

Comparing these results to the numbers we can manually find in the input text, we can see that the results we have in here are what we expect to see. We can commit these changes and move to the next step.

Check number's neighborhood

Now when we have the numbers and we know their position it the grid, we can determine the neighborhood of each of these numbers. Then we can check these neighbors if any of them is a symbol. Actually we can find the indexes at which the neighborhood spans. In the checking step we can actually even check the whole area, even the bits there the number itself is, as we know that the number is not a symbol.

This function give us start and end x and y indexes. We are checking if points above, below, to the left and to the right are not outside of the grid. If the points are outside, we use the numbers position instead. When we run this code, we get:

So, we have the numbers and for each number we can calculate its surroundings. Now the only step left is to check these areas for a presence of symbols. But first lets save what we have.

Looking for symbols

Now when we have the numbers and their neighborhoods, we can search in them to filter out those numbers which are touching any symbol (this number is then the part number we are looking for).

Here we have a chain of functions which are determining if the given number has a symbol in its neighborhood. To do that it takes all the numbers and the input grid. Then it uses the array method in which, using the , we check if there is a symbol in the numbers surrounding. To determine if the character is a symbol we simply check if the character isn't a number and if it isn't a dot. After filtering the numbers we also them to leave only the part number without any other additional data. These are the results:

As we know, in the test data, only the numbers and are not the part numbers and we can't see these two numbers in the final output, so we can assume our function works fine. Lets save our progress.

Summing the part numbers

Now the only last bit of code we need is to add those part numbers together. We can do it simply with the method.

And the output is:

Looking at the description of this challenge, is the output we have expected to see. We can save our progress.

Real input data

The final step to solve the first part of the day 1 challenge is to use the real input data provided on the day 2 page. I created the file inside of the directory and put the data in it. Now it is time to read the input file. This time again we can reuse the function from day 1.

Final result

Now we can replace the test input data and run our script one last time to get the final answer to the puzzle.

Now we can copy the number we get and paste it in the submit field on the website. Clicking the button and... A great success! The final step is to commit our final code.

Now please feel invited to follow me in part two - Day 3, part 2