Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.