# Advent of Code Day 19–Mutating Molecules

December 21. 2015 0 Comments

- Posted in:
- C#
- Advent of Code
- F#
- LINQ

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 More Effective LINQ.