img of Advent of Code 2024 - Day 7: Bridge Repair

Advent of Code 2024 - Day 7: Bridge Repair

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 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.

Today’s challenge takes me to a jungle where engineers are trying to repair a broken rope bridge. Unfortunately, they can’t finish the job because some elephants have stolen the operators from their calibration equations.

My task is to figure out which of the given equations can be solved by inserting the right operators: addition (+), multiplication (*) and later, (in part two) a new concatenation operator (||). I’ll need to evaluate these equations left-to-right and determine which test values can be produced. Once I identify the valid equations, I’ll calculate the total calibration result.

Today will be my first day with Swift

Problem Breakdown

The input consists of several lines, each with a target value and a series of numbers. For each line, I need to insert operators between the numbers and check if I can make the target value. The operators must be applied left-to-right, and numbers cannot be rearranged.

Example input:

456255051: 518 367 3 35 39 7 8
1358: 592 80 529 74 83
1464: 241 1 2 1 6
46217848: 17 3 4 9 2 9 74 4 46 2 7 3
19284295257: 8 5 4 8 94 3 5 8 6 8 41 8
2864344343820: 2 864 344 34 3 820
10332050008487: 7 4 738 100 50 84 85
2385120: 9 7 7 4 53 593 98 6 88
160267179632: 2 2 707 6 6 8 2 9 4 98
248910: 2 4 62 9 6 613 3 779 3

Explanation for the first line: My task is to check if it is possible to get 456255051 from the numbers 518, 367, 3, 35, 39, 7, 8 using only addition, multiplication, and (in part two) concatenation, while parsing from left to right.

Solution Approach (preparation)

In this solution, the core logic revolves around parsing the input and checking if a target value can be formed from a series of numbers using different mathematical operations. To achieve this, I use a custom Calculation struct that holds each equation’s target value and a list of numbers that will be evaluated.

Step 1: Defining the Calculation Struct

The Calculation struct is designed to store two pieces of information:

  • target: The desired result for the equation.
  • nums: An array of integers representing the numbers involved in the equation.

This structure helps organize the data for each equation, allowing me to easily pass it around and process it during the calculations.

// main.swift
struct Calculation {
    var target = 0
    var nums: [Int] = []
}

Step 2: Parsing the Input File

The next key step involves reading the input file containing the equations. The parse function reads the content of the file line by line and splits each line into two parts:

  1. The target value, which is the number before the colon (:).
  2. The list of numbers, which are the values after the colon.

I use String.split to break the input into the target and numbers, then map the numbers from strings to integers. If the format of the line is incorrect, an error message is printed, and the line is skipped (or should just panic).

Here’s how the parsing process works:

  1. Read the file contents using String(contentsOfFile:).
  2. Split the file into lines and loop through each line.
  3. For each line, split it at the colon (:).
  4. Extract the target value and the list of numbers, converting the numbers into an integer array.
  5. Add the resulting Calculation struct to an array of calculations.

This approach simplifies the process of handling the equations, allowing easy access to each Calculation’s target value and associated numbers.

// main.swift
func parse(filePath: String) -> [Calculation] {
    var calcs: [Calculation] = []
    do {
        let fileContents = try String(contentsOfFile: filePath, encoding: .utf8)
        for line in (fileContents.split{ $0.isNewline }) {
            let parts = line.split { $0 == ":" }
            if parts.count != 2 {
                print("There is something wrong with the file contents!")
                continue
            }
            var calc = Calculation()
            calc.target = Int(parts[0])!
            calc.nums = parts[1].split { $0 == " " }.map { Int($0)! }
            calcs.append(calc)
        }
    } catch {
        print("Error reading file: \(error.localizedDescription)")
    }
    return calcs
}

Plus point for swift for the built in .isNewline helped me because today I tried to ‘code’ on Windows… TLDR: ‘\r\n’ != ‘\n’)

Code solution

Once the preparation is done and the input has been parsed into Calculation structs, the next step is to evaluate the calculations. This part of the solution focuses on filtering valid calculations and summing up the target values that can be formed from the numbers using the allowed operations (addition and multiplication).

The main logic happens in the filtering function isCalculationValid, which checks whether it’s possible to achieve the target value from the numbers in the equation by applying a combination of addition and multiplication, evaluated left to right.

Filtering and Summing the Results

The code snippet below reads the input file, parses the calculations, filters out the valid ones using isCalculationValid, and then sums up the target values of those valid calculations:

