-
Notifications
You must be signed in to change notification settings - Fork 0
/
20-1.linq
103 lines (93 loc) · 3.55 KB
/
20-1.linq
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
<Query Kind="Program">
<NuGetReference>Dijkstra.NET</NuGetReference>
<Namespace>Dijkstra.NET.Graph</Namespace>
<Namespace>Dijkstra.NET.Graph.Exceptions</Namespace>
<Namespace>Dijkstra.NET.Graph.Simple</Namespace>
<Namespace>Dijkstra.NET.PageRank</Namespace>
<Namespace>Dijkstra.NET.ShortestPath</Namespace>
</Query>
void Main()
{
Directory.SetCurrentDirectory(Path.GetDirectoryName(Util.CurrentQueryPath));
string[] inputLines = System.IO.File.ReadAllLines("20.txt");
Dictionary<string, List<(int X, int Y)>> portals = new Dictionary<string, List<(int X, int Y)>>();
Dictionary<(int X, int Y), uint> points = new Dictionary<(int X, int Y), uint>();
Graph<(int X, int Y), string> graph = new Graph<(int X, int Y), string>();
for (int y = 0; y < inputLines.Length; y++)
{
for (int x = 0; x < inputLines[0].Length; x++)
{
char c = inputLines[y][x];
if (c == '.')
{
uint n = graph.AddNode((x, y));
points.Add((x, y), n);
}
}
}
string CAPS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for (int y = 0; y < inputLines.Length; y++)
{
for (int x = 0; x < inputLines[0].Length; x++)
{
char c = inputLines[y][x];
if (c == '.')
{
uint point = points[(x, y)];
var adjacent = GetAdjacent(x, y);
foreach (var a in adjacent.Where(adj => adj.C == '.'))
{
graph.Connect(point, points[(a.X, a.Y)], 1, string.Empty);
}
}
if (CAPS.Contains(c))
{
var adjacent = GetAdjacent(x, y);
if (adjacent.Any(a => a.C == '.') && adjacent.Any(a => CAPS.Contains(a.C)))
{
var portal = adjacent.Single(a => a.C == '.');
var ch = adjacent.Single(a => CAPS.Contains(a.C));
string name = new string(new char[] { c, ch.C }.OrderBy(c => c).ToArray());
if (!portals.ContainsKey(name)) portals.Add(name, new List<(int X, int Y)>());
portals[name].Add((portal.X, portal.Y));
}
}
}
}
foreach (var portal in portals.Where(p => p.Value.Count == 2))
{
uint a = points[(portal.Value[0].X, portal.Value[0].Y)];
uint b = points[(portal.Value[1].X, portal.Value[1].Y)];
graph.Connect(a, b, 1, string.Empty);
graph.Connect(b, a, 1, string.Empty);
}
uint start = points[(portals["AA"][0].X, portals["AA"][0].Y)];
uint end = points[(portals["ZZ"][0].X, portals["ZZ"][0].Y)];
var path = graph.Dijkstra(start, end);
path.Distance.Dump();
List<(int X, int Y, char C)> GetAdjacent(int x, int y)
{
List<(int X, int Y, char C)> adjacent = new List<(int X, int Y, char C)>();
if (x > 0) // Left
{
char c = inputLines[y][x-1];
adjacent.Add((x-1, y, c));
}
if (x < inputLines[0].Length-1) // Right
{
char c = inputLines[y][x+1];
adjacent.Add((x+1, y, c));
}
if (y > 0) // Up
{
char c = inputLines[y-1][x];
adjacent.Add((x, y-1, c));
}
if (y < inputLines.Length-1) // Down
{
char c = inputLines[y+1][x];
adjacent.Add((x, y+1, c));
}
return adjacent;
}
}