«

I understand now, here is my modified solution, it does work a bit
better.

<code>

all_possible = ""

10.times do |key1| 10.times do |key2|
10.times do |key3| 10.times do |key4|
current_code = Array.new
current_code << key1 << key2 << key3 << key4
next if all_possible =~ /#{current_code.to_s}(1|2|3)/
left, left_over = Array.new( current_code ), Array.new
right, right_over = Array.new( current_code ), Array.new
while true do
left_over << left.shift
right_over.insert( 0, right.pop )
if left.length == 0
if key1 == 0
all_possible += current_code.to_s + "1"
elsif key1 == 1
all_possible += current_code.to_s + "2"
else
all_possible += current_code.to_s + "3"
end
break
elsif all_possible =~ /^#{left.to_s}(1|2|3)/
all_possible = left_over.to_s + all_possible
break
elsif all_possible =~ /#{right.to_s}$/
if key1 == 0
all_possible += right_over.to_s + "1"
elsif key1 == 1
all_possible += right_over.to_s + "2"
else
all_possible += right_over.to_s + "3"
end
break
end
end
end end
end end

print "string length: ", all_possible.length, "\n"

</code>

On Mar 29, 2006, at 3:44 AM, Ross Bamford wrote:

> Probably a bit late on (sorry) but this is a cleaned up version that
> does much the same and is marginally quicker.

Thanks Ross!

--Apple-Mail-2-25062225
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

