# https://adventofcode.com/2020/day/18

from src.util.types import Data, Solution


def prepare_data(data: str) -> list[list[int | str]]:
    parsed_data = []
    for line in data.splitlines():
        line = line.replace(" ", "")
        tokens: list[int | str] = []
        for char in line:
            tokens.append(int(char) if char.isdigit() else char)
        parsed_data.append(tokens)
    return parsed_data


def evaluate(expressions, i=0):
    left = expressions[i]
    if left == "(":
        left, i = evaluate(expressions, i + 1)
    next_i = None
    while i < len(expressions) - 1:
        operator = expressions[i + 1]
        if operator == ")":
            return left, i + 1
        right = expressions[i + 2]
        if right == "(":
            right, next_i = evaluate(expressions, i + 3)
        if operator == "+":
            left += right
        elif operator == "*":
            left *= right
        if next_i is None:
            i += 2
        else:
            i = next_i
            next_i = None
    return left


def part_1(homework):
    return sum(evaluate(line) for line in homework)


def add_parentheses(line):
    # Put parentheses around additions so they are evaluated first.
    parentheses_levels = {"(": 1, ")": -1}
    i = 0
    while i < len(line):
        if line[i] == "+":
            level = 0
            # look left of the "+"
            for j, char in reversed(list(enumerate(line[:i]))):
                level += parentheses_levels.get(char, 0)
                if level == 0:
                    line = line[:j] + ["("] + line[j:]
                    i += 1
                    break
            # look right of the "+"
            for j, char in enumerate(line[i + 1:], i + 1):
                level += parentheses_levels.get(char, 0)
                if level == 0:
                    line = line[:j+1] + [")"] + line[j+1:]
                    i += 1
                    break
        i += 1
    return line


def part_2(homework):
    return sum(evaluate(add_parentheses(line)) for line in homework)


def solve(data: Data) -> Solution:
    solution = Solution()
    for i in range(6):
        sample_data = prepare_data(data.samples[i])
        solution.samples_part_1.append(part_1(sample_data))
        solution.samples_part_2.append(part_2(sample_data))

    challenge_data = prepare_data(data.input)
    solution.part_1 = part_1(challenge_data)
    solution.part_2 = part_2(challenge_data)
    return solution

# https://adventofcode.com/2020/day/18

from src.util.types import Data, Solution


def prepare_data(data: str) -> list[list[int | str]]:
    parsed_data = []
    for line in data.splitlines():
        line = line.replace(" ", "")
        tokens: list[int | str] = []
        for char in line:
            tokens.append(int(char) if char.isdigit() else char)
        parsed_data.append(tokens)
    return parsed_data


def evaluate(expressions, i=0):
    left = expressions[i]
    if left == "(":
        left, i = evaluate(expressions, i + 1)
    next_i = None
    while i < len(expressions) - 1:
        operator = expressions[i + 1]
        if operator == ")":
            return left, i + 1
        right = expressions[i + 2]
        if right == "(":
            right, next_i = evaluate(expressions, i + 3)
        if operator == "+":
            left += right
        elif operator == "*":
            left *= right
        if next_i is None:
            i += 2
        else:
            i = next_i
            next_i = None
    return left


def part_1(homework):
    return sum(evaluate(line) for line in homework)


def add_parentheses(line):
    # Put parentheses around additions so they are evaluated first.
    parentheses_levels = {"(": 1, ")": -1}
    i = 0
    while i < len(line):
        if line[i] == "+":
            level = 0
            # look left of the "+"
            for j, char in reversed(list(enumerate(line[:i]))):
                level += parentheses_levels.get(char, 0)
                if level == 0:
                    line = line[:j] + ["("] + line[j:]
                    i += 1
                    break
            # look right of the "+"
            for j, char in enumerate(line[i + 1:], i + 1):
                level += parentheses_levels.get(char, 0)
                if level == 0:
                    line = line[:j+1] + [")"] + line[j+1:]
                    i += 1
                    break
        i += 1
    return line


def part_2(homework):
    return sum(evaluate(add_parentheses(line)) for line in homework)


def solve(data: Data) -> Solution:
    solution = Solution()
    for i in range(6):
        sample_data = prepare_data(data.samples[i])
        solution.samples_part_1.append(part_1(sample_data))
        solution.samples_part_2.append(part_2(sample_data))

    challenge_data = prepare_data(data.input)
    solution.part_1 = part_1(challenge_data)
    solution.part_2 = part_2(challenge_data)
    return solution

# https://adventofcode.com/2020/day/18 # Put parentheses around additions so they are evaluated first. # look left of the "+" # look right of the "+"