Advent of Code Day 7

Here are some

Problem: Bridge Calibration Equation Validator

You are tasked with helping a group of engineers verify equations for calibrating a bridge. Each equation consists of:

1. A target value TTT, provided before a colon (:).
2. A sequence of numbers N1,N2,…,Nk, separated by spaces, provided after the colon.

Your goal is to determine whether it is possible to insert the operators + (addition) or * (multiplication) between the numbers N1, N2, …, Nk​, such that when evaluated from left to right (ignoring operator precedence), the result equals TTT.

If an equation is valid, include TTT in the total calibration result. Otherwise, discard it.

Example:

Input:

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

Output:

3749

Explanation: The valid equations are:

• 190: 10 19 → 10∗19=190
• 3267: 81 40 27 → 81+40∗27=3267
  • 81+40∗27=3267 or 81∗40+27=3267
• 292: 11 6 16 20 → 11+6∗16+20=292

The total calibration result is 190+3267+292=3749

Constraints:

1. 1≤length of number sequence≤101 \leq \text{length of number sequence} \leq 101≤length of number sequence≤10
2. 1≤Ni,T≤1051 \leq N_i, T \leq 10^51≤Ni​,T≤105
3. Each equation has exactly one target value TTT and one sequence of numbers.

Notes:

1. Operators are evaluated left-to-right, not based on standard precedence rules.
2. Each valid TTT should be added to the total calibration result only once, even if multiple operator combinations can produce TTT.
3. If no combination of operators can produce TTT, the equation is invalid.

from itertools import product


def evaluate_expression(numbers, operators):
    """
    Evaluates the expression formed by inserting operators between numbers from left to right.
    """
    result = numbers[0]
    for i in range(len(operators)):
        if operators[i] == "+":
            result += numbers[i + 1]
        elif operators[i] == "*":
            result *= numbers[i + 1]
    return result


def can_form_target(target, numbers):
    """
    Determines if the target can be formed using the numbers with any combination of operators.
    """
    n = len(numbers) - 1  # Number of operator slots
    for operators in product(["+", "*"], repeat=n):
        if evaluate_expression(numbers, operators) == target:
            return True
    return False


def total_calibration_result(data: str):
    """
    Calculates the total calibration result by summing up target values of valid equations.
    """

    equations = data.splitlines()
    total = 0
    for equation in equations:
        # Parse the equation
        target, numbers = equation.split(":")
        target = int(target.strip())
        numbers = list(map(int, numbers.strip().split()))

        # Check if the target can be formed
        if can_form_target(target, numbers):
            total += target

    return total

Problem: Bridge Calibration with Concatenation

The engineers have discovered an additional operator, ||, which concatenates numbers. For example:

• 12∣∣345=1234512 || 345 = 1234512∣∣345=12345

Your task is to determine whether equations can be made true by inserting any combination of the following operators:

1. Addition (+)
2. Multiplication (*)
3. Concatenation (||)

All operators are evaluated left-to-right, ignoring standard precedence rules. If an equation is valid, include its target value in the total calibration result.

Example:

Input:

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

Output:

11387

Explanation: Using the three operators (+, *, ||), the valid equations are:

1. 190: 10 19 → 10∗19=190
2. 3267: 81 40 27 → 81+40∗27=3267
3. 292: 11 6 16 20 → 11+6∗16+20=292
4. 156: 15 6 → 15 ∣∣ 6=156
5. 7290: 6 8 6 15 → 6∗8∣∣6∗15=7290
6. 192: 17 8 14 → 17∣∣8+14=192

The total calibration result is 190+3267+292+156+7290+192=11387

Constraints:

1. 1≤length of number sequence≤101 \leq \text{length of number sequence} \leq 101≤length of number sequence≤10
2. 1≤Ni,T≤1051 \leq N_i, T \leq 10^51≤Ni​,T≤105
3. Each equation has exactly one target value TTT and one sequence of numbers.

from itertools import product


def evaluate_expression(numbers, operators):
    """
    Evaluates the expression formed by inserting operators between numbers from left to right.

    :param numbers: List of integers.
    :param operators: List of operators ('+', '*', '||').
    :return: The evaluated result as an integer.
    """
    result = numbers[0]
    for i in range(len(operators)):
        if operators[i] == "+":
            result += numbers[i + 1]
        elif operators[i] == "*":
            result *= numbers[i + 1]
        elif operators[i] == "||":
            result = int(str(result) + str(numbers[i + 1]))
    return result


def can_form_target(target, numbers):
    """
    Determines if the target can be formed using the numbers with any combination of operators.

    :param target: The target value to achieve.
    :param numbers: List of integers in the equation.
    :return: True if the target can be formed, False otherwise.
    """
    n = len(numbers) - 1  # Number of operator slots
    for operators in product(["+", "*", "||"], repeat=n):
        if evaluate_expression(numbers, operators) == target:
            return True
    return False


def total_calibration_result(data: str):
    """
    Calculates the total calibration result by summing up target values of valid equations.

    :param equations: A list of strings, each representing an equation in the format "T: N1 N2 ... Nk".
    :return: The total calibration result as an integer.
    """
    equations = data.splitlines()

    total = 0
    for equation in equations:
        # Parse the equation
        target, numbers = equation.split(":")
        target = int(target.strip())
        numbers = list(map(int, numbers.strip().split()))

        # Check if the target can be formed
        if can_form_target(target, numbers):
            total += target

    return total



print(total_calibration_result(data))