Day 7: Bridge Repair

Class {
	#name : 'Day7Solver',
	#superclass : 'AoCSolver',
	#instVars : [
		'equations'
	],
	#category : 'AoCDay7',
	#package : 'AoCDay7'
}

Day7Solver >> parseRawData [
	equations := rawData lines collect: [ :eqString | Day7Equation newFromString: eqString ]
]

Day7Solver >> solvePart1 [
	^ ((equations select: [ :eq | eq canBeSolved: { #+. #* } ]) collect: #testValue) sum
]

Day7Solver >> solvePart2 [
	^ ((equations select: [ :eq | eq canBeSolved: { #+. #*. #|| } ]) collect: #testValue) sum
]

Class {
	#name : 'Day7Equation',
	#superclass : 'Object',
	#instVars : [
		'testValue',
		'terms'
	],
	#category : 'AoCDay7',
	#package : 'AoCDay7'
}

Day7Equation class >> newFromString: aString [ 
	| parts terms |
	parts := aString splitOn: ': '.
	terms := (parts second splitOn: ' ') collect: #asInteger.
	^ self new testValue: parts first asInteger; terms: terms
]

Day7Equation >> canBeSolved: operators [
	| totals |
	totals := { terms first }.
	terms allButFirstDo: [ :term |
		totals := (operators collect: [ :op |
			           totals collect: [ :prev | prev perform: op with: term ] ])
			          flattened select: [ :x | x <= testValue ] ].
	^ totals includes: testValue
]

Integer >> || anInteger
	^ (self asString , anInteger asString) asInteger

#! /usr/bin/env racket
#lang racket

(require rackunit)

(define (possible? target equation oprs)
  (define (helper target cur equation oprs)
    (cond
      ;; we found a match
      [(and (eq? cur target) (empty? equation)) #t]
      ;; we reached the end of the equation and cur != target
      [(empty? equation) #f]
      ;; we went past the target, no point to keep trying this path
      [(> cur target) #f]
      [else (for/or ([opr (in-list oprs)])
              (let ([res (opr cur (first equation))])
                (helper target res (cdr equation) oprs)))]))
  (cond
    ;; can't car or cdr on '()
    [(empty? equation) #f]
    [else (helper target (car equation) (cdr equation) oprs)]))

;; parse input port to a list of '(target equation)s
(define (parse in-port)
  (for/list ([line (in-lines in-port)])
    (let* ([split (string-split line ": ")]
           [target (string->number (first split))]
           [equation-strings (string-split (second split) " ")]
           [equation (map string->number equation-strings)])
      (list target equation))))

;; concatenation operator for part 2
(define (|| l r)
  (string->number (string-append (number->string l)
                                 (number->string r))))

;; run with a given list of operators
(define (run parsed oprs)
  (for/sum ([line (in-list parsed)])
    (let* ([target (first line)]
           [equation (second line)])
      (cond
        [(possible? target equation oprs) target]
        [else 0]))))

(define (day07/run-part01 parsed)
  (run parsed (list + *)))
(define (day07/run-part02 parsed)
  (run parsed (list + * ||)))

(check-equal? (day07/run-part01 (parse (open-input-file "examples/day07.in"))) 3749 "Test part 1")
(check-equal? (day07/run-part02 (parse (open-input-file "examples/day07.in"))) 11387 "Test part 2")

(let* ([in-port (open-input-file "inputs/day07.in")]
       [parsed (parse in-port)]
       [part1 (day07/run-part01 parsed)]
       [part2 (day07/run-part02 parsed)])
  (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))

import "utils" as utils;

let input = utils::get_input(7, false).split("\n").map(|line| {
    let parts = line.split(":");
    let solution = parts[0].parse_int();
    parts[1].trim();
    let values = parts[1].split(" ").map(|v| v.parse_int());
    #{solution: solution, values: values}
});

let total = 0;
for equation in input {
    let values = equation.values;
    let op_sets = ["+", "*"].permutations_with_replacement(values.len()-1);
    for ops in op_sets {
        let value = values[0];
        for (op, i) in ops {
            switch op {
                "+" => value += values[i + 1],
                "*" => value *= values[i + 1],
            }
        }
        if value == equation.solution {
            total += value;
            break;
        }
    }
}

print(`part 1: ${total}`);

let total = 0;
for equation in input {
    let values = equation.values;
    let op_sets = ["+", "*", "||"].permutations_with_replacement(values.len()-1);
    for ops in op_sets {
        let value = values[0];
        for (op, i) in ops {
            switch op {
                "+" => value += values[i + 1],
                "*" => value *= values[i + 1],
                "||" => value = `${value}${values[i + 1]}`.parse_int(),
            }
        }
        if value == equation.solution {
            total += value;
            break;
        }
    }
}

print(`part 2: ${total}`);

Simple recursive solution. I actually accidentally misinterpreted it initially and thought I was supposed to find the number of possibilities for each equation, but it runs quick enough that doing so doesn't really have any downside.

#!/usr/bin/awk -f
function check(a, ptr, len, val, test) {
	if (ptr > len)
		return (val == test)
	else
		return check(a, ptr+1, len, val+a[ptr], test) + check(a, ptr+1, len, val*a[ptr], test)
}

BEGIN { total = 0 }

{
	sub(/:/, "")

	for (i = 1; i <= NF; ++i)
		a[i] = $i

	if (check(a, 3, NF, a[2], a[1]) > 0)
		total += a[1]
}

END { print(total) }

This one was very simple, I just copied another function call into the chain on line 6 and deleted the operator (which automatically leads to concatenation in AWK). I finally felt the consequences of recursively finding all possible solutions here, but it still completes within a few seconds so I just let it be.

#!/usr/bin/awk -f
function check(a, ptr, len, val, test) {
	if (ptr > len)
		return (val == test)
	else
		return check(a, ptr+1, len, val+a[ptr], test) + check(a, ptr+1, len, val*a[ptr], test) + check(a, ptr+1, len, val a[ptr], test)

}

BEGIN { total = 0 }

{
	sub(/:/, "")

	for (i = 1; i <= NF; ++i)
		a[i] = $i

	if (check(a, 3, NF, a[2], a[1]) > 0)
		total += a[1]
}

END { print(total) }

/* Advent of Code 2024
 * Day 07: Bridge Repair
 */

#import "Basic";
#import "File";
#import "String";

Operator :: enum {
    ADD;
    MULTIPLY;
    CONCATENATE;
}

// Finds all permutations of an arbitrary length made up of elements from a
// given array. Repeats are allowed.
find_permutations :: (elements: [] $T, length: int) -> [][..] T {
    permutations: [..][..] T;
    queue: [..][..] T;

    for elements {
        permutation: [..] T;
        array_add(*permutation, it);
        array_add(*queue, permutation);
    }

    while queue.count {
        permutation := pop(*queue);
        if permutation.count == length {
            array_add(*permutations, permutation);
            continue;
        }

        for elements {
            new_permutation: [..] T;
            array_copy(*new_permutation, permutation);
            array_add(*new_permutation, it);
            array_add(*queue, new_permutation);
        }
    }

    return permutations;
}

is_equation_possible :: (
    required_result: int,
    numbers: [] int,
    operators: [] Operator
) -> bool {
    // Not much of an ingenious solution here. There is probably a faster way to
    // solve this than bruteforcing (again...), but this works well enough.
    for operators: find_permutations(operators, numbers.count - 1) {
        result := numbers[0];
        for 1..numbers.count - 1 {
            if operators[it - 1] == {
                case .ADD; result += numbers[it];
                case .MULTIPLY; result *= numbers[it];

                case .CONCATENATE;
                    power := 10;
                    next_number := numbers[it];

                    while power <= next_number {
                        power *= 10;
                    }

                    result *= power;
                    result += next_number;
            }
        }

        array_free(operators);

        if result == required_result {
            return true;
        }
    }

    return false;
}

main :: () {
    input, success := read_entire_file("inputs/day_07.txt");
    assert(success);

    total_part_1 := 0;
    total_part_2 := 0;

    for split(input, "\n") {
        if it == "" {
            continue;
        }

        parts := split(it, ": ");
        required_result := string_to_int(parts[0]);

        numbers: [..] int;
        for split(parts[1], " ") {
            array_add(*numbers, string_to_int(it));
        }

        if is_equation_possible(required_result, numbers, .[.ADD, .MULTIPLY]) {
            total_part_1 += required_result;
        }

        if is_equation_possible(
            required_result,
            numbers,
            .[.ADD, .MULTIPLY, .CONCATENATE]
        ) {
            total_part_2 += required_result;
        }
    }

    print("Part 1: %\nPart 2: %\n", total_part_1, total_part_2);
}

This one took about an hour to solve, twice as long as yesterday's, but bone-headed mistakes are gonna happen. I just have to accept that.

After the Hot Springs puzzle last year, I kind of assumed you had to memoize the recursive equation solve in part 2, but adding memoization added so much overhead that the runtime was 10x what it is without it. Now part 2 runs in about 0.8 seconds.

pub fn part1(input: &PuzzleInput) -> String {
    input
        .equations
        .iter()
        .map(|(target, numbers)| {
            let mut n: Vec<i64> = numbers.clone();
            let first = n.remove(0);

            let soln = solve_equation(first, *target, n);

            if soln {
                *target
            } else {
                0
            }
        })
        .sum::<i64>()
        .to_string()
}

fn solve_equation(current: i64, target: i64, remainder: Vec<i64>) -> bool {
    if current == target && remainder.is_empty() {
        return true;
    }

    if remainder.is_empty() {
        return false;
    }

    let next = remainder.first().unwrap();
    let next_remainder = remainder[1..].to_vec();

    solve_equation(current + next, target, next_remainder.clone())
        || solve_equation(current * next, target, next_remainder)
}

fn solve_equation(current: i64, target: i64, remainder: Vec<i64>) -> bool {
    if current == target && remainder.is_empty() {
        return true;
    }

    if remainder.is_empty() {
        return false;
    }

    let mut next_remainder = remainder.clone();
    let next = next_remainder.pop().unwrap();

    if solve_equation(current + next, target, next_remainder.clone())
        || solve_equation(current * next, target, next_remainder.clone())
    {
        return true;
    }

    let left = current.to_string();
    let right = next.to_string();
    let concated = left + &right;
    let concated_num = concated.parse::<i64>().unwrap();

    solve_equation(concated_num, target, next_remainder)
}

Somewhat out of laziness, I generated the op permutations from an incrementing integer.

E.g. On a line with n numbers, I would need n-1 operators.

For part 1, this would require testing up to 2^(n-1) op combos, so I used an integer starting at 0 and incrementing to that number. When it was say, 6, that would translate to binary 0 1 1, and then I'd translate each digit to an operator: + * *

Part 2 was almost the same, except the combos were 3^(n-1) and I converted the integer to ternary: 6 -> 0 2 0 -> + || +.

defmodule AdventOfCode.Solution.Year2024.Day07 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input) do
    for line <- String.split(input, "\n", trim: true) do
      [target, ns] = String.split(line, ":")
      {String.to_integer(target), for(n <- String.split(ns), do: String.to_integer(n))}
    end
  end

  def part1(equations), do: sum_solvable(equations, 2)
  def part2(equations), do: sum_solvable(equations, 3)

  defp sum_solvable(eqs, n_ops) do
    for {target, _ns} = eq <- eqs, solvable?(eq, n_ops), reduce: 0, do: (acc -> acc + target)
  end

  def solvable?({target, ns}, n_ops) do
    ns
    |> stream_calculations(n_ops)
    |> Enum.any?(&(&1 == target))
  end

  def stream_calculations([], _n_ops), do: []
  def stream_calculations([n], _n_ops), do: [n]

  def stream_calculations(ns, n_ops) do
    upper_bound = n_ops ** (length(ns) - 1)

    Stream.unfold(0, fn
      ^upper_bound -> nil
      op_combo -> {apply_ops(op_combo, ns, n_ops), op_combo + 1}
    end)
  end

  defp apply_ops(op_combo, ns, n_ops) do
    op_combo
    |> Integer.digits(n_ops)
    |> zero_pad(length(ns))
    |> Enum.zip_reduce(ns, 0, &eval_op/3)
  end

  defp zero_pad(l, n), do: List.duplicate(0, max(0, n - length(l))) ++ l

  defp eval_op(0, b, a), do: a + b
  defp eval_op(1, b, a), do: a * b
  defp eval_op(2, b, a), do: a * 10 ** (1 + trunc(:math.log10(b))) + b
end

Is there any way to optimize this? (Besides the obvious parallelization by line)
It almost seems like a cryptography problem.

Running the whole thing in one process:

Name             ips        average  deviation         median         99th %
Parse         302.82        3.30 ms     ±2.25%        3.28 ms        3.53 ms
Part 1         34.66       28.85 ms     ±5.40%       28.69 ms       37.07 ms
Part 2          0.56     1777.75 ms     ±0.59%     1783.57 ms     1783.96 ms

Comparison: 
Parse         302.82
Part 1         34.66 - 8.74x slower +25.55 ms
Part 2          0.56 - 538.34x slower +1774.45 ms

After switching to a Task.async_stream call to check each line concurrently:

Name             ips        average  deviation         median         99th %
Part 1        105.77        9.45 ms     ±2.56%        9.45 ms       10.17 ms
Part 2          3.08      324.21 ms     ±2.38%      324.76 ms      333.83 ms

On the bright side, my intuition that this was a job for a recursive function was spot-on. I almost never use those (apart from coding challenges like AoC) and they tend to break my brain, so I expected to wrestle with the implementation for a while. I'm actually quite pleased that I nailed it right away! I must be getting the hang of these.

My function evaluates the first two operands in the list, and loops through the array of available operations to create permutations. (Originally this array included - and / but I had to sheepishly remove them when I realized they were out of scope.) For each permutation, the function calculates the result of that operation and calls itself with [result, ...rest] as the new list of operands. When the function sees that only one element is in that array, it accepts that as the final result for the current recursed permutation, and it compares that against the expected number.

Part 2 was the same logic, I just added a new concatenation operation. Thankfully my approach of representing the available operations as functions in an array was well suited for this, and I was able to complete it within a couple minutes.

type InputData = [number, number[]][];
type Operations = Array<(a: number, b: number) => number>;

function formatInput(input: string): InputData {
  return input
    .trim()
    .split('\n')
    .map(line => {
      const splitLine = line.split(': ') as [string, string];
      return [parseInt(splitLine[0], 10), splitLine[1].split(' ').map(operand => parseInt(operand, 10))];
    });
}

const part1Operations: Operations = [
  (a, b) => a + b, // add
  (a, b) => a * b, // multiply
];

const part2Operations: Operations = [
  ...part1Operations,
  (a, b) => Number(`${a}${b}`), // concatenate
];

const recursiveTestOperator = (remainingOperands: number[], expected: number, operations: Operations): boolean => {
  if (remainingOperands.length === 1) {
    return remainingOperands[0] === expected;
  }
  for (const operation of operations) {
    const [a, b, ...rest] = remainingOperands;
    if (recursiveTestOperator([operation(a, b), ...rest], expected, operations)) {
      return true;
    }
  }
  return false;
};

export function run(input: string): string[] {
  const data = formatInput(input);

  const totalValidEquations = (equations: InputData, operations: Operations): number => {
    let total = 0;
    for (const [testValue, operands] of equations) {
      if (recursiveTestOperator(operands, testValue, operations)) {
        total += testValue;
      }
    }
    return total;
  };

  return [`${totalValidEquations(data, part1Operations)}`, `${totalValidEquations(data, part2Operations)}`];
}