Referencias a variables y arrays en PHP

PHP sigue muchas de la reglas de C, por lo que no podía faltar la referencia. Veamos un ejemplo ilustrativo, tenemos un array de elementos y queremos recorrerlo realizando modificaciones a medida que lo hacemos. La función preferida para esto es foreach, pero al hacerlo trabajamos sobre una copia de la variable, por lo que al salir del bucle nuestros cambios desaparecen.

Un primer intento podria ser este:

if (!empty($data['noticias'])) { foreach ($data['noticias'] as $each) {

$each['fechaactual'] = date(“Y-m-d h:i:s”);

} }

Para solucionar esto usamos una referencia:

if (!empty($data['noticias'])) { foreach ($data['noticias'] as $k=>$v) {

/* Creamos la referencia en la posición actual */
$pointer =& $data['noticias'][$k];

/* Hacemos cambios en el arreglo original */
$pointer['fechaactual'] = date(“Y-m-d h:i:s”);

} }

Campos adicionales personalizados para usuarios en Wordpress

Muchas veces en nuestro sitio queremos poder agregar campos personalizados para los usuarios. Ya sea un número de facturación, direcciones, tipo de cliente o una cuenta de twitter.

A pesar de que Wordpress no trae aún en forma nativa la gestión de campos personalizados para usuarios (en la versión actual, 2.9.2), podemos hacer una pequeña modificación en nuestro archivo functions.php del theme.

Abrimos el archivo mencionado y simplemente agregamos el siguiente código:

<?php
/* Con este bloque mostramos en el admin el campo adicional en el admin */

add_action( ’show_user_profile’, ‘my_show_extra_profile_fields’ );
add_action( ‘edit_user_profile’, ‘my_show_extra_profile_fields’ );

function my_show_extra_profile_fields( $user ) { ?>

<h3>Datos adicionales</h3>

<table>

<tr>
<th><label for=”escliente”>Es cliente?</label></th>

<td>
Si <input type=”radio” name=”escliente” id=”escliente” value=”si” <?php if (esc_attr( get_the_author_meta( ‘escliente’, $user->ID )) == “si”) { ?> checked=”checked” <? } ?> >
No <input type=”radio” name=”escliente” id=”escliente” value=”no” <?php if (esc_attr( get_the_author_meta( ‘escliente’, $user->ID )) == “no”) { ?> checked=”checked” <? } ?> >
</td>
</tr>

</table>
<?php } ?>
<?php
/* Este bloque actualiza el campo al guardar los cambios */

add_action( ‘personal_options_update’, ‘my_save_extra_profile_fields’ );
add_action( ‘edit_user_profile_update’, ‘my_save_extra_profile_fields’ );

function my_save_extra_profile_fields( $user_id ) {

if ( !current_user_can( ‘edit_user’, $user_id ) )
return false;

/* Actualizamos cada campo adicional con su ID */
update_usermeta( $user_id, ‘escliente’, $_POST['escliente'] );
}
?>

Luego para ver en el sitio público los campos adicionales podemos hacerlo de la siguiente forma:

<?php if ( get_the_author_meta( ‘escliente’ ) ) { ?>
<p> Es cliente: <?php the_author_meta( ‘escliente’ ); ?></p>
<?php }  ?>

Micropagos en Juegos y Juegos en todo

Dando un vistazo a las tendencias de juegos, servicios de celulares y demás aplicaciones de ocio como pueden ser trivias, sorteos, etc. se puede ver una tendencia clara hacia la interacción constante con el usuario. Cada vez se requiere una respuesta más elaborada a estas aplicaciones, lo cual nos lleva a invertir más tiempo y a darle una importancia relativa mayor en nuestra vida. El resultado, una vez que estamos participando no podemos dejar de hacerlo.

Los juegos online como Mafia, Farmville y otros están marcando el camino para las nuevas generaciones de entretenimiento. Juegos donde participas con tus amigos, donde tu grupo social está incluído y compartes pero sobre todo compites con tus conocidos. Una vez que tenemos nuestra granja y vemos la de nuestros amigos, queremos una mejor, invertimos más tiempo y esto alimenta el círculo para que sigamos en él.

Claro que en caso de que no tengamos el tiempo suficiente para construir paso a paso nuestra granja podemos gastar unos pocos dólares y nos ahorramos el tiempo… O si estamos en el Mafia podemos comprar lo que otros tienen y se han ganado con tiempo. ¿Qué padre le negaría unos dólares a su hijo que ha estado tan tranquilo con ese juego las últimas semanas?

Esto nos lleva a los micropagos. Los micropagos son pagos de un dólar por ejemplo, que se puedan hacer al instante y con un servicio de celular o a través de Paypal, con comisiones mínimas que permiten que el pago sea rentable. Este eslabón posibilita la creación de aplicaciones que requieran de pagos mínimos para obtener resultados rápidos, creando un abanico hasta ahora inexplorado para compras en Internet, el público en general que no cuenta con tarjetas de crédito.

Es de suponer que los micropagos sean el próximo paso a dar por parte de Facebook, en su intento de crear una red cerrada o Internet propia, donde otras grandes companías como Google no puedan participar ni interferir, y donde los usuarios no tengan la necesidad de salir de esta red.

Sumando micropagos, celulares, juegos en celulares y el día de mañana juegos en la TV, en la calle, en discotecas y pubs podemos imaginar un futuro donde participar en juegos, compartiendo y compitiendo con nuestros amigos y contactos de redes sociales sea la norma. Y a falta de tiempo podamos gastar unos pocos dólares para estar en el msmo nivel sin tener que invertir tiempo.

