Conjectura de Collatz

Uma excelente forma de aprender, é tentar resolver problemas. A gente ja comentou aqui sobre o project Rosalind e o project Euler. Eles tem excelentes problemas, que são bem instrutivos tentar resolver. Agora eu descobri outro lugar, que funciona de forma similar, mas tem problemas de computação, o UVa Online Judge. E aqui vamos para o primeiro problema, para ver como funciona.

A conjectura de Collatz, também conhecida como problema 3n + 1 é uma sequência de números, como a sequência de fibonacci. É uma função que qualquer número que a gente coloca nela termina em 1.

A função é essa:

   f(n) = \left\{       \begin{array}{lr}         n/2 & : se\ {n \equiv 0} (mod\ 2)\\         3n+1 & : se\ {n \equiv 1} (mod\ 2)       \end{array}     \right.

Bem, as vezes é mais fácil olhar a função na linguagem do R, as vezes fica mais fácil entender o que fazer. No R essa função fica assim:

collatz<-function(n) {
    if( (n %% 2) == 0 ) {
        n<-n/2
    } else {
        n<-n*3+1
    }
    return(n)
}

Agora se a gente digitar collatz(n), onde n é um número qualquer e temos o próximo valor da sequência.

> collatz(22) [1] 11

Certo, para ver a sequência inteira, basta fazermos isso até chegar a 1.
Podemos fazer uma segunda função, que usa essa primeira para cumprir essa tarefa no R

seqcollatz<-function(n) {
    vetor<-c(n)
    i<-1
 
    while(vetor[i]!=1) {
        vetor[i+1]<-collatz(vetor[i])
        i<-i+1
    }
 
    return(vetor)
}

E voala, podemos ver a sequência e o seu tamanho.

> seqcollatz(22) [1] 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 > seqcollatz(10) [1] 10 5 16 8 4 2 1

Uma característica legal, é que se você for olhar a sequência inteira, como tudo converge para o 1, se a gente olhar do 1 para frente, podemos pensar nas possibilidades de inicio na forma de um grafo.

exemplo

Veja que de qualquer número que começamos, cedo ou tarde, a gente entra num “trilho” rumo ao número 1. Alias, todo mundo converge para o 8, mas o tamanho da sequência não é obvia, veja como o 9 gera uma sequência enorme, enquanto o 16 por exemplo, gera uma sequência curta.

Mas o problema é mais simples que entender a estrutura dessa sequência, ele simplesmente quer dar 2 entradas, dois números inteiros, e devemos ver o tamanho da sequência a todos os números dentro desse intervalo de dois inteiros e dizer qual foi a maior.

Então a entrada é um conjunto de pares de números, algo como:

1 10 100 200 201 210 900 1000

E a saída esperada para essa entrada é:

1 10 20 100 200 125 201 210 89 900 1000 174

Ou seja entre 1 e 10, a maior sequência tem 20 elementos, que é a serie formada quando começamos no 9.

> seqcollatz(9) [1] 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 > length(seqcollatz(9)) [1] 20

Como UVa Online Judge não aceita programas em R, então temos que fazer usando alguma das linguagens que ele aceita. Em C, minha tentativa ficou assim.

#include <stdio.h>
 
/* Função que calcula o proximo valor na sequencia de collatz*/
int collatz(int n) {
  if(n!=1) {
    if(n%2==0) {
      n=n/2;
    } else {
      n=n*3+1;
    }
  }
    return n;
}
 
/* Função que calcula o tamanho da sequencia para um determinado n*/
int seqcollatz(int n) {
  int ciclo=1;
  while(n!=1) {
      n=collatz(n);
      ciclo++;
  }
  return ciclo;
}
 
int main(void){
  int a,b,i,ciclo,maior,x,y;
 
  while (scanf("%d %d", &x, &y) != EOF) {
 
    if(x>y) {
      a=y;
      b=x;
    } else {
      a=x;
      b=y;
    }
 
    maior=1;
 
    for(i=a;i<=b;i++) {
      ciclo=seqcollatz(i);
      if(maior<ciclo) {
	maior=ciclo;
      }
    }
 
    printf("%d %d %d\n",x,y,maior);
  }
  return 0;
}

Então são duas funções auxiliares, como a gente estava olhando em R, uma da o próximo número na sequência, e a outra verifica o tamanho da sequência.

Alguma coisa especiais são necessárias, como a entrada não tem um número de casos a serem testados, a gente precisa de algo especial no scanf, para ele parar quando não houver mais entradas. o != EOF, não sei o que isso faz perfeitamente para falar a verdade, mas funciona.

Além disso o problema tem umas pegadinhas.
Primeiro em nenhum momento ele diz que as entradas vão estar na ordem, menor depois maior, então isso precisa ser testado, e eles tem que ser impressos no final na ordem que entraram. Eu apanhei um bocado para entender isso.

Submetendo esse programa, eu tive uma resposta correta, mas uma bosta, fiquei em 22948 no ranking. Mas eficiência fica para a próxima. O legal que é possível submeter programa em java também.

Meu programa em java ficou assim:

import java.util.Scanner;
 
class main {
 
	public static int collatz(int n){
		 if(n!=1) {
			    if(n%2==0) {
			      n=n/2;
			    } else {
			      n=n*3+1;
			    }
			  }
			    return n;
	}
 
	public static int seqcollatz(int n){
		int ciclo=1;
 
		  while(n!=1) {
 
		      n=collatz(n);
		      ciclo++;
 
		  }
 
		  return ciclo;
	}
 
	public static void main(String[] args) {
 
		int a,b,i,ciclo,maior,x,y;
 
		Scanner leitor = new Scanner(System.in);
 
		while(leitor.hasNext()) {
			x=leitor.nextInt();
			y=leitor.nextInt();
 
			   if(x>y) {
				      a=y;
				      b=x;
				    } else {
				      a=x;
				      b=y;
				    }
 
				    maior=1;
 
				    for(i=a;i<=b;i++) {
 
				      ciclo=seqcollatz(i);
 
				      if(maior<ciclo) {
					maior=ciclo;
				      }
 
				    }
 
				    System.out.printf("%d %d %d\n",x ,y ,maior);
 
		}
 
		leitor.close();
 
	}
 
}

A ideia é exatamente a mesma do programa em C.

Ele funcionou beleza no terminal, mas não sei porque o UVa Online Judge não aceita ele, fica dando um runtime error, mas no terminal tudo da certo:

$ javac collatzsequence.java $ java collatzsequence < input.txt 1 10 20 100 200 125 201 210 89 900 1000 174

Agora é começar a tentar resolver mais problemas, mas essa é mais uma opção além do Rosalind e do Project Euler para aprender mais um pouquinho de programação.

Os scripts e programas vão ficar disponíveis la no repositório recologia do github, se alguém quiser olhar, porque as vezes alguns problemas são frustantes, principalmente quando ficamos cometendo erros bobos. Se alguém souber como resolver direito o programa em Java, e melhorar a performance em C eu agradeço muito sugestões. Em C imagino que operações em Bits sejam mais rápidas.

Insertionsort em R e C++ usando o pacote rcpp

Bem, depois de vermos o algorítimo mais simples que tem para ordenar um vetor, o bubble sort. Agora a gente vai olhar outro um pouco mais legal, esse se chama insertion sort.

A ideia é a seguinte:

Então a gente tem um vetor qualquer, com n elementos.
 C = \{X_1 , X_2 , X_3 , \dots , X_n  \}

E a gente quer que esses elementos fiquem assim:

 Regra = \{x_1 \leq x_2 \leq x_3 \leq \dots \leq x_n  \}

Como a gente faz?
Vamos supor um conjunto aqui.

 C = \{6, 5, 3, 1, 8, 7, 2, 4\}

Ele esta desorganizado porque ele não respeita nossa Regra_1. So olhar o primeiro elemento que é 6.

So que a estratégia aqui muda. O que a gente faz?
Primeiro pega um sub-vetor, um pedaço desse la em cima.

 C = \{6\}

Esse vetor está organizado? Sim, não temos ninguém para comparar. Um vetor de 1 elemento sempre está organizado.

Agora pegamos o segundo elemento, o 5.
Ai fazemos a pergunta onde ele deveria está?
Antes ou depois do 6?
Bem ele é menor que o 6 então tem que estar depois, então movemos o 6 um índice pra frente e dai colocamos o 5.

 C = \{5 ,6\}

Agora pegamos outro elemento, o 3, e repetimos o os passos anteriores.

Perguntamos, onde é a posição do 3?
Ele é menor que o 6? Sim então movemos o 6 um índice para a frente.
Ele é menor que o 5? Sim, então movemos o 5 um índice para a frente, como estamos na primeira casa do vetor, paramos. E ficamos com o seguinte.

 C = \{3 ,5 ,6\}

Notem que o que temos é que o inicio do vetor sempre esta organizado dessa forma, e sempre adicionamos um elemento a um vetor organizado. Mas se o elemento que formos adicionar deve ficar na ultima posição, a gente não vai mover nada de lugar, ou seja, vai estar tudo certo e teremos organizado com menos trocas de posição de elementos. Diferente do bubblesort, que tínhamos que comparar o vetor inteiro para garantir que o ultimo elemento é o maior, mas depois temos que refazer varias comparações para garantir que o segundo maior elemento é o penúltimo, ou seja nunca tinha como escapar de comparar tudo com tudo, aqui tem.

Mas talvez vendo uma animaçãozinha fica mais fácil de entender.

Insertion-sort-example-300px

Apesar de parecer complicado, esse é o jeito que a maioria das pessoas organiza cartas na mão, quando a gente quer deixar em alguma ordem. Veja so.

Ok, mas então como fica esse processo no R?

insertionsort<-function(vetor){
    n<-length(vetor)
 
    for(i in 2:n) {
        aux=vetor[i]
        j=i-1
        while(j>=1 && vetor[j]>aux) {
            vetor[j+1]<-vetor[j]
            j=j-1
            }
        vetor[j+1]=aux
        }
    return(vetor)
    }

Bem simples, um loop usando i diz qual o tamanho do vetor que já está organizado, veja que a gente começa do 2, ja que o índice 1 já está organizado, e ai é só salvar a ultima posição, usamos um while para quanto o auxiliar for menor que o valor no vetor ir empurrando ele para a frente e quando isso não é verdade, colocamos o valor que salvamos no auxiliar na posição desejada.

E esse processo funciona que uma beleza.

> vetor<-sample(100) > vetor [1] 78 2 25 43 10 56 8 64 49 41 32 60 59 5 3 38 69 46 13 77 70 57 4 [24] 26 51 45 53 73 85 55 36 66 83 80 61 79 48 50 62 42 35 23 97 19 27 20 [47] 65 94 54 81 1 82 75 93 86 24 71 63 100 34 39 28 6 7 30 33 31 11 72 [70] 18 99 16 17 96 95 52 76 14 89 22 84 98 91 67 37 87 40 88 21 58 92 29 [93] 12 68 15 90 74 47 9 44 > insertionsort(vetor) [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [24] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 [47] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 [93] 93 94 95 96 97 98 99 100

Podemos fazer isso também usando o Rcpp, mas ai é preciso lembrar, que na linguagem C e C++, diferente do R, os índices começam no 0 e não em 1, então o primeiro elemento de um vetor está na posição vetor[1] no R, mas esta na posição vetor[0] no C++.
Com isso em mente, o código é praticamente o mesmo.

library(Rcpp)
cppFunction("
    NumericVector insertionsortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=1;i<n;i++) {
            aux=vetor[i];
            j=i-1;
            while(j>=0 && vetor[j]>aux) {
                vetor[j+1]=vetor[j];
                j=j-1;
                }
            vetor[j+1]=aux;
            }
        return vetor;
        }
")

E funciona legal também.

> insertionsortC(vetor) [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [24] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 [47] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 [93] 93 94 95 96 97 98 99 100

Bem a gente vai ver daqui dois algorítimos de ordenação, se eu continuar fazendo isso, que o que a gente manda para o Rcpp, o código que está entre aspas, pode ser um arquivo texto com o código. E poderíamos mandar mais funções juntas, mas no quicksort a gente vai ver como organizar isso, por enquanto deixa desse jeito que é mais simples.

Mas outra forma ainda de implementar isso é com recursão. A gente ja usou recursão para resolver problemas no Rosalind. Mas basicamente é so chamar a mesma função dentro dela mesma. Um exemplo bem simples é o fatorial.

Fatorial é aquele número que multiplicamos por ele menos 1 até chegar a 1.
Assim,  3!=3 \cdot 2 \cdot 1 e 2 fatorial seria  2!=2 \cdot 1

Então outra forma de escrever isso é  3!=3 \cdot 2!. Fazendo isso até chegar no 1 fatorial, logo no R isso fica assim.

fatorial<-function(n) {
    if(n==1) {
        return(1)
        } else {
            return(n*fatorial(n-1))
            }
    }

Que da.

> fatorial(3) [1] 6

Ou seja, temos um caso base, que é o 1 e vamos fazendo alguma coisa até chegar nessa base.
O insertionsort pode seguir esse raciocínio também da seguinte forma:

cppFunction("
    NumericVector insertionsortRC(NumericVector vetor, int n) {
 
        double aux;
        int i;
 
        if(n>1) {
            insertionsortRC(vetor,n-1);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }
 
        return vetor;
        }
    ")

Que funciona também

> insertionsortRC(vetor,length(vetor)) [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [24] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 [47] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 [93] 93 94 95 96 97 98 99 100

Agora eu so conseguir fazer o insertionsort recursivo fazendo uma função que recebe dois argumentos. Eu até perguntei no stack-overflow aqui se tinha como fazer de outra forma, mas não sei se é possivel, mas tudo funciona de qualquer forma.
Que descobri que não sabia fazer foi fazer o insertion sort de forma recursiva no R. Tem uma pergunta aberta aqui na lista brasilera de r r-br. Se alguém puder me explicar como faz, eu fico grato.

E bem eu acho que é isso, agora temos dois algorítimos de ordenação. Vamos adicionar mais alguns a essa lista e depois será divertido tentar analisar o quão bom cada um é, e quanto…

Bem o script está aqui embaixo além do repositório recologia no github. Até a próxima.

vetor<-sample(100)
vetor
 
insertionsort<-function(vetor){
    n<-length(vetor)
 
    for(i in 2:n) {
        aux=vetor[i]
        j=i-1
        while(j>=1 && vetor[j]>aux) {
            vetor[j+1]<-vetor[j]
            j=j-1
            }
        vetor[j+1]=aux
        }
    return(vetor)
    }
 
insertionsort(vetor)
 
library(Rcpp)
 
cppFunction("
    NumericVector insertionsortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=1;i<n;i++) {
            aux=vetor[i];
            j=i-1;
            while(j>=0 && vetor[j]>aux) {
                vetor[j+1]=vetor[j];
                j=j-1;
                }
            vetor[j+1]=aux;
            }
        return vetor;
        }
")
 
 
 
insertionsortC(vetor)
 
cppFunction("
    NumericVector insertionsortRC(NumericVector vetor, int n) {
 
        double aux;
        int i;
 
        if(n>1) {
            insertionsortRC(vetor,n-1);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }
 
        return vetor;
        }
    ")
 
vetor
insertionsortRC(vetor,length(vetor))
 
fatorial<-function(n) {
    if(n==1) {
        return(1)
        } else {
            return(n*fatorial(n-1))
            }
    }
 
fatorial(3)

Bubblesort em R e C++ usando o pacote rcpp

Opa, a algum tempo atras eu estava olhando como usar funções escritas em C do R, aqui.

Mas como a gente viu la, é um tramite danado tudo isso, desde a parte de escrever o programa, compilar, etc.

Mas o mais complicado, é conseguir fazer a linguagem C entender como está organizado os dados que vem do R, e vice versa. Mas quem viu aquele post, também viu uma alma caridosa que postou no comentario sobre como fazer isso usando o pacote rcpp.

Bem, dando uma olhada como fazer as coisas, parece que nada é tão impraticável assim. Então como uma primeiro olhada, vamos olha um algorítimo chamado bubblesort feito direto no R e usando o rcpp.

Esse algorítimo entra numa categoria que acho que todo livro de algorítimos básico aborda, e realiza uma tarefa básica essencial, organiza um vetor em alguma ordem, aqui a ordem numérica.

Então a gente tem um vetor qualquer, com n elementos.
 C = \{X_1 , X_2 , X_3 , \dots , X_n  \}

E a gente quer que esses elementos fiquem assim:

 C = \{x_1 \leq x_2 \leq x_3 \leq \dots \leq x_n  \}

Ou seja, uma ordem crescente, eles vão ficar organizados dentro do vetor.

Como a gente consegue isso? A gente vai comparando o primeiro com o segundo, se o segundo for menor a gente troca os dois de lugares, senão a gente mantem eles nos mesmo lugares, depois comparamos o segundo com o terceiro, se for diferente trocamos de lugares esses dois, senão mantemos nos mesmo lugares, fazemos isso até chegar na comparação do ultimo com o penúltimo. Depois dessa comparação e troca se necessário, a gente pode fazer uma afirmação quanto a esse vetor, podemos dizer que o ultimo elemento é o maior elemento do vetor, ja que ele foi empurrado la pro fundo, a partir daqui da para pensar que se continuamos fazendo isso agora até o penúltimo, depois até o antepenúltimo, ao chegar na comparação que vai até o segundo termo, temos certeza que todo o vetor está organizado depois disso.

No fim do post tem uma animação para entender melhor, mas vamos ver como fica o código na linguagem R.

bubblesortR<-function(vetor) {
    aux<-numeric()
    for(i in 1:(length(vetor)-1)) {
        for(j in 1:(length(vetor)-i)) {
            if(vetor[j]>vetor[j+1]) {
                aux<-vetor[j]
                vetor[j]<-vetor[j+1]
                vetor[j+1]<-aux
                    }
                }
            }
        return(vetor)
 
    }

Então a gente recebe o vetor, ai veja que o primeiro loop, que usa i, ele vai até o fim do vetor, depois ele vem diminuindo, isso é o que diminuímos no segundo loop que usa j, e dentro desses dois loops tudo que a gente faz é comparar os pares de valores, e se j for menor que o próximo, a gente troca, senão não fazemos nada.

Mas mais fácil é testar a função, então se temos uma vetor desorganizado, com 100 números assim:

> vetor<-sample(100) > vetor [1] 56 89 96 69 37 65 45 74 9 55 84 7 31 92 14 47 41 21 28 11 42 39 19 [24] 64 76 38 22 24 3 85 63 20 53 88 70 59 32 83 82 18 77 57 91 95 73 81 [47] 27 33 17 10 34 100 71 16 23 29 87 35 13 78 43 46 36 52 58 90 60 40 15 [70] 1 4 68 61 94 50 48 67 86 97 66 72 5 6 62 26 99 79 2 54 8 51 98 [93] 93 75 25 80 49 12 30 44

A função vai organizar eles e deixar assim:

> bubblesortR(vetor) [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [24] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 [47] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 [93] 93 94 95 96 97 98 99 100

Legal né, acontece que para fazer isso então, quanto mais números tivermos, mais operações temos que fazer e mais isso demora.

A gente pode na verdade medir o tempo no R usando a função system.time, fazendo algo como um experimento, sorteamos um vetor de números inteiros do tamanho que queremos e ordenamos ele, marcando quanto tempo demora, e a gente pode fazer isso para diferentes tamanhos e ver o que acontece, nesse caso a gente ve o seguinte.

> system.time(bubblesortR(sample(100))) usuário sistema decorrido 0.048 0.000 0.045 > system.time(bubblesortR(sample(1000))) usuário sistema decorrido 4.684 0.004 4.701 > system.time(bubblesortR(sample(5000))) usuário sistema decorrido 116.784 0.172 117.215

Mais ou menos, conforme aumentamos o número de elementos, aumentamos o tempo de execução, mas não linearmente, porque olha so, ao aumentarmos de 100 para 1000, aumentamos uma ordem de magnitude o tempo ali, mas quanto aumentamos em 5 vezes o número de elementos, aumentamos muito mais que 5 vezes o tempo.
Legal né, mas esse não é o foco ainda. Vamos olhar como fazer a mesma coisa no rcpp, usando código na linguagem c++.

library(Rcpp)
 
cppFunction("
    NumericVector bubblesortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=0;i<n-1;i++) {
            for(j=0;j<n-i-1;j++) {
                if(vetor[j]>vetor[j+1]) {
                    aux=vetor[j];
                    vetor[j]=vetor[j+1];
                    vetor[j+1]=aux;
                    }
                }
            }
        return vetor;
        }
")

Bem, o código é bem parecido, so a sintaxe do for que é diferente um pouco e temos que usar uma função para obter o tamanho do vetor, igual quando usamos length no R.
Se usarmos ele no mesmo vetor que criamos antes teremos o mesmo efeito

> bubblesortC(vetor) [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [24] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 [47] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 [93] 93 94 95 96 97 98 99 100

Certo, mas vamos olhar os tempos de execução para matar a curiosidade.

> system.time(bubblesortC(sample(100))) usuário sistema decorrido 0 0 0 > system.time(bubblesortC(sample(1000))) usuário sistema decorrido 0.004 0.000 0.004 > system.time(bubblesortC(sample(5000))) usuário sistema decorrido 0.084 0.000 0.087

São bem menores, isso porque é outra linguagem que é mais rápida que o R, mas como nada na vida é de graça, a gente paga o preço de tudo ser mais complexo de fazer. Complexo no sentido que, pelo menos eu, acho mais fácil escrever as coisas direto no R.

Mas quanto o tempo começar a se mostrar como um empecilho, vale a pensa pelo menos ter idea de soluções possíveis como essa. Existe um tutorial bem bacana aqui sobre como usar o Rcpp, além de um livro do próprio autor que está disponível, e foi publicado esse ano.

Outra coisa é que esse algorítimo é bem lento, mas é interessante pensar como ele funciona, como a descrição sempre é complexa para mim, eu fiz essa animação bem comum em todo post, livro ou sei la quem que está tentando entender o que esta acontecendo numa ordenação.

bubblesort

Bem o script esta aqui embaixo e no repositório recologia, e espero continuar lendo mais um pouco sobre Rcpp e colocando mais coisas aqui, mas aqui ja deu para ter uma ideia, e ver que é bem legal, ja que poupa todo o tramite como visto ao tentarmos usar a função .C
Além de quebrar o recesso sem postar nada, muitas provas ultimamente 🙁

library(Rcpp)
 
cppFunction("
    NumericVector bubblesortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=0;i<n-1;i++) {
            for(j=0;j<n-i-1;j++) {
                if(vetor[j]>vetor[j+1]) {
                    aux=vetor[j];
                    vetor[j]=vetor[j+1];
                    vetor[j+1]=aux;
                    }
                }
            }
        return vetor;
        }
")
 
bubblesortR<-function(vetor) {
    aux<-numeric()
    for(i in 1:(length(vetor)-1)) {
        for(j in 1:(length(vetor)-i)) {
            if(vetor[j]>vetor[j+1]) {
                aux<-vetor[j]
                vetor[j]<-vetor[j+1]
                vetor[j+1]<-aux
                    }
                }
            }
        return(vetor)
 
    }
 
vetor<-sample(100)
 
vetor
bubblesortR(vetor)
bubblesortC(vetor)
 
system.time(bubblesortR(sample(100)))
system.time(bubblesortR(sample(1000)))
system.time(bubblesortR(sample(5000)))
 
system.time(bubblesortC(sample(100)))
system.time(bubblesortC(sample(1000)))
system.time(bubblesortC(sample(5000)))
 
 
vetor<-sample(8)
 
#Animação
num<-1
aux<-vector()
resposta<-logical()
 
for(i in 1:(length(vetor)-1)) {
    for(j in 1:(length(vetor)-i)) {
        num<-num+1
        jpeg(sprintf("bubble%04d.jpg",num), width = 350, height = 350)
        cores<-rep("grey",8)
        cores[c(j,j+1)]<-"blue"
        resposta<-vetor[j]>vetor[j+1]
        barplot(vetor,names.arg = vetor,yaxt="n",col=cores,main=paste(vetor[j],"maior que", vetor[j+1],"?"))
        dev.off()
 
         if(vetor[j]>vetor[j+1]) {
             aux<-vetor[j]
             vetor[j]<-vetor[j+1]
             vetor[j+1]<-aux
             }
 
        num<-num+1
        jpeg(sprintf("bubble%04d.jpg",num), width = 350, height = 350)
        if(resposta==TRUE) {
            cores<-rep("grey",8)
            cores[c(j,j+1)]<-"red"
            barplot(vetor,names.arg = vetor,yaxt="n",col=cores,main=paste("Trocamos",vetor[j],"e", vetor[j+1],"de lugar"))
            }else{
                cores<-rep("grey",8)
                cores[c(j,j+1)]<-"blue"
                barplot(vetor,names.arg = vetor,yaxt="n",col=cores,main="Não trocamos nada")
                }
        dev.off()
        }
    }
 
system("convert -delay 90 bu*.jpg  bubblesort.gif")
system("rm bu*.jpg")

Arduino – Pisca luzes binomial

DSC04419

E mais um pequeno projetinho bem bobo com Arduino.

Domingo, sem nada para fazer, eu tentei ver como faz para ler dados do Arduino no computador.
Na linguagem dele existe um comando Serial e o modelo Uno tem uma porta serial para transmitir ou receber dados do computador, que da para fazer via o cabo usb.

Bem eu fiz um pequeno programinha, ainda de piscar luzes, mas agora eu fiz elas piscarem de forma aleatória. Usando o gerador do números aleatórios que vem no c, o random(), eu gerava um número, ai testava se ele era par ou impar, se for par eu acendo uma luz azul, senão eu acendo a luz amarela no caso de impar. Ele vai ficar no fim do post.

DSC04423

Até ai não tem muita coisa, mas o legal é que agora eu criei duas variáveis, para manter uma contagem de quantas vezes cada luz ficava acesa, depois eu imprimia no monitor do ide do Arduino.

Captura de tela de 2013-06-09 13:53:29

Assim eu conseguia receber um dado direto do Arduino.

Falta aprender melhor como fazer um esquema para o computador ir lendo os dados e salvando num arquivo, isso seria bem útil, e parece que não será uma tarefa muito árdua ja que muita gente quer fazer isso.

Em python, eu vi aqui que existe uma library chamada pyserial exatamente para fazer isso, so que não especifica para Arduino. Na verdade essa é uma pergunta bem recorrente como vemos nos posts aqui e aqui por exemplo, para iniciar.

Bom é isso, bom domingo.

//Apenas para usar um define para aprender, agora toda pausa vale 700
//So mudar o valor aqui para pausas diferentes
#define pausa 700L
 
//Iniciando as variáveis que serão usadas
int carapin = 13 , coroapin = 12 ;
int cara = 0 , coroa = 0 , n = 100 , numero , i;
 
void setup() {
//Aqui a gente inicia tantos os pinos como a porta serial
//para comunicar com o computador
  Serial.begin(9600);
  pinMode(carapin, OUTPUT);
  pinMode(coroapin, OUTPUT);
  randomSeed(analogRead(0));
}
 
// Aqui é o loop que vai ficar em modo infinito.
void loop() {
 
  //Vamos fazer contagens de 100 vezes apenas, para ver o final
  for(i=1;i<=n;i++) {
    //Aqui geramos um número pseudo-aleatório
    numero = random(0,1000);
 
// Se ele for par, a gente acende a luz por 700 milisegundos de pausa
// Mas veja que antes eu incremento o contador de cara
// Imprimo o número de caras e pulo uma linha.
// Aqui eu apanhai um pouco porque achei que tudo era igual o printf do C
    if((numero % 2) == 0) {
      cara++;
      Serial.print("Cara = ");
      Serial.print(cara);
      Serial.print("\n");
      digitalWrite(carapin, HIGH);
      delay(pausa);
      digitalWrite(carapin, LOW);
      delay(250);
    } else {
      coroa++;
      Serial.print("Coroa = ");
      Serial.print(coroa);
      Serial.print("\n");
      digitalWrite(coroapin, HIGH);
      delay(pausa);
      digitalWrite(coroapin, LOW);
      delay(250);
    }
  }
 
//Depois de 100 vezes no loop acendendo e apagando luzes e contando
// Eu imprimo a contagem final de cara e coroa e reinicio as variáveis
// Antes de começar a contar denovo. 
  Serial.print("Final");
  Serial.print("\n");
  Serial.print("Cara = ");
  Serial.print(cara);
  Serial.print(" e Coroa =");
  Serial.print(coroa);
  Serial.print("\n");
  Serial.print("--------------------------");
  Serial.print("\n");
 
  cara = 0;
  coroa= 0;
  delay(1000);
 
}

Arduino

DSC04416

Desde que eu me interessei por evolução, eu comecei a procurar sobre como são os métodos utilizados para conseguir dados para trabalhar com genética e evolução, mais especificamente, como se faz PCR e depois sequência o resultado da PCR, porque esses são os dados que a gente vê nos problemas de bioinformática projeto Rosalind, aquele monte de letrinha que são sequências de DNA, RNA, etc.

Esse tipo de produto, máquinas que fazem PCR, custam uma fortuna, pelo menos eu não tenho condições de comprar, definitivamente um produto que não chega na mão de qualquer curioso. Inclusive é ruim pois, por exemplo no segundo grau ou mesmo na faculdade, quando os Azão azinho da vida poderiam fazer sentido e estudar ser mais legal, tudo que se vê é teoria e um papo sobre ervilha comumente, nada mais.

Fazer PCR depende de um termociclador, um aparelho caro que só grandes empresas produzem e que talvez o preço tenha a ver com a baixa procura, sei-la. Mas procurando sobre termocicladores, eu conheci um projeto chamado Open PCR.

ca5259b3fb380c31847aaa3cd487e6f0-original

Basicamente dois caras ficaram cansados do alto custo para se adquirir um termociclador, e queriam ter um. Viram como faz um termociclador e fizeram o deles em casa. Eles inclusive comentam que uma das motivações, era que eles queriam fazer experimentos com genética, com alunos, tipo ver alguns genes conhecidos relacionados a cor de cabelo, polegar opositor, etc.

A gente raspa a bochecha de todo mundo da sala, coleta material, pega uns primers prontos e outras coizinhas e tenta amplificar esses genes na galera e corre no gel, e isso torna a aula de genética na escola muito mais interessante. Mas tudo empacava nos custos, então eles reduziram os custos construindo o próprio termociclacdor, e agora eles tem uma pequena empresa que vende esses termocicladores por 600 dólares, com o intuito de abrir essa possibilidade a todos.

Mas não para por ai, eles deixam disponível todas as especificações do produto deles, logo, se você produzir as peças, que eles ensinam como, todas as especificações estão abertas, você pode fazer o seu próprio termociclador em casa, ou até melhorar o projeto, um hardware open-source.

Bem isso é algo que chama a atenção, pessoas comuns fazendo algo complexo em casa, como isso é possível?

Foi ai que eu vi que esses caras são na verdade parte de um movimento cultural chamado de Makers.

Esses caras, usaram uma coisa chamada Arduino, que é uma plaquinha com um microcontrolador que da para ligar no computador e programar ele, e ele tanto recebe informação de coisas como manda informação, pro computador ou coisas.

Como assim?

O Termociclador é uma máquina, que tem um sensor de temperatura, uma coisa que esquenta a amostra e outra que resfria. Os caras bolaram um lugar para colocar amostras, um pratinho que recebe amostras, e fizeram um programa que le a temperatura e faz os ciclos da PCR, primeiro esquenta a amostras, ai resfria, pelo tanto de vezes necessários de acordo com o programa, como com o Arduino o computador sabe a temperatura, o Arduino lê um sensor e manda a informação pro computador, o computador pode mandar informação para aquecer ou resfriar com um cooler de computador, e eu não sei o nome da coisinha que esquenta, tornando tudo isso possível.

Pode parecer complexo, mas se você ouvir a historia do porque os caras inventaram a Arduino, você pode mudar de idéia, aqui tem um documentário rapidinho sobre os caras que inventaram o Arduino.

Vale a pena ver, mas denovo a boa historia que nos anima, alguns caras queriam ensinar sobre eletrônica, e como funcionam as coisas. Mas você tem que ver tanta teoria antes de fazer um sistema que pisca uma luz, que desanima todo mundo, um artista por exemplo não quer saber muito de eletrônica para fazer luzes piscarem de forma bonita. Mas eles falaram não, e se a gente conseguir simplificar tudo isso, fazer um sisteminha que você pluga no computador, diz para o microcontrolador o que ele tem que fazer com um programinha e pimba, ta funcionando, assim as pessoas conseguem fazer coisas legais, e isso estimula todo mundo a querer aprender mais para fazer coisas mais legais.

Mas acredito que não imaginaram nas proporções que isso iria tomar, isso virou a diversão de quem queria aprender eletrônica. Mas além disso pessoas começar a refazer produtos que ja existem nas suas casas.

So que no meio científico, alguns caras, como os que fizeram o OpenPCR, tornaram mais barato e talvez mais democrático a ciência.

Mas não para aqui.

Um site chamado Instructables, onde as pessoas podem depositar seus projetos, um cara fez um termociclador que segundo ele da para montar a um custo de 85 dolares. Esse projeto aqui.

FMXHYHAH4AGJRQD.LARGE

Se até agora eu não fui claro, aqui o que aparece é uma oportunidade bem legal, que é uma forma muito legal de coletar dados.

No r-bloggers, eu ja tinha visto alguns caras, como aqui e aqui, que estão conectando o computador com o mundo através do Arduino para coletar dados, e os dados ja caem direto no R, muito legal.

Basicamente você compra um sensor como esse por exemplo.

sku_138531_1_small

Ai você coloca ele no arduino e faz o arduino mandar os dados para o seu computador, sem muito esforço é até possível você colocar um acessório no arduino para ele mandar os dados wireless para o seu computador, so deixar um pilha nele.

So que os tipos de sensores, de coisas que da para medir são imensas, temperatura, umidade, luz, movimento, vibração, coordenadas geográficas, da para medir de tudo com os muitos tipos de sensores ou combinações deles.

sku_142834_1

Agora se você pensa num experimento, como essas coisas são baratinhas e um sensor desse na maioria dos casos não passa de 10 dolares, deve ser muito útil, além de aumentar a quantidade de dados que você pode coletar e a qualidade das medias, ja que sempre tudo é medido por um único coletor, um computador, que você sempre pode verificar e testar a qualidade dos dados que ele entrega. Ele pode ficar coletando dados o tempo que você especificar, até 24 horas por dia.

Eu imagino que um aquário com câmeras registrando o movimento de peixes, ou dados de micro-clima em qualquer lugar, desde a mata até arvores, ou até características limnológicas da água, qual o micro-clima dentro de uma caverna e como isso influência no comportamento de morcegos, você deixa uma caixinha la coletando dados, somado a mais observações pessoais e conhecimento sobre quais são morceguinhos que estão la, deve dar para fazer muita coisa legal.

E grande parte dessas coisas já estão construídas, o trabalho é juntar vários projetos e fazer eles funcionarem juntos a nosso favor, coletando os dados que precisamos para o nosso experimento, e dar um jeito de gravar a informação, seja em memoria, mandar wireless para o conforto da onde você esta, além de manter o conforto do seu objeto de estudo, ja que você não vai estar la atrapalhando os bixinhos.

Além disso, assim como o R, existe uma comunidade gigante trabalhando nisso, então não é algo que você nunca encontrara ninguém para tirar duvidas ou ajudar a construir essas coisas, você não vai embarcar sozinho nisso.

Mas se ainda sim dúvidas forem colocadas sobre a viabilidade disso, até o LHC, o experimento mais caro que eu conheço, que deve juntar os físicos, engenheiros mais fodas do mundo, tem uns Arduinos pelos cantos coletando dados. Olhem o simbolo nessa caixinha, o mesmo da minha plaquinha la do começo do post.

lhcarduino

Então como não pareceu tão difícil assim, até eu fui olhar como é uma plaquinha dessa, comprei uma da china por uns trocados e fui ver como é a idéia disso.

Basicamente você faz um programinha na linguagem C, que não é o C propriamente dito, mas tudo funciona como no C. Fiz um programinha para piscar luzes em sequência. Meu programinha é assim.

/* Piscar luzes do pino 13 a 3 */
 
//inicializa variaveis que vou usar
int i;
int led[11];
 
// A rotina de setup, inicia assim que se aperta o reset da placa
void setup() {               
 
  //Atribui valor aos pinos
  for(i=0;i<=10;i++) {
    led[i] = i+3;
  }
 
  // Inicializa os pinos como saida
 
  for(i=0;i<=10;i++) {
    pinMode(led[i], OUTPUT);
  }
 
}
 
// A rotina de loop que vai rodar para sempre
void loop() {
  digitalWrite(led[0], LOW);
  for(i=1;i<=10;i++) {            // Loop com a luzes indo
    digitalWrite(led[i], HIGH);   // Acende a luz
    delay(500);               
    digitalWrite(led[i], LOW);    // Apaga a luz
  }   
  for(i=9;i>1;i--) {              // Loop com a luzes voltando
    digitalWrite(led[i], HIGH);   // Acende a luz
    delay(500);               
    digitalWrite(led[i], LOW);    // Apaga a luz
  }  
  digitalWrite(led[0], HIGH);     // Antes de recomeçar eu deixo a ultima ligada
}

E o resultado é:
DSC04415

Luzinhas piscando numa sequência que eu determinei, bem bobinho e inútil, mas a possibilidade de coletar dados e guardar pode ser bem inspiradora e animar o aprendizado. As pessoas vão tão longe com essas coisas, que até laser para matar mosquitos, e apenas os que transmitem malaria é possível fazer.
Mas realmente essa parece uma possibilidade bem legal e que pode render alguns frutos legais num futuro, mesmo não sendo algo muito sofisticado ou elegante, quem sabe.
Mas enquanto nada acontece o jeito é continuar estudando. Até a próxima.