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;
		}
	}	
}