Skip to content

Instantly share code, notes, and snippets.

@tkihira

tkihira/solve.js Secret

Created Jan 3, 2023
Embed
What would you like to do?
Optimized solver for 2023 puzzle
const prettyPrintLog = {};
const prettyPrint = (expr) => {
const stack = [];
for (const c of expr) {
switch (c) {
case -1: {
const r = stack.pop();
const l = stack.pop();
stack.push({ str: `${l.str}+${r.str}`, priority: 3 });
break;
}
case -2: {
const r = stack.pop();
const l = stack.pop();
if (r.priority < 3) {
stack.push({ str: `${l.str}-${r.str}`, priority: 3 });
} else {
stack.push({ str: `${l.str}-(${r.str})`, priority: 3 });
}
break;
}
case -3: {
const r = stack.pop();
const l = stack.pop();
const rStr = r.priority === 3 ? `(${r.str})` : r.str;
const lStr = l.priority === 3 ? `(${l.str})` : l.str;
stack.push({ str: `${lStr}*${rStr}`, priority: 2 });
break;
}
case -4: {
const r = stack.pop();
const l = stack.pop();
const rStr = r.priority >= 2 ? `(${r.str})` : r.str;
const lStr = l.priority === 3 ? `(${l.str})` : l.str;
stack.push({ str: `${lStr}/${rStr}`, priority: 2 });
break;
}
default:
stack.push({ str: c, priority: 1 });
}
}
const output = stack.pop().str;
if (!prettyPrintLog[output]) {
prettyPrintLog[output] = true;
console.log(output);
}
};
const solve = (expr) => {
const stack = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
let pos = 0;
for (let i = 0; i < expr.length; i++) {
const item = expr[i];
if (item < 0) {
const left = stack[pos - 2];
const right = stack[pos - 1];
switch (item) {
case -1: stack[--pos - 1] = left + right; break;
case -2: stack[--pos - 1] = left - right; break;
case -3: stack[--pos - 1] = left * right; break;
case -4: stack[--pos - 1] = left / right; break;
}
} else {
stack[pos++] = item;
}
}
const result = stack[0] - 2023;
if (-0.001 < result && result < 0.001) {
prettyPrint(expr);
}
};
const opCharList = [0, -1, -2, -3, -4];
const traverse = (expr, depth, number, opes, nums, eightDepth) => {
if (depth === 19) {
solve(expr)
}
for (let i = 0; i < opCharList.length; i++) {
const op = opCharList[i];
if (!op) {
if (number > 0) {
expr[depth] = number;
if (traverse(expr, depth + 1, number - 1, opes, nums + 1, number === 8 ? 0 : eightDepth < 0 ? eightDepth : eightDepth + 1)) {
return true;
}
}
} else {
if (nums - opes >= 2) {
if (eightDepth === 0 && op !== -4) {
continue;
}
expr[depth] = op;
traverse(expr, depth + 1, number, opes + 1, nums, eightDepth - 1);
}
}
}
};
traverse([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0, 10, 0, 0, -1);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment