Skip navigation

Just recently I had to compare different ways of copying a large file. I could have used the clock/clock_gettime C functions from time.h, but I decided to keep the code clean and make the time measurement external from the program.

#!/bin/bash

ITERATIONS=10
SLEEP=5
TIMES_FILE="times"

for iter in `seq 1 $ITERATIONS`
do
sleep $SLEEP
/usr/bin/time -o $TIMES_FILE -a -p $@
done

echo $(cat $TIMES_FILE | grep real | awk '{print $2}' | awk '{t+=$1} END {print t/NR}')
rm $TIMES_FILE

If you’re wondering why there’s a sleep there is just because you might want to wait for the next iteration to begin (In my case I wanted to give time to the sync daemon to run).I wish I was better at awk as I’m sure there’s a way to save a few pipes there but as I said, it’s just quick and dirty.

Advertisements

This was my solution:

import Data.List
p1 = [‘q’,’z’,’ ‘,’e’,’j’,’p’,’m’,’y’,’s’,’l’,’j’,’y’,’l’,’c’,’k’,’d’,’k’,’x’,’v’,’e’,’d’,’d’,’k’,’n’,’m’,’c’,’r’,’e’,’j’,’s’,’i’,’c’,’p’,’d’,’r’,’y’,’s’,’i’,’r’,’b’,’c’,’p’,’c’,’y’,’p’,’c’,’r’,’t’,’c’,’s’,’r’,’a’,’d’,’k’,’h’,’w’,’y’,’f’,’r’,’e’,’p’,’k’,’y’,’m’,’v’,’e’,’d’,’d’,’k’,’n’,’k’,’m’,’k’,’r’,’k’,’c’,’d’,’d’,’e’,’k’,’r’,’k’,’d’,’e’,’o’,’y’,’a’,’k’,’w’,’a’,’e’,’j’,’t’,’y’,’s’,’r’,’r’,’e’,’u’,’j’,’d’,’r’,’l’,’k’,’g’,’c’,’j’,’v’]

p2 = [‘z’,’q’,’ ‘,’o’,’u’,’r’,’l’,’a’,’n’,’g’,’u’,’a’,’g’,’e’,’i’,’s’,’i’,’m’,’p’,’o’,’s’,’s’,’i’,’b’,’l’,’e’,’t’,’o’,’u’,’n’,’d’,’e’,’r’,’s’,’t’,’a’,’n’,’d’,’t’,’h’,’e’,’r’,’e’,’a’,’r’,’e’,’t’,’w’,’e’,’n’,’t’,’y’,’s’,’i’,’x’,’f’,’a’,’c’,’t’,’o’,’r’,’i’,’a’,’l’,’p’,’o’,’s’,’s’,’i’,’b’,’i’,’l’,’i’,’t’,’i’,’e’,’s’,’s’,’o’,’i’,’t’,’i’,’s’,’o’,’k’,’a’,’y’,’i’,’f’,’y’,’o’,’u’,’w’,’a’,’n’,’t’,’t’,’o’,’j’,’u’,’s’,’t’,’g’,’i’,’v’,’e’,’u’,’p’]

addCases :: [String] -> [String]
addCases strings = zipWith addCase strings [1..]
where
addCase st n = “Case #” ++ (show n) ++ “: ” ++ st ++ “\n”

parseInput :: String -> IO [String]
parseInput name = (readFile name) >>= (\x -> return (drop 1 $ lines x))

translation = zip p1 p2

translate x = take 1 [y | (r,y) <- translation, r ==x]

translateLine line = concat $ map translate line
main = do
input <- parseInput “in.in”
let translated = map translateLine input
let output = addCases translated
writeFile “out.out” (concat output)

A feature I miss from Gnome 2 is the ability to control the network proxy with ease. In order to change the proxy in Gnome3 one has to open the control center, go to the Network section, and click on the Network Proxy button. This doesn’t disturb me much, but the fact that I don’t have access to the proxy settings directly from Gnome shell is a bit irritating. Not only it is tedious but you cannot have a widget placed on your bar like you used to in Gnome 2.

gnome control centergnome proxy settings

If you want to make a key binding to open the network settings, all you have to do is bind it to run gnome-control-center network and the network settings menu will pop-out when needed but I’m willing to go further:

The NetworkManager daemon executes scripts located under /etc/NetworkManager/dispatcher.d/ every time there’s a connection or a disconnection on one of the interfaces.

I wrote a small script that switches the proxy on/off depending on the name of the network:

#!/bin/bash

#######Parameters to customize##########

my_interface="wlan0"
proxy_network="foo"
desired_proxy="proxy.bar.net"
desired_port="3128"
username="bob"

########################################

function gsettings_change {
    userid=`id -u $username`
    sudo -u $username env $(strings /proc/$(pgrep -U $userid gnome-session | head -n 1)/environ | grep DBUS) gsettings set org.gnome.system.proxy$1
}

function change_proxy {
    if [ $1 = "on" ]
    then
        gsettings_change ".http host $desired_proxy"
        gsettings_change ".http port $desired_port"
        gsettings_change " mode 'manual'"
    else
        gsettings_change " mode 'none'"
    fi
}

