From: Timothy Bennett Date: 2006-03-30T16:17:46+09:00 Subject: Re: [QUIZ] B & E (#72) Hi, I wanted to discuss this problem from a more mathematical perspective. Anyone that's interested, please comment on this, I'm curious what others' thoughts are. It strikes me that there should be a mathematical way to determine the minimum number of presses necessary to cover all key codes. This would of course be based on the code length (n), and the number of stop codes (m). I also believe that attaining the minimum number of strokes requires that there be no duplicated codes, but that having that nice "0 codes were tested more than once" message doesn't guarantee that you have the best solution. For examples, I'm going to talk about the easiest case to think about: n = m = 1. That is, each code is just 1 digit in length, and there is only one stop code (we'll choose 1, but it really doesn't matter). Now, the general formula for the worst case (the brute force just-enter-every-code method, without the tested? check), is (n + 1) * 10 ** n. In this example, the worst case is 20: 01112131415161718191 It is easy to see that the best case here is 19: 0112131415161718191 Now let's switch the example to n = 1, m = 3, where the stop codes are 1, 2, and 3. This is now the best case: 01231415161718191 (length 17) A little bit more experimentation should be enough to convince anyone that the length of the best solution will be 20 - m when n = 1, and m is in the range [1,9]. The formula breaks if m = 10, so I'm just going to throw that out to keep the model simple right now. The 20 in this case is the length of the worst case scenario, so I believe that this can be generalized to worst-case-length - amount-of-overlap The worst-case-length is of course (n + 1) * 10 ** n; I don't think that needs further study. The part that I haven't been able to generalize is the "amount of overlap." For n = 1, we're good, but that's not very interesting, and the formula breaks when n = 2. Take this case: n = 2, m = 1. I worked out a solution by hand, and I don't believe it's possible to go below 271 keystrokes. I haven't been able to figure out a general formula that works for n = 1 and for that n = 2, m = 1 data point. I think it may be based on the number of occurrences of the stop codes in the code set (let's call this number k), but I'm not sure. To be clear on what I mean, for the n = 2 case, the digit 1 appears 20 times in the 00..99 range. This is the same for 2 and 3, so if m = 3, stop codes appear 60 times in the code set. In general, k = m * n * (10 ** (n - 1)) But I can't find a way to work k in, and I've only got those data points to work with. There are a couple of other potential data points, but I don't know if they're valid. For example, my solution found the n = 2, m = 3 case solution with 219 strokes and no overlap. However, I don't know for sure, yet, whether 219 is the correct minimum for that case. I think it probably is, but I don't know. To explain why I'm not sure, take this example for n = 1, m = 1: 000000112131415161718191 Running that through the keypad will produce no duplicate tests, but it's obviously not a minimal solution. So, I can't trust that the program's solution is the true minimum, even if no codes were tested more than once. Anyway, some other possible data points that my program generated (but have not been verified) are: n = 3, m = 1 => 3,439 n = 4, m = 1 => 40,951 For all other cases, my solution didn't manage to avoid duplicate testing. So, that's an outline of what I've figured out so far. If anyone has ideas about how one might predict the length of the ideal solution, speak up :) Tim