- Interview with Charles Petzold on WP7 development and more (Dennis Delimarsky)
- How do emulators work and how are they written?
- Is Redis a noSQL db, a cache, or a messaging server?
- Ask HN: Hacker Hobbies?
- The Ultimate Collection of 3DS Max Tutorials
- Just How Fast Is That Code? and Mutating Expressions, Jason Bock
- Augmented Reality Domino Knock-Down Game
- Cassandra by Example. Eric Evans created a nice Cassandra tutorial using building a Twitter clone as an example. Many people want to see more data modeling examples. Here you are.
- Collapse Selection in Solution Explorer – Extension #7
- Applying different matrix transformations on multiple objects
- Making AI work
- Shadows & shadows on other objects…
- Particle Animations using Microsoft XNA:Part II(Article)
- Algorithm: Determine shape of two sectors delineated by an arbitrary path, and then fill one.
- Searching a 25 GB corpus for a single word
- Permutation algorithm in the form of..
- breadth first or depth first search
- Where can I find the diff algorithm?
- How does a hash table work?
- Are there any design-patterns specifically useful for game-development?
- Algorithm for finding the best routes for food distribution in game

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The lowest sum for a set of five primes for which any two primes concatenate to produce another prime: ");`

6:7: TestBenchSetup();8: TestBenchLoader(using_martrix_to_narrow_down_scope_and_probing_for_primes_chain);9:`10: Console.WriteLine("Press any key to exit");`

11: Console.ReadKey();12: }13:14: static readonly int max = 100000000;15: static readonly bool[] master_primes = generate_primes(max);16:`17: /// <summary>`

`18: /// firstly i picked a arbitrary range of primes from 2 to 10000(glad it worked out)`

`19: /// then i created a matrix to find all the pairs of primes can be concat both way`

`20: /// then the probe recursive method is used to find if the prime_chain of length 5 exist`

`21: /// the first chain found should be the answer (and it is!)`

`22: /// sigh, the first solution to break 1-second calculation time (~3s on my pc)`

`23: /// prolly a lot of optimization can be done, but im done with this question for now, theres`

`24: /// way too many other things to do or prepare 😦`

`25: /// </summary>`

`26: /// <returns></returns>`

27: static int using_martrix_to_narrow_down_scope_and_probing_for_primes_chain()28: {29: var primes = master_primes;`30: var size = (int)Math.Sqrt(max);`

31: var matrix = new int[size, size];`32: int row, col;`

`33: for (row = 2; row < size; row++)`

34: {`35: for (col = 2; col < size; col++)`

36: {37: if (primes[row] == false && primes[col] == false && matrix[row, col] == 0)38: {`39: if (concat_both_way(row, col, primes))`

40: {41: matrix[row, col] = 1;42: matrix[col, row] = 1;43: }`44: else`

45: {46: matrix[row, col] = -1;47: matrix[col, row] = -1;48: }49: }50: }51: }52: var count = 5;53: var accum = new int[count];`54: for (row = 3; row < size; row++)`

55: {`56: for (col = 3; col < size; col++)`

57: {`58: if (matrix[row, col] == 1)`

59: {60: accum[5 - count] = row;`61: if (probe(col, matrix, size, count - 1, accum))`

`62: return accum.Sum();`

63: }64: }65: }`66: return 0;`

67: }68:`69: /// <summary>`

`70: /// basically a recursive method that walk the matrix map for possible combination of prime numbers`

`71: /// and keeps drilling down to see if evetually we would have 5 primes that satisified the condition`

`72: /// specified by this problem`

`73: /// how it workrs:`

`74: /// 1. scanning the row givien by the row variable,`

`75: /// 2. find the cell that has the following: 1 as value, produces primes by concat with all the number in accum array`

`76: /// 3. if 2. is true, add the column number to accum array,`

`77: /// 4. if the count variable contain one:`

`78: /// a. true: that means we found all the primes we need, return true.(the accum array now contains all the answer)`

`79: /// b. false: that means we still need to find more primes,`

`80: /// call itself with the column number as row number, and reduce the count by 1.`

