Permutaciones en matrices (Visual Basic y C++)

Un ejercicio clásico de programación consiste en generar todas las permutaciones de una matriz o cadena de caracteres. Para este último caso en Visual Basic hay una solución que consta de dos procedimientos (uno de ellos recursivo), mientras que para las matrices, echando mano de la Wikipedia buena (en inglés), así como de sitios como rosettacode.org (una Wikipedia de la programación), la mejor solución para generar pemutaciones es el algoritmo de Heap, que puede ser recursivo o no recursivo (como el indicado más adelante, más práctico para permutar matrices):


procedure generate(n : integer, A : array of any):
c : array of int
for i := 0; i < n; i += 1 do
c[i] := 0
end for
output(A)
i := 0;
while i < n do
if c[i] < i then
if i is even then
swap(A[0], A[i])
else
swap(A[c[i]], A[i])
end if
output(A)
c[i] += 1
i := 0
else
c[i] := 0
i += 1
end if
end while

Resolviendo la Estrella Mágica

Estrella mágica de grado 6: la suma de los lados de cada triángulo mayor, y de los números del hexágono interno, debe ser siempre 26. Abajo se muestra una de las 72 soluciones posibles.

Como parte de mi afición por los cubos de Rubik había encontrado hace un tiempo el canal de Cuby, un youtuber aficionado a estos cubos y a los puzzles en general. En uno de sus videos presenta una Estrella Mágica, un acertijo con forma de estrella de seis puntas en el cual hay que colocar los números del 1 al 12, de modo tal que los lados de cada triángulo mayor de la estrella, así como los seis números del hexágono central, sumen 26:

Y aquí entra nuevamente el tema de las permutaciones. Aunque existen soluciones matemáticas para este problema, la primera intención siempre suele ser resolverlo por fuerza bruta, es decir, con un programa que genere todas las permutaciones posibles y muestre las soluciones.