// main.swift
  let filePath = FileManager.default.currentDirectoryPath.appendingPathComponent("input.txt")
  let result = parse(filePath: filePath)
                .filter { isCalculationValid(calc: $0) }
                .map { $0.target }
                .reduce(0, +)
  print("result :: \(result)")
  • parse(filePath: filePath): Parses the input file into an array of Calculation structs.
  • filter { isCalculationValid(calc: $0) }: Filters the calculations to only keep the ones where the target can be achieved.
  • map { $0.target }: Extracts the target values from the valid calculations.
  • reduce(0, +): Sums up the valid target values to produce the final result.

The isCalculationValid Function

The core of the solution lies in the isCalculationValid function. Here’s how it works:

// main.swift
func isCalculationValid(calc: Calculation) -> Bool {
    var results = [Int]()
    results.append(calc.nums[0])
    for i in 1..<calc.nums.count {
        let currentNum = calc.nums[i]
        var newResults = [Int]()
        for result in results {
            newResults.append(result + currentNum)
            newResults.append(result * currentNum)
        }
        results = newResults
    }
    for result in results {
        if result == calc.target {
            return true
        }
    }
    return false
}
  • Initial Setup: The function starts by adding the first number from the list (calc.nums[0]) into a results array. This is the starting point for our calculations.
  • Iterating Over Numbers: The function then iterates through the rest of the numbers (calc.nums[i]). For each number, it applies both the addition (+) and multiplication (*) operators with every value already in the results array. This generates all possible intermediate results.
  • Updating the Results: After processing all previous results with the current number, the results array is updated with all possible results.
  • Checking for Target: Once all numbers have been processed, the function checks if any of the results in the array match the target value (calc.target). If so, it returns true, indicating the calculation is valid.
  • Return false: If no result matches the target, the function returns false, indicating the calculation is invalid.

Part Two: Concatenation

Part Two of the challenge builds directly on the logic from Part One, but with an important change: I now need to account for the possibility of concatenation between numbers in addition to addition and multiplication. Concatenation involves joining two numbers together rather than performing an arithmetic operation on them.

In order to handle this new operation, I slightly modified the existing function to introduce an option for concatenation. The modification was quite straightforward — by adding a withConcat flag to the isCalculationValid function, I was able to control whether concatenation should be considered as part of the calculation.

The Core Changes

The isCalculationValid function from Part Two is almost identical to Part One, with a small addition. The key difference is that we now check for the concatenation operation, which is handled by the concatNums function.

// main.swift
func isCalculationValid(calc: Calculation, withConcat: Bool = false) -> Bool {
  // ... the same
  newResults.append(result + currentNum)
  newResults.append(result * currentNum)
  if withConcat {
      newResults.append(concatNums(a: result, b: currentNum))
  }
  // ... the same
}

Of course it needs to be changed to true where isCalculationValid is called:

// main.swift
  let result = parse(filePath: filePath)
                .filter { isCalculationValid(calc: $0, withConcat: true) }
                .map { $0.target }
                .reduce(0, +)

Concatenation Logic

At first, I attempted to handle the concatenation by simply interpolating the two numbers into a string, and then converting that string back into an integer. The approach was straightforward and worked fine for small inputs, but I quickly realized that it wasn’t the most efficient solution (my computer made this clear by spinning its fans as if it were running a marathon!). Interpolating numbers into strings and then converting them back to integers introduces unnecessary overhead, especially for larger numbers or when this operation is performed multiple times in a loop. Then I remembered a mathematical technique we discussed in class that can accomplish the same thing much more efficiently. Rather than using string manipulation, the formula for concatenation is based purely on arithmetic

Here’s how the concatenation is done mathematically:

  1. Calculate the number of digits in the second number (b).
  2. Multiply the first number (a) by 10 ^ k, where k is the number of digits in b.
  3. Add the second number (b) to this result, effectively appending b to a.

Example:

a = 5
b = 11
number_of_digits_in_b = 2
concat = (5 * 10 ^ 2) + 11  = 511

But I needed to know how many digits are in b. This time, I remembered how to do that. The function is quite understandable, as shown below.

// main.swift

/* Calculate a * 10^k + b, where k is the number of digits in B */
func concatNums(a: Int, b: Int) -> Int {
    let powerOfTen = Int(pow(10.0, Double(countDigits(of: b))))
    return (a * powerOfTen) + b
}

func countDigits(of number: Int) -> Int {
    if number < 10 {
        return 1
    }
    var count = 0
    var n = number
    while n > 0 {
        n /= 10
        count += 1
    }
    return count
}

And that’s all. It worked.

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 ⭐.

Conclusion

This challenge was an interesting mix of basic arithmetic and string manipulation (and fun math formulas). The solution is straightforward and quite efficient (could be better), and I was able to implement it in Swift.

The task was easier then yesterday, for sure.

As of Swift… As a language I think it is fun and the syntax is mostly ‘clean’ but the documentation and tooling is one of the worst I’ve seen (I think no explanation is needed).

Tommorow I will try Kotlin