Phone Typing (#21)

by Hans Fugal

I am amazed whenever I see or hear about the rising generation of keypad punchers. People that can carry on IM conversations with a 12-key phone pad without instantly going mad; it's mind-boggling. As adaptive as the rising generation is, the "Multitap" solution is far from efficient. For example, I learned from Wheel of Fortune that the most common letters are RSTLNE, only one of which (T) is the first tap on one of the keys.

Your mission then, should you choose to accept it, is to develop a more efficient algorithm for key entry. User interaction is simply the 12 keys (0-9, * and #) with the letters printed on them as usual, and visual feedback of what they have typed so far. Simulating algorithms thought up by other people (e.g. LetterWise) is fair game.

[ Editor's Note:

Hans sent the following code to get people started with a simple testing inteface for their algorithms:

ruby
class TapEvent
attr_reader :when, :digit
def initialize(digit)
@digit = digit
@when = Time.now
end
def to_s
@digit
end
end

class PhonePad
attr_reader :text, :cursor
def set_text(text,cursor)
@text = text
@cursor = cursor
end
def register(&block)
@observers.push block
end
def initialize
@observers = []
@text = ''
@cursor = 0
end
def notify_observers(digit)
if digit =~ /[0-9*#]/
@observers.each { |block| block.call(TapEvent.new(digit)) }
end
end
end

class CLIPhonePad < PhonePad
def initialize
super
Thread.new do
while not $stdin.eof? do
$stdin.readline.split('').each { |c| notify_observers(c) }
end
end
end
def set_text(text,cursor)
super(text,cursor)
puts to_s
end
def run
end
def to_s
@text.dup.insert(@cursor,'_')
end
end

if $0 == __FILE__
p = CLIPhonePad.new

p.register do |ev|
puts "#{ev} at #{ev.when}"
p.set_text(p.text+ev.digit, p.cursor+1)
end

Thread.list[0].join
end

Hans's code is well suited to GUI adaption, if you're so inclined. (Please post to Ruby Talk if you do build a GUI for this. That's not a spoiler.)

Here's another version by me, that doesn't require you press return after the digits:

ruby
begin
require "Win32API"

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

loop do
char = read_char.chr
case char
when /^(?:\d|\*|#)$/
### Replace the following line with your algorithm. ###
puts "You entered #{char}."
when /q/i
break
else
puts "'#{char}' is not a key on the keypad."
end
end

-JEG2 ]

This is an area of serious research for some people; don't fret it if your algorithm isn't perfect or ideal, and don't spend too long on it. ;-) Make your goal to be better than dumb, which is to say be better than "Multitap".

Quiz Summary

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:

ruby
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:

ruby
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.

ruby
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:

ruby
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:

ruby
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...