MacGyver Development

Solve the party planning problem and earn $1 000 000 USD

2015-01-07T10:48:00.000+01:00

The party planning problem deals with a village of 200 people where two villagers either are friends or dislike each other. A big party is to be planned and your task is to find the largest set of people in the village to be invited to the party fulfilling the condition that all the invited people must be friends with each other.

This seems like an ordinary puzzle that could take some hours to figure out. However, after giving it some thought, it turns out to be a quite hard problem. In fact it is a version of a well known problem called the “Clique problem”. It is the mother of hard problems and is intricately connected to other hard problems such as prime factorization, the knapsack problem and the travelling salesman. This problem is so hard that the Clay Mathematics Institute has offered a prize of $1 000 000 to anyone who can show that this or similar problems in the same class of problems can be solved in a practical way. Likewise, you win the money for showing that it is impossible to solve these problems without spending an amount of time in comparison to the age of the universe.

Before going into the fascinating details of this problem we should start with discussing what easy and hard problem really are from a computational standpoint. Consider the problem of solving the multiplication of 17 x 13. If you can’t solve this directly in your head you know a method from school on how to multiplicate the digits individually to come to the conclusion that the product is 221. If feels like an easy problem. Consider the reverse, what numbers should you multiply to get 221? This is harder, we probably have to test a lot of numbers to see if they divide 221 without a remainder to finally find that 17 and 13 are the factors of 221.

Now consider the same problem but with the numbers 37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061. If you’re not Rainman you will probably not do the multiplication in your head but you could do it with a pen and paper and some spare time. A computer would calculate the product in a split second. What about the reverse? Finding what two numbers to multiply to receive the product 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 turns out to be extremely hard even with the help of a computer. It is so hard that this is the cornerstone of communication security on the Internet (RSA cryptography).

What is the actual difference? For these kind of problems we have methods also known as algorithms which acts as recipes on how to produce a solution to a specific kind of problem. In the case of multiplication we know from school that we should write the numbers above each other and multiply each digit with all the digits in the other number. The total number of simple operations will in this case be n² if the numbers have n digits. This is a common way to denote how hard a problem is to solve. If the problem has an input of size n, in this case the number of digits in the numbers to multiply, the solution will require us to perform a number of simple operations proportional to some function of n, in this case n². If you remember from school, a polynomial is a function where the variable is raised to different powers such as n¹ + n² + n³ + … n^x. So the complexity of the multiplication problem which is n² is a polynomial.

A problem which can be solved with an algorithm that performs something proportional to a polynomial number of operations in relation to the size of the input is considered an easy problem. There is in fact a name for these kind of problems. They belong to the class P of problems where P means that they can be solved in polynomial time.

Now let’s consider the reverse of our math problem where we tried to find the factors of the product. In this case, since we must test numbers smaller than the product for divisibility, the number of simple operations needed in this naive algorithm will grow exponentially with the number of digits in the product. For example, to find the factors of 221 we have to try whether it is divisible by 2, 3, 4, 5 … and so on. A number of one more digit like 5671 would require 10 times as many tries.

Problems like this where the number of operations needed to find the solution grows exponentially with the size of the input are considered hard. An interesting thing about this hard problem is that if you in some way find a solution (the factors of the number), it is an easy thing to verify that the solution is correct. You would simply multiply the factors and see whether they really produce the product. More formally, the task to verify the solution is in the class P of problems.

Now we’re closing in on the $1 000 000 problem. All these problems, which seems very hard to solve, but once you have a solution it is straight forward to verify that the solution is correct, are called NP problems (nondeterministic polynomial time). This means that we don’t really know the complexity to solve them, but a solution can be verified with an algorithm that belongs to class P (an easy task). To win the money you must show that either P = NP or P ≠ NP. That means, either you must prove that you can solve an NP problem in a fast way or show that this is impossible and there can’t exist any algorithm however smart it is that can solve these problems in a fast way.

Do you see the connection with the party planner problem? It is hard to find a group of people which all are friends among all the presumably invited persons. But once you have found this group, it is easy to verify that all these persons really are friends.

Another way to state this is that all these problems are some sort of search problems. You try to search for factors of number, a subset of party people or for all the other NP problems there are similar searches needed. The thing you win the money for is to determine whether you can solve these type of search problems without actually need to search out all the possibilities in a brute force manner which often means an exponential number of operations to test all combinations.

Let’s take a closer look at the party planning problem, or as we will call it from now, the Clique problem. We simplify our example and assume that there are seven people in the village and they can be represented as a graph. Each villager is a node in the graph and paths between two nodes indicates that the corresponding villagers are friends with eachother. The problem now is to find the largest subgraph where each node is connected to all other nodes in the subgraph. Such a subgraph is called a clique.

The naive algorithm would try all combinations to verify whether there is a clique of size 1, 2, 3 and so on until no such clique can be found. In the example below an exhaustive search is made to find a valid clique of size 4.

See how the search complexity would explode in possible permutations when increasing the number of nodes to 8, 9, 10...?

There are many NP problems which on the surface seems very different. Some famous examples include the travelling salesman problem (TSP) where you search for a tour between a set of cities shorter than a given length. The boolean satisfiability problem (SAT) where you try to find a configuration for a set of boolean variables that makes an expression true. For example the expression (a AND NOT b) can be evaluated to true if a = true and b = false. There are no known algorithms to solve these problems in polynomial time.

Now for some mind boggling facts about these problems. The clique problem together with several other NP problems are part of a special subclass in NP called NP-complete problems. Such problems have the property that all other NP problems can be converted to them in polynomial time. This means that for example the problem of factorizing a large number can in a fast way be remade into a graph clique problem. Solve the clique problem and you have the answer for the factorization.
See what this implies? If you can find a fast way of solving the clique problem or any other NP complete problem you have as a side effect solved all other NP problems since they can trivially (in respect to computational time) be converted to that problem.

If this algorithm was discovered, the digital landscape would be completely changed. Internet security would become obsolete over night and many other applications could be revolutionized with faster algorithms.

The NP equals P problem is probably the most famous open question within the field of computational computer science. Solve it and your name will be engraved in various precious metals.

Footnote:
The numbers for the example of large prime factorization described in this article are in fact taken from another challenge given by the RSA company. They posted publically a set of large semi prime numbers in 1991. A semi prime number is the factor of two primes. Each number had a reward attached so that when someone managed to factor the number they could claim prizes from $1,000 up to $200,000 USD. The numbers ranged from 330 to 2048 binary digits. The reason for this was to survey the academic landscape and find the cutting edge algorithms for prime factorization which their cryptographic product is based on. To current date all challenges up to 768 digits ($50,000) are beaten by various teams around the world. The challenge was discontinued in 2007.

Raspberry Pi Weather Station with multiple thermometers

2015-01-06T13:41:00.000+01:00

Last Christmas I gave my father in law a weather station to monitor temperature inside their summer house to avoid the pipes to freeze during the winter. It has been working well but has only been measuring the temperature inside the house. During the holiday we added another sensor to be able to also read the temperature outside the house.
See this blog post for the original setup
http://macgyverdev.blogspot.se/2014/01/weather-station-using-raspberry-pi.html

Adding more thermometers is straight forward since the sensor used, a digital DS18B20, uses the OneWire protocol which the Raspberry Pi has drivers for. Adding more sensors doesn't require more ports on the Pi but instead reuses the same three ports for power, ground and data as the first sensor. Each thermometer has a unique hard wired address which is used to communicate over the data wire with the Raspberry Pi driver.

Programmatically, the new sensor is represented as a device folder in /sys/bus/w1/devices. You can simply cat this new file and find the latest temperature reading.

The Raspberry Pi posts the temperature readings to a CouchDB server and a small single page app presents the historical readings with graphs for the current day, week and month.

The original code is available on GitHub at https://github.com/johannoren/WeatherStation.
The adaptations for multiple sensors can be found on branch https://github.com/johannoren/WeatherStation/tree/multiplesensors

Become a better programmer with programming challenges

2014-04-28T20:26:00.000+02:00

When I went to university me and some friends spent time on practising algorithm implementations for the national programming contests that were held each year. The concept was (and still is) to solve about ten problems in a couple of hours time using a programming language of choice. The source code is submitted to an automatic judge that compiles the code and feeds the executable with test data and verifies that the program delivers the correct output expected for the input.

After being out in real work I have noticed that I have had good use of these earlier exercises. One of the most important lessons is to know by heart the complexity of different algorithms and when to use a simple brute force method and when a more advanced algorithm must be implemented.

I noticed that the old Online Judge system that we practised on in the early 2000s still is online and has grown to a large site with lots of users solving programming challenges. If you want to recapitulate your algorithm skills this is a fun and very hands on way to do small exercises and get feedback in realtime. Also there is an addictive gamification effect of trying to solve more problems.

Browse the catalogue of problems and find some challenge that feels interesting. The problems are color coded so you know which one you already solved and some stats that gives a hint on how difficult the problems have been for other users to solve.

Once you have submitted your code you get instant feedback on how your code has performed on the judges test cases.

At the moment you may submit solutions in C/C++/C++11 and Java. Create an account at http://uva.onlinejudge.org/. Once you've done that you can follow your progress and your statistics in different ways. Here's my stats http://uhunt.felix-halim.net/id/426271.

I've recently done a couple of problems per night just for the fun of it. It feels exciting to program on a hard problem using just 20 lines of code instead of coding 1000 lines of boiler plate which I guess many of us do at our every day works.

Without trying to indicate that I'm an expert on complex algorithms, here are some things I think are valuable when getting serious about algorithm design and solving harder programming challenges.

Complexity theory

If you didn't take a course on complexity theory or don't remember the basics I think this is a must to have in the toolbox for every programmer. This implies knowing which problems are inherently hard. By hard we dont mean hard to implement a solution for, but hard in the sense that the resources (CPU time or memory) scales bad with larger and larger sets of input for the problem.

The standard way of measuring the complexity of an algorithm is to resolve the algorithms Ordo or Big-O function. The formal definition is that this Big-O function O() satifies

f(x) = O(g(x)) when x ➝ ∞ if and only if |f(x)| < M |g(x)| for all x > x₀

In English this means that there is a constant M which when multiplied with g(x) always will be larger (make an upper bound) on the function f(x) which is the time or memory usage of the algorithm for the input size x of the problem when x is sufficiently large (larger than some certain x₀). These values always considers the worst case input for the algorithm. This might need an example.

Consider the problem of sorting an array of n values. The basic bubble sort algorithm is probably the easiest algorithm to implement and uses two nested for loops to swap the values into a sorted order. Since the arrays have the size n, which is the size of the input of the problem, the Big-O function for this will be O(n²). Why? The number of operations needed to sort the array will be proportional to two nested sweeps over the array of size n, which makes M×n×n operations. So g(n) = n². Here the actual swap operation is the constant M number of machine operations.

Another problem, consider finding a value in a sorted tree (or in a sorted array for that matter via binary search). In this algorithm, each inspection of a node in the tree is proportional to one operation. Each inspection will cut the size of the tree in half so only one of the halfs will be needed to be examined in the next operation. This means that the number of operations needed to find the value will be less than the number of values in the tree. So we have an algorithm that is faster than the linear g(n) = n. In fact this class of problems are solved in logarithmic time proportional to the size of the input, or O(log(n)).

So going back to programming challenges, by knowing a lot of algorithms you might figure out which one will suit the particular problem. First of all, always find the bounds of the input data for your problem. What are the most extreme inputs we might expect to handle? Then, assuming the worst case scenario, what is the most easily implemented algorithm we can get away with within the requirements on time and space utilization?

For example, to sort an array of at most 10 000 000 values, bubble sort would require something proportional to n×n = 100 000 000 000 000 operations. Even with multi cores, this will not be fast. So by knowing that for example the heap sort algorithm is O(n log n) we know that this algorithm will sort the array proportional to 10 000 000 × 7 = 70 000 000. Definitively something that can be accomplished within a fraction of a second.

But assume that we know that the values in the array are all in the range of 1 to 1000 000. This extra clue can give us the hint to consider bucket sort which has larger memory requirements than heap sort but can perform the sort in linear time proportional to the input size, O(n).

Know your algorithms

The above example of sorting shows that it is essential to know a lot of algorithms. By "knowing", you don't need to know the implementation of them. You can always search the web for actual implementations, pseudo code or even find them implemented in some library. The important part is to know that they exist and for what particular problems they are useful and what requirements they put on input data, time and memory usage so you can make a decision on whether they are applicable for your problem.

