Saturday, December 7, 2024

Advent of Code: Day 7

advent-of-code

Stephen Keane@skeane.io

Advent of Code: Day 7

Day7: Bridge Repair

Check out Bridge Repair for the day7 puzzle.

Part 1

itertools to the rescue on this one!

day 7 gives us a series of terms and asks us to figure out all of the different expressions we can build using a combination of '+' and '*' operators.

I played around with this for a little while before realizing that python has a pre-built solution for this in itertools.product:

plugging in a function using itertools.product, quickly got me the combinations I needed.

        def getOperatorCombinations(operators, numCombinations):
          operatorCombinations = []
          for combination in itertools.product(operators, repeat=len(terms)-1):
              operatorCombinations.append(combination)
          return operatorCombinations

Once that was in place, this should have come together fast.

I struggled a bit because I didn't read the puzzle description carefully enough. I initially built strings of the expressions and then used eval(string) to evaluate each of them. This didn't work because the puzzle wanted me to ignore the order of operations and just evaluate left to right.

I added a subfunction to do that, and got the solution I needed.

Part 1 Solution:

testPath = './testInput.txt'
inputPath = './input.txt'
chosenPath = inputPath

import itertools
import re

def getValidEquations(path):
  validEquations = []
  def isValid(result, terms):
      operators = ['+', '*']
      numCombinations = (len(terms)-1) * len(operators)
      def getOperatorCombinations(operators, numCombinations):
          operatorCombinations = []
          for combination in itertools.product(operators, repeat=len(terms)-1):
              operatorCombinations.append(combination)
          return operatorCombinations
      
      def makeExpression (terms, operatorCombinations):
          expressions = []
          for i in range(len(operatorCombinations)):
              expression = []
              for j in range(len(terms)):
                  expression.append(str(terms[j]))
                  if j < len(operatorCombinations[i]):
                      expression.append(str(operatorCombinations[i][j]))
              expressions.append(expression)
          return expressions
      
      allExpressions = makeExpression(terms, getOperatorCombinations(operators, numCombinations))

      def evaluateExpression(expression):
          arr = re.findall(r'd+|[+*]', expression)
          result = int(arr[0])
          i = 1
          while i < len(arr):
              operator = arr[i]
              num = int(arr[i + 1])       
              if operator == '+':
                  result += num
              elif operator == '*':
                  result *= num
              i += 2  
          return result

      for expression in allExpressions:
          string = ''.join(expression)
          if evaluateExpression(string) == int(result):
              validEquations.append(evaluateExpression(string))
              break

      return validEquations
  with open(path, 'r') as file:    
      lines = file.readlines()
      for line in lines:
          line = line.strip()
          result, terms = line.split(': ')
          terms = terms.split(' ')
          terms = list(map(int, terms))
          total = (isValid(result, terms))
  return (sum(total))

print(getValidEquations(chosenPath))

Part 2

for part 2, I just needed to add a "||" operator that concatenated the two numbers together.

I added the new operator to the list of operators, the itertools.product gave me the new list of combinations with no extra work on my part.

    operators = ['+', '*', '|']
    numCombinations = (len(terms)-1) * len(operators)
    def getOperatorCombinations(operators, numCombinations):
        operatorCombinations = []
        for combination in itertools.product(operators, repeat=len(terms)-1):
            operatorCombinations.append(combination)
        return operatorCombinations

Once that was in place, I updated my evaluateExpression (i.e.,'ignore PEMDAS') function to handle the new operator to get the part 2 solution.

        def evaluateExpression(expression):
          arr = re.findall(r'd+|[+*|]', expression)
          result = int(arr[0])
          i = 1
          while i < len(arr):
              operator = arr[i]
              num = int(arr[i + 1])       
              if operator == '+':
                  result += num
              elif operator == '*':
                  result *= num
              elif operator == '|':
                  result = int(f'{result}{num}')
              i += 2  
          return result

Part 2 Solution:

testPath = './testInput.txt'
inputPath = './input.txt'
chosenPath = inputPath
import itertools
import re

def getValidEquations(path):
  validEquations = []
  def isValid(result, terms):
      operators = ['+', '*', '|']
      numCombinations = (len(terms)-1) * len(operators)
      def getOperatorCombinations(operators, numCombinations):
          operatorCombinations = []
          for combination in itertools.product(operators, repeat=len(terms)-1):
              operatorCombinations.append(combination)
          return operatorCombinations
      
      def makeExpression (terms, operatorCombinations):
          expressions = []
          for i in range(len(operatorCombinations)):
              expression = []
              for j in range(len(terms)):
                  expression.append(str(terms[j]))
                  if j < len(operatorCombinations[i]):
                      expression.append(str(operatorCombinations[i][j]))
              expressions.append(expression)
          return expressions
      
      allExpressions = makeExpression(terms, getOperatorCombinations(operators, numCombinations))

      def evaluateExpression(expression):
          arr = re.findall(r'd+|[+*|]', expression)
          result = int(arr[0])
          i = 1
          while i < len(arr):
              operator = arr[i]
              num = int(arr[i + 1])       
              if operator == '+':
                  result += num
              elif operator == '*':
                  result *= num
              elif operator == '|':
                  result = int(f'{result}{num}')
              i += 2  
          return result
      
      for expression in allExpressions:
          string = ''.join(expression)
          if evaluateExpression(string) == int(result):
              validEquations.append(evaluateExpression(string))
              break

      return validEquations
  with open(path, 'r') as file:    
      lines = file.readlines()
      for line in lines:
          line = line.strip()
          result, terms = line.split(': ')
          terms = terms.split(' ')
          terms = list(map(int, terms))
          total = (isValid(result, terms))
  return (sum(total))

print(getValidEquations(chosenPath))