Posts Tagged ‘Programacion’

Newer Entries »

¿Como funciona el swaping con XOR?

March 6th, 2008

Los que estudiaron programación indudablemente se encontraron con el problema de swapear dos variables, es decir, intercambiar su valor, y los profesores indudablemente mostraban la resolución:

1
2
3
4
5
6

	void Swap (ref int a, ref int b) 
	{
		int swapTemporal = a;
		a = b;
		b = swapTemporal;
	}

Donde se usaba una variable temporal para no perder el valor de a cuando se le asigna el valor de b, para posteriormente asignárselo a b. Algunos tal ves se hayan encontrado la resolución alternativa, usando XOR sin variable temporal:

1
2
3
4
5
6

	void Swap (ref int a, ref int b) 
	{
		a = a ^ b;
		b = a ^ b;
		a = a ^ b;
	}

Y quedaron sorprendidos por que ciertamente funciona.

¿Pero, por que?

Empezamos definiendo rápidamente, XOR es un OR exclusivo, lo que significa que es un operador binario que nos da como resultado un 1 solamente si uno de los dos (pero no ambos) operandos es igualmente 1, es decir, la siguiente tabla de verdad:

	_________________
	| a | b | a ^ b |
	-----------------
	| 0 | 0 |   0   |
	| 0 | 1 |   1   |
	| 1 | 0 |   1   |
	| 1 | 1 |   0   |
	-----------------

Dado esto podemos definir un par de axiomas:

	a ^ a = 0
	a ^ 0 = a

es decir:

  • Si ambos operandos son iguales en un XOR el resultado es invariablemente cero
  • Si un operando es igual a cero en un XOR el resultado es invariablemente el valor del otro operando

Y estos dos axiomas son lo único que necesitamos para comprobar que el primer y segundo código son equivalentes:

a’ = a ^ b //Es a prima para evitar confundir la variable con el valor original de a

b’ = a’ ^ b
Si sutituimos el valor de a’ tenemos:
b’ = (a ^ b) ^ b
b ^ b = 0 por nuestro primer axioma, por lo que nos queda:
b’ = a ^ 0
a ^ 0 = a por nuestro segundo axioma, por lo que tenemos
b’ = a

a’ = a’ ^ b’ //Si sustituimos los valores de a’ y b’ tenemos:
a’ = (a ^ b) ^ a
a ^ a = 0 por nuestro primer axioma, por lo que nos queda:
a’ = b ^ 0
b ^ 0 = b por nuestro segundo axioma, por lo que tenemos
a’ = b

Asi, al finl de las tres operaciones a’ tiene el valor original de b, y b’ el valor original de a.

Q.E.D. \o/

Como ven la demostración es trivial y seguramente un overkill, pero te puede matar 5 minutos de aburrimiento :p. Nos vemos en la siguiente entrega cuando demuestre que el negro es blanco, claro, al menos que muera antes en un crucero de zebras.

4 comments »

Posted in Programacion

Tags:

Aprendiendo Regex – El imperio contrataca.

February 21st, 2008

Gnoblis posteo hacerca de un pequeño programa que hizo para convertir bbcode a html en su web: http://gnoblis.gamersla.net/?p=67. El codigo esta aca http://gamersla.net/gnoblis/descargas/CCast.cs

Su solucion si bien funciona, no es de lo mas elegante. El problema es facilmente resuelto con expresiones regulares, y se lo hizo saber en un comentario en su post.

Claro, los que me conocen sabran que no es suficiente haberle dicho como se podria resolver mejor, ¡hace falta hacerlo uno mismo!

Asi que como demostracion del poder de las expresiones regulares y que no soy un hablador les muestro el codigo:

Nota, el programa no lo probe a excepcion de las expreciones regulares, por lo que pueden encontrarse con sorpresas ;) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

using System;
using System.IO;
using System.Text;
using System.Text.RegularExpressions;
 
class Program
{
 
