AdventOfCodeDay19.cs

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Text;

namespace AdventOfCodeDay19
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			var ss = new StreamReader ("../../input1.txt");
			var input = new List<string> ();
			string line;

			while ((line = ss.ReadLine ()) != null) {
				input.Add (line);
			}

			var replacements = new List<Replacement> ();
			var regex = new Regex ("^(?<a>.*) => (?<b>.*)$");

			for (var i = 0; i < input.Count - 2; i++) {
				var m = regex.Matches (input [i]) [0];

				replacements.Add (new Replacement{ Value = m.Groups ["b"].Value, Replaces = m.Groups ["a"].Value });
			}

			replacements = replacements.OrderByDescending (a => a.Value.Length).ToList ();

			var molecule = input.Last ();

			var all = FindAllReplacements (new Molecule { Value = molecule, Generation = 0 }, replacements);

			Console.WriteLine ($"part 1: {all.Count()}");
			 

			var gen = FindAllReverseReplacements (new Molecule { Value = molecule, Generation = 0 }, replacements);

			for (var i = 0; i < 10000; i++) {

				gen = GetNextGeneration (gen, replacements);

				if (gen.Count > 0) {

					//Console.WriteLine ($"{i}: {gen.Count}");

					//Console.WriteLine ($"{string.Join("\n", gen.Select(a=>a.Value))}");

					var found = gen.Any (a => a.Value == "e");
					if (found) {
						Console.WriteLine ($"Found a molecule in generation {gen.First().Generation}");
						break;
					}
				}
			}

			Console.WriteLine ("Done");
		}


		public static List<Molecule> FindAllReverseReplacements (Molecule molecule, List<Replacement> replacements)
		{
			var molecules = new List<Molecule> ();

			var r = 0;

			foreach (var replacement in replacements) {
				int idx = 0;
				while ((idx = molecule.Value.IndexOf (replacement.Value, idx)) >= 0) {
					var newone = MakeReplacement (molecule.Value, replacement.Value, replacement.Replaces, idx);
					//Console.WriteLine ($"{newone} : {replacement.Replaces} => {replacement.Value}");
					idx += replacement.Replaces.Length;
					molecules.Add (new Molecule { Value = newone, Generation = molecule.Generation + 1 });
					r += molecules.Count;
				}
			}
			//Console.WriteLine (molecules.First ().Value.Length);
			return molecules;
		}


		public static List<Molecule> GetNextGeneration (List<Molecule> current, List<Replacement> replacements)
		{
			var next = new List<Molecule> ();
			foreach (var s in current) {
				var r = FindAllReverseReplacements (s, replacements);
				next.AddRange (r);
			}
			next = next.OrderBy (a => a.Value.Length).Take (5).ToList ();
			return next;
		}


		public static List<Molecule> FindAllReplacements (Molecule molecule, List<Replacement> replacements)
		{
			var molecules = new List<Molecule> ();

			foreach (var replacement in replacements) {
				int idx = 0;
				while ((idx = molecule.Value.IndexOf (replacement.Replaces, idx)) >= 0) {
					var newone = MakeReplacement (molecule.Value, replacement.Replaces, replacement.Value, idx);
					//Console.WriteLine ($"{newone} : {replacement.Value} => {replacement.Replaces}");
					idx += replacement.Replaces.Length;
					molecules.Add (new Molecule { Value = newone, Generation = molecule.Generation + 1 });
				}
			}
			molecules = molecules.DistinctBy (a => a.Value).ToList ();
			return molecules;
		}


		public static string MakeReplacement (string m, string replaces, string value, int start)
		{
			var sb = new StringBuilder ();
			sb.Append (m.Substring (0, start));
			sb.Append (value);
			sb.Append (m.Substring (start + replaces.Length));
			return sb.ToString ();
		}
	}

	public class Molecule
	{
		public string Value { get; set; }

		public int Generation { get; set; }
	}

	public class Replacement
	{
		public string Value{ get; set; }

		public string Replaces { get; set; }
	}

	public static class Extensions
	{
		public static IEnumerable<TSource> DistinctBy<TSource, TKey>
		(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
		{
			HashSet<TKey> knownKeys = new HashSet<TKey> ();
			foreach (TSource element in source) {
				if (knownKeys.Add (keySelector (element))) {
					yield return element;
				}
			}
		}
	}
}