From: Ruby Quiz <james@...>
Date: 2005-03-03T23:23:23+09:00
Subject: [SUMMARY] Phone Typing (#21)

The topic of this week's quiz was very interesting to me.  I regret that I
couldn't steal enough time to try a solution of my own.  However, I've enjoyed
playing with the solutions quite a bit.  Thanks Hans!

So what's all the fuss about?  Let's run a simple test, using Dave Burt's
solution (because it puts each step on a new line).  The following is me typing
a simple sentence with the multitap method.  (Note:  I did modify one line of
Dave's code used here, to make the digits come last as they do on my phone and
in Brian's solution.)  Forgive the length, but in a way it's telling:

	m_
	mw_
	mx_                                        # second keypress
	my_                                        # third keypress
	my _
	my w_
	my wg_
	my wh_                                     # second keypress
	my wi_                                     # third keypress
	my wid_
	my wie_                                    # second keypress
	my wif_                                    # third keypress
	my wifd_
	my wife_                                   # second keypress
	my wife _
	my wife d_
	my wife da_
	my wife dam_
	my wife dan_                               # second keypress
	my wife dana_
	my wife danap_
	my wife danaq_                             # second keypress
	my wife danar_                             # third keypress
	my wife danas_                             # fourth keypress
	my wife danas _
	my wife danas a_
	my wife danas b_                           # second keypress
	my wife danas bg_
	my wife danas bh_                          # second keypress
	my wife danas bi_                          # third keypress
	my wife danas bip_
	my wife danas biq_                         # second keypress
	my wife danas bir_                         # third keypress
	my wife danas birt_
	my wife danas birtg_
	my wife danas birth_                       # second keypress
	my wife danas birthd_
	my wife danas birthda_
	my wife danas birthdaw_
	my wife danas birthdax_                    # second keypress
	my wife danas birthday_                    # third keypress
	my wife danas birthday _
	my wife danas birthday g_
	my wife danas birthday h_                  # second keypress
	my wife danas birthday i_                  # third keypress
	my wife danas birthday ip_
	my wife danas birthday iq_                 # second keypress
	my wife danas birthday ir_                 # third keypress
	my wife danas birthday is_                 # fourth keypress
	my wife danas birthday is _
	my wife danas birthday is a_
	my wife danas birthday is ap_
	my wife danas birthday is app_
	my wife danas birthday is apq_             # second keypress
	my wife danas birthday is apr_             # third keypress
	my wife danas birthday is aprg_
	my wife danas birthday is aprh_            # second keypress
	my wife danas birthday is apri_            # third keypress
	my wife danas birthday is aprij_
	my wife danas birthday is aprik_           # second keypress
	my wife danas birthday is april_           # third keypress
	my wife danas birthday is april _
	my wife danas birthday is april d_
	my wife danas birthday is april e_         # second keypress
	my wife danas birthday is april eg_
	my wife danas birthday is april eh_        # second keypress
	my wife danas birthday is april ei_        # third keypress
	my wife danas birthday is april eig_
	my wife danas birthday is april eigg_
	my wife danas birthday is april eigh_      # second keypress
	my wife danas birthday is april eight_
	my wife danas birthday is april eightg_
	my wife danas birthday is april eighth_    # second keypress

Here's the same exercise, with LetterWise:

	o_
	_                                          # had to push *
	m_
	my_
	my _
	my w_
	my wh_
	my w_                                      # had to push *
	my wi_
	my wid_
	my wi_                                     # had to push *
	my wif_
	my wife_
	my wife _
	my wife f_
	my wife _                                  # had to push *
	my wife d_
	my wife da_
	my wife dan_
	my wife danc_
	my wife dan_                               # had to push *
	my wife dana_
	my wife danas_
	my wife danas _
	my wife danas a_
	my wife danas _                            # had to push *
	my wife danas b_
	my wife danas bi_
	my wife danas bir_
	my wife danas birt_
	my wife danas birth_
	my wife danas birthe_
	my wife danas birth_                       # had to push *
	my wife danas birthd_
	my wife danas birthda_
	my wife danas birthday_
	my wife danas birthday _
	my wife danas birthday h_
	my wife danas birthday _                   # had to push *
	my wife danas birthday i_
	my wife danas birthday is_
	my wife danas birthday is _
	my wife danas birthday is a_
	my wife danas birthday is as_
	my wife danas birthday is a_               # had to push *
	my wife danas birthday is ar_
	my wife danas birthday is a_               # had to push *, a second time
	my wife danas birthday is ap_
	my wife danas birthday is app_
	my wife danas birthday is ap_              # had to push *
	my wife danas birthday is apr_
	my wife danas birthday is apri_
	my wife danas birthday is april_
	my wife danas birthday is april _
	my wife danas birthday is april f_
	my wife danas birthday is april _          # had to push *
	my wife danas birthday is april d_
	my wife danas birthday is april _          # had to push *, a second time
	my wife danas birthday is april e_
	my wife danas birthday is april ei_
	my wife danas birthday is april eig_
	my wife danas birthday is april eigh_
	my wife danas birthday is april eight_
	my wife danas birthday is april eighti_
	my wife danas birthday is april eight_     # had to push *
	my wife danas birthday is april eighth_

(I'm sure Dana will be looking forward to all your gifts this year.)

That's a pretty radical difference.  Let me line up those stats:

	               Multitap  LetterWise
	  keypresses:  74          52
	second press:  20 (27%)    12 (23%)
	 third press:  14 (19%)     2 (4%)
	fourth press:   2 (3%)      0

However, and this is purely subjective so feel free to completely ignore it, I'm
almost positive I entered the sentence faster with Multitap.  Isn't that ironic?
The reason is that I can glance at the keypad and know exactly what I need to
do.  With LetterWise, I had to wait and see what I got, before I could respond. 
The document linked to by the quiz seemed to imply this was a phase I would get
past, eventually.

So, between the two methods explored in the solution, LetterWise is definitely a
by the numbers improvement.  Subjectively though, it may take some getting use
to.  Try it for yourself.

Oh, should I be talking about Ruby here?  Right, let's get on that.

I want to take a look at Dave Burt's code that was used in the examples above,
but not all of it.  I'll leave out his TK interface and a few classes mainly
useful in testing.

First, Dave combined the code Hans and I offered with the quiz to build a better
command-line interface.  Here's the class for that:

	class CharPhonePad < PhonePad
	  def initialize
	    super
	    Thread.new do
	      loop do
	        case c = self.class.read_char
	        when 3, 4, 26, 27  # Break on Ctrl+C, Ctrl+D, Ctrl+Z, Escape
	          break
	        when 43  # convert '+' to '*' for ease of typing on numpad
	          c = 42
	        when 45, 46, 47 # convert '-', '.', '/' to '#' for ease of typing
	          c = 35
	        end
	        notify_observers(c.chr)
	      end
	    end
	  end
	  def set_text(text, cursor)
	    super(text, cursor)
	    puts to_s
	  end
	  def to_s
	    @text.dup.insert(@cursor, '_')
	  end

	  begin
	    require "Win32API"
	    def self.read_char
	      c = Win32API.new("crtdll", "_getch", [], "L").Call
	    end
	  rescue LoadError
	    def self.read_char
	      system "stty raw -echo"
	      STDIN.getc
	    ensure
	      system "stty -raw echo"
	    end
	  end
	end

Nothing real surprising there.  Dave just extended Hans's framework with my
character reading methods.  It's a nicer option than what I offered because you
can use the event system.  Note the character case block adds some niceties for
using your keyboard number pad.

Next, here's Dave's Multipress/Multitap implementation:

	class TapHandler
	  def initialize(phone_pad)
	    @p = phone_pad
	  end
	end

	class MultipressTapHandler < TapHandler
	  attr_accessor :timeout
	  def initialize(phone_pad, timeout = 1.5)
	    super(phone_pad)
	    @timeout = timeout
	  end
	  def process_event(ev)
	    if (@last_event && 
	        ev.digit == @last_event.digit &&
	        Time.now - @last_event.when < timeout)
	      char_set = PhonePad::InputMap[ev.digit]
	      char_index = (char_set.index(@p.text[-1].chr) + 1) % char_set.size
	      @p.set_text(@p.text[0..-2] + char_set[char_index], @p.cursor)
	    else
	    ### modified by JEG2 for discussion example ###
	      @p.set_text(@p.text+PhonePad::InputMap[ev.digit][0], @p.cursor+1)
	    ### actual code by Dave Burt ###
	    #  @p.set_text(@p.text+ev.digit, @p.cursor+1)
	    end
	    @last_event = ev
	  end
	end

All the exciting work in there happens in process_event().  The if checks to see
if it has memorized a previous event.  If it has and this new event is the same
digit and the timout for that press hasn't expired yet, the next character in
the InputMap is selected.   In all other cases, the first character of the
InputMap is selected.  That's all there is to Multitap.

	class LetterWiseTapHandler < TapHandler
	  # method taken from:
	  # MacKenzie, I. S., Kober, H., Smith, D., Jones, T., Skepner, E. (2001).
	  # LetterWise: Prefix-based disambiguation for mobile text input.
	  # Proceedings of the ACM Symposium on User Interface Software and
	  # Technology - UIST 2001, pp. 111-120. New York: ACM.
	  # http://www.yorku.ca/mack/uist01.html
	  
	  # A lot of the logic in this method is captured in the InputMap,
	  # which maps prefixes of up to 3 letters and a key (0-9) onto 
	  # an array of letters inmost-likely-first order.
	  
	  #require 'yaml'
	  # 1.8MB, ~ 6 seconds to load
	  #InputMap = YAML.load_file('predict3.yaml')
	  # 2.3MB, ~ 3 seconds to load  
	  InputMap = eval(File.read('predict3.rb'))  
	  
	  def initialize(phone_pad)
	    super(phone_pad)
	    @cycle = ['*']
	  end
	  def process_event(ev)
	    prefix = @p.text[/\w{0,3}$/]
	    if ev.digit == '*'  # change last letter
	      @cycle.push @cycle.shift  # rotate
	      @p.set_text(@p.text[0..-2], @p.cursor - 1)
	    elsif InputMap[prefix]
	      @cycle = InputMap[prefix][ev.digit].dup
	    else
	      @cycle = InputMap[nil][ev.digit].dup
	    end
	    @cycle ||= %w[. ! - & @ $ * +]
	    @p.set_text(@p.text + @cycle[0], @p.cursor + 1)
	  end
	end

As the comments suggest, there's not a lot of logic in here.  Surprisingly,
there isn't that much in the evaled predict3.rb file either.  It's just one big
boring hash, which you can see for yourself, if you follow the links to Dave's
solution.

Again, process_event() is where the action is.  Really, it just looks up the
last three letters entered in the InputMap to find the order of the letters (the
elsif part) or cycles to the next most likely letter (the if part).  The system
seems to support some punctuation characters, but I couldn't figure out how to
get at them when using it.

Here's the code that kicks off the process:

	if $0 == __FILE__
	  
	  #p = CLIPhonePad.new  # Command-line interface
	  p = CharPhonePad.new  # Raw command-line interface
	  #p = TkPhonePad.new  # TK interface
	  
	  # just dump digits pressed
	  #tap_handler = NoOpTapHandler.new(p)
	  # tap the shape of a letter on the keypad!
	  #tap_handler = IconicTapHandler.new(p)
	  # standard multi-press, 1.5s timeout
	  #tap_handler = MultipressTapHandler.new(p)
	  # letter-wise prediction; * to change letter
	  tap_handler = LetterWiseTapHandler.new(p)

	  p.register do |ev|
	    tap_handler.process_event(ev)
	  end

	  Thread.list[0].join
	end

Dave, repeat after me, "optparse is my friend..."  Be kind to the guy who plays
with your code, because it might be me.  Here's that and more without the
comment dance:

	if $0 == __FILE__
		require "optparse"
		
		# defaults
		pad = :raw
		tap = :letterwise
		
		# parse options
		opts = OptionParser.new do |opts|
			opts.banner = "Usage:  #$0 [OPTIONS]"
			
			opts.separator ""
			opts.separator "Specific Options:"
			
			opts.on( "-i INTERFACE",
			         [:raw, :tk, :cli],
			         "Interface you would like to use:",
			         "  raw, tk or cli." ) do |v|
				pad = v
			end
			opts.on( "-m MODE",
			         [:letterwise, :multipress, :iconic, :noop],
			         "The input algorithm to use:",
			         "  letterwise, multipress, iconic or noop." ) do |v|
				tap = v
			end
			opts.on( "-h", "-?", "--help",
			         "Show this text." ) do
				puts opts
				exit
			end
		end
		opts.parse!(ARGV)
	  
		# handle results
		case pad
		when :raw then p = CharPhonePad.new
		when :tk  then p = TkPhonePad.new
		when :cli then p = CLIPhonePad.new
		end
		case tap
		when :letterwise then tap_handler = LetterWiseTapHandler.new(p)
		when :multipress then tap_handler = MultipressTapHandler.new(p)
		when :iconic     then tap_handler = IconicTapHandler.new(p)
		when :noop       then tap_handler = NoOpTapHandler.new(p)
		end

		# run program
		p.register { |ev| tap_handler.process_event(ev) }
		Thread.list[0].join
	end

Brian makes them even prettier, so scan his solution for an even better example.

My thanks to both Brian and Dave for playing with this one while I didn't have
time to.  Also, thank you Hans for such a clever topic.

Tomorrows quiz takes us all the way to Rome...