    public static void Main(string[] args)
    {
 
        StreamReader inputReader;
        StreamWriter outputWriter;
        string actualLine;
        StringBuilder inputFileContent = new StringBuilder ();
 
        foreach (string actualFile in args) //Agrego la capacidad de convertir varios archivos a la ves
        {
            if (!File.Exists(actualFile))
            {
                Console.WriteLine("File not found, skipped: {0}", actualFile);
                continue;                   //Ignoramos el archivo, pero seguimos con los demas \o/
            }
 
            inputReader = new StreamReader(File.OpenRead(actualFile));
 
 
            inputFileContent.Remove(0, inputFileContent.Length);
            while ((actualLine = inputReader.ReadLine()) != null)
                inputFileContent.AppendLine(string.Format("{0}{1}", actualLine, "<br />"));
 
            inputReader.Close ();
 
            if (inputFileContent.Length == 0)
            {
                Console.WriteLine("Empty file, skipped: {0}", actualFile);
                continue;
            }
 
            string bbcodeData = inputFileContent.ToString();
 
            //Quitamos todos los espacios antes y despues de un igual, no solo uno
            bbcodeData = Regex.Replace(bbcodeData, @"\ {0,}=\ {0,}", "=", RegexOptions.IgnoreCase | 
                                                                          RegexOptions.Multiline);
 
            //Convertimos [b], [i], [u], [s] y sus respectivos cierres
            bbcodeData = Regex.Replace(bbcodeData, @"\[(?<tag>\/{0,1}[b|i|u|s])\]", @"<${tag}>", 
                RegexOptions.IgnoreCase | RegexOptions.Multiline);
 
            //imagenes
            bbcodeData = Regex.Replace(bbcodeData, @"\[img\](?<url>.*?)\[\/img\]",
                "<img src=\"${url}\" />", RegexOptions.IgnoreCase | RegexOptions.Multiline);
 
            //Links
            bbcodeData = Regex.Replace(bbcodeData, @"\[url=(?<url>.*?)\](?<data>.*?)\[/url\]",
                "<a href=\"${url}\">${data}</a>", RegexOptions.IgnoreCase | RegexOptions.Multiline);
 
            //Colores
            bbcodeData = Regex.Replace(bbcodeData, @"\[color=(?<color>.*?)\](?<data>.*?)\[/color\]", 
                "<font color=\"${color}\">${data}</font>", RegexOptions.IgnoreCase | 
                                                           RegexOptions.Multiline);
 
            outputWriter = new StreamWriter (File.Create(actualFile + ".html"));
 
            outputWriter.Write(bbcodeData);
 
            outputWriter.Close();
        }
    }
}

2 comments »

Posted in Programacion

Tags:

¿No sabes XPath? ¡Aprende!

December 11th, 2007

Otra de las herramientas de un desarrollador que se vuelven completamente imprescindibles una ves que las conoces es XPath.

XPath es un estándar del W3C para realizar querys a documentos Xml, haciendo fácil filtrar los nodos de un documento de acuerdo a la estructura y atributos de los nodos.

Si no usamos XPath, tendríamos que iterar a través de todos los nodos de un documento Xml para obtener la información que buscamos.

Para no hacérsela mas larga voy a dejar que el código hable por si mismo.

Imaginen que tienen el siguiente Xml:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<?xml version="1.0" encoding="utf-8" ?> 
<Sucursales>
	<Sucursal name="Matriz">
		<Articulo name="Monitor" precio="1500"/>
		<Articulo name="Impresora" precio="400"/>
	</Sucursal>
	<Sucursal name="Mayoreo">
		<Articulo name="Monitor" precio="1600"/>
		<Articulo name="Impresora" precio="500"/>
	</Sucursal>
	<Sucursal name="Menudeo">
		<Articulo name="Monitor" precio="1800"/>
		<Articulo name="Impresora" precio="700"/>
	</Sucursal>
</Sucursales>

Y ustedes quieren saber tres cosas:

  1. ¿Que artículos con que precios se encuentran en la sucursal Matriz?
  2. ¿Que sucursales tienen monitores?
  3. ¿Que precio tiene una impresora en la sucursal menudeo?

Sin XPath estas tres simples preguntas se convierte en esta monstruosidad:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

using System;
using System.Xml;
using System.Collections.Generic;
 
class Program
{
    public static void Main()
    {
        XmlDocument document = new XmlDocument();
        document.Load("Test.xml");
        XmlNode sucursales = document.ChildNodes[1];
 
        //Obtener los articulos de la sucursal matriz
        XmlNodeList articulosMatriz;
        foreach (XmlNode sucursal in sucursales.ChildNodes)
            if (sucursal.Name == "Sucursal")
                if (sucursal.Attributes["name"].Value == "Menudeo")
                    articulosMatriz = sucursal.ChildNodes;
 
        //Obtener todas las sucursales que tienen monitores
        List<XmlNode> sucursalesConMonitor = new List<XmlNode>();
        foreach (XmlNode sucursal in sucursales.ChildNodes)
        {
            if (sucursal.Name == "Sucursal")
            {
                foreach (XmlNode articulo in sucursal.ChildNodes)
                {
                    if (articulo.Name == "Articulo")
                    {
                        if (articulo.Attributes["name"].Value == "Monitor")
                        {
                            sucursalesConMonitor.Add(sucursal);
                            break; //Siguiente sucursal
                        }
                    }
                }
            }
        }
 
        //Obtener el precio de una impresora en la sucursal menudeo
        XmlNode impresoraSucursalMenudeo = null;
        foreach (XmlNode sucursal in sucursales.ChildNodes)
        {
            if (sucursal.Name == "Sucursal")
            {
                if (sucursal.Attributes["name"].Value == "Menudeo")
                {
                    foreach (XmlNode articulo in sucursal.ChildNodes)
                    {
                        if (articulo.Name == "Articulo")
                        {
                            if (articulo.Attributes["name"].Value == "Impresora")
                            {
                                impresoraSucursalMenudeo = articulo;
                                break; 
                            }
                        }
                    }
 
                    if (impresoraSucursalMenudeo != null)
                        break; //Se encontro el articulo, terminamos!
                }
            }
        }
    }
}

