Atomocopter

Today I write about a fine piece of software, which helps a lot to improve your workflow. My desktop consists of several computers, depending on what I’m working. Very often I ended up with 2 keyboards, one mouse and a notebook, chaos on my desk! But not anymore! I found Synergy to be a great solution for my problem. Now it’s almost like I have a second display connected to my main computer. But actually I have two displays (PC, notebook) with two separate computers, each providing CPU capacity. And I even can copy and paste between both of them.

The main work is done by an open source program called Synergy. With QuickSynergy, which provides a GUI for Synergy, the configuration part is done within a few seconds.

To be set up on Ubuntu just do:
sudo apt-get install synergy
sudo apt-get install quicksynergy
Launch QuickSynergy on both computers, the one with pluged keyboard and mouse will act as server, the others will be clients. You have to refer to your clients by their host names, IP-adress won’t work. So make sure your server has a proper /etc/hosts file. Here you can read more about it: gnuski.blogspot.com. The interface looks slightly different than on these screenshots, but that’s not really important.

A side effect is: according to Anton Olsen’s article on Wired this is another step towards complete geekness. Well, with QuickSynergy this is an easy point.

The convex hull of a finite set of points M can be understood as the minimal convex set which still contains M. A more detailed definition can be found at Wikipedia. One of the best known algorithms to calculate the convex hull is the Graham scan. This algorithm finds a valid solution with a time complexity of O(n*log n). The theory behind this algorithm can be found on the web, again the article on Wikipedia is a good point to start.

I implemented this algorithm quick and dirty in Python, here’s the code:


def theta(p0,p1):
   """Actually not an angle but has the same ordering functionality."""
   dx = p1[0] - p0[0]
   dy = p1[1] - p0[1]
   ax = abs(dx)
   ay = abs(dy)
   t=0 if dx==0 and dy == 0 else dy/(ax+ay)
   if dx<0:
     t=2-t
   elif dy<0:
     t=4+t
   return t*90

def ccw(p0,p1,p2):
   """clockwise: <0, linear: =0, counter-clockwise: >0"""
   return (p1[0]-p0[0])*(p2[1]-p0[1]) - (p1[1]-p0[1])*(p2[0]-p0[0])

def chull(point_set):
   num = len(point_set)
   # get lowest point
   x,y = zip(*point_set)
   min_y = y.index(min(y))
   point_set[0], point_set[min_y] = point_set[min_y], point_set[0]
   # sort by angle
   point_set[1:] = sorted(point_set[1:],
     lambda i,j: cmp(theta(point_set[0],i),theta(point_set[0],j)))
   point_set.insert(0,point_set[-1])
   current = 2
   hull = point_set[0:2]
   for i in range(current, num+1):
     while ccw(point_set[current],point_set[current-1],
       point_set[i]) >= 0:
       hull.pop()
       current -= 1
     hull.append(point_set[current])
     current +=1
     point_set[current],point_set[i] = point_set[i],point_set[current]
   return hull


I've written a small plotter tool in Tkinter to visualize what chull does. The green circles mark extremal points. My implementation actually works but has problems when it doesn't get a set of points. If a point appears in the input data (list of tuples) more than once (especially min_y) the program breaks with a "IndexError: pop from empty list". I took theta from one of Sedgewicks books (Algorithms), note that this function doesn't return an euclidean angle.

While fooling around with Prolog I remembered the wonderful puzzle site of Angela and Otto Janko. They provide a huge collection of puzzles, riddles, sudokus and other stuff. Even though the page is in german it’s a wonderful resource to challenge your brain. I found a simple logic puzzle called “Die Bombe“, and of course I tried to disarm the bomb. With Prolog!

Here’s the riddle (translated) and my solution:

The bomb has 7 flip switches. To disarm the bomb you must put the switches in their correct position. And you got this inforamtions: the bomb detonates when:

1. if switch 3 is on plus 2 and 4 are off, boom!
2. if 1 and 4 off plus 7 is on, boom!
3. if 1, 3 and 4 are off, boom!
4. if 6 is off plus 2 and 3 are on, boom!
5. if 4 and 3 are on, boom!
6. if 6 is on and if, as long as 7 is on, 1 is on too, boom!
7. if 6 is on and, provided 7 is on, 1 is on too, boom!
8. if 1 and 5 are on plus 7 is off, boom!
9. if 3 is off plus 4 and 5 are on, boom!
10. if 1 and 7 are on, boom!
11. if 5 off and if, as long as 2 and 6 are on, 3 is on too, boom!
12. if 7 off plus 3 or 4 on, boom!
13. if switch 6 and 7 are in different positions, boom!
14. if switch 2, 3 and 5 are off, boom!
15. if switch 1 and 2 are on and switch 5 and 7 are off, boom!
16. if 6 and 7 are off, boom!

So we are looking for a binary 7-digit permutation. Transcoded to facts we see that none of the following combinations is allowed:

%     1 2 3 4 5 6 7
boom([_,0,1,0,_,_,_]).
boom([0,_,_,0,_,_,1]).
boom([0,_,0,0,_,_,_]).
boom([_,1,1,_,_,0,_]).
boom([_,_,1,1,_,_,_]).
boom([1,_,_,_,_,1,1]).
boom([1,_,_,_,1,_,0]).
boom([_,_,0,1,1,_,_]).
boom([1,_,_,_,_,_,1]).
boom([_,1,1,_,0,1,_]).
boom([_,_,1,1,_,_,0]).
boom([_,_,_,_,_,0,1]).
boom([_,_,_,_,_,1,0]).
boom([_,0,0,_,0,_,_]).
boom([1,1,_,_,0,_,0]).
boom([_,_,_,_,_,0,0]).


The first idea was to generate all possible permutations (with the command permutation/2) and compare them with the given facts. This gives proper solutions, but it is very slow. Here the according code:

% defuse([A,B,C,D,E,F,G]) :-
%     permutation([A,B,C,D,E,F,G,_,_,_,_,_,_,_],[0,0,0,0,0,0,0,1,1,1,1,1,1,1]),
%     not(boom([A,B,C,D,E,F,G])).

And here’s my optimized defuser:

defuse([A,B,C,D,E,F,G]) :-
per_bin([_,_,_,_,_,_,_],[A,B,C,D,E,F,G]),
not(boom([A,B,C,D,E,F,G])).
per_bin([],[]).
per_bin([X|Xs],[X|Ys]) :- member(X,[0,1]), per_bin(Xs,Ys).


Finally here’s the file. Note: my provider wont let you download .pl-files, so I renamed it. bomb.pl

When editing files with vim the length of your lines is only limited by your machine. Looking at the documentation a line can have a length of at least 32767 characters. But it’s annoying to read or edit files without reasonable set line breaks, so how can we limit the length of a line to a more useful amount of characters? With the command :set tw=72 you can set the text width to 72 chars for newly inserted text. This will not affect lines which already exist in your file, though. Every time your line reaches a length of 72 characters vim will insert automatically a new line.

To reformat already existing text in your files you can use gq, followed by a movement, for example the amount of lines you want to change. So if you want to reformat your whole file just press gggqG (gg jumps to the head of the file, G to the bottom). Another trick is to use visual mode, if you want to reformat only one paragraph (all lines between to blank lines) try the following: vipgq.

Joining two lines is easy too, just move the cursor to the proper line and hit J. Again you can combine this with visual mode (vipJ).