From cbc44625ef05239f8c4c5c35583a62d44aea805b Mon Sep 17 00:00:00 2001 From: Marijn Besseling Date: Sat, 16 May 2026 23:13:15 +0200 Subject: add import & solver --- .gitignore | 3 +- ColourFlood/ColourFlood.csproj | 9 ++ ColourFlood/Program.cs | 253 ++++++++++++++++++++++++++++++++++++++++- 3 files changed, 262 insertions(+), 3 deletions(-) diff --git a/.gitignore b/.gitignore index add57be..f400df3 100644 --- a/.gitignore +++ b/.gitignore @@ -2,4 +2,5 @@ bin/ obj/ /packages/ riderModule.iml -/_ReSharper.Caches/ \ No newline at end of file +/_ReSharper.Caches/ +.idea/ \ No newline at end of file diff --git a/ColourFlood/ColourFlood.csproj b/ColourFlood/ColourFlood.csproj index ee5276c..9b4368e 100644 --- a/ColourFlood/ColourFlood.csproj +++ b/ColourFlood/ColourFlood.csproj @@ -9,4 +9,13 @@ true + + ARM64 + none + + + + + + 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 neighbors = new List(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 cells = new Dictionary(); + private HashSet captured; + + public bool Done => cells.Count == captured.Count; + public int Score => captured.Count; + + public IEnumerable 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 newCaptures) + { + current = newColour; + captured.UnionWith(newCaptures); + } + + public HashSet Capture(Colour newColour) + { + if (current == newColour) return []; + + HashSet newCaptures = []; + Queue queue = new Queue(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 -- cgit v1.2.3