¡HORRIBLE!

Claro que si hicieron la tarea y saben XPath, ¡las cosas cambian dramáticamente!:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

using System;
using System.Xml;
 
class Program
{
    public static void Main()
    {
        string xPathQuery;
        XmlDocument document = new XmlDocument();
        document.Load("Test.xml");
 
        //Obtener los articulos de la sucursal matriz
        xPathQuery = @"/Sucursales/Sucursal[@name='Matriz']/Articulo";
        XmlNodeList nodes = document.SelectNodes(xPathQuery);
 
        //Obtener todas las sucursales que tienen monitores
        xPathQuery = @"/Sucursales/Sucursal[./Articulo[@name='Monitor']]";
        nodes = document.SelectNodes(xPathQuery);
 
        //Obtener el precio de una impresora en la sucursal menudeo
        xPathQuery = @"/Sucursales/Sucursal[@name='Menudeo']/Articulo[@name='Impresora']";
        XmlNode node = document.SelectSingleNode(xPathQuery);
    }
}

SIMPLE, SENCILLO Y HERMOSO

Si no saben nada al respecto lean por lo menos este tutorial de w3schools, no se arrepentirán.

P.S XPath es un estándar, por lo que no depende de .NET, puedes usarlo en Java, Python o lo que te de tu gana

No comments »

Posted in Programacion

Tags:

¿No sabes Regex? ¡Aprende!

December 7th, 2007

Algo de lo que me e dado cuenta cuando e dado platicas/talleres/cursos es que la gran mayoría de los desarrolladores, al menos de la región, no tienen ni puta idea acerca de que demonios son las expresiones regulares (Regex para los amigos).

Muchos recuerdan haber escuchado algo al respecto en su clase de autómatas en la universidad, pero como a todos, les paso de noche :P .

Es difícil de entender como la gente puede pasarse sentado en su vida profesional sin saber Regex, escribiendo cientos de lineas de código resolviendo problemas que con unos cuantos caracteres de Regex queda solucionado.

Si aun no sabes Regex, ¡deja de leer esto inmediatamente y ponte a buscar información al respecto!

Para los escépticos, un pequeño ejemplo:

Imagina que quieres validar que un teléfono siga el formato (900) 9-00-00-00, la forma común de hacerlo seria algo cómo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

    bool isValidPhoneNumber(string input)
    {
        //Validate (900) 9-00-00-00
        if (input.Length != 16)
            return false;
        if (!input.StartsWith("("))
            return false;
        if (input[4] != ')')
            return false;
        int number;
        if (!int.TryParse(input.Substring(1, 3), out number))
            return false;
        if (input[1] == '0' || !char.IsNumber(input[1]))
            return false;
        if (input[5] != ' ')
            return false;
        string[] numbers = input.Substring(6, 10).Split ('-');
        if (numbers.Length != 4)
            return false;
        foreach (string subpart in numbers)
            if (!int.TryParse(subpart, out number))
                return false;
        if (numbers[0][0] == '0')
            return false;
        return true;
    }

Es tedioso de hacer, resulta fácil dejar errores en el, sin mencionar que es completamente horrible y resulta difícil de entender, y precisamente este es uno de los momentos en que Regex es útil:

1
2
3
4
5
6
7
8

   bool isValidPhoneNumber(string input)
    {
        //Validate (900) 9-00-00-00
        string expression = @"^\([1-9]\d{2}\)\ [1-9](\-\d{2}){3}$";
        System.Text.RegularExpressions.Regex regex = 
            new System.Text.RegularExpressions.Regex(expression);
        return regex.IsMatch(input);
    }

Si bien la sintaxis puede resultar confusa al inicio, basta un poco de practica para acostumbrarse a ella y puede llegar a ahorrarte toneladas de trabajo, especialmente si la usas para buscar patrones de texto en ves de solamente validación.

Confíen en mi, si no las conocen, ¡Aprendan!.

P.S: No me hago responsable de cualquier mal uso que puedan hacer de ellas ;)

9 comments »

Posted in Programacion

Tags: