AdventOfCode23/Day22/BrickStack.cs

namespace Day22;

public class BrickStack
{
    private readonly List<Brick> _bricks = new List<Brick>();
    private Dictionary<Vec, Brick?> _space = new Dictionary<Vec, Brick?>();
    private Vec _min = Vec.Zero;
    private Vec _max = Vec.Zero;
    
    public BrickStack()
    {
        
    }

    public void Add(Brick brick)
    {
        _bricks.Add(brick);

        _min = Min(_min, brick.Start, brick.End);
        _max = Max(_max, brick.Start, brick.End);
    }

    public void Populate()
    {
        _space = new Dictionary<Vec, Brick?>();
        foreach (var b in _bricks.OrderBy(x => x.MinZ))
        {
            foreach (var p in b.Points())
            {
                if (!_space.TryAdd(p, b))
                {
                    throw new Exception("Unexpected overlap during populate phase");
                }
            }
        }
    }

    public void Collapse()
    {
        foreach (var b in _bricks.OrderBy(x => x.MinZ))
        {
            var newZ = 1L;
            foreach (var p in b.Points())
            {
                var below = p;
                while (below.Z > newZ - 1)
                {
                    var target = _space.GetValueOrDefault(below);
                    if (target == null || target == b)
                    {
                        below = below.Add(Vec.Down);
                    }
                    else
                    {
                        if (below.Z + 1 > newZ)
                        {
                            newZ = below.Z + 1;
                        }

                        break;
                    }
                }
            }

            if (newZ < b.MinZ)
            {
                MoveDown(b, b.MinZ - newZ);
            }
        }
    }

    public void Print()
    {
        for (var y = _min.Y; y <= _max.Y; y++)
        {
            for (var z = _min.Z; z <= Math.Min(_max.Z, 19); z++)
            {
                for (var x = _min.X; x <= _max.X; x++)
                {
                    var brick = _space.GetValueOrDefault(new Vec(x, y, z));
                    if (brick != null)
                    {
                        Console.Write(brick.Label);
                    }
                    else
                    {
                        Console.Write('.');
                    }
                }

                Console.Write(' ');
            }
            
            Console.WriteLine();
        }
    }

    public long CountSafeRemoval()
    {
        var count = 0L;
        foreach (var b in _bricks.OrderBy(x => x.MinZ))
        {
            var above = BricksAbove(b).ToList();
            
            if (above.Count == 0 || above.All(a => BricksBelow(a).Count() >= 2))
            {
                count++;
            }
        }

        return count;
    }

    public long CountAllFalling()
    {
        var supports = new Dictionary<Brick, List<Brick>>();
        var isSupportedBy = new Dictionary<Brick, List<Brick>>();
        
        foreach (var b in _bricks.OrderBy(x => x.MinZ))
        {
            supports.TryAdd(b, new List<Brick>());
            isSupportedBy.TryAdd(b, new List<Brick>());
            foreach (var above in BricksAbove(b))
            {
                supports[b].Add(above);

                isSupportedBy.TryAdd(above, new List<Brick>());
                isSupportedBy[above].Add(b);
            }
        }

        var count = 0L;
        foreach (var b in _bricks.OrderBy(x => x.MinZ))
        {
            // walk "up" the graph to all nodes that only have supports within our "set" starting with the current brick
            var set = new HashSet<Brick>();
            var edge = new List<Brick> { b };
            while (edge.Count > 0)
            {
                foreach (var e in edge)
                {
                    set.Add(e);
                }

                edge = edge.SelectMany(e => supports[e])
                    .Distinct()
                    .Where(above => isSupportedBy[above].Count(below => !set.Contains(below)) == 0)
                    .ToList();
            }

            count += set.Count - 1;
        }

        return count;
    }

    private Vec Min(params Vec[] vectors)
    {
        var x = vectors[0].X;
        var y = vectors[0].Y;
        var z = vectors[0].Z;
        foreach (var v in vectors.Skip(1))
        {
            x = Math.Min(x, v.X);
            y = Math.Min(y, v.Y);
            z = Math.Min(z, v.Z);
        }

        return new Vec(x, y, z);
    }
    
    private Vec Max(params Vec[] vectors)
    {
        var x = vectors[0].X;
        var y = vectors[0].Y;
        var z = vectors[0].Z;
        foreach (var v in vectors.Skip(1))
        {
            x = Math.Max(x, v.X);
            y = Math.Max(y, v.Y);
            z = Math.Max(z, v.Z);
        }

        return new Vec(x, y, z);
    }

    private void MoveDown(Brick brick, long count)
    {
        foreach (var p in brick.Points())
        {
            _space.Remove(p);
        }
        brick.MoveDown(count);
        foreach (var p in brick.Points())
        {
            if (!_space.TryAdd(p, brick))
            {
                throw new Exception("Unexpected overlap during collapse phase");
            }
        }
    }

    private IEnumerable<Brick> BricksAbove(Brick brick)
    {
        return brick.Points()
            .Select(p => _space.GetValueOrDefault(p.Add(Vec.Up)))
            .Where(b => b != null && b != brick)
            .Cast<Brick>()
            .Distinct();
    }
    
    private IEnumerable<Brick> BricksBelow(Brick brick)
    {
        return brick.Points()
            .Select(p => _space.GetValueOrDefault(p.Add(Vec.Down)))
            .Where(b => b != null && b != brick)
            .Cast<Brick>()
            .Distinct();
    }
}