Programing Challenge 1 - Ordenar puntos en espacio tridimensional (Python)

Este es un ejercicio básico de introducción al Programing Challenge. El objetivo de estos ejemplos o ejercicios no es explicar la base de la programación si no, aplicar los conocimientos ya conocidos y aplicarlos con el lenguaje de programación Python.

En este caso uso estos ejercicios para aprender Python pero pueden ser realizados con cualquier lenguaje de programación. Aunque si que se explicaran ciertos temas que pueden ser de interés como algoritmos y formas de plantear los problemas.
Y por último aclarar que en el mundo de la programación existen diferentes vías de llegar a un mismo resultado. 

Ordenar puntos en espacio tridimensional

En este caso se desea ordenar una cantidad de puntos dispersos en el espacio. Estos puntos se crean de manera aleatoria. El criterio que seguimos para ordenarlos es a razón de la distancia a la que se encuentre del origen de coordenadas. Para ordenar estos puntos usaremos el algoritmo de la burbuja (Bubble sort)

Resumen de objetivos:

* Crear puntos aleatorios es un espacio tridimensional.
* Calcular la distancia de los puntos al origen de coordenadas [0, 0, 0].
* Ordenar puntos a razón de distancia utilizando el algoritmo de la burbuja.

Puntos Aleatorios

Para crear puntos aleatorios haremos uso de la función randint(int low, int high), esta función devuelve valores enteros en un rango de low (incluido) a high (excluido). Para poder utilizar esta función debemos importar la biblioteca random:

from random import randint

A esta función le pasaremos un parámetro pointRange anteriormente definido este parámetro define el rango de valores que la función random creará.

for x in range (nPoint):
    newPoint=[x+1,randint(-pointRange,pointRange),randint(-pointRange,pointRange),randint( pointRange,pointRange)]  
    points.append(newPoint)

Calcular distancia al origen

El cálculo se hace a través de la formula de la distancia entre puntos, aplicando su forma de 3 coordenadas. Asignando uno de los puntos el (0, 0, 0) y otro el punto aleatorio creado anteriormente.

Como podemos observar en la fórmula necesitamos realizar operaciones matemáticas sencillas. Sin embargo la raíz cuadrada no se contempla como operación matemática básica y para poder operar con ella debemos importar la biblioteca math.

import math

Esta biblioteca nos permitirá utilizar la función sqrt() para realizar la raíz cuadrada.

for e in range (nPoint):
    d = math.sqrt(((points[e][1]-0)**2)+((points[e][2]-0)**2)+((points[e][3]-0)**2))

    points[e].append(d)

Nota: ** nos permite indicar el exponencial, 'x**2' equivale a 'x^2'.

Está distancia la añadiremos a nuestro array en su correspondiente slot y de esta manera estaremos almacenado el orden de creación, las tres coordenadas del punto y su distancia al origen de coordenadas.

Ordenar puntos

Por último, nos queda ordenar los puntos, de menor a mayor. Para ello vamos a utilizar el algoritmo de la burbuja (bubble sort), aunque podríamos utilizar el algoritmo de ordenación que quisiéramos. Para ello vamos a crear un función o mejor dicho definición (mas acorde a la terminología que utiliza Python).

El algoritmo de la burbuja es uno de los algoritmos más sencillo de entender y de los mas básicos, bubble sort se basa en recorrer un array o lista comparando valores de dos en dos, en caso de que no estén ordenados, que es cuando p(x) > p(x+1), los intercambiara y volverá a recorrer desde el principio el array o la lista, de esta manera se da un momento que un uno de los ciclos de esta iteración no se produzca ningún intercambio, en ese momento sabremos que nuestro valores están ordenados.


def bubbleSort(alist):
    n = len(alist)
    for i in range(len(alist)-1):
        swp = False
        for j in range(len(alist)-1):
            if (alist[j][4] > alist[j+1][4]):
                tempPoint =  alist[j]
                alist[j] = alist[j+1]
                alist[j+1] = tempPoint
                swp = True

        if (swp == False):
            break


En el siguiente Programing Challenge nos metemos en materia de clases y objetos y realizaremos este mismo ejercicio pero mejorando el código y reordenandolo.

Todos los ficheros .py usados en los challenges los podéis encontrar en mi GitHub (https://github.com/KarlVaello/python-programming-challenges)

Este es el código completo de este Programing Challenge.
_________________________________________________________________________

from random import randint
import math

# def that sort an array of points (bubble algorithm)
def bubbleSort(alist):
    n = len(alist)
    for i in range(len(alist)-1):
        swp = False
        for j in range(len(alist)-1):
            if (alist[j][4] > alist[j+1][4]):
                tempPoint =  alist[j]
                alist[j] = alist[j+1]
                alist[j+1] = tempPoint
                swp = True

        if (swp == False):
            break

nPoint = 9 # numer of points
points = [] # points array

pointRange = 90 #aleatory range

# loop to create new random points
for x in range (nPoint):
   newPoint=[x+1,randint(-pointRange,pointRange),randint(-pointRange,pointRange),randint(-pointRange,pointRange)]  
    points.append(newPoint)

# loop to print element on creation order
print("Element on creation order [x,y,z]")
for i in range(nPoint):
    print(points[i])
    
print()
# loop to calculate distance to [0, 0, 0] of each point
print("Element on creation order [x,y,z, DistanceTo0,0,0]")
for e in range (nPoint):
    d = math.sqrt(((points[e][1]-0)**2)+((points[e][2]-0)**2)+((points[e][3]-0)**2))
    points[e].append(d)
    
# loop to print element on creation order and distance to [0, 0, 0]
for i in range(nPoint):
    print(points[i])
    
# bubble sort algorithm
bubbleSort(points)

print()
# print elements in order
print("Elements ordered by distance")
for i in range(nPoint):
    print(points[i])

_________________________________________________________________________

0 comentarios:

Publicar un comentario