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

Comment by Tiago Becerra Paolini

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