Uiua

This turned out to be reasonably easy in Uiua, though this solution relies on macros which maybe slow it down.

(edit: removing one macro sped it up quite a bit)

(edit2: Letting Uiua build up an n-dimensional array turned out to be the solution, though sadly my mind only works in 3 dimensions. Now runs against the live data in around 0.3 seconds.)

Try it here

Data   ← ⊜(□⊜⋕⊸(¬∈": "))⊸≠@\n "190: 10 19\n3267: 81 40 27\n83: 17 5\n156: 15 6\n7290: 6 8 6 15\n161011: 16 10 13\n192: 17 8 14\n21037: 9 7 18 13\n292: 11 6 16 20"
Calib! ← ≡◇⊢▽⊸≡◇(∈♭/[^0]:°⊂) # Calibration targets which can be constructed from their values.
&p/+Calib!⊃(+|×)Data
&p/+Calib!⊃(+|×|+×ⁿ:10+1⌊ₙ₁₀,)Data

Haskell

import Control.Arrow
import Data.Char
import Text.ParserCombinators.ReadP

numP = read <$> munch1 isDigit
parse = endBy ((,) <$> (numP <* string ": ") <*> sepBy numP (char ' ')) (char '\n')

valid n [m] = m == n
valid n (x : xs) = n > 0 && valid (n - x) xs || (n `mod` x) == 0 && valid (n `div` x) xs

part1 = sum . fmap fst . filter (uncurry valid . second reverse)

concatNum r = (+r) . (* 10 ^ digits r)
    where
        digits = succ . floor . logBase 10 . fromIntegral

allPossible [n] = [n]
allPossible (x:xs) = ((x+) <$> rest) ++ ((x*) <$> rest) ++ (concatNum x <$> rest)
    where
        rest = allPossible xs

part2 = sum . fmap fst . filter (uncurry elem . second (allPossible . reverse))

main = getContents >>= print . (part1 &&& part2) . fst . last . readP_to_S parse

Haskell

A surprisingly gentle one for the weekend! Avoiding string operations for concatenate got the runtime down below one second on my machine.

import Control.Arrow
import Control.Monad
import Data.List
import Data.Maybe

readInput :: String -> [(Int, [Int])]
readInput = lines >>> map (break (== ':') >>> (read *** map read . words . tail))

equatable :: [Int -> Int -> Int] -> (Int, [Int]) -> Bool
equatable ops (x, y : ys) = elem x $ foldM apply y ys
  where
    apply a y = (\op -> a `op` y) <$> ops

concatenate :: Int -> Int -> Int
concatenate x y = x * mag y + y
  where
    mag z = fromJust $ find (> z) $ iterate (* 10) 10

main = do
  input <- readInput <$> readFile "input07"
  mapM_
    (print . sum . map fst . (`filter` input) . equatable)
    [ [(+), (*)],
      [(+), (*), concatenate]
    ]

Python

It is a tree search

def parse_input(path):

  with path.open("r") as fp:
    lines = fp.read().splitlines()

  roots = [int(line.split(':')[0]) for line in lines]
  node_lists = [[int(x)  for x in line.split(':')[1][1:].split(' ')] for line in lines]

  return roots, node_lists

def construct_tree(root, nodes, include_concat):

  levels = [[] for _ in range(len(nodes)+1)]
  levels[0] = [(str(root), "")]
  # level nodes are tuples of the form (val, operation) where both are str
  # val can be numerical or empty string
  # operation can be *, +, || or empty string

  for indl, level in enumerate(levels[1:], start=1):

    node = nodes[indl-1]

    for elem in levels[indl-1]:

      if elem[0]=='':
        continue

      if elem[0][-len(str(node)):] == str(node) and include_concat:
        levels[indl].append((elem[0][:-len(str(node))], "||"))
      if (a:=int(elem[0]))%(b:=int(node))==0:
        levels[indl].append((str(int(a/b)), '*'))
      if (a:=int(elem[0])) - (b:=int(node))>0:
        levels[indl].append((str(a - b), "+"))

  return levels[-1]

