Another Casual Coder

"S he played out to me to me!!! in those two years till sometimes dropping from the devil foe, I triumphed!!! and singing the least some one! big words that cover "                                                - By ThinkPad Lenovo X220, 2012-? A poem is a work of art. But it can also be seen as a work of science! This post is about teaching a computer in < 600 lines of code how to create English poems. Well, poems in general are abstract entities, so if the computer is going to learn how to write poems, it will have to learn that poems are most of the time deeply abstract, and deeply complex to understand :) To a degree, that makes our lives easier. Ok, so how do we go about teaching a computer how to write somewhat valid (albeit abstract!) poems? We'...

The hint!!!! Hope it sheds some light: let's assume that we want to get the last 10 decimal digits of another big number, such as: 8^1234. We can do it by using the mod operator: (8^1234)%10000000000. Try Bing , it will give you the answer: 4154645504 Now, instead of raising 8 to 1234, let's now assume that we want the last 10 digits of an even larger number: 8^45671234. Same approach, use the mod operator, unfortunately this time the number is too big for either Bing, or Google, or even WolfranAlpha to return an answer, but anyways, I got the answer to (8^45671234)%10000000000: 0273045504 Now, take a look at these two numbers and look at the common digits towards the end: (8^1234)%10000000000          = 41546 45504 (8^(45671234)%10000000000 = 02730 45504 See the "coincidence"? If we're raising a number K to N where N is a number with D digits, the last (D+1) digits of the result will be the same as if we raise the numb...

The problem in this post is related to subsets, and the solution shows a nice trick to avoid mystical recursive solutions. The enumeration for the problem is simple: given a set S of numbers (integers) and a target number N, print all the subsets S' of S such that Summation(S') = N. The trick to generate the subsets lies in the binary representation of a number. Suppose that we want to generate all the subsets of a set with 3 elements. We know from basic set theory that the number of subsets of this set is 2^3, also known as 8. Now let's see the binary representation of all the numbers from 0 to 7: 0 = 0 0 0 1 = 0 0 1 2 = 0 1 0 3 = 0 1 1 4 = 1 0 0 5 = 1 0 1 6 = 1 1 0 7 = 1 1 1 The bits interpretation here should be: " if the bit is 1, then the element at that position belongs to the subset ". Hence take for instance the number 3: 3 = 0 1 1 Since our original set has 3 elements, say {a,b,c}, this third subset should contain only elements b and c sin...

The problem comes from the IBM Ponder This October 2014 Challenge: http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/October2014.html What are the last 10 decimal digits of 2^(3^(4^(5^(6^(7^(8^9))))))? This is a big number. If you just take 8^9, you'll end up with 134,217,728. Now try raising, say, 2 to the power of this number, or 2^134,217,728. For comparison sake, the number of atoms in the universe is less than 2^324. The problem is asking for the last 10 decimal digits, so that should have been an important clue. It should have rang a bell for two key ideas behind solving this problem: 1) Modular Arithmetic : to get the last 3 digits of 1234, all I have to do is calculate 1234%(10^3) 2) Big Integers . Try Binging for Big Integers in C# . Solution in the next post. Have fun!

If a solution to a problem smells like Dijkstra's Algorithm, chances are it is one. Take a look at the problem described here: http://codercareer.blogspot.com/2014/10/no-56-maximal-value-of-gifts.html . In essence, you're given a matrix (I call it a maze) and with a very strict rule to moving around, you have to find the max path from the top leftmost cell to the bottom rightmost one. The solution given in the link is a very elegant DM (Dynamic Programming) one. There is also a brute-force one which we won't get into. But I actually wanted to use this problem to exemplify the application of Dijkstra's Algorithm. It is a little overkill to use Dijkstra here, but I find this problem the perfect simple one to exemplify Dijkstra's. Dijkstra's Algorithm is a weighted BFS (breadth-first search). One needs to make use of a Priority Queue (PQ) class (down below). The overall idea of Dijkstra's is the following: Determine whether your PQ will work in ascending or ...