bunch of stuff

Project Euler problem 90~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The numbers of distinct arrangements: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_Monte_Carlo_ish_simulation_to_generate_dices_and_count_distinct);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically using Fisher–Yates shuffle to "produce" dices and then use Trie to keep track of 
 16:         /// distincts dices combinations in monte carlo-ish simulation runs until no more new "count"
 17:         /// </summary>
 18:         static int using_Monte_Carlo_ish_simulation_to_generate_dices_and_count_distinct()
 19:         {
 20:             var squares = new int[9, 2]
 21:             {
 22:                 {0,1}, //0
 23:                 {0,4}, //1
 24:                 {0,9}, //2-
 25:                 {1,6}, //3-
 26:                 {2,5}, //4
 27:                 {3,6}, //5-
 28:                 {4,9}, //6-
 29:                 {6,4}, //7-
 30:                 {8,1}  //8
 31:             };
 32:             // dice related variables, seed1 and seed2 are used to be shuffle around to generate dices
 33:             var seed1 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 34:             var seed2 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 35:             var d1 = new bool[10];
 36:             var d2 = new bool[10];
 37:             var d1d2 = new bool[20];
 38:             var trie = new Trie();
 39:             var rnd = new Random();
 40:             var limit = 600000; // 600k sim runs seem to be good enough to stablely produce answer
 41:             var count = 0;
 42:             while (--limit > 0)
 43:             {
 44:                 shuffle(seed1, rnd);
 45:                 shuffle(seed2, rnd);
 46:                 for (int i = 0; i < 10; i++)
 47:                 {
 48:                     d1[i] = false;
 49:                     d2[i] = false;
 50:                 }
 51:                 for (int i = 0; i < 6; i++)
 52:                 {
 53:                     d1[seed1[i]] = true;
 54:                     d2[seed2[i]] = true;
 55:                 }
 56:                 if (validate(squares, d1, d2) == true)
 57:                 {
 58:                     for (int i = 0; i < 10; i++)
 59:                     {
 60:                         d1d2[i] = d1[i];
 61:                         d1d2[i + 10] = d2[i];
 62:                     }
 63:                     if (trie.Insert(d1d2) == false)
 64:                     {
 65:                         count++;
 66:                     }
 67:                 }
 68:             }
 69:             // divide by 2 since order of dice1 and dice2 doesnt matter, took awhile to find out 😦
 70:             return count % 2 == 0 ? count / 2 : count / 2 + 1; 
 71:         }
 72: 
 73:         /// <summary>
 74:         /// bascially using the Fisher–Yates shuffle to "randomly" generate dice
 75:         /// http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
 76:         /// </summary>
 77:         static void shuffle(int[] dice, Random rnd)
 78:         {
 79:             for (int i = dice.Length; i > 1; i--)
 80:             {
 81:                 var j = rnd.Next(i);
 82:                 var tmp = dice[j];
 83:                 dice[j] = dice[i - 1];
 84:                 dice[i - 1] = tmp;
 85:             }
 86:         }
 87:         /// <summary>
 88:         /// check to see if d1 and d2 can form all the square numbers and also satisfied the rule such that
 89:         /// 6 and 9 can be treated interchangeably
 90:         /// </summary>
 91:         /// <param name="criteria">all of the square numbers below one-hundred</param>
 92:         /// <param name="d1">1st dice</param>
 93:         /// <param name="d2">2nd dice</param>
 94:         /// <returns>true for pass</returns>
 95:         static bool validate(int[,] criteria, bool[] d1, bool[] d2)
 96:         {
 97:             int a, b;
 98:             for (int i = 0; i < 9; i++)
 99:             {
100:                 a = criteria[i, 0];
101:                 b = criteria[i, 1];
102:                 // ugly crap, but orwill
103:                 if (i == 0 || i == 1 || i == 4 || i == 8)
104:                 {
105:                     if (((d1[a] && d2[b]) || (d1[b] && d2[a])) == false)
106:                         return false;
107:                 }
108:                 else
109:                 {
110:                     if (a == 6 || a == 9)
111:                     {
112:                         if ((((d1[6] || d1[9]) && d2[b]) || (d1[b] && (d2[6] || d2[9]))) == false)
113:                             return false;
114:                     }
115:                     else if (b == 6 || b == 9)
116:                     {
117:                         if (((d1[a] && (d2[6] || d2[9])) || ((d1[6] || d1[9]) && d2[a])) == false)
118:                             return false;
119:                     }
120:                 }
121:             }
122:             return true;
123:         }
124: 
125:         /// <summary>
126:         /// to be used in Trie, with array[0 to 9] for dice1 and [10 to 19] for dice2
127:         /// </summary>
128:         class Node
129:         {
130:             public Node[] nodes;
131:             public Node()
132:             {
133:                 nodes = new Node[20];
134:             }
135:             public bool Contain(int n)
136:             {
137:                 return nodes[n] != null;
138:             }
139:             public Node GetChildren(int n)
140:             {
141:                 return nodes[n];
142:             }
143:         }
144: 
145:         /// <summary>
146:         /// using Trie to save all the distinct 1st and 2nd dice combinations.
147:         /// </summary>
148:         class Trie
149:         {
150:             public Node root;
151:             public Trie()
152:             {
153:                 root = new Node();
154:             }
155:             /// <summary>
156:             /// inserts element into trie
157:             /// </summary>
158:             /// <param name="d1d2">concatenation of dice1 and dice2</param>
159:             /// <returns> true if already existed, false otherwise</returns>
160:             public bool Insert(bool[] d1d2) //d1d2, concatenation of d1[0 to 9], d2[10 to 19]
161:             {
162:                 bool existed = true;
163:                 Func<int, Node, Node> insert = null;
164:                 insert = (num, parent) =>
165:                     {
166:                         if (parent.Contain(num) == true)
167:                             return parent.GetChildren(num);
168:                         else
169:                         {
170:                             var newNode = new Node();
171:                             parent.nodes[num] = newNode;
172:                             existed = false;
173:                             return newNode;
174:                         }
175:                     };
176:                 var node = root;
177:                 for (int i = 0; i < d1d2.Length; i++)
178:                 {
179:                     if (d1d2[i] == true)
180:                         node = insert(i, node);
181:                 }
182:                 return existed;
183:             }
184:         }
185: 
186:         static Stopwatch stopwatch = new Stopwatch();
187:         static void TestBenchSetup()
188:         {
189:             // Uses the second Core or Processor for the Test
190:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
191:             // Prevents "Normal" processes from interrupting Threads
192:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
193:             // Prevents "Normal" Threads from interrupting this thread
194:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
195:         }
196:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
197:         static void TestBenchLoader(Func<int> test_method)
198:         {
199:             stopwatch.Reset();
200:             stopwatch.Start();
201:             var result = 0;
202:             long avg_tick = 0;
203:             long avg_ms = 0;
204:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
205:             // stabilizes the CPU cache and pipeline.
206:             {
207:                 result = test_method(); // Warmup
208:             }
209:             stopwatch.Stop();
210:             for (int repeat = 0; repeat < 20; ++repeat)
211:             {
212:                 stopwatch.Reset();
213:                 stopwatch.Start();
214:                 result = test_method();
215:                 stopwatch.Stop();
216:                 avg_tick += stopwatch.ElapsedTicks;
217:                 avg_ms += stopwatch.ElapsedMilliseconds;
218:             }
219:             avg_tick = avg_tick / 20;
220:             avg_ms = avg_ms / 20;
221:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
222:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
223:         }
224:     }

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