From: Ruby Quiz <james@...>
Date: 2006-03-24T22:56:18+09:00
Subject: [QUIZ] B & E (#72)

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 <steve@waits.net>
	#
	
	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