LevelsChecker - click to expand!
namespace GameData
{
public class LevelsChecker
{
private readonly int _sideSize;
public LevelsChecker(int sideSize)
{
_sideSize = sideSize;
}
public bool LevelPassable(List<int> occupiedPositions, List<int> counts)
{
var graph = new Graph(_sideSize, occupiedPositions, counts);
var results = graph.PerformSearch();
if (results.Count <= 0)
{
return false;
}
Debug.LogFormat($"Total winning combinations {results.Count}");
foreach (var connections in results)
{
Debug.LogFormat($"{string.Join(",", connections)}");
}
return true;
}
}
public class Graph
{
public HashSet<IEnumerable<Connection>> PerformSearch()
{
GatherCombinations();
return ProcessResults();
}
private HashSet<IEnumerable<Connection>> ProcessResults()
{
var stopwatch = new Stopwatch();
stopwatch.Start();
var allPossibleCombinations = CartesianProduct(_connectionsMapping.Values).ToList();
Debug.LogFormat($"all possible combinations {allPossibleCombinations.Count} in {stopwatch.Elapsed}");
stopwatch.Stop();
stopwatch.Reset();
stopwatch.Start();
var totalCount = _positionToCount.Values.Sum();
var requiredPathLength = _verticesInGraph - _occupiedPositions.Count;
var winningCombinations = new List<WinningCombination>(100);
// this one has incredibly long execution time - exponential!!!!
for (var i = 0; i < allPossibleCombinations.Count; i++)
{
var currentPath = new List<int>(16);
var counts = new Dictionary<int, int>(_positionToCount);
var countLeft = totalCount;
var combinationConnections = new List<Connection>(totalCount);
foreach (var connection in allPossibleCombinations[i])
{
var path = connection.GetPath();
if (currentPath.Any(index => path.Contains(index)))
{
break;
}
var fromCount = counts[connection.GetFrom()];
var toCount = counts[connection.GetTo()];
if (fromCount <= 0 || toCount <= 0)
{
continue;
}
currentPath.AddRange(path);
counts[connection.GetFrom()] = --fromCount;
counts[connection.GetTo()] = --toCount;
combinationConnections.Add(connection);
countLeft -= 2;
if (countLeft <= 0)
{
break;
}
}
if (countLeft == 0 && currentPath.Count == requiredPathLength)
{
winningCombinations.Add(new WinningCombination {Index = i, Connections = combinationConnections});
}
}
stopwatch.Stop();
Debug.LogFormat($"winning combinations {winningCombinations.Count} in {stopwatch.Elapsed}");
return FilterDuplicateResults(winningCombinations, allPossibleCombinations);
}
private static HashSet<IEnumerable<Connection>> FilterDuplicateResults(List<WinningCombination> winningCombinations,
List<IEnumerable<Connection>> allPossibleCombinations)
{
// duplicates are possible due to the nature of the CartesianProduct algorithm
// when the same set of values works in different combinations
var uniques = new HashSet<IEnumerable<Connection>>(new SequenceComparer<Connection>());
foreach (var winningCombination in winningCombinations)
{
var connections = allPossibleCombinations[winningCombination.Index];
var combination = connections.Intersect(winningCombination.Connections);
uniques.Add(combination);
}
return uniques;
}
// https://stackoverflow.com/questions/32263241/cartesian-product-in-c-sharp-using-enumeratos
private static IEnumerable<IEnumerable<Connection>> CartesianProduct(IEnumerable<IEnumerable<Connection>> sequences) {
IEnumerable<IEnumerable<Connection>> emptyProduct = new[] { Enumerable.Empty<Connection>() };
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from acc in accumulator
from item in sequence
select acc.Concat(new [] { item }));
}
private class WinningCombination
{
public int Index { get; set; }
public List<Connection> Connections { get; set; }
}
private class SequenceComparer<T> : IEqualityComparer<IEnumerable<T>>
{
public bool Equals(IEnumerable<T> seq1, IEnumerable<T> seq2)
{
return seq1.SequenceEqual(seq2);
}
public int GetHashCode(IEnumerable<T> seq)
{
return seq.Aggregate(53, (current, elem) => current * 37 + elem.GetHashCode());
}
}
}
}
