Tag: recursion

The goal for the day was to find out if summing or multiplication would produce the result of an equation, evaluating from left to right (not as usual in maths, evaluating multiplication first). For example:

190: 10 19

Here the result is 190, so it is obvious that multiplication is needed, 10 x 19 is 190. Things get a bit more complicated when there are more numbers:

3267: 81 40 27

Here it is possible to solve the correct result by 81 + 40 * 27 and 81 * 40 + 27 since they both equal 3267. Basically this is a problem where you want to try out different combinations, also called as permutations, of how to use summing and multiplication to produce the correct end result. The input contains some formulas that do not produce the correct result with any permutation, so those are ignored when producing the end sum of the game.

One way to solve this is using recursion – trying different combinations based on the previous evaluation step result with the current number and looking if, after evaluating all the numbers, this produces the correct result.

Simplified, the recursive part looks like the code below. Parameters are:

• result: The expected end result of the evaluation.
• intermediate: The intermediate result of the previous + and * operations on the previous numbers, and
• numbers: the numbers not yet evaluated.

The return value is the result of the evaluation, either the correct result or zero if evaluation didn’t result in the correct result.

func evaluate(_ result: Int, _ intermediate: Int, _ numbers: [Int]) -> Int {
  if numbers.count == 1 {
   if intermediate + numbers.first! == result {
    return result
   } else if intermediate * numbers.first! == result {
    return result
   }
   return 0
  }
  
  let nextNumber = numbers.first!
  
  let summed = intermediate + nextNumber
  let multiplied = intermediate * nextNumber
  
  let evaluateSummed = evaluate(result, summed, Array(numbers.suffix(numbers.count - 1)), useConcatOperator: useConcatOperator)
  if evaluateSummed == result {
   return result
  }
  let evaluateMultiplied = evaluate(result, multiplied, Array(numbers.suffix(numbers.count - 1)), useConcatOperator: useConcatOperator)
  if evaluateMultiplied == result {
   return result
  }
  return 0
}

Recursion must always stop, otherwise it would continue forever – or actually, until stack memory available to the program runs out, producing a stack overflow.

Ending the recursion is handled first; if there is only one number left (the rightmost) we check if the intermediate result of the previous calculations together with the last number produce the expected result either by summing or multiplying. If not, return zero to indicate that this permutation of operations does not work correctly .

If there was more than one number left, both the sum and multiplication is calculated from the previous intermediate result, together with the current number. Then both intermediate values are used — recursively calling evaluate twice with sum and multiplied intermediate — with the rest of the numbers, checking if this produced the result we want. If not, code continues to the end of the function and returns zero — cannot do the thing with this permutation of operations.

I could have optimized the result, finishing the recursion earlier if the produced intermediary sum is greater than the end result. In that case, it is not useful to continue handing the numbers that are still left. Maybe I’ll add that later.

Second part of the puzzle added a third operator, concatenation. In addition to summing or multiplying, two numbers could be also concatenated, e.g. numbers 12 and 34 would result in number 1234.

This was easily added to the code above, just add another else if branch in the beginning and in the end part of the algorithm above, and execute those conditionally (if the function was called from part 2 solution).

Since the non-optimized version was already fast enough, haven’t done any optimization:

$ swift run -c release AdventOfCode 7 --benchmark
Building for production...
Build of product 'AdventOfCode' complete! (0.17s)
Executing Advent of Code challenge 7...
Part 1: 12940396350192
Part 2: 106016735664498
Part 1 took 0.023434208 seconds, part 2 took 0.590302166 seconds.

Now lunch, then some socializing, maybe continuing to Day 8 puzzles today or tomorrow, let’s see…