viernes, 24 de abril de 2015

El Misterio del pase de parámetros en Java: ¿por valor o referencia?


Resulta sorprendente como después de llevar tiempo programando en Java y haber hecho infinidad de maravillas  uno se pueda quedar perplejo y hasta embarazado con la cuestión de si se pasan o no los parámetros por valor o referencia y cómo y cuándo. En un aula de clases no se le suelen dedicar ni dos horas ha hablar sobre eso.  De hecho en la Web existen diversidad opiniones sobre este tema, ¡pero no debería estar sujeto a opinión!, estamos hablando de algo que indiscutiblemente  tiene una implementación formal, de algo que esta programado y definido por el standar de Java por lo siglos de los siglos y que nadie puede cambiar ¿pero de cuál standar estamos hablando? ¿sera uno de estos? ¿o estos? ¿quién sera tan sesudo y paciente como para ponerse a revisarlos?. La polémica esta armada, vean la que se armo en stack overflow por este tema.

Parece que el problema esta en la forma en como hablamos. De hecho creo que eso de parámetros por valor y referencia es semánticamente confuso, pero Scott Stanchfield que es mucho más experto que yo, no esta de acuerdo con mi opinión, ni con la de muchos otros. Hablar de parámetros por valor y referencia no es algo muy típico de java o de los libros que tratan sobre java, no les extrañe si no consiguen nada sobre eso en muchos o no pocos de ellos.  Eso es algo más bien propio de lenguaje C. En java no se declara explicítamente parámetros por referencia o por valor, no existen por ejemplo los punteros , que es de donde viene esa distinción. Y sin embargo los parámetros implicítamente se pasan por valor o por referencia. Así que no es simplemente una extrapolación invalidad de los conocimientos de lenguaje C.

Un tema tan sencillo como este es algo que este link, parece haber cubierto plena y satisfactoriamente.  Lo dice y lo muestra muy claro:

"En Java todos los parámetros se pasan por valor
Cuando se realiza la llamada a un método, los parámetros formales reservan un espacio en memoria y reciben los valores de los parámetros actuales.
Cuando el argumento es de tipo primitivo (int, double, char, boolean, float, short, byte), el paso por valor significa que cuando se invoca al método se reserva un nuevo espacio en memoria para el parámetro formal. El método no puede modificar el parámetro actual.
Cuando el argumento es una referencia a un objeto (por ejemplo, un array o cualquier otro objeto) el paso por valor significa que el método recibe una copia de la dirección de memoria donde se encuentra el objeto. La referencia no puede modificarse pero sí se pueden modificar los contenidos de los objetos durante la ejecución del método"

En primer lugar lo que dice allí hecha por tierra que en Java se pasen parámetros por referencia y valor, dado que dice que solo se pasan por valor, y por tanto si se estaría extrapolando de forma invalidad los conceptos de lenguaje C. Pero antes de discutir eso vamos a ver cómo es que maneja java el pase de los parámetros.

Según ese link si los parámetros son primitivos la función tomará sus valores pero no podrá modificar el valor del parámetro original. Si los parámetros son objetos, la función podrá modificar los contenidos de los objetos.

Pero ¿qué pasa si los parámetros que se le pasan son arrays de primitivos? Efectivamente el link no dice nada sobre eso. Los arrays en Java son objetos aunque sean array de primitivos,  no es algo que sea obvio o haya que deducir (excepto programando), hay que saberlo.  Alguien que comento en Stack overflow dice que eso se especifica claramente en en la sección 4.3.1 de la Java Language Specification

Asi que si escriben:

char bb[] = {'s', 'o', 'p'};
if (bb instanceof Object) System.out.println("Yes!");

dira 'Yes!' .

Así que eso que se decía de que todos las clases de Java heredaban de Object es también cierto para los arrays primitivos.

Eso si, si escriben:

char bb[] = {'s', 'o', 'p'};
System.out.println("Nombre de Clase: " + bb.getClass().getName());

Les saldrá una cosa rara.

El link también decia que si se pasaban objectos a un método el contenido de estos podría ser modificado por el mismo. Por el contenido entiendo los atributos del objeto. Sin embargo hay ciertos objetos que sobrecargan el operador '=' (extrapolando la terminología de C++ dado que en Java en realidad no se sobrecargan los operadores) para lo eso no es cierto. Me refiero al objetos como String o Integer.