Hosting para diseñadores y revendedores

Presentamos una solución ideal para diseñadores y revendedores que necesitan alojar dominios y obtener el mejor beneficio de los sitios. El plan de alojamiento web ofrecido por Trepcom Technologies incluye además de todas las funcionalidades modernas, soporte técnico y asesoramiento para comprar dominios, configurar sitios y optimizar con SEO.

Nuevos planes de Hosting para diseñadores y revendedores Recibidos X Responder | Nicolás Rodríguez Medeyros para usuario mostrar detalles 17:14 (14 minutos antes) Estamos lanzando nuevos planes de hosting para diseñadores y revendedores. La idea es que te puedas olvidar de problemas de hosting y sacarle un mayor margen al alojamiento de los sitios. Todas las consultas tecnicas y soporte lo damos nosotros, casillas de correo, cuentas de ftp, bases de datos, etc. Estos serian los dos planes basicos: Plan Diseñador/Programador: U$S 100 por año 500 MB en disco 25 GB de trasnaferencia mensual 10 dominios 10 bases de datos Plan Avanzado: U$S 200 por año 1000 MB en disco 100 GB de transferencia mensual 25 dominios 25 bases de datos Funcionalidades incluidas en ambos: PHP 5 Mysql 5 Acceso FTP Estadisticas de trafico 50 casillas de correo con antivirus, antispam y espacio ilimitado (7GB aprox. cada una) Soporte para configuracion de sitios, compra de dominios y administracion. Cualquier consulta a las ordenes! Folleto Plan de hosting.jpg 125 K   Vista Descargar Responder Reenviar Responder | Trepcom Technologies para bcc: Agustin, bcc: Gaston, bcc: Alvaro, bcc: Pablo, bcc: Federico, bcc: Martin, bcc: Adolfo, bcc: Matias, bcc: Javier, bcc: Ana, bcc: Mauro mostrar detalles 17:18 (10 minutos antes) Estamos lanzando nuevos planes de hosting para diseñadores y revendedores. La idea es que te puedas olvidar de problemas de hosting y sacarle un mayor margen al alojamiento de los sitios. Todas las consultas tecnicas y soporte lo damos nosotros, casillas de correo, cuentas de ftp, bases de datos, etc. Estos serian los dos planes basicos: Plan Diseñador/Programador: U$S 100 por año 500 MB en disco 25 GB de trasnaferencia mensual Alojamiento para 10 dominios 10 bases de datos Plan Revendedor: U$S 200 por año 1000 MB en disco 100 GB de transferencia mensual Alojamiento para 25 dominios 25 bases de datos Funcionalidades incluidas en ambos: PHP 5 Mysql 5 Acceso FTP Estadisticas de trafico 50 casillas de correo con antivirus, antispam y espacio ilimitado (7GB aprox. cada una) Soporte para configuracion de sitios, compra de dominios y administracion. Cualquier consulta a las ordenes! Enrique Techera Folleto Plan de hosting.jpg 125 K   Vista Descargar Responder Reenviar

Herramientas esenciales para trabajadores freelance e independientes, administración de tiempo, finanzas y tareas.

Cuando trabajamos como freelance o bien en un grupo independiente nos enfrentamos a muchas tareas administrativas y de monitoreo que pueden ser tediosas. Es importante llevar una agenda de clientes, seguimiento de proyectos, colaboración con otras personas, finanzas, entre otros.  Muchas veces perdemos de vista estas tareas por algunos dias o semanas y luego tenemos un problema ya que no sabemos con exactitud que cliente nos tiene que pagar, que fechas manejamos para los proyectos, etc.

Por suerte existen muchas herramientas online para hacernos la vida más fácil:

Administración de proyectos

• http://www.writeboard.com – Una simple pizarra en blanco para dejar comentarios.
• http://www.tadalist.com – Lista de tareas para realizar.
• http://basecamphq.com – Un poderoso gestor de proyector, recomendado si debemos trabajar en equipo.

Administración de clientes

• http://www.highrisehq.com – Complejo administrador de clientes con todo detalle.
• http://www.google.com/a/smallbiz – Herramienta de Google para compartir documentos y contactos en línea.
• http://www.feelbreeze.com – Envío masivo de correos.

Finanzas

• http://www.freshbooks.com – Administrador con versión gratuita.
• http://invoice.zoho.com – Potente administrador, genera balances, reportes, etc.
• http://www.lessaccounting.com – Gestor recomendado de finanzas.

Recursos: desarrolladores

• http://www.my-debugbar.com/wiki/IETester/HomePage – Prueba tu sitio en todas las versiones de Internet Explorer.
• https://addons.mozilla.org/en-US/firefox/addon/60 – Herramienta para diseñadores web, plugin de Firefox.
• https://addons.mozilla.org/en-US/firefox/addon/1843 – Potente depurador para desarrolladores, plugin de Firefox.

Recursos: tipografías

• http://www.dafont.com – Uno de los mejores sitios de fuentes.
• http://www.smashingmagazine.com/2007/08/08/80-beautiful-fonts-typefaces-for-professional-design – Tipografías de alta calidad.
• http://www.fonttester.com/ – Compara distintas fuentes.

Recursos: menús css

• http://css.maxdesign.com.au/listamatic/ – Colección de scripts.
• http://www.dynamicdrive.com/dynamicindex1/indexb.html – Colección de menús.
• http://www.accessify.com/tools-and-wizards/developer-tools/list-o-matic/ – Crea tus propio menús.

