Day 19 - Advent of Code 2015
adventofcode.com

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?

  • Amy@piefed.blahaj.zoneEnglish
    2·
    5 days ago

    Oh gosh, I remember this one. Working backwards is a good idea. In addition, you can just look at the start of the string when trying substitutions. I don’t think that’s valid in general, but it worked for me in this case.

    There’s another trick you can do if you look carefully at the input data. I didn’t implement it in my solution because I didn’t spot it myself, but it essentially makes the problem trivial.

    • owenfromcanada@lemmy.caOP
      2·
      5 days ago

      Thanks for your thoughts! For the input data, I did notice that every substitution goes from 1 element to 2-8 elements. I suppose I could take that into account, and order them from “most efficient” to “least efficient”, and that way I might be able to stop iterating earlier?

      I also haven’t looked into whether there are any combinations that are impossible to build from (or inversely to break down into e).

      Those two are probably good avenues to try.

      Thanks again!

      • Amy@piefed.blahaj.zoneEnglish
        2·
        5 days ago

        That’s not quite the key observation…

        spoiler

        Many of the productions end in an element which does not appear on the left-hand side. That acts as a flag which tells you where to look for substitutions.