Advent of Code - Day 7, 2024: Backtracking and Eval
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC.
using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) retVal += target; } sr.Close(); Console.WriteLine(retVal); } bool TryAll1(string[] numbers, long target, string str, int index) { if (index == numbers.Length - 1) { str += numbers[index]; return Evalute1(str, target); } char[] ops = new char[] { '+', '*' }; foreach (char op in ops) if (TryAll1(numbers, target, str + numbers[index] + op.ToString(), index + 1)) return true; return false; } bool Evalute1(string exp, long target) { long result = 0; long part = 0; bool isSum = true; for (int i = 0; i < exp.Length; i++) { if (exp[i] >= '0' && exp[i] <= '9') { part = 10 * part + (int)(exp[i] - '0'); } else { if (isSum) result += part; else result *= part; part = 0; isSum = exp[i] == '+'; } if (result > target) return false; } if (isSum) result += part; else result *= part; return result == target; } bool TryAll2(string[] numbers, long target, string str, int index) { if (index == numbers.Length - 1) { str += numbers[index]; return Evalute2(str, target); } string[] ops = new string[] { "+", "*", "||" }; foreach (string op in ops) if (TryAll2(numbers, target, str + numbers[index] + op, index + 1)) return true; return false; } bool Evalute2(string exp, long target) { long result = 0; long part = 0; int op = 0; //0: +, 1: *, 2: || for (int i = 0; i < exp.Length; i++) { if (exp[i] >= '0' && exp[i] <= '9') { part = 10 * part + (int)(exp[i] - '0'); } else { if (op == 0) result += part; else if (op == 1) result *= part; else { string s1 = result.ToString(); string s2 = part.ToString(); string val = s1 + s2; result = Int64.Parse(val); } part = 0; if (exp[i] == '+') op = 0; else if (exp[i] == '*') op = 1; else { op = 2; i++; } } if (result > target) return false; } if (op == 0) result += part; else if (op == 1) result *= part; else { string s1 = result.ToString(); string s2 = part.ToString(); string val = s1 + s2; result = Int64.Parse(val); } return result == target; } void Process2() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll2(numbers, target, "", 0)) retVal += target; } sr.Close(); Console.WriteLine(retVal); }
Comments
Post a Comment