[Exercise] Phone Keypad

Joe

Most of you are old enough to remember how incredibly primitive texting on the first mobile phones was. Hell, some of you are probably still using these keyboards today. For those of you who don't see what I'm talking about, here's how it used to work.

Leaving punctuation aside, a keyboard would use 8 keys (from 2 to 9) to type the letters of the alphabet. Each letter would be assigned to a key, in a sorted alphabetical order, like this:

| key | letter  |
|-----+---------|
|   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 |
|-----+---------|

For example, in order to type the letter "o", one would need to press the key "6" twice. In order to type successive letters on the same key, one would need to enter the first letter, wait a bit, then enter the second letter. That would slow our typing considerably and generally annoy us a lot.

Exercise
What's the most annoying word of the english language to type on these keyboard? Annoying in that case would be the word with the highest number of consecutive letters belonging to the same key.

Bonus questions
Try to play a bit with the definition of "most annoying". What's more annoying, a word with 5 consecutive letters on the same key or a word with 3 consecutive letters on the same key twice?

What's the longest "not annoying" (0 consecutive letters on the same key) word?

Where to get a dictionary?
You will need a list of all the english words for this exercise. You can easily snatch one off the web. If you don't feel like searching:

You can use the dict used by OpenOffice for spell checking
If you're on a Unix system, there's a dictionary somewhere on your system. Most probably under /usr/share. For example on MacOSX you can find it in /usr/share/dict/words.

Ra8

I defined hardness as the number of stops a user has to do first, then by how short is the string:
If a user has to wait 5 times for a string of size 8 and 5 times for a string of size 12, the string of size 8 is harder.

<script>
function getNum(char)
{
    /*
        Returns the mapping of a character in the
        keyboard, example getNum("a") return 2 and
        getNum("r") returns 7
    */
    map="22233344455566677778889999";
    return map[char.toLowerCase().charCodeAt(0)-97];
}
function getNums(str){
    /*
        Returns all the mappings of a string
        letter by letter
    */
    ret="";
    for(k=0;k<str.length;k++)
        ret+=getNum(str[k]);
    return ret;
}
function f(str)
{
    /*
        Counts how many times consecutive digits
        which will be the difficulty
    */
    str=getNums(str);
    newstr=str[0];
    for(i=0;i<str.length;i++)
    {
        if(str[i]!=newstr[newstr.length-1])
            newstr+=str[i];
    }
    return (str.length-newstr.length);
}
hardness=[];
for(j=0;j<DIC.length;j++)
{
    hardness.push({
        str:DIC[j],
        h:f(DIC[j])
    });
}
hardness.sort(function(a,b){return (a.h==b.h)?a.str.length - b.str.length:(b.h - a.h)});

console.log("The shortest hardest string to write is: " + hardness[0].str);
console.log("The longest easiest string to write is: " + hardness[hardness.length-1].str);
</script>

output:
The shortest hardest string to write is: gnomonologically
The longest easiest string to write is: hexamethylenetetramine

Other strings that are of the same hardness: pseudomonocotyledonous (only 1)
Other strings that are of the same easiness: hexanitrodiphenylamine, scleroticochorioiditis, electroencephalography, poluphloisboiotatotic... many more

Joe

I tried to do it in JavaScript as well, just to be reminded how much I suck at it.
Here's a program that returns the word with the highest consecutive streak of pressing the same key (there are multiple ones, this returns the first occurrence):

var fs = require('fs');
var dict_filename = "/usr/share/dict/words"

function letterToKey(word) {

    /* Returns a string replacing each letter in the argument word with the
       corresponding key.

       For instance:

       letterToKey("hello") === "43556";
    */

    keypad = {
	'a': '2',
	'b': '2',
	'c': '2',
	'd': '3',
	'e': '3',
	'f': '3',
	'g': '4',
	'h': '4',
	'i': '4',
	'j': '5',
	'k': '5',
	'l': '5',
	'm': '6',
	'n': '6',
	'o': '6',
	'p': '7',
	'q': '7',
	'r': '7',
	's': '7',
	't': '8',
	'u': '8',
	'v': '8',
	'w': '9',
	'x': '9',
	'y': '9',
	'z': '9'
    };

    var key_word = "";

    for(var i=0; i<word.length; ++i) {
	key_word += keypad[word[i].toLowerCase()];
    }

    return key_word;
}

function max_consecutive(key_word) {
    /* Returns the length of the longest streak of consecutive characters in the
       argument word.

       For instance:

       max_consecutive("33444134") === 3;
       max_consecutive("11223334444") === 4;
    */

    var previous = "";
    var longest_streak = 0;
    var new_streak = 0;

    for (var i=0; i<key_word.length; ++i) {
	var current = key_word[i];

	if (current !== previous) {
	    longest_streak = new_streak > longest_streak ? new_streak : longest_streak;
	    previous = current;
	    new_streak = 1;
	} else {
	    new_streak += 1;
	}
    }

    return longest_streak;
}

