# Advent of Code Day 19–Mutating Molecules

December 21. 2015 Posted in:

Today’s challenge was certainly a tricky one, with the brute force solution effectively ruled out due to how long it would take. I did just about manage to get my 2 goal stars though – find out how by watching the video:

I actually tackled this in F# first. My solution to part a worked fine, but my algorithms for part b were too slow to solve the real input, leaving me looking elsewhere for inspiration. With limited time available I decided against implementing my own A* solution and borrow a trick from someone else. Judging by the subreddit, it seems many people found shortcuts or interesting properties of the input data allowing the search space to be reduced.

```
let mutate (sq:string) (replacements:(string*string) list) = seq {
for pos in [0 .. sq.Length - 1] do
for (a,b) in replacements do
if sq.Substring(pos).StartsWith(a) then
yield sq.Substring(0,pos) + b + sq.Substring(pos+a.Length)
}
let problemData = "day19.txt" |> File.ReadAllLines
let replacements =
problemData
|> Seq.map (fun s -> s.Split(' '))
|> Seq.filter (fun a -> a.Length = 3)
|> Seq.map (fun [|a;b;c|] -> (a,c))
|> Seq.toList
let medicineMolecule = problemData.[problemData.Length - 1]
mutate medicineMolecule replacements |> Seq.distinct |> Seq.length |> printfn "a: %d" // 509
let rand = new System.Random()
let swap (a: _[]) x y =
let tmp = a.[x]
a.[x] <- a.[y]
a.[y] <- tmp
// shuffle an array (in-place)
let shuffle a =
Array.iteri (fun i _ -> swap a i (rand.Next(i, Array.length a))) a
// What-a-baller algorithm
// https://www.reddit.com/r/adventofcode/comments/3xflz8/day_19_solutions/cy4cu5b
let search mol (reps:(string*string)[]) =
let mutable target = mol
let mutable mutations = 0
while not (target = "e") do
let mutable tmp = target
for a, b in reps do
let index = target.IndexOf(b)
if index >= 0 then
target <- target.Substring(0, index) + a + target.Substring(index + b.Length)
mutations <- mutations + 1
if tmp = target then
target <- mol
mutations <- 0
shuffle reps
mutations
search medicineMolecule (replacements |> List.toArray) |> printfn "b: %d" // 195
// note the search algorithm is not guaranteed to pick out the shortest solution:
search "XXXX" ([("y","XX");("e","yy");("e","XXXX")] |> List.toArray) |> printfn "broken: %d"
search "XXXX" ([("y","XX");("e","yy");("e","XXXX")] |> List.rev |> List.toArray) |> printfn "broken: %d"
```

And here’s a C# version, taking pretty much the same approach:

```
IEnumerable<string> Mutate(string sq, IEnumerable<string[]> replacements)
{
return from pos in Enumerable.Range(0, sq.Length)
from rep in replacements
let a = rep[0]
let b = rep[1]
where sq.Substring(pos).StartsWith(a)
select sq.Substring(0,pos) + b + sq.Substring(pos+a.Length);
}
public static IEnumerable<T> Shuffle<T>(IEnumerable<T> source)
{
Random rnd = new Random();
return source.OrderBy<T, int>((item) => rnd.Next());
}
public int Search (string molecule, IEnumerable<string[]> replacements)
{
var target = molecule;
var mutations = 0;
while (target != "e")
{
var tmp = target;
foreach (var rep in replacements)
{
var a = rep[0];
var b = rep[1];
var index = target.IndexOf(b);
if (index >= 0)
{
target = target.Substring(0, index) + a + target.Substring(index + b.Length);
mutations++;
}
}
if (tmp == target)
{
target = molecule;
mutations = 0;
replacements = Shuffle(replacements).ToList();
}
}
return mutations;
}
void Main()
{
var problemData = File.ReadAllLines("day19.txt");
var replacements = problemData
.Select(s => s.Split(' '))
.Where(a => a.Length == 3)
.Select(a => new[] { a[0], a[2] })
.ToList();
var medicineMolecule = problemData[problemData.Length - 1];
Mutate(medicineMolecule,replacements)
.Distinct()
.Count()
.Dump("a"); // 509
Search(medicineMolecule, replacements)
.Dump("b"); // 195
}
```

Want to learn more about LINQ? Be sure to check out my Pluralsight course LINQ Best Practices.

## Comments

And I have got here because I was trying this problem today. One would imagine that randomly trying different operations would be the slowest way, but it actually worked much faster than any of the search algorithms I tried to come up with (that just kept running forever).

This is a case that I even though I can understand what it is being done, I just can't understand why not only it works, but also it works in a fraction of second. Maybe the input data was designed to work that way, or there was some sort of unintentional weakness in its generation.

But it still is quite cool indeed!

Tiago Becerra Paolini