Numeros Primos

En una materia de mi carrera Lic. Informática, mi docente nos dio de tarea(reto) calcular los números primos que se encuentran en el rango de mil millones números (100.000.000.000) y generarlo en un archivo.

Cualquiera dirá hallar el numero primo es fácil, si es verdad de echo ya hay algoritmos que te calculan los números primos, pero para un rango de mil millones la cosa se complica.

El reto esta en generarlo en el menor tiempo posible en el lenguaje funcional Haskell.

Mi docente me explico un poco como funciona la criba de Erastotenes, entonces decidí aplicar ese algoritmo para generar los números primos.

Este es mi primer intento para 10 millones de números:

	{-======================================================================================
	Autor : to_On1
	Email : antonio.mq@gmail.com
	Versión : 0.1
	Descripción : Aplicación del algoritmos de Erastotenes
	=======================================================================================-}
	main :: IO()
	main = writeFile "primosErastotenes" $ unlines $ erastotenes [2..10000000]
	erastotenes :: [Integer] -> [String]
	erastotenes [] = []
	erastotenes (x:xs) | x^2 > last xs = show x : map show xs
	| otherwise = show x : erastotenes (filter (\ y -> y `mod` x/= 0 ) xs)

view raw gistfile1.hs hosted with ❤ by GitHub

Y obtuve los siguientes resultados

$ time ./Primes

real 1m8.407s
user 1m5.015s
sys 0m0.815s

Con mi código, de entrada no podre superar el reto, entonces me puse a analizar por que tardaba tanto y como podía mejorarlo.

Pude hacer la siguiente mejora para mil millones de números:

	{-==================================================================================
	Autor : to_On1
	Email : antonio.mq@gmail.com
	Version : 0.2
	Descripcion : Este algoritmo (mejorado) es una modificacion del algoritmo de
	Erastotenes,donde armo una lista discriminando los números
	multiplos de 2,3,..47, esto reduce a menos de la mitad la lista que sera
	evaluada.
	===================================================================================-}
	main :: IO()
	main = writeFile "primes" $ unlines $ res ++ (primos $ lista 53)
	where
	res = "2":"3":"5":"7":"11":"13":"17":"19":"23":"29":"31":"37":"41":"43":"47":[]
	-- Creo la lista donde mi valor final sera 999999999 esto es devido a que
	-- mil millones es numero par
	lista :: Integer -> [Integer]
	lista 999999999 = []
	lista x | x `mod` 3 == 0 = lista $ x+2
	| x `mod` 5 == 0 = lista $ x+2
	| x `mod` 7 == 0 = lista $ x+2
	| x `mod` 11 == 0 = lista $ x+2
	| x `mod` 13 == 0 = lista $ x+2
	| x `mod` 17 == 0 = lista $ x+2
	| x `mod` 19 == 0 = lista $ x+2
	| x `mod` 23 == 0 = lista $ x+2
	| x `mod` 29 == 0 = lista $ x+2
	| x `mod` 31 == 0 = lista $ x+2
	| x `mod` 37 == 0 = lista $ x+2
	| x `mod` 41 == 0 = lista $ x+2
	| x `mod` 43 == 0 = lista $ x+2
	| x `mod` 47 == 0 = lista $ x+2
	| otherwise = x : lista (x+2)
	primos :: [Integer] -> [String]
	primos [] = []
	primos (x:xs) | x < floor (sqrt 1000000000)+1 = show x : map show xs
	| otherwise = show x : primos (filter (\ y -> y `mod` x /= 0) xs )

view raw gistfile1.hs hosted with ❤ by GitHub

$time ./Primos
real 4m59.920s
user 4m40.015s
sys 0m6.015s


Si hacemos una comparación con mi primera versión, logre mejorar bastante ya que para el primero solo calculo para diez millones y para el segundo calculo para mil millones números.

Haciendo cálculos matemáticos 100 * 5 (redondeado al tiempo que tardo para mil millones) = 500 minutos y lo dividimos en 60 minutos, nos dará el siguiente resultado 500/60 = 8.33.

Esto quiere decir que para calcular el rango de mil millones de números tardara 8 horas con 33 minutos.

Criptografia

En los entrenamientos para el concurso de la ACM_ICPC realizado en la UMSS, propuse el siguiente problema.

