2011-03-27

# Using gnome keyring in xmonad

I stumbled across this problem when I decided to switch completely to this fantastic window manager called Xmonad.

I use SSH a lot and I also use Ubuntu’s cloud service(UbuntuOne). I use public key logins in most of the hosts I SSH into, so in order not to unlock my key each time I wanted to SSH or SCP to another host I used the GNOME keyring to store the unlocked key. And UbuntuOne uses the keyring to store the password to use to login to the service.

When I started using Xmonad I lost the keyring and I was becoming mad. So I started searching on how I could enable it in my Xmonad session. I couldn’t find a definite guide so I investigated a little bit of how the keyring worked and I’m explaining here what to do in order to have the gnome keyring start after the login and having it fully functional with the ssh.

First of all you need to change the file in /usr/share/xsessions/xmonad.desktop in order to execute a script of ours instead of the xmonad. It will look like this:

[Desktop Entry]
Encoding=UTF-8
Name=XMonad
Comment=Lightweight tiling window manager
Exec=xmonad.start
Icon=xmonad.png
Type=XSession

Now we are going to have the script (with executable privileges) somewhere in the path, a correct place to have it is /usr/local/bin. So a simple /usr/local/bin/xmonad.start script would be:

#!/bin/bash

#most basic xmodmap stuff
xmodmap -e 'remove Lock = Caps_Lock'
xmodmap -e 'keysym Caps_Lock = Control_L'
xmodmap -e 'add Control = Control_L'
xmodmap -e 'keycode 166 = Hyper_R'
xmodmap -e 'add mod5 = Hyper_R'

~/.xmonadrc

exec xmonad

Basically what this file does is mapping some keys and executing a script .xmonadrc in the home of the user. This is done in order to allow different users set different settings. In that script is where the magic will happen, but with that magic won’t be enough. Here’s what you have to include in that file in order to start the keyring. In my file I set up a trayer and launch some other programs.

eval $(gnome-keyring-daemon --start) export GNOME_KEYRING_SOCKET export GNOME_KEYRING_PID Those three commands will launch the keyring daemon and set up the environmental variables needed to make it work. This will work perfectly with the stored passwords but ssh’s keyring overrides this gnome keyring and the unlocking of the ssh key won’t work (don’t know why yet). In order to correct this it is necessary to update the .profile in the home of your user. You need to append the following line: export SSH_AUTH_SOCK="$GNOME_KEYRING_CONTROL/ssh"

With that the ssh will use the keyring daemon and we are ready to use it for everything. Just restart gdm or re-log into the user.

Hope it was useful.

2011-03-22

# Project Euler problem 329 - Solved

You can find the statement of this problem here.

The solution to this problem is really an easy one. It’s just straightforward dynamic programming.

The DP approach I used is top-down with memoization. The DP dictionary will be indexed by a 2-tuple of the starting cell and the string of the expected sequence. And it’s initialized for all the numbers for the strings ‘N’ and ‘P’.

The function which calculates the probability of a sequence from a determined cell first checks if it’s already in the DP dictionary, if it’s not there are three cases:

1. The cell is number 1: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 2.
2. The cell is number 500: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 499.
3. Rest of the cells: the probability of listening a sequence is: the probability of hearing the first letter of the string in that position multiplied by (p + q) where p stands for the probability of listening to the rest of the string from the previous cell divided by 2 (the probability of choosing the previous cell is 0.5) and q stands for the probability of listening to the rest of the string from the next cell divided by 2 (the probability of choosing the next cell is 0.5).

The result is the sum of the probability of listening to the sequence from each cell and then divided by 500. There’s a probability of 1/500 to start in each cell.

The python code is available problem329.py:

from CommonFunctions import find_primes_less_than
from fractions import Fraction

d = {}

primes = set(find_primes_less_than(501))
for i in range(1, 501):
if i in primes:
d[(i, 'P')] = Fraction(2, 3)
d[(i, 'N')] = Fraction(1, 3)
else:
d[(i, 'P')] = Fraction(1, 3)
d[(i, 'N')] = Fraction(2, 3)

def calc_prob(i, string):
if (i, string) in d:
return d[(i, string)]

if (i == 1):
prob = d[(i, string[0])] * calc_prob(i + 1, string[1:])
elif (i == 500):
prob = d[(i, string[0])] * calc_prob(i - 1, string[1:])
else:
prob = d[(i, string[0])] * (calc_prob(i + 1, string[1:]) * Fraction(1, 2) + calc_prob(i - 1, string[1:]) * Fraction(1, 2))

d[(i, string)] = prob
return prob

if __name__ == '__main__':
result = Fraction(0, 1)
for i in range(1, 501):
result += calc_prob(i, 'PPPPNNPPPNPPNPN')
print("The result is:", result / 500)
2011-03-17

# Project Euler problem 186 - Solved

The statement for this problem can be found here.

The solution of this problem is quite straightforward. I will use a list which will hold sets, each of them will represent the nodes in a connected graph.

First of all a generator is needed in order to produce the caller and receiver of each phone call. For that I use a generator function implemented with the yield instruction.

The next thing to keep in mind is that once you know the caller and receiver, how can you efficiently find in which connected graphs are they in. To accomplish this, the set’s list will hold for position i the set where i is in or the position where it was moved to. If a number was moved several times you need to follow the chain of indexes until you find a set.

Having mentioned the two key techniques used it is easy to code the program that solves the problem. “While the connected graph that the president is in is less than 990000(99%): get the next phone call, find the graphs of each of the participants, if they differ then join both sets in one and in the other’s position set the corresponding reference.”

The python code is problem186.py:

from collections import deque

def generator():
queue_55 = deque()
queue_24 = deque()
for k in range(1, 56):
s_k = (100003 - 200003 * k + 300007 * (k ** 3)) % 1000000
queue_55.append(s_k)
if k >= 32:
queue_24.append(s_k)
yield s_k
while True:
s_k = (queue_55.popleft() + queue_24.popleft()) % 1000000
queue_55.append(s_k)
queue_24.append(s_k)
yield s_k

graph_list = [set([i]) for i in range(1000000)]

def get_pos_of(i):
while isinstance(graph_list[i], int):
i = graph_list[i]
return i

if __name__ == '__main__':
gen = generator()
res = 0
while len(graph_list[get_pos_of(524287)]) < 990000:
c1 = next(gen)
c2 = next(gen)
if c1 == c2:
continue
res += 1
i1 = get_pos_of(c1)
i2 = get_pos_of(c2)
if i1 != i2:
to_put_into = min(i1, i2)
to_remove = max(i1, i2)
graph_list[to_put_into] |= (graph_list[to_remove])
graph_list[to_remove] = to_put_into
print("The result is:", res)