its Friday~

Project Euler problem 14~

  1: class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The starting number which under one million and produces the longest chain");
  8:             sw.Start();
  9:             var sum1 = test1();
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("hand roll for-loop memoization brute force way(ms:{0}): {1}", sw.ElapsedMilliseconds, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             sw.Start();
 16:             var sum2 = test2();
 17:             sw.Stop();
 18:             Console.WriteLine(string.Format("no memoization for-loop brute force way(ms:{0}): {1}", sw.ElapsedMilliseconds, sum2));
 19: 
 20:             sw.Reset();
 21: 
 22:             sw.Start();
 23:             var sum3 = test3();
 24:             sw.Stop();
 25:             Console.WriteLine(string.Format("cool LINQ recursive memoization brute force way(ms:{0}): {1}", sw.ElapsedMilliseconds, sum3));
 26: 
 27:             Console.WriteLine("Press any key to exit");
 28:             Console.ReadKey();
 29:         }        
 30: 
 31:         /// <summary>
 32:         /// wow took unusually long on this question, 
 33:         /// formulated the code to get the answer but it was wrong,
 34:         /// finally i gave up and google for solution
 35:         /// turns out the "current" can be greater than int, so had to use long
 36:         /// lawl~~~~~~
 37:         /// pretty interesting that linq recursive solution is slightly faster
 38:         /// since its caching a lot more comparing to test1 (999999 vs 2168611 entries), probably negate 
 39:         /// linq and recursive overhead.
 40:         /// but then again, i cant think of a way for for loop to cache same as recurive way, cant do backtrack
 41:         /// </summary>
 42:         /// <returns></returns>
 43:         static int test1()
 44:         {
 45:             var map = new Dictionary<long, int>();
 46:             long current = 0;
 47:             var count = 0;
 48:             var max = 0;
 49:             var max_index = 0;
 50:             for (int i = 1; i < 1000000; i++)
 51:             {
 52:                 current = i;
 53:                 count = 1;
 54:                 while (current > 1)
 55:                 {
 56:                     if (map.ContainsKey(current))
 57:                     {
 58:                         count += map[current];
 59:                         break;
 60:                     }
 61: 
 62:                     current = current % 2 == 0 ?
 63:                         current = current / 2 : current = 3 * current + 1;
 64: 
 65:                     count++;
 66:                 }
 67:                 map[i] = count;
 68:                 if (count > max)
 69:                 {
 70:                     max = count;
 71:                     max_index = i;
 72:                 }
 73:             }
 74:             return max_index;
 75:         }
 76: 
 77:         static int test2()
 78:         {
 79:             long current = 0;
 80:             var count = 0;
 81:             var max = 0;
 82:             var max_index = 0;
 83:             for (int i = 1; i < 1000000; i++)
 84:             {
 85:                 current = i;
 86:                 count = 1;
 87:                 while (current > 1)
 88:                 {
 89:                     current = current % 2 == 0 ?
 90:                         current = current / 2 : current = 3 * current + 1;
 91: 
 92:                     count++;
 93:                 }
 94:                 if (count > max)
 95:                 {
 96:                     max = count;
 97:                     max_index = i;
 98:                 }
 99:             }
100:             return max_index;
101:         }
102: 
103:         static int test3()
104:         {
105:             var cache = new Dictionary<long, int>();
106:             var ChainCount = Memoize<long, int>(((n, self) => 
107:                 n <= 1 ? 1 : n % 2 == 0 ? 1 + self(n / 2) : 1 + self(3 * n + 1)), cache);
108: 
109:             return Enumerable.Range(1, 1000000)
110:                 .Select(n => ChainCount(n))
111:                 .MaxIndex() + 1;
112:         }
113: 
114:         /// <summary>
115:         /// found on http://explodingcoder.com/cms/content/painless-caching-memoization-net
116:         /// written by spoulson
117:         /// </summary>
118:         public static Func<TArg, TResult> Memoize<TArg, TResult>
119:             (Func<TArg, Func<TArg, TResult>, TResult> function, IDictionary<TArg, TResult> cache)
120:         {
121:             Func<TArg, TResult> memoizeFunction = null;
122:             return memoizeFunction = key => cache.ContainsKey(key) ? cache[key] : (cache[key] = function(key, memoizeFunction));
123:         }
124:     }
125:     static class Extension
126:     {
127:         /// <summary>
128:         /// http://stackoverflow.com/questions/462699/how-do-i-get-the-index-of-the-highest-value-in-an-array-using-linq
129:         /// written by Jon skeet
130:         /// </summary>
131:         public static int MaxIndex<T>(this IEnumerable<T> sequence)
132:             where T : IComparable<T>
133:         {
134:             int maxIndex = -1;
135:             T maxValue = default(T); // Immediately overwritten anyway
136: 
137:             int index = 0;
138:             foreach (T value in sequence)
139:             {
140:                 if (value.CompareTo(maxValue) > 0 || maxIndex == -1)
141:                 {
142:                     maxIndex = index;
143:                     maxValue = value;
144:                 }
145:                 index++;
146:             }
147:             return maxIndex;
148:         }
149:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s