Solution to AOC 2022 Day 19 Part 1

aoc-2022-day19-refined.linq

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

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

void Main()
{
	const bool UseSampleInput = false;
	using (var tr =
		UseSampleInput ? GetSampleInput() : OpenDataFile()
		)
	{
		var bplst = ParseInput(tr).ToList();
		var lst = bplst.Select(sim => new { id = sim.id, maxGeodes = FindMaxGeodes(new MiningSimulation(sim)) }).ToList()
			//.Dump("blueprint scores")
		;
		lst.Select(x => x.id * x.maxGeodes).Sum().Dump("Part 1");
	}
}

static int GetFinalGeodesUpperBound(MiningSimulation sim)
{
	// v1: assumed we could create a new geode robot each cycle.
	// not close enough to reality to prune enough dead branches; couldn't even solve the sample
	// v2: assumed we could create a new obsidian robot each cycle
	// good enough for the sample but too slow for the puzzle
	// v3: assume we can create a new clay robot each cycle
	int geodeRobotCount = sim.GeodeRobotCount;
	int obsidianRobotCount = sim.ObsidianRobotCount;
	int clayRobotCount = sim.ClayRobotCount;	

	int obsidianCount = sim.ObsidianCount;
	int obsidianCost = sim.GeodeRobotObsidianCost;
	
	int clayCount = sim.ClayCount;
	int clayCost = sim.ObsidianRobotClayCost;

	int geodeCount = sim.GeodeCount;
	for (int i = sim.TimePassed; i < TimeLimit; i++)
	{
		var newClayRobotCount = clayRobotCount;
		var newObsidianRobotCount = obsidianRobotCount;
		var newGeodeRobotCount = geodeRobotCount;

		if (obsidianCount >= obsidianCost)
		{
			// spend 1min building a geode robot
			obsidianCount -= obsidianCost;
			newGeodeRobotCount++;
		}
		if (clayCount >= clayCost)
		{
			// spend 1min building an obsidian robot
			clayCount -= clayCost;
			newObsidianRobotCount++;
		}
		// somehow also spend that same minute building a clay robot
		newClayRobotCount++;
		
		clayCount += clayRobotCount;
		obsidianCount += obsidianRobotCount;
		geodeCount += geodeRobotCount;
		
		geodeRobotCount = newGeodeRobotCount;
		obsidianRobotCount = newObsidianRobotCount;
		clayRobotCount = newClayRobotCount;
	}
	return geodeCount;
}

record struct MiningAction(int time, string robotType)
{
	public override string ToString()
	{
		var sb = new StringBuilder();
		sb.AppendFormat("T={0}: ", time);
		if (robotType == null) sb.Append("Wait");
		else sb.Append("Build ").Append(robotType);
		return sb.ToString();
	}
}

const int TimeLimit = 24;
int FindMaxGeodes(MiningSimulation sim)
{
	var queue = new CheapPriorityQueue<(double rate, int timePassed, int estimatedFutureValue), 
		(MiningSimulation sim, ImmutableList<MiningAction> history, ImmutableList<MiningSimulation> simHistory)>();
	queue.Enqueue((0.0, 0, 0), 
		(sim, ImmutableList<MiningAction>.Empty,
		ImmutableList<MiningSimulation>.Empty)
	);
	var dc = new DumpContainer()
		//.Dump("progress")
		;
	var dc_best = new DumpContainer()
		//.Dump("Best pressure, err, geode count")
		;
	
	int bestGeodesEver = 0;
	ImmutableList<MiningAction> bestSequence = default;
	ImmutableList<MiningSimulation> bestHistory = default;

	while (queue.Count > 0)
	{
		var (state, history, simHistory) = queue.Dequeue();
		dc.Content = $"Queue count = {queue.Count}";
		if (state.TimePassed > TimeLimit)
		{
			continue; // dead
		}
		
		if (state.TimePassed > 0)
			simHistory = simHistory.Add(state);

		var curGeodeCount = state.GeodeCount;
		if (curGeodeCount > bestGeodesEver)
		{
			bestGeodesEver = curGeodeCount;
			bestSequence = history;
			bestHistory = simHistory;
			dc_best.Content = bestGeodesEver;
		}

		if (state.TimePassed == TimeLimit) continue; // outtatime

		var finalGeodesUpperBound = state.GetFinalValueUpperBound();
		if (finalGeodesUpperBound <= bestGeodesEver)
		{
			//Console.WriteLine("pruned");
			// dead-end
			continue;
		}

		foreach (var robot2build in state.GetBuildableRobots())
		{
			var nextState = state.BuildRobot(robot2build);
			queue.Enqueue((-nextState.GeodesPerMinute, -nextState.TimePassed, -nextState.GetFinalValueUpperBound()),
				(nextState, history.Add(new MiningAction(state.TimePassed, robot2build)), simHistory)
				);
		}

		if (state.MakesSenseToWait)
		{
			var nextState = state.Wait1Minute();
			queue.Enqueue((-nextState.GeodesPerMinute, -nextState.TimePassed, -nextState.GetFinalValueUpperBound()),
					(nextState, history.Add(new MiningAction(state.TimePassed, null)), simHistory)
					);

		}
	}

	return bestGeodesEver;
}

