ColourFlood/Program.cs 6.9 K · 258 lines · raw · history

1 using System.Text;
2 using HtmlAgilityPack;
3
4 namespace ColourFlood;
5
6 class Program
7 {
8 public static void ColourToConsoleColor(Colour colour)
9 {
10 Console.BackgroundColor = colour switch
11 {
12 Colour.Green => ConsoleColor.Green,
13 Colour.Orange => ConsoleColor.Red,
14 Colour.Blue => ConsoleColor.Blue,
15 Colour.Purple => ConsoleColor.DarkMagenta,
16 Colour.Teal => ConsoleColor.Cyan,
17 };
18 }
19 static void Main(string[] args)
20 {
21 var doc = new HtmlDocument();
22 doc.Load("test.html");
23 Grid original = new PonderClub().From(doc);
24
25 Colour[]? best = null;
26
27 PriorityQueue<(Colour[] history, Grid grid), int> queue = new PriorityQueue<(Colour[] history, Grid grid), int>();
28
29 queue.Enqueue(([], original), -original.Score);
30
31 while (queue.Count > 0)
32 {
33 var queueItem = queue.Dequeue();
34 handleQueueItem(queueItem.history, queueItem.grid);
35 }
36
37 PrintHistory(best);
38
39 void handleQueueItem(Colour[] history, Grid grid)
40 {
41 foreach (var choice in grid.Possibilities)
42 {
43 var newGrid = new Grid(grid);
44 Colour[] newhistory = [..history, choice];
45 var captures = newGrid.Capture(choice);
46 newGrid.SwitchColour(choice, captures);
47
48 if (newGrid.Done)
49 {
50 if (best != null && newhistory.Length >= best.Length) return;
51
52 best = newhistory;
53 PrintHistory(best);
54
55 Task.Run(() =>
56 {
57 foreach (var item in queue.UnorderedItems
58 .Where(item => item.Element.history.Length >= best.Length)
59 .ToArray())
60 {
61 queue.Remove(item.Element, out _, out _);
62 }
63
64 queue.TrimExcess();
65 });
66
67 return;
68 }
69 if (best != null && newhistory.Length >= best.Length) return;
70
71 queue.Enqueue((newhistory, newGrid), -newGrid.Score - captures.Count + newhistory.Length);
72 }
73 }
74 }
75
76 private static void PrintHistory(Colour[]? history)
77 {
78 Console.Write($"{history.Length}: ");
79 foreach (var pick in history)
80 {
81 ColourToConsoleColor(pick);
82 Console.Write(" ");
83 }
84 Console.ResetColor();
85 Console.WriteLine();
86 }
87 }
88
89 interface Import
90 {
91 Grid From(HtmlDocument doc);
92 }
93
94 class PonderClub : Import
95 {
96 public Grid From(HtmlDocument doc)
97 {
98 var gridNode = doc.DocumentNode.SelectSingleNode("""//*[@id="root"]/div/div/div[1]/div/div/div[2]/div/div""");
99
100 var init = gridNode.ChildNodes.Select(cellNode => cellNode.FirstChild.GetClasses().Last() switch
101 {
102 "css-128i23a" => Colour.Green,
103 "css-1husk6m" => Colour.Orange,
104 "css-1nbkhyv" => Colour.Blue,
105 "css-1wib823" => Colour.Purple,
106 "css-tolu00" => Colour.Teal,
107 }).ToArray();
108
109 return new Grid((short)Math.Sqrt(init.Length), init);
110 }
111 }
112
113 enum Colour : byte
114 {
115 Green,
116 Orange,
117 Blue,
118 Purple,
119 Teal
120 }
121
122 record struct Pos(short X, short Y)
123 {
124 public Pos[] Neighbors(short width, short height)
125 {
126 List<Pos> neighbors = new List<Pos>(4);
127 if (Y != 0)
128 {
129 neighbors.Add(this with { Y = (short)(Y - 1) });
130 }
131
132 if (X != 0)
133 {
134 neighbors.Add(this with { X = (short)(X - 1) });
135 }
136
137 if (X != width - 1)
138 {
139 neighbors.Add(this with { X = (short)(X + 1) });
140 }
141
142 if (Y != height - 1)
143 {
144 neighbors.Add(this with { Y = (short)(Y + 1) });
145 }
146
147 return neighbors.ToArray();
148 }
149 }
150
151 record struct Grid
152 {
153 private static short width;
154 private static short height;
155 private Colour? current;
156 private static readonly Dictionary<Pos, Colour> cells = new Dictionary<Pos, Colour>();
157 private HashSet<Pos> captured;
158
159 public bool Done => cells.Count == captured.Count;
160 public int Score => captured.Count;
161
162 public IEnumerable<Colour> Possibilities
163 {
164 get
165 {
166 var current = this.current;
167 var captured = this.captured;
168 return cells
169 .Where(kv => kv.Value != current && !captured.Contains(kv.Key))
170 .Select(kv => kv.Value)
171 .Distinct();
172 }
173 }
174
175 public Grid(Grid original)
176 {
177 current = original.current;
178 captured = [..original.captured];
179 }
180
181 public Grid(short size, Colour[] init) : this(size, size, init) { }
182
183 public Grid(short width, short height, Colour[] init)
184 {
185 Grid.width = width;
186 Grid.height = height;
187
188 if (width * height != init.Length)
189 {
190 throw new InvalidOperationException("Invalid init");
191 }
192
193 captured = [new (0, 0)];
194
195 var index = 0;
196 for (short y = 0; y < height; y++)
197 {
198 for (short x = 0; x < width; x++)
199 {
200 cells.Add(new(x, y), init[index++]);
201 }
202 }
203
204 var captures = Capture(init[0]);
205 SwitchColour(init[0], captures);
206 }
207
208 public void SwitchColour(Colour newColour, HashSet<Pos> newCaptures)
209 {
210 current = newColour;
211 captured.UnionWith(newCaptures);
212 }
213
214 public HashSet<Pos> Capture(Colour newColour)
215 {
216 if (current == newColour) return [];
217
218 HashSet<Pos> newCaptures = [];
219 Queue<Pos> queue = new Queue<Pos>(captured);
220 while (queue.Count > 0)
221 {
222 var cell = queue.Dequeue();
223 foreach (var neighbor in cell.Neighbors(width, height))
224 {
225 if (captured.Contains(neighbor) || newCaptures.Contains(neighbor)) continue;
226
227 if (cells[neighbor] == newColour)
228 {
229 newCaptures.Add(neighbor);
230 queue.Enqueue(neighbor);
231 }
232 }
233 }
234
235 return newCaptures;
236 }
237
238 public void Print()
239 {
240 for (short y = 0; y <= height-1; y++)
241 {
242 for (short x = 0; x <= width-1; x++)
243 {
244 var cell = new Pos(x, y);
245 var colour = cells[cell];
246 if (captured.Contains(cell) && current != null)
247 {
248 colour = current.Value;
249 }
250 Program.ColourToConsoleColor(colour);
251 Console.Write(new string(' ', 2));
252 }
253 Console.ResetColor();
254 Console.WriteLine();
255 }
256 Console.WriteLine();
257 }
258 }