Recursos: colores

• http://www.colorschemer.com/schemes/ – Elige una paleta de colores.
• http://kuler.adobe.com – Potente herramienta de Adobe para elegir colores.
• http://www.colorjack.com/sphere/ – Rápida herramienta para seleccionar una paleta.

Recursos: Fotos

• http://www.sxc.hu/ – Stock de fotos gratuitas.
• http://www.dreamstime.com/ – Fotos casi gratuitas.
• http://www.veer.com/ – Sitio para fotos de alta calidad.

Creando una startup/empresa propia, toma de decisiones, ideales y objetivos

Crear una empresa propia es algo simple y complicado a la vez. Depende en gran parte de nuestra capacidad de elegir bien algunos elementos al comenzar la misma y durante el proceso no equivocarnos demasiado. Fallar en el intento es la norma y nunca es el momento ideal para lanzarse al agua. Es una cuestión de determinación frente a una situación que presente ventajas.

Por lo general no se necesita una idea revolucionaria para tener éxito, únicamente necesitamos una idea clara de lo que buscamos y la determinación para llevarlo adelante. Esta determinación no se debe confundir con rigidez.

Debemos estar preparados cada día para cambiar el rumbo y ajustarnos a las necesidades y oportunidades de nuestros clientes y mercado. Reinventar la empresa sin miedos, como norma base.

Puede sonar contradictorio, pero uno de los factores clave de las startups es la capacidad de maniobra frente a situaciones complejas, a diferencia de empresas grandes donde las decisiones deben enfrentar la inercia propia de sus directores y empleados.

El tema de directorios nos lleva al siguiente punto, la elección de los socios al momento de crear la empresa.

Es fundamental contar con socios al momento de iniciar el proyecto, para intercambiar ideas, ampliar la red de contactos de la empresa y lograr una motivación extra.

Un fundador solitario se enfrenta a retos enormes, como la visión de una única perspectiva de los problemas, asi como la limitación en las tareas que puede realizar en paralelo. Si se trata de una empresa de tecnología es probable que uno de los fundadores cuente con la capacidad técnica, mientras otro se pueda especializar en las ventas.

El financiamiento de la startup suele ser más sencillo si se cuenta con varios socios, pudiendo repartir la carga entre varios para no comprometer la situación económica que obligue a cancelar el proyecto. Este financiamiento por lo general surge de ahorros generados en un trabajo previo. Contar con una reserva inicial para un plazo de 6 meses a 1 año es imprescindible en una empresa nueva.

Por lo general los primeros meses de estado embrionario de la empresa se recorren en paralelo a un trabajo tradicional, tanteando el terreno, desarrollado las herramientas necesarias y conociéndose con los potenciales socios. El problema llega, o mejor dicho, no llega, hasta que se toma la decisión de cortar el cordón umbilical y lanzarse adelante.

El momento de lanzarse al agua nunca es ideal, siempre se pueden intentar mejores condiciones, lo cual aún antes de comenzar define el grado de temeridad y ejecutividad del directorio.

Una vez en el agua con nuestros socios, el grado de compromiso no puede fallar. La decisión de dedicarse fulltime a la empresa es crítica, así como la capacidad de enfocarse en las ventas y en nuestro producto. En la actualidad contando con un sitio web, número de teléfono y una presencia corporativa profesional (logo, tarjetas, etc) no necesitaremos mas que una simple oficina que genere gastos mínimos. El personal de la empresa puede consistir de un núcleo duro de socios fulltime y una red de personas de confianza para trabajos específicos, sin necesidad de tomar gastos grandes que nos comprometan.

La oficina debe contar con instalaciones básicas pero enfocadas en maximizar la productividad, ya sea en equipos actuales, escritorios y sillas adecuadas, buena iluminación y un ambiente agradable. Existe la tendencia en la actualidad y gracias a la tecnología a dar flexibilidad en horarios y forma de trabajo. Esto se puede lograr mediante acceso remoto a la red, laptops y sitios web para administración de proyectos. De acuerdo a las características del personal esto tendrá un grado mayor o menor de éxito. Algunas personas logran el balance por si mismos, mientras que otros necesitan al menos una estructura básica de horarios para mantener el ritmo.

Crear una cultura de ahorro y eficiencia desde el primer día es importante, si la empresa logra crecer y obtener un financiamiento externo puede caer en el derroche. Es fácil sentir que el dinero sobra al lograr una inversión o grandes ventas. La reinversión productiva debe estar anteo todo, cada dólar gastado debe provocar más ventas o mejoras de producto.

Durante la etapa de pequeña empresa puede regir un sistema simple de reparto por rendimiento, de forma de motivar al desempeño excepcional y lograr la sana competencia entre los miembros. La etapa de dedicación extrema y uso de reservas no dura para siempre, ya sea por falta de fondos como por agotamiento de las personas.

Lograr ventas es un proceso que puede tomar meses, construir redes de clientes paso a paso de forma que los clientes mismos hagan el trabajo por nosotros en el futuro mediante recomendaciones. Este flujo de clientes es necesario para la supervivencia de la empresa, contando con personal especializado en las ventas y clientes, preferentemente con alguno de los socios como vendedor ya que el compromiso va más allá del sueldo que reciba.

Vender la piel del oso antes de tenerla, puede ser la diferencia entre la mera supervivencia de la empresa y el éxito.

