Advent of Code 2024 - Day 2: Red-Nosed Reports
Attention!
-
Check Advent of Code for the full challenge details. They created everything we need to know about the challenge - give them your support.
-
My solutions are not ‘the’ solutions - I target one of the possible solutions. They might not be the most efficient, but they are a way to solve the problem. I do not plan to spend too much time doing the challenges.
-
Every challenge = different language - just for fun and learning.
-
I do not include the input data, but you can find it on the Advent of Code website or in the repository of the code.
The Advent of Code challenges continue, I’m back with Day 2, and this time, it’s all about analyzing reactor safety reports from the mysterious Red-Nosed Reindeer nuclear fusion/fission plant. The task involves ensuring that certain reports—specifically, reactor safety data reports—are safe based on a series of rules.
I will use Golang to solve the puzzle.
Problem Breakdown
The data consists of several reports, each containing a list of numbers called levels. For each report, I need to determine whether the levels are safe by verifying that:
- The levels are either all increasing or all decreasing.
- The difference between adjacent levels must be at least 1 and at most 3.
Example:
7 6 4 2 1 --> Safe
1 2 7 8 9 --> Unsafe
9 7 6 2 1 --> Unsafe
1 3 2 4 5 --> Unsafe
8 6 4 4 1 --> Unsafe
1 3 6 7 9 --> Safe
In this example, two reports are safe.
Part One: Finding Safe Reports
The first task is straightforward. For each report, I need to check if it is safe by ensuring that:
- The numbers are either all increasing or all decreasing.
- The difference between each adjacent pair of numbers is between 1 and 3 (inclusive).
Code for Part One
The main function reads the input data and splits it on a newline character, checks lines and prints the result (sum of the safeLevels).
// main.go
func main() {
input, err := os.ReadFile("input.txt")
if err != nil {
log.Fatalf(err.Error())
}
safeLevels := 0
for _, line := range strings.Split(string(input), "\n") {
digits := strings.Split(strings.TrimSpace(line), " ")
if isLineSafe(digits) {
safeLevels += 1
}
}
log.Printf(":: 1 > Safe levels: %d \n", safeLevels)
}
The main logic is of course in the isLineSafe function. It is not complicated, it ensures that:
- The difference between consecutive digits is between 1 and 3.
- The direction (increasing or decreasing) is consistent throughout the sequence.
- If either condition is violated at any point, the function returns false.
In isLineSafe functions I’m using some helper functions:
- getDirection: Determines whether the sequence of digits is increasing or decreasing based on two numbers.
- abs: Simple utility function that calculates the absolute value of an integer.
// main.go
func isLineSafe(digits []string) bool {
previousNum := 0
direction := 0
for index, digit := range digits {
num, _ := strconv.Atoi(digit) // ignoring error
if index == 0 {
previousNum = num
continue
}
if index == 1 {
direction = getDirection(num, previousNum)
}
difference := abs(num - previousNum)
currentDirection := getDirection(num, previousNum)
previousNum = num
if !(difference > 0 && difference < 4) || (direction != currentDirection) {
return false
}
}
return true
}
func getDirection(num, previousNum int) int {
if num > previousNum {
return 1
} else {
return -1
}
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
Part Two: The Problem Dampener
In the second part of the puzzle, the engineers introduce a new module called the Problem Dampener, which allows them to “ignore” a single bad level in an otherwise safe report. If removing a single level from an unsafe report makes it safe, then the report should be considered safe.
New Strategy:
For each report, if it’s unsafe, I attempt to remove one level at a time and check if the resulting report is safe. If any report becomes safe after removing one level, I count it as safe.
Code for Part Two
Part two is similar to part one, but it tries to fix the report. For each unsafe report, I loop through each level and attempt to remove one level at a time. After removing a level, I check if the new report meets the safety conditions. If it does, we count it as safe.
// main.go
func main() {
// ... part one hidden
safeLevels = 0
for _, line := range strings.Split(string(input), "\n") {
digits := strings.Split(strings.TrimSpace(line), " ")
if isLineSafe(digits) {
safeLevels += 1
continue
}
inner:
for index := range digits {
newDigits := removeOneElement(digits, index)
if isLineSafe(newDigits) {
safeLevels += 1
break inner
}
}
}
log.Printf(":: 2 > Safe levels with Problem Dampener: %d \n", safeLevels)
}
The more important thing in the part two is the removeOneElement function that simply creates new array of digits without the indexed one.
It is not the most optimal solution, but I did not take more time to improve it.
// main.go
func removeOneElement(digits []string, index int) []string {
newDigits := make([]string, 0)
for i, digit := range digits {
if i == index {
continue
}
newDigits = append(newDigits, digit)
}
return newDigits
}
Final Solution Code
The final solution code can be found on my GitHub repository.
If you like the content, don’t forget to give it a star ⭐.
Time Complexity:
- Part One: For each report, the time complexity is O(n) where n is the number of levels in the report. The main bottleneck here is iterating through the report and checking the conditions.
- Part Two: The time complexity increases because for each unsafe report, we check all possible single-level removals, making the complexity O(n²) in the worst case.
Optimizations:
The solution works well within the problem’s constraints, but in a more complex scenario, optimizing the checking and removal process could be necessary.
Conclusion
Day 2’s challenge was a great exercise in array manipulation and logic checking. The second part, with the introduction of the Problem Dampener, added an extra layer of complexity, but using nested loops to check each possible solution worked perfectly (not the best performance of course).
Tomorrow, C. Stay tuned.