Interviewbit Question - Solución al problema de la potencia de dos enteros.

Este es un problema de tipo entrevista, encontrado en interviewbit.com.

El problema nos menciona que debemos encontrar si dada una entrada de tipo entero con signo de 32 bits, podemos representarla cómo sigue: A^B, donde A > 0, y B > 1. Como entrada al algoritmo tenemos un número positivo.

De entrada, sabemos que el número que recibimos es positivo. Los números enteros de 32 bits con signo utilizan un bit dentro de las combinaciones para representar el signo, por tanto el rango de números se reduce a solo 2^31. Eso reduce a la mitad el nivel de posibilidades donde existen la solución.

Ahora, veamos algunos ejemplos y la solución. Recordemos que debemos solo debemos mencionar si  existe el número, por tanto debemos regresar tan solo verdadero o falso, en nuestro caso regresaremos solo un entero, 0 o 1.

Entrada: 9

Salida: 1 

Razón: 3*3 = 9

Entrada: 49

Salida: 1

Razón: 7^2 = 49

Entrada: 729

Salida: 1 

Razón: 7^3 = 7*7*7 = 729

Ahora bien, sabemos que si  Z = A ^ B,  eso quiere decir que si dividimos B veces a Z entre A, nos dará 1. Por ejemplo 729 = 7*7*7, y 729/7/7/7 = 1. Tomemos eso en cuenta. Usaremos el lenguaje Go para la solución de este problema.

Definamos una función isPower que recibe un entero.

IsPower es el método que implementa la solución a nuestro problema.

Ahora bien, podemos obviar la solución más simple, cuando la entrada es 1. Por consecuencia, la respuesta es 1.

Obviamos el caso más simple.

Ahora bien, dado un número, la potencia más grande (o la primera) a la que se puede elevar A antes de sobrepasar el limite es el cuadrado.

Marcamos el límite como el la raíz cuadrada.

Iteraremos uno a uno sobre los exponentes antes del limite, de tal manera que encontremos la solución.

Iteramos para encontrar si el número es solución.

Finalmente, la solución completa que tenemos es:

Solución final.

Si te queda alguna duda o tienes alguna solución parecida, no dudes en comentarla.

Algoritmos HASH: Usando las herramientas en GNU/Linux para verificar archivos.

Las funciones hash o funciones de una sola vía.

Las funciones hash o funciones de una sola vía son algoritmos que generan una representación única e inequívoca de un objeto; dada una mensaje de entrada, genera un código de salida que representa de manera única al mismo. Si te has fijado, quizás has notado que cuando descargas un archivo de alguna página web algunas veces el autor te deja los valores hash generados por distintos algoritmos; en particular, se hace referencia a estos 'códigos' como las sumas de verificación de los archivos. 

Se les llama algoritmo de una sola vía, porque no hay manera de regresar de un valor hash a su valor original a diferencia, por ejemplo, de algoritmos de cifrado donde existe una 'trampa' que permite descifrar el mensaje (Estrictamente hablando, no hay comprobaciones matemáticas que verifiquen que, efectivamente, es imposible obtener el valor original a través de su hash). Otra característica importante a agregar es que estas funciones deben estar libres de colisiones; una colisión implica que, dados dos mensajes distintos a la entrada de un algoritmo hash tendrán el mismo hash resultante.

Pero ¿por qué son importantes los hash? La importancia de estos algoritmos hash viene de sus posibles aplicaciones; existen distintas pero en esta ocasión nos concentraremos en una en especifíco: verificación de integridad o sumas de verificación. Como se mencionó anteriormente, las páginas webs suelen poner junto a sus enlaces de descarga los valores hash de los archivos, ésto lo hacen con el fin que puedas verificar la integridad del archivo; en otras palabras, para verificar si el archivo ha sido modificado con fines maliciosos (por ejemplo, le hayan inyectado algún software malicioso), te lo hayan cambiado a la hora de descargarlo o simplemente el archivo se haya dañado o vuelto corrupto debido a algún error en la descarga o a errores en el sistema de archivos de tu sistema operativo.

Existen distintas familias de funciones hash hoy en día, pero algunas de propósito general son:

• MD4(128) - No se recomienda usar
• MD5(128) - No se recomienda usar
• SHA-1(160) - No se recomienda usar
• SHA-2 (224, 256)
• SHA-3 (224, 256, 384, 512)

Ya no se recomienda el uso de algunas (como se etiqueta en la lista anterior), debido a que se ha demostrado que, bajo ciertas condiciones, se pueden forzar las colisiones.

Verificación de mensajes en GNU/Linux.
Usaremos rhash como nuestra herramienta en línea de comandos para verificar nuestros mensajes. El uso de la aplicación es sencilla y puede calcular sumas hash de varias familias, incluidas SHA.

Para nuestro ejemplo, creemos un archivo de texto y pongamosle un texto. 

Figura 1: Ejemplo de texto.

A continuación, ejecutemos el comando rhash junto con el nombre de nuestro archivo.

Figura 2: Suma de verificación en formato SVF (simple verification format).

Vemos como nuestro mensaje ha dado el valor hash 51DB575A. Por defecto, rhash nos da el valor en formato SFV con una CRC-32. 

Veamos ahora cual es la suma de verificación usando SHA-256:

Figura 3: Suma de verificación usando SHA-256.

Probemos ahora una sola letra en nuestro texto.

Figura 4: Texto cambiado.

Corramos de nuevo el programa y miremos el resultado. 

Figura 5: Resultado de la suma de verificación con el texto modificado.

Comparemos ambos hashes y veamos que dada un pequeño cambio genero un cambio muy marcado; los valores hash son completamente distintos.

Podemos ver que las  funciones hash son herramientas bastante poderosas y forman parte del día a día en el mundo del internet y la seguridad.

Emacs Lisp - Función/comando para reemplazar coincidencias de texto.

Una de las grandes ventajas de la utilización del editor Gnu Emacs es su capacidad para extender las funciones del mismo editor a través de elisp.

 Para empezar a adentrarme en el lenguaje, decidí escribir una pequeña función que me ayudara a rápidamente cambiar todas las coincidencias de una cadena de texto en un buffer.  A continuación, explico como lograr esto de manera sencilla.

Funciones y sus argumentos.

Para definir una función en elisp, usamos la siguiente palabra (o símbolo, para ser más correcto según lisp):

defun 

Simplemente una abreviación de "define function". Este símbolo le dice a lisp, que el consecuente código dentro de la lista definida sea enlazado a otro símbolo: el nombre de nuestra función. Por ejemplo:

(defun suma (x y)
      (+ x y)
) 

¿Qué hace esta función? Es simple. Toma dos argumentos recibidos y los suma. En otras palabras, enlaza el símbolo "suma" con el código consecuente dentro de la función, el de la suma.

Ahora bien, observemos que después de la definición del nombre de la función viene otra lista. Esta es la lista de los parametros a usar en nuestro función y que deben ser pasados al momento de llamarla. Por ejemplo, evaluemos la siguiente función:

(suma 3 4)

Deberá imprimirse en nuestro mini-buffer el número 7.

La función interactive.

La función interactive hace que nuestra función pueda volverse un comando (pueda ser llamada con M-x/alt-x). Distintos argumentos dados a nuestra función, le dan distintos comportamientos a la llamada de nuestro comando/función.

Para nuestro caso, usaremos el argumento "s", como argumento de interactive. Este argumento, leerá del minibuffer y lo guardará en nuestra lista de argumentos dados a la función.

La función save-excursion.

Esta función nos permitirá guardar la posición actual del cursor (su punto, de acuerdo a la terminología de emacs). Esto debido a que mientras cuando se haga la búsqueda y reemplazo, el punto/point/cursor estará moviendose a través de todo el texto. Para evitar que, al usar la función, nos deje en donde no estabamos colocados usamos save-excursion.

La función beginning-of-buffer.

Retorna el cursor al principio del buffer.

re-search-forward, regexp-quote y replace-match.

Estas tres funciones son las que harán el trabajo fuerte de nuestro comando. 

re-search-forward nos moverá a través de las coincidencias del texto, como un puntero. Al ser llamada, regresará la ubicación de la coincidencia, en la siguiente iteración nos dará la siguiente coincidencia.

regexp-quote: Le daremos un string de argumento y nos retornará la forma de evaluar el string como si fuera una expresión regular.

replace-match: La llamamos para reemplazar la coincidencia que teníamos con re-search-forward dandole el string a reemplazar.

 Nuestra función: replace-all-ins-of.

(defun replace-all-inst-of (x y)
  ;; pregunta por los argumentos
  (interactive "sSearch (with regexp): \nsReplace: ")
  (save-excursion ;; guardar el actual punto
    (beginning-of-buffer) ;; moverse al principio del buffer 
    ;; Empezar la busqueda hacia adelante
    (while (re-search-forward (regexp-quote x) nil t)
      (replace-match y))
    )
  )

Evaluamos la función al ponernos al final de la misma y haciendo Ctrl-x CTRL-e. Esto también agregará nuestra función a los comandos de emacs.

Finalmente para probar la función, hacemos M-x replace-all-inst-of o ALT-x replace-all-inst-of.

Cabe destacar que para "instalar" de forma permanente nuestra función como un comando necesitamos guardarlo en nuestro archivo de inicio .emacs. De esta manera, siempre estará disponible en las siguientes sesiones de nuestro editor.

Obtener el ensamblador de un programa en C en Linux.

El otro día me dio curiosidad de ver como se veía las instrucciones en ensamblador de un programa sencillo en C, en Linux. A continuación, muestro el ejemplo que hice de manera sencilla.

Código en C:

Yo decidí, para empezar con algo simple, hacer el dump de un pequeño código usando una sentencia for:

1 2 3 4 5 6 7

#include <stdio.h> int main() { int i; for(i = 1; i <= 10; i++); return 0; }

Nombramos el archivo como main.c

Escribiendo el Makefile 

Para evitarnos el gran trabajo de escribir dos comandos, realizaremos un archivo Makefile que corra automáticamente los comandos con las flags necesarias.

1 2 3

all: gcc -g -c main.c -fverbose-asm -O0 objdump -d -M intel -S main.o

Cabe destacar que objdump obtendrá el código ensamblador con una sintaxis de intel, como se específica en el flag -M intel; si se desea obtener con otra sintaxis, debe buscarse en la manual del comando.

Obteniendo el ensamblador:
Corremos el siguiente comando:

1

$ make

Y se nos mostrará en la terminal el ensamblador resultado de nuestro código, para este caso específico:

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

gcc -g -c main.c -fverbose-asm -O0 objdump -d -M intel -S main.o main.o: formato del fichero elf64-x86-64 Desensamblado de la sección .text: 0000000000000000 <main>: #include <stdio.h> int main() { 0: 55 push rbp 1: 48 89 e5 mov rbp,rsp 4: 48 83 ec 10 sub rsp,0x10 int i; for(i = 1; i <= 10; i++); 8: c7 45 fc 01 00 00 00 mov DWORD PTR [rbp-0x4],0x1 f: eb 04 jmp 15 <main+0x15> 11: 83 45 fc 01 add DWORD PTR [rbp-0x4],0x1 15: 83 7d fc 0a cmp DWORD PTR [rbp-0x4],0xa 19: 7e f6 jle 11 <main+0x11> i++; 1b: 83 45 fc 01 add DWORD PTR [rbp-0x4],0x1 foo(); 1f: b8 00 00 00 00 mov eax,0x0 24: e8 00 00 00 00 call 29 <main+0x29> return 0; 29: b8 00 00 00 00 mov eax,0x0 } 2e: c9 leave 2f: c3 ret

Cualquier duda, comentario o sugerencia es bienvenida en los comentarios!

Encender y apagar un led con Android y Raspberry Pi

Hace poco pude hacerme con un dispositivo Android y decidí empezar a sacarle un poco de jugo. A continuación, les muestro y explico, lo más claro posible, el resultado.

Objetivo:

Comunicar un dispositivo Android y una Raspberry Pi por medio de sockets para encender y apagar un led a través de la red local usando.

Materiales:

- 1 LED

- Raspberry Pi [Cualquier modelo]

- Resistor 330 Ohms

- Protoboard

- Jumper Hembra Macho [para la conexión Raspberry Pi a protoboard]

Breve explicación:
El método usado para la comunicación entre los dispositivos esta vez fueron los sockets.
La Raspberry Pi corre un pequeño script en python que está a la espera de una conexión entrante, que en nuestro caso sería el dispositivo Android. Cuando recibe una conexión, la RPi crea un nuevo socket, un canal de comunicación, donde recibe un caracter enviado por el dispotivo Android. Hay dos posibles caracteres que pueden ser enviados, 'A' o 'B'. Si se recibe A, el LED enciende; con B, éste se apaga.

En la aplicación en Android, tenemos tres elementos sencillos: dos campos de texto y un botón. El primero para la IP de la RPi, el segundo para el puerto (Nota: El número de puerto debe ser el mismo que el declarado en el script de la RPi, y se recomienda uno que sea distinto a los reservados para otras conexiones. En este caso, yo opté por el puerto 1000) y, finalmente, el botón de On/Of. Este botón es el encargado de llamar a la función que tratará de conectarse a la RPi y enviar los datos. El socket se destruye al finalizar la comunicación, así que cada vez que presionamos el botón se crea uno nuevo.

Ejemplo de uso:

