Back to General discussions forum
I've been staring at this for a good bit now... I verified by hand that the roads my program picked actually connected all the villages and that the sum of their costs matches what my program outputted... have no idea what's wrong.
Expected: 662841 My Result: 660195
I couldn't fit the input nor roads in this post whilst having it formatted as code. Pasted it here: https://pastebin.com/KgU5ZpQN
Wait a minute... I've just realized that the "Expected" has a higher savings than mine. Okay, I'm thinking then that my program simply didn't find the optimal solution. For some reason I was thinking my result was better.
Okay, removing an optimization I had put in place fixed it.
That's curious :) I recollect great small book on java by Joshua Bloch (one of java founding fathers) - there was one chapter, like Don't optimize it until you know it's necessary - and the next chapter like Don't haste with optimization even if you think it's necessary. Though my experience hints it's a bit exaggeration, really we often fall into troubles by sophisticating our solutions more than needed :)
If you would like I can use magic button delete
on this thread.
If you would like I can use magic button delete on this thread.
I don't mind one way or the other.
Don't optimize it until you know it's necessary... Don't haste with optimization even if you think it's necessary
Certainly not an uncommon sentiment. The more common phrase I hear is Premature optimization is the root of all evil.
The full quote from Donald Knuth's "The Art of Computer Programming" goes: "The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming."
Oh, thanks for sharing the source (Knuth) - I never had a heart to read him whole, only fragments - and since it is a grain of wisdom, let me just update the thread title then :)