GCJ Africa 2010 - T9 Spelling
The T9 Spelling problem in the qualification round of Google Code Jam Africa 2010 is, like the other problems in this round, fairly trivial. For some given text sequences you need to map them to key presses on a numeric key pad provided. You just need to look through each character provided and replace it with the appropriate key press sequence. Here I'm making use of a dictionary to ensure constant time lookup operations for mapping characters to key press sequences, and I track the last key pressed so I know when to insert a "pause" (denoted by a 0).
Here's some simple C# code that solves it [running time is O(n) for strings of size n]:
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
namespace GoogleCodeJam.Africa2010.T9Spelling
{
class Program
{
static void Main()
{
const string basePath = @"C:\";
var infile = new StreamReader(basePath + "large.txt");
var outfile = new StreamWriter(basePath + "output.txt");
var map = new Dictionary<string, string>
{
{"a", "2"},
{"b", "22"},
{"c", "222"},
{"d", "3"},
{"e", "33"},
{"f", "333"},
{"g", "4"},
{"h", "44"},
{"i", "444"},
{"j", "5"},
{"k", "55"},
{"l", "555"},
{"m", "6"},
{"n", "66"},
{"o", "666"},
{"p", "7"},
{"q", "77"},
{"r", "777"},
{"s", "7777"},
{"t", "8"},
{"u", "88"},
{"v", "888"},
{"w", "9"},
{"x", "99"},
{"y", "999"},
{"z", "9999"},
{" ", "0"}
};
int n = Int32.Parse(infile.ReadLine());
for (int caseNo = 1; caseNo <= n; caseNo++)
{
var msg = infile.ReadLine();
var answer = new StringBuilder();
int last = -1;
for (int i = 0; i < msg.Length; i++)
{
string mapped = map[msg[i].ToString()];
if (mapped[0] == last)
answer.Append(" ");
answer.Append(mapped);
last = mapped[0];
}
outfile.WriteLine("Case #{0}: {1}",caseNo, answer);
}
infile.Close();
outfile.Close();
}
}
}
18 Apr 2010 Damien Wintour
