Win a copy of Beginning Java 17 Fundamentals: Object-Oriented Programming in Java 17 this week in the Java in General forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

AoC 2021 - Day 14 Solutions (Spoilers!)

 
Saloon Keeper
Posts: 13500
305
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So I believe that every substitution rule is the root of a tree of substitution rules that apply to the resulting polymer after the parent substitution rule has been applied.

For instance, the substitution rule "CH -> B" is the parent of two substitution rules "CB -> H" and "BH -> H".

Now, the child of a substitution rule may already appear somewhere further up in the tree, so link these nodes back to their ancestor rule to form a graph of rules.

The graph of rules then models a nondeterministic finite state automaton in which each state transition increments the count of the inserted element. If the automaton is in the same state more than once (which means it is applying the rule to different substrings of the polymer), you can simply combine the states by summing their element counts. This means that for each step, you have to apply each rule at most once, so it complete 40 steps lightning fast.

I'm sure there's a much simpler algorithm that is easier to explain, but this makes sense in my head and it's what I'm going to try tomorrow.
 
Marshal
Posts: 5222
323
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sounds like an interesting approach. I'm curious to hear whether it works in practice.

I had two hurdles to overcome.

1. My initial solution to part 1 was maintaining a string of the resulting polymer after each step, which worked ok for 10 steps but consumed all available memory before reaching 40 steps.

To resolve this I discovered that I could determine the character count by working on polymer pairs at a time and accumulating a total count without having to maintain the full polymer string for each step

2. Memory problems solved, I now discovered that it took too long to complete. That was solved with memoization. However, I was stumped for hours because I was keeping a map of polymer pairs to character counts as my cache, but then realised that the cache key had to be a composite of the polymer pair and the required rule application steps.

That's probably explained very poorly, but hopefully you get the gist.
 
Bartender
Posts: 4747
184
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Quite quiet for day 14. I guess part B was the hardest one sofar.

Just finished it, finally had some time to implement my idea. However, it was more involved than I expected.

First: it ran part B in just 0.17 seconds, on my trusty 10 year old laptop.

The idea was using a frequency map for each level 0, 1, 2, ..., 40, and so the code had only to do with calculating a few Maps, and presenting the result for level 40. The map being of the form Map<Integer, Map<Duo, Long>>, where Duo is a class consisting of two Strings (had I java 17, I would have used a record for this)

You must use Longs in the frequency map, because I had these frequencies at level 40 (but the outcome is different for other users):

max freq: letter N, 10.159.740.693.876
min freq: letter F,    156.927.414.539
and delta was       10.002.813.279.337


If anyone is interested in the method and/or code, let me know.


 
reply
    Bookmark Topic Watch Topic
  • New Topic