## Google Code Jam: Text Messaging Outrage

Round 1C began with the "Text Messaging Outrage" problem which basically asks that we identify the most efficient letter-to-key assignment on a phone to minimize the number of key presses needed by users. Google quite helpfully provide a frequency distribution for each letter. Given the frequency distribution it's obvious what the optimal assignment is - for the letters that are most frequently used assign them key press combinations that require the fewest key presses. Technically speaking this is a *greedy approach *and it should be intuitively obvious why it produces the optimal assignment.

This was one of the easiest problems encountered so far! Here's the code in C#:

using System; using System.IO; namespace GoogleCodeJam.TextMessage { class Program { static void Main() { string basePath = ""; StreamReader infile = new System.IO.StreamReader(basePath + "large.txt"); StreamWriter outfile = new System.IO.StreamWriter(basePath + "output.txt"); int testCases = Int32.Parse(infile.ReadLine()); for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based { long minKeyPressCount = 0; // read in the input data string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None); int P = Int32.Parse(data[0]); // max number of letters to place on a key int K = Int32.Parse(data[1]); // number of keys available int L = Int32.Parse(data[2]); // number of letters in the alphabet // read in the letter frequencies int[] frequencies = new int[L]; int[] indexes = new int[L]; string[] freqData = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None); int i = 0; foreach (string s in freqData) { indexes[i] = i; frequencies[i] = Int32.Parse(s); i++; } int nextKfree = 0; // the one-based index of the key with the next lowest key press combo int nextPfree = 1; // the one-based index of the letter on the "low key" with the next lowest key press combo // map the most used letters to the shortest key press routines available Array.Sort(frequencies,indexes); // ~ O(n log n) on average since it uses an unstable QuickSort internally Array.Reverse(frequencies); // ~ O(n) Array.Reverse(indexes); // ~ O(n) int ii = 0; foreach (int x in indexes) // from greatest- to least-used index { // find the next available key press combo walking through from cheapest to dearest nextKfree++; if (nextKfree > K) { nextKfree = 1; nextPfree++; } checked { minKeyPressCount += (frequencies[ii] * nextPfree); } ii++; } // write out the results outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, minKeyPressCount)); } infile.Close(); outfile.Flush(); outfile.Close(); } } }

*30 Jul 2008*
*Damien Wintour*
2 comments