Another Casual Coder

In mathematics there are still many open problems, but they are getting more and more bizarre to even be comprehended. One open problem that is easy to grasp is the following: given a positive integer N, let a partition of N be defined as a summation of positive numbers K = n1+n2+…+nn for 1 <= ni <= N, such that K = N. How many such K’s exist? In other words, how many different ways are there to express a number N as a summation of positive numbers? For example, the number 4 can be written as: 1) 1+1+1+1 2) 1+1+2 3) 1+3 4) 2+2 5) 4 Hence, there are a total of 5 different partitions of the number 4. What would be the formula of #Partitions(N)? No one knows… It is known to be exponential, though. Now, switching to algorithms, how do we write a code to generate all the partitions of a number? Code itself is very suitable for functional language: a base case when the target number reaches 0, followed by the induction where we change not only the starting...

The problem is the following: given a sequence of N numbers (N <= 10), using the most common mathematic operators {+, -, /, *} determine the math expression that will yield the max result. For example, if the numbers given are {1, 2, 3} (and btw, the order matters), you can generate multiple different valid math expressions using {+, -, /, *}, such as: 1 + 2 + 3 = 6 1 / 2 + 3 = 3.5 And so on. However, the expression yielding the max result is 1 + 2*3 = 7. To solve this problem you need two functions, both recursive ones: first to evaluate a math expression. Second, to generate the different expressions. The math expression evaluator needs to take care of the order of the operators properly - a hint is to go right to left and having the operators inside the main for loop in reverse order of precedence, i.e., addition, subtraction, multiplication and division. The use of brackets is important when you have a case like this one: {-0.2, -0.2}. One of the expressions to be formulated...

This is a solution for ACM problem http://acm.tju.edu.cn/toj/showp1022.html . This seems to be a variation of the knapsack problem, where the use of dynamic programming might do the trick, but I opted for a brute-force with some heuristic to cut down the search considerably. The strategy is the following: have a list of parcels; try to fit each square into the current parcel, if the current parcel is full or if it cannot fit into the current parcel, create an extra one and repeat the process. Encapsulating the operations on the parcel within a class helps. My first implementation ran forever. Then the following hypothesis (heuristic?) made all the difference: start with the largest squares first, and if you ever find a set of parcels that fit them all, stop – that will be your minimal set. Now I can’t prove mathematically that the hypothesis is valid, but it seems intuitive and it worked for all the inputs I tried. In the end, a simple line change to go from the largest to the smallest...

This is the solution for the problem http://acm.tju.edu.cn/toj/showp1021.html . The problem deals with the generation of strings based on a very limited grammar. Given the constraints given (only two chars in the allowed alphabet, and the max string length no greater than 15) the problem becomes suitable for a brute-force with few but important optimizations along the way: restrict the search using the length, restrict the search if you have processed that same string before. Note that functional programming seems the ideal tool for this kind of problem (hence, I have changed the coding style to mimic functional programming): using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace LSystem {     class Program     {         static void Main(string[] args)         {         ...

This is the solution to problem http://acm.tju.edu.cn/toj/showp1016.html . I found this problem to be a little complicated, and although the code below solves it I’m inclined to believe this isn’t the most optimal code. There are several techniques worth-mentioning in the solution to this problem: first, the use of a Trie data structure to represent the words in the dictionary. Notice that a Trie is nothing but a tree with each node having potentially multiple child nodes. It is usually a very sparse tree, though. Use the same technique of building a tree: start with a private Node class, and go from there. The use of hashtables come very handy in building the Trie. Next, write a (non-recursive) function to detect whether a certain word belongs to the dictionary, if so return the cumulative probability for that word (or -1 if the word isn’t there). Finally, you’ll need to write some (recursive) code to generate the potential permutations given a sequence of digits. Because you don’t kn...