I apologize for the 11th hour solution; this week was busy. It took
me a while to come up with an algorithm that would actually produce
fewer keystrokes than the naive just write-out-every-code-so-long-as-
it-isn't-already-tested solution in every case. After trying a few
(I believe 3 is the number) poor solutions, I was getting frustrated,
so I figured I'd just try to work through it backwards. This worked
out rather well, I think (it beats the naive solution by over 70,000
strokes on the 5-digit, 3-stop case). It was pretty fun, too: I
actually had a reason to use lambda and shift (which I've never used
before), as well as inject (which I've only used once before).

Of course, it takes a while to run (the 5 digit, 3 stop code case
took nearly 40 minutes on a dual 2.7GHz PowerMac G5), so I'm
providing the output as well as the code.

So, here're my results:
user system total real
One stop digit:

2 digits 0.010000 0.000000 0.010000 ( 0.006755)
Search space exhausted.
Tested 100 of 100 codes in 271 keystrokes.
0 codes were tested more than once.
================================================== ==========
3 digits 0.110000 0.000000 0.110000 ( 0.132552)
Search space exhausted.
Tested 1000 of 1000 codes in 3439 keystrokes.
0 codes were tested more than once.
================================================== ==========
4 digits 9.580000 0.260000 9.840000 ( 11.005426)
Search space exhausted.
Tested 10000 of 10000 codes in 40951 keystrokes.
0 codes were tested more than once.
================================================== ==========
5 digits 1208.900000 23.850000 1232.750000 (1439.590285)
Search space exhausted.
Tested 100000 of 100000 codes in 468682 keystrokes.
46 codes were tested more than once.
================================================== ==========

Three stop digits:

2 digits 0.010000 0.000000 0.010000 ( 0.005834)
Search space exhausted.
Tested 100 of 100 codes in 219 keystrokes.
0 codes were tested more than once.
================================================== ==========
3 digits 0.170000 0.000000 0.170000 ( 0.196276)
Search space exhausted.
Tested 1000 of 1000 codes in 2545 keystrokes.
4 codes were tested more than once.
================================================== ==========
4 digits 16.580000 0.300000 16.880000 ( 19.149404)
Search space exhausted.
Tested 10000 of 10000 codes in 28105 keystrokes.
96 codes were tested more than once.
================================================== ==========
5 digits 1910.240000 27.430000 1937.670000 (2240.60393
Search space exhausted.
Tested 100000 of 100000 codes in 299559 keystrokes.
1517 codes were tested more than once.
================================================== ==========


My code is attached, along with alarm_keypad.rb (which contains the
AlarmKeypad class).

Tim


--Apple-Mail-2-25062225
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0755;
x-mac-creator=454D4178;
name="mirror_bne.rb"
Content-Disposition: attachment;
filename=mirror_bne.rb

#!/usr/bin/env ruby -w

require 'alarm_keypad'
require 'benchmark'

def crack_code (code_length, stop_digits)

# This is the weak part of the algorithm (in the case of there being more than 1 stop digit)
# Unfortunately, I don't have the time right now to write something better than a random
# selection.
stop_digit = lambda { stop_digits[rand(stop_digits.size)].to_s }

pad = AlarmKeypad.new code_length, stop_digits

# Work with codes with lots of stop digits in them first.
all_codes = ("0"*code_length.."9"*code_length).to_a.sort_by{|c | num_of_stop_digs c, stop_digits }.reverse

# This algorithm works backwards, so we start with a stop digit, followed by a code.
# You may notice that this doesn't reverse the codes themselves, which means that
# the code that will actually get input into the pad is the reverse of the code used.
solution = stop_digits[0].to_s + all_codes.shift

while !all_codes.empty?
match = /[#{stop_digits.join}](.{0,#{code_length-1}})$/.match(solution[-code_length..-1])
string = (match ? match[1] : nil)
if match.nil?
solution << stop_digit.call + all_codes.shift
elsif string.nil? || string.empty?
solution << all_codes.shift
else
overlap = match ? string.size : 0
code = all_codes.find { |c| c.index(string) == 0 }
if code.nil?
code = all_codes.shift
solution << stop_digit.call + code
else
all_codes.delete code
solution << code[overlap..-1]
end
end
end

solution.reverse.split(//).each{ |d| pad.press d.to_i }
pad
end

def num_of_stop_digs (code, stop_digits)
stop_digits.inject(0) { |num_stop_digs, dig| num_stop_digs + code.count(dig.to_s) }
end

if __FILE__ == $PROGRAM_NAME
include Benchmark

bm(10) do |x|
hacked_pad = nil
puts "One stop digit:\n"
puts
for i in (2..5)
x.report("#{i} digits") { hacked_pad = crack_code(i, [1]) }
hacked_pad.summarize
puts "="*60
end

puts
puts "Three stop digits:"
puts
for i in (2..5)
x.report("#{i} digits") { hacked_pad = crack_code(i, [1,2,3]) }
hacked_pad.summarize
puts "="*60
end
end
end

--Apple-Mail-2-25062225
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0644;
x-mac-creator=454D4178;
name="alarm_keypad.rb"
Content-Disposition: attachment;
filename=alarm_keypad.rb

#!/usr/bin/env ruby -w

#
# Stephen Waits <>
#

class AlarmKeypad

# init a keypad, with length of security code, and the code's
# stop digits
def initialize(code_length = 4, stop_digits = [1,2,3])
# remember the length of the security code
@code_length = code_length

# and which digits cause a code to be checked
@stop_digits = stop_digits

# and reset our data structures to 0
clear
end


# reset keypad to initial state
def clear
# an array of each code and how many times it's been entered
@codes = Array.new(10**@code_length,0)

# last N+1 keypad button presses
@key_history = []

# total number of keypad button presses
@key_presses = 0
end


# press a single digit
def press(digit)
# add digit to key history
@key_history.shift while @key_history.size > @code_length
@key_history << digit
@key_presses += 1

# see if we just tested a code
if @stop_digits.include?(@key_history.last) and
@key_history.length > @code_length
@codes[@key_history[0,@code_length].join.to_i] += 1
end
end

# find out if every code had been tested
def fully_tested?
not @codes.include?(0)
end

# find out if an individual code has been tested
# NOTE: an actual keypad obviously doesn't offer this functionality;
# but, it's useful and convenient (and might save duplication)
def tested?(code)
@codes[code] > 0
end

# output a summary
def summarize
tested = @codes.select { |c| c > 0 }.size
tested_multiple = @codes.select { |c| c > 1 }.size

puts "Search space exhausted." if fully_tested?
puts "Tested #{tested} of #{@codes.size} codes " +
"in #{@key_presses} keystrokes."
puts "#{tested_multiple} codes were tested more than once."
end
end


if $0 == __FILE__
hacked_pads = []
for i in (1..5)
a = AlarmKeypad.new(i, [1, 2, 3])
("0"*i.."9"*i).each do |c|
next if a.tested?(c.to_i)
c.split(//).each { |d| a.press(d.to_i) }
a.press(rand(3) + 1)
end
a.summarize
end

for i in (1..5)
a = AlarmKeypad.new(i, [1])
("0"*i.."9"*i).each do |c|
next if a.tested?(c.to_i)
c.split(//).each { |d| a.press(d.to_i) }
a.press(1)
end
a.summarize
end
end

--Apple-Mail-2-25062225--

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

On Mar 29, 2006, at 11:37 PM, Ross Bamford wrote:
>
> I think this problem is basically the shortest common superstring
> problem:
>
> http://www2.toki.or.id/book/AlgDesig...K5/NODE209.HTM
>
> Which is basically how my solution (and I think yours too) approached
> it. The upshot is that it's easy to find a common superstring, and
> even
> a reasonably short common superstring, but very difficult to find the
> _shortest_ or determine how long it would be (it's NP complete I
> think).

I definitely need to study more math and algorithms. Yes, this does
seem to be a variation on the shortest common superstring, and the
sources I'm finding say that it is NP-complete. Unfortunately, the
existence of the stop digits seems to complicate matters somewhat.
The most thorough discussion I've found online (so far, haven't
looked very long yet) is a PDF discussing, of all things, the Pokemon
trading card game: http://home.earthlink.net/~mstamp1/papers/poke.pdf

Nothing I've found so far discusses how one might predict the length
of the shortest common superstring, though. I feel, that for our
rather narrow problem domain, that it should be possible. Especially
since the substrings in the more traditional superstring problems are
random to some degree, while we know what all of our strings are.
Hm, I'll have to think on this more.

Tim