I used a reverse lookup hash table. Each key was the name of a node, and its value was the name of the parent node. This was taking advantage of the way the nodes only ever had one parent.
Distances between nodes was just the sum of the distance between them and their first common ancestor. First common ancestor was calculated by walking one of the nodes all the way up to root, collecting the node names, then walk the other one up until you find a name that's in the other list.
I'd like to say I was being clever, but I definitely stumbled across this one.
walk the other one up until you find a name that's in the other list
Oh, but that IS clever. At a glance though, you're stepping through the first list for each check as you walk up the second - is there a more efficient way to perform that check, or am I overestimating the computational hit? Not that I'd expect it to practically matter...
is there a more efficient way to perform that check, or am I overestimating the computational hit?
Yeah, it's definitely not optimal. Repeatedly 'finding' in a list is annoying. If I was trying to optimize...
You could store the 'list' as yet another hash table, keying off the node name with values set to the distance, as there's no need to store that information as an ordered sequence if you save the distance. That way you could query it to find out if a node is present, step forward on the other path when its not, or add the distance returned from the hash to the distance travelled from the other path. That's a bit neater.
I'm beginning to wonder whether I just try to solve everything with hashes...
is there a more efficient way to perform that check, or am I overestimating the computational hit?
Yeah, it's definitely not optimal. Repeatedly 'finding' in a list is annoying. If I was trying to optimize...
You could store the 'list' as yet another hash table, keying off the node name with values set to the distance, as there's no need to store that information as an ordered sequence if you save the distance. That way you could query it to find out if a node is present, step forward on the other path when its not, or add the distance returned from the hash to the distance travelled from the other path. That's a bit neater.
I'm beginning to wonder whether I just try to solve everything with hashes...
Boring as it's been, being forced to drill data structures in C++ has admittedly been pretty helpful. Nothing is complicated.
Willing to share how you solved it? I saw this solution when I first read the problem and didn't spend much time thinking of other strategies.
Willingly.
I used a reverse lookup hash table. Each key was the name of a node, and its value was the name of the parent node. This was taking advantage of the way the nodes only ever had one parent.
Distances between nodes was just the sum of the distance between them and their first common ancestor. First common ancestor was calculated by walking one of the nodes all the way up to root, collecting the node names, then walk the other one up until you find a name that's in the other list.
I'd like to say I was being clever, but I definitely stumbled across this one.
Oh, but that IS clever. At a glance though, you're stepping through the first list for each check as you walk up the second - is there a more efficient way to perform that check, or am I overestimating the computational hit? Not that I'd expect it to practically matter...
Yeah, it's definitely not optimal. Repeatedly 'finding' in a list is annoying. If I was trying to optimize...
You could store the 'list' as yet another hash table, keying off the node name with values set to the distance, as there's no need to store that information as an ordered sequence if you save the distance. That way you could query it to find out if a node is present, step forward on the other path when its not, or add the distance returned from the hash to the distance travelled from the other path. That's a bit neater.
I'm beginning to wonder whether I just try to solve everything with hashes...
Yeah, it's definitely not optimal. Repeatedly 'finding' in a list is annoying. If I was trying to optimize...
You could store the 'list' as yet another hash table, keying off the node name with values set to the distance, as there's no need to store that information as an ordered sequence if you save the distance. That way you could query it to find out if a node is present, step forward on the other path when its not, or add the distance returned from the hash to the distance travelled from the other path. That's a bit neater.
I'm beginning to wonder whether I just try to solve everything with hashes...
It's hashes all the way down...