#region CheapPriorityQueue
class CheapPriorityQueue<TPriority, TValue>
{
	class ShimComparer : IComparer<(TPriority key, long sequence)>
	{
		IComparer<TPriority> _keyComparer;
		public ShimComparer(IComparer<TPriority> keyComparer)
		{
			_keyComparer = keyComparer;
		}

		public int Compare((TPriority key, long sequence) x, (TPriority key, long sequence) y)
		{
			int cmp = _keyComparer.Compare(x.key, y.key);
			if (cmp != 0) return cmp;
			return x.sequence.CompareTo(y.sequence);
		}
	}

	SortedDictionary<(TPriority key, long sequence), TValue> _dict;
	long _sequence;

	public CheapPriorityQueue() : this(Comparer<TPriority>.Default)
	{
	}

	public CheapPriorityQueue(IComparer<TPriority> comparer)
	{
		_dict = new SortedDictionary<(TPriority, long), TValue>(new ShimComparer(comparer));
	}

	public int Count => _dict.Count;
	public TValue Dequeue()
	{
		var firstEntry = _dict.First();
		_dict.Remove(firstEntry.Key);
		return firstEntry.Value;
	}
	public void Enqueue(TPriority priority, TValue value)
	{
		var sequence = _sequence++;
		_dict[(priority, sequence)] = value;
	}
}
#endregion

class MiningSimulation
{
	public MiningSimulation(Blueprint blueprint)
	{
		this.Blueprint = blueprint;
		RobotCount = new int[blueprint.robots.Length];
		ResourceCount = new int[blueprint.robots.Length];
		var typeMap = TypeMap = new Dictionary<string, int>();
		var robots = blueprint.robots;
		for (int i = 0; i < robots.Length; i++)
			typeMap[robots[i].type] = i;

		// you start with one ore robot
		RobotCount[typeMap["ore"]]++;

		_clayIndex = typeMap["clay"];
		_obsidianIndex = typeMap["obsidian"];
		_geodeIndex = typeMap["geode"];
	}

	int? _finalGeodesUpperBound;
	public int GetFinalValueUpperBound()
	{
		if (_finalGeodesUpperBound == null)
			_finalGeodesUpperBound = GetFinalGeodesUpperBound(this);
		return _finalGeodesUpperBound.Value;
	}

	public MiningSimulation Clone()
	{
		var tmp = (MiningSimulation)MemberwiseClone();
		tmp._finalGeodesUpperBound = null;
		tmp.RobotCount = (int[])tmp.RobotCount.Clone();
		tmp.ResourceCount = (int[])tmp.ResourceCount.Clone();
		tmp.MakesSenseToWait = false;
		return tmp;
	}

	public int GetResourceCount(string name) => ResourceCount[TypeMap[name]];
	public MiningSimulation Wait1Minute()
	{
		var copy = Clone();
		copy.Advance1Minute();
		return copy;
	}
	void Advance1Minute()
	{
		MakesSenseToWait = false;
		TimePassed++;
		for (int i = 0; i < RobotCount.Length; i++)
		{
			ResourceCount[i] += RobotCount[i];
		}
	}
	public MiningSimulation BuildRobot(string type)
	{
		var copy = Clone();
		var typeIdx = TypeMap[type];
		copy.BuildRobot(typeIdx);
		return copy;
	}
	