Description

El gente to_O1 estuvo investigando por mucho tiempo a una banda de "Hackers" que opera en la ciudad de Cochabamba. En su investigación pudo interceptar varios mensajes cifrados que se enviaban entre " Hackes"; después de hacer un análisis a todos los mensajes interceptados descubrió que cada palabra tiene una llave que lo cifra. to_On1 elaboro un algoritmo que pueda descifrar los mensajes cifrados. pero lamentablemente en un accidente aéreo el agente to_On1 falleció y con el su portátil donde tenia toda la información de como descifrar los mensajes.

Ahora usted formara parte de nuestro equipo de investigación y como su primera tarea sera elaborar un algoritmo que pueda descifrar los mensajes, gracias al agente to_On1 tenemos todas las llaves que utilizan los "Hackers" para poder descifrar los mensajes.

Esperemos que este ejemplo le ayuden a elaborar el algoritmo descifrador

Encrypted message : ahac qvkzayo mj klcmbi
Kay word : hackers
Decoded message : this message is secure

INPUT

La entrada consiste en N casos (1<= N <=10000). La primera linea solo contiene un numero entero positivo N. A continuación siguen los casos. La primera linea de cada coso contiene dos números enteros M y K (1 <= M ,K <= 10000) separados por un espacio. M determina la cantidad de palabras que tiene el mensaje cifrado, K determina la cantidad de llaves para descifrar el mensaje. OUPUT

Por cada caso hay que imprimir el mensaje descifrado.

Input

3
5 5
rvcu if acm d qgjqpzm
you can not decrypt it
4 4
wco eaa acm uacs
you can not know
5 2
fwqf # yxtjaf zd (591-123?u24)?
hi world


Ouput

this is not a message
you can not know
your # number is (591-123?m24)?

Solution

La solución es muy sencilla solo hay que agarrar cada dígito del mensaje y de las palabras llave y aplicar el Cifrado de Vigenere de forma invertida con todos los dígitos, en caso de que las palabras llave tenga menos dígitos que el mensaje, entonces se vuelve a utilizar las palabras llave hasta terminar de descifrar todo los dígitos del mensaje.

A continuación una solución en Haskell

	{-
	Author : to_On1
	Porblem : Criptography
	Version : 100711
	-}
	main :: IO()
	main = mapM_ putStrLn . decode . lines =<< getContents
	decode :: [String] -> [String]
	decode (x:xs) = des xs
	where
	des :: [String] -> [String]
	des [] = []
	des (x:y:z:zs) = let kay = concat $ words z
	in (desifrar y kay kay): des zs
	desifrar :: String -> String -> String -> String
	desifrar [] _ _ = ""
	desifrar (x:xs) (y:ys) zs | x == ' ' = ' ' : desifrar xs (y:ys) zs
	| es x = let num1 = snd $ head $ filter (\ z -> fst z == x ) letras
	num2 = snd $ head $ filter (\ z -> fst z == y ) letras
	resta = num1 - (num2-1)
	res = if ys == [] then zs else ys
	in if resta <= 0 then
	(fst $ head $ filter (\w-> snd w == 26+resta)letras):desifrar xs res zs
	else
	(fst $ head $ filter (\w-> snd w == resta) letras) : desifrar xs res zs
	| otherwise = let res = if ys == [] then zs else ys
	in x : desifrar xs res zs
	where
	es e = elem e ['a'..'z']
	--letras :: [(Char,Int)]
	letras = [('a',1),('b',2),('c',3),('d',4),('e',5),('f',6),('g',7),('h',8),('i',9),('j',10),
	('k',11),('l',12),('m',13),('n',14),('o',15),('p',16),('q',17),('r',18),('s',19),
	('t',20),('u',21),('v',22),('w',23),('x',24),('y',25),('z',26)
	]

view raw gistfile1.hs hosted with ❤ by GitHub

Cofigurar Xmonad en Gnome - Ubuntu

En un post anterior explique como configurar xmonad como gestor de escritorio por defecto. Ahora explicare como configurar Xmonad en Gnome, para lo cual hay que seguir los siguientes pasos: Abrimos una terminal y instalamos el xmonad

$ sudo aptitude install xmonad

Aptitude se encarga automáticamente de todas las dependencias. Luego debemos crear y modificar el archivo de configuración.

$ mkdir ~/.xmonad && touch ~/.xmonad/xmonad.hs

Abrimos el archivo xmonad.hs

$ gedit ~/.xmonad/xmonad.hs

y copiamos las siguientes lineas de código

import XMonad
import XMonad.Config.Gnome

main = xmonad gnomeConfig

Ahora debemos recompilar el archivo xmonad.hs con el siguiente comando

$ xmonad --recompile

Ahora tenemos que activarlo nuestra configuración de nuestro xmonad, para lo cual tenemos que avisarle a gnome que utilice xmonad como decorador de ventanas en lugar de gnome-wm. Tenemos dos opciones uno configurar por consola otro visualmente. Por consola:

$ gconftool-2 -s /desktop/gnome/session/required_components/windowmanager xmonad --type string

Forma gráfica:

ejecutamos por la consola la siguiente aplicación

$ gconf-editor

vamos abriendo las pestañas desktop, gnome, session y requiered_components, ahora debemos hacer clic derecho en windowmanager, elegir “Editar clave" allí escribir xmonad en lugar de gnome-wm ahora reiniciamos nuestro sistema o cerramos sesión y volvemos a entrar, ahora podremos disfrutar de nuestro xmonad :)

Roman Calculator

Utilizando mi algoritmo para convertir un numero entero es un numero romano; encontré un problema en el juez virtual Spoj donde aplicar mi algoritmo.
El ejercicio es Roman Calculator, donde se tiene que hacer operaciones matemáticas con números romanos. Los datos de entrada y salida seria de la siguiente manera

Input:
6
II + III
II - III
II * III
VI : III
V % III
I - I
Output:
V
-I
VI
II
II
ERROR

Este seria mi solución para Roman Calculator

	{--
	Author : to_On1
	Problem : Roman Calculator
	url Problem : http://www.spoj.pl/SHORTEN/problems/ROMANCAL/
	--}
	main :: IO()
	main = mapM_ putStrLn . calculator . lines =<< getContents
	calculator :: [String] -> [String]
	calculator (x:xs) = map (\ y -> result (words y) ) xs
	result :: [String] -> String
	result (x:y:z:xs) = case y of
	"+" -> convert ((aNum x roma) + (aNum z roma))
	"-" -> let num = ((aNum x roma) - (aNum z roma))
	in if num < 0 then "-"++convert (-1 * num)
	else convert num
	"*" -> convert ((aNum x roma) * (aNum z roma))
	":" -> convert (div (aNum x roma) (aNum z roma))
	"%" -> convert (mod (aNum x roma) (aNum z roma))
	roma =[("M",1000),("CM",900),("D",500),("CD",400),("C",100),("XC",90),("L",50),("XL",40),
	("X",10),("IX",9),("V",5),("IV",4),("I",1)]
	aNum :: String -> [(String,Integer)] -> Integer
	aNum "" _ = 0
	aNum (x:xs) ys | length xs > 0 = if filter (\ z -> fst z == (x:(head xs):[])) ys == []
	then ( snd ( (filter (\ z -> fst z == x:[] ) ys) !! 0)) + aNum xs ys
	else (snd ((filter (\ z -> fst z == (x:(head xs):[])) ys)!! 0)) + aNum (tail xs) ys
	| otherwise = (snd (filter (\ z -> fst z == x:[]) ys !! 0)) + aNum xs ys
	convert :: Integer -> String
	convert num | num > 0 = roman 0 num
	| otherwise = "ERROR"
	where
	roman _ 0 = ""
	roman p n | n >= snd (roma !! p) = fst (roma !! p) ++ roman p (n - snd(roma!!p))
	| otherwise = roman (p+1) n

view raw gistfile1.hsc hosted with ❤ by GitHub

Convertir un Entero en un Número Romano

A modo de entrenar mis habilidades de programación en haskell decidí hacer un algoritmo que me convierta un numero entero que este entre 1 y 3999 a su equivalente número romano

	{--
	- Author : Antonio Mamani
	- Description : Convert integer to roman numerical
	- version : 26022010
	--}
	entero = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	romano = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
	convert :: Int -> String
	convert num | num > 0 && num < 4000 = roman 0 num
	| otherwise = "Número fuera de rango"
	where
	roman _ 0 = ""
	roman p n | n >= entero !! p = romano !! p ++ roman p (n-entero!!p)
	| otherwise = roman (p+1) n