if [ $2 = "up" -a $1 = $my_interface ] #interface is up
then
    network_name=`/usr/bin/nm-tool | /bin/grep \* | /usr/bin/tail -n 1 | /usr/bin/awk '{print $1}' | /bin/sed 's/^\*\([a-zA-Z_0-9\-]*\).*/\1/g'`

    if [ $network_name = $proxy_network ]
    then
        change_proxy "on" $desired_proxy $desired_port
    else
        change_proxy "off"
    fi
fi

In order to change the gnome proxy we use the gsettings set org.gnome.system.proxy command, but the changes made are only applied to the user that runs the command, NetworkManager runs as root and therefore we have to sudo -u to the user we want to change the proxy to. Because the gsettings uses the DBUS_SESSION_BUS_ADDRESS env variable, we have to extract it from  /proc/$(pgrep -U $userid gnome-session | head -n 1)/environ and for that reason the user must also be logged on when the connection is established. I hope NetworkManager  to feature automatic proxy profile management in the future, until then we’ll just have to keep hacking.

Vim logoI still consider myself a novice when it comes to using Vim. Until now, every time I wanted to use syntax highlighting I had to append an extension (depending on the syntax) to the name of the file, but this is rather tedious specially when you first open Vim without specifying the file you’ll create. I asked the folks at #vim and they told me I could use :set syntax=<NAME> where <NAME> is the type of syntax I want to use:

Vim with no syntax set

and then:
Vim with c++ syntax set

When we have syntax on on our .vimrc file , we let Vim guess the syntax mode that we need depending on the file. But what if the file has an extension that is used by another programming language? Let’s show the example of Prolog and Perl. They both use .pl extensions but let’s say that we work mostly with prolog files. If syntax on is set, Vim will use perl highlighting when we open an empty prolog file, in order to avoid this we have can use the autocmd command as follows:

autocmd Filetype pl set syntax=prolog

This will make sure that everytime we open a .pl file vim uses the prolog highlighting instead of perl.

A few posts ago I designed a very simple yet slow algorithm to find prime numbers based on a direct implementation  of their definition. Today I’m going to use the sieve of Eratosthenes to accomplish the same task.

So basically the algorithm for finding prime numbers using this approach is to write the numbers from 2 to X on a table, we then start by crossing out all multiples of 2 (because 2 is the first number on the list) by doing so we rule-out numbers that are not primes because they are multiples of something. When we’re done, we iterate the whole process over the next available number (a number that has not been crossed out), when we run out of available numbers we can assure that the numbers that were left are prime numbers.

How do we implement this? let’s look back at the algorithm. An iteration of the sieve is to look for the first number of the table and eliminate multiples of this number, so given a list of numbers, we have to create a function that returns the numbers that are not multiples of the first element of the list:

sieve :: [Int] -> [Int]
sieve (x:xs) = [ r | r <- xs, mod r x /= 0 ]

That was very straightforward, but we’re not done yet. This function returns a list of numbers that are candidates of being prime numbers, so in order to find the rest we have to “pass on” the remaining numbers to the function again thus creating the next iteration.

Let’s do this step by step. Let’s say we want to find the prime numbers up to 20. We first rule-out numbers that are multiples of 2 and because we’re starting with 2 we know that 2 is a prime number. Now we have a list of numbers that we know might be prime numbers: [3,5,7,9,11,13,15,17,19], we pass this list to the function again so we know that 3 is prime (because it was the first one of the list) and [5,7,11,13,17,19] is what was left. We take 5 as the next prime number and iterate again and again..

So what we’re actually doing is: given a list (x:xs) we take the first element of the list (x) and apply sieve over the list, then apply sieve over sieve (list).. (x,sieve(x),sieve(sieve(x)…) There’s a function that comes with haskell called iterate that does exactly that:

iterate f x == [x, f x, f (f x), …]

so iterate sieve [2..] will actually return all the sieves from all the iterations, but where are the prime numbers? The prime numbers will be the first element of all the sieves:

primes = map head (iterate sieve [2..])

And we’re done!

You’ve probably heard of this puzzle before. A farmer went to the market and bought a fox, a goose, and a bag of beans, on his way home he realizes that he has to cross a river, there’s a boat that can take him from one side to the other, but there’s a problem: The boat is only big enough for him and one of his belongings, How can the farmer cross the river knowing that he cannot leave the fox and the goose alone (because the fox will eat the goose) nor the goose and the bag of beans (because the goose will eat the beans)?

This is just one of many river-crossing puzzles, and they can all be solved using a very similar approach to what I’m going to show you:

First, let’s define the state of the puzzle at anytime:
st([Farmer, Fox, Goose, Beans])
where Farmer Fox Goose and Beans are variables that can take values of “left” or “right” whether that element is on the left or right side of the river.

Let’s tell Prolog what our initial and final states are:

initial(st([left, left, left, left])).

final(st([right, right, right, right])).

Solving these kind of puzzles is a matter of finding a node in a graph where each state of our puzzle is a node and the line between a node and another node is determined by a transition rule. The transition rule is nothing but a function that given a certain state will return a possible “next” state, say for example our initial state is st([left, left, left, left]), a valid next state could be st([right, left, right, left]) which means the farmer took the goose and crossed the river.

We define the transition rules as follows:

crossing(st([left,X,Y,Z]),st([right,X,Y,Z]), farmer_crosses_river).
crossing(st([right,X,Y,Z]),st([left,X,Y,Z]), farmer_comes_back).

crossing(st([left,X,left,Z]),st([right,X,right,Z]), bring_goose_over).
crossing(st([right,X,right,Z]),st([left,X,left,Z]), bring_goose_back).

crossing(st([left, left, X, Y]),st([right, right, X, Y]), bring_fox_over).
crossing(st([right, right, X, Y]),st([left, left, X, Y]), bring_fox_back).

crossing(st([left, X, Y, left]),st([right, X, Y, right]), bring_beans_over).
crossing(st([right, X, Y, right]),st([left, X, Y, left]), bring_beans_back).

The rules are pretty self-explanatory, crossing st([left,X,Y,Z]),st([right,X,Y,Z] means “farmer_crosses_river”, as you can see, the farmer variable changed from left to right and the rest was left intact.

Now, all those transitions are valid but we are tied down to certain restrictions, for example, the farmer can’t leave everything on one side or they will eat each other. For that reason we have to create a rule “not_allowed” that will be true whenever a state we transitioned to is illegal do to the circumstances of the puzzle. I mentioned earlier that crossing will match all possible states where we can move to, but after generating it we will use “not_allowed” to check if the state is legal.

not_allowed(st([X, Y, Y, _])) :- X \== Y.

not_allowed(st([X, _, Y, Y])) :- X \== Y.

Basically, the state that represents that the farmer is on one side and both the fox and the goose on the other is not allowed. Same for the goose and the bag of beans.

Now we have almost everything we need to solve the puzzle, we define the rule river(P) where P is a list of crossings,

river(P) :-
initial(Start), final(End),
river_aux(Start, End, [Start], P).

river_aux(A,B,V,P) is a rule that will be true when you can go to A from B by the crossings defined by P. V is the list of previously visited nodes on the graph, if we didn’t have V we would loop through the graph infinitely. To summarize, river_aux looks for a node in a graph, leaving from A, and after P transitions ends in B.

river_aux(A,A,_,[]). % To go from A to A the crossing is empty meaning that we do not cross at all, this will be true when we reach our destination.

river_aux(A,B,V,P) :-
crossing(A,C,Action),
not(not_allowed(C)),
not(member(C,V)),
river_aux(C,B,[C|V],Plan),
P = [Action | Plan].

As I mentioned earlier, crossing will try to match a node in the graph where we can go to from A called C by doing a certain crossing “Action”, later we check whether C is allowed, if it is we check that it has not been visited before by using “member” (to avoid loops), finally, we go from C to our final destination, adding C to the list of previously visited nodes and making P the previous actions plus the recent one.

We finally ask Prolog to look for a path from the initial state to the final one.

?- river(P).
P = [bring_goose_over, farmer_comes_back, bring_fox_over, bring_goose_back, bring_beans_over, farmer_comes_back, bring_goose_over] ;
P = [bring_goose_over, farmer_comes_back, bring_beans_over, bring_goose_back, bring_fox_over, farmer_comes_back, bring_goose_over] ;
false.

A friend from class just recently mentioned something about a binary to decimal converter, I didn’t find it hard at all but I wanted to use function composition and ended up with something like this:

bintodec :: [Int] -> Int

bintodec = ((sum . map (\(a,b) -> a*b)) . zip (iterate (*2) 1))

where the input is a list of 1 and 0 for example:

*Main> bintodec [1,1,0,1]

11

I know this can be done in many other ways, but it was the first thing that came to my mind =)

I was wondering how beautiful prime number generation would be in Haskell so I gave it a shot.

First I define what the divisors of a number are:

divisors :: Integer -> [Integer]

divisors 1 = [1]

divisors x = 1:[ y | y <- [2..(x `div` 2)], x `mod` y == 0] ++ [x]

Since 1 and x are always divisors of x I append them to the list comprehension that checks for divisors from 2 to (x `div` 2). Why x `div` 2 and not [2..x]? Well no divisor of a number will ever be larger than half of the number, so I can save some cpu there.

*Main> divisors 15
[1,3,5,15]

*Main> divisors 16
[1,2,4,8,16]

*Main> divisors 17
[1,17]

Seems to be working fine, now how do we know if a given number is prime?

prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.  -Wikipedia

Hmm, so x is prime if divisors x == [1,x]

isPrime :: Integer -> Bool

isPrime x = divisors x == [1,x]

*Main> isPrime 10
False

*Main> isPrime 11
True

We can now define our prime number generator as:

primeNums :: [Integer]

primeNums = [ x | x <- [2..], isPrime x]

*Main> primeNums

[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,…

Probably not the fastest prime number generator, but it should do the trick.