Conociendo nuestro producto y nuestras limitaciones, podemos complementarnos con el trabajo o servicio de otras empresas, que nos den lo que por tiempo o dinero aún no somos capaces de generar nosotros mismos. De esta forma podemos construir un producto mucho más complejo y útil de lo que lograríamos con algo completamente “artesanal”. Como parte de la preparación de la empresa debemos conocer las empresas que pueden aportarnos estos complementos.

La venta del producto estrella puede ser un fracaso rotundo, para lo cual debemos estar preparados a reinventarnos. Si vendemos equipamiento necesitaremos contar con stock, personal calificado en el manejo del mismo y una cadena logística. Algunos pasos se pueden complementar con otras empresas, aunque recurrirán en costos mayores, por lo que el volumen suele ser crítico en este tipo de empresa. Por su parte vender conocimientos o servicios requiere de la capacidad técnica, personal calificado y acumulación de experiencia en el área.

Por regla general nuestros productos se deben basar en nuestras áreas de conocimiento experto, lo cual nos lleva a la necesidad de investigar e innovar constantemente para poder adaptarnos.

A medida que se desarrolla el proceso de crecimiento se pueden plantear momentos de extrema tensión entre los socios. Contar con los ambientes adecuados para evitar la acumulación de tensiones es importante. Reuniones semanales donde realizar balances e intercambiar ideas pueden evitar un desastre a largo plazo.

Aún así los socios no están casados de por vida, con el tiempo se puede perder el interés y se deben seguir caminos separados.

Probablemente lo más difícil es decidir cómo hacerlo sin dañar la empresa. Por esta razón es que se debe buscar siempre una separación en buenos términos, manteniendo el equipo de trabajo unido.

En el ideal los socios deberían mantener un contacto estrecho, ya que es probable que en un futuro tengan servicios o compañías complementarias para trabajar.

Algoritmo de Backtracking en C/C++, formalización e implementación

Veamos un ejemplo típico de algoritmo de Backtracking. Tenemos una serie de elementos únicos, cada uno con un peso o volumen ocupado, y cada elemento a su vez nos da cierta ganancia. Disponemos de una capacidad limitada por lo que debemos seleccionar de los elementos disponibles aquellos que nos den la mayor ganancia posible.

Supongamos que tenemos n elementos disponibles, numerados de 0 a n-1 y dos arreglos, uno p[n] que indica el peso de cada elemento y g[n] que indica la ganancia que nos da el elemento. M indica la carga máxima que podemos llevar. Debemos buscar elegir los elementos que nos den la mejor ganancia dado el espacio que ocupan.

Con estos datos pasemos a formalizar el problema.

Forma de la solución: Utilizaremos una tupla de largo n <x0,x1,…,xn-1>, donde cada elemento xi indica con 1 si llevamos el elemento i, o con 0 si no lo llevamos.

Reestricciones Explícitas: Cada elemento xi de la tupla se corresponde con un elemento i disponible.

Reestricciones Implícitas: La sumatoria de los pesos de los elementos seleccionados no superan la capacidad disponible M.

Función Objetivo: Maximizar la ganancia.

Predicados de Poda: Supongamos que en un momento dado encontramos una solución M_sol que es la mejor encontrada hasta el momento. Y supongamos que estamos construyendo una nueva solución parcial llamada sol. Dada esta solución parcial tendremos una poda si la suma de la ganancia que llevamos en la parcial, más las restantes que aún no hemos evaluado no llega a superar la ganacia de M_sol. Esto quiere decir que si la parcial tiene desde 0…k elementos, y nos quedan por analizar k…n-1, pero aunque eligieramos todos no llegamos a superar la ganancia de M_sol, no tiene sentido seguir con esta recorrida.

Terminada la conceptualización del problema, podemos pasar a construir la función que llamará al Backtracking:

int carga ( int* g, int* p, int* sol, int M) {
int pos = 0; // Posicion actual en la recorrida de elementos.
int ganancia = 0; // Ganancia parcial acumulada.
int m_ganancia = 0; // Mejor ganancia encontrada
int disponible = M; // Espacio disponible restante.
int restante = 0; // Ganancia restante disponible

int * parcial = new int[n]; // Marcaremos con 1 si llevamos al i, o con 0 en caso contrario
for (int i=0; i<n; i++) {
parcial[i] = 0; // Inicializamos en cero los eltos elegido.
restante += g[i]; // Ganancia de los elementos restantes, para la poda.
}

/* Llamamos a la función recursiva */
Back(g, p, parcial, ganancia, m_ganancia, disponible, restante, pos, sol);

delete[] parcial;
return m_ganancia;
}

Y veamos el código de la función recursiva:

void Back(int* g, int* p, int* parcial, int ganancia, int &m_ganancia, int disponible, int restante, int pos, int* sol) {
/* El primer paso es verificar que queda espacio disponible.
Ademas verificamos que podamos llegar a encontrar una mejor solución,
en caso contrario podamos. */
if ( (disponible > 0) && (ganancia + restante > m_ganancia)) {
/* Si ya pasamos por todos los elementos, terminamos */
if (pos == n) {
/* Ya sabemos que encontramos una mejor solucion que m_ganancia */
m_ganancia = ganancia;
for (int i=0; i<n; i++)
sol[i] = parcial[i];
/* Si no llegamos al final, probamos el elemento actual */
} else {
parcial[pos] = 1;
/* Probamos elegir el elemento y actualizamos los valores de ganancia y peso */
Back(g, p, parcial, ganancia, ganancia+g[pos], m_ganancia, disponible-p[pos], restante-g[pos], pos+1, sol);

parcial[pos] = 0;
/* O bien no lo llevamos y probamos seguir sin este elemento */
Back(g, p, parcial, ganancia, ganancia, m_ganancia, disponible, restante-g[pos], pos+1, sol);
}
}
}

