add import & solvermain

1 files changed, 251 insertions, 2 deletions

diff --git a/ColourFlood/Program.cs b/ColourFlood/Program.cs
index 140b88b..ddf5be0 100644
--- a/ColourFlood/Program.cs
+++ b/ColourFlood/Program.cs
@@ -1,9 +1,258 @@
-namespace ColourFlood;
+using System.Text;
+using HtmlAgilityPack;
+
+namespace ColourFlood;
 
 class Program
 {
+    public static void ColourToConsoleColor(Colour colour)
+    {
+        Console.BackgroundColor = colour switch
+        {
+            Colour.Green => ConsoleColor.Green,
+            Colour.Orange => ConsoleColor.Red,
+            Colour.Blue => ConsoleColor.Blue,
+            Colour.Purple => ConsoleColor.DarkMagenta,
+            Colour.Teal => ConsoleColor.Cyan,
+        };
+    }
     static void Main(string[] args)
     {
-        Console.WriteLine("Hello, World!");
+        var doc = new HtmlDocument();
+        doc.Load("test.html");
+        Grid original = new PonderClub().From(doc);
+        
+        Colour[]? best = null;
+        
+        PriorityQueue<(Colour[] history, Grid grid), int> queue = new PriorityQueue<(Colour[] history, Grid grid), int>();
+        
+        queue.Enqueue(([], original), -original.Score);
+
+        while (queue.Count > 0)
+        {
+            var queueItem = queue.Dequeue();
+            handleQueueItem(queueItem.history, queueItem.grid);
+        }
+
+        PrintHistory(best);
+
+        void handleQueueItem(Colour[] history, Grid grid)
+        {
+            foreach (var choice in grid.Possibilities)
+            {
+                var newGrid = new Grid(grid);
+                Colour[] newhistory = [..history, choice];
+                var captures = newGrid.Capture(choice);
+                newGrid.SwitchColour(choice, captures);
+                
+                if (newGrid.Done)
+                {
+                    if (best != null && newhistory.Length >= best.Length) return;
+                
+                    best = newhistory;
+                    PrintHistory(best);
+
+                    Task.Run(() =>
+                    {
+                        foreach (var item in queue.UnorderedItems
+                                     .Where(item => item.Element.history.Length >= best.Length)
+                                     .ToArray())
+                        {
+                            queue.Remove(item.Element, out _, out _);
+                        }
+                    
+                        queue.TrimExcess();
+                    });
+
+                    return;
+                }
+                if (best != null && newhistory.Length >= best.Length) return;
+
+                queue.Enqueue((newhistory, newGrid), -newGrid.Score - captures.Count + newhistory.Length);
+            }
+        }
+    }
+
+    private static void PrintHistory(Colour[]? history)
+    {
+        Console.Write($"{history.Length}: ");
+        foreach (var pick in history)
+        {
+            ColourToConsoleColor(pick);
+            Console.Write("  ");
+        }
+        Console.ResetColor();
+        Console.WriteLine();
+    }
+}
+
+interface Import
+{
+    Grid From(HtmlDocument doc);
+}
+
+class PonderClub : Import
+{
+    public Grid From(HtmlDocument doc)
+    {
+        var gridNode = doc.DocumentNode.SelectSingleNode("""//*[@id="root"]/div/div/div[1]/div/div/div[2]/div/div""");
+
+        var init = gridNode.ChildNodes.Select(cellNode => cellNode.FirstChild.GetClasses().Last() switch
+        {
+            "css-128i23a" => Colour.Green,
+            "css-1husk6m" => Colour.Orange,
+            "css-1nbkhyv" => Colour.Blue,
+            "css-1wib823" => Colour.Purple,
+            "css-tolu00" => Colour.Teal,
+        }).ToArray();
+
+        return new Grid((short)Math.Sqrt(init.Length), init);
+    }
+}
+
+enum Colour : byte
+{
+    Green,
+    Orange,
+    Blue,
+    Purple,
+    Teal
+}
+
+record struct Pos(short X, short Y)
+{
+    public Pos[] Neighbors(short width, short height)
+    {
+        List<Pos> neighbors = new List<Pos>(4);
+        if (Y != 0)
+        {
+            neighbors.Add(this with { Y = (short)(Y - 1) });
+        }
+
+        if (X != 0)
+        {
+            neighbors.Add(this with { X = (short)(X - 1) });
+        }
+
+        if (X != width - 1)
+        {
+            neighbors.Add(this with { X = (short)(X + 1) });
+        }
+
+        if (Y != height - 1)
+        {
+            neighbors.Add(this with { Y = (short)(Y + 1) });
+        }
+        
+        return neighbors.ToArray();
+    }
+}
+
+record struct Grid
+{
+    private static short width;
+    private static short height;
+    private Colour? current;
+    private static readonly Dictionary<Pos, Colour> cells = new Dictionary<Pos, Colour>();
+    private HashSet<Pos> captured;
+
+    public bool Done => cells.Count == captured.Count;
+    public int Score => captured.Count;
+    
+    public IEnumerable<Colour> Possibilities
+    {
+        get
+        {
+            var current = this.current;
+            var captured = this.captured;
+            return cells
+                .Where(kv => kv.Value != current && !captured.Contains(kv.Key))
+                .Select(kv => kv.Value)
+                .Distinct();
+        }
+    }
+
+    public Grid(Grid original)
+    {
+        current = original.current;
+        captured = [..original.captured];
+    }
+    
+    public Grid(short size, Colour[] init) : this(size, size, init) { }
+    
+    public Grid(short width, short height, Colour[] init)
+    {
+        Grid.width = width;
+        Grid.height = height;
+
+        if (width * height != init.Length)
+        {
+            throw new InvalidOperationException("Invalid init");
+        }
+
+        captured = [new (0, 0)];
+
+        var index = 0;
+        for (short y = 0; y < height; y++)
+        {
+            for (short x = 0; x < width; x++)
+            {
+                cells.Add(new(x, y), init[index++]);
+            }
+        }
+
+        var captures = Capture(init[0]);
+        SwitchColour(init[0], captures);
+    }
+
+    public void SwitchColour(Colour newColour, HashSet<Pos> newCaptures)
+    {
+        current = newColour;
+        captured.UnionWith(newCaptures);
+    }
+
+    public HashSet<Pos> Capture(Colour newColour)
+    {
+        if (current == newColour) return [];
+
+        HashSet<Pos> newCaptures = [];
+        Queue<Pos> queue = new Queue<Pos>(captured);
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            foreach (var neighbor in cell.Neighbors(width, height))
+            {
+                if (captured.Contains(neighbor) || newCaptures.Contains(neighbor)) continue;
+
+                if (cells[neighbor] == newColour)
+                {
+                    newCaptures.Add(neighbor);
+                    queue.Enqueue(neighbor);
+                }
+            }
+        }
+        
+        return newCaptures;
+    }
+
+    public void Print()
+    {
+        for (short y = 0; y <= height-1; y++)
+        {
+            for (short x = 0; x <= width-1; x++)
+            {
+                var cell = new Pos(x, y);
+                var colour = cells[cell];
+                if (captured.Contains(cell) && current != null)
+                {
+                    colour = current.Value;
+                }
+                Program.ColourToConsoleColor(colour);
+                Console.Write(new string(' ', 2));
+            }
+            Console.ResetColor();
+            Console.WriteLine();
+        }
+        Console.WriteLine();
     }
 }
\ No newline at end of file