Algorithmathon Day 17: Telephone Words

Created: 26 August 2013  Modified:

It is easier for most humans to remember words rather than to remember numbers. Having only 10 numbers and 26 letters the numbers would need to double or triple up with letters. The history of the telephone keypad is interesting. For example it wasn’t until mobile telephones became ubiquitous that the world was even using the same letters for the same numbers. The results of this world standard makes little since to me. We will view the correlations between letters and numbers in our code.

Our challenge will be to write a small program to list out the possible combinations of letters for a telephone number. I think of this problem as being a series of wheels with letters on the circumference. If each wheel represents a number then some wheels will have no letters on it while some will have three or even four letters. The first wheel starts spinning and when it reaches the first letter it starts spinning the the second wheel which starts spinning the third wheel and so on. For a seven digit number the cost could range from 7 to 4^7^. The first being the case for the number 111-1111 and the second being 999-9999. Most numbers will fall towards the middle of these two extremes.

A solution will involve steps similar to the below.

Seems pretty straightforward let’s hop right into build our RSpec tests.

telephone_words_spec.rb

require 'spec_helper'

describe TelephoneWords do

  describe "Class" do
    it "should have method 'build_words'" do
      TelephoneWords.method_defined?(:build_words).should be_true
    end
  end

  describe "Instance" do

    it "should not return nil when 'build_words([2,2,2])' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2]
      telephone_words.build_words(number_array).should_not be_nil
    end

    it "should return 27 when 'build_words([2,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end 

    it "should return 27 when 'build_words([1,2,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [1,2,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end   

    it "should return 27 when 'build_words([2,2,2,1]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2,1]
      telephone_words.build_words(number_array).length.should == 27
    end 

    it "should return 27 when 'build_words([2,1,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,1,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end  

    it "should return 2916 when 'build_words([3,5,2,2,9,6,6]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [3,5,2,2,9,6,6]
      telephone_words.build_words(number_array).length.should == 2916
    end  
  end
end

Finally our solution.

telephone_words.rb

class TelephoneWords < Array
  
  def initialize()
    @number_dictionary = { 0=> [], 1 => [], 2 => ['A','B','C'], 3 => ['D','E','F'], 4 => ['G','H','I'], 5 => ['J','K','L'], 6 => ['M','N','O'], 7 => ['P','Q','R','S'], 8 => ['T','U','V'], 9 => ['W','X','Y','Z'] }
  end


  #Find all possible letter combinations from a telephone number.
  #
  #* *Args*    :
  #  - +telephone_number+ -> The telephone number to be analyzed.
  #* *Returns* :
  #  - An array containing strings representing all the possible letter combinations.
  def build_words(telephone_number)
    if telephone_number.nil? || telephone_number.length < 1
      return
    end
    return_results = Array.new()
    build_words_by_recursion(telephone_number,Array.new(),return_results,0)
    return return_results
  end

  private
    
  #Find all possible letter combinations from a telephone number by recursing
  #through the possible letter combinations.
  #
  #* *Args*    :
  #  - +telephone_number+ -> The telephone number to be analyzed.
  #  - +current_word+ -> The combinations of letters currently being put together to build a word.
  #  - +return_results+ -> An array used to store the combinations of letters
  #  - +depth+ -> Tracks which telephone number is currently being examined.
  #* *Returns* :
  #  - An array containing strings representing all the possible letter combinations.
    def build_words_by_recursion(telephone_number,current_word,return_results,depth)
      if depth > (telephone_number.length - 1)
        return_results[return_results.length]=current_word.join()
      end
      unless telephone_number[depth].nil?
        if telephone_number[depth] == 0 || telephone_number[depth] == 1
          current_word.push(telephone_number[depth].to_s)
          build_words_by_recursion(telephone_number,current_word,return_results,depth + 1)
          current_word.pop()
        else
          @number_dictionary[telephone_number[depth]].each { | letter |
            current_word.push(letter)
            build_words_by_recursion(telephone_number, current_word, return_results, depth + 1)
            current_word.pop()
          }          
        end
      end
    end
end
tags: Algorithm - Algorithmathon - RSpec - Ruby - Telephone Words
   Less Is More