Si se hace:

String cadena = 'dsfskjlf';

luego se pasa como parámetro  a un método y allí se sustituye por otro valor eso no tendrá ningún efecto sobre el parámetro que se paso luego de salir del método. Parece que esto es cierto para todo Objecto que sobrecargue (extrapolando como dije antes) al operador '=', los cuales no son muchos.

Formalmente no se como se explicaría estas excepciones en Java, porque en general es cierto que si los atributos de un objeto que se paso como parámetro a un método se modifican en dicho método los cambios se mantendrán luego de salir del método. En el caso de String y Integer parece claro. aunque sea raro, que el valor que se le asiga a los mismos no constituye un atributo del objeto.

Para evitar las extrapolaciones con lenguje C, Java debe tener un lenguage complementamente propio y autosufienciente, en donde los casos que he mencionado anteriormente no induzcan la menor confusión. Sin duda que Java tiene eso, aunque no lo maneje a ese nivel y al parecer son muchos los que tienen ese problema. Quiero decir, por ejemplo, que encuentro incomodo,  referirme a casos como los anteriores sin hablar de parámetros por referencia y valor o referirme a algo como la sobrecarga que como se ha visto no serían terminos muy propios o apropiados para el  lenguaje Java. Incluso seria errado simplemente decir que en Java los parámetros siempre se pasan por valor, allí también se esta extrapolando. ¿Pero no refleja esta confusión también debilidades en el lenguaje Java?.

Concluyo finalmente con un código que de forma empírica muestra como maneja los parámetros Java. Con esto espero no volver a tener nuevamente esta confusión.


package misc;

/**
 * Programa que ilustra el pase de parámetros en Java
 * @author alexander
 */
public class PasoParametrosFunciones {
    public PasoParametrosFunciones () {
        int a=3;
        char c='a';
        byte e= (byte)11;
        System.out.println("Paso de valores primitivos: ");
        System.out.println("Valor antes de ejecutar la función: a = " +a + ", c = " +c + ", d =" + e);
        paso_primitivos (a, c, e );
        System.out.println("Valor despues de ejecutar la funcion: a = " +a + ", c = " +c + ", d =" + e);
       
        int aa[] = {1, 2, 7};
        char bb[] = {'s', 'o', 'p'};
       
        System.out.println("Paso de arrays primitivos: ");       
       
        System.out.println("Valor antes de ejecutar la función: aa[2] = " +aa[2] + ",bb[1] = " + bb[1]);       
        paso_array_primitivos (aa, bb);
        System.out.println("Valor despues de ejecutar la función: aa[2] = " +aa[2] + ",bb[1] = " + bb[1]);               
       
        System.out.println("Paso de Objectos: ");       
       
        String veronica = new String ("Veronica");
        Persona persona = new Persona("Carlos Fuentes", 'M', 21);
        Integer v = 4333;
       
        System.out.println("Valor antes de ejecutar la función: String veronia = " +veronica + ", Entero v " + v +
                ", Nombre Persona = " + persona.getNombre() + ", Edad Persona = " + persona.getEdad());

        paso_objectos (veronica, persona, v);
        System.out.println("Valor antes de ejecutar la función: String veronia = " +veronica + ", Entero v " + v +
                ", Nombre Persona = " + persona.getNombre() + ", Edad Persona = " + persona.getEdad());
   
    }
    static public void main(String args[]) {
        new PasoParametrosFunciones ();
    }
    void paso_primitivos (int a, char c, byte e) {
        a=199; c='3'; e= (byte) 'f';
    }
    void paso_array_primitivos (int aa[], char bb[]) {
        aa[0]= 7;
        aa[1]= 99;
       
        aa[2]= 88;
       
        bb[0]= 'z';
        bb[1] ='b';
        bb[2] = 'i';
    }
    void paso_objectos(String nombre, Persona p, Integer aa) {
        nombre= "Laura";
        p.setNombre("Jaimito");
        p.setEdad(1000);
        aa = 821;
       
    }
}

class Persona {
    private String nombre;
    private char sexo;
    private int edad;
   