view raw gistfile1.hs hosted with ❤ by GitHub

Personalizar xmonad

Con la ayuda de amigo Carlos pude configurar mi xmonad de la siguiente manera,


Con la explicación que are a continuación uno podrá modificar a placer su xmonad.


Para ello hay que tener instalado xmonad . el siguiente paso es instalar xmobar lo puedes descargar de su pagina oficial o si tienes instalado darcs ejecuta el siguiente comando.

darcs get http://darcs.complete.org/xmobar

ahora hay que configurar ciertos archivos para poder agregar programas que se inicien por defecto, control de volumen, red , batería, etc.

Pasos:

1. crear el archivo .xmobarrc

touch ~/.xmobarrc

2. abrimos el archivo creado y copiamos los siguientes codigos

Config { font = "-*-Fixed-Bold-R-Normal-*-13-*-*-*-*-*-*-*"
, bgColor = "black"
, fgColor = "grey"
, position = TopW L 85
, lowerOnStart = True
, commands = [ Run Network "eth0" ["-L","0","-H","32","--normal","green","--high","red"] 10
, Run Network "wlan0" ["-L","0","-H","32","--normal","green","--high","red"] 10
, Run Weather "EGPF" ["-t"," F","-L","64","-H","77","--normal","green","--high","red","--low","lightblue"] 36000
, Run Cpu ["-L","3","-H","50","--normal","green","--high","red"] 10
, Run Memory ["-t","Mem: %"] 10
, Run Swap [] 10
, Run Date "%a %b %_d %Y %H:%M:%S" "date" 10
, Run StdinReader
, Run Com "df" ["-h | grep /dev/sda2 | awk '{print $5}'"] "disk1" 60
, Run Com "df" ["-h | grep /dev/sda3 | awk '{print $5}'"] "disk2" 60
, Run Battery ["-L", "50", "-H", "75", "--high", "green", "--normal", "yellow", "--low", "red"] 10
]
, sepChar = "%"
, alignSep = "}{"
, template = "%StdinReader% }{ %cpu% | %memory% %swap% | Battery: %battery% | HD1: %disk1% | HD2: %disk2% | %date%"
}

Todo este código es configurable de acuerdo a lo que quieres que aparezca en el xmobar para mayor información puedes ver la pagina oficial de xmobar.

3. hora nos creamos los siguientes archivos si es que no los tenemos creados


touch /usr/share/xsessions/xmonad.start


touch /usr/share/xsessions/xmonad.desktop

4. abrimos el archivo xmonad.start y copiamos el siguiente código


#!/bin/bash

xrdb -merge .Xresources

trayer --edge top --align right --SetDockType true --SetPartialStrut true --expand true --width 15 --height 12 --transparent true --tint 0x000000 &

gnome-screensaver

gnome-settings-daemon

if [ -x /usr/bin/gnome-power-manager ] ; then
sleep 1
gnome-power-manager
fi

if [ -x /usr/bin/nm-applet ] ; then
nm-applet --sm-disable &
fi

kmix --keepvisibility

feh --bg-scale /home/usuario/Imágenes/geek.jpg &

exec xmonad


En este archivo lo que hacemos es poder colocar la imagen que queramos en el fondo de escritorio, también que estén activos el medidor de la batería, configuración de la red, control de volumen, también podemos agregar programas que queremos que se inicialices eso depende de cada uno.

Para que todo esto funcione tenemos que instalar los siguientes programas

sudo apt-get install feh kmix trayer

5. el siguiente paso es llamar a este archivo xmodan.start, para ello abrimos el archivo xmonad.desktop y copiamos las siguientes lineas

[Desktop Entry]
Encoding=UTF-8
Name=XMonadAntonio
Comment=Leightweight tiling window manager
Exec=/usr/share/xsessions/xmonad.start
Icon=xmonad.png
Type=XSession


6. por ultimo creamos el siguiente archivo xmonad.hs en caso que no exista dentro el directorio .xmonad

mkdir ~/.xmonad


cd .xmonad

touch xmonad.hs

