Ross Bamford
3/27/2006 4:18:00 PM
Hmm, this is a tricky one :) This solution is pretty ugly (I've not
seriously tried to clean it up, either) and slow.
There are actually two solutions in here, one that's fast and 'good
enough' for the smaller digit counts, and one that's *very* slow but
gives shorter results with less retesting of codes.
Neither of these are all that much better than simply running through
and checking each code against AlarmKeypad#tested? but then that's to be
expected I guess, perhaps this is why real alarms don't tend to
duplicate that functionality :P
I ran benchmarked tests to get an idea of how it did. The tests are
doing simple sequential tests (seq), sequential using tested? (seq/chk),
the simple/quick(er) way (simple) and the slow, better way (best). Check
out the 'best' time for 4 digit codes - there has to be room for
improvement there :/
### 2 digits, [1,2,3] stops ###
user system total real
seq. 0.010000 0.000000 0.010000 ( 0.005530)
Search space exhausted.
Tested 100 of 100 codes in 300 keystrokes.
39 codes were tested more than once.
seq/chk 0.010000 0.000000 0.010000 ( 0.008893)
Search space exhausted.
Tested 100 of 100 codes in 234 keystrokes.
11 codes were tested more than once.
simple 0.000000 0.000000 0.000000 ( 0.006074)
Search space exhausted.
Tested 100 of 100 codes in 243 keystrokes.
15 codes were tested more than once.
best 0.050000 0.000000 0.050000 ( 0.054995)
Search space exhausted.
Tested 100 of 100 codes in 223 keystrokes.
2 codes were tested more than once.
### 3 digits, [1,2,3] stops ###
user system total real
seq. 0.070000 0.000000 0.070000 ( 0.064838)
Search space exhausted.
Tested 1000 of 1000 codes in 4000 keystrokes.
513 codes were tested more than once.
seq/chk 0.060000 0.000000 0.060000 ( 0.062613)
Search space exhausted.
Tested 1000 of 1000 codes in 2944 keystrokes.
224 codes were tested more than once.
simple 0.090000 0.000000 0.090000 ( 0.086938)
Search space exhausted.
Tested 1000 of 1000 codes in 2960 keystrokes.
223 codes were tested more than once.
best 6.430000 0.050000 6.480000 ( 6.741495)
Search space exhausted.
Tested 1000 of 1000 codes in 2623 keystrokes.
50 codes were tested more than once.
### 4 digits, [1,2,3] stops ###
user system total real
seq. 0.820000 0.020000 0.840000 ( 0.871923)
Search space exhausted.
Tested 10000 of 10000 codes in 50000 keystrokes.
6108 codes were tested more than once.
seq/chk 0.690000 0.010000 0.700000 ( 0.704795)
Search space exhausted.
Tested 10000 of 10000 codes in 33395 keystrokes.
2569 codes were tested more than once.
simple 1.830000 0.030000 1.860000 ( 1.869937)
Search space exhausted.
Tested 10000 of 10000 codes in 33555 keystrokes.
2620 codes were tested more than once.
best 781.350000 5.520000 786.870000 (796.666829)
Search space exhausted.
Tested 10000 of 10000 codes in 28614 keystrokes.
435 codes were tested more than once.
### 5 digits, [1,2,3] stops ###
user system total real
seq. 11.010000 0.140000 11.150000 ( 11.248501)
Search space exhausted.
Tested 100000 of 100000 codes in 600000 keystrokes.
69494 codes were tested more than once.
seq/chk 7.450000 0.060000 7.510000 ( 7.563379)
Search space exhausted.
Tested 100000 of 100000 codes in 371028 keystrokes.
30902 codes were tested more than once.
simple 136.960000 6.250000 143.210000 (145.916674)
Search space exhausted.
Tested 100000 of 100000 codes in 371394 keystrokes.
31105 codes were tested more than once.
best (not tested)