using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace CSharp
{
    class Program
    {
        static Dictionary<uint, bool?> happyNumbers = new Dictionary<uint, bool?> { {1, true} };

        static void Main (string [] args)
        {
            while (true) {
                happyNumbers.Clear ();
                Console.Write ("Pick an upper bound: ");
                var input = Console.ReadLine ();
                if (string.IsNullOrEmpty (input)) break;
                var upperBound = uint.Parse (input);
                var stopWatch = new Stopwatch ();
                stopWatch.Start ();
                var happies = HappyNumbers (upperBound);
                stopWatch.Stop ();
                Console.WriteLine ("Time taken to calculate numbers: {0}", stopWatch.Elapsed);
                Console.WriteLine ("{0} happy number(s) between 0 and {1}.", happies.Count (), upperBound);
                // I know this is slow, but I'm not timing the generation of the string
                Console.Write ("Do you want the list? (Y/N)");
                var list = Console.ReadLine ();
                if (list.ToUpper ().Equals ("Y")) {
                    var numberList = string.Join (",", happies.Select (num => num.ToString ()).ToArray ());
                    Console.WriteLine ("Number list: {0}", numberList);
                }
            }
        }

        static IEnumerable<uint> HappyNumbers (uint upperBound) {
            var numbers = new List<uint> { 1 };
            for (uint current = 2; current < upperBound; ++current) {
                var happiness = IsHappy (current);
                if (happiness.HasValue && happiness.Value) numbers.Add (current);
            }
            return numbers;
        }

        static bool? IsHappy (uint value)
        {
            bool? happiness;

            if (happyNumbers.TryGetValue (value, out happiness)) {
                if (happiness == null) return happyNumbers[value] = false;
            } else {
                happyNumbers[value] = happiness = null;
                uint newValue = 0;

                for (uint i = value; i != 0; i /= 10) {
                    uint lsd = i % 10;
                    newValue += lsd * lsd;
                }

                if (newValue == 1) happiness = true;
                else happiness = IsHappy (newValue);

                if (happiness.HasValue && happiness.Value) happyNumbers[value] = true;
                else happyNumbers[value] = happiness;
            }

            return happiness;
        }
    }
}