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:



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:



$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

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

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