Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ] B & E (#72)

Reply
Thread Tools

[QUIZ] B & E (#72)

 
 
Ruby Quiz
Guest
Posts: n/a
 
      03-24-2006
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 <(E-Mail Removed)>
#

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


 
Reply With Quote
 
 
 
 
James Edward Gray II
Guest
Posts: n/a
 
      03-24-2006
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



 
Reply With Quote
 
 
 
 
Stephen Waits
Guest
Posts: n/a
 
      03-24-2006

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



 
Reply With Quote
 
Timothy Bennett
Guest
Posts: n/a
 
      03-24-2006

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



 
Reply With Quote
 
semmons99@gmail.com
Guest
Posts: n/a
 
      03-27-2006
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

 
Reply With Quote
 
Stephen Waits
Guest
Posts: n/a
 
      03-27-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) 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



 
Reply With Quote
 
Stephen Waits
Guest
Posts: n/a
 
      03-27-2006
Ross Bamford wrote:
> Hmm, this is a tricky one


Indeed.. thanks for the solutions Ross!

--Steve



 
Reply With Quote
 
semmons99@gmail.com
Guest
Posts: n/a
 
      03-28-2006
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>

 
Reply With Quote
 
Matthew Moss
Guest
Posts: n/a
 
      03-28-2006
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, (E-Mail Removed) <(E-Mail Removed)> 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>
>
>
>



 
Reply With Quote
 
Stephen Waits
Guest
Posts: n/a
 
      03-28-2006

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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments