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);
graph.GatherCombinations();
return true;
}
}
// https://www.geeksforgeeks.org/find-paths-given-source-destination/
public class Graph
{
private readonly int _verticesInGraph;
private readonly int _sideSize;
private List<int>[] _adjacencyList;
private readonly List<int> _corners;
private readonly List<int> _downSide;
private readonly List<int> _leftSide;
private readonly List<int> _rightSide;
private readonly List<int> _upSide;
private readonly List<int> _inner;
private readonly List<int> _occupiedPositions;
private readonly Dictionary<int, int> _positionToCount;
private readonly Dictionary<int, List<Connection>> _connectionsMapping = new Dictionary<int, List<Connection>>();
public Graph(int sideSize, List<int> occupiedPositions, List<int> counts)
{
_sideSize = sideSize;
_verticesInGraph = sideSize * sideSize;
_occupiedPositions = occupiedPositions;
_positionToCount = new Dictionary<int, int>();
for (var i = 0; i < _occupiedPositions.Count; i++)
{
_positionToCount[_occupiedPositions[i]] = counts[i];
}
_corners = new List<int>
{
0,
_sideSize - 1,
_sideSize * _sideSize - _sideSize,
_sideSize * _sideSize - 1
};
_downSide = new List<int>();
for (var i = 1; i < _corners[1]; i++)
{
_downSide.Add(i);
}
_leftSide = new List<int>();
for (var i = _sideSize; i < _corners[2]; i += _sideSize)
{
_leftSide.Add(i);
}
_rightSide = new List<int>();
for (var i = _corners[1] + _sideSize; i < _corners[3]; i += _sideSize)
{
_rightSide.Add(i);
}
_upSide = new List<int>();
for (var i = _corners[2] + 1; i < _corners[3]; i++)
{
_upSide.Add(i);
}
_inner = new List<int>();
for (var i = 0; i < _sideSize * _sideSize; i++)
{
_inner.Add(i);
}
_inner = _inner.Except(_corners).Except(_downSide).Except(_leftSide).Except(_rightSide).Except(_upSide).ToList();
}
private void InitAdjList()
{
_adjacencyList = new List<int>[_verticesInGraph];
for (var i = 0; i < _verticesInGraph; i++)
{
_adjacencyList[i] = new List<int>();
}
}
private void AddEdge(int from, int to, List<int> remainingOccupiedPositions)
{
if (remainingOccupiedPositions.Contains(from) || remainingOccupiedPositions.Contains(to))
{
return;
}
_adjacencyList[from].Add(to);
}
private void CollectAllPaths(int from, int to)
{
var isVisited = new bool[_verticesInGraph];
var pathList = new List<int> {from};
FindAllPaths(from, to, isVisited, pathList);
}
private void FindAllPaths(int from, int to,
bool[] isVisited,
List<int> localPathList)
{
isVisited[from] = true;
if (from.Equals(to))
{
var path = new List<int>(localPathList);
var originalFrom = path.First();
path.Remove(path.First());
path.Remove(path.Last());
if (path.Count > 0)
{
var con = new Connection(originalFrom, to, path);
if (_connectionsMapping.ContainsKey(originalFrom))
{
var values = _connectionsMapping[originalFrom];
values.Add(con);
_connectionsMapping[originalFrom] = values;
}
else
{
_connectionsMapping[originalFrom] = new List<Connection> {con};
}
}
isVisited[from] = false;
return;
}
foreach (var i in _adjacencyList[from])
{
if (!isVisited[i])
{
localPathList.Add(i);
FindAllPaths(i, to, isVisited,
localPathList);
localPathList.Remove(i);
}
}
isVisited[from] = false;
}
private void GatherCombinations()
{
for (var i = 0; i < _occupiedPositions.Count; i++)
{
var from = _occupiedPositions[i];
for (var j = 0; j < _occupiedPositions.Count; j++)
{
if (i == j) continue;
var to = _occupiedPositions[j];
var remainingOccupiedPositions = new List<int>(_occupiedPositions);
remainingOccupiedPositions.Remove(from);
remainingOccupiedPositions.Remove(to);
InitAdjList();
for (var index = 0; index < _verticesInGraph; index++)
{
if (index == _corners[0])
{
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + _sideSize, remainingOccupiedPositions);
}
else if (index == _corners[1])
{
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + _sideSize, remainingOccupiedPositions);
}
else if (index == _corners[2])
{
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - _sideSize, remainingOccupiedPositions);
}
else if (index == _corners[3])
{
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index - _sideSize, remainingOccupiedPositions);
}
else if (_downSide.Contains(index))
{
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + _sideSize, remainingOccupiedPositions);
}
else if (_leftSide.Contains(index))
{
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + _sideSize, remainingOccupiedPositions);
AddEdge(index, index - _sideSize, remainingOccupiedPositions);
}
else if (_rightSide.Contains(index))
{
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + _sideSize, remainingOccupiedPositions);
AddEdge(index, index - _sideSize, remainingOccupiedPositions);
}
else if (_upSide.Contains(index))
{
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index - _sideSize, remainingOccupiedPositions);
}
else if (_inner.Contains(index))
{
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + _sideSize, remainingOccupiedPositions);
AddEdge(index, index - _sideSize, remainingOccupiedPositions);
}
}
CollectAllPaths(from, to);
}
}
Debug.LogFormat($"values.Count {_connectionsMapping.Values.Sum(value => value.Count)}");
}
public class Connection
{
private readonly int _from;
private readonly int _to;
private readonly List<int> _path;
public Connection(int from, int to, List<int> path)
{
_from = from;
_to = to;
_path = path;
}
public int GetFrom()
{
return _from;
}
public int GetTo()
{
return _to;
}
public List<int> GetPath()
{
return _path;
}
public override string ToString()
{
return $"From {_from} to {_to} via {string.Join(" ", _path)}";
}
}
}
}