    public Persona(String nombre, char sexo, int edad) {
        this.nombre = nombre;
        this.sexo= sexo;
        this.edad = edad;
       
    }

    public String getNombre() {
        return nombre;
    }

    public void setNombre(String nombre) {
        this.nombre = nombre;
    }

    public char getSexo() {
        return sexo;
    }

    public void setSexo(char sexo) {
        this.sexo = sexo;
    }

    public int getEdad() {
        return edad;
    }

    public void setEdad(int edad) {
        this.edad = edad;
    }
   
}

Ghost Effect con la programación script de GIMP (script-fu)

Para GIMP se pueden hacer scripts que automaticen tareas que se hacen desde la interfaz gráfica. Por ejemplo, el siguiente script esta hecho para correr desde bash. Lo que hace es tomar un conjunto de imágenes que representan una secuencia animada y tomando una imagen como fondo transparenta el conjunto imagenes animadas sobre dicho fondo, creando lo que se conoce como un ghost effect. Las imagenes que se utilizen para ello deberán haberse tomado previamente sin mover la cámara y utilizando una imagen como fondo en un escenario vacio y sin nada animado, que este en la misma posición en la cuál se toman la secuencia de imagenes animadas. De otra forma lo que se obtendra es un revoltijo.

#!/bin/bash
# Script para crear animaciones que trabaja con dos capas
# - Una en la que hay un fondo estático
# - Y otra de la animación la cual se transparenta contra el fondo
# El resultado es aspecto fantasmal de la imagen animada.
# Tanto el fondo estático como la capa animada deben tomarse en la misma posición y sin mover la cámara