def solve_problem(file_name, include_concat):

  roots, node_lists = parse_input(Path(cwd, file_name))
  valid_roots = []

  for root, nodes in zip(roots, node_lists):

    top = construct_tree(root, nodes[::-1], include_concat)

    if any((x[0]=='1' and x[1]=='*') or (x[0]=='0' and x[1]=='+') or
           (x[0]=='' and x[1]=='||') for x in top):

      valid_roots.append(root)

  return sum(valid_roots)

Haskell

I’m not very proud, I copied my code for part two.

import Control.Arrow hiding (first, second)

import qualified Data.List as List
import qualified Data.Char as Char

parseLine l = (n, os)
        where
                n = read . takeWhile (Char.isDigit) $ l
                os = map read . drop 1 . words $ l

parse :: String -> [(Int, [Int])]
parse s = map parseLine . takeWhile (/= "") . lines $ s

insertOperators target (r:rs) = any (target ==) (insertOperators' r rs)
insertOperators' :: Int -> [Int] -> [Int]
insertOperators' acc []     = [acc]
insertOperators' acc (r:rs) = insertOperators' (acc+r) rs ++ insertOperators' (acc*r) rs

insertOperators2 target (r:rs) = any (target ==) (insertOperators2' r rs)
insertOperators2' :: Int -> [Int] -> [Int]
insertOperators2' acc []     = [acc]
insertOperators2' acc (r:rs) = insertOperators2' (acc+r) rs ++ insertOperators2' (acc*r) rs ++ insertOperators2' concatN rs
        where
                concatN = read (show acc ++ show r)

part1 ls = filter (uncurry insertOperators)
        >>> map fst
        >>> sum
        $ ls
part2 ls = filter (uncurry insertOperators2)
        >>> map fst
        >>> sum
        $ ls

main = getContents >>= print . (part1 &&& part2) . parse

C

Big integers and overflow checking, what else is there to say 😅​

#include "common.h"

/* returns 1 on sucess, 0 on overflow */
static int
concat(uint64_t a, uint64_t b, uint64_t *out)
{
	uint64_t mul;

	for (mul=1; mul<=b; mul*=10) ;

	return 
	    !__builtin_mul_overflow( mul, a, out) &&
	    !__builtin_add_overflow(*out, b, out);
}

static int
recur(uint64_t expect, uint64_t acc, uint64_t arr[], int n, int p2)
{
	uint64_t imm;

	return
	    n < 1 ? acc == expect :
	    acc >= expect ? 0 :
	    recur(expect, acc + arr[0], arr+1, n-1, p2) ||
	    recur(expect, acc * arr[0], arr+1, n-1, p2) ||
	    (p2 && concat(acc, arr[0], &imm)
	        && recur(expect, imm, arr+1, n-1, p2));
}

int
main(int argc, char **argv)
{
	char buf[128], *tok, *rest;
	uint64_t p1=0, p2=0, arr[32], expect;
	int n;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while ((rest = fgets(buf, sizeof(buf), stdin))) {
		assert(strchr(buf, '\n'));
		expect = atoll(strsep(&rest, ":"));

		for (n=0; (tok = strsep(&rest, " ")); n++) {
			assert(n < (int)LEN(arr));
			arr[n] = atoll(tok);
		}

		p1 += recur(expect, 0, arr, n, 0) * expect;
		p2 += recur(expect, 0, arr, n, 1) * expect;
	}

	printf("07: %"PRIu64" %"PRIu64"\n", p1, p2);
	return 0;
}

https://github.com/sjmulder/aoc/blob/master/2024/c/day07.c

Factor

TUPLE: equation value numbers ;
C: <equation> equation

: get-input ( -- equations )
  "vocab:aoc-2024/07/input.txt" utf8 file-lines [
    split-words unclip but-last string>number
    swap [ string>number ] map <equation>
  ] map ;

: possible-quotations ( funcs numbers -- quots )
  dup length 1 -
  swapd all-selections
  [ unclip swap ] dip
  [ zip concat ] with map
  swap '[ _ prefix >quotation ] map ;

: possibly-true? ( funcs equation -- ? )
  [ numbers>> possible-quotations ] [ value>> ] bi
  '[ call( -- n ) _ = ] any? ;

: solve ( funcs -- n )
  get-input
  [ possibly-true? ] with filter
  [ value>> ] map-sum ;

: part1 ( -- n )
  { + * } solve ;

: _|| ( m n -- mn )
  [ number>string ] bi@ append string>number ;

: part2 ( -- n )
  { + * _|| } solve ;

Uiua

Credits to @mykl@lemmy.world for the approach of using reduce and also how to split the input by multiple characters.
I can happily say that I learned quite a bit today, even though the first part made me frustrated enough that I went searching for other approaches ^^

Part two just needed a simple modification. Changing how the input is parsed and passed to the adapted function took longer than changing the function itself actually.

Run with example input here

PartOne ← (
  &rs ∞ &fo "input-7.txt"
  ⊜□≠@\n.
  ≡◇(⊜□≠@:.)
  ≡⍜⊡⋕0
  ≡⍜(°□⊡1)(⊜⋕≠@ .)
  ⟜(⊡0⍉)

  # own attempt, produces a too low number
  # ≡(:∩°□°⊟
  #   ⍣(⍤.◡⍣(1⍤.(≤/×)⍤.(≥/+),,)0
  #     ⊙¤⋯⇡ⁿ:2-1⊸⧻
  #     ⊞(⍥(⟜⍜(⊙(↙2))(⨬+×⊙°⊟⊡0)
  #         ↘1
  #       )⧻.
  #       ⍤.=0⧻.
  #     )
  #     ∈♭◌
  #   )0)

  # reduce approach found on the programming.dev AoC community by mykl@lemmy.world
  ≡(◇(∈/(◴♭[⊃(+|×)]))⊡0:°⊂)
  °□/+▽
)

PartTwo ← (
  &rs ∞ &fo "input-7.txt"
  ⊜(□⊜⋕¬∈": ".)≠@\n.
  ⟜≡◇⊢
  ≡◇(∈/(◴♭[≡⊃⊃(+|×|⋕$"__")]):°⊂)
  °□/+▽
)

&p "Day 7:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

TypeScript

I wrote my own iterator because I’m a big dummy. Also brute forced (~8s). Might be worth adding a cache to skip all the questions that have been computed / done.

import { AdventOfCodeSolutionFunction } from "./solutions";

function MakeCombination<T>(choices: Array<T>, state: Array<number>): Array<T> {
    return state.map((v) => choices[v]);
}

function MakeStateArray(length: number) {
    const newArray = [];
    while (length-- > 0)
        newArray.push(0);

    return newArray;
}

function IncrementState(state: Array<number>, max: number): [state: Array<number>, overflow: boolean] {
    state[0]++;
    for (let index = 0; index < state.length; index++) {
        if (state[index] == max) {
            state[index] = 0;

            if (index + 1 == state.length)
                return [state, true];

            state[index + 1]++;
        }
    }

    return [state, false];
}

function GenerateCombinations<T>(choices: Array<T>, length: number): Array<Array<T>> {
    const states = MakeStateArray(length);
    const combinations: Array<Array<T>> = [];

    let done = false
    while (!done) {
        combinations.push(MakeCombination(choices, states));
        done = IncrementState(states, choices.length)[1];
    }


    return combinations;
}

enum Op {
    MUL = "*",
    ADD = "+",
    CON = "|",
}

function ApplyOp(a: number, b: number, op: Op): number {
    switch (op) {
        case Op.MUL:
            return a * b;
        case Op.ADD:
            return a + b;
        case Op.CON:
            return Number(`${a}${b}`);
    }
}

function ApplyOperatorsToNumbers(numbers: Array<number>, ops: Array<Op>): number {
    let prev = ApplyOp(numbers[0], numbers[1], ops[0]);

    for (let index = 2; index < numbers.length; index++) {
        prev = ApplyOp(prev, numbers[index], ops[index - 1])
    }

    return prev;
}

export const solution_7: AdventOfCodeSolutionFunction = (input) => {
    const numbers = // [{target: 123, numbers: [1, 2, 3, ...]}, ...]
        input.split("\n")
            .map(
                (v) => v.trim()
                    .split(":")
                    .map(v => v.trim().split(" ").map(v => Number(v)))
            ).map(
                (v) => {
                    return { target: v[0][0], numbers: v[1] }
                }
            );

    let part_1 = 0;
    let part_2 = 0;

    for (let index = 0; index < numbers.length; index++) {
        const target = numbers[index].target;
        const numbs = numbers[index].numbers;

        // GenerateCombinations(["+", "*"], 2) => [["+", "+"], ["+", "*"], ["*", "+"], ["*", "*"]]
        const combinations = GenerateCombinations([Op.ADD, Op.MUL], numbs.length - 1); 

        // part 1 calculations
        for (let combinationIndex = 0; combinationIndex < combinations.length; combinationIndex++) {
            const combination = combinations[combinationIndex];
            const result = ApplyOperatorsToNumbers(numbs, combination);
            if (result == target) {
                part_1 += result;
                break;
            }
        }

        const combinations2 = GenerateCombinations([Op.ADD, Op.MUL, Op.CON], numbs.length - 1);

        // part 2 calculations
        for (let combinationIndex = 0; combinationIndex < combinations2.length; combinationIndex++) {
            const combination = combinations2[combinationIndex];
            const result = ApplyOperatorsToNumbers(numbs, combination);
            if (result == target) {
                part_2 += result;
                break;
            }
        }

    }

    return {
        part_1,
        part_2,
    }
}

C#

public class Day07 : Solver
{
  private ImmutableList<(long, ImmutableList<long>)> equations;

  public void Presolve(string input) {
    equations = input.Trim().Split("\n")
      .Select(line => line.Split(": "))
      .Select(split => (long.Parse(split[0]), split[1].Split(" ").Select(long.Parse).ToImmutableList()))
      .ToImmutableList();
  }

  private bool TrySolveWithConcat(long lhs, long head, ImmutableList<long> tail) {
    var lhs_string = lhs.ToString();
    var head_string = head.ToString();
    return lhs_string.Length > head_string.Length &&
      lhs_string.EndsWith(head_string) &&
      SolveEquation(long.Parse(lhs_string.Substring(0, lhs_string.Length - head_string.Length)), tail, true);
  }

  private bool SolveEquation(long lhs, ImmutableList<long> rhs, bool with_concat = false) {
    if (rhs.Count == 1) return lhs == rhs[0];
    long head = rhs[rhs.Count - 1];
    var tail = rhs.GetRange(0, rhs.Count - 1);
    return (SolveEquation(lhs - head, tail, with_concat))
      || (lhs % head == 0) && SolveEquation(lhs / head, tail, with_concat)
      || with_concat && TrySolveWithConcat(lhs, head, tail);
  }

  public string SolveFirst() => equations
    .Where(eq => SolveEquation(eq.Item1, eq.Item2))
    .Select(eq => eq.Item1)
    .Sum().ToString();
  public string SolveSecond() => equations
    .Where(eq => SolveEquation(eq.Item1, eq.Item2, true))
    .Select(eq => eq.Item1)
    .Sum().ToString();
}

python

45s on my machine for first shot, trying to break my will to brute force 😅. I’ll try improving on it in a bit after I smoke another bowl and grab another drink.

import itertools
import re
import aoc

def ltr(e):
    r = int(e[0])
    for i in range(1, len(e), 2):
        o = e[i]
        n = int(e[i + 1])
        if o == '+':
            r += n
        elif o == '*':
            r *= n
        elif o == '||':
            r = int(f"{r}{n}")
    return r

def pl(l, os):
    d = [int(x) for x in re.findall(r'\d+', l)]
    t, ns = d[0], d[1:]
    ops = list(itertools.product(os, repeat=len(ns) - 1))
    for o in ops:
        e = str(ns[0])
        for i, op in enumerate(o):
            e += f" {op} {ns[i + 1]}"
        r = ltr(e.split())
        if r == t:
            return r
    return 0

def one():
    lines = aoc.get_lines(7)
    acc = 0
    for l in lines:
        acc += pl(l, ['+', '*'])
    print(acc)

def two():
    lines = aoc.get_lines(7)
    acc = 0
    for l in lines:
        acc += pl(l, ['+', '*', '||'])
    print(acc)

one()
two()

Java

Today was pretty easy one but for some reason I spent like 20 minutes overthinking part 2 when all it needed was one new else if. I initially through the concatenation operator would take precedence even tho it clearly says “All operators are still evaluated left-to-right” in the instructions…

I’m sure there are optimizations to do but using parallelStreams it only takes around 300ms total on my machine so there’s no point really

import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
import java.util.List;

public class Day7 {
    public static void main(final String[] _args) throws IOException {
        final List<Equation> equations = Files.readAllLines(Path.of("2024\\07\\input.txt"), StandardCharsets.UTF_8).stream()
            .map(line -> line.split(":\\s"))
            .map(line -> new Equation(
                    Long.parseLong(line[0]),
                    Arrays.stream(line[1].split("\\s"))
                        .map(Integer::parseInt)
                        .toArray(Integer[]::new)
                )
            ).toList();

        final char[] part1Operators = {'+', '*'};
        System.out.println("Part 1: " + equations.parallelStream()
            .mapToLong(equation -> getResultIfPossible(equation, part1Operators))
            .sum()
        );

        final char[] part2Operators = {'+', '*', '|'};
        System.out.println("Part 2: " + equations.parallelStream()
            .mapToLong(equation -> getResultIfPossible(equation, part2Operators))
            .sum()
        );
    }

    private static Long getResultIfPossible(final Equation equation, final char[] operators) {
        final var permutations = Math.pow(operators.length, equation.values.length - 1);
        for (int i = 0; i < permutations; i++) {
            long result = equation.values[0];
            int count = i;

            for (int j = 0; j < equation.values.length - 1; j++) {
                // If the result is already larger than the expected one, we can short circuit here to save some time
                if (result > equation.result) {
                    break;
                }

                final char operator = operators[count % operators.length];
                count /= operators.length;

                if (operator == '+') { result += equation.values[j + 1]; }
                else if (operator == '*') { result *= equation.values[j + 1]; }
                else if (operator == '|') { result = Long.parseLong(String.valueOf(result) + String.valueOf(equation.values[j + 1])); }
                else {
                    throw new RuntimeException("Unsupported operator " + operator);
                }
            }

            if (result == equation.result) {
                return result;
            }
        }

        return 0L;
    }

    private static record Equation(long result, Integer[] values) {}
}

Made a couple of attempts to munge the input data into some kind of binary search tree, lost some time to that, then threw my hands into the air and did a more naïve sort-of breadth-first search instead. Which turned out to be better for part 2 anyway.
Also, maths. Runs in just over a hundred milliseconds when using AsParallel, around half a second without.

List<(long, int[])> data = new List<(long, int[])>();

public void Input(IEnumerable<string> lines)
{
  foreach (var line in lines)
  {
    var parts = line.Split(':', StringSplitOptions.TrimEntries);

    data.Add((long.Parse(parts.First()), parts.Last().Split(' ').Select(int.Parse).ToArray()));
  }
}

public void Part1()
{
  var correct = data.Where(kv => CalcPart(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();

  Console.WriteLine($"Correct: {correct}");
}
public void Part2()
{
  var correct = data.AsParallel().Where(kv => CalcPart2(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();

  Console.WriteLine($"Correct: {correct}");
}

public bool CalcPart(long res, Span<int> num, long carried = 0)
{
  var next = num[0];
  if (num.Length == 1)
    return res == carried + next || res == carried * next;
  return CalcPart(res, num.Slice(1), carried + next) || CalcPart(res, num.Slice(1), carried * next);
}

public bool CalcPart2(long res, Span<int> num, long carried = 0)
{
  var next = num[0];
  // Get the 10 logarithm for the next number, expand the carried value by 10^<next 10log + 1>, add the two together
  // For 123 || 45
  // 45 ⇒ 10log(45) + 1 == 2
  // 123 * 10^2 + 45 == 12345
  long combined = carried * (long)Math.Pow(10, Math.Floor(Math.Log10(next) + 1)) + next;
  if (num.Length == 1)
    return res == carried + next || res == carried * next || res == combined;
  return CalcPart2(res, num.Slice(1), carried + next) || CalcPart2(res, num.Slice(1), carried * next) || CalcPart2(res, num.Slice(1), combined);
}

Nim

Bruteforce, my beloved.

Wasted too much time on part 2 trying to make combinations iterator (it was very slow). In the end solved both parts with 3^n and toTernary.

Runtime: 1.5s

func digits(n: int): int =
  result = 1; var n = n
  while (n = n div 10; n) > 0: inc result

func concat(a: var int, b: int) =
  a = a * (10 ^ b.digits) + b

func toTernary(n: int, len: int): seq[int] =
  result = newSeq[int](len)
  if n == 0: return
  var n = n
  for i in 0..<len:
    result[i] = n mod 3
    n = n div 3

proc solve(input: string): AOCSolution[int, int] =
  for line in input.splitLines():
    let parts = line.split({':',' '})
    let res = parts[0].parseInt
    var values: seq[int]
    for i in 2..parts.high:
      values.add parts[i].parseInt

    let opsCount = values.len - 1
    var solvable = (p1: false, p2: false)
    for s in 0 ..< 3^opsCount:
      var sum = values[0]
      let ternary = s.toTernary(opsCount)
      for i, c in ternary:
        case c
        of 0: sum *= values[i+1]
        of 1: sum += values[i+1]
        of 2: sum.concat values[i+1]
        else: raiseAssert"!!"
      if sum == res:
        if ternary.count(2) == 0:
          solvable.p1 = true
        solvable.p2 = true
        if solvable == (true, true): break
    if solvable.p1: result.part1 += res
    if solvable.p2: result.part2 += res

Codeberg repo

J

Didn’t try to make it clever at all, so it’s fairly slow (minutes, not seconds). Maybe rewriting foldl_ops in terms of destructive array update would improve matters, but the biggest problem is that I don’t skip unnecessary calculations (because we’ve already found a match or already reached too big a number). This is concise and follows clearly from the definitions, however.

data_file_name =: '7.data
lines =: cutopen fread data_file_name
NB. parse_line yields a boxed vector of length 2, target ; operands
NB. &. is "under": u &. v is v^:_1 @: u @: v with right rank of v
parse_line =: monad : '(". &. >) (>y) ({.~ ; (}.~ >:)) '':'' i.~ >y'
NB. m foldl_ops n left folds n by the string of binary operators named by m,
NB. as indices into the global operators, the leftmost element of m naming
NB. an operator between the leftmost two elements of n. #m must be #n - 1.
foldl_ops =: dyad define
   if. 1 >: # y do. {. y else.
      (}. x) foldl_ops (((operators @. ({. x))/ 2 {. y) , 2 }. y)
   end.
)
NB. b digit_strings n enumerates i.b^n as right justified digit strings
digit_strings =: dyad : '(y # x) #:"1 0 i. x ^ y'
feasible =: dyad define
   operators =: x  NB. global
   'target operands' =. y
   +./ target = ((# operators) digit_strings (<: # operands)) foldl_ops"1 operands
)
compute =: monad : '+/ ((> @: {.) * (y & feasible))"1 parse_line"0 lines'
result1 =: compute +`*

concat =: , &.: (10 & #.^:_1)
result2 =: compute +`*`concat