A Short Preface...
"Hey Ethan, have you heard about Advent of Code (AoC)?" asked my colleague at work.
Looking back as I write this experience in my blog now, this seemingly innocent question started my less than small obsession with completing at least one day of the coding challenge.
I must first say that I am no means a competitive programmer and I had no intention of being anywhere on the leaderboards of this event nor writing the most efficient solution.
My goals were simple. I wanted to test my problem-solving and programming abilities in a fun way, so I set myself up to take on day 1 of AoC 2023 with as little external help as possible. Yes, this meant no asking ChatGPT :)
In this blog post, I would like to discuss my approach and solution to the question that I attempted for day 1 (part 1) of AoC 2023. In addition, at the end, I want to talk about an alternative solution that I read after completing part 1.
This blog post mainly serves as a documentation of my code for my future reference. However, at the same time, I do hope whoever reads this may find this solution insightful :)
What's Advent of Code?
Advent of Code is an annual coding event created by Eric Wastl which runs from 1st to 25th December. Every day during this period, a Christmas themed puzzle will be released at midnight (U.S Eastern standard time). These puzzles can be solved using any programming language and at any pace with no time limit. As the days progress, the puzzles will generally increase in difficulty. Solving a puzzle will award a certain amount of Gold Stars which can be collected and used as an indication of an event member's participation.
There is also a competitive side to this event where programmers try to solve the puzzle as quickly as possible upon release. The top few scores will have their usernames on a leaderboard.
As I began learning more about this event, I also read about some members using extremely unorthodox methods to solve the puzzles such as using Assembly language, Microsoft Excel, etc.
The Puzzle (Part 1)
Above is a screenshot of the puzzle for day 1 of the event. The calibration document consisted of 1001 lines of text similar to the examples given in the screenshot. The expected output should be a somewhat large integer that is the sum of all the 2-digit numbers that are derived from each line of the calibration document.
My language of choice to solve this puzzle was Python3. I aimed to solve this challenge using only basic native Python functions. This meant no using of external libraries and algorithms or data structures.
After reading through the puzzle and understanding the objectives, I began researching string methods in Python. I created a small test program to test out the limitations and to find the logical flow to get a solution. I also tested some methods for lists in Python.
Within this test program, I tested my solution using the first line of text in the calibration document. After getting the correct numerical result for the first line, I tested the solution on some other lines of the calibration document to verify the results and check its reliability.
When the results seemed to be correct, I made this program into a function. This function is the lineprocessor(name) function in the code below.
Code Walkthrough
inputfile = open("input.txt", "r") #open input file in read mode
rawinput = inputfile.read()
mainlst = rawinput.split("\n") #split elements of the text file wherever there is a space
inputfile.close()
mainlst_index = 0
runningsum = []
def lineprocessor(name):
lst = []
lst_index = 0
first_number = 0
first_filled = False
last_number = 0
for letters in name:
lst.append(letters)
for i in range(len(lst)): #find and save first number
if lst[lst_index].isnumeric() == False: #if character is not a number, skip to next
lst_index = lst_index + 1
elif lst[lst_index].isnumeric() == True and first_filled == False: #if current character is a number, save the number to first no. variable and declare first no. variable as filled
first_number = lst[lst_index]
first_filled = True
lst_index = lst_index + 1
elif lst[lst_index].isnumeric() == True and first_filled == True: #searching for second number
last_number = lst[lst_index]
lst_index = lst_index + 1
if last_number == 0:
last_number = first_number
output = str(first_number) + str(last_number) #add the first and last number together as strings
return int(output) #format the output as an integer
print("Number of distinct elements in input file:", len(mainlst))
for i in range(len(mainlst)):
runningsum.append(lineprocessor(mainlst[mainlst_index]))
mainlst_index = mainlst_index + 1
totalsum = sum(runningsum)
print("Sum of all calibration values = ", totalsum)
Above is my full solution for part 1 of the puzzle. I will now discuss the flow of the program in detail.
Reading Calibration Document Text Input Into Python
inputfile = open("input.txt", "r") #open input file in read mode
rawinput = inputfile.read()
mainlst = rawinput.split("\n") #split elements of the text file wherever there is a space
inputfile.close()
mainlst_index = 0
runningsum = []
To start, I saved the calibration document provided as a .txt file so that it can be read by the code. The text file is titled "input.txt".
The saved text file will then be split into its respective elements using blank spaces as a delimiter. The elements are then saved into a list (mainlst). Lastly, the input file is closed.
To work with the list, I created an index (mainlst_index) and set it to "0" at the start of the program. I also created a blank list (runningsum) to save all the outputs of the function. This list can then be summed using the sum() function at the end of the program to give the final output for submission.
Main function
def lineprocessor(name):
lst = []
lst_index = 0
first_number = 0
first_filled = False
last_number = 0
for letters in name:
lst.append(letters)
for i in range(len(lst)): #find and save first number
if lst[lst_index].isnumeric() == False: #if character is not a number, skip to next
lst_index = lst_index + 1
elif lst[lst_index].isnumeric() == True and first_filled == False: #if current character is a number, save the number to first no. variable and declare first no. variable as filled
first_number = lst[lst_index]
first_filled = True
lst_index = lst_index + 1
elif lst[lst_index].isnumeric() == True and first_filled == True: #searching for second number
last_number = lst[lst_index]
lst_index = lst_index + 1
if last_number == 0:
last_number = first_number
output = str(first_number) + str(last_number) #add the first and last number together as strings
return int(output) #format the output as an integer
Above is the function that I created from the test program. This function takes in a string as an argument and returns a single 2-digit number in integer form.
There are 5 local variables declared at the start of this function. I will explain the use of these variables as I elaborate on the function in detail.
for letters in name:
lst.append(letters)
This function first splits the input string and appends each individual character in a list (lst).
for i in range(len(lst)): #find and save first number
if lst[lst_index].isnumeric() == False: #if character is not a number, skip to next
lst_index = lst_index + 1
elif lst[lst_index].isnumeric() == True and first_filled == False: #if current character is a number, save the number to first no. variable and declare first no. variable as filled
first_number = lst[lst_index]
first_filled = True
lst_index = lst_index + 1
elif lst[lst_index].isnumeric() == True and first_filled == True: #searching for second number
last_number = lst[lst_index]
lst_index = lst_index + 1
if last_number == 0:
last_number = first_number
It will then check character by character from the list(lst) using a for-loop. The number of times the for-loop will run is dependent on the length of the input string. In other words, the number of elements in the list (lst).
The individual characters are first checked if they are numbers using the .isnumeric() method. This method returns either a logical "True" or "False".
The first character of the list is checked by using the index (lst_index which is initialized to "0") and seeing if the value at the current index is a number or not. If it is not a number, the index will increment by 1 to check the next element of the list. This will keep executing until a number is encountered. This checking process is carried out by the first "if" statement.
elif lst[lst_index].isnumeric() == True and first_filled == False: #if current character is a number, save the number to first no. variable and declare first no. variable as filled
first_number = lst[lst_index]
first_filled = True
lst_index = lst_index + 1
When a number has been encountered, the .isnumeric() method will return a "True" and the first "elif" block will execute. This will happen because there has been no condition thus far that satisfies the condition of the first "elif" block. While the .isnumeric() condition is satisfied, the "first_filled" flag is still at its initialized state which is a logical "False". This block can only be run if both conditions are True due to the logical "AND" relationship set in the condition.
The code in this conditional block will then store the value at the current index of the list into the "first_number" variable. The "first_filled" flag will then be set to a logical "True" and the index will increment by 1 to continue checking the following list elements.
Due to the conditions set to run this "elif" block, this block will only run once per function call.
elif lst[lst_index].isnumeric() == True and first_filled == True: #searching for second number
last_number = lst[lst_index]
lst_index = lst_index + 1
The last "elif" block will check if the remaining elements of the list are numbers after the first number has been found. If another number has been found, the code block will store the number in the "last_number" variable.
If this block detects another number later on down the list, the "last_number" variable will update to the current value of the list index. This ensures that the "last_number" variable will truly be the last number encountered in the list.
The index will then increment to check the next element of the list.
if last_number == 0:
last_number = first_number
This isolated "if" statement simply checks if the "last_number" variable has been updated. If the variable has not been updated, it means that no other numbers were encountered after the first number has been saved. In other words, the "last_number" variable will hold the value of "0" as initialized at the start of the function.
If no other numbers are encountered after the first, the "last_number" variable will take on the value of the first number encountered.
output = str(first_number) + str(last_number) #add the first and last number together as strings
return int(output) #format the output as an integer
After the list index (lst_index) is equal to the length of the input string (as declared in the for-loop), the first and last numbers will then be added together as strings and saved in the "output" variable.
Finally, the function will return the "output" variable as an integer.
Compiling Function Outputs
print("Number of distinct elements in input file:", len(mainlst))
for i in range(len(mainlst)):
runningsum.append(lineprocessor(mainlst[mainlst_index]))
mainlst_index = mainlst_index + 1
totalsum = sum(runningsum)
print("Sum of all calibration values = ", totalsum)
Above is the piece of code that glues all the parts of this program together.
The portion to take note here is the for-loop. This for-loop will run the same number of times as the number of lines in the input calibration document. Since the calibration document has been saved as a list (mainlst), the number of times this for-loop will run will simply be the length of said list.
Within this loop, the lineprocessor() function will be applied to all elements of the main list (main_lst) starting at index "0". The outputs of the function are appended to the "runningsum" list and the main list index (mainlst_index) will increment by 1.
Once this loop has completed running, the length of the "runningsum" list will be the same as the length of the "mainlst" list.
To get the solution of the program, the sum() function is called on the "runningsum" list. This value is saved to the "totalsum" variable. The variable is then printed, and the program concludes here.
Submission Time!!
With fingers crossed, I ran the code and was relieved to see a "somewhat large integer" value printed on my terminal. I decided to submit my answer and was pleasantly surprised to see that it was correct the first time :)
There's my first Advent of Code gold star!
As this was my first time participating in this event, I was not aware that puzzles usually come in 2 parts. However, I decided maybe it was enough for one day. I shall attempt part 2 on another day. Perhaps tomorrow.
Side note: Apologies for the low-quality screenshot. The gold star is really all that matter though. Oh, and being one step closer to restoring snow operations too of course. That matters too :)
Alternative Solution
Remember the alternative solution I mentioned in my preface?
Let's do a quick walkthrough of the code flow before I end off this post. The alternative solution changes the way my lineprocessor() function derives the first and last number of the function input argument.
Here is a simple program flow of the alternative solution:
Split the input string of the function into individual strings and store it in a list. This step is the same as what my function does.
From the beginning of the list, check each character if it is a number. Continue checking up the list by incrementing the list index by 1 until the first number is encountered and store it in the "first_number" variable. Sounds familiar to my approach so far...
Here is where the difference is. Once the first number has been found, start searching from the end of the list**.** Continue checking down the list by decrementing the list index by 1 starting from the end until a number is encountered. The first number encountered in this reverse process will be saved in the "last_number" variable.
If no number is encounter, "last_number" will be equal to "first_number".
There you have it, 2 digits.
This seems like a more efficient solution compared to mine. Maybe because it seems like there is a possibility that it carries out lesser "checks" as compared to my solution which will assume that the entire string needs to be checked.
I'm not sure if it really is more efficient...but I'm willing to give it a try and maybe find a way to work out a quantifiable way to measure the efficiency of this process. Perhaps by measuring the space and time complexity of the 2 solutions. I'll need to learn big "O" notation for that. Seems interesting enough, if I do decide to get to it, I'll write about my findings in a subsequent blog post :)
A Short Conclusion
Well, this whole puzzle has been really fun to work on so far. And I'm not saying that because the answer was correct the first time. Remember, this is only part 1 and part 2 is well on its way. So far this has been a fun exercise that's quite a breath of fresh Christmas air for me.
It definitely is an interesting experience participating in my first coding event and I think I'll be keeping my eyes peeled for more in the future. I was also delighted to see that this event had been running for quite a number of years. I'm looking forward to attempting the puzzles from previous years, but I think after completing part 2, I would like to get back to my hardware development projects. At least for now. I'll be back for more AoC very soon for sure though :)
Happy Holidays!!!