{
cat <<EOF
(define (crea-transparencia imagen_fondo imagen_animacion imagen_salidad)
  (let* (
     (image (car (gimp-file-load RUN-NONINTERACTIVE imagen_fondo imagen_fondo)))
     (layer nil)
         (drawable nil)
     )

    (set! layer (car (gimp-file-load-layer RUN-NONINTERACTIVE image imagen_animacion)))
   

    (gimp-image-add-layer image layer 0 )
    (gimp-layer-set-opacity layer 25)
    (set! drawable (car (gimp-image-merge-visible-layers image EXPAND-AS-NECESSARY)))
    (file-jpeg-save RUN-NONINTERACTIVE image drawable imagen_salidad imagen_salidad 1 0 0 0 " " 0 1 0 1)
    (gimp-image-delete image) ; ... o la memoria explotara
    )
  )

(gimp-message-set-handler 1) ; Messages to standard output
EOF

imagen_fondo="../00554/0531.jpg"

for i in ../00554/*.jpg; do
  imagen_salidad=`echo $i | cut -d '/' -f 3`
  echo "(gimp-message \"$i\")"
  echo "(crea-transparencia \"$imagen_fondo\" \"$i\" \"$imagen_salidad\")"
done

echo "(gimp-quit 0)"
} | gimp -i -b -


Este es un ejemplo de un video que desarrolle para un proyecto en la universidad hace un tiempo:


domingo, 8 de marzo de 2015

Programación Gráfica en Linux


Programación a nivel de lenguaje C


Este es un programa sobre el conjunto Mandelbrot  extraido de esta página, que no daba ningún detalle de cómo compilarlo. Para poder compiarlo deben descargarse las librerias de OpenGL y Glut, el paquete de build-essentials y utilizar la instrucción:

$ gcc -o maldenbrot.o maldenbrot.c -lGL -lglut -lm




// Compilar con gcc -o maldenbrot.o maldenbrot.c -lGL -lglut -lm
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <GL/glut.h>
#include <GL/gl.h>
#include <GL/glu.h>

void set_texture();

typedef struct {unsigned char r, g, b;} rgb_t;
rgb_t **tex = 0;
int gwin;
GLuint texture;
int width, height;
int tex_w, tex_h;
double scale = 1./256;
double cx = -.6, cy = 0;
int color_rotate = 0;
int saturation = 1;
int invert = 0;
int max_iter = 256;

void render()
{
    double    x = (double)width /tex_w,
        y = (double)height/tex_h;

    glClear(GL_COLOR_BUFFER_BIT);
    glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE);

    glBindTexture(GL_TEXTURE_2D, texture);

    glBegin(GL_QUADS);

    glTexCoord2f(0, 0); glVertex2i(0, 0);
    glTexCoord2f(x, 0); glVertex2i(width, 0);
    glTexCoord2f(x, y); glVertex2i(width, height);
    glTexCoord2f(0, y); glVertex2i(0, height);

    glEnd();

    glFlush();
    glFinish();
}

int dump = 1;
void screen_dump()
{
    char fn[100];
    int i;
    sprintf(fn, "screen%03d.ppm", dump++);
    FILE *fp = fopen(fn, "w");
    fprintf(fp, "P6\n%d %d\n255\n", width, height);
    for (i = height - 1; i >= 0; i--)
        fwrite(tex[i], 1, width * 3, fp);
    fclose(fp);
    printf("%s written\n", fn);
}

void keypress(unsigned char key, int x, int y)
{
    switch(key) {
    case 'q':    glFinish();
            glutDestroyWindow(gwin);
            return;
    case 27:    scale = 1./256; cx = -.6; cy = 0; break;

    case 'r':    color_rotate = (color_rotate + 1) % 6;
            break;

    case '>': case '.':
            max_iter += 128;
            if (max_iter > 1 << 15) max_iter = 1 << 15;
            printf("max iter: %d\n", max_iter);
            break;

    case '<': case ',':
            max_iter -= 128;
            if (max_iter < 128) max_iter = 128;
            printf("max iter: %d\n", max_iter);
            break;

    case 'c':    saturation = 1 - saturation;
            break;

    case 's':    screen_dump(); return;
    case 'z':    max_iter = 4096; break;
    case 'x':    max_iter = 128; break;
    case ' ':    invert = !invert;
    }
    set_texture();
}

void hsv_to_rgb(int hue, int min, int max, rgb_t *p)
{
    if (min == max) max = min + 1;
    if (invert) hue = max - (hue - min);
    if (!saturation) {
        p->r = p->g = p->b = 255 * (max - hue) / (max - min);
        return;
    }
    double h = fmod(color_rotate + 1e-4 + 4.0 * (hue - min) / (max - min), 6);
#    define VAL 255
    double c = VAL * saturation;
    double X = c * (1 - fabs(fmod(h, 2) - 1));

    p->r = p->g = p->b = 0;

    switch((int)h) {
    case 0: p->r = c; p->g = X; return;
    case 1:    p->r = X; p->g = c; return;
    case 2: p->g = c; p->b = X; return;
    case 3: p->g = X; p->b = c; return;
    case 4: p->r = X; p->b = c; return;
    default:p->r = c; p->b = X;
    }
}

void calc_mandel()
{
    int i, j, iter, min, max;
    rgb_t *px;
    double x, y, zx, zy, zx2, zy2;
    min = max_iter; max = 0;
    for (i = 0; i < height; i++) {
        px = tex[i];
        y = (i - height/2) * scale + cy;
        for (j = 0; j  < width; j++, px++) {
            x = (j - width/2) * scale + cx;
            iter = 0;

            zx = hypot(x - .25, y);
            if (x < zx - 2 * zx * zx + .25) iter = max_iter;
            if ((x + 1)*(x + 1) + y * y < 1/16) iter = max_iter;

            zx = zy = zx2 = zy2 = 0;
            for (; iter < max_iter && zx2 + zy2 < 4; iter++) {
                zy = 2 * zx * zy + y;
                zx = zx2 - zy2 + x;
                zx2 = zx * zx;
                zy2 = zy * zy;
            }
            if (iter < min) min = iter;
            if (iter > max) max = iter;
            *(unsigned short *)px = iter;
        }
    }

    for (i = 0; i < height; i++)
        for (j = 0, px = tex[i]; j  < width; j++, px++)
            hsv_to_rgb(*(unsigned short*)px, min, max, px);
}

void alloc_tex()
{
    int i, ow = tex_w, oh = tex_h;

    for (tex_w = 1; tex_w < width;  tex_w <<= 1);
    for (tex_h = 1; tex_h < height; tex_h <<= 1);

    if (tex_h != oh || tex_w != ow)
        tex = realloc(tex, tex_h * tex_w * 3 + tex_h * sizeof(rgb_t*));

    for (tex[0] = (rgb_t *)(tex + tex_h), i = 1; i < tex_h; i++)
        tex[i] = tex[i - 1] + tex_w;
}

void set_texture()
{
    alloc_tex();
    calc_mandel();

    glEnable(GL_TEXTURE_2D);
    glBindTexture(GL_TEXTURE_2D, texture);
    glTexImage2D(GL_TEXTURE_2D, 0, 3, tex_w, tex_h,
        0, GL_RGB, GL_UNSIGNED_BYTE, tex[0]);

    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
    render();
}

void mouseclick(int button, int state, int x, int y)
{
    if (state != GLUT_UP) return;

    cx += (x - width / 2) * scale;
    cy -= (y - height/ 2) * scale;

    switch(button) {
    case GLUT_LEFT_BUTTON: /* zoom in */
        if (scale > fabs(x) * 1e-16 && scale > fabs(y) * 1e-16)
            scale /= 2;
        break;
    case GLUT_RIGHT_BUTTON: /* zoom out */
        scale *= 2;
        break;
    /* any other button recenters */
    }
    set_texture();
}


