Re: Problem 185
Posted: Thu Aug 02, 2012 7:27 pm
I just solved it but continued to play around with it to see if I could reduce the runtime. Against my own intuition (or logic? because it must have been intuition that made me try), I arranged the attempts in descending order of correct digits. This reduced the runtime by a factor of (almost) 10! From 2.67s to 275ms.
It would seem to me that 3 attempts with one correct digit each give you more information that helps reduce search space than one attempt with 3 correct digits. Can someone PM me and help me understand this 'paradox'? I'll use the discussion to write a detailed post on the Problem's Forum.
It would seem to me that 3 attempts with one correct digit each give you more information that helps reduce search space than one attempt with 3 correct digits. Can someone PM me and help me understand this 'paradox'? I'll use the discussion to write a detailed post on the Problem's Forum.
, I think the reason is that if there is just one correct digit, then there are only 16 possibilities. However, if there are three correct digits, then there are 560 possibilities. So by starting your tree at the top with the minimal amount of branches, your depth search is much lower. That's my guess anyways.