Help with an old one...

Okay, so I'm almost a decade behind on this...

But I only found out about AoC this year. So I'm gradually going through the backlog. And this is the first one that has left me clueless about a reasonable approach.

https://adventofcode.com/2015/day/19

I'm on part 2 of this problem (reconstructing the molecule in the least number of steps). So far, I've figured...

• I need to work "backwards" (going from the target molecule down to e in the fewest steps possible) in order to bound the problem
• Tried brute forcing it this way, way too inefficient
• So I tried limiting the maximum number of steps--even at 10 steps max, I only make it through a small fraction in several minutes
• I tried rewriting my recursive function as a while loop, didn't help

Things I could try:

• use more efficient data types (I'm using Python and doing slicing, not sure if changing that would make a difference)
• represent the formulae in some other format (not sure what would be better)
• doing something less "brute-force-y", not sure what that would be

Anyone willing to offer any pointers?