Skip to content

Instantly share code, notes, and snippets.

@AdamWhiteHat
Last active January 7, 2023 03:00
Show Gist options
  • Save AdamWhiteHat/eb16e3a1419506389feb0f59975fade9 to your computer and use it in GitHub Desktop.
Save AdamWhiteHat/eb16e3a1419506389feb0f59975fade9 to your computer and use it in GitHub Desktop.
Abelian Sandpile Group Class Arithmetic
/// <summary>Abelian Sandpile Class</summary>
public class SandPile : IEquatable<SandPile>
{
#region static Sandpile Values
public static SandPile Zero = new SandPile(new int[,] { { 2, 1, 2 }, { 1, 0, 1 }, { 2, 1, 2 } }, 4);
public static SandPile One = new SandPile(new int[,] { { 3, 2, 3 }, { 2, 1, 2 }, { 3, 2, 3 } }, 4);
public static SandPile NegativeOne = new SandPile(new int[,] { { 1, 3, 1 }, { 3, 3, 3 }, { 1, 3, 1 } }, 4);
// These can all be constructed from the above three sandpiles.
public static SandPile Two = SandPile.Add(One, One);
public static SandPile Three = SandPile.Add(Two, One);
public static SandPile Four = SandPile.Add(Three, One);
public static SandPile Five = SandPile.Add(Four, One);
public static SandPile Six = SandPile.Add(Five, One);
public static SandPile Seven = SandPile.Add(Six, One);
public static SandPile Eight = SandPile.Add(Seven, One);
public static SandPile NegativeTwo = SandPile.Add(NegativeOne, NegativeOne);
public static SandPile NegativeThree = SandPile.Add(NegativeTwo, NegativeOne);
public static SandPile NegativeFour = SandPile.Add(NegativeThree, NegativeOne);
public static SandPile NegativeFive = SandPile.Add(NegativeFour, NegativeOne);
public static SandPile NegativeSix = SandPile.Add(NegativeFive, NegativeOne);
public static SandPile NegativeSeven = SandPile.Add(NegativeSix, NegativeOne);
public static SandPile NegativeEight = SandPile.Add(NegativeSeven, NegativeOne);
#endregion
#region Public Properties
/// <summary>This represents the n in an n by n grid of tiles.</summary>
public int Dimension;
/// <summary>Represents the angle of repose; the sand stacking height which, when reached, will cause the sand pile to topple. The maximum height of a stable sand pile, then, is ToppleHeight-1.</summary>
public int ToppleHeight;
/// <summary>The tiles of the Dimension-by-Dimension sized board. These values represent the height of the sand stacked at this tile.</summary>
public int[,] Tiles;
#endregion
#region Constructors
public SandPile()
: this(3)
{ }
public SandPile(int dimension)
: this(dimension, 4)
{ }
public SandPile(int dimension, int toppleHeight)
: this(dimension, toppleHeight, SandPile.NewArray(dimension))
{ }
public SandPile(int[,] tiles, int toppleHeight)
: this(tiles.GetLength(0), toppleHeight, tiles)
{ }
public SandPile(int dimension, int toppleHeight, int[,] tiles)
{
Dimension = dimension;
ToppleHeight = toppleHeight;
Tiles = tiles;
if (Tiles.GetLength(0) != this.Dimension || Tiles.GetLength(1) != this.Dimension)
{
throw new ArgumentOutOfRangeException();
}
}
#endregion
#region Static Methods
/// <summary>Adds tow SandPiles together, topples them if needed and then returns the result.</summary>
public static SandPile Add(SandPile left, SandPile right)
{
if (right.Dimension != left.Dimension || left.ToppleHeight != right.ToppleHeight)
{
throw new ArgumentException();
}
int[,] newTiles = SandPile.NewArray(left.Dimension);
for (int x = 0; x < left.Dimension; x++)
{
for (int y = 0; y < left.Dimension; y++)
{
newTiles[x, y] = left.Tiles[x, y] + right.Tiles[x, y];
}
}
return Topple(new SandPile(newTiles, left.ToppleHeight));
}
/// <summary>Iteratively topples all tiles whos sand stack heights are greater than or equals to ToppleHeight, and returns the resulting stable configuration as a new SandPile.</summary>
public static SandPile Topple(SandPile from)
{
SandPile result = new SandPile(from);
bool done = false;
while (!done)
{
for (int x = 0; x < result.Dimension; x++)
{
for (int y = 0; y < result.Dimension; y++)
{
if (result.Tiles[x, y] >= result.ToppleHeight)
{
if (x + 1 < result.Dimension)
{
result.Tiles[x + 1, y]++;
}
if (x - 1 >= 0)
{
result.Tiles[x - 1, y]++;
}
if (y + 1 < result.Dimension)
{
result.Tiles[x, y + 1]++;
}
if (y - 1 >= 0)
{
result.Tiles[x, y - 1]++;
}
result.Tiles[x, y] -= result.ToppleHeight;
}
}
}
done = true;
for (int i = 0; i < result.Dimension; i++)
{
if (Enumerable.Range(0, result.Dimension).Any(index => result.Tiles[i, index] >= result.ToppleHeight))
{
done = false;
break;
}
}
}
return result;
}
#endregion
#region Equality Methods
public static bool Equals(SandPile left, SandPile right)
{
return left.Equals(right);
}
public bool Equals(SandPile other)
{
if (this.Dimension != other.Dimension || this.ToppleHeight != other.ToppleHeight)
{
return false;
}
for (int x = 0; x < this.Dimension; x++)
{
for (int y = 0; y < this.Dimension; y++)
{
if (this.Tiles[x, y] != other.Tiles[x, y])
{
return false;
}
}
}
return true;
}
#endregion
#region Overrides
public override int GetHashCode()
{
return Sanitize(this.ToString()).GetHashCode();
}
/// <summary>Returns a formatted string representation of this SandPile.</summary>
public override string ToString()
{
StringBuilder result = new StringBuilder();
for (int x = 0; x < this.Dimension; x++)
{
for (int y = 0; y < this.Dimension; y++)
{
result.Append($"{Tiles[x, y]} ");
}
result.Append(Environment.NewLine);
}
return result.ToString();
}
#endregion
#region Private Methods
private static int[,] NewArray(int dimension)
{
int[,] result = new int[dimension, dimension];
int x = -1;
while (++x < dimension)
{
int y = -1;
while (++y < dimension)
{
result[x, y] = 0;
}
}
return result;
}
private static string Sanitize(string input)
{
return input.Replace(" ", "").Replace("\r", "").Replace("\n", "");
}
#endregion
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment