There really are only a few pieces of information you can glean from a single weighing.
1) That a coin is unknown (U),
2) known good (KG),
3) potentially heavy (PH),
4) or potentially light (PH).
No other information can actually be gleaned from a weighing at all. So if you capture this information about every coin involved in a weighing, you've captured all the information there is to know.
The real trick in the search is to be able to set up your recursion so that you search all future possibilities, but keep track of the shortest future path that you found as the recursion ends.
Uglier is knowing when to recurse and when not to. You obviously don't want to recurse when you're down to a single coin you haven't been able to prove good. But you also don't want to recurse when the weighing can't gain you more useful but non-contradictory information.
(For example, you could weigh two piles of three coins, see that they're balanced, and mark them up as good. Any possible outcome from doing the same weighing again as a future weighing on the same branch must result in the same answer, so there's no point trying. If it _did_ come out differently, you'd have a contradiction. So somehow, recursing down the path of trying that weighing must be avoided.)
I think I'm going to give this more thought. |
