var input = File.ReadAllText("../../../../Input.in");
var initialWorld = input.Where(c => c == '.' || (c >= 'A' && c <= 'D')).ToArray();
var hallwaySize = initialWorld.Where(c => c == '.').Count();
int[] cost = new[] { 1, 10, 100, 1000 };
int[] directions = new[] { -1, 1 };
Console.WriteLine("Part 1 takes " + Organize(new GameState(initialWorld, 0)) + " energy");
var extras = @"
#D#C#B#A#
#D#B#A#C#";
var extraChars = extras.Where(c => c >= 'A' && c <= 'D').ToArray();
var deepWorld = initialWorld.Take(hallwaySize + 4).Concat(extraChars).Concat(initialWorld.Skip(hallwaySize + 4)).ToArray();
Console.WriteLine("Part 2 takes " + Organize(new GameState(deepWorld, 0)) + " energy");
bool IsRoomOrganized(char[] world, int depth, int r)
{
for (int i = depth - 1; i >= 0; i--)
{
var c = world[hallwaySize + i * 4 + r];
if (c == '.')
{
return true;
}
if (c != 'A' + r)
{
return false;
}
}
return true;
}
int RoomCount(char[] world, int depth, int r)
{
int count = 0;
for (int i = depth - 1; i >= 0; i--)
{
var c = world[hallwaySize + i * 4 + r];
if (c == '.')
{
return count;
}
count++;
}
return count;
}
void PushRoom(char[] world, int depth, int r, char c)
{
for (int i = depth - 1; i >= 0; i--)
{
var index = hallwaySize + i * 4 + r;
if (world[index] == '.')
{
world[index] = c;
return;
}
}
return;
}
void PopRoom(char[] world, int depth, int r)
{
for (int i = 0; i < depth; i++)
{
var index = hallwaySize + i * 4 + r;
if (world[index] != '.')
{
world[index] = '.';
return;
}
}
return;
}
char PeekRoom(char[] world, int depth, int r)
{
for (int i = 0; i < depth; i++)
{
var index = hallwaySize + i * 4 + r;
if (world[index] != '.')
{
return world[index];
}
}
return '0';
}
List<GameState> GetNeighbors(int depth, GameState state)
{
var neighbors = new List<GameState>();
for (int i = 0; i < hallwaySize; i++)
{
if (state.World[i] == '.')
{
continue;
}
var picked = state.World[i];
var pickedIndex = picked - 'A';
bool canMoveToRoom = IsRoomOrganized(state.World, depth, pickedIndex);
if (!canMoveToRoom)
{
continue;
}
var targetPosition = 2 + 2 * pickedIndex;
var direction = targetPosition > i ? 1 : -1;
for (int j = direction; Math.Abs(j) <= Math.Abs(targetPosition - i); j += direction)
{
if (state.World[i + j] != '.')
{
canMoveToRoom = false;
break;
}
}
if (!canMoveToRoom)
{
continue;
}
var newWorld = new char[state.World.Length];
state.World.CopyTo(newWorld, 0);
newWorld[i] = '.';
PushRoom(newWorld, depth, pickedIndex, picked);
var newEnergy = state.Energy + (Math.Abs(targetPosition - i) + (depth - RoomCount(state.World, depth, pickedIndex))) * cost[pickedIndex];
neighbors.Add(new GameState(newWorld, newEnergy));
}
if (neighbors.Count > 0)
{
return neighbors;
}
for (int r = 0; r < 4; r++)
{
if (IsRoomOrganized(state.World, depth, r))
{
continue;
}
var picked = PeekRoom(state.World, depth, r);
var pickedIndex = picked - 'A';
var energy = state.Energy + (depth - RoomCount(state.World, depth, r) + 1) * (cost[pickedIndex]);
var roomPosition = 2 + 2 * r;
foreach (var direction in directions)
{
var distance = direction;
while (roomPosition + distance >= 0 && roomPosition + distance < hallwaySize && state.World[roomPosition + distance] == '.')
{
if (roomPosition + distance == 2 || roomPosition + distance == 4 || roomPosition + distance == 6 || roomPosition + distance == 8)
{
distance += direction;
continue;
}
var newWorld = new char[state.World.Length];
state.World.CopyTo(newWorld, 0);
newWorld[roomPosition + distance] = picked;
PopRoom(newWorld, depth, r);
neighbors.Add(new GameState(newWorld, energy + Math.Abs(distance) * cost[pickedIndex]));
distance += direction;
}
}
}
return neighbors;
}
bool IsTarget(GameState state, int depth)
{
for (int i = 0; i < hallwaySize; i++)
{
if (state.World[i] != '.')
{
return false;
}
}
for (int r = 0; r < 4; r++)
{
if (!IsRoomOrganized(state.World, depth, r))
{
return false;
}
}
return true;
}
int Organize(GameState initialState)
{
var depth = (initialState.World.Length - hallwaySize) / 4;
var frontier = new PriorityQueue<GameState, int>();
frontier.Enqueue(initialState, 0);
var visited = new HashSet<string>();
while (frontier.Count > 0)
{
var node = frontier.Dequeue();
var worldString = new String(node.World);
if (visited.Contains(worldString))
{
continue;
}
if (IsTarget(node, depth))
{
return node.Energy;
}
visited.Add(worldString);
frontier.EnqueueRange(GetNeighbors(depth, node).Select(n => (n, n.Energy)));
}
return 999;
}
record struct GameState(char[] World, int Energy) { }