Esquemático y conexiones:
No he podido crear un esquemático por falta de tiempo, en cuánto pueda lo haré.

El LED se conecta al resistor de 330 Ohms y ésta está conectada al GPIO 17 de la RPi, el número de pin puede ser cambiado por cualquier otro disponible. El cátodo del LED se conecta a algún pin GND de la RPi.

Esquemático de GPIO:
http://www.peatonet.com/wp/wp-content/uploads/2014/08/PinoutRaspberry-1.jpeg 

Proyecto en Android Studio:
1. Crea una nuevo proyecto en Android Studio que tenga una actividad en blanco. Elige el SDK al que quieras compilar la aplicación.

2. Modifica el AndroidManifest.xml agregando los siguientes permisos:

<uses-permission android:name="android.permission.INTERNET" >
</uses-permission>
<uses-permission android:name="android.permission.ACCESS_NETWORK_STATE" >
</uses-permission>

3. Modifica el archivo xml de tu actividad prinicipal de la siguiente forma:

<RelativeLayout  xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" 
 android:layout_width="match_parent"
 android:layout_height="match_parent" 
 android:paddingLeft="@dimen/activity_horizontal_margin"
 android:paddingRight="@dimen/activity_horizontal_margin"
 android:paddingTop="@dimen/activity_vertical_margin"
 android:paddingBottom="@dimen/activity_vertical_margin" 
 tools:context=".Main"
 android:id="@+id/relativeLayout">
  <EditText   android:layout_width="match_parent"   android:layout_height="wrap_content"
   android:hint="Introduzca la ip"
   android:inputType="numberDecimal"
   android:digits="0123456789."
   android:id="@+id/editText1" />
  <EditText   android:id="@+id/editText2"   android:layout_width="match_parent"
   android:layout_height="wrap_content"
   android:hint="Introduzca el puerto"
   android:inputType="number"
   android:layout_below="@+id/editText1"
   android:layout_alignParentStart="true" />
  <Button   style="?android:attr/buttonStyleSmall"   android:layout_width="200dp"
   android:layout_height="wrap_content"
   android:text="On/Off"
   android:id="@+id/buttonLed"
   android:layout_alignParentTop="true"
   android:layout_centerHorizontal="true"
   android:layout_marginTop="201dp"
   android:onClick="togLed"
  />
</RelativeLayout>

4.  Modifica tu actividad principal con el siguiente código:

import android.support.v7.app.ActionBarActivity;
import android.os.Bundle;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;

public class Main extends ActionBarActivity {
    private LedToggle ledToggle;
    private boolean ledState = true;
    private Button button;
    private EditText ipText;
    private EditText portText;
    @Override    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        button = (Button) findViewById(R.id.buttonLed);
        ipText = (EditText) findViewById(R.id.editText1);
        portText = (EditText) findViewById(R.id.editText2);
        }

    @Override    public boolean onCreateOptionsMenu(Menu menu) {
        getMenuInflater().inflate(R.menu.menu_main, menu);
        return true;
    }

    @Override    public boolean onOptionsItemSelected(MenuItem item) {
        int id = item.getItemId();
        if (id == R.id.action_settings) {
            return true;
        }

        return super.onOptionsItemSelected(item);
    }

    public void togLed(View view) {
        try {
            String ipAddr = ipText.getText().toString();
            int nPuerto = Integer.parseInt(portText.getText().toString());
            if (ledState == false) ledState = true;
            else ledState = false;
            ledToggle = new LedToggle(ipAddr, nPuerto);
            ledToggle.execute(ledState);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

5. Crea una nueva clase que será el controlador encargado de enviar los datos y pedir conexión a la RPi, llamada LedToggle. Esta clase extiende de AsyncTask, para poder manejar la petición en un hilo distinto al principal.

import android.os.AsyncTask;

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.net.Socket;

/** * */public class LedToggle extends AsyncTask<Boolean, Void, Void>{
    private Socket socket = null;
    private OutputStream outputStream = null;
    private String sockeAdd = null;
    private int portNum;

    public LedToggle(String s, int p) {
        sockeAdd = s;
        portNum = p;
    }

    @Override    protected Void doInBackground(Boolean... params) {
        try {
            socket = new Socket(sockeAdd, portNum);
            outputStream = socket.getOutputStream();

            if(params[0] == true)
                outputStream.write('A');
            else                outputStream.write('B');
            outputStream.close();
            socket.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }


}

6. El siguiente script de python debe estar corriendo en la Raspberry Pi.






Más adelante escribiré un post explicando más a detalle los temas. Cualquier duda, sugerencia o comentario son bienvenidos :-D