/// A common security method used for online banking is to ask the user for three random characters from a passcode.
/// For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
///
/// The text file, keylog.txt, contains fifty successful login attempts.
///
/// Given that the three characters are always asked for in dorder, analyse the file so as to determine the shortest possible secret passcode of unknown length.
using System;
class Program
{
static void Main()
{
string path = @"keylog.txt";
string[] file = File.ReadAllLines(path);
Dictionary<char, HashSet<char>> graph = new Dictionary<char, HashSet<char>>();
foreach (string line in file)
{
for (int i = 0; i < line.Length; i++)
{
char current = line[i];
if (!graph.ContainsKey(current))
{
graph[current] = new HashSet<char>();
}
for (int j = i + 1; j < line.Length; j++)
{
char next = line[j];
graph[current].Add(next);
}
}
}
HashSet<char> visited = new HashSet<char>();
List<char> result = new List<char>();
foreach (char node in graph.Keys)
{
if (!visited.Contains(node))
{
TopologicalSort(graph, node, visited, result);
}
}
result.Reverse();
string passcode = string.Join("", result);
Console.WriteLine($"Shortest possible secret passcode: {passcode}");
}
static void TopologicalSort(Dictionary<char, HashSet<char>> graph, char node, HashSet<char> visited, List<char> result)
{
visited.Add(node);
if (graph.ContainsKey(node))
{
foreach (char neighbor in graph[node])
{
if (!visited.Contains(neighbor))
{
TopologicalSort(graph, neighbor, visited, result);
}
}
}
result.Add(node);
}
}