#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;
}

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 ;

import argparse
import os


class Calibrations:
    def __init__(self, target, operators) -> None:
        self.operators = operators
        self.target = target
        self.target_found = False

    def do_math(self, numbers, operation) -> int:
        if operation == "+":
            return numbers[0] + numbers[1]
        elif operation == "*":
            return numbers[0] * numbers[1]
        elif operation == "||":
            return int(str(numbers[0]) + str(numbers[1]))

    def all_options(self, numbers, last) -> int:
        if len(numbers) < 1:
            return last
        for j in self.operators:
            # If we found our target already, abort
            # If the last value is greater than the target, abort
            if self.target_found or last > self.target:
                return
            total = self.all_options(
                numbers[1:], self.do_math((last, numbers[0]), j)
            )
            if total == self.target:
                self.target_found = True

    def process_line(self, line) -> int:
        numbers = [int(x) for x in line.split(":")[1].strip().split()]
        self.all_options(numbers[1:], numbers[0])
        if self.target_found:
            return self.target
        return 0


def main() -> None:
    path = os.path.dirname(os.path.abspath(__file__))
    parser = argparse.ArgumentParser(description="Bridge Repair")
    parser.add_argument("filename", help="Path to the input file")
    args = parser.parse_args()
    sum_of_valid = [0, 0]
    with open(f"{path}/{args.filename}", "r") as f:
        for line in f:
            line = line.strip()
            target = int(line.split(":")[0])
            for idx, ops in enumerate([["+", "*"], ["+", "*", "||"]]):
                c = Calibrations(target, ops)
                found = c.process_line(line)
                sum_of_valid[idx] += found
                if found:
                    break
    for i in range(0, 2):
        part = i + 1
        print(
            "The sum of valid calibrations for Part "
            + f"{part} is {sum(sum_of_valid[:part])}"
        )


if __name__ == "__main__":
    main()

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,
    }
}

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);
}

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) {}
}

(defstruct calibration result inputs)

(defun p1-process-line (line)
  (let ((parts (str:words line)))
    (make-calibration :result (parse-integer (car parts) :junk-allowed t)
                      :inputs (mapcar #'parse-integer (cdr parts)))))

(defun apply-opperators (c opps)
  (let ((accum (car (calibration-inputs c))))
  (loop for o in opps
        for v in (cdr (calibration-inputs c))
        until (> accum (calibration-result c))
        if (eql o 'ADD)
          do (setf accum (+ accum v))
        else if (eql o 'MUL)
          do (setf accum (* accum v))
        else
          do (setf accum (+ v (* accum (expt 10 (1+ (floor (log v 10)))))))
        finally (return accum)
        )))

(defun generate-operators (item-count)
  (labels ((g-rec (c results)
             (if (< c 1)
                 results
                 (g-rec (1- c) (loop for r in results
                                     collect (cons 'ADD r)
                                     collect (cons 'MUL r))))))
    (g-rec (1- item-count) '((ADD) (MUL)))))

(defun generate-ops-hash (c gen-ops)
  (let ((h (make-hash-table)))
    (dotimes (x c)
      (setf (gethash (+ 2 x) h) (funcall gen-ops (+ 1 x))))
    h))

(defun validate-calibration (c ops-h)
  (let ((r (calibration-result c))
        (ops (gethash (length (calibration-inputs c)) ops-h)))
    (loop for o in ops
          for v = (apply-opperators c o)
          when (= v r)
            return t)))

(defun run-p1 (file) 
  (let ((calibrations  (read-file file #'p1-process-line))
        (ops (generate-ops-hash 13 #'generate-operators)))
    (loop for c in calibrations
          when (validate-calibration c ops)
            sum (calibration-result c))))

(defun generate-operators-p2 (item-count)
  (labels ((g-rec (c results)
             (if (< c 1)
                 results
                 (g-rec (1- c) (loop for r in results
                                     collect (cons 'ADD r)
                                     collect (cons 'MUL r)
                                     collect (cons 'CAT r))))))
    (g-rec (1- item-count) '((ADD) (MUL) (CAT)))))

(defun run-p2 (file) 
  (let ((calibrations  (read-file file #'p1-process-line))
        (ops (generate-ops-hash 13 #'generate-operators-p2)))
    (loop for c in calibrations
          when (validate-calibration c ops)
            sum (calibration-result c))))