Advent of Code Day 19–Mutating Molecules

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
}