[QUIZ] B & E (#72)

Discussion in 'Ruby' started by Ruby Quiz, Mar 24, 2006.

  1. Ruby Quiz

    Ruby Quiz Guest

    The three rules of Ruby Quiz:

    1. Please do not post any solutions or spoiler discussion for this quiz until
    48 hours have passed from the time on this message.

    2. Support Ruby Quiz by submitting ideas as often as you can:

    http://www.rubyquiz.com/

    3. Enjoy!

    Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
    on Ruby Talk follow the discussion.

    -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    by Stephen Waits

    Like many homeowners, I have a residential monitored alarm system installed in
    my house. It consists of a few keypads and several remote sensors.

    My alarm has three modes of operation:

    1. Off - completely disarmed
    2. Away - everything (perimeter and interior) armed
    3. Stay - perimeter armed

    The keypad consists of 12 buttons, which includes the digits '0' through '9',
    plus '*' and '#'. The '*' and '#' are only used for special programming.

    The digits '1', '2', and '3' are also labeled "Off", "Away", and "Stay". This
    corresponds to the three system modes mentioned above.

    The security code is 4 digits long. To set or change the system's mode, you
    simply enter your 4 digit security code, followed by the digit ('1', '2', or
    '3') which corresponds to the mode you want to set.

    For example, if the security code was 1234:

    12341 - sets system to "Off"
    12342 - sets system to "Away"
    12343 - sets system to "Stay"

    What if you make a mistake when you're entering your code? Yes, this is where
    an interesting observation comes into play. To answer the question... if you
    make a mistake you just start over. In other words, the keypad seems to only
    care that the last 5 keypresses match a valid code+command sequence.

    For example, if you entered the first two digits of your code incorrectly, you
    could just simply start over with the correct code, without any kind of reset:

    8912341
    ++ => first 2 keypresses erroneous, oops!
    +++++ => last 5 keypresses == valid code+command sequence

    The thought occurs to me, and I'm sure to the reader, that perhaps this can be
    exploited. For example, if you entered the sequence 1234123, you are actually
    testing 3 different codes:

    1234123 => what you entered
    12341 => 1234 + 1/off
    .23412 => 2341 + 2/away
    ..34123 => 3412 + 3/stay

    Problems:

    1. What is the shortest sequence of digits you can come up with that tests every
    code in this alarm system? The worst case is 5*10**4, or 50000 keypresses.

    2. What if the security code was 5 digits instead of 4? Worst case here is
    6*10**5, or 600000 keypresses.

    3. What if the "stop digits" changed from [1, 2, 3], to just [1]? For instance,
    maybe the system is armed (mode 2 or 3) and only actually beeps when switching
    to mode 1. (See Assumptions below)

    4. Can you also minimize the number of duplicate code tests?

    Assumptions:

    * We assume the keypad will actually let you go on entering digits for this
    long. I haven't tested it, but it seems silly that it might actually allow
    this. However, as a long time comp.risks reader, almost nothing surprises me.

    * We assume that the keypad will always signify a valid code+command sequence,
    regardless of mode. In reality, if you set to Away when it's already in Away,
    it might not emit it's "success" signal.

    #!/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__
    # a random button presser, 3 digit codes
    a = AlarmKeypad.new(3)
    a.press( rand(10) ) until a.fully_tested?
    a.summarize
    
    # sequential code entry, 4 digit codes
    a = AlarmKeypad.new(4)
    ("0000".."9999").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
    
    # sequential code entry, 5 digit codes, only [1] as a stop digit
    a = AlarmKeypad.new(5,[1])
    ("00000".."99999").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
    Ruby Quiz, Mar 24, 2006
    #1
    1. Advertising

  2. On Mar 24, 2006, at 7:56 AM, Ruby Quiz wrote:

    > by Stephen Waits


    Just by a neat little quirk of serendipity this quiz was launched on
    the quiz creator's birthday. Happy birthday Stephen!

    James Edward Gray II
    James Edward Gray II, Mar 24, 2006
    #2
    1. Advertising

  3. On Mar 24, 2006, at 6:57 AM, James Edward Gray II wrote:

    > Happy birthday Stephen!


    Thanks! I'm looking forward to those solutions...

    --Steve
    Stephen Waits, Mar 24, 2006
    #3
  4. On Mar 24, 2006, at 8:28 AM, Stephen Waits wrote:

    >
    > On Mar 24, 2006, at 6:57 AM, James Edward Gray II wrote:
    >
    >> Happy birthday Stephen!

    >
    > Thanks! I'm looking forward to those solutions...
    >
    > --Steve
    >


    Happy birthday Steve.

    In case you're curious, my solution is... not doing so well. I
    thought I'd built up a decent model by working with code lengths I
    could fit in my head (e.g. 1 or 2 digits), but it actually does much
    worse than the naive solution for 4 and 5 digit codes (it does better
    for 1-3 digit codes). So, back to the drawing board for me.

    Tim
    Timothy Bennett, Mar 24, 2006
    #4
  5. Ruby Quiz

    Guest

    Re: B & E (#72)

    I think that there are more key presses then you think. There are
    (10**4)*3 different combinations which totals 30,000. But that takes
    30,000*5 key presses which is 150,000 key presses. So if the code was 5
    digits, it is 1,500,000 key presses to test them all by brute force.
    Anyway, here is my first solution. It is unrefined, but I haven't
    really had time to work on it much.

    <code>

    # Shane Emmons
    #
    # Quiz 72 B&E
    #
    # This code is very ugly and inefficient, but I wanted to get
    # something out there to look at. Sorry I didn't have more
    # time to work on this quiz.

    all_possible = ""

    10.times do |key1| 10.times do |key2| 10.times do |key3|
    10.times do |key4| 3.times do |key5|
    current_code = Array.new
    current_code << key1 << key2 << key3 << key4 << key5 + 1
    next if all_possible.include?( current_code.to_s )
    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 << right.pop
    if left.length == 0
    all_possible += current_code.to_s
    break
    elsif all_possible =~ /^#{left.to_s}/
    all_possible = left_over.to_s + all_possible
    break
    elsif all_possible =~ /#{right.to_s}$/
    all_possible += right_over.to_s
    break
    end
    end
    end end
    end end end

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

    </code>

    Shane
    , Mar 27, 2006
    #5
  6. Re: B & E (#72)

    wrote:
    > I think that there are more key presses then you think. There are
    > (10**4)*3 different combinations which totals 30,000. But that takes
    > 30,000*5 key presses which is 150,000 key presses. So if the code was 5
    > digits, it is 1,500,000 key presses to test them all by brute force.
    > Anyway, here is my first solution. It is unrefined, but I haven't
    > really had time to work on it much.


    Hi Shane,

    I'm not sure I follow you..

    With 4 digit codes, there are 10,000 unique codes, or 10**4. Each code
    takes a maximum of 5 keypresses to test, therefore 5*10**4 == 50k
    keypresses.

    Regardless, thanks for your solution!

    --Steve
    Stephen Waits, Mar 27, 2006
    #6
  7. Ross Bamford wrote:
    > Hmm, this is a tricky one :)


    Indeed.. thanks for the solutions Ross!

    --Steve
    Stephen Waits, Mar 27, 2006
    #7
  8. Ruby Quiz

    Guest

    Re: B & E (#72)

    You are right that there are 10,000 unique codes, but each of those
    codes can have any of the three unique modifier keys attached to it so
    10,000 * 3 = 30,000 unique combinations you must press. And, since
    there are 5 keys in the 4 key code + 1 modifier key, it is 30,000 * 5 =
    150,000. At first I didn't realize this until I wrote the loop to
    generate all of the unique code/modifier key combinations. The one key
    to this I believe, is that you have to treat the modifier key (1,2,3)
    as part of the code not a seperate entity. Here is some code to prove
    the solution.

    <code>

    output, num_codes = '', 0

    10.times do |x1| 10.times do |x2| 10.times do |x3|
    10.times do |x4| 3.times do |x5|
    output += x1.to_s + x2.to_s + x3.to_s + x4.to_s + x5.to_s
    num_codes += 1
    end end
    end end end

    print "number codes: ", num_codes.to_s, "\n"
    print "output length: ", output.length, "\n"

    </code>
    , Mar 28, 2006
    #8
  9. Ruby Quiz

    Matthew Moss Guest

    Re: B & E (#72)

    I think part of the problem was that it didn't matter which modifier
    key you hit, the system would confirm the code. So while 150,000 is
    right if you need to test every combo with every modifier, 50,000 is
    what the problem was looking for (i.e., every combo with _any_
    modifier).


    On 3/28/06, <> wrote:
    > You are right that there are 10,000 unique codes, but each of those
    > codes can have any of the three unique modifier keys attached to it so
    > 10,000 * 3 =3D 30,000 unique combinations you must press. And, since
    > there are 5 keys in the 4 key code + 1 modifier key, it is 30,000 * 5 =3D
    > 150,000. At first I didn't realize this until I wrote the loop to
    > generate all of the unique code/modifier key combinations. The one key
    > to this I believe, is that you have to treat the modifier key (1,2,3)
    > as part of the code not a seperate entity. Here is some code to prove
    > the solution.
    >
    > <code>
    >
    > output, num_codes =3D '', 0
    >
    > 10.times do |x1| 10.times do |x2| 10.times do |x3|
    > 10.times do |x4| 3.times do |x5|
    > output +=3D x1.to_s + x2.to_s + x3.to_s + x4.to_s + x5.to_s
    > num_codes +=3D 1
    > end end
    > end end end
    >
    > print "number codes: ", num_codes.to_s, "\n"
    > print "output length: ", output.length, "\n"
    >
    > </code>
    >
    >
    >
    Matthew Moss, Mar 28, 2006
    #9
  10. Re: B & E (#72)

    On Mar 28, 2006, at 6:53 AM, Matthew Moss wrote:

    > I think part of the problem was that it didn't matter which modifier
    > key you hit, the system would confirm the code. So while 150,000 is
    > right if you need to test every combo with every modifier, 50,000 is
    > what the problem was looking for (i.e., every combo with _any_
    > modifier).


    That's right. Sorry for the confusion.

    --Steve
    Stephen Waits, Mar 28, 2006
    #10
  11. Ruby Quiz

    Guest

    Re: B & E (#72)

    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>
    , Mar 28, 2006
    #11
  12. 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!
    Stephen Waits, Mar 29, 2006
    #12
  13. --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.603938)
    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--
    Timothy Bennett, Mar 30, 2006
    #13
  14. 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
    Timothy Bennett, Mar 30, 2006
    #14
  15. 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/AlgDesignManual/BOOK/BOOK5/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
    Timothy Bennett, Mar 30, 2006
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    364
    James Edward Gray II
    Jan 18, 2005
  2. David Tran
    Replies:
    9
    Views:
    182
    David Tran
    Jan 21, 2005
  3. Ruby Quiz

    [QUIZ] 1-800-THE-QUIZ (#20)

    Ruby Quiz, Feb 18, 2005, in forum: Ruby
    Replies:
    15
    Views:
    322
    gabriele renzi
    Feb 24, 2005
  4. Marcelo Alvim

    [QUIZ] Newbie doubts about the quiz

    Marcelo Alvim, Aug 15, 2006, in forum: Ruby
    Replies:
    15
    Views:
    250
    Marcelo Alvim
    Aug 16, 2006
  5. Daniel Moore
    Replies:
    10
    Views:
    306
    James Gray
    Jan 31, 2009
Loading...

Share This Page