130 lines
3.9 KiB
C#
130 lines
3.9 KiB
C#
// #define Day23
|
|
#if Day23
|
|
|
|
var lines = File.ReadAllLines("day23/input")
|
|
.ToList();
|
|
|
|
var spaces = Enumerable.Repeat('.', 11).ToArray();
|
|
|
|
var charInfos = new Dictionary<char, CharInfo>() {
|
|
{'A', new CharInfo(new Stack<char>(), 2, 1)},
|
|
{'B', new CharInfo(new Stack<char>(), 4, 10)},
|
|
{'C', new CharInfo(new Stack<char>(), 6, 100)},
|
|
{'D', new CharInfo(new Stack<char>(), 8, 1000)},
|
|
};
|
|
var allStackPos = charInfos.Values.Select(i => i.stackPos).ToHashSet();
|
|
|
|
foreach (var charInfo in charInfos.Values) {
|
|
int pos = 2;
|
|
var chars = new List<char>();
|
|
while (pos < lines.Count && lines[pos][charInfo.stackPos+1] != '#') {
|
|
chars.Add(lines[pos][charInfo.stackPos+1]);
|
|
pos++;
|
|
}
|
|
chars.Reverse();
|
|
chars.ForEach(c => charInfo.stack.Push(c));
|
|
}
|
|
|
|
int maxStackDepth = charInfos.Values.Select(i => i.stack.Count).Max();
|
|
|
|
long globalMinimumCost = long.MaxValue;
|
|
Solve(charInfos, spaces, 0L);
|
|
Console.WriteLine(globalMinimumCost);
|
|
|
|
void Solve(Dictionary<char, CharInfo> charInfos, char[] spaces, long cost) {
|
|
if (cost >= globalMinimumCost) {
|
|
return;
|
|
}
|
|
if (Solved(charInfos, spaces)) {
|
|
if (cost < globalMinimumCost) {
|
|
globalMinimumCost = cost;
|
|
}
|
|
return;
|
|
}
|
|
bool spaceMoveToStack = false;
|
|
for (int i = 0; i < spaces.Length; i++) {
|
|
if (spaces[i] != '.' && CheckMoveFromSpaces(i, spaces)) {
|
|
spaceMoveToStack = true;
|
|
char moved = spaces[i];
|
|
CharInfo charInfo = charInfos[spaces[i]];
|
|
spaces[i] = '.';
|
|
charInfo.stack.Push(moved);
|
|
long curCost = (Math.Abs(i - charInfo.stackPos) + (maxStackDepth - charInfo.stack.Count + 1)) * charInfo.cost;
|
|
Solve(charInfos, spaces, cost + curCost);
|
|
charInfo.stack.Pop();
|
|
spaces[i] = moved;
|
|
}
|
|
}
|
|
if (spaceMoveToStack) {
|
|
return;
|
|
}
|
|
|
|
foreach ((var key,var value) in charInfos) {
|
|
if (value.stack.Any(c => c != key)) {
|
|
for (int i = 0; i < spaces.Length; i++) {
|
|
if (spaces[i] != '.' || allStackPos.Contains(i) || CheckMoveToSpacesImpossible(value.stackPos, i, spaces)) {
|
|
continue;
|
|
}
|
|
var movedChar = value.stack.Pop();
|
|
var movedCharInfo = charInfos[movedChar];
|
|
spaces[i] = movedChar;
|
|
long curCost = (Math.Abs(i - value.stackPos) + (maxStackDepth - value.stack.Count)) * movedCharInfo.cost;
|
|
Solve(charInfos, spaces, cost + curCost);
|
|
value.stack.Push(movedChar);
|
|
spaces[i] = '.';
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int NumberOfChars(Dictionary<char, CharInfo> charInfos, char[] spaces) {
|
|
return charInfos.Values.Select(i => i.stack.Count).Sum() + spaces.Count(c => c != '.');
|
|
}
|
|
|
|
bool CheckMoveToSpacesImpossible(int from, int to, char[] spaces) {
|
|
int min = Math.Min(from, to);
|
|
int max = Math.Max(from, to);
|
|
|
|
for (int i = min; i <= max; i++) {
|
|
if (spaces[i] != '.') {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool CheckMoveFromSpaces(int posInSpaces, char[] spaces) {
|
|
CharInfo charInfo = charInfos[spaces[posInSpaces]];
|
|
if (charInfo.stack.Any(c => !c.Equals(spaces[posInSpaces]))) {
|
|
return false;
|
|
}
|
|
|
|
int min, max;
|
|
if (charInfo.stackPos == posInSpaces) { // should not happen
|
|
return true;
|
|
} else if (charInfo.stackPos > posInSpaces) {
|
|
min = posInSpaces + 1;
|
|
max = charInfo.stackPos;
|
|
} else {
|
|
min = charInfo.stackPos;
|
|
max = posInSpaces - 1;
|
|
}
|
|
|
|
for (int i = min; i <= max; i++) {
|
|
if (spaces[i] != '.') {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool Solved(Dictionary<char, CharInfo> charInfos, char[] spaces) {
|
|
if (spaces.All(c => c == '.') && charInfos.All(info => info.Value.stack.All(c => c == info.Key))) {
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
record CharInfo(Stack<char> stack, int stackPos, long cost);
|
|
#endif |