7. abrimos el archivo xmonad.hs y copiamos el siguiente código haskell


import XMonad
import XMonad.Hooks.DynamicLog
import XMonad.Hooks.ManageDocks
import XMonad.Util.Run(spawnPipe)
import XMonad.Util.EZConfig(additionalKeys)
import System.IO

myManageHook = composeAll
[ className =? "Gimp"      --> doFloat
, className =? "Vncviewer" --> doFloat
--    , className =? "Pidgin"    --> doFloat
]

main = do
xmproc <- spawnPipe "xmobar /home/usurio/.xmobarrc" xmonad $ defaultConfig { manageHook = manageDocks <+> myManageHook
                   <+> manageHook defaultConfig
, layoutHook = avoidStruts  $  layoutHook defaultConfig
, logHook = dynamicLogWithPP $ xmobarPP
        { ppOutput = hPutStrLn xmproc
        , ppTitle = xmobarColor "green" "" . shorten 50
        }
, modMask = mod4Mask     -- Rebind Mod to the Windows key
} `additionalKeys`
[ ((controlMask, xK_Print), spawn "sleep 0.2; scrot -s")
, ((0, xK_Print), spawn "scrot")
]

Listo, no se olvide cambiar los directorios por la de usted para que funcione, ahora serramos sesión y escogemos la sesión XmonadAntonio y listo ya puedes disfrutar del xmonad :)

Instalar GHC, Cabal y WXHaskell en Ubuntu

Instalación de GHC 6.10.1, Cabal y WXHaskell en Ubuntu 

Pasos:

1. Instalar los siguientes paquetes.

 sudo apt-get install build-essential libglut3-dev libglitz-glx1-dev zlib1g-dev libwxgtk2.8-dev libgmp3-dev

2. Creamos un directorio donde descargaremos los binarios de ghc

cd ~
mkdir ghc
cd ghc

3. Descargamos los binarios de ghc release (6.10.1)
## Download the appropriate BINAIRY ghc release (6.10.1)

# Para sistemas de 32-bit
wget http://haskell.org/ghc/dist/6.10.1/ghc-6.10.1-i386-unknown-linux-libedit2.tar.bz2

#Para sistemas de 64-bit
wget http://haskell.org/ghc/dist/6.10.1/ghc-6.10.1-x86_64-unknown-linux-libedit2.tar.bz2

4. Descargamos el codigo fuente de cabal y sus dependencias

wget http://hackage.haskell.org/packages/archive/zlib/0.5.0.0/zlib-0.5.0.0.tar.gz
wget http://hackage.haskell.org/packages/archive/HTTP/4000.0.5/HTTP-4000.0.5.tar.gz
wget http://hackage.haskell.org/packages/archive/cabal-install/0.6.2/cabal-install-0.6.2.tar.gz

5. Descomprimimos los archivos que acabamos de descargar

tar -xzf zlib-0.5.0.0.tar.gz
tar -xzf HTTP-4000.0.5.tar.gz
tar -xzf cabal-install-0.6.2.tar.gz


6. ahora instalamos cada uno de los paquetes

6.1 nos vamos a donde esta los binarios de ghc y ejecutamos los siguientes comandos

./configure
sudo make install


6.2 Instalamos el paquete zlib y ejecutamos los siguientes comandos

cd zlib-0.5.0.0
runhaskell Setup configure
runhaskell Setup build
sudo runhaskell Setup install
cd ..

6.3 Instalamos el paquete HTTP

cd HTTP-4000.0.5
runhaskell Setup configure
runhaskell Setup build
sudo runhaskell Setup install
cd ..

6.4 Instalamos el paquete cabal-install

cd cabal-install-0.6.2
runhaskell Setup configure
runhaskell Setup build
sudo runhaskell Setup install
cd ..

7. ahora ya tenemos compilado cabal-install, para probar ejecutamos los siguientes comandos

~/.cabal/bin/cabal update
~/.cabal/bin/cabal list

8. Si estos 2 comandos funcionan, copiamos en el directorio del sistema

sudo cp ~/.cabal/bin/cabal /usr/local/bin/

9. Intalamos wxcore y wx

sudo cabal install wxcore
sudo cabal install wx

Eso seria todo ahora a disfrutar de Haskell y wxHaskell para hacer interfaces graficas :)