void resize(int w, int h)
{
    printf("resize %d %d\n", w, h);
    width = w;
    height = h;

    glViewport(0, 0, w, h);
    glOrtho(0, w, 0, h, -1, 1);

    set_texture();
}

void init_gfx(int *c, char **v)
{
    glutInit(c, v);
    glutInitDisplayMode(GLUT_RGB);
    glutInitWindowSize(640, 480);
    glutDisplayFunc(render);

    gwin = glutCreateWindow("Mandelbrot");

    glutKeyboardFunc(keypress);
    glutMouseFunc(mouseclick);
    glutReshapeFunc(resize);
    glGenTextures(1, &texture);
    set_texture();
}

int main(int c, char **v)
{
    init_gfx(&c, v);
    printf("keys:\n\tr: color rotation\n\tc: monochrome\n\ts: screen dump\n\t"
        "<, >: decrease/increase max iteration\n\tq: quit\n\tmouse buttons to zoom\n");

    glutMainLoop();
    return 0;
}

martes, 20 de enero de 2015

Seguridad de una infraestructura de Red


Siguiendo el esquema de capas del modelo OSI se podría hablar de seguridad de la Red a nivel de varias capas, nos enfocaremos en solo en 4 de ellas:

  • Seguridad a nivel de Capa de Enlace (intranet)
  • Seguridad a nivel de Capa de Red (intranet)
  • Seguridad a nivel de Capa de Transporte (LAN o WAN)
  • Seguridad a nivel de Capa de Aplicaciones

En cada una de estas capas existen todo un conjunto de protocolos especificados para trabajar dentro de cada una de ellas. Estos protocolos muchas veces presentan ciertos defectos o vulnerabilidades, inherente a la propia especificación de los mismos o las limitaciones físicas que hay en el mundo real para implementarlos, por ejemplo: el ancho de banda o los recursos de la máquina. Por otra parte están las vulnerabilidades de las aplicaciones que trabajan con dichos protocolos. No hay que confundir las dos cosas, una cosa son los vulnerabilidades de los protocolos y otra la de las aplicaciones. En ocasiones existen tecnologías o configuraciones de red que permiten corregir o apaliar los riesgos de un determinado protocolo, en otras no, o bien los inconvenientes o costos son tales que hacen imposible cualquier implementación. Finalmente están las vulnerabilidades ocasionadas por errores humanos en cuanto a la configuración de un servicio o la infraestructura de red.

Hay protocolos de bajo nivel que suelen ser implementados directamente en el kernel del sistema operativo (por ejemplo ICMP). También hay protocolos se ejecutan en aplicaciones que tienen un nivel de privilegio alto, sea root, administrador o system. Debe tenerse en consideración cuáles son los parámetros de configuración óptimos, cuando eso se puede manipular, que permitirían minimizar los riegos de la infraestructura de red, para los protocolos implementados a nivel de kernel. Por ejemplo la deshabilitación de las respuestas a los mensajes de ping, en el caso de que sea pertinente. También debería tenerse muy en cuenta cuáles son las aplicaciones potencialmente peligrosas que se ejecutan con un alto nivel de privilegio y que medidas se pueden tomar para minimizar los riegos.

