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

Popular posts from this blog

Golang vs. C#: performance characteristics (simple case study)

Advent of Code - Day 6, 2024: BFS and FSM

Claude vs ChatGPT: A Coder's Perspective on LLM Performance