AOC 2024 Day 7 Part 2 - DFS with pruning

aoc-2024-day07b-dfs.linq

<Query Kind="Program">
  <Namespace>System.Collections.Immutable</Namespace>
</Query>

#load "../common/aoc-input-util.linq"
#load "../common/aoc-input-util2.linq"
#load "../common/aoc-parsers.linq"
#load "../common/aoc-exec-util.linq"

const bool EXAMPLE = false;

void Main()
{
	RunMain((tr) =>
	{
		var input = SimpleOneLineParser<(long key, string values)>(tr, @"^(\d+): ((?:\d+(?: |$))+)$")
			.Select(x => (x.key, args: x.values.Split(' ').Select(long.Parse).ToArray()))
			.ToList();
		var result = input
			.Where(x => IsSolvable(x.key, x.args))
			.ToList()
			.Dump("solvable")
			.Select(x => x.key)
			.Sum()
			//.ToList()
			.Dump();
		return result;
});
}

/// <summary>brute force of cartesian product</summary>
bool IsSolvable2(long target, long[] operands)
{
	//Console.WriteLine("Considering: {0}", operands.Length);
	var operators = operands.Length - 1;
	if (operators >= 63) throw new Exception("too many operands");
	long maxop = 1;
	for (int i=0; i<operators; i++) maxop *= 3;
	for (long i = 0; i < maxop; i++)
	{
		long accum = operands[0];
		long i_reg = i;
		for (int j = 0; j < operators; j++)
		{
			var result = i_reg % 3;
			i_reg /= 3;
			if (result == 0)
			{
				accum += operands[j + 1];
			} else if (result == 1) {
				accum *= operands[j + 1];
			}
			else
			{
				accum = long.Parse(accum.ToString() + operands[j + 1].ToString());
			}
			if (accum > target) break;
		}
		if (accum == target) return true;
	}
	return false;
}

/// <summary>a smarter version that prunes impossible concatenation and multiplication steps</summary>
bool IsSolvable(long target, Span<long> operands, Dictionary<(long target, int len), bool> cache = null)
{
	if (operands.Length == 0) return false;
	var lastarg = operands[operands.Length - 1];
	if (operands.Length == 1) return (lastarg == target);
	var prevargs = operands.Slice(0, operands.Length - 1);
	var cacheKey = (target, operands.Length);
	if (cache == null) cache = new Dictionary<(long targe, int len), bool>();
	else if (cache.TryGetValue(cacheKey, out var cached)) return cached;

	bool is_ok = false;
	if (target >= lastarg)
	{
		if (IsConcatOf(target, lastarg, out var new_target))
		{
			is_ok = IsSolvable(new_target, prevargs, cache);	
		}
		if (!is_ok && (target % lastarg) == 0)
		{
			// might be a multiply!
			is_ok = IsSolvable(target / lastarg, prevargs, cache);
		}
		if (!is_ok && target >= lastarg)
		{
			// might be an addition!
			is_ok = IsSolvable(target - lastarg, prevargs, cache);
		}
	}
	
	cache.Add(cacheKey, is_ok);
	return is_ok;
}

bool IsConcatOf(long target, long right_operand, out long left_operand)
{
	long divisor = 10;
	while (divisor <= right_operand) divisor *= 10;
	if ((target % divisor) == right_operand)
	{
		left_operand = target / divisor;
		return true;
	}
	else
	{
		left_operand = default;
		return false;
	}
}

class Sim
{
	public int w, h;
	public string[] grid;
	public SignedPoint OtherObstruction;
	public SignedPoint pos;
	public int dir;
	public bool Step()
	{
		var target_pos = pos + DirectionVelocity[dir];
		if (target_pos.InBounds(w, h))
		{

			if (target_pos != OtherObstruction && grid[target_pos.Y][target_pos.X] != '#')
			{
				pos = target_pos;
				//Console.WriteLine("travel to {0}", target_pos);
			}
			else
			{
				dir = dir switch
				{
					NORTH => EAST,
					EAST => SOUTH,
					SOUTH => WEST,
					WEST => NORTH,
					_ => throw new InvalidOperationException(),
				};
				//Console.WriteLine("turn to {0}", DirectionNames[dir]);
			}
			return true;
		}
		else return false; ;
	}
}

const string EXAMPLE_1 = @"
190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20
";

TextReader GetSampleInput()
{
	return new StringReader(EXAMPLE_1);
}