En el minuto 6:58 del video está el código usado por él (C# sobre Visual Studio), y como a mí me colapsó el Visual Basic al querer resolverlo en Excel, me pareció mejor volver al C++ (sobre Dev-C++), y crear un programa que además cuente el número de soluciones. Resulta que aunque hay 479.001.600 permutaciones posibles, sólo 72 solucionan el problema. Adjunto aquí el código fuente y la aplicación generada, con el valor de cada letra del tablero según el esquema de la imagen anterior.

Resolver por fuerza bruta un problema como éste es muy sencillo, comparado con otros como el problema de las n damas, que consiste en colocar n damas en un tablero de ajedrez de n por n casillas, de manera que no haya más de una dama por cada fila, columna y diagonal del tablero, que se complica al resolverlo por fuerza bruta cuando n pasa de 50, y para el cual hay una recompensa de un millón de dólares para una solución polinomial (no algorítmica) con n igual a 1000. Lo que en el fondo no es otra cosa que una solución del problema P=NP:

Convertir coordenadas UTM y geográficas (Colombia)

Más que un manual para gente que ya sepa de topografía, cartografía o ingeniería, el siguiente es un resumen de las herramientas en línea que (a mi parecer) son más útiles para convertir las coordenadas que se pueden obtener con herramientas de uso común entre arquitectos o delineantes.

Normalmente, en arquitectura se suele trabajar con levantamientos topográficos hechos con el llamado sistema de coordenadas UTM (Universal Transversal de Mercator), que marca la distancia en metros de la abcisa (x o Este) y la ordenada (y o Norte), a partir de un punto de referencia que suele cambiar dependiendo de las zonas del sistema cartográfico establecido:

Sin embargo, a la hora de georreferenciar un punto de un proyecto con herramientas de arquitectura como AutoCAD o Revit, o software no especializado como Google Earth, no siempre se logra la conversión correcta de un sistema de coordenadas a otro. Por ejemplo, si fuera por los tutoriales, y usando los servicios en línea que hay, uno diría que las coordenadas UTM del centro de la Plaza de Bolívar en Bogotá, según Google Earth, son: 602489.26 m E, 508305.27 m N. Sin embargo, no es así porque la información no es suficiente.

Por ejemplo, supongamos que el centro de la Plaza de Bolívar esté en las coordenadas geográficas 4.5981206, -74.0782322 (según Google Maps). Lo primero que hay que hallar es el sistema de cada zona. La página más práctica que encontré fue spatialreference.org, que permite ver la zona cubierta por cada sistema de referencia. Por ejemplo, la zona que incluye a Bogotá es EPSG:3116 MAGNA-SIRGAS / Colombia-Bogotá. En dicha página sólo hay que explorar las opciones Previous o Next para saber qué sistema de referencia cubre la zona que deseamos buscar en el resto del país.

Detalle del sitio spatialreference.org con la zona cubierta por la zona Magna-Sirgas Colombia-Bogotá del sistema EPSG:3116 (en las opciones Previous/Next se ve el área cubierta por cada sistema)

Una vez hallado el sistema podemos entrar a EPSG.io y, habiendo introducido el sistema de referencia y el sistema de coordenadas al que queremos hacer la conversión, obtendremos las coordenadas correctas. Que en el ejemplo de la Plaza de Bolívar son 999919.63, 1000212.36 en el sistema UTM.

Conversor de coordenadas del sitio EPSG.io. Es necesario saber el sistema de coordenadas del punto, y el sistema al que queremos convertirlas.

Una vez obtenidas las coordenadas es más fácil trabajar con software como AutoCAD o Civil Map que utilizan diferentes sistemas de coordenadas para la geolocalización de proyectos. También es útil entre arquitectos a la hora de hacer trámites ante la aeronáutica civil, que exige estas coordenadas a la hora de expedir normas para licencias de construcción en predios cercanos a los aeropuertos. Como digo, esta guía va dirigida a arquitectos o delineantes, que no tienen (tenemos) la misma formación en esto que los topógrafos o los ingenieros, por lo cual el artículo queda abierto a correcciones y sugerencias.

Seis meses en bicicleta

En realidad son casi ocho meses desde cuando decidí apostar por la bicicleta como mi principal opción de transporte, pero unos seis en días hábiles acumulados. Además iba a escribir esto para cuando cumpliera mi primer año en cicla, pero no creo que mientras la use como hasta ahora haya mucha diferencia. Ya he acumulado más de 3.000 km. recorridos y bastantes experiencias como para hacerme a la idea de cómo es andar en bicicleta por Bogotá.

Cuando comprobé lo deficiente del transporte público en toda la ciudad esta zona, y después de descartar las opciones desde los patines y los patinetes eléctricos hasta la moto, me decidí por una bicicleta eléctrica usada, y me declaro muy satisfecho por esa compra. Y después de comprobar que a pesar de no ser Ámsterdam o Copenhague, es posible moverse en bicicleta en Bogotá a pesar de todos sus problemas, que van desde la seguridad, la falta de infraestructura o de cultura ciudadana.

Dicen moda porque “alternativa al cada vez peor transporte público de Bogotá” quedaba muy largo.

En todo este tiempo, puedo decir que salvo algún roce con algún ciclista o peatón, no he tenido ningún incidente medianamente grave, ni mucho menos un accidente. Buena parte del asunto tiene que ver con usar una bicicleta de menos de 350 vatios de potencia, por lo cual es lícito circular por los andenes asumiendo la misma actitud del Distrito (ante la falta de las ciclorrutas necesarias), de autorizar el uso compartido de andenes por parte de ciclistas y peatones, dando a éstos la máxima prioridad (pues no tiene sentido que haya que apearse por hasta tres cuadras para pasar de una ciclorruta a otra sólo porque la ciudad está mal diseñada).

Sin embargo, la principal lección que he aprendido es la de que hay que saber andar conservadoramente y a la defensiva. Admito que he cometido algunas imprudencias, pero en lo posible he querido cumplir con lo necesario, a veces al punto de la ñoñez. Cuando la situación se sale un pelo de lo normal, parar. Portar todo el equipo (casco, luces, espejos, pito, chaleco) y respetar los semáforos y las señales (como la de no cruzar los puentes peatonales montado). Pero sobre todo, la clave de saber andar a la defensiva es asumir que los demás son unos idiotas. Peatones que cruzan las vías sin mirar, ciclistas con celular en la mano (o que van por la izquierda), runners que se creen bicicletas (y por tanto invaden las ciclorrutas), conductores que no saben usar las direccionales, y recicladores, ancianos y algún caso psiquiátrico que creen que la ciclorruta o el bicicarril son extensión del andén. Carne de democracia, que llaman.

¿Cómo me ha ido con la bicicleta? En términos generales, bien. Es plegable, suficiente como para caber en el ascensor, pero desafortunadamente no en un taxi (porque no es una Brompton). Y acaba de llegar de mantenimiento, por lo que da gusto usarla en sus tres modos: sin motor (como la bicicleta que no tuve hasta los 16), con acelerador (con autonomía de hasta 30 km.), o con pedaleo asistido (por cada pedalada, el motor avanza el equivalente a otra). Sólo un pinchazo, que en la bicicletería del barrio me solucionaron. Porque eso es otra cosa: en muchos talleres aún no se atreven a meterle mano a estas bicicletas, y la marca que las ofrece sólo tiene una sede en Bogotá.

Con la bicicleta he podido matar dos pájaros de un tiro (por más que los animalistas adoctrinados se ofendan): la falta de transporte y el sedentarismo. Además de reemplazar el cortisol por la dopamina (o sea, Transmilenio por la bicicleta), una vez me contagié de gripa, y en lugar de padecerla, decidí sudarla en la bicicleta en vez de la cama. No sé exactamente cómo ni por qué, pero al día siguiente, resultó que me alivié. Como si me hubiera ahorrado los peores cinco días. Y pensar que estoy rodeado de sedentarios que dicen que recorrer 18 km. diarios (incluyendo los cerros de Suba) en una bicicleta de 30 kilos no cuenta como ejercicio.

Otra cosa es la infraestructura. Si bien para una rin 20 los andenes y ciclorrutas en esta parte de la ciudad están en estado transitable (la mayoría de las plegables son rin 16), en lugar de presumir los kilómetros de ciclorrutas hechos y acumulados, la alcaldía debería prestar más mantenimiento a la red existente, que está en un estado muy regular (y aprender definitivamente a hacer andenes, de paso). Pero en su lugar, este nefasto alcalde, además de los cuatro años de retrovisor apuntados a los “doce años de izquierda” anteriores (a los que ya superó en ineptitud y despotismo), ha decidido aumentar aún más la tarifa del transporte público (lo que sólo justifica más los casi $700.000 ahorrados en estos meses en pasajes de Transmilenio).

De la seguridad, mejor no hablar. Ser latinoamericano colombiano bogotano es un acto de fe. La clave está en los horarios; a la hora en que en los recorridos de siempre es peligroso andar en bicicleta, resulta ser la misma hora en la que se meten a robar en Transmilenio. La bicicleta está registrada, pero duele pensar que la justicia no ayuda, o que en una ciudad que necesita cada vez más a Dredd, el jefe de policía sea Gorgory (o sea, un tipo que sale con frases como el ladrón es el que roba. Entonces, el que roba es un ladrón.)

En resumen, le he cogido gusto a la bicicleta (aunque no tanto como para ponerle nombre), y a andar por ella en Bogotá (mientras la infraestructura lo permita). Sé muy bien que no siempre se puede contar con la bici, y que el transporte público debe ser siempre una opción (rápida, cómoda, eficiente, limpia y segura, si no es mucha molestia). Pero mientras se pueda, prefiero la bicicleta en lugar de Transmilenio (porque el SITP ni siquiera es una opción) y encontrar al salir ese recordatorio que ya han puesto en varios puentes peatonales: “En bici ya habrías llegado”.

P.D.: la mejor alternativa a comprar una bicicleta eléctrica suele ser convertir una bicicleta convencional. Existen kits hasta por la mitad del precio, incluso empresas que venden estas bicicletas ofrecen la instalación.

Simulando el cubo de Rubik en Excel

Hace ya unos tres años que comencé a estudiar el cubo de Rubik, aquel rompecabezas inventado por Erno Rubik en 1974 y que se convertió en el juguete más vendido de la historia. Coincidió la compra de mi primer cubo (hace muchos más años, uno muy barato y malo en una cacharrería) con la lectura de un artículo de una revista sobre su historia y el hallazgo de métodos para resolverlo y de todas sus curiosidades matemáticas. También descubrí que es una afición muy popular (sobre todo entre coleccionistas) y para muchos, casi un deporte. Así pues, también comencé una pequeña colección de estos rompecabezas:

Mi pequeña colección de cubos de Rubik y sus variantes.

Si bien hay simuladores en línea o para PC, siempre pensé que una buena forma de entender cómo funciona el cubo de Rubik y sus variantes (porque a Rubik sólo puede atribuírsele el clásico de 3x3x3 capas), era poder ver todas sus caras al tiempo (es decir, como un cubo desplegado). Y las únicas aplicaciones que encontré para ver un cubo en 2D eran archivos de Excel, muy ingeniosos pero que se limitaban al cubo de 3x3x3. Así que pensé que podría hacer un simulador 2D de cubos desde 2 hasta n capas. Todavía está en proceso, pero para quien le interese (y tenga sugerencias), el resultado a día de hoy está aquí.

Ejemplo con valor de n=4. Se puede seleccionar cada cara, un punto de la cara (flechas de arriba), y la dirección de giro de la capa (flechas de abajo)

Es más bien un pasatiempo y un repaso de programación que una aplicación ready-to-use, pero permite ver cómo funciona no sólo el cubo, sino los algoritmos que permiten resolverlo o generar patrones.

Cómo girar una matriz cuadrada

Como uso Excel para repasar mis ejercicios de programación, resulta que para poder girar las capas del cubo simulado en Excel necesitaba saber algo que no pude encontrar ni en mis apuntes ni en la web: cómo girar una matriz de n x n (al menos no en Visual Basic). Así que aquí va una propuesta de cómo resolví el problema en Excel a partir de una hoja en blanco y una matriz de 4×4 con los números del 1 al 16:

Girar a la derecha

Sub GirarR()
Dim i, j, n, x, y As Integer
Dim m() As Integer
n = 4 'Este valor se puede obtener de otra forma
ReDim m(1 To n, 1 To n) As Integer
'Girar matriz
x = n
y = 1
For i = 1 To n
For j = 1 To n
m(i, j) = Cells(x, y)
x = x - 1
Next j
y = y + 1
x = n
Next i
'Mostrar en pantalla
For i = 1 To n
For j = 1 To n
Cells(i, j) = m(i, j)
Next j
Next i
End Sub

Girar a la izquierda

Sub GirarL()
Dim i, j, n, x, y As Integer
Dim m() As Integer
n = 4 'Este valor se puede obtener de otra forma
ReDim m(1 To n, 1 To n) As Integer
'Girar matriz
x = 1
y = n
For i = 1 To n
For j = 1 To n
m(i, j) = Cells(x, y)
x = x + 1
Next j
y = y - 1
x = 1
Next i
'Mostrar en pantalla
For i = 1 To n
For j = 1 To n
Cells(i, j) = m(i, j)
Next j
Next i
End Sub