AOC2018 day 23 part 2

day23-2.linq

<Query Kind="Program">
  <Namespace>static System.Math</Namespace>
</Query>

struct Point3 {
    public int X;
    public int Y;
    public int Z;
    public Point3(int x, int y, int z) => (X, Y, Z) = (x, y, z);
    public int ManhattanDist(Point3 other) => Abs(X - other.X) + Abs(Y - other.Y) + Abs(Z - other.Z);
    public override string ToString() => $"[{X}, {Y}, {Z}]";
}

// octahedral - inclusive bounds
struct Bot {
    public Point3 Position;
    public int Radius;
    public Bot(int x, int y, int z, int radius) => (Position, Radius) = (new Point3(x, y, z), radius);
}

// cubic - half-open ranges
abstract class OctreeNode {
    public Point3 Center { get; }
    public int Radius { get; }
    public OctreeNode(Point3 center, int radius) {
        if ((radius & radius - 1) > 0) throw new ArgumentOutOfRangeException(nameof(radius), "radius must be power of 2");
        (Center, Radius) = (center, radius);
    }
    public bool BotRangeOverlaps(Bot bot) {
        int Clamp(int val, int min, int max) => Min(Max(val, min), max - 1);
        var nearest = new Point3(
            Clamp(bot.Position.X, Center.X - Radius, Center.X + Radius),
            Clamp(bot.Position.Y, Center.Y - Radius, Center.Y + Radius),
            Clamp(bot.Position.Z, Center.Z - Radius, Center.Z + Radius));
        return bot.Position.ManhattanDist(nearest) <= bot.Radius;
    }
    public abstract int MaxBotOverlaps { get; }
    public abstract IEnumerable<LeafNode> GetLeaves();
}

class LeafNode : OctreeNode {
    public IList<Bot> BotOverlaps { get; private set; }
    public ParentNode? Parent { get; }
    public LeafNode(ParentNode? parent, Point3 center, int radius, IList<Bot> bots) : base(center, radius) {
        Parent = parent;
        BotOverlaps = bots.Where(BotRangeOverlaps).ToList();
    }
    public override int MaxBotOverlaps => BotOverlaps.Count;
    public override IEnumerable<LeafNode> GetLeaves() => new[] { this };
    public ParentNode Split() {
        if (Radius == 1) throw new InvalidOperationException("can't split, already 1-radius");
        var result = new ParentNode(Center, Radius, BotOverlaps);
        if (Parent != null) Parent.Children[Array.IndexOf(Parent.Children, this)] = result;
        return result;
    }
}

class ParentNode : OctreeNode {
    public OctreeNode[] Children { get; set; }
    public ParentNode(Point3 center, int radius, IList<Bot> bots) : base(center, radius) {
        int half = radius / 2;
        Children = new OctreeNode[] {
            /* -x-y-z */ new LeafNode(this, new Point3(center.X - half, center.Y - half, center.Z - half), half, bots),
            /* -x-y+z */ new LeafNode(this, new Point3(center.X - half, center.Y - half, center.Z + half), half, bots),
            /* -x+y-z */ new LeafNode(this, new Point3(center.X - half, center.Y + half, center.Z - half), half, bots),
            /* -x+y+z */ new LeafNode(this, new Point3(center.X - half, center.Y + half, center.Z + half), half, bots),
            /* +x-y-z */ new LeafNode(this, new Point3(center.X + half, center.Y - half, center.Z - half), half, bots),
            /* +x-y+z */ new LeafNode(this, new Point3(center.X + half, center.Y - half, center.Z + half), half, bots),
            /* +x+y-z */ new LeafNode(this, new Point3(center.X + half, center.Y + half, center.Z - half), half, bots),
            /* +x+y+z */ new LeafNode(this, new Point3(center.X + half, center.Y + half, center.Z + half), half, bots),
        };
    }
    public override int MaxBotOverlaps => Children.Max(c => c.MaxBotOverlaps);
    public override IEnumerable<LeafNode> GetLeaves() => Children.SelectMany(c => c.GetLeaves());
}

void Main() {
    var bots = (
        from line in File.ReadLines(Util.CurrentQueryPath.Replace(".linq", ".txt"))
        let vals = Regex.Matches(line, "-?\\d+").Cast<Match>().Select(m => int.Parse(m.Value)).ToArray()
        select new Bot(vals[0], vals[1], vals[2], vals[3])
    ).ToList();

    int radius = 1, largest = bots
        .Select(b => b.Position)
        .SelectMany(p => new[] { Abs(p.X), Abs(p.Y), Abs(p.Z) })
        .Max();
    for (; radius <= largest; radius <<= 1) ; // smallest larger power of 2
    ParentNode root = new LeafNode(null, default, radius, bots).Split();
    int maxOverlaps = int.MaxValue;
    while (true) {
        maxOverlaps = root.MaxBotOverlaps;
        var candidates = root.GetLeaves().Where(leaf => leaf.MaxBotOverlaps == maxOverlaps);
        if (candidates.All(c => c.Radius == 1)) break;
        foreach (var c in candidates) {
            if (c.Radius > 1) c.Split();
        }
    }
    int result = root.GetLeaves()
        .Where(leaf => leaf.MaxBotOverlaps == maxOverlaps)
        .Min(hotspot => bots
            .Where(hotspot!.BotRangeOverlaps)
            .Max(b => b.Position.ManhattanDist(default) - b.Radius));
    Console.WriteLine("Part 2: {0}", result);
}