Array.prototype.index_of_max = function () {
    /* Works only for arrays of numbers.

       Locate the maximum value in an array and returns the index of its first
       occurrence.

       For instance:
       [1, 3, 2].index_of_max() === 1;
       [1, 3, 2, 3].index_of_max() === 1;

       I don't know why this is a method of the prototype and not a stand-alone
       fuction like the others.
    */

    var current_maximum = 0;

    for (var i=0; i<this.length; ++i) {
	current_maximum = Math.max(current_maximum, this[i]);
    }

    return this.indexOf(current_maximum);
};

fs.readFile(dict_filename, 'utf8', function (err,data) {
    // guard in case there's an error opening the file
    if (err) {
	return console.log(err);
    }

    words_array = data.split('\n');
    var key_words = words_array.map(letterToKey);
    var longest_streak_array = key_words.map(max_consecutive);

    console.log(words_array[longest_streak_array.index_of_max()]);
});

CodingFreak

It's been so long since I've visited lebgeeks! Now the questions look easier :)
Here's my answer in C++11:

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <vector>

int main() {

    int points = 0;
    int most_annoying_word_points = 0;
    std::vector<std::string> most_annoying_words;

    // Mapping letters to keys
    std::map<char, int> dumbphone = {
        { 'a', 2 },
        { 'b', 2 },
        { 'c', 2 },
        { 'd', 3 },
        { 'e', 3 },
        { 'f', 3 },
        { 'g', 4 },
        { 'h', 4 },
        { 'i', 4 },
        { 'j', 5 },
        { 'k', 5 },
        { 'l', 5 },
        { 'm', 6 },
        { 'n', 6 },
        { 'o', 6 },
        { 'p', 7 },
        { 'q', 7 },
        { 'r', 7 },
        { 's', 7 },
        { 't', 8 },
        { 'u', 8 },
        { 'v', 8 },
        { 'w', 9 },
        { 'x', 9 },
        { 'y', 9 },
        { 'z', 9 }
    };

    // check for each word
    std::string word;

    // Open dictionary
    std::ifstream dict("/usr/share/dict/words");

    // Check if dictionary is found
    if (dict.is_open()) {

        // For each word
        while (getline(dict, word)) {
            
            // Reset number of points for every word
            points = 0;

            // Loop through all letters of a word
            for (int i = 1; i < word.length(); i++)

                // If the next letter is not a small letter, discard the word an start with the next one
                if ( ! (word.at(i-1) >= 97 && word.at(i-1) <= 122) ) {
                    points = 0;
                    break;
                }

                // Otherwise, compare it with the following letter to see if the same key needs to be pressed
                else if (dumbphone[word.at(i-1)] == dumbphone[word.at(i)])
                    points++;

            // If word has the most points, then remove all previous annoying words and add this one to the list
            if (points > most_annoying_word_points) {
                most_annoying_words.clear();
                most_annoying_word_points = points;
                most_annoying_words.push_back(word);
            }

            // Add to most annoying words if points matches current most annoying word
            else if (points == most_annoying_word_points)
                most_annoying_words.push_back(word);

        }

        // Print the most annoying words
        std::cout << "The most annoying words are" << std::endl << std::endl;
        for (int i = 0; i < most_annoying_words.size(); i++)
            std::cout << most_annoying_words[i] << std::endl;

        std::cout << std::endl << "With " << most_annoying_word_points << " points each " << std::endl;

        // Close dictionary
        dict.close();
    }

    else
        std::cout << "Unable to open file" << std::endl;
    
    return 0;
}

Here's the output:

"The most annoying words are

accommodated
accommodation
accommodations
cannonaded
cannonball
cannonballs
decommissioned
highlighted
highlighters
monotonically
moonlighted
moonlighters
noncommittally
nondenominational
nonprofessional
nonprofessionals
professorships

With 6 points each"

By points I mean the number of waits. I've used the dictionary /usr/share/dict/words on Linux, it would be great if someone could verify the answer. Cheers!

rolf

rahmu wroteMost of you are old enough to remember how incredibly primitive texting

I was able to type messages on my phone without looking at it, even when it's my pocket, texting while I'm driving wtihout endangering my life and the life of others, wth this "incredibly primitive" method...

Obviously

rolf wrote
rahmu wroteMost of you are old enough to remember how incredibly primitive texting
I was able to type messages on my phone without looking at it, even when it's my pocket, texting while I'm driving wtihout endangering my life and the life of others, wth this "incredibly primitive" method...

Same here! I still can't do that on a touch keyboard. But I just send audio notes while driving, a fair solution. Or voice recognition for humorous results.

raja

Just for shits and giggles. Decided to go with shell scripting (semi) one-liners:

$ (cat /usr/share/dict/words | while read word; do echo $(echo $word | tr abcdefghiklmnopqrstuvwxyz 22233344455566677778889999 | grep -o '\([0-9]\)\1\+' | tr -d '\n' | wc -c) $word; done) | sort > /tmp/annoying

Formatted version:

(cat /usr/share/dict/words | while read word; 
do 
   echo $(echo $word | tr abcdefghiklmnopqrstuvwxyz 22233344455566677778889999 | grep -o '\([0-9]\)\1\+' | tr -d '\n' | wc -c) $word
done) | sort > /tmp/annoying

Why? Because I can, that's why.

Note: this took 15min to run on my machine with a 230k words file. So use with care