	void BuildRobot(int typeIdx)
	{
		var robotDef = Blueprint.robots[typeIdx];
		var resource1idx = TypeMap[robotDef.cost1.type];
		var resource2idx = (robotDef.cost2.qty > 0 ? TypeMap[robotDef.cost2.type] : 0);

		var tmp = ResourceCount[resource1idx] -= robotDef.cost1.qty;
		if (tmp < 0) throw new Exception("can't build this robot!");
		tmp = ResourceCount[resource2idx] -= robotDef.cost2.qty;
		if (tmp < 0) throw new Exception("can't build this robot!");

		Advance1Minute();

		RobotCount[typeIdx]++;
	}
	enum RobotBuildPolicy
	{
		CannotBuild,
		CanBuild,
		CanSoonBuild,
	}
	RobotBuildPolicy GetBuildPolicy(RobotType robot)
	{
		var type1idx = TypeMap[robot.cost1.type];
		var type2idx = (robot.cost2.qty > 0) ? TypeMap[robot.cost2.type] : type1idx;
		// can we build it? YES WE CAN!
		if (ResourceCount[type1idx] >= robot.cost1.qty &&
			ResourceCount[type2idx] >= robot.cost2.qty)
			return RobotBuildPolicy.CanBuild;
		// hrm. well, will we be able to build it in the FUTURE?
		if (RobotCount[type1idx] > 0 && RobotCount[type2idx] > 0)
			return RobotBuildPolicy.CanSoonBuild;
		// okay, we can't build this robot, but waiting is not going to improve the situation
		// (THIS HEURISTIC IS SLIGHTLY WRONG. I hope it's not wrong enough to give me the wrong answer.)
		return RobotBuildPolicy.CannotBuild;
	}

	public IEnumerable<string> GetBuildableRobots()
	{
		var robots = Blueprint.robots;
		for (int i = 0; i < robots.Length; i++)
		{
			var robot = robots[i];
			var policy = GetBuildPolicy(robot);
			if (policy == RobotBuildPolicy.CanBuild) yield return robot.type;
			else if (policy == RobotBuildPolicy.CanSoonBuild) MakesSenseToWait = true;
		}
	}
	public readonly Blueprint Blueprint;
	public int TimePassed { get; private set; }
	readonly int _obsidianIndex;
	readonly int _geodeIndex;
	readonly int _clayIndex;
	public int GeodeCount => ResourceCount[_geodeIndex];
	public int GeodeRobotCount => RobotCount[_geodeIndex];

	public int ObsidianCount => ResourceCount[_obsidianIndex];
	public int ObsidianRobotCount => RobotCount[_obsidianIndex];
	public int GeodeRobotObsidianCost => Blueprint.robots[_geodeIndex].cost2.qty;

	public int ClayCount => ResourceCount[_clayIndex];
	public int ClayRobotCount => RobotCount[_clayIndex];
	public int ObsidianRobotClayCost => Blueprint.robots[_obsidianIndex].cost2.qty;
	
	public double GeodesPerMinute => (double)GeodeCount / (double)TimePassed;
	public bool MakesSenseToWait { get; private set; }
	readonly Dictionary<string, int> TypeMap;
	int[] RobotCount;
	int[] ResourceCount;
	public object ToDump() => new {
		Robots = RobotCount,
		Resources = ResourceCount,
	};
	
}

record struct RobotCost(int qty, string type);
record struct RobotType(string type, RobotCost cost1, RobotCost cost2);
record class Blueprint(int id, RobotType[] robots);
IEnumerable<Blueprint> ParseInput(TextReader tr)
{
	var bp_parser = new Regex(@"^Blueprint (\d+): ");
	var robot_parser1 = new Regex(@"^Each (\w+) robot costs (\d+) (\w+)\.\s*");
	var robot_parser2 = new Regex(@"^Each (\w+) robot costs (\d+) (\w+) and (\d+) (\w+)\.\s*");
	foreach (var _line in ReadAllLines(tr))
	{
		var line = _line;
		var m = bp_parser.Match(line); if (!m.Success) throw new Exception(_line);
		int bp_id = int.Parse(m.Groups[1].Value);
		line = line.Substring(m.Groups[0].Length);
		var robots = new List<RobotType>(4);
		while (line.Length > 0)
		{
			m = robot_parser1.Match(line);
			if (m.Success)
			{
				line = line.Substring(m.Groups[0].Length);
				var robot = new RobotType(m.Groups[1].Value,
						new RobotCost(int.Parse(m.Groups[2].Value), m.Groups[3].Value),
						default
					);
				robots.Add(robot);
				continue;
			}
			m = robot_parser2.Match(line);
			if (m.Success)
			{
				line = line.Substring(m.Groups[0].Length);
				var robot = new RobotType(m.Groups[1].Value,
						new RobotCost(int.Parse(m.Groups[2].Value), m.Groups[3].Value),
						new RobotCost(int.Parse(m.Groups[4].Value), m.Groups[5].Value)
					);
				robots.Add(robot);
				continue;
			}
			throw new Exception("error: " + _line);
		}
		yield return new Blueprint(
			bp_id,
			robots.ToArray()
		);

	}
}

const string EXAMPLE_1 = @"
Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay.  Each geode robot costs 3 ore and 12 obsidian.
";

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