De esta forma la función recursiva hace todas las combinaciones posibles de llevar ciertos elementos guardando el mejor resultados posible. Cada vez que se llega a pos == n es que recorrimos toda la secuencia, por lo que llegamos al final de la rama de decisiones del algoritmo. En ese momento y como el if que verifica que el espacio disponible sea sufuciente y que obtuvimos una mejor solución a la previa encontrada, podemos copiar el resultado obtenido.

Estructuras de datos y algoritmos en C/C++: Backtracking, formalización y ejemplos

Continuando con la serie de artículos sobre C/C++, vamos a ver la técnica de programación conocida como Backtracking. Esta técnica se basa en generar todo el espacio de soluciones posibles a un problema dado, pudiendo filtrarse o seleccionar las soluciones que cumplan con ciertas características. Backtracking funciona en forma recursiva, genera árboles de soluciones posibles, recorriendo todo el espectro de posibilidades.

En un primer vistazo Backtracking funciona como un algoritmo de fuerza bruta, que prueba todas las combinaciones posibles, aunque podemos optimizar y mejorar el rendimiento analizando el problema que queremos resolver.Los algoritmos de backtracking suele ser ineficientes, aunque mediante estas optimizaciones se puede moderar la misma, la repetición de cálculos hace que sean ampliamente inferiores a los algoritmos construídos sobre Programación Dinámica. En la próxima entrada analizaremos las diferencias, ahora volvamos a Backtracking .

Por ejemplo, supongamos que tenemos un conjunto de colores y un mapa dado y queremos colorearlo, de forma que dos países adyacentes no tengan el mismo color. Podemos pensar en este problema como si fuera un grafo, donde los vértices conectados son los países limítrofes.

Este problema puede solucionarse de varias formas, por ejemplo buscando una solución cualquiera, o bien buscar todas las soluciones que existen, o bien la solución óptima que utiliza la menor cantidad de colores.

Lo primero que debemos hacer es formalizar el problema, así logramos identificar los elementos del mismo y se simplifica la tarea de construir el algoritmo. La formalización requiere definir:

Forma de la Solución: Cómo presentaremos la solución al problema. En este caso utilizaremos una tupla de largo fijo N formada por elementos xN, donde N es la cantidad de países que debemos colorear. En la posición 1 colocaremos el color asignado al país 1, en la posición 2 el color del país 2 y así sucesivamente.

Reestricciones Explícitas: El espacio de soluciones, o las soluciones posibles al problema, involucra a un único elemento de la tupla. En este caso indica que cada elemento xi es uno de los países a colorear.

Reestricciones Implícitas: Define las relaciones entre los elementos de la tupla, involucra a varios o todos los elementos de la tupla. En este caso debemos aplicar la reestricción que si dos países son adyacentes no deben tener el mismo color. Por lo que si 1 y 2 son adyacentes en el grafo, entonces los elementos x1 y x2 deben ser distintos.

Función Objetivo: Define lo que queremos maximizar o minimizar en las soluciones generadas. Puede ser la mínima o máxima cantidad de colores por ejemplo.

Predicados de Poda: Nos permite evitar buscar soluciones que es evidente no van a generar una solución útil. Por ejemplo supongamos que buscamos el mínimo de colores, entonces una vez que obtenemos una solución posible al problema sabemos que cualquier solución parcial que se esté construyendo puede ser descartada si la cantidad de colores supera a la ya encontrada.

Con estos elementos definidos podemos pasar a implementar el algoritmo con una idea general de como representar cada elemento. Lo primero que haremos será crear una estructura para nuestra tupla solución:

struct tupla {
int* colores; // Arreglo de colores asignados a los pasies
int* cantVeces; // Cantidad de veces que se usa cada color
int cantColores; // Cantidad total de colores usados
}

El próximo paso es preparar la invocación del algoritmo recursivo, al cual le pasaremos esta tupla para que trabaje:

void invocacion(int n, int k) {
/* La primera tupla será sobre la que se trabajará, en t solo guardamos la mejor solución obtenida */
tupla t, sol;
t.colores = new int[n];
sol.colores = new int[n]; // Colores asignados a los paises, n países
t.cantVeces = new int[k];
sol.cantVeces = new int[k]; // Cantidad de veces de cada color, k colores

for (int i=0; i<n; i++) {
t.colores[i] = 0;
sol.colores[i] = 0; // Inicializamos en cero los colores asignados a países
}
for (int i=0; i<k; i++) {
t.cantVeces[i] = 0;
sol.cantVeces[i] = 0; // Inicializamos en cero la cantidad de veces usada de cada color
}
t.cantColores = 0;
sol.cantColores = 0; // Cantidad de colores usados

colorear(t,sol,0,n); // Invocación al algoritmo
}

Esta función invocación prepara el terreno y luego llama a la función recursiva, pasándole una tupla t donde ir armando las soluciones posibles y sol para guardar la mejor solución encontrada. Esta misma tupla sol se usará para comparar con las tuplas que se van encontrando, de forma de saber si encontramos una mejor solución o no. El tercer parámetro es el primer país sobre el cual comenzar a trabajar, n la cantidad de países total, de forma que el algoritmo puede saber en que momento llega a asignar colores a todos los países y debe detenerse, y k la cantidad de colores para realizar las pruebas con los colores disponibles.

Veamos un ejemplo de la función recursiva colorear:

/* Noten que la tupla sol es pasada por referencia, de modo que cualquier estado de la recurrencia puede modificarla y es visible para todos los demás estados. */
void colorear(tupla t, tupla &sol, int i, int n, int k) {
/* Reestriccion implicita, verificamos que al colocar el color en esta posición
no queden dos paises adyacentes con el mismo color. */
if (Factible(t,i))
if (EsMejor(t,sol))
if (EsSolucion(t,i)) {
Copiar(sol, t)
} else {
for (int color=1; color <= k, color++)
colorear(AsignarColor(t,i,color),sol, i+1, n, k);
}
}

Utilizamos una seria de funciones auxiliares.

Factible: Indica si la tupla t, con colores asignados hasta la posición i no contiene países adyacentes con el mismo color.

EsMejor: Indica si la cantidad de colores utilizados en t es menor que los de sol.

EsSolucion: Indica si se completo la cantidad de países a colorear. Si es así (y como antes vimos que era mejor esta solución que la de sol) procedemos a copiar la misma en sol.

AsignarColor: Como todavía no completamos la cantidad de países debemos asignar un color de los k disponbles al país i, y continuar con la recursión.

Los detalles importantes a tener en cuenta son algunos como que la tupla sol puede ser modificada copiando el contenido de t sobre ella por cualquier paso recursivo que encuentre una mejor solución que la que tenemos hasta el momento. Claro que cuando sol es vacía debemos tener cuidado para no tener una solución vacía como la mejor encontrada. Otro detalle importante es no perder soluciones posibles, por eso en cada paso intentamos asignar todos los colores a cada país, para luego en la nueva llamada verificar la adyacencia.

Una posible implementación de AsignarColor, teniendo en cuenta la estructura de tupla que definimo podría ser:

tupla Asignarcolor(tupla t, int, i, int color) {
t.colores[i] = color;
t.cantVeces[color] = t.cantVeces[color]+1; // Incrementamos la cantidad de veces que usamos el color
if (t.cantVeces[color] == 1)
t.cantColores = t.cantColores +1; // Si el color asignado no habia usado aun, incrementamos cantColores
return t;
}

Este algoritmo construido con Backtracking nos permite generar todas las combinaciones posibles de colores asignados, optimizando de forma que podemos detener la recursión en un paso intermedio al encontrar dos países adyacentes con el mismo color.

En la próxima entrada veremos otro ejemplo de Backtracking similar implementado.

The Pirate Bay Trial – Juicio a la bahia pirata, el juicio del siglo en Internet

En este mes de febrero se decidirá el destino de la bahia pirata (http://www.thepiratebay.org/), uno de los mayores sitios en Internet para intercambio de archivos e información, y una de las piedras fundamentales de la red torrent.

Pero hay mucho más en juego, no es solo la continuidad de un sitio de jóvenes rebeldes que utilizan el salto tecnológico para intentar cambiar las reglas de juego. De un modelo donde las multinacionales y los medios controlan al flujo de información y las personas reciben lo que estas deciden, a una democrática y a veces caótica red donde todos son iguales y todos pueden crear y distribuir información. Esta libertad es lo que está en juego, la naturaleza descentralizada y sin barreras de Internet.

Para comprender la situación es necesario entender que gracias a la tecnología las reglas de juego deben cambiar, los costos de distribución y acceso a la infromación son prácticamente nulos, lo que ha llevado a la explosión de intercambio de información en la red. Pero los medios tradicionales de información desean mantener el control sobre el flujo y la distribución, imponiendo un modelo de reestricción que no concuerda con las posibilidades que da Internet.

El salto a la fama internacional de The Pirate Bay se produjo en el 2008 cuando por presiones del gobierno norteamericano el gobierno de Suecia intentó cerrar el portal. Durante algunos días el sitio cayó, solo para resurgir algunos días después con servidores distribuídos por todo el mundo y una vitalidad renovada. Frente a este fracaso y la inesperada fama del sitio, el siguiente paso es intentar llevar tras las rejas a las personas detrás del portal.

Las suspicacias ya han comenzado a ser evidentes, desde testigos que son directivos de multinacionales con su probable tendencia a beneficiar a sus empresas, a intentos de bloquear el acceso a los expedientes del caso.

Este juicio será el primero en una larga batalla por mantener la libertad de Internet, contra el modelo de imposición y control propuesto por algunas empresas y grupos de poder. Por primera vez en la historia de la humanidad prácticamente cualquier ser humando tiene la capacidad de hacer eco en el mundo entero, sin necesidad de acceso a influencias y grandes recursos económicos. La posibilidad de no ser un simple condumidor pasivo de información, dando una voz como lo es este msmo blog entre millones de la red.

Por eso, este parece ser el juicio del siglo que definirá como será Internet en el futuro.

Hash – Tablas de dispersión

Es común al crear estructuras de datos y luego trabajar sobre las mismas, tener la necesidad de realizar búsquedas  en forma más frecuente que la necesidad de realizar inserciones. Por ejemplo si tenemos una lista de personas podríamos querer saber si cierta persona está ingresada, o saber información acerca de la misma. Para estos casos en que queremos realizar consultas sobre la estructura de datos puede ser útil trabajar con una estructura de datos que permita realizar búsquedas rápidas (de orden pequeño).

La estructura que vamos a ver es la Tabla de dispersión o Hash, la cual nos permite acceder a una posición dentro de la misma en orden 1, (O(1) caso promedio), realizando una cantidad fija de operaciones. De esta forma nos aseguramos de llegar a donde deberíamos encontrar la información en forma rápida sin importar la cantidad de elementos que tengamos en la estructura.

Un Hash no es más que un arreglo, en el cual podemos usar dos técnicas de ordenamiento interno. Este ordenamiento define donde colocar un elemento al insertar, pudiendo utilizarse dispersion abierta o dispersión cerrada.

Supongamos que tenemos el siguiente Hash:

En principio no es mas que un arreglo, pero crearemos un puntero en cada celda, de forma que podamos tener cualquier tipo de información guardad dentro de las mismas.

typedef struct tablahash{
int totalDisp;
nodoHash* hash[LARGOHASH+1];
};

Dijimos que el hash nos permite acceder en forma rápida a una de las posiciones dentro del mismo, esto se realiza mediante una función de dispersión que dada cierta entrada o valor, nos devuelve el valor dentro del hash donde debemos buscar la información que nos interesa.

Por ejemplo, si tenemos la lista de personas ingresadas por cédula, y le pasamos el numero de cédula 123456789 la función de dispersión nos devolverá la posición X dentro del hash donde debemos buscar la información de esa persona. Una función de dispersión básica pero útil suele ser sumar los valores ASCII de los caracteres y obtener el resto de dividir entre el largo del Hash, ya que no podemos obtener posiciones fuera del Hash mismo.

Un ejemplo de funcìón de dispersión sería el siguiente:

int calcularClaveInsertar(char const* id) {
int i, disp, length;
disp = 0;
length = strlen(id);

for(i=0; i<length; i++)
disp += id[i];
disp = disp % LARGOHASH;

return disp;
}

Esta función recibe un string y nos devuelve la posición correspondiente al mismo dentro del Hash de largo LARGOHASH.

Ya se habran dado cuenta que podemos tener problemas, que pasa si para dos cédulas diferentes tenemos el mismo resultados de dispersión? Y que sucede si tenemos muchos elementos, más de las posiciones disponibles dentro del hash? Estos casos son llamados “colisiones” ya que la información intenta ocupar el mismo lugar de memoria o posición dentro del hash. Para estos casos es que tenemos que analizar los dos tipos de dispersión posible, abierta y cerrada.

En el caso de la dispersión abierta lo que haremos al tener una colisión será simplemente tener una lista encadenada en cada nodo, por lo que iremos ampliando la lista a medida que tenemos colisiones. Si por ejemplo tenemo el hash de largo 10, e insertamos las cadenas  ”hola” (104+111+108+97 % 10 = 0), “que” (113+117+101 % 10 = 1), “tal” (116+97+108 % 10 = 1), “hash” (104+97+115+104 % 10 = 0) tendríamos un resultado como el siguiente:

En las posiciones 0 y 1 tuvimos colisiones por lo que tenemos dos listas de dos elementos en cada una. Estos nos lleva a ver que en el peor caso de un hash de dispersión abierta tendremos una única lista de elementos en una sola posición, con lo que nuestro hash será simplemente una lista y no nos será de mucha utilidad.

Por esta razón debemos tomar algunas precauciones al utilizar esta estructura de datos, debemos utilizar una función de dispersión adecuada, es decir que nos devuelva valores lo más distribuidos posibles, debemos utilizar un tamaño de hash mayor a la cantidad de elementos que tendremos o que suponemos llegaremos a tener, y es una buena práctica utilizar un número primo en el largo del hash de forma que nos tengamos muchas colisiones al dividir sobre el largo del hash.

El segundo caso, la dispersión cerrada, no permite la creación de listas, pudiendo haber un solo elemento por cada nodo del hash. Para resolver las colisiones se utilizan funciones de redispersión que permiten buscar otra posición dipsonible para el elemento.

Para las funciones de redispersión tenemos la posibilidad de realizar una función lineal, que al encontrar una colisión sume 1 a la posición encontrada, tratando de encontrar una celda libre a continuación. Por ejemplo si tuviéramos el caso anterior, lo que haríamos hubiera sido insertar la palabra “hola” en la posición 0, luego “que” en la posición 1, cuando vamos a insertar “tal” nos encontramos con la posición 1 ya ocupada, por lo que sumamos 1 y lo insertamos en la posición 2. Cuando vamos a insertar “hash” encontramos la posición 0 ocupada, pasamos a la 1 y lo mismo, sumamos 1 nuevamente y la 2 también esta ocupada por lo que pasamos a la 3 que sí esta libre e insertamos ahí. 

Cuando vamos a buscar un elemento al hash caculamos la función de dispersión, por ejemplo para la palabra “tal”, obtenemos el valor 1, vamos a esa posición y no lo encontramos. Entonces vamos sumando 1 hasta encontrarlo o que la celda sea vacía.

El problema sucede cuando eliminamos un elemento y “cortamos” esta cadena, de forma que no podemos seguir este procedimiento. Por ejemplo supongamos que eliminamos la palabra “tal”, luego queremos saber si “hash” pertenece, para lo cual calculamos la dispersión, obtenemos 0, comenzamos a avanzar sumando 1, pasamos a la posición 1, luego a la 2 y llegamos a una celda vacía. No podemos saber que “hash” está en la próxima posición, ya que la celda vacía indica que se termino la cadena. Podríamos buscar una solución alternativa, por ejemplo marcar las casillas cuando borramos con un valor especial de forma que cuando buscamos y encontramos una de estas casillas sigamos avanzando sin detenernos. Así pasaríamos de la posición 2 a la 3 y econtraríamos “hash”.

El problema con la dispersión cerrada lineal es que comenzamos a agrupar los elementos, de forma que terminamos nuevamente con una lista continua dentro del hash y terminamos trabajando como si se tratara de una lista, perdiendo la eficiencia de acceso rápido en el caso promedio.

Tenemos la posibilidad de modificar la función de redispersión, pasando de una lineal a una cuadrática, la cual nos permite dar “saltos” dentro del hash cuando tenemos colisiones. En lugar de sumar 1 al encontrar una colisión sumamos i^2, de esta forma sumamos 0, 1, 4, 9… evitando crear secuencias continuas en un principio. El problema en el caso de la redispersión cuadrática y de que el tamaño del hash es limitado, es que volvemos a caer sobre las mismas posiciones luego de varios saltos, por lo que no utilizamos todo el espacio disponible.

Con la redispersión cuadrática podemos utilizar hasta la mitad del tamaño del hash (si el largo del mismo es de tamaño primo). Es importante realizar un conteo de los elementos y en caso de que el hash este siendo llenado debemos realizar una reestructuración del hash, creando uno nuevo de mayor tamaño primo, por ejemplo un primo cercano al doble, e insertando los elementos del hash anterior en este nuevo hash. Esta operación es bastante costosa, aunque si se tiene cuidado en la elección del tamaño del hash según las características del problema no debería ser una operación frecuente.

Vemos un ejemplo del código de un hash con dispersión abierta. Definimos la estructura de datos como un arreglo con punteros:

// Nodo de un elemento en el hash
typedef struct nodoEtq {
char* idDisposivo;
nodoEtq* sig;
};

// Nodo del hash
typedef struct nodoHash {
nodoEtq* disp;
};

typedef struct tablahash {
int totalDisp;
nodoHash* hash[LARGOHASH+1];
};

Necesitaremos inicializar el hash, ya que las posiciones del arreglo son punteros.

// Inicializa todas las posiciones del hash
void inicializarHash (nodoHash** hash) {
int i;

for (i = 0; i <= LARGOHASH; i++)
hash[i] = NULL;

return;
}

tablahash * hash = new tablahash;
inicializarHash(hash->hash);
hash->totalDisp = 0;

Luego necesitaremos la función de dispersión y una función auxiliar para saber si una celda del hash es vacía:

// Calcula la clave a usar para insertar
int calcularClaveInsertar(char const* id) {
int i, disp, length;
disp = 0;
length = strlen(id);

for(i=0; i<length; i++)
disp += id[i];

disp = disp % LARGOHASH;
return disp;
}

// Celda vacia del hash
bool esVaciaCeldaHash(nodoHash** hash, int disp) {
return hash[disp] == NULL;
}

La función para insertar elementos en el Hash:

// Inserta en el hash un identificador
nodoEtq* insertarHash(nodoHash** hash, char* id) {
int disp;
nodoEtq* nodoEtiqueta = new nodoEtq;
nodoHash* nodoH = new nodoHash;
char* idDisp = new char[strlen(id)+1];

nodoEtiqueta->idDisposivo = idDisp;
strcpy(nodoEtiqueta->idDisposivo,id);

disp = calcularClaveInsertar(id);

if (hash[disp] == NULL) {
nodoEtiqueta->sig = NULL;
} else {
nodoEtiqueta->sig = hash[disp]->disp;
}

nodoH->disp = nodoEtiqueta;
hash[disp] = nodoH;

return nodoEtiqueta;
}

// Inovación a la insersión
// Creamos un nuevo nodo, insertamos el char* idD e incrementamos la cantidad de elementos.
nodoEtq* nuevoNodo = new nodoEtq;
nuevoNodo = insertarHash(hash->hash, idD);
gl->totalDisp++;

Como dijimos al comenzar, la idea del hash es buscar elementos dentro del mismo en forma rápida, vemos una función para realizar las búsquedas:

// Indica si pertenece un identificador al hash
nodoEtq* perteneceHash(nodoHash** hash, char const* id) {
nodoEtq* nodo;
int pos;

pos = calcularClaveInsertar(id);
if (esVaciaCeldaHash(hash, pos)) {
return NULL;
} else {
nodo = hash[pos]->disp;
while ((nodo != NULL) && (strcmp(nodo->idDisposivo,id) != 0)) {
nodo = nodo->sig;
}

if (nodo != NULL) {
return nodo;
} else {
return NULL;
}

}
}

Al utilizar dispersión abierta tenemos una lista en cada celda, por lo que luego de calcular la dispersión debemos recorrer la lista de ese nodo en busca del elemento o el fin de lista. En caso de encontrar el nodo lo devolvemos, o en caso contrario devolvemos NULL.

Por último, una función para desplegar el hash, puede ser útil para realizar pruebas o ver el estado del hash en un momento dado:

// Función auxiliar para desplegar la lista de cada nodo
void desplegarHashLista(nodoHash* lista) {
nodoHash* recorrer;

recorrer = lista;
while (recorrer->disp != NULL) {
printf(“Valor: %s,”, recorrer->disp->idDisposivo);
recorrer->disp = recorrer->disp->sig;
}

return;
}

// Despliega el hash
void desplegarHash (nodoHash** hash) {
int i;

for (i = 0; i < LARGOHASH; i++) {
if (hash[i] == NULL) {
printf(“NULL “);
} else {
desplegarHashLista(hash[i]);
}
}

return;
}