Ponder This Oct 2016: irrational numbers, hash-tables and string manipulation

The IBM Ponder This October challenge is now available here and it seems to be a quite interesting problem. In essence, it is asking for the first 5-digits long sub-sequence that is common to all numbers e, PI and square-root of 2. This post describes one way to approach and solve this problem.

First, all these three numbers are irrational numbers. The importance of this fact in the context of this problem is that as you generate more and more digits for these numbers, the fact that they are irrational means that they will never repeat, and as such the chances of generating all different 5-digits numbers is quite high. And how many 5-digits numbers are there? Not that many. More precisely, 100,000 (from 00000 to 99999). Hence, assuming that we have a way to generate their digits, we can relatively quickly find all these 100,000 sequences as we go along. We can use a hash-table to store those numbers, and when they were found. One hash-table per number, hence a total of three hash-tables.

Second, and the arguably tricky part: how to generate the digits of these numbers? Well, don't. Look up online and you'll certainly find these numbers up to as many digits as you want. My hunch is that if you find them up to 2,000,000 digits, that should be good enough.

From this point on it becomes straightforward:
 - Read the numbers e, PI and sqrt(2)
 - Do a string parsing looking for the 5-digits sub-strings
 - Fill up their hash-tables
 - Then, parse the content in their hash-tables and store the match with the least amount of time
 - Transform the time from seconds to HH:MM:SS

Here is the result for 2-digits sub-sequences:

And if you run for 5-digits sub-sequence, you also get the result, which I'm obfuscating in order to not spoil the fun:

Code is down below - cheers, Marcelo.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Collections;

namespace IBMPonderThisOctober2016
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] filesWithDigits = { "e.txt", "pi.txt", "sqrt2.txt" };
            Hashtable[] htMaps = new Hashtable[filesWithDigits.Length];

            for (int i = 0; i < htMaps.Length; i++)
            {
                htMaps[i] = new Hashtable();
            }

            int MAXDIGITS = 2000000;
            int LENDIGITS = 5;
            for (int i = 0; i < filesWithDigits.Length; i++)
            {
                CreateMap(filesWithDigits[i],
                          MAXDIGITS,
                          LENDIGITS,
                          htMaps[i]);
            }

            int minTime = Int32.MaxValue;
            string bestNumber = "";
            for (int i = 0; i < (int)Math.Pow(10, LENDIGITS); i++)
            {
                int candidateTime = 0;
                for (int j = 0; j < htMaps.Length; j++)
                {
                    if (!htMaps[j].ContainsKey(i.ToString()))
                    {
                        candidateTime = Int32.MaxValue;
                        break;
                    }
                    else
                    {
                        candidateTime += (int)htMaps[j][i.ToString()];
                    }
                }

                if (candidateTime < minTime)
                {
                    minTime = candidateTime;
                    bestNumber = i.ToString();
                    Console.WriteLine("Candidate number {0} generated after {1} seconds", bestNumber, minTime);
                }
            }

            Console.WriteLine();
            if (minTime < Int32.MaxValue)
            {
                Console.WriteLine("Solution:");
                Console.WriteLine("Number {0} generated after {1}", bestNumber, ConvertToHMS(minTime));
            }
            else
            {
                Console.WriteLine("No Solution");
            }
        }

        public static void CreateMap(string digitsFile,
                                     int maxDigits,
                                     int lenDigits,
                                     Hashtable htMap)
        {
            Console.Write("Reading digits file {0}...", digitsFile);
            FileInfo fi = new FileInfo(digitsFile);
            StreamReader sr = fi.OpenText();

            string d = "";
            while (!sr.EndOfStream && d.Length < maxDigits)
            {
                d += sr.ReadLine().Trim();
            }

            sr.Close();
            Console.WriteLine("Done (read {0} digits)", d.Length);

            Console.Write("Creating map for sequence of length {0}...", lenDigits);
            string current = "";
            for (int i = 0; i < d.Length && i < maxDigits && htMap.Count < (int)Math.Pow(10, lenDigits); i++)
            {
                if (current.Length < lenDigits)
                {
                    current += d[i].ToString();
                }
                else
                {
                    current = current.Substring(1) + d[i].ToString();
                }

                if (current.Length == lenDigits && !htMap.ContainsKey(current))
                {
                    htMap.Add(current, i + 1);
                }
            }
            Console.WriteLine("Done!");
            Console.WriteLine("Map count = {0}", htMap.Count);
        }

        public static string ConvertToHMS(int seconds)
        {
            int s = seconds % 60;
            int m = (seconds / 60) % 60;
            int h = m / 60;

            string ret = "";

            if (h < 10)
            {
                ret += "0";
            }
            ret += h.ToString();
            ret += ":";

            if (m < 10)
            {
                ret += "0";
            }
            ret += m.ToString();
            ret += ":";

            if (s < 10)
            {
                ret += "0";
            }
            ret += s.ToString();

            return ret;
        }
    }
}