The Reverse Words problem in the qualification round of Google Code Jam Africa 2010 is trivial. You are given a bunch of space separated words that you need to re-order (just the words, not the characters within the words). The number of words is, at most, 1000 so doing everything in memory is entirely feasible on a modern computer. Just be sure to watch out for the separating spaces in the result. You don't want any leading/training spaces.

Here's some simple C# code that solves it [running time is O(n) for n words. Space required is solely to hold the input values plus a small constant overhead to build the result]:

using System;

using System.IO;

using System.Text;

 

namespace GoogleCodeJam.Africa2010.ReverseWords

{

    class Program

    {

        static void Main()

        {

            const string basePath = @"C:\";

            var infile = new StreamReader(basePath + "B-large-practice.in");

            var outfile = new StreamWriter(basePath + "output.txt");

 

            int n = Int32.Parse(infile.ReadLine());

            for (int caseNo = 1; caseNo <= n; caseNo++)

            {

                var words = infile.ReadLine().Trim().Split(new []{' '});

                var answer = new StringBuilder();

                for (int i = words.Length-1; i >= 0; i--)

                    answer.Append(" " + words[i]);

 

                outfile.WriteLine("Case #{0}: {1}",

                                    caseNo, answer.ToString().Trim());

            }

            infile.Close();

            outfile.Close();

        }

    }

}

Bookmark and Share