#!/usr/bin/ruby
#
# Phone Numbers to Words converter
#
# A response to Ruby Quiz of the Week #20 [ruby-talk:131563]
# Produce phone numbers made of words from normal numeric ones.
# Takes numeric phone numbers on standard input, and produces equivalent
# word-replacements on standard output.
# Takes an optional parameter (-d or --dict) to change the dictionary
# from the default /usr/share/dict/words
#
# Author: Dave Burt <dave at burt.id.au>
#
# Created: 21 Feb 2005
#
# Last modified: 23 Feb 2005
#
# Fine print: Provided as is. Use at your own risk. Unauthorized copying is
#             not disallowed. Credit's appreciated if you use my code. I'd
#             appreciate seeing any modifications you make to it.

module PhoneWords
	
	# match any bits of the number with all available words
	# returns an array of "matches", each of which is
	# a hash with keys :start, :length, and :words
	def self.match(number, numbers_to_words_map)
		fragments = []
		result = []
		number.length.times do |i|
			(i+1).times do |start|
				match = numbers_to_words_map[number[start, number.length - i]]
				if match
					result << {
						:start => start,
						:length => number.length - i,
						:words => match
					}
				end
			end
		end
		
		# matches need to be sorted by [:start] for combine()
		result.sort_by {|match| match[:start] }
	end
	
	# return all combinations of matches that don't overlap
	# (returns an array of arrays of matches)
	# pre: matches must be in ascending order of match[:start]
	def self.combine(matches)
		result = []
		next_start=0
		matches.each do |match|
			
			# each match is a potential solution by itself
			result << [match]
			
			# skip ahead to the next match that doesn't overlap
			next_start = nil
			matches.size.times do |i|
				if matches[i][:start] >= match[:start] + match[:length]
					next_start = i
					break
				end
			end
			
			# concatenate all later matching combinations with this match
			if next_start
				combine(matches[next_start..-1]).each do |combination|
					result << ([match] + combination)
				end
			end
		end
		result
	end
	
	# turn word match combinations into an array of "final product" phone numbers
	# and filter out numbers with 2 digits in a row
	def self.new_phone_numbers(number, combinations)
		new_numbers = []
		
		combinations.each do |matches|
			
			# create an index to iterate through each combination of words
			# in all matches (parallel to matches)
			index = matches.map do |match|
				match[:words].size - 1
			end
			index[0] += 1  # to offset the decrement at start of loop
			begin
				index.size.times do |i|
					if index[i] == 0
						index[i] = matches[i][:words].size - 1
					else
						index[i] -= 1
						break
					end
				end
				
				new_number = number.dup
				matches.reverse.each_with_index do |match, i|
					new_number[match[:start], match[:length]] =
						'-' +
						match[:words][index[matches.size - i - 1]] +
						'-'
				end
				unless /\d\d/ =~ new_number
					new_number.gsub! /^-/, ''
					new_number.gsub! /--/, '-'
					new_number.gsub! /-$/, ''
					new_numbers << new_number
				end
			end while index.inject {|sum, n| sum + n } > 0
		end
		new_numbers.sort
	end
	
	if __FILE__ == $0
		require 'optparse'
		
		# set dictionary filename
		words_file = '/usr/share/dict/words'
		opts = OptionParser.new do |opts|
			opts.banner = "Usage: #{$0} [-d dictionary_file]"
			opts.on('-d', '--dict FILENAME') do |filename|
				words_file = filename
			end
		end
		opts.parse! ARGV
		
		# initialize letters-to-numbers-and-back-again maps
		digits_to_letters = {
			0 => %w[0],
			1 => %w[1],
			2 => %w[2 A B C],
			3 => %w[3 D E F],
			4 => %w[4 G H I],
			5 => %w[5 J K L],
			6 => %w[6 M N O],
			7 => %w[7 P Q R S],
			8 => %w[8 T U V],
			9 => %w[9 W X Y Z],
		}
		letters_to_digits = {}
		digits_to_letters.each_pair do |digit, letters|
			letters.each do |letter|
				letters_to_digits[letter[0]] = digit
			end
		end
		
		# read words, and map digits to the words they make
		numbers_to_words_map = {}
		File.open(words_file) do |f|
			f.each_line do |word|
				word.chomp!
				word.gsub! /[^A-Za-z0-9]/, ''
				word.upcase!
				key = word.split(//).map do |letter|
					letters_to_digits[letter[0]].to_s
				end.join
				numbers_to_words_map[key] ||= []
				numbers_to_words_map[key] << word
			end
		end
		
		# main loop: get a number, show its replacements, repeat
		ARGF.each do |number|
			number.chomp!
			number.gsub! /\D/, ''
			
			next if number.nil? || number.empty?
			
			matches = match(number, numbers_to_words_map)
			combinations = combine(matches)
			new_numbers = new_phone_numbers(number, combinations)
			
			# output findings
			if new_numbers.empty?
				# puts '  (no matches found)'  # i like this, but it's disallowed by the spec
			else
				puts "#{new_numbers.size} replacements for #{number}:"
				new_numbers.sort.each do |new_number|
					puts new_number
				end
			end
		end  # ARGF.each
	end  # if __FILE__ == $0
end  # module PhoneWords