La tarea del administrador de red en el caso de las aplicaciones que tienen bugs o errores se reduce simple y llanamente a actualizar dichas aplicaciones con los parches respectivos. Hay aplicaciones y sistemas que se actualizan automáticamente mientras que hay otras que no. También existen vulnerabilidades de Zero-day para las que no existen parches conocidos o para las que hay que buscar parches de 3ra partes, en muchos casos de dudosa confiabilidad. Debe evaluarse si en esos casos conviene o no deshabilitar o sustituir los servicios asociados con esas vulnerabilidades.

Una cuestión importante es cómo identificar mediante la monitorización del tráfico de la Red cualquier ataque o fallo en la misma. Evidentemente esto requiere del uso de sniffers y el dominio de técnicas para usarlos. En cuanto al tráfico, en algunos casos, como los mensajes de broadcast o multicast, es posible identificar un tráfico irregular desde cualquier puerto de un switch o ubicación de red. Hay un tráfico de red que solo es visible dentro de los puertos de un switch, hay un tráfico de Intranet y hay un tráfico de Internet . Hay técnicas de hacking como el ARP Spoofing para visualizar el tráfico de un determinado nodo en un Switch.

El responsable de la seguridad de una red deberá tener presente los riesgos que hay a nivel de las distintas capas de la red, cuáles son los protocolos y aplicaciones trabajando en ellas de forma activa en el IBE y la localización física de los nodos o dispositivos asociados. Las aplicaciones afectadas pueden ser el propio sistema operativo. 

jueves, 4 de septiembre de 2014

ora2pg: Migrando Funciones y Procedures de Oracle a PostgreSQL desde un archivo


Estos son dos ejemplos sencillos:

 Funciones:
ora2pg -p -t FUNCTION -i acctbalance.sql -o acctbalance_pg.sql


Procedures:
ora2pg -p -t PROCEDURE -i acctbalance.sql -o acctbalance_pg.sql


Problema 1004. Sightseeing Trip (Ruta Turística) de acm.timus.ru

  1004. Sightseeing Trip

Este problema lo resolví utilizando un algoritmo de recorrido de un grafo, que represento por medio de una matriz y varios vectores. El grafo lo recorro por medio de una rutina que utiliza backtraking.  Debe compilarse con g++


// Compilar con g++

#include <stdio.h>
#include <string.h>


int no_se_ha_escogido_el_nodo(int vertic, int lim );
void guarda_vector(int vert_i, int lim);
void recorrido_minimo(int nivel, int distancia_recorrida) ;

int calcula_distancia (int lim, int indi);
int ind_vector(int vector, int lim);


int vert[100][10000];     // matriz que enlaza un vertice con otro
int cam[100][100];      // matriz que indica la distancia entre cada camino
int ind[100], i;    // matriz que indica el indice de los caminos que parten de un vertice
int vertices[100];     // matriz que indica el vertice que se esta recorriendo para un determinado nivel de profundidad
int vect_guardado[100]; // matriz en donde se guarda el recorrido de la solucion
int orden[100];        // matriz que indica el orden en el que se dieron los vertices o nodos
int se_dio[101];
int lim_vector_guardado;     // el tamaño del vector que se guardo
int vertice_i;



int distancia_minima = 0x7fffffff;
int N, M;

