Caching solution for AOC 2023 day 16

tslater-aoc-2023-day16b.linq

#load "C:\Users\Stevie-O\Documents\LINQPad Queries\advent-of-code\common\aoc-input-util.linq"
#load "C:\Users\Stevie-O\Documents\LINQPad Queries\advent-of-code\common\aoc-parsers.linq"

const string EXAMPLE_1 = @"
.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....-|.\
..//.|....
";

void Main()
{
	using (var tr =
		OpenDataFile()
		//GetSampleInput(1)
		)
	{
		var input = ReadAllLines(tr).ToArray();
		var day16 = new Day16(input);
		day16.Solve_2().Dump("Solve_2()");
	}
}
internal class Day16
{
	enum Direction
	{
		NORTH = UserQuery.NORTH, EAST = UserQuery.EAST, SOUTH = UserQuery.SOUTH, WEST = UserQuery.WEST
	}

	class VisitTracker
	{
#if USE_ARRAY
		bool[,] VisitGrid;
		int Height => VisitGrid.GetLength(1);
		int Width => VisitGrid.GetLength(0);
#else
		HashSet<SignedPoint> VisitSet = new HashSet<SignedPoint>();
#endif

		public VisitTracker(int width, int height)
		{
#if USE_ARRAY
			VisitGrid = new bool[width, height];
#endif
		}

		public bool IsVisited(int x, int y) =>
#if USE_ARRAY
			VisitGrid[x, y]
#else
			VisitSet.Contains(new SignedPoint(x, y))
#endif
			;

		public void PrintVisitGrid()
		{
#if USE_ARRAY
			for (var y = 0; y < Height; y++)
			{
				for (var x = 0; x < Width; x++)
				{
					Console.Write(VisitGrid[x, y] ? 'X' : '.');
				}
				Console.WriteLine();
			}
#endif
		}

		public int GetVisitCount()
		{
#if USE_ARRAY
			var count = 0;
			for (var x = 0; x < Width; x++)
			{
				for (var y = 0; y < Height; y++)
				{
					if (VisitGrid[x, y])
					{
						count++;
					}
				}
			}

			return count;
#else

			return VisitSet.Count;
#endif
		}

		public bool Visit(SignedPoint location)
		{
#if USE_ARRAY
			if (VisitGrid[location.X, location.Y]) return false;
			VisitGrid[location.X, location.Y] = true;
			return true;
#else

			return VisitSet.Add(location);
#endif
		}

		public void MergeFrom(VisitTracker other)
		{
#if USE_ARRAY
			for (var x = 0; x < Width; x++)
			{
				for (var y = 0; y < Height; y++)
				{
					VisitGrid[x, y] |= other.VisitGrid[x, y];
				}
			}
#else
			VisitSet.UnionWith(other.VisitSet);
#endif

		}


	}

	class LightRay
	{
		public SignedPoint Position;
		public Direction Direction;
		public int Width;
		public int Height;

		public LightRay(SignedPoint position, Direction direction, int width, int height)
		{
			Position = position;
			Direction = direction;
			Width = width;
			Height = height;
		}

		public void TurnCW()
		{
			Direction = (Direction)(((int)Direction + 2) % 8);
		}

		public void TurnCCW()
		{
			Direction = (Direction)(((int)Direction + 6) % 8);
		}

		public bool Move()
		{
			Position += DirectionVelocity[(int)Direction];

			if (Position.X < 0 || Position.X >= Width || Position.Y < 0 || Position.Y >= Height)
			{
				return false;
			}
			else
			{
				return true;
			}
		}
	}

	char[,] Grid;
	int Width;
	int Height;


	string RenderGrid(VisitTracker visited)
	{
		var sb = new StringBuilder((Width + Environment.NewLine.Length) * Height);
		for (var y = 0; y < Height; y++)
		{
			for (var x = 0; x < Width; x++)
			{

				char gridch = Grid[x, y];
				char drawch = gridch switch
				{
					'.' => visited.IsVisited(x, y) ? '#' : '.',
					_ => gridch,
				};
				sb.Append(drawch);
			}
			sb.AppendLine();
		}
		return sb.ToString();
	}


	VisitTracker CreateTracker() => new VisitTracker(Width, Height);

	public Day16(string[] lines)
	{
		Width = lines[0].Length;
		Height = lines.Length;

		Grid = new char[lines[0].Length, lines.Length];
		for (var y = 0; y < lines.Length; y++)
		{
			for (var x = 0; x < lines[y].Length; x++)
			{
				Grid[x, y] = lines[y][x];
			}
		}
	}

	enum RayAction
	{
		MoveOn, // '.'
		PipeThrough, // '|' from north/south or '-' from east/west
		OffGrid, // exited the grid
		TurnCCW,
		TurnCW,
		SplitNS,    // '|' from east/west
		SplitEW, // '-' from north/south
	}

	RayAction GetRayAction(SignedPoint position, Direction dir)
	{
		return Grid[position.X, position.Y] switch
		{
			'.' => RayAction.MoveOn,
			'/' => (dir == Direction.EAST || dir == Direction.WEST) ? RayAction.TurnCCW : RayAction.TurnCW,
			'\\' => (dir == Direction.EAST || dir == Direction.WEST) ? RayAction.TurnCW : RayAction.TurnCCW,
			'|' => (dir == Direction.NORTH || dir == Direction.SOUTH) ? RayAction.PipeThrough : RayAction.SplitNS,
			'-' => (dir == Direction.NORTH || dir == Direction.SOUTH) ? RayAction.SplitEW : RayAction.PipeThrough,
		};
	}

	Dictionary<(SignedPoint, Direction), (RayAction action, SignedPoint endPos, Direction endDir, VisitTracker visited)> SegmentCache = new();
	(RayAction action, SignedPoint endPos, Direction endDir, VisitTracker visited) RunRaySegment(RayAction startAction, SignedPoint startPos, Direction startDir)
	{
		var cacheKey = (startPos, startDir);
		if (!SegmentCache.TryGetValue(cacheKey, out var result))
		{
			result = SegmentCache[cacheKey] = _RunRaySegment(startAction, startPos, startDir);
			SegmentCache[(result.endPos, GetReverseDirection(result.endDir))] = (startAction, startPos, GetReverseDirection(startDir), result.visited);
		}
		return result;
	}
	static Direction GetReverseDirection(Direction d) =>
		(Direction)ReverseDirection[(int)d];
	(RayAction action, SignedPoint endPos, Direction endDir, VisitTracker visited) _RunRaySegment(RayAction startAction, SignedPoint startPos, Direction startDir)
	{
		var tracker = CreateTracker();
		var ray = new LightRay(startPos, startDir, Width, Height);

		// if we didn't start from off-grid, make sure we track that we visited the start position
		if (startAction != RayAction.OffGrid)
			tracker.Visit(ray.Position);

		RayAction stopAction = RayAction.OffGrid;
		while (ray.Move())
		{
			var stop = false;
			tracker.Visit(ray.Position);
			var action = GetRayAction(ray.Position, ray.Direction);
			switch (action)
			{
				case RayAction.MoveOn: break;
				case RayAction.TurnCCW: ray.TurnCCW(); break;
				case RayAction.TurnCW: ray.TurnCW(); break;
				default: // terminate segment
					stopAction = action;
					stop = true; // can't "break" out of the while loop from here
					break;
			}
			if (stop) break;
		}
		return (stopAction, ray.Position, ray.Direction, tracker);
	}

	VisitTracker RunRay(SignedPoint entryPoint, Direction entryDirection)
	{
		var visited = new HashSet<(SignedPoint, Direction)>();
		var tracker = CreateTracker();
		var rays = new Queue<(RayAction startAction, SignedPoint startPos, Direction startDir)>();

		rays.Enqueue((RayAction.OffGrid, entryPoint, entryDirection));

		while (rays.Count > 0)
		{
			var rayInfo = rays.Dequeue();

			if (!visited.Add((rayInfo.startPos, rayInfo.startDir)))
			{
				//Console.WriteLine("Already visited: {0}", (rayInfo.startPos, rayInfo.startDir));
				continue; // we've already done this one
			}
			var newRayInfo = RunRaySegment(rayInfo.startAction, rayInfo.startPos, rayInfo.startDir);
			//RenderGrid(newRayInfo.visited).Dump($"{rayInfo} -> {newRayInfo}");
			//Console.WriteLine("{0} -> {1}", rayInfo, newRayInfo);

			// merge in all the spots visited by this last segment
			tracker.MergeFrom(newRayInfo.visited);

			switch (newRayInfo.action)
			{
				case RayAction.OffGrid: break; // dead-end
				case RayAction.PipeThrough:
					// keep going
					rays.Enqueue((RayAction.PipeThrough, newRayInfo.endPos, newRayInfo.endDir));
					//Console.WriteLine("enqueued: {0}", rays.Last());
					break;
				case RayAction.SplitEW:
					rays.Enqueue((RayAction.PipeThrough, newRayInfo.endPos, Direction.EAST));
					rays.Enqueue((RayAction.PipeThrough, newRayInfo.endPos, Direction.WEST));
					break;
				case RayAction.SplitNS:
					rays.Enqueue((RayAction.PipeThrough, newRayInfo.endPos, Direction.NORTH));
					rays.Enqueue((RayAction.PipeThrough, newRayInfo.endPos, Direction.SOUTH));
					break;
				default: throw new Exception("internal error");
			}
		}

		return tracker;
	}

	public object Solve_1()
	{
		var ray = RunRay(new SignedPoint(-1, 0), Direction.EAST);
		ray.PrintVisitGrid();
		return ray.GetVisitCount();
	}

	public object Solve_2()
	{
		var rayCount = 0;

		/* start a ray from each point along the border of the grid and find which one returns the largest visit count */
		var maxVisitCount = 0;
		for (var x = 0; x < Width; x++)
		{
			var ray = RunRay(new SignedPoint(x, -1), Direction.SOUTH);
			maxVisitCount = Math.Max(maxVisitCount, ray.GetVisitCount());
			//Console.WriteLine();
			//ray.PrintVisitGrid();

			ray = RunRay(new SignedPoint(x, Height), Direction.NORTH);
			maxVisitCount = Math.Max(maxVisitCount, ray.GetVisitCount());
			//Console.WriteLine();
			//ray.PrintVisitGrid();
			rayCount += 2;
		}

		for (var y = 0; y < Height; y++)
		{
			var ray = RunRay(new SignedPoint(-1, y), Direction.EAST);
			maxVisitCount = Math.Max(maxVisitCount, ray.GetVisitCount());
			//Console.WriteLine();
			//RenderGrid(ray).Dump();
			//ray.PrintVisitGrid();

			ray = RunRay(new SignedPoint(Width, y), Direction.WEST);
			maxVisitCount = Math.Max(maxVisitCount, ray.GetVisitCount());
			//Console.WriteLine();
			//ray.PrintVisitGrid();
			rayCount += 2;
		}


		return maxVisitCount;
	}
}


#region SignedPoint

const int NORTH = 0, NORTHEAST = 1, EAST = 2, SOUTHEAST = 3, SOUTH = 4, SOUTHWEST = 5, WEST = 6, NORTHWEST = 7;
static readonly string[] DirectionNames = new string[] { nameof(NORTH), nameof(NORTHEAST), nameof(EAST), nameof(SOUTHEAST), nameof(SOUTH), nameof(SOUTHWEST), nameof(WEST), nameof(NORTHWEST), };
static readonly int[] ReverseDirection = new int[] { SOUTH, SOUTHWEST, WEST, NORTHWEST, NORTH, NORTHEAST, EAST, SOUTHEAST };

static readonly Velocity[] DirectionVelocity = new[]
{
		new Velocity(0, -1), // NORTH
		new Velocity(1, -1), // NORTHEAST
		new Velocity(1, 0), // EAST
		new Velocity(1, 1), // SOUTHEAST
		new Velocity(0, 1), // SOUTH
		new Velocity(-1, 1), // SOUTHWEST
		new Velocity(-1, 0), // WEST
		new Velocity(-1, -1), // NORTHWEST
};

readonly struct Velocity
{
	public readonly int Dx, Dy;
	public Velocity(int dx, int dy)
	{
		Dx = dx; Dy = dy;
	}
	public static Velocity operator *(in Velocity v, int c)
	{
		return new Velocity(v.Dx * c, v.Dy * c);
	}
	public override string ToString() => ToString(null, null);
	public string ToString(string format, IFormatProvider formatProvider)
	{
		return string.Concat("dx = ", Dx.ToString(format, formatProvider), ", dy = ", Dy.ToString(format, formatProvider));
	}
}


// Point structure optimized for signed coordinates (from my 2018 solutions)
readonly struct SignedPoint : IEquatable<SignedPoint>, IFormattable
{
	public static SignedPoint Origin => new SignedPoint();

	public readonly int X, Y;
	//public int DistanceFromOrigin => GetManhattanDistance(SignedPoint.Origin);
	public SignedPoint(int x, int y) { X = x; Y = y; }
	public static SignedPoint operator +(SignedPoint sp, in Velocity v) => sp.OffsetBy(v);
	public SignedPoint OffsetBy(int dx, int dy) { return new SignedPoint(X + dx, Y + dy); }
	public SignedPoint OffsetBy(in Velocity v) { return OffsetBy(v.Dx, v.Dy); }
	public SignedPoint FlipX() { return new SignedPoint(-X, Y); }
	public SignedPoint FlipY() { return new SignedPoint(X, -Y); }
	public SignedPoint FlipXY() { return new SignedPoint(-X, -Y); }
	public SignedPoint Go(int direction) { return OffsetBy(DirectionVelocity[direction]); }
	public bool Equals(SignedPoint b) { return X == b.X && Y == b.Y; }
	public override bool Equals(object obj) => (obj is SignedPoint) && Equals((SignedPoint)obj);
	public override int GetHashCode()
	{
		return X ^ (((Y >> 16) & 0xFFFF) | (Y << 16));
	}
	public override string ToString() => ToString(null, null);
	public string ToString(string format, IFormatProvider formatProvider)
	{
		return string.Concat("(", X.ToString(format, formatProvider), ", ", Y.ToString(format, formatProvider), ")");
	}
	public int GetManhattanDistance(int x, int y) => GetManhattanDistance(new SignedPoint(x, y));
	public int GetManhattanDistance(in SignedPoint pt) { return Math.Abs(X - pt.X) + Math.Abs(Y - pt.Y); }
	public static bool operator ==(in SignedPoint a, in SignedPoint b) { return a.X == b.X && a.Y == b.Y; }
	public static bool operator !=(in SignedPoint a, in SignedPoint b) { return !(a == b); }
	//public object ToDump() => new { X, Y };
}

#endregion