Optimizing a c# solution (algorithm)
Hi, our professor gave us this problem for uni https://observablehq.com/@mpcowan/day-6-universal-orbit-map as a challenge (not graded), and asked us if we can optimize the solution in any way. Do you guys have any opinion on how to do it? I have so far thought about caching the results of recursion but on further analysis, I realized that the recursion call never really repeats, so caching doesn't make sense. I am also reading up more about dynamic programming and matrix exponentiation but I am not sure how else I can optimize this. Do you guys have any hints or any idea?
Observable
Day 6: Universal Orbit Map
You've landed at the Universal Orbit Map facility on Mercury. Because navigation in space often involves transferring between orbits, the orbit maps here are useful for finding efficient routes between, for example, you and Santa. You download a map of the local orbits (your puzzle input). Except for the universal Center of Mass (COM), every obj...
4 Replies
The code seems to be JS, so am already big optimization would be using C#
I already converted it to c# here https://github.com/AnmolSinha1201/Orbit but apparently it can be improved further in terms of algorithm
GitHub
GitHub - AnmolSinha1201/Orbit
Contribute to AnmolSinha1201/Orbit development by creating an account on GitHub.
So far I have read up on dynamic programing, but since the results produced in one recursion call is never utilized again, I believe that's not the best approach.
I have also tried reading up on some matrix exponentiation, but since the result depends on variable number of children, I can't think of any idea to optimize this
algorithmically, it is optimal (it can at best be linear, because you have to go through all inputs)
if you only need to analyze the COM node, you could make it only go through the input once, but I don't think that'd even be faster
when it comes to your actual code, you're doing some redundant operations which will affect performance and memory usage, but not the complexity
for example, you don't need to store the name in the node
you can replace contains key and add with a single operation with
CollectionsMarshal.ForgotTheName
and also not using linq