Another Casual Coder

NP-Complete problems are hard by definition. If you ever face an NP-Complete problem, chances are you'll be trying a bunch of heuristics to find an approximate optimal solution. A problem that I came across recently was this one: given a set of 1000 words, find the minimum subset of words in order to cover all English letters . It is a simple problem statement but behind the scenes this problem is nothing but a variation of the set cover problem , a classic NP-Complete problem. Knowing that the problem is an NP-Complete problem, one quickly realizes that doing a brute-force won't work: we have 1000 words. The number of subsets of all these words is of the order of 2^1000, also known as: 1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825187145285692314043598457757469857480393456777482423098542107460506237114187795418215304647498358194126739876755916554394607706291457119647768654216766042983165262438683720...

I'll now show you a mathematical trick to always win the heads and tails game (for more information about the game itself, please read " heads and tails game - part 1 "). Suppose that your opponent plays something like this: TTTHTHTHTHHHTTT. Here is the simplest and weirdest trick to achieve a 75% chance of winning: O = TTTHTHTHTHHHTTT. Define C = F(O) as follows: Take the second to last element of O. In this case, "T" (TTTHTHTHTHHHT T T) Move that element to the front. Hence so far C = F(O) =  T TTTHTHTHTHHHTT Flip the first element. Hence, C = F(O) = H TTTHTHTHTHHHTT That's all. This will give you a 75% chance of winning - pure magic!!! Well, I win!!! :) You win 269175 times (or 25.3797893244125% of the total) And I win 791413 times (or 74.6202106755875% of the total) Wait, what if we decide to follow the same approach but, instead of using the second to last element, we use, say, the fourth element? Wouldn't that give us an...

Let's suppose that we play the following game: Pick a sequence of heads (H) and tails (T). Any sequence, of a reasonable length, say 10 Suppose your sequence is HTTHTHTHTT. Call this sequence O (for Opponent) The computer will then pick a random sequence of same length Let's suppose the sequence is THHHHTTHHT. Call this sequence C (for Computer) We'll then start tossing coins up randomly, in sequence The first sequence (O or C) to be generated wins a point. Notice that Ad Infinitum eventually O or C will be generated (assuming a reasonably random random-number generator) Repeat steps 5 and 6 for 1M (one million) times Whoever has the most points wins :) We then play this game, and this is one of the results ("I" means the computer): Well, I win!!! :) You win 499610 times (or 49.961% of the total) And I win 500390 times (or 50.039% of the total) Well, pretty close, it could have gone either way, near 50% chance of win to each party. OK, let'...

IBM has a nice monthly programming challenge called IBM Ponder This. If you solve the challenge, you get your name stamped on their page. That's all. Some of the challenges are purely mathematical. Others are purely algorithmic. During the month of September 2016 they released a very nice problem which you can read here:  http://www.research.ibm.com/haifa/ponderthis/challenges/September2016.html The solution requires a couple of interesting steps: Build a simple permutation function (not necessarily needed, you can do the first step to come up with the 4-people permutation by hand. The good thing though is that this would be a good training for he main algorithm) Do a simple DFS generating all the possibilities but not repeating any configuration (which cuts down the tree already) During the DFS calculate the current local penalty Finally, the most important step: trim aggressively by returning right away as soon as the current penalty goes over the best penalty thus far ...