`81: /// 5. if the for loop is finished(if we ever get to this point), return false.`

`82: /// </summary>`

`83: /// <param name="row">the row that we want to sweep</param>`

`84: /// <param name="matrix">the map that contains all the possible primes combination</param>`

`85: /// <param name="size">the size(side length) of the matrix</param>`

`86: /// <param name="count">how many more primes to find</param>`

`87: /// <param name="accum">the array contains so far the primes found</param>`

`88: /// <returns>true if we reached the answer(all 5 primes found)</returns>`

89: static bool probe(int row, int[,] matrix, int size, int count, int[] accum)90: {91: for (int col = 3; col < size; col++)92: {`93: if (matrix[row, col] == 1 && isGood(accum, matrix, accum.Length - count, col))`

94: {95: accum[accum.Length - count] = col;`96: if (count == 1)`

97: return true;98:`99: return probe(col, matrix, size, count - 1, accum);`

100: }101: }102: return false;103: }104:`105: /// <summary>`

`106: /// basically checks to see if all the number in accum array can form primes`

`107: /// by concact with "num" in the array with any other in array`

`108: /// </summary>`

`109: /// <param name="accum">array contain numbers</param>`

`110: /// <param name="matrix">prime pair matrix</param>`

`111: /// <param name="count">current "length" of the array</param>`

`112: /// <param name="num">the number to be check against</param>`

`113: /// <returns></returns>`

114: static bool isGood(int[] accum, int[,] matrix, int count, int num)115: {116: for (int i = 0; i < count; i++)117: {`118: if (matrix[num, accum[i]] != 1)`

119: return false;120: }121: return true;122: }123:`124: /// <summary>`

`125: /// baically checks if both n1-n2 and n2-n1 produce prime`

`126: /// </summary>`

127: static bool concat_both_way(int n1, int n2, bool[] primes)128: {129: var num = 0;130:`131: // tail`

132: num = n1 * (int)Math.Pow(10, (int)Math.Log10(n2) + 1) + n2;133: if (primes[num] == true)134: return false;135:`136: // head`

137: num = n2 * (int)Math.Pow(10, (int)Math.Log10(n1) + 1) + n1;138: if (primes[num] == true)139: return false;140:141: return true;142: }143:144: static bool[] generate_primes(int max)145: {`146: var bound = (int)Math.Sqrt(max);`

147: var primes = new bool[max];`148: primes[0] = true;`

`149: primes[1] = true;`

`150: int s, m;`

`151: for (s = 2; s <= bound; s++)`

152: {153: if (primes[s] == false)154: {`155: for (m = s * s; m < max; m += s)`

156: {`157: primes[m] = true;`

158: }159: }160: }`161: return primes;`

162: }163:164: static Stopwatch stopwatch = new Stopwatch();165: static void TestBenchSetup()166: {`167: // Uses the second Core or Processor for the Test`

`168: Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);`

`169: // Prevents "Normal" processes from interrupting Threads`

170: Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;`171: // Prevents "Normal" Threads from interrupting this thread`

172: Thread.CurrentThread.Priority = ThreadPriority.Highest;173: }`174: // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx`

175: static void TestBenchLoader(Func<int> test_method)176: {177: stopwatch.Reset();178: stopwatch.Start();179: var result = 0;`180: long avg_tick = 0;`

`181: long avg_ms = 0;`

182: while (stopwatch.ElapsedMilliseconds < 1200) // A Warmup of 1000-1500 ms`183: // stabilizes the CPU cache and pipeline.`

184: {`185: result = test_method(); // Warmup`

186: }187: stopwatch.Stop();188: for (int repeat = 0; repeat < 20; ++repeat)189: {190: stopwatch.Reset();191: stopwatch.Start();192: result = test_method();193: stopwatch.Stop();194: avg_tick += stopwatch.ElapsedTicks;195: avg_ms += stopwatch.ElapsedMilliseconds;196: }197: avg_tick = avg_tick / 20;198: avg_ms = avg_ms / 20;199: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",200: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));201: }202: }

Advertisements