#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

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

(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))))

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

import { AdventOfCodeSolutionFunction } from "./solutions";

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

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

    return newArray;
}

function IncrementState(state: Array, max: number): [state: Array, 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(choices: Array, length: number): Array> {
    const states = MakeStateArray(length);
    const combinations: Array> = [];

    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, ops: Array): 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,
    }
}

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 kotlin.collections.any
import kotlin.math.pow

fun main() {
    fun part1(input: List): Long {
        val operations = setOf(CalibrationOperation.Plus, CalibrationOperation.Multiply)
        return generalizedSolution(input, operations)
    }

    fun part2(input: List): Long {
        val operations = setOf(CalibrationOperation.Plus, CalibrationOperation.Multiply, CalibrationOperation.Concat)
        return generalizedSolution(input, operations)
    }

    val testInput = readInput("Day07_test")
    check(part1(testInput) == 3749L)
    check(part2(testInput) == 11387L)

    val input = readInput("Day07")
    part1(input).println()
    part2(input).println()
}

fun parseInputDay7(input: List) = input.map {
    val calibrationResultAndInput = it.split(':')
    calibrationResultAndInput[0].toLong() to calibrationResultAndInput[1].split(' ').filter { it != "" }.map { it.toLong() }
}

fun generalizedSolution(input: List, operations: Set): Long {
    val parsedInput = parseInputDay7(input)
    val operationsPermutations = CalibrationOperation.operationPermutationSequence(*operations.toTypedArray()).take(calculatePermutationsNeeded(parsedInput, operations)).toList()
    return sumOfPossibleCalibrationEquations(parsedInput, operationsPermutations)
}

fun calculatePermutationsNeeded(parsedInput: List>>, operations: Set): Int {
    val highestNumberOfOperations = parsedInput.maxOf { it.second.size - 1 }
    return (1..highestNumberOfOperations).sumOf { operations.size.toDouble().pow(it).toInt() }
}

fun sumOfPossibleCalibrationEquations(parsedInput: List>>, operationPermutationCollection: Collection): Long {
    val permutationsGrouped = operationPermutationCollection.groupBy { it.size }
    return parsedInput.sumOf { (equationResult, equationInput) ->
        if (permutationsGrouped[equationInput.size - 1]!!.any { operations ->
                equationResult == equationInput.drop(1)
                    .foldIndexed(equationInput[0]) { index, acc, lng -> operations[index](acc, lng) }
            }) equationResult else 0
    }
}

typealias OperationPermutation = List

sealed class CalibrationOperation(val operation: (Long, Long) -> Long) {
    operator fun invoke(a: Long, b: Long) = operation(a, b)
    object Plus : CalibrationOperation({ a: Long, b: Long -> a + b })
    object Multiply : CalibrationOperation({ a: Long, b: Long -> a * b })
    object Concat : CalibrationOperation({ a: Long, b: Long -> "$a$b".toLong() })

    companion object {
        fun operationPermutationSequence(vararg operations: CalibrationOperation) = sequence {
            val cache = mutableListOf()
            val calculateCacheRange = { currentLength: Int ->
                val sectionSize = operations.size.toDouble().pow(currentLength - 1).toInt()
                val sectionStart = (1 until currentLength - 1).sumOf { operations.size.toDouble().pow(it).toInt() }
                sectionStart..(sectionStart + sectionSize - 1)
            }

            // Populate the cache with initial values for permutation length 1.
            operations.forEach { operation -> yield(listOf(operation).also { cache.add(it) }) }

            var currentLength = 2
            var offset = 0
            var cacheRange = calculateCacheRange(currentLength)
            var rotatingOperations = operations.toList()
            yieldAll(
                generateSequence {
                    if (cacheRange.count() == offset) {
                        rotatingOperations = rotatingOperations.rotated(1)
                        if (rotatingOperations.first() == operations.first()) {
                            currentLength++
                        }

                        offset = 0
                        cacheRange = calculateCacheRange(currentLength)
                    }

                    val cacheSlice = cache.slice(cacheRange)

                    return@generateSequence (cacheSlice[offset] + rotatingOperations.first()).also {
                        cache += it
                        offset++
                    } 
                }
            )
        }
    }
}