int main (void) {
  int i;
  int ni; int nk; int distancia;

  int distancia_min, distancia_recorrida;
 




  do {
    memset(vert, 0, sizeof(int)*1000000);
    memset(cam, 0, sizeof(int)*10000);
    memset(ind, 0, sizeof(int)*100);
    memset(orden, 0, sizeof(int)*100);
    memset(se_dio, 0, sizeof(int)*101);

    scanf("%d", &N);  // toma vertices
    if(N==-1) break;
    scanf("%d", &M);  // toma el numero de caminos
    int j=0;
    for(i=0; i < M; i++) {
   
      scanf("%d%d%d", &ni, &nk, &distancia);
      if(cam[ni-1][nk-1] == 0) {
        vert[ni-1][ind[ni-1]] = nk;
        vert[nk-1][ind[nk-1]] = ni;

        if(se_dio[ni-1]== 0 ) {

          se_dio[ni-1]=1;
          orden[j] = ni;j++; 
        } 
        if(se_dio[nk-1] ==0) {
          se_dio[nk-1]=1;    
          orden[j] = nk;j++;        
        }

        ind[ni-1]++;
        ind[nk-1]++;
        cam[ni-1][nk-1] = distancia;
        cam[nk-1][ni-1] = distancia;   
      }
      else if(cam[ni-1][nk-1] > distancia) {
        cam[ni-1][nk-1] = distancia;
        cam[nk-1][ni-1] = distancia;   

      }
     

    }

    // debido a que el grafo puede ser inconexo se chequean todos los vertices utilizando la matriz orden[k]... saltando de 2 en dos porque basta con
    // chequear uno de la pareja de cada camino dado
    //vertice_i=orden[0];
   

    for(int k=0; k < N; k+=2) {
      vertice_i = orden[k];
      recorrido_minimo(0, 0);

    }


    if(distancia_minima != 0x7fffffff) {
      for(i=0; i < lim_vector_guardado-1; i++) {
        printf("%d ", vect_guardado[i]);
      }

      printf("%d\n", vect_guardado[lim_vector_guardado-1]);
      distancia_minima = 0x7fffffff;
    }

    else {
      printf("No solution.\n");
    }

  } while(1);



}


void recorrido_minimo(int nivel, int distancia_recorrida) {
   int j, distancia;

  
   if(distancia_recorrida >= distancia_minima) return;
   if(nivel==0) {
     vertices[nivel] = vertice_i;

     recorrido_minimo(1, distancia_recorrida);
   }

   else {

     j=0;

    
     while(vert[vertices[nivel-1]  -1 ][j]!=0  )  {
       distancia = no_se_ha_escogido_el_nodo(vert[vertices[nivel-1] -  1][j] , nivel );   
      
       if(!distancia) {
        
         vertices[nivel] = vert[vertices[nivel-1] -1 ][j];

         recorrido_minimo(nivel+1, distancia_recorrida + cam[vertices[nivel-1] -1 ][vertices[nivel] - 1]);  

       }  
       else if(nivel - ind_vector(vert[vertices[nivel-1] -  1][j], nivel) > 2){

      if(distancia < distancia_minima) {

            distancia_minima = distancia;
            guarda_vector(vert[vertices[nivel-1] -  1][j], nivel);
          }

       }
       j++;


     }



   }
    


}

int ind_vector(int vector, int lim) {
  int i;
  for(i=0; i < lim; i++ ) {
    if(vector == vertices[i]) {  
      return i;
    }    

  }
}

int no_se_ha_escogido_el_nodo(int vertic, int lim ) {
  int i;
  for(i=0; i < lim; i++ ) {
    if(vertic == vertices[i]) {       
      return calcula_distancia (lim, i);
    }

  }

  return 0;
}


void guarda_vector(int vert_i, int lim) {
  int i;
  for(i=0; i < lim; i++){
     if(vertices[i] == vert_i)  {
       for(int j=i; j < lim; j++) {
         vect_guardado[j-i] = vertices[j] ;


       }
       break;
     }

  }
  lim_vector_guardado = lim - i;

}

int calcula_distancia (int lim, int indi) {
  int distancia=0;
  for(int i=indi+1; i < lim; i++) {
    distancia = distancia + cam[vertices[i-1] -1 ][vertices[i] - 1];
  }
  distancia = distancia + cam[vertices[indi] -1 ][vertices[lim-1] - 1];
  return distancia;

}

viernes, 7 de marzo de 2014

Cómo pasar los nombres de archivos que contengan espacios a una tubería


Al utilizar el comando find de esta forma:

find . -iname "*.htm*" | xargs -n1 grep -H -i "palabra"

los nombres de archivos que contengan espacios se pasaran de forma fragmentada en la tubería, de forma tal que un nombre de archivo como "Fulano de tal.htm",  pasado a grep con la tuberia (pipe en inglés: '|') lo vera como 3 archivos distintos: "Fulano", "de", "tal.hm", debido a que toma el carácter de espacio " ", como un delimitador. Para evitar dicho problema debe corregirse la instrucción anterior de esta forma:

find . -iname "*.htm" -print0 | xargs -0 -n1 grep -H -i "palabra"