There are specific algorithms targeting very specific problems such as Dijkstra's algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs. This is a rather common problem within the class of graph problems so it can be handy to know by heart, but maybe more interesting is to analyze what makes Dijkstra's algorithm successful. It is a typical example of Dynamic Programming (DP) which is a general approach of solving many hard problems by breaking them into smaller and simpler subproblems and solving the larger problem by combining solutions of smaller problems. Other general ideas that can be useful in many different contexts is divide and conquer algorithms, greedy algorithms and backtracking.

When considering the programming challenges in the Online Judge system, often the hard and most interesting part is to figure out what class the problem belongs to. Can the problem description be translated into a graph problem for example? In that case which graph algorithm will solve the problem?

Without any intention to be complete, here's some algorithms that can be valueable to know about and put in your toolbox together with some suggestions on problems to apply them on.

Sorting

When considering which algorithm to choose, think about what requirements you have and the expected input. For example, some algorithms are stable, where stable means that if two objects are considered equal (depending on the comparison function used when sorting), the relative order of them will be preserved. For example the quick sort algorithm is much more complicated to implement if it must behave in a stable manner. Furthermore, some algorithms have very nice average Big-O requirements but may deteriorate to O(n²) if the values to sort already are sorted. Ordo funtioncs are always given for worst case scenarios.

Merge sort is a popular O(n log n) sorting algorithm implemented in Perls sorting library. Timsort, O(n log n) is based on merge sort but can run in linear time if the input is already sorted. Timsort is deployed in JDK 7 and Python libraries. Heap sort has even less memory requirements than merge sort and runs in the same time asymptotically.

If you have the possibility to sort in parallel there are implementations of for example merge sort than can give even better performance.

UVA problems that could be relevant to practise on: 299 - Train Swapping, 10252 - Common Permutation.

Graph problems

The most important thing to consider when attacking graph problems is how to traverse the graph. Depth First Search (DFS) is easily implemented with recursion but can have problems with non termination if the graph's size is similar to the internet and if recursion is made in languages like Java or C, the stack will overflow in a certain amount of iterations (stackframes). Other languages like Scala can avoid new stack frames if the code is written tail recursively which internally is unwrapped as a while loop. In older languages, you must know how to convert your recursive solution to an imperative loop solution when search depths become substantial.

Adaptations to DFS can be for example iterative deepening, popular in implementations of game trees in for example Chess engines. This means that the search is performed to deeper and deeper depths in iterations making it possible to abort if for example a certain time constraint is broken. Useful when the branching factor of the searched tree is large. Alpha-beta pruning is a clever way to reduce the search space by limiting the branching factors in DFS in game trees.

Typical uses of DFS are finding a solution out of a maze, planarity testing, finding connected components of a graph, deciding biconnectivity of a graph and topological sorting of a directed graph.

Breadth First Search (BFS) is based on a queue data structure and is easily implemented without recursion. Some typical uses of BFS is to find all nodes within a connected component, finding the shortest path between two nodes of an unweighted graph and to find the maximum flow in a flow network.

Some practise problems on general graph and tree traversals are 167 - The Sultan's Successors, 115 - Climbing Trees, 297 - Quadtrees.

Combining DFS or BFS with ideas like greedy selection and DP and you have some of the most famous algorithms below.

Dijsktra's algorithm - Find the shortest path from a specific node to all other nodes in a graph with non-negative edge costs. The original algorithm from 1959 runs in O(|V|²) where |V| is the number of vertices in the graph. An improvement uses a Fibonacci heap as priority queue which runs in O(|E| + |V| log |V|) where |E| is the number of edges. However, implementing a Fibonacci heap is work on its own so only use it if necessary.

Bellman–Ford algorithm - Similar to Dijkstra's algorithm, Bellman-Ford finds shortests paths in a graph but can also handle negative edge weights (as long as there are no negative cycles since that means there is no shortest path).

Prim's and Kruskal's algorithms can be used to find a minimum spanning tree of a graph. That means, a tree that includes all vertices that are connected within the graph. These algorithms have similar time complexity as Dijkstra since the O(|V|²) can be improved to O(|E| + |V| log |V|) with a Fibonacci heap. Prim's algorithm is a good example of a greedy algorithm.

Floyd-Warshall's algorithm finds all shortest paths costs between all nodes in a graph with positive or negative edge weights (no negative cycles though). The simplest implementation can be extended to also keep a backtracking table so it is possible to not only find the path costs but also reconstruct the actual shortest path between all nodes. FW is a typical example of Dynamic Programming. FW runs in O(|V|³).
A good practice problem is 104 - Arbitrage.

Sequence and string problems

There are a lot of problems involving finding longest sequences or subsequences in different lists. These lists can be arrays of numbers or characters written as strings. Often a combination of sorting and some specific algorithm is best medicine.

The Longest Increasing Subsequence algorithm (LIS) will in the list 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 figure out that the longest sequence in ascending order must be 0, 2, 6, 9, 13, 15. Note there can of course be other equally long sequences. LIS runs in O(n log n) since its implementation is based on binary search.

The Longest common substring problem means to find out that "XYZ" is the longest common substring in the three strings "XYXYZ", "YXYZX" and "XYZYX". There are two types of algorithms for this, one builds a suffix tree and one is based on dynamic programming.

The problem of finding the minimum number of edit operations needed to turn one string into another is addressed by the String-to-string correction problem. A side effect of the algorithm for this is that by storing the deltas you can for example store many very large quite similar strings by only keeping one copy of the first string and then the small deltas of the edits needed to turn it into the other strings. An application would be to store for example DNA sequences or similar in this way. The Levenshtein distance is the number of changes needed to turn a string into another and can solve the String-to-string problem via a DP approach.

Practise problems: 111 - History Grading.

Number theory

Math problems can sometimes feel academical but there are important real life applications considering for example prime numbers and cryptography or how many ways something can be done using combinatorics.

Problems concerning prime numbers are common. To verify whether a certain number is prime (primality testing), different algorithms can be used. For moderate bounds on input, simply test for divisibility up to √n. Once n is large you might need faster ways to test for primality. One of the fastest algorithms which runs in polynomial time is the AKS test which can be implemented in O(log(n)⁶).

A tougher problem is to factor a number into its prime factors. The most difficult numbers are semiprimes which are the product of two primes. No polynomial algorithm is known to do this which is the base of RSA cryptography. If you know more about the properties of the composite number there can be shortcuts to factor the number. Numbers on the form r^e±s can be efficiently factored using the Special Number Field Sieve algorithm if r and s are relatively small. From this the General Number Field Sieve is derived which is the most efficient classical algorithm known for factoring integers > 100 digits.

There are problems where you need to find the greatest common divisor (gcd) of two numbers. This number can be found using the Euclidean algorithm which can be implemented as below where % is Javas syntax for modulus.

int gcd(int a, int b) {
   if (b != 0) {
      return gcd(b, a % b);
   }
   return Math.abs(a);
}

Once we have gcd, we can easily calculate the least common multiple (lcm) of two numbers as

Another problem that you will find in some of the UVA challenges includes raising large powers. If you are to calculate a^b and b is large the naive solution would include b number of multiplications of a. A much faster way is to use repeated squaring which means that you square the results to make the number of multiplications logarithmic in relation to b. Some pseudo code for this would be

/**
 * Calculates n to the p power, where 
 * p is a positive number.
 */
LargeInt power(LargeInt n, LargeInt p) {
   if (p == 0) return 1
   if (p == 1) return n
   if (isOdd(p)) {
      return n * power( n * n, (p - 1) / 2 )
   } else {
      return power( n * n, p / 2 )
   }
}

There are some problems on calculating Fibonacci sequences. If you wind up with Time Limit Exceeded (TLE) from the judge on these and you think you have made a really fast algorithm avoiding recursion and no double calculations, remember that factorials can be expressed in a closed form as well where F(n) is the n'th number in the sequence.

Problems: 136 - Ugly Numbers, 160 - Factors and Factorials, 583 - Prime Factors,

Combinatorics

Variations on combinatorics is a common theme. Assume you have a box of n items, in how many unique ways can you pick k items? 0 <= k <= n.
If you remember your discreet mathematics this is solved using binomial coefficients (Pascal's triangle). The academic version is often described as a divisions of factorials.

This is not a practical implementations however. The formula can be rewritten as a product of terms better suited for an engineering implemention.

Example problems: 10219 - Find the ways !, 11401 - Triangle Counting

Probability theory

Knowing some basic probability theory is not only good for programming challenges. Besides the basic definitions and axioms (Kolgomorov) there are lots of interesting topics such as stochastic processes and variables, probability distributions, Bayes theorem and more.

Practise problem: 10491 - Cows and Cars

Dynamic Programming

Dynamic programming (DP) is a methodology for attacking complex problems by splitting the problem into simpler subproblems which solutions can be reused to solve the original problem. The problem must have the property of overlapping subproblems. This means that the subproblems are occuring several times in the problem and can be reused in the DP approach. A simple example of this would be a function f(n) to calculate Fibonacci numbers. Since f(n) = f(n-1) + f(n-2), a DP approach would store each f(x) to reuse previously calculated valued. The stored values are called "memo-ized".

In general, DP is a technique to speed up solutions of problems where you make brute force searches and cache intermediate results.

Let's examine a more complex problem where DP actually makes great difference.

"Suppose you have x dollars and want to figure out in how many unique ways you get change for this in the coins 1c, 5c, 10c, 25c and 50c."

The brute force approach would be to nest five for loops and iterate over the five different coins and count the number of valid combinations. A very simple algorithm but it would not scale well with larger amounts of dollars or if we had more types of coins increasing the number of nested for loops.

Let's start thinking from a dynamic programming perspective. Can we make the problem simpler? Let's assume we have solved the same problem (in some at this time unknown way) for 4 currencies. So we know how many combinations you could get x dollars in 1c, 5c, 10c and 25c. Could this help us? Yes, then we could deduce that the total number of combinations would be the sum of 0, 1, 2 ... n number of 50c coins where n is the maximal number of 50c coins you could get out of x dollars. Each such number of combinations could be calculated by the already known function since it handles the other four coins.

Naturally, we can use the same approach to solve the problem for 4, 3 and 2 coins. The case of 1 coin is so simple that we can implement it without relying on any other assumed function.

Here's a recursive implementation of this idea.

 private int combinations(final int[] change, final int maxCoins,
  final int amount) {

   /*
    * Base case 1. If amount = 0, there is one combination -> no change.
    */
   if (amount == 0) {
    return 1;
   }

   /*
    * Base case 2. If negative amount, no solutions
    */
   if (amount < 0) {
    return 0;
   }

   /*
    * Base case 3. No change to work with -> no solutions
    */
   if (maxCoins <= 0) {
    return 0;
   }

   /*
    * Here goes the recursion, sum all combinations using one coin less
    * from the list of coins plus the number of combinations if we remove
    * one of the largest coins from the total amount.
    */
   final int c = combinations(change, maxCoins - 1, amount) + combinations(change, maxCoins, amount - change[maxCoins - 1]);

   return c;
  }

Call it with the number of available coins and the number of coins in the array to use together with the total amount of dollars (times 100 to get int values for cents).

int combs = combinations([1, 5, 10, 25, 50], 5, 500000);

This will work, but it will not be efficient. For each invocation that does not end in a base case, two recursive calls will be performed and the same subproblem will be recalculated over and over again.

The good thing is that we have divided the problem into specific overlapping subproblems. Now we can add the idea of dynamic programming. Add a cache that stores previous calculations as a base case to make the recursive solution only calculate subproblems that not have been encountered before.

    private int combinations(final int[] change, final int maxCoins,
            final int amount, final int lookupTable[][]) {

        /*
         * Base case 1. If amount = 0, there is one combination -> no change.
         */
        if (amount == 0) {
            return 1;
        }

        /*
         * Base case 2. If negative amount, no solutions
         */
        if (amount < 0) {
            return 0;
        }

        /*
         * Base case 3. No change to work with -> no solutions
         */
        if (maxCoins <= 0) {
            return 0;
        }

        /*
         * Base case 4. This is already calculated, so DP finds result in cache
         */
        if (lookupTable[maxCoins][amount] != -1) {
            return lookupTable[maxCoins][amount];
        }

        /*
         * Here goes the recursion, sum all combinations using one coin less
         * from the list of coins plus the number of combinations if we remove
         * one of the largest coins from the total amount.
         */
        final int c = combinations(change, maxCoins - 1, amount,
                lookupTable)
                + combinations(change, maxCoins, amount
                        - change[maxCoins - 1], lookupTable);

        lookupTable[maxCoins][amount] = c;

        return c;
    }

This will perform efficiently and is it is easy to understand the logic. Unfortunately a problem with recursive solutions in imperative languages like Java is that deep recursions will run out of stack space. So to make this solution even more generic we should rewrite it using loops instead of in the more aestethic functional style.

    private int[][] combinations(final int[] change, final int maxCoins,
            final int amount) {

        final int[][] lookupTable = new int[amount + 1][maxCoins + 1];

        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j <= maxCoins; j++) {
                if (i == 0) {
                    lookupTable[i][j] = 1;
                } else if (j == 0) {
                    lookupTable[i][j] = 0;
                } else if (change[j - 1] > i) {
                    lookupTable[i][j] = lookupTable[i][j - 1];
                } else {
                    lookupTable[i][j] = lookupTable[i - change[j - 1]][j]
                            + lookupTable[i][j - 1];
                }
            }
        }

        return lookupTable;
    }

This function retrieves the all the memoized combinations and we find the solution to our problem as

        final int[] change = { 1, 5, 10, 25, 50 };
        final int[][] combs = combinations(change, change.length, maxDollars);
        final int   answer = combs[amountToChange][5];

In the UVA problem set you will often need to think from a DP perspective to create solutions that are fast enough for the input data and the time constraints.

Some good problems to practise on: 103 - Stacking Boxes, 108 - Maximum Sum

The particular coin change problem described above is available in several versions on UVA. Have a try at problem 147 - Dollars.

Divide and Conquer

Divide and conquer algorithms are based on multi branched recursion. It breaks down a problem into several sub problems and recurse on them. These can thereby be divided into subproblems until they are small enough to be easily solved. Then the solutions are used to generate the answer to the complex problem. Quicksort, merge sort, discrete Fourier transform (FFT), top down parsers used in syntactic analysis are D&C algorithms.

Another example that can be useful to know in the UVA problem challenges is that there is an algorithm called Karatsuba which multiplies two large integers (with thousand or millions of digits) fast. It runs in O(3n^log₂3) which is notably faster than the O(n²) method we learned in school. Karatsuba is a D&C algorithm. Binary search could be called a simple form of D&C.

Suitable practise problems: 10341 - Solve It

Greedy algorithms

A greedy algorithm makes local optimal choices at each stage during the algorithm in hope of producing a global optimum. Many problems will fail to do so with a greedy approach since the complete search space is not visited. But for certain problems greedy selection works well and can therefore create fast solutions. In other cases where the optimal solution is not possible to calculate in an efficient way, a greedy solution might come up with a decent approximation or bounded result.

Examples of greedy algorithms are the construction of a Huffman tree during Huffman coding or Kruskal's algorithm for finding a minimum spanning tree of a graph.

Practise problem: 11389 - The Bus Driver Problem

Backtracking

Backtracking is a technique that finds one or all solutions to a problem by trying different candidates and abandon those branches that breaks the constraints of the problem which means that the current path cannot lead to a valid solution of the problem.

An example where backtracking would be suitable is a solver for a Sudoku puzzle. By doing a depth first search and inserting new numbers in empty positions and for each insertion checking whether the new number breaks any constraints of the rules of Sudoku, the board can be iteratively filled with valid numbers. As soon as a number violates the rules and all numbers have been tried in the current position, the algorithm must backtrack to the previous position and try another number.

Examples where backtracking is suitable are puzzles and combinatorial optimization problems such as the knapsack problem.

A good practise problem is the classic Eight Queens puzzle where you should position eight queens on a chessboard without any queen threatening another. Here's a few modifications on that theme on the UVA site 11085 - Back to the 8-Queens, 167 - The Sultan's Successors.

UVA Online Judge

The online judge system at http://uva.onlinejudge.org/ accepts code in C/C++/C++11/Java. Some hints for beginners might be to start with an easy problem to get to know the judge. Good choices might be problem 10018 - Reverse and Add or 11172 - Relational Operator.

Important, read the input and output constraints carefully. For example, if the input consists of integers and are between 0 and 4,294,967,295 remember that a signed 32 bit integer will overflow so you should use a 64-bit integer or an unsigned int depending on the language you code in.

Output format matters, so be careful with trailing spaces and linefeeds. Sometimes you simply must try with or without an ending newline since the problem description won't tell which one is correct unfortunately.

Create a good template which you can copy when starting on a new problem. If you code in Java you will probably have everything you need in the standard library such as BigIntegers and much more. If you code in C/C++ it can be good to add some routines for handling arbitrary large numbers to your template.

If you get stuck on a problem try to create test cases for all the border cases allowed in the input. Try the worst possible input and also the smallest possible input to see that you get reasonable output.

Many basic problems can be solved with simple ad hoc brute force solutions but the more interesting problems with greater time complexities will perform very badly with naive solutions. The problems are often devised so that brute force solutions will not be able to perform within the time limits. However, once you've created a fancy solution based on DP or some other approach it is not always self evident that the algorithm is correct. In those cases it can still be valuable to run the outputs from your algorithm against a quickly coded brute force solution to verify that they produce the same output.

If you still is stuck and can't figure out why the online judge gives your solution "Wrong Answer" you can check the forums where many helpful programmers gives hints or test data to test your code against.

Good luck!

Edit 2014-05-01:
I got feedback on whether I could recommend any books for those interested to dig deeper. I got two books which I bought ten years ago which I still think should be relevant.

Programming Challenges: The Programming Contest Training Manual by Skiena and Revilla is exactly what it sounds like. A walktrough of different types of programming challenges and techniques for solving them.

Algorithms by Sedgewick and Wayne is more a general CS book and a good read.

New Eclipse project connected to Git repository

2014-03-17T10:32:00.003+01:00

You have a new Eclipse project to work on and you want to version control it on a Git repository on another machine. Here's how you do it.

1. On the server you wish to have your Git repository remotely stored, setup an empty repository. In our examples here the repository and project will be called UVaOnline

johan@htpc ~/gitrepos $ pwd

/home/johan/gitrepos

johan@htpc ~/gitrepos $ mkdir UVaOnline.git

johan@htpc ~/gitrepos $ cd UVaOnline.git/

johan@htpc ~/gitrepos/UVaOnline.git $ git --bare init --shared=all

2. Add a file to this empty project if you wish to make sure there is something to check out from Eclipse.

johan@htpc ~/gitrepos $ cd /tmp

johan@htpc /tmp $ git clone /home/johan/gitrepos/UVaOnline.git/

johan@htpc /tmp $ cd UVaOnline/

johan@htpc /tmp $ touch FOO

johan@htpc /tmp $ git add FOO

johan@htpc /tmp $ git commit

johan@htpc /tmp $ git push origin master

3. In Eclipse, add the Git Repository Exploring perspective via the menu Window -> Open Perspective.

4. Click the "Clone a Git repository and add the clone to this view" icon in the perspective.

5. In the first step of this wizard, enter the connection details for the Git repository. In my case I use my SSH user to log on the server.

6. If your project was emtpy, you only have the master branch to work with. Click next.

7. Choose where you wish to have your local Git repository on the machine Eclipse is installed on. I selected the "Import all existing projects after clone finishes".

8. Now a new repository should be available in the Git repository Explorer.

9. Try to fetch the repository if you want to see the refs configurred.

10. You see the connection URL again, next.

11. Here you could add or delete refs pointers. For our purposes, this looks alright.

12. To import the project into the Java/Java EE perspectives, click the "Import Projects" option in the menu.

13. Since this project is a bare bones project with no .project file with Java facets, we must select to import the project as a "Import as general project".

14. Probably the default name is good enough.

15. Now you could start adding file to your project. I made my project a Maven project here and added some source code. Once you're ready to commit to the remote repository, right-click and choose Team -> Synchronise Workspace.

16. In the next view, select the files you wish to commit and add them to Git index first.

17. Then right click again and commit.

18. If you do not click "Commit and push" the files are only added to your local git repository on the same machine. That can be good if you want to pile up a bunch of local commits before pushing to the remote repository. When you want to push all local commits, in the Java perspective right click and go via Remote to Push.

19. If it is the first time, you might need to add a spec for this. If you work on master which you do if you have followed the tutorial, simple add "refs/heads/master" as source and destination ref and click "Add spec".

20. New spec added.

21. Once finished, the commits you had locally are pushed to the remote repo.

Thats it. I have some more stuff on working with Git in Eclipse in this blogpost about Github cloning.

For more advanced Git usage, you might need the console. That's no problem, simply make sure to refresh the Eclipse project after working in the console since Eclipse must refresh the .git folder etcetera. See this Git cheat sheat for my favourites.

Porthello Legends - Android Reversi Port

2014-02-18T17:25:00.003+01:00

I wrote a clone of the game Reversi/Othello for Android three years ago and it actually made some progress on Google Play (Market as it was called then). It was downloaded nearly 1000 times and a lot of players seems to have enjoyed it because I could see in the highscore lists and the Analytics statistics that they spent quite some time on trying to beat the AI to gain access to even harder levels.

Unfortunately, the name Othello Legends was a bad choice since it was trademarked. That meant that after 6 months the game was suspended from Google Play. Since I put quite a lot of effort into the game it is a shame that it disappeared and I have now done a refactoring to the new name Porthello Legends :-).

My Android tablet died last summer and all I got to test with is an pretty old HTC Desire which the game seems to work fine on. It would be interesting to get feedback on how the game performs on newer phones/tablets as well.

Check out the game at Google Play, search for "Porthello Legends" or go to https://play.google.com/store/apps/details?id=se.noren.android.porthello&hl=en.

The old blogpost on the inital release can be found here http://macgyverdev.blogspot.se/2011/12/othello-legends-10-in-android-market.html.

Apache web server as reverse proxy and virtual host for Tomcat 7

2014-02-11T10:04:00.001+01:00

I'm running a couple of sites on a Linux server on my local network. I only have one public ip address but I want to be able to host multiple sites on my servers. So this can be done by using a reverse proxy in front of the application servers which delegates traffic depending on which host name the end user was trying to request.

I've implemented this by using the reverse proxy feature with virtual hosts in the Apache HTTP web server.
The result this exercise is trying to achieve is that external traffic from internet requesting pages from the site www.all-about-units.com which is DNS mapped to my public ip address will be routed to the Apache web server on the local network via a port forwarding rule in the router on the local network. The Apache web server will look into its rules for virtual hosts and see that the user requested the domain www.all-about-units.com and therefore delegate the traffic to a separate Apache Tomcat 7 servlet container running on the local network to serve the request. The traffic is then forwarded back through the web server to the end user.

Setup Apache HTTP server as reverse proxy

First of all the Apache HTTP web server must be installed. I had mine installed since long ago but if I remember correctly there's not much than doing this is you have a Debian/Ubuntu/Mint like Linux server

sudo apt-get install apache2

Now, to enable the reverse proxy feature of the Apache server

/ $ sudo a2enmod proxy_http

Next, we must create a configuration for our new site as a virtual host. Go to the directory of available sites

/etc/apache2/conf.d $ cd /etc/apache2/sites-available/

Copy the default configuration to a setup for your site

/etc/apache2/sites-available $ sudo cp default all-about-units

Lets edit the configuration file. The first line tells the Apache server to listen on port 80, the standard HTTP port. Next the names of the virtual host are given. So traffic requesting another domain name or the ip address directly will not be handled by this virtual host configuration.

Next look att the ProxyPass and ProxyPassReverse, these tell Apache where to forward the request that has matched this virtual host rule. In this case to the Tomcat server on the same machine (127.0.0.1 is the loopback address of localhost) but on port 8080. The slash before the address means that all requests should be forwarded to the Tomcat server. If for example you had ProxyPass /foo/bar/ http://127.0.0.1:8080/ then the request www.all-about-units.com/foo/bar/page.html would be redirected to 127.0.0.1:8080/page.html

/etc/apache2/sites-available $ sudo vim all-about-units



<VirtualHost *:80>

  ServerName all-about-units.com

  ServerAlias www.all-about-units.com




  ProxyRequests Off

  ProxyPreserveHost On




  <Proxy *>

    Order deny,allow

    Allow from all

  </Proxy>




  ProxyPass / http://127.0.0.1:8080/

  ProxyPassReverse / http://127.0.0.1:8080/

</VirtualHost>

Enable and disable the site

To tell the Apache HTTP web server to enable this configuration, run the a2ensite command on the name of the new configuration

/etc/apache2/sites-available $ sudo a2ensite all-about-units


Enabling site all-about-units.

To activate the new configuration, you need to run:

  service apache2 reload

Reload Apache



/etc/apache2/sites-available $ sudo service apache2 reload

 * Reloading web server config

I had some issues so I restarted Apache the hard way also and then it works.

/etc/apache2/sites-available $  sudo /etc/init.d/apache2 restart



 * Restarting web server apache2                                                          apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.1.1 for ServerName

 ... waiting apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.1.1 for ServerName

That's it!

Verify in the logs of the application server that the request are directed correct and your home.
Next step might be to enable the mod cache feature of Apache to let the web server handle caching of all static material served by the application server like css, images and javascript. More on that in another post.

If you for some reason want to take the site of the web for some time you can instead of stopping the application server disable the site in the web server virtual host forwarding by using the command

sudo a2dissite all-about-units

How to make Jenkins install the packaged war in a Tomcat 7

2014-02-04T22:17:00.002+01:00

This is a sequel to http://macgyverdev.blogspot.se/2014/01/setup-jenkins-project-from-git.html where I set up Jenkins to build my latest project. The next step is to install the war-file built by Jenkins on my Tomcat 7 server.

First of all we must make sure Tomcat accepts installations by scripting instead of the human html GUI version. In the tomcat-users.xml file, located in something similar to this:

/var/lib/tomcat7/conf/tomcat-users.xml

Make sure that the admin user, whatever his name is, has the role manager-script. Here's the important part of my file:

<tomcat-users>

</tomcat-users>

Now, in Jenkins you must install the Deploy Plugin. You find it in the plugins section.

Your Jenkins job is here assumed to be configured to package a war file. You can verify this by inspecting that a build generates a war file like this:

~/.jenkins/jobs/UnitConversion/workspace/target/Unitconversion.war

For this Jenkins job, go to the settings page and add a new post-build action. Choose the "Deploy war/ear to a container".

In this view make sure the path to the packaged war is relative to the workspace area of the job. Most probably it will be "target/yourapp.war".

Now, rebuild your job and when inspecting the console logs you should see that the war/ear is installed!

Deploying /home/johan/.jenkins/jobs/UnitConversion/workspace/target/Unitconversion.war to container Tomcat 7.x Remote
  Redeploying [/home/johan/.jenkins/jobs/UnitConversion/workspace/target/Unitconversion.war]
  Undeploying [/home/johan/.jenkins/jobs/UnitConversion/workspace/target/Unitconversion.war]
  Deploying [/home/johan/.jenkins/jobs/UnitConversion/workspace/target/Unitconversion.war]
Finished: SUCCESS

This way it takes two clicks from editing the code in Eclipse to update the site All About Units in production, first commit and push to Git, second start the Jenkins job.

One note, if you have deployed your application with context root "/" in Tomcat as I have done, see http://macgyverdev.blogspot.se/2014/02/how-to-change-context-root-to-in-tomcat.html, you can not have Context path = "/" in the configuration above. Instead, keep multiple context roots in Tomcat, and as in my example add the context root with a longer name, otherwise the deploy plugin cannot undeploy the ROOT web application. If you according to my blog post on it has manipulated the server.xml a reinstallation of "/webappname" will also reinstall the ROOT application since they point to the same directory on disk.

How to change context root to / in Tomcat 7

2014-02-04T20:55:00.000+01:00

Here's my problem, I have a new project going which will be deployed as http://www.all-about-units.com/en. It's a site for general facts and info about units. It's a Java web application running on a Tomcat 7 servlet container. It is automatically deployed to the context root "Unitconversion" since that is the name of the WAR-file when it is uploaded via the admin ui.
That means I will access it as

http://myserver:port/Unitconversion

I want it to be deployed as context root "/" so that the URL becomes this in production

http://myserver:port/

My Tomcat 7 is running on a Linux Mint server but I guess these instructions are the same regardless of operating system. Here's how I managed to get it working.

First I uploaded my new web application in the Tomcat manager admin GUI. We got something like this now.

Now, if you inspect the file system you should have your app deployed at /var/lib/tomcat7/webapps.

johan@johanhtpc /var/lib/tomcat7/webapps $ ll
total 31040
drwxrwxr-x 5 tomcat7 tomcat7 4096 feb 4 20:22 .
drwxr-xr-x 6 root root 4096 dec 18 19:25 ..
drwxr-xr-x 3 root root 4096 dec 18 19:25 ROOT
drwxr-xr-x 10 tomcat7 tomcat7 4096 feb 4 20:22 Unitconversion
-rw-r--r-- 1 tomcat7 tomcat7 23617897 feb 4 20:22 Unitconversion.war
drwxr-xr-x 8 tomcat7 tomcat7 4096 dec 28 12:44 WeatherStationServer
-rw-r--r-- 1 tomcat7 tomcat7 8140647 dec 28 12:44 WeatherStationServer.war

The hacky way now would be to change the ROOT application with my new code, a simple overwrite with my web app. But that doesn't smell so good...

So what you do is that you edit

/var/lib/tomcat7/conf/server.xml

and add these lines inside the <Host> element. Change "Unitconversion" to your application name.

</Context>

</Context>

This will make the default root application appear under context root "/ROOT".

Restart Tomcat to make changes take place.

sudo /etc/init.d/tomcat7 restart

And now the app is accessible at "/" and at the old context root "Unitconversion" as well. This is also seen in the GUI if you refresh the manager.

Java 8 in Eclipse

2014-01-28T09:13:00.000+01:00

Have you tried out Java 8 yet? The official release is not until March 2014 but there have been a set of release candidates to play with. It is actually very easy to get up and running.

Download a JDK 8 snapshot from https://jdk8.java.net/ and install it.
Install a version of Eclipse that can handle Java 8 syntax. I downloaded Eclipse Luna 4.4 from http://downloads.efxclipse.org/eclipse-java8/2013-05-19/.

To get started, create a new project in Eclipse and make sure you have chosen the Java 8 JRE.

Here's a class that uses a lambda expression to instantiate the functional interface PowerCalculator. A functional interface is an interface with only one abstract method.

public class TestClass {

    interface PowerCalculator {
        int pow(int n, int exponent);
    }

    public static void main(final String[] args) {
        final PowerCalculator calc = (int n, final int exponent) -> {
            return (int) Math.pow(n, exponent);
        };
        
        int product = calc.pow(3, 4);
        System.out.println(product);
    }
}

This outputs the expected "81".

That was maybe not very cool, but when looking into the more functional style of programming you can do with lambda expressions, this is the most interesting Java upgrade since Java 5 in my opinion.
I wrote an article in 2012 on FP in Java http://macgyverdev.blogspot.se/2012/10/functional-programming-in-java.html and took a quick look now again to see whether the original spec still is valid.

Here is a few examples I tried on the Collections framework. There has been changes since the 2012 draft. For example is the stream() interface added, previously you could do a filter() directly on the collection. The stream interface allows for parallel execution and

public class TestClass {

    public static void main(final String[] args) {
     List<Animal> animals = Arrays.asList(new Animal(10), new Animal(20), new Animal(30), new Animal(40));
     
     // Each animal eats another calorie
     animals.forEach(a -> a.eat(1));
     
     // Print animal
     animals.forEach(a -> a.print());
     
     // Print only the animals which have more than 30 calories
     animals.stream()
            .filter(a -> a.nutrition() > 30)
            .forEach(a -> a.print());
     
     // Calculate total sum of all animals calories
     int sum = animals.stream()
                      .mapToInt(a -> a.nutrition())
                      .sum();
    }
}

class Animal {
 private int calories = 0;
 
 public Animal(int calories) {
  this.calories = calories;
 }
 
 public void eat(int calories) {
  this.calories += calories;
 } 

 public void print() {
  System.out.println("Calories: " + calories);
 } 

 public int nutrition() {
  return calories;
 }
}

The Eclipse support in Luna 4.4 is pretty good. But when using the command completition it is not obvious what the different lamda expression consumers expect. I guess once you have played around with it some more you get accustomed to the Predicate and Consumer APIs.

Setup Jenkins project from Git repository with Findbugs, Cobertura and Checkstyle

2014-01-24T19:33:00.000+01:00

I created a Jenkins setup for my current Java hobby project (a site on physical units intended to make ads money, check it out at http://www.all-about-units.com) yesterday and noticed that my old note on how to setup Jenkins (then it was written for Hudson) is a bit out of date. The Jenkins configuration menues for generating Findbugs static analysis, Cobertura code coverage and Checkstyle format control were completely new. In addition to that, I've migrated to Git since then so there are a few steps also involved in getting Git running as code repository within Jenkins.

Here's a workflow for setting up Jenkins with these features.

Install Jenkins and plugins

First of all, if you haven't installed Jenkins the easiest way is to download the war archive from http://jenkins-ci.org/. This article is based on Jenkins version 1.532.1. You can install in in a server container like Tomcat or Jetty, but the easiest way to get started is to run it from the command line like

java -jar jenkins.war

I created a small bash script which also changes the port since I have another server using the default 8080 port.

#!/bin/sh

nohup java -jar jenkins.war --httpPort=8081

So now you can access Jenkins via http://localhost:8081 or similar.

Now we must install some plugins which are not part of the core distribution. Go to the settings of Jenkins and find the Plugins section.

Here you should at least find the following plugs and install them

Creating Jenkins job

Create a new Jenkins job. My project handles its dependencies via Maven 3 which suits Jenkins very well. Choose the Maven 2/3 option.

In the next step, choose Git as SCM. If you have your Git repository on the same server as Jenkins you can simply add the file path to the repository. Otherwise you setup the security credentials here as well. Also, choose if you want to build master or some other branch.

We haven't talked about the pom.xml for the project yet, but it will be configured to use some Maven goals. So in the Maven goals section, add goals for test package site.

Under Build settings, check the boxes for Publish Checkstyle analysis results, Publish FindBugs analysis results and Publish duplicate code analysis results.

In the Post-build Actions add a step for Cobertura reporting.

Maven will generate the Cobertura report to the Jenkins workspace under path /target/site/cobertura/coverage.xml so add this in the configuration of the action.

Now you should have a Jenkins job setup ready for building.

Before building we must make sure the pom.xml of the project has the correct plugins and reports configured.

Maven pom.xml configuration

After all the dependency specifications in the pom.xml add something similar to this. In this setup Cobertura is configured in the package phase and that's why we added that Maven goal above. If you hadn't added this in the pom file, you could have added separate Maven goals for Cobertura in Jenkins as well.

<build>

<finalName>Unitconversion</finalName>

<groupId>org.codehaus.mojo</groupId>

<artifactId>findbugs-maven-plugin</artifactId>

<version>${findbugs.version}</version>

</plugin>

<groupId>org.codehaus.mojo</groupId>

<artifactId>cobertura-maven-plugin</artifactId>

<version>${cobertura.version}</version>

</formats>

</configuration>

<phase>package</phase>

<goals>

<goal>cobertura</goal>

</goals>

</execution>

</executions>

</plugin>

</plugins>

</build>

<groupId>org.codehaus.mojo</groupId>

<artifactId>findbugs-maven-plugin</artifactId>

<version>${findbugs.version}</version>

</plugin>

<groupId>org.apache.maven.plugins</groupId>

<artifactId>maven-checkstyle-plugin</artifactId>

<version>${checkstyle.version}</version>

</plugin>

<groupId>org.apache.maven.plugins</groupId>

<artifactId>maven-surefire-report-plugin</artifactId>

<version>${surefire.reportplugin.version}</version>

</plugin>

<groupId>org.codehaus.mojo</groupId>

<artifactId>cobertura-maven-plugin</artifactId>

<version>${cobertura.version}</version>

</formats>

</configuration>

</plugin>

</plugins>

</reporting>

Run the job and everything should work out of the box. Do another build to start getting history graphs like below of the trend of failing tests, checkstyle warnings, issues found by Findbugs and te code coverage statistics from Cobertura.

Share code between Windows and Linux using git

2014-01-21T17:59:00.000+01:00

Here's how I setup my git repository on my Linux HTPC which I can store my projects on from the Windows workstation. No extra daemons or servers running. Plain ssh.

First create a repository on the Linux machine.

johan@johanhtpc ~ $ mkdir gitrepos
johan@johanhtpc ~ $ cd gitrepos/
johan@johanhtpc ~ $ mkdir UnitConversion.git
johan@johanhtpc ~ $ cd UnitConversion.git/
johan@johanhtpc ~ $ git --bare init --shared=all

Now, from the Windows machine, I start up gitbash and go to the directory where I have the code I want to share. Then I add a new remote against my Linux machine and name the remote htpc.

Johan@ELLINGTONI5 /c/ws/UnitConversion
$ git init
Initialized empty Git repository in c:/ws/UnitConversion/.git/

Johan@ELLINGTONI5 /c/ws/UnitConversion (master)
$ git remote add htpc johan@johanhtpc:gitrepos/UnitConversion.git

I add everything in this directory to the local repository

Johan@ELLINGTONI5 /c/ws/UnitConversion (master)
$ git add --all

Johan@ELLINGTONI5 /c/ws/UnitConversion (master)
$ git commit

Now, let's push everything over the network to the Linux machine.

Johan@ELLINGTONI5 /c/ws/UnitConversion (master)
$ git push htpc master
johan@johanhtpc's password:
Counting objects: 729, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (601/601), done.
Writing objects: 100% (728/728), 141.03 MiB | 8.35 MiB/s, done.
Total 728 (delta 118), reused 0 (delta 0)
To johan@johanhtpc:johanrepo.git
869b12e..ab0f0b7 master -> master

Now, if I want to checkout the code on the Linux machine as a working copy, it's really simple

johan@johanhtpc ~/ws $ git clone ~/gitrepos/UnitConversion.git
Cloning into 'UnitConversion'...
done.

Now, push and pull from the local repositories against the common to work. Notice that from the Linux working repository the remote is named by default origin. So when pushing the command will be

johan@johanhtpc ~/ws/UnitConversion $ git push origin master

Weather Station using Raspberry Pi, Tomcat and CouchDB

2014-01-01T18:51:00.000+01:00

As a Christmas gift I've built a remote temperature sensoring system to make it possible to record and keep track of the temperature in a summer house on an island in the Baltic Sea. The background is that the temperature cannot be too cold in the house during the winter, since the piping may freeze. This gizmo could maybe help in tuning the electric heating of the house to avoid making it too warm but not too cold either. It will also help to identify when the power is out in the house and the heating is malfunctioning making it necessary to travel out to the house to avoid the water to freeze.

Overview

The layout is a Raspberry Pi using a DS18B20 digital temperature sensor that reads the temperature in the house. There is a NMT radio router in the house which serves Internet access. On a Tomcat server in the cloud, a Java web app accepts readings from the Raspberry via a REST API and stores the information in a CouchDB database. The web application also presents a single page web app that reads temperature data via the REST API and presents some nice graphs and tables. The frontend is built using Bootstrap to get a responsive design for both desktop and mobile.

The finished web application would look like this on desktop

and on a phone it would scale appropriately as well.

At the top the application will report for how long the sensor has been active (possibly since the last electricity outtake). If the sensor has not reported any readings during 15 minutes, it is assumed to be offline and a warning will be presented that we have no knowledge of the current temperature. If the ekectricity is gone in the house the heat will probably also be gone.

Setup the hardware

What you need:

Raspberry Pi
SD card (at least 4GB)
Micro USB cable
Ethernet cable
DS18B20 temperature sensor
4.7 kOhm resistor
Wires
Piece of PCB bread board
Some kind of case
Soldering iron

So first of all let's setup the Raspberry Pi unit. I had the oldest model with 256MB RAM and Ethernet. I also have one of the newer 512MB models and I've tried the setup successfully on both. Since the 256MB version worked, that's the one I've shipped. Here's how to make it into a temperature sensor.

Try out the connections on a breadboard according to this sketch (borrowed from AdaFruit)

The ports on the Pi are if not obvious in the sketch the 3.3V power port at slot 1, the data pin is pin #4 and the third wire is connected to ground.

DS18B20 water proof temp sensor

There are several versions of the DS18B20 temperature sensor. I used the water proof version, it's only marginally more expensive than the others but since it has a chord in contrast to the other ones it can be put outside a window if you want.

Then install the software according to below and make sure everything works. However, to make the final product more stable and resistent to shakes you should of course solder the wires. I recommend using an experiment board for this with lanes. I bought one of these a long time ago from Swedish Kjell & Company. It makes the soldering easy and you have lanes of conducting copper which makes it easy to overview your structure and debug errors with a voltmeter.

In this build the amount of board needed is tiny so not many cents of hardware needed. I bought a general purpose plastic box as well to mount the parts within. The box I found had predrilled holes within the box suitable for attaching PCBs and other parts. Very practical.

The final assembly looked like this with the top of the box removed

Setup the software

Burn Raspbian OS to SD card (I had an old 4GB digital camera SD card over.
Enable SSHD as default. See http://macgyverdev.blogspot.se/2012/08/raspberry-pi-how-to-get-ssh-and-tomcat.html
Create a script directory and copy the Python program into it. You find the python source code in the GitHub repository https://github.com/johannoren/WeatherStation in the folder raspberrypi/src/weatherstation.py

mkdir weatherstation
scp /WeatherStationServer/raspberrypi/src/weatherstation.py pi@piaddress:weatherstation/

So the juice is in the weatherstation.py python script. But to run it by default on start up we create a wrapper bash script. Create a file /home/pi/weatherstation/weatherstation.sh containing

#!/bin/sh
sleep 10
sudo python /home/pi/weatherstation/weatherstation.py

Make sure this kicks in when the Raspberry boots by adding this to /etc/rc.local

/home/pi/weatherstation/weatherstation.sh &

In the weatherstation.py script, adjust the URI to your potential backend server. The lines containing the following should be adjusted to your server and appname. The appname should be changed to the name of your system preferrably so that you may have multiple systems running on the same backend and CouchDB database.


conn = httplib.HTTPConnection("192.168.1.6:8080")

conn.request("POST", "/WeatherStationServer/api/temperature/appname", params, headers)

Reboot the Raspberry Pi and the script should try to post readings to the URI in the script.

If you want to make your own script or just verify that the sensor is working correctly the important thing about this sensor is that when you add the kernel modules that handle the protocol the sensor is using, specific file handles will be created by the operating system containing the current temperature.
So you could alternatively try

sudo modprobe w1-gpio
sudo modprobe w1-therm
cd /sys/bus/w1/devices
ls
cd 28-xxxx (change this to match what serial number pops up)
cat w1_slave

So, assuming you are using the provided python script, now we must setup a server that can handle these temperature postings. The source code is in the GitHub repository, you can pull via https://github.com/johannoren/WeatherStation.git

Install this in a Java web server, I used Tomcat 7. To install Tomcat on a Linux Ubuntu flavoured server is trivial

sudo apt-get install tomcat7 tomcat7-admin tomcat7-common

I personally use Eclipse to build my code, and then export the Web module as war archive (Right-click on the module in Eclipse and choose Export -> WAR archive). Then you can deploy the war file directly in the Tomcat web admin console which is usually located here http://serveraddress/manager/html.

However, the application must store the temperature data in a database and it is configured to use HTTP RESTful calls to store and retrieve JSON data. CouchDB will make a perfect backend for this.

Some notes on installation and how to work with CouchDB using curl in this blog post http://macgyverdev.blogspot.se/2013/12/couchdb-on-linux-mint.html, but it is trivial, apt-get to install.

sudo apt-get install couchdb -y

Create a database for the particular temperature sensor application via

curl -vX PUT http://127.0.0.1:5984/nameofapp

Depending on where you have deployed the CouchDB databse the Java application must be adjusted to communicate to the correct address and port. Before building and exporting the war archive to deploy in Tomcat make sure this constant is correct

WeatherStation /src/se/noren/weatherstation/WeatherStationServiceImpl.java

private static final String COUCHDB_SERVER = "http://johanhtpc:5984";

That's it, now the web app on the server can start posting readings to the database via essentially doing POSTs to the same URL. I used Spring Templates in the Java code which makes REST calls a no brainer. Look at this source code to figure out how to wrap the Spring Template to handle cookies, error handling etcetera https://github.com/johannoren/WeatherStation/blob/master/src/se/noren/weatherstation/adapter/CouchDBAdapter.java

If you wish to see the contents of the database you can do something like this

curl -X GET http://127.0.0.1:5984/nameofapp/_all_docs?include_docs=true

And if you want to delete it to reset testing, you can guess what you need

curl -vX DELETE http://127.0.0.1:5984/nameofapp

More commands in the previous mentioned post.

All good. That's about it I think, if interested in more details on some part, please comment.

If you want to use Fahrenheit or some other system of measurement for temperatures, check out my new hobby project All About Units where there's a lot of goodies on units.

You can buy your Raspberry Pi from many places on the net. Amazon has got both new and used ones for a cheaper prize.

Addition 2015-01-06:
This setup has been extended with another temperature sensor to monitor outside temperature as well. See this blogpost for the additions: http://macgyverdev.blogspot.se/2015/01/raspberry-pi-weather-station-with.html

Just for reference:
I added Google Analytics tracking to be able to see the utilization of the sensor. Here I learned a new thing as well about Analytics. I had the probe run for some time at home before christmas to see that it behaved stable and didn't crash after a long running time, which it didn't, but I unfortunately noticed that the first deployment I made in Google App Engine of the server backend used up to much resources and went over the free quota limit making the server unusable. So I moved the server backend to another server residing on a different domain. Suddenly the Analytics stats disappeared on december 22nd. I had already started wrapping the present. :-/

So the problem is that Google Analytics is specifying the cookie domain in the Javascript. I think this is new, I have no domains in my old Analytics scripts. So what you need to do if you encounter this problem is to manually change this line in the Google Analytics Javascript snippet

	(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]\|\|function(){
	(i[r].q=i[r].q\|\|[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
	m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
	})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

	ga('create', 'UA-46361998-1', 'newdomain.com');
	ga('send', 'pageview');

Git GitHub Cheat Sheet

2013-12-28T22:49:00.000+01:00

Some of the most frequent git commands I use, but also forget between the times I need them.

Setup a repository

git clone <repository>

Clone the specified repo to current location. Think CVS checkout.

To clone a GitHub repository, copy the link to the repo on the GitHub site.

git clone https://github.com/johannoren/WeatherStation.git

If you instead start by creating your project locally you initialize git by

mkdir MyProject

cd MyProject

git init

To add a file

touch foo

git add foo

git commit -m "First commit"

To connect your local repository to GitHub (or other remote repository) assuming we have created a MyProject project on GitHub we create a remote named origin.

git remote add origin https://github.com/johannoren/MyProject.git

To push our local commited file to the remote origin on the main branch master

git push origin master

To clone a repository on one of your other machines, do this over ssh
git clone ssh://johan@192.168.1.6:/home/johan/gitrepos/MyRepo.git

Git configuration

git config -e

Open the Git config file in the default editor

git config --global user.name 'Johan Noren'

git config --global user.email abc@gmail.com

Edit the author and email when making commits

git config --list

List all Git configuration options

If you add --global after these config commands, they will be applied to all repositories and not only the current repo.

Diffs, shows, blames, history and info

git diff

What has changed since your last commit? To diff only a file use

git diff -- <filename>

git status

List added files to the staging area, changed files and untracked files.

git log

Show the most recent commits. Comes with a collection of options:

--color Color coded

--graph Commit graph added to the left

--decorate Add branch and tag names to commits

--stat Show files changed, inserted, deleted

-p Show all diffs

--author="Johan Noren" Commits by a certain author

--after="MMM DD YYYY" ex. ("Jun 20 2008") Filter commits by date

--before="MMM DD YYYY"

--merge Filter out commits occuring in the current merge conflict.

git show <revision>

Show the diff of a commit specified by <revision>. Revision can be any SHA1 commit ID, branch name, or tag.

git blame <filename>

Show the author of each line in a file.

git ls-files

List all files version controlled

Add and delete files

git add <file> <file> ...

Add files to the git project

git add <directory>

Add all files in direcotry including all subdirectories

git add .

Add all created/modified files in current directory (not deleted)

git add -u

Add to index only files deleted/modified and not those created

git add -A

Do both operation at once, add to index all files

git add -p

Patch mode allows you to stage parts of a changed file, instead of the entire file. This allows you to make concise, well-crafted commits that make for an easier to read history.

git rm <file> <file>

Remove the files from the git project.

git rm $(git ls-files --deleted)

Remove all deleted files from the git project

Stage and commit

git add <file1> <file2> ...

git stage <file1> <file2> ...

Add changes in <file1>, <file2> ... to the staging area which will be included in the next commit

git add -p

git stage --patch

Walk through the current changes (hunks) and decide for each change which to add to the staging area.

git reset HEAD <file1> <file2> ...

Remove files from the next commit

git commit <file1> <file2> ... [-m <message>]

Commit <file1>, <file2> ... optionally using commit message <msg>

git commit -a

Commit all files changed since your last commit not including new (untracked) files.

Branches and merging

git branch

List all local branches

git branch -r

List all remote branches

git branch <branchname>

Create a new branch named <branchname>, referencing the same point in history as the current branch.

git branch <branch> <start-point>
Create a new branch named <branch>, referencing <start-point>, which may be specified using a branch name or a tag name and more.

git push <repo> <start-point>:refs/heads/<branch>
Create a new remote branch named <branch>, referencing <start-point> on the remote. Repo is the name of the remote.
Examples:
git push origin origin:refs/heads/branch-1
git push origin origin/branch-1:refs/heads/branch-2
git push origin branch-1 ## shortcut

git branch -d <branchname>

Delete branch <branchname>

git branch -r -d <remote-branch>

Delete a remote-tracking branch. Example

git branch -r -d branchname/master

git checkout <branchname>

Update the working directory to reflect the version referenced by <branchname> and make the current branch <branchname>

git checkout -b <branchname> <start-point>

Create a new branch <branchname> referencing <start-point>, and check it out.

git merge <branchname>

Merge branch <branchname> into the current branch.

Handle remote repositories

git fetch <remote>
Update the remote-tracking branches for <remote> (defaults to "origin"). Does not initiate a merge into the current branch, see "git pull".

git pull
Fetch changes from the server, and merge them into the current branch.

git push
Update the server with the commits across all branches that are common between the local copy and the server. Local branches that were never pushed to the server are not shared.

git push origin <branch>
Update the server with your commits made to <branch> since your last push. This is always required for new branches that you wish to share. After the first explicit push, "git push" is sufficient.

git remote add <remote> <remote_url>
Add a remote repository to your git config. Can then be fetched locally.
git remote add myworkteam git://github.com/somename/someproject.git
git fetch myworkteam

Revert local changes

Assuming you did not commit the file, or add it to the index, then:

git checkout filename

Assuming you added it to the index, but did not commit it, then:

git reset HEAD filename

git checkout filename

Assuming you did commit it, then:

git checkout origin/master filename

Assuming you want to blow away all commits from your branch (VERY DESTRUCTIVE):

git reset --hard origin/master

CouchDB on Linux Mint - Cheat sheet

2013-12-20T22:41:00.000+01:00

Here's my cheat sheet for working with CouchDB on a Linux Mint server.

Installation

Installation is trivial
sudo apt-get install couchdb -y

Test to see that it works.
curl http://127.0.0.1:5984/

should return something like

{"couchdb":"Welcome","version":"1.2.0"}

Create a database named 'johantest'
curl -X PUT http://127.0.0.1:5984/johantest

Delete the same database
curl -X DELETE http://127.0.0.1:5984/johantest

Adding documents

Assume you didn't delete the database, add a document like this
curl -X POST http://127.0.0.1:5984/johantest \
-H 'Content-Type: application/json' \
-d '{"SomeProperty":"Test1","AnotherProperty":"Test2","Age":32,"PropList":["Prop1","Prop2","Prop3"]}'

To retrieve all documents in a database

curl -X GET http://127.0.0.1:5984/johantest/_all_docs

Gives
{"total_rows":1,"offset":0,"rows":[
{"id":"4571d772c7d61fa34a7579ce6f04d47b","key":"4571d772c7d61fa34a7579ce6f04d47b","value":{"rev":"1-a268e2541be30dae295fb88015bd1a5c"}}
]}

That will only give references so you can GET each document detail. To fetch the contents of an individual document, fetch using the key from the provious GET.

curl -X GET http://127.0.0.1:5984/johantest/4571d772c7d61fa34a7579ce6f04d47b

Gives

{"_id":"4571d772c7d61fa34a7579ce6f04d47b","_rev":"1-a268e2541be30dae295fb88015bd1a5c","SomeProperty":"Test1","AnotherProperty":"Test2","Age":32,"PropList":["Prop1","Prop2","Prop3"]}

If you wish to fetch all documents in one large JSON blob
curl -X GET http://127.0.0.1:5984/johantest/_all_docs?include_docs=true

Gives
{"total_rows":1,"offset":0,"rows":[
{"id":"4571d772c7d61fa34a7579ce6f04d47b","key":"4571d772c7d61fa34a7579ce6f04d47b","value":{"rev":"1-a268e2541be30dae295fb88015bd1a5c"},"doc":{"_id":"4571d772c7d61fa34a7579ce6f04d47b","_rev":"1-a268e2541be30dae295fb88015bd1a5c","SomeProperty":"Test1","AnotherProperty":"Test2","Age":32,"PropList":["Prop1","Prop2","Prop3"]}}
]}

Settings and logs

Settings are stored in /etc/couchdb/default.ini

To be able to connect to the databse via HTTP from other machines on network, change

bind_address = 0.0.0.0

The actual database is stored by default at
/var/lib/couchdb/1.2.0 and is named in this case johantest.couch

If you wish to move it to another partition or similar, change the settings
database_dir = /var/lib/couchdb/1.2.0
view_index_dir = /var/lib/couchdb/1.2.0

To get a feel of the amount of disk used by Couch I notice that my Weather Station application has stored 8800 JSON documents in a format like this

{"id":"6ea52d20ab226121a325d0e3c5ffe4b5","key":"6ea52d20ab226121a325d0e3c5ffe4b5","value":{"rev":"1-087372f223546fb03c75605decb4a442"},"doc":{"_id":"6ea52d20ab226121a325d0e3c5ffe4b5","_rev":"1-087372f223546fb03c75605decb4a442","temperature":23.75858110517378563,"rawDate":1385961273368,"key":"holmon"}}

That will occupy 28.9 MB of disk with the default settings of compression etcetera.

To see what requests has been made against the database, the log is placed at

/var/log/couchdb/couch.log

which can be changed in the settings file as well. Output for the tests above

[Sat, 28 Dec 2013 09:08:41 GMT] [info] [<0.2082.8>] 127.0.0.1 - - PUT /johantest 201

[Sat, 28 Dec 2013 09:34:03 GMT] [info] [<0.28823.7>] 127.0.0.1 - - DELETE /johantest 200

[Sat, 28 Dec 2013 09:34:07 GMT] [info] [<0.25248.7>] 127.0.0.1 - - PUT /johantest 201

[Sat, 28 Dec 2013 09:34:13 GMT] [info] [<0.3856.8>] 127.0.0.1 - - POST /johantest 201

[Sat, 28 Dec 2013 09:34:22 GMT] [info] [<0.2437.8>] 127.0.0.1 - - GET /johantest/_all_docs?include_docs=true 200

[Sat, 28 Dec 2013 09:35:29 GMT] [info] [<0.2449.8>] 127.0.0.1 - - GET /johantest/_all_docs 200

[Sat, 28 Dec 2013 09:35:41 GMT] [info] [<0.2339.8>] 127.0.0.1 - - GET /johantest/4571d772c7d61fa34a7579ce6f04d47b 200

Clone a GitHub project into Eclipse

2013-12-19T22:27:00.001+01:00

I've been using the Git command line tools to setup my workspaces against GitHub and then importing projects into Eclipse going back and forth to the command line to diff, commit and push back to origin. In my current project I've discovered the Git Repository Explorer in Eclipse and how it makes many of the tasks much easier.

To clone an existing GitHub repository add the perspective Git Repository Explorer

Choose to clone a repository

Add details about the remote repository

The URI can be found on the GitHub page for the repository you wish to clone

Select the branch to check out and in the next view tick the "Import all existing projects after clone finishes"

Then you got your project in your workspace as expected

Now the usual Eclipse goodies har here for you, to diff local changes is much clearer than the command line diff utility for example

The synchronize option to see all changes in your local copy

Inspecting the history of the file is also presented in a more readable manner

Commit and push to origin (GitHub in this case) is a single operation if you wish

Spice up your comments

2013-11-14T18:03:00.000+01:00

I was searching for something on StackOverflow and found this off-topic thread on comments.
A few gems:

Exception up = new Exception("Something is really wrong.");
throw up; //ha ha

//When I wrote this, only God and I understood what I was doing
//Now, God only knows

//
// Dear maintainer:
//
// Once you are done trying to 'optimize' this routine,
// and have realized what a terrible mistake that was,
// please increment the following counter as a warning
// to the next guy:
//
// total_hours_wasted_here = 42
//

//Mr. Compiler, please do not read this.

// I dedicate all this code, all my work, to my wife, Darlene, who will
// have to support me and our three children and the dog once it gets
// released into the public.

// drunk, fix later

// Magic. Do not touch.

return 1; # returns 1

// If I from the future read this I'll back in time and kill myself.

double penetration; // ouch

/////////////////////////////////////// this is a well commented line

// I am not sure if we need this, but too scared to delete.

// I am not responsible of this code.
// They made me write it, against my will.

//Dear future me. Please forgive me.
//I can't even begin to express how sorry I am.

options.BatchSize = 300; //Madness? THIS IS SPARTA!

// I have to find a better job

// hack for ie browser (assuming that ie is a browser)

} catch (PartInitException pie) {
// Mmm... pie
}

// John! If you'll svn remove this once more,
// I'll shut you, for God's sake!
// That piece of code is not “something strange”!
// That is THE AUTH VALIDATION.

try {

}
catch (SQLException ex) {
// Basically, without saying too much, you're screwed. Royally and totally.
}
catch(Exception ex)
{
//If you thought you were screwed before, boy have I news for you!!!
}

// Catching exceptions is for communists

// If you're reading this, that means you have been put in charge of my previous project.
// I am so, so sorry for you. God speed.

/**
* For the brave souls who get this far: You are the chosen ones,
* the valiant knights of programming who toil away, without rest,
* fixing our most awful code. To you, true saviors, kings of men,
* I say this: never gonna give you up, never gonna let you down,
* never gonna run around and desert you. Never gonna make you cry,
* never gonna say goodbye. Never gonna tell a lie and hurt you.
*/

// If this code works, it was written by Paul. If not, I don't know who wrote it

/**
* If you don't understand this code, you should be flipping burgers instead.
*/

//Abandon all hope yea who enter beyond this point

catch (Ex as Exception)
{
// oh crap, we should do something.
}

// TODO make this work

// This is crap code but it's 3 a.m. and I need to get this working.

Netflix on Linux Mint 14

2013-09-22T10:41:00.000+02:00

Netflix uses Microsoft Silverlight in their web version which makes it impossible to watch Netflix on Linux machines since no native client is available. The Pipelight project has released a plugin that emulates Silverlight using the Netscape Plugin API and wine. So all browsers supporting the Netscape Plugin API like Firefox and Chrome should be able to use this trick.

This is tested on my Linux Mint 14 HTPC with Chrome and works like a charm. It is even faster then the earlier Linux Desktop Netflix client that was available as apt-get install.

If you have an earlier version of Pipelight first remove it

sudo apt-get remove pipelight

Install the plugin and enable it

sudo apt-add-repository ppa:ehoover/compholio

sudo apt-add-repository ppa:mqchael/pipelight

sudo apt-get update

sudo apt-get install pipelight-multi

sudo pipelight-plugin --enable silverlight

That should be it. But the Netflix web site has a check that your browser is a Windows based browser. Emulate this by installing a plugin that enables you to choose which user agent your browser should mimick. I use the User Agent Shifter for Chrome.

If you use this one, switch to Windows Firefox 15 or similar in the menu.

Pipelight also supports Adobe Flash, so if you have need for that, install it via

pipelight-plugin --enable flash

Simple backups with rsync

2013-04-14T13:29:00.000+02:00

Here's my notes on how I setup my home network backup system in case I forget it.
I was first thinking of backing everything to some cloud service like Google Drive or Dropbox, but it will be quite expensive since I have too much home movies, images and sound recordings. So what I've done is that I have one backup of the stuff on a USB harddrive and another duplicate on the HTPC server. The same technique could be used to backup to a server at a friends house to make the backups completely fire proof.

Using the old Unix command rsync it is really easy to automate this. I installed rsync via cygwin, google for cwrsync which is rsync for Windows. My HTPC is a Linux Mint server so I created a RSA keypair for my Linux user and stored the keys on my Windows desktop machine in directory c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc.

So now we can authenticate against the HTPC with ssh which rsync supports and I only need to create a configuration of what I want to synchronize.

I created a config command file like this.

@ECHO OFF

SETLOCAL

SET CWRSYNCHOME=%ProgramFiles(x86)%\CWRSYNC

SET CYGWIN=nontsec

SET HOME=%HOMEDRIVE%%HOMEPATH%

SET CWOLDPATH=%PATH%

SET PATH=%CWRSYNCHOME%\BIN;%PATH%



rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/e/Dokument" johan@johanhtpc:PCBackups

rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/e/Musik" johan@johanhtpc:PCBackups

rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/e/Programmering" johan@johanhtpc:PCBackups

rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/e/Bilder" johan@johanhtpc:PCBackups

rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/e/Audiobooks" johan@johanhtpc:PCBackups

rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/c/ws" johan@johanhtpc:PCBackups

rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/c/recordings" johan@johanhtpc:PCBackups

rsync -av --chmod u+rwx -e "ssh -i c:\docume~1\Johan\.ssh\id_rsa_rsync_johanhtpc" "/cygdrive/c/render" johan@johanhtpc:PCBackups

So when run, rsync will check each folder on the Windows harddrive or external harddrive against the directory on the backup server. If new files have been created or existing files are updated they will be synchronized. No action will be taken for directories or files that are unchanged.

To automate this, I used the Windows scheduler. I added a task that will run each night at 00:59. It will simply run the above command.

Create server backdoors using SQL Injection

2013-02-02T17:59:00.003+01:00

If you're a web programmer you are probably aware of the most common security mistakes we make. OWASP keeps statistics on what exploits are the most common. If you're not familiar with these, this should be mandatory reading https://www.owasp.org/index.php/Top_10_2010-Main.

As shown, injections are still one of the worse problems. If you're not familiar with SQL injection check out some basic ways to exploit it on vulnerable site. The examples are often about trying to select some sensitive data and getting the data to be rendered on the vulnerable site.

I'm not a black hat hacker so I've always thought about SQL injection as something primarily putting the site and it's data into danger. But tag along to see that SQL injection can be the entry point of pwning the complete server and getting inside the firewall and the internal network.

Now, I was reading up on SQL the other day for a project at work and stumbled upon some SQL syntax I didn't know about. Combining this with an SQL injection vulnerability could be dynamite.

So first, assume you found a weakness on a site. There are tools for that, but basically try to append code to request parameters like ' or 'foo'='1 or similar to look for server crashes giving you a hint of SQL injection problems like Unknown column 'foo' in 'where clause'. Now you would "normally" start the tiresome work of finding something valuable in the database.

But, with the SQL syntax INTO FILE you can write files. Nice. So depending on what technology the server is based on you could write files that can be accessed via the web interface. If the file names in the URI don't give away what technology used look at the HTTP header value of Server. If for example the header talks about JBoss you can guess that the site is Java based and we could try to create JSP files. Similarly you could aim for creating PHP script files etc if that's whats dished out by the server.

So, by using something like this in the injection exploit (the red is what is supplied by the hacker via the request parameter injection)

SELECT a, b FROM someunknowntable WHERE someunknowncolumn = '' UNION SELECT '<?php system($_GET["cmd"]); ?>' INTO OUTFILE '/var/www/htdocs/pwn.php'; --

or similar for other scripting technologies like JSP, ASP etc you have created a public backdoor.

Catastrophe!

Point you're browser to http://thesite.com/pwn.php?cmd=pwd

to print out the currect working directory of the web server process.

Now only imagination stops you. cmd=cat /etc/passwd /etc/shadow to dump all user credentials. If the web server is running as root it's too easy to start creating misery like keylogging the other users or dumping all databases.

The lesson from this is that if you have five web servers and databases hosting different sites on your server it is the weakest link of them that defines the total security. So by hacking the not so important server with an SQL injection weakness you can get to the data of the highly secured applications with no SQL injection weaknesses via a backdoor.

Some thought on avoiding this kind of problems

Always use frameworks and libraries that removes the possibility of SQL injection. Java has prepared statements or some of the ORM technologies. The other languages has their own ways.
Run the database process as a user with low file access priviligies so that it can't write files anywhere it shouldn't be able to. Or even better, run it on a separate machine.
Same for the web server, don't run it as root. There are other ways of hacking web or application servers to gain shell access.
A general good thought is not to reveal to much information about what technology serves the site if possible to make it harder to exploit knowledge about how it behaves. For example, don't show server versions in HTTP headers, don't show crash stacktraces in server responses in production mode and so on.

Sink Hole Animation

2013-01-04T14:17:00.003+01:00

I made a little animation which fakes a sink hole in the platform outside the Umeå Östra train station. This relies on camera tracking which takes a real scene and incorporates it in a simulated 3D environment.

Prerequisities

A camera, (in my case a Canon 550D), some bright post-its, Blender (free and open source), Gimp or other image processing software and a few hours of modelling time and a nights sleep for rendering the scene.

Pick a scene

Figure out a scene. To make the camera tracking easiser to automate, pick a bright scene so that you will have short shutter times. Also, (which I failed to follow) try to keep your camera steady and make pans slow and steady to avoid blurry and unsharp images in your film. Record in highest possible resolution of your camera.

Object tracking

You must find some high contrast objects in the scene which you will use to track during the movement of the real camera in order for Blender to figure out the relative position of these objects. Preferrably use objects which will have parallax shifts when you move around in the scene. Also use a few objects that lie in your ground plane (the train platform) so that you can create a correct coordinate system.

In this scene, I want good resolution around the sink hole, but there are few high contrast objects, so I scattered some yellow pieces of post it notes around the area.

Record your movie, import it into Blender and use the new Movie Clip Editor, which has come in one of the latest releases, to tag tracking objects. In the best of worlds, the software can follow the movement of the high contrast objects through the whole movie clip. Didn't work like a charm for me, had to manually help the tracker when the camera panned fast, so that's a note to self for future trackings. When you solve the system, Blender will figure out how the camera has moved during the photo shoot and create a camera animation for that for the virtual camera used later when rendering.

Modelling and rendering

I made a real simple hole model in Blender with some gravel textures overlaying eachother. Then by using the composition features of Blender you can merge each frame in the original movie clip with the rendered model with the correct camera position. In this example, the large disk in the image representing the ground is not rendered in the final composition, but it can receive renderable shadows, so that you can have your own 3D objects cast shadows onto the ground in the movie.

For reference, the original movie looks like

This is based in an excellent explanation of the Blender camera tracking functionality by Andrew Price on BlenderGuru.

Hermanizer Power Pedal - A DIY Fuzz Box

2012-12-29T01:55:00.002+01:00

For christmas gift to my brother I thought I'd try to make a guitar effect pedal. The main feature would be to have a nice sounding distortion effect, classic rock fuzz. I also found an article on Instructables by Harrymatic discussing adding a timer IC to the circuit to create a sound slicing/chopping kind of effect. This construction is based on his ideas.

So what you need is an amplifier IC, I used an LM386 circuit which can amplify a signal up to 200 times. To be able to control the amplification and the output signal, two potentiometers (resistors with variable resistance) acts as gain and volume controls. The sound slicing effect is created by a NE555 timer circuit which flips the voltage on its output pin high and low in a repeating fashion. The frequency of this is determined by a third potentiometer which is glued to a "effect rate" knob.

Circuit diagram of the effect pedal - click for larger picture

Depending on the state of the FX On/Off switches, pin 6 of the amplifier IC is fed by either a constant feed from the power source or a chopped up square wave from the timer IC.

So first step to try this out was connect everything on a breadboard.

If you buy your ICs with DIL8 sockets they will fit nicely on a standard breadboard. An important lesson from this setup is that you must ground both your input jack coming from your instrument and the output jack going to headphones/speakers/amplifiers or else you will get very disturbing hizzes and noises.

Once everything worked out on the breadboard I printed and soldered the circuits on a stripboard. The soldering is not shown in this picture since the circuits are on the backside of the stripboard.

For a case I bought a metal case and drilled the necessary holes for the potentiometers, switches and the power LED.

I bought the stuff I didn't already have at home from ELFA. It amounts to somewhere around 200 SEK. The integrated circuits are about 8 SEK each but the casing and the knobs turned out to be the most expensive stuff.

After stuffing everything inside the pedal works fine. When only using the distortion effect no hearable background fuzz is noticed. However, when enabling the chopping effect there is a constant background noise which is evident if no signal is coming from the instrument.

The final effect box

So how does the pedal sound? Well, this is the sound when applying quite a lot of distortion effect on an otherwise clean organ sound. I'm not a guitar player like my brother, but here's a few chords from my old Squire guitar lined directly into the effect pedal with pretty much distortion.

Here's a synth line which after a few seconds get the the chopper effect applied. In the end of the clip the rate of the effect is increased to maximum.

Functional programming in Java?

2012-10-06T11:18:00.001+02:00

After more toying with Scala on my spare time while hacking Java in office hours I miss out on using all these functional idioms in my Java programs. So with Java 8 coming closer I got interested in how the JDK team is planning on utilizing the new Java closure syntax in for example the collections libraries to support a more functional style of programming. While I have it fresh in memory, let me tell you some cool aspects of this!

Closures in Java

Closures are anonymous functions also known as lambda expression. In languages where functions are first class members you could assign a lamba expression to a function variable. However, this is not entirely true for the Java implementation. In order not to mess up the type system to much, the engineers behind the implementation of the Lambda JSR 335 in OpenJDK has taken the approach to use interfaces containing one method to become special in the language. Such an interface is called a functional interface. An example of such an interface is ActionListener

public interface ActionListener { 
    void actionPerformed(ActionEvent e);
}

or Runnable or Comparator.

So in JDK 7 or earlier syntax, this is how you would declare for example an ActionListener

ActionListener l = new ActionListener() { 
  public void actionPerformed(ActionEvent e) { 
    doWork(e.getModifiers());
  }
};

However, with the new Java 8 syntax, you'd write it as

ActionListener l = (ActionEvent e) -> doWork(e.getModifiers());

So you get rid of all the unnecessary boilerplate code inherent in anonymous class creations so common in Java. More pleasing examples of usages of this syntax

Comparator<String> c = (s1, s2) -> s1.compareToIgnoreCase(s2);

FileFilter java = f -> f.getName().endsWith(".java");

There's a lot of interesting things going on here like how lexical scopes work, variable binding, type inference etcetera. Check out project lead Brian Goetz report on how these things works.

Java Collection libraries

So how will this be used in the collection libraries which are probably the most used toolkit of the Java platform? First of all, the Collections team has decided not to restart by rewriting the collections libraries from scratch. While mentioning that this might be a candidate for future JDK versions, version 8 will instead provide an evolutionary step forward in the Collections by adding extension methods to existing interfaces (List, Set, Iterable) and retrofit existing classes with new interfaces such as Stream.

A major shift will be from the imperative style of external iteration to the more functional style of internal iteration. For example, the recommended idiom in Java 5+ to change a property on all objects in a collection uses

for (Car c : cars) {
    c.setState(MOVING);
}

With closures you'll write this as

cars.forEach(c -> { c.setState(MOVING); });

What are the benefits of this idiom? You move the control flow to the library instead of the client code. In this way the library can decide on potentially use laziness, parallelism and out-of-order execution to improve performance which will be showed in later examples.

You can pipeline operations. In this example the filter operation uses a predicate to decide which objects in the collection to pipe to the final forEach clause.

cars.filter(c -> c.getWeight() > 2000)
      .forEach(c -> { c.setState(STOPPED); });

And to store results from computations using for example the map operation which operates on each value in the piped collection use something like

Set<Engine> smallEngines = cars.filter(c -> c.getMaxSpeed() < 100)
                .map(c -> c.getEngine())
                .into(new HashSet<>());

or to sum them. This is the well known functional idiom of map reduce.

int sum = cars.filter(c -> c.getState() == MOVING)
                .map(c -> c.getWeight())
                .sum();

So, all these operations will not create temporary new collections and pass on to the next operation. Instead they operate lazily and stream values between the control blocks. This implies good performance when for example searching for the first object that satisfies some condition. The upstream iterator in this example will not continue the iteration when getFirst() has found a match.

Car fastCar = cars.filter(c -> c.getSpeed() > 120).getFirst();

When used to these constructs, a lot of boilerplate code should be possible to remove. Here Brian Goetz shows an example of a method in java.lang.Class as today

 for (Method m : enclosingInfo.getEnclosingClass().getDeclaredMethods()) {
     if (m.getName().equals(enclosingInfo.getName()) ) {
         Class<?>[] candidateParamClasses = m.getParameterTypes();
         if (candidateParamClasses.length == parameterClasses.length) {
             boolean matches = true;
             for(int i = 0; i < candidateParamClasses.length; i++) {
                 if (!candidateParamClasses[i].equals(parameterClasses[i])) {
                     matches = false;
                     break;
                 }
             }

             if (matches) { // finally, check return type
                 if (m.getReturnType().equals(returnType) )
                     return m;
             }
         }
     }
 }

 throw new InternalError("Enclosing method not found");

and how it could be rewritten without all the temporary variables making it both more readable and less error prone.

Method matching =
  Arrays.asList(enclosingInfo.getEnclosingClass().getDeclaredMethods())
    .filter(m -> Objects.equals(m.getName(), enclosingInfo.getName())
    .filter(m ->  Arrays.equals(m.getParameterTypes(), parameterClasses))
    .filter(m -> Objects.equals(m.getReturnType(), returnType))
    .getFirst();
if (matching == null)
    throw new InternalError("Enclosing method not found");
return matching;

There's a lot of more cool features on the project site, but before ending you should see how easy parallel computation can become. By streaming the pipeline via parallel() the library will try to divide the pipeline stream of operations to all your cores.

int sum = cars.parallel()
                .filter(c -> c.getState() == MOVING)
                .map(c -> c.getWeight())
                .sum();

Via the new interface Splittable you can also very easily use the Fork/Join framwork for divide and conquer tasks.

Timeplans

This looks awesome. But when can we use it? According to the milestone plan the public review version should be available in January 2013. The JDK 8 timeplan currently looks like

2012/7 Expert Group formation
2012/9 Early Draft Review
2013/1 Public Review
2013/6 Proposed Final Draft
2013/8 Final Release
http://openjdk.java.net/projects/jdk8/spec/

But you can download bleeding edge versions of the OpenJDK 8 binaries today and play around with the lambda language construct and the current implementations in the collections libraries as well as a lot of the other libraries. http://jdk8.java.net/download.html

Alternative functional libraries

If you can't wait there are libraries for functional programming in Java that will work with JDK5 or newer.

Guava

Googles Guava libraries have support for functional idioms. However without language support the code easily becomes messed up with boilerplate. On the other hand, there are a lot of good stuff in Guava like a richer set of collection constructs and easier use of immutable collections types. Here

Multiset<Integer> lengths = HashMultiset.create(
  FluentIterable.from(strings)
    .filter(new Predicate<String>() {
       public boolean apply(String string) {
         return CharMatcher.JAVA_UPPER_CASE.matchesAllOf(string);
       }
     })
    .transform(new Function<String, Integer>() {
       public Integer apply(String string) {
         return string.length();
       }
     }));

Lambdaj

Another interesting library is Lambdaj which uses static imported methods to hide give a nicer looking syntax. This is some typical Java code to sort a list of persons according to age

List<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
        public int compare(Person p1, Person p2) {
           return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
        }
});

With Lambdaj, you could express this as

List<Person> sortedByAgePersons = sort(persons, on(Person.class).getAge());

Check out more features at http://code.google.com/p/lambdaj/wiki/LambdajFeatures.

FunctionalJava

FunctionalJava solves the syntax verbosity problem by using the Java 7 BGGA proposal syntax. This adds closures as a part of the language dialect. However, this requires a pass with a pre compiler to render compilable Java code.
This is an example of code that adds 42 to each element in the array.

final Array<Integer> a = array(1, 2, 3);
final Array<Integer> b = a.map({int i => i + 42});
arrayShow(intShow).println(b); // {43,44,45}

Noteworthy is that solution also heavily relies on static imports. Check out more example at http://functionaljava.org/examples/1.5/

My thoughts

In the end though, due to the lack of anonymous functions in Java today, the best choice to program in a functional way is probably to stick to Scala, Clojure, Groovy or another of the JVM languages that has inherent support for this style until Java 8. With what we got today in Java you can still use many of the functional concepts like preferring immutable data, avoiding side effects and more.

The above mentioned alternatives are just a few of what's out there. But common among them are either that you must rely on preprocessing some functional dialect of Java to produce compilable Java code or to use a verbose syntax like Guava. In my opinion these tradeoffs effect on readability, maintainability and possibly portability just isn't worth it.

By the way, Brian Goetz appears 20 mins into the Java One 2012 Technical keynote to show off some collection examples of Java 8. http://medianetwork.oracle.com/video/player/1871712019001

Debugging Knockout.js

2012-09-03T20:29:00.000+02:00

Knockout.js is really powerful. A consequence of being awesome is unfortunately that its magic makes it hard to debug when it doesn't behave as you expect.

Here's a trick that might come in handy if a data binding does not behave properly. You can print the the variables of the view model that is in the current scope by inserting this debugging tag in your HTML source.

<pre data-bind="text: JSON.stringify(ko.toJS($data), null, 3)"></pre>

Yielding a print like this in the rendered page

{
   "myViewModelVar1": "someValue",
   "myViewModelVar2": "someOtherValue"
}

You know any other handy tricks?

Learning Scala - Photo collage creator

2012-08-19T15:28:00.000+02:00

I finally took the time this summer to read a book on Scala. I bought Programming in Scala by Martin Odersky, the father of the language, which I think was a good choice. Regardless whether I'll write a lot of Scala programs in the future I learnt some new general programming techniques and a well needed recap on programming language fundamentals from school. After reading it and applied it on a couple of hobby projects I must say that I feel excited.

My first project to play around with the language is a photo collage creator where you supply the program a motive and a set of images to create a collage from. The algorithm tries to puzzle the images together to create a collage that best fits the motive.

The motive to create collage from.

The motive is divided in segments and the image catalogue is searched for best fitting images to puzzle together.

The final collage in low-res.

When printing the collage in high resolution, for example 16384 x 10922 pixels the effect becomes quite cool when you approach the collage from a distance to a near closeup.

Let me just show you an arbitrary Scala function in this program that demonstrates a few of the things that I like compared to my daily work horse Java.

  /**
   * Calculate the average brightness of a portion of an image.
   * 
   * @param img Image to analyse for average brightness.
   * @param startx Start x coordinate of image subset to analyze 
   * @param starty Start y coordinate of image subset to analyze
   * @param stopx Stop x coordinate of image subset to analyze
   * @param stopy Stop y coordinate of image subset to analyze
   * @return Average brightness of the subset of the image
   */
  def brightness(img: BufferedImage, startx: Int, starty: Int, stopx: Int, stopy: Int): Int = {

    @tailrec
    def estimateBrightness(x: Int, y: Int, maxx: Int, maxy: Int, aggr: Int): Int = {
      if (y == maxy)
        aggr
      else if (x == maxx)
        estimateBrightness(startx, y + 1, maxx, maxy, aggr)
      else
        estimateBrightness(x + 1, y, maxx, maxy, aggr + rgb2gray(img.getRGB(x, y)))
    }
   
    /*
     * Average the brightness of the number of evaluated pixels with 
     * the aggregate of their calculated values.
     */
    val aggregatedBrightness = estimateBrightness(startx, starty, stopx, stopy, 0)
    aggregatedBrightness / ((stopx - startx) * (stopy - starty))
  }

As you can see, Scala is statically typed, but the compiler tries to infer as much as possible. You can create a constant variable with the val keyword. But it will in this example figure out that the variable aggregatedBrightness must be of the type (or subclass) Int since it is evaluated via the function estimateBrightness(). You will save yourself a lot of boilerplate declarations.

But what about the function estimateBrightness? It is declared inside the scope of the function brightness(). In Scala a function is on par with any plain old objects and can be referenced via variables or passed as arguments to functions and also be declared inside functions as a consequence. Why wouldn't it always be so?

Everything has a value, even a for loop or an if clause will result in something that can be passed to a variable or statement. This makes for concise and beautiful code.

Scala is basically a functional language but with all the imperative concepts around to make it easy for imperative people like me to make the transition to a more functional style in the tempo that suits me. In this example I made my calculations in a functional style using recursion instead of using loop constructs. I tried to write the program without any for or while loops at all but my conclusion is that just because it is nice to make everything recursive and functional it must not inherently be readable and understandable. I'll stick to my imperative guns when I need them for some time more.

An interesting annotation is @tailrec on the local function declaration. It forces the compiler to verify that this recursive function will be tail-call optimized, meaning that you can be sure that this function will not create stack frames for each invocation in the recusive loop. If so you would be running out of stack after some 10 000 invocations depending on your JVM startup flags.

To be able to write efficient and understandable functional programs my impression is that the requirements of the programmer are heightened compared to programming in plain old Java/C/C++. A challenge I'm gladly willing to continue with.

Instead of me trying to convince you that Scala seems like a great contribution to the Java VM family I strongly recommend you to read the book. You'll definitively become a better C# or Java programmer as well afterwards.

If you want to play around with the Photo Collage creator program and generate som collages of your own clone the code from GitHub.

https://github.com/johannoren/PhotoCollage

I have used Eclipse with the Scala plugin which make the program run without any hazzle. To configure it without any code changes, create a directory photos in the module, and put one image in that directory as your motive and name if motive.jpg. Put all your images that will be part of the puzzle in a subdirectory called inputphotos. Run PhotoCollage and monitor the standard out until the program is finished. Run time depends mainly on the number of images in the directory inputphotos.

Raspberry Pi - how to get ssh and Tomcat running

2012-08-04T02:21:00.000+02:00

Finally got my Raspberry Pi! The cheap $25/$35 board with 700Mhz ARM cpu, GPU, 256 mb RAM, dual USB, ethernet and a bunch of general purpose IO pins. Looking awesome in its bare metal and firing it up is no problem. I flashed an SD card with the Raspbian “wheezy” Linux distribution. To write the image to the SD card I used Win32DiskImager from a PC with SD card slot.

After attaching USB keyboard, network cable and HDMI it comes to life by using a micro USB as power supply. The diods flashes and even X runs quite smooth on this limited hardware.

However, after playing around I soon realised I will be much more comfortable working on a distance from my ordinary desktop machine. So how to enable ssh?
A lot of tutorials talks about something as simple as this to enable ssh daemon on boot.
sudo mv /boot/boot_enable_ssh.rc /boot/boot.rc

Sorry, I have no such files in my /boot directory. Furthermore, when trying to start the ssh daemon with
/etc/init.d/ssh start
it refuses to start. Clues in the startup log are

Could not load host key: /etc/ssh/ssh_host_rsa_key Could not load host key: /etc/ssh/ssh_host_dsa_key

Why these are corrupt I don't know, but it's easy to regenerate them.

ssh-keygen -t rsa1 -f /etc/ssh/ssh_host_rsa_key
ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key

Make ssh daemon start permanent

sudo update-rc.d ssh defaults

A sudo reboot and everything seems ok.

Now, my mission for tonight was to get a web server running on the chipset. Here's what you need to do to make Tomcat 7 run.

Tomcat obviously need Java:
sudo apt-get install openjdk-6-jdk

And you obviously need a potent editor
sudo apt-get install vim

Clean up your installs to save some space on the SD card
sudo apt-get clean

Now, download, unpack and install Tomcat
wget http://mirrors.axint.net/apache/tomcat/tomcat-7/v7.0.28/bin/apache-tomcat-7.0.28.tar.gz
tar xzf apache-tomcat-7.0.28.tar.gz
cd apache-tomcat-7.0.28/conf
vim tomcat-users.xml

Add a user to the authorization file, directly below <tomcat-users> add
<user username="system" password="raspberry" roles="manager-gui"/>

Now start Tomcat
cd ../bin
sudo sh startup.sh

Nice! From your PC (or via a browser on the Pi) surf against the Tomcat console.
http://192.168.1.90:8080/

(Figure out the ip address via for example ifconfig)

It takes a short while to warm up the server but then you can login via Manager App. Now, it's business as usual. Upload a war archive and you have a nifty web server running you web application, for $35!

MacGyver Development

Solve the party planning problem and earn $1 000 000 USD

Raspberry Pi Weather Station with multiple thermometers

Become a better programmer with programming challenges

Complexity theory

Know your algorithms

Sorting

Graph problems

Sequence and string problems

Number theory

Combinatorics

Probability theory

Dynamic Programming

Divide and Conquer

Greedy algorithms

Backtracking

UVA Online Judge

New Eclipse project connected to Git repository

Porthello Legends - Android Reversi Port

Apache web server as reverse proxy and virtual host for Tomcat 7

Setup Apache HTTP server as reverse proxy

Enable and disable the site

How to make Jenkins install the packaged war in a Tomcat 7

How to change context root to / in Tomcat 7

Java 8 in Eclipse

Setup Jenkins project from Git repository with Findbugs, Cobertura and Checkstyle

Install Jenkins and plugins

Creating Jenkins job

Maven pom.xml configuration

Share code between Windows and Linux using git

Weather Station using Raspberry Pi, Tomcat and CouchDB

Overview

Setup the hardware

Setup the software

Git GitHub Cheat Sheet

Setup a repository

Git configuration

Diffs, shows, blames, history and info

Add and delete files

Stage and commit

Branches and merging

Tags

Handle remote repositories

Revert local changes

CouchDB on Linux Mint - Cheat sheet

Installation

Adding documents

Settings and logs

Clone a GitHub project into Eclipse

Spice up your comments

Netflix on Linux Mint 14

Simple backups with rsync

Create server backdoors using SQL Injection

Sink Hole Animation

Prerequisities

Pick a scene

Object tracking

Modelling and rendering

Hermanizer Power Pedal - A DIY Fuzz Box

Functional programming in Java?

Closures in Java

Java Collection libraries

Timeplans

Alternative functional libraries

Guava

Lambdaj

FunctionalJava

My thoughts

Debugging Knockout.js

Learning Scala - Photo collage creator

Raspberry Pi - how to get ssh and Tomcat running