Algoritmo en python 3 para realizar la búsqueda A* (A estrella)

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#!/usr/bin/python -w
 
 
 
 
 
# Inicializamos las listas de abiertos y cerradas en vacio
 
 
# Inicializamos todos los estados como arreglos de clave y valor,
 
 
# con sus respectivos estados vecinos como clave y el costo como valor
 
 
# Establecemos la lista de estados, para luego accederla mediante el indice
 
 
# y tambien la lista de distancias entre cada par de estados.
 
 
opened = []
 
 
closed = []
 
 
q0 = {1:5, 2:4, 3:11}
 
 
q1 = {0:5, 3:6, 4:15}
 
 
q2 = {0:4, 3:5, 4:12}
 
 
q3 = {0:11, 1:6, 2:5, 4:5}
 
 
q4 = {1:15, 2:12, 3:5}
 
 
states = [q0, q1, q2, q3, q4]
 
 
distances = [[0, 5, 4, 11, 17], [5, 0, 5, 6, 15], [4, 5, 0, 5, 12], [11, 6, 5, 0, 5], [17, 15, 12, 5, 0]]
 
 
 
 
 
# Funcion para obtener el camino entre 2 estados, mediante el algoritmo de busqueda A*
 
 
def get_way(start, goal):
 
 
    actual = start
 
 
    # "Importamos" nuestra variable global para poderla modificar localmente
 
 
    global opened
 
 
    # Agregamos el estado actual a la lista de estados abiertos
 
 
    opened.append(actual)
 
 
    finalized = False
 
 
    # No terminaremos hasta que no hayamos llegado a el estado meta
 
 
    while not finalized:
 
 
        # Si el estado actual es igual a la meta, entonces agregamos al estado acual
 
 
        # a la lista de cerrados y devolvemos la lista la cual indica nuestro camino
 
 
        if actual == goal:
 
 
            closed.append(actual)
 
 
            return closed
 
 
        else:
 
 
            # Si no, tomamos todos los estados vecinos del estado actual que no se incluyen
 
 
            # en la lista de estados cerrados, y los agregamos a la lista de abiertos
 
 
            opened = [k for k in states[actual].keys() if k not in closed]
 
 
            # Cerramos el estado actual
 
 
            closed.append(actual)
 
 
            # Ahora tomamos como estado actual, aquel estado vecino con el menor costo
 
 
            # y distancia
 
 
            actual = less_f_score(actual, opened)
 
 
            # Limpiamos la lista de abiertos y realizamos una iteracion mas
 
 
            opened = []
 
 
 
 
 
# Funcion para determinar el estado vecino con el menor costo y distancia
 
 
def less_f_score(actual, opened):
 
 
    # Obtenemos la suma del costo y la distancia menor, para un conjunto de estados vecinos
 
 
    less = min([states[actual][state] + distances[state][goal] for state in opened])
 
 
    # Recorremos la lista de vecinos
 
 
    for state in opened:
 
 
        # Si la suma del costo y la distancia para un estado es igual a la menor
 
 
        # entonces devolvemos dicho estado
 
 
        if states[actual][state] + distances[state][goal] == less:
 
 
            return state
 
 
 
 
 
if __name__ == "__main__":
 
 
    # Ingresamos los valores para el estado inicial y el estado meta
 
 
    start = input("Input the start state: ")
 
 
    goal = input("Input the goal state: ")
 
 
    try:
 
 
        # Los convertimos a enteros
 
 
        start = int(start)
 
 
        goal = int(goal)
 
 
    except:
 
 
    print("Invalid number")
 
 
    # Obtenemos el camino el cual es una lista de estados
 
 
    way = get_way(start, goal)
 
 
    # Imprimimos la respuesta
 
 
    print("<", end = " ") 
 
 
    for state in way:
 
 
        print(state, end = " ")
 
 
    print(">")
 
 
    # Terminamos

 



Algoritmo en Python para obtener las progresiones de acordes comúnes de la escala mayor

Desde el IDLE:
 
>> chords = ["I", "ii", "iii", "IV", "V", "vi", "viidis"]
>> progs = []
>> chordi = "I"
>>
>> for chordii in chords:
    if chordii == "iii":
        chordiii = "vi"
        for chordiv in ["ii", "IV"]:
            progs.append([chordi, chordii, chordiii, chordiv])
    elif chordii == "vi":
        for chordiii in ["ii", "IV"]:
            for chordiv in ["V", "viidis"]:
                progs.append([chordi, chordii, chordiii, chordiv])
    elif chordii in ["ii", "IV"]:
        for chordiii in ["V", "viidis"]:
             chordiv = "iii"
            progs.append([chordi, chordii, chordiii, chordiv])
    elif chordii in ["V", "viidis"]:
        chordiii = "iii"
        chordiv = "vi"
        progs.append([chordi, chordii, chordiii, chordiv])
    elif chordii == "I":
        for chordiii in chords:
            if chordiii == "iii":
                chordiv = "vi"
                progs.append([chordi, chordii, chordiii, chordiv])
            elif chordiii == "vi":
                for chordiv in ["ii", "IV"]:
                    progs.append([chordi, chordii, chordiii, chordiv])
            elif chordiii in ["ii", "IV"]:
                for chordiv in ["V", "viidis"]:
                    progs.append([chordi, chordii, chordiii, chordiv])
            elif chordiii in ["V", "viidis"]:
                chordiv = "iii"
                progs.append([chordi, chordii, chordiii, chordiv])
            elif chordiii == "I":
                for chordiv in chords:
                    progs.append([chordi, chordii, chordiii, chordiv])
 
>> for prog in progs:
    print "-".join(prog)

Salida:

I-I-I-I
I-I-I-ii
I-I-I-iii
I-I-I-IV
I-I-I-V
I-I-I-vi
I-I-I-viidis
I-I-ii-V
I-I-ii-viidis
I-I-iii-vi
I-I-IV-V
I-I-IV-viidis
I-I-V-iii
I-I-vi-ii
I-I-vi-IV
I-I-viidis-iii
I-ii-V-iii
I-ii-viidis-iii
I-iii-vi-ii
I-iii-vi-IV
I-IV-V-iii
I-IV-viidis-iii
I-V-iii-vi
I-vi-ii-V
I-vi-ii-viidis
I-vi-IV-V
I-vi-IV-viidis
I-viidis-iii-vi


Script en bash para redimensionar imágenes

El script funciona de la siguiente forma:

 user@host:~$ script directorio 800x600

Donde:

script es el archivo que contiene este codigo y que guardamos en la carpeta bin

directorio es el directorio que contiene las imágenes que vamos a redimensionar

y 800x600 es el nuevo tamaño que vamos a asignar

 

Nota: este script no es recursivo, por lo tanto no toma las imágenes de los subdirectorios del directorio dado

 

#!/bin/bash

E_BADPARAMS=99
E_BADDIRECTORY=100

if [[ -z "$1" || -z "$2" ]]
then
    echo "Usage example: scriptname /home/user/Pictures -resize 800x600"
    exit $E_BADPARAMS
else
    dir=$1
    if [[ -d "$dir" || -d ./"$dir" ]]
    then
        size=$2
        if [[ $dir =~ .*[^/]$ ]]
        then
            dir=$dir/
        fi
        for file in "$dir"*.{jpg,JPG,png,PNG}
        do
            if [ -f "$file" ]
            then
                echo "Convirtiendo $file ..."
                convert "$file" -resize $size "$file".tmp
                mv "$file".tmp "$file"
                if [ -t "$file".tmp ]
                then
                    rm "$file".tmp
                fi
            fi
        done
    else
        echo "Bad directory."
        exit $E_BADDIRECTORY
    fi
fi


Funciones para convertir de decimal a binario

He encontrado 2 buenos algoritmos para convertir un numero decimal a binario a través de estas funciones que reciben el numero entero en base 10 a convertir y devuelven una cadena de caractéres con los dígitos del mismo número ya convertido a base 2.

 

Python versión 2.7 

 

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
34
35
36
37
38
def binario1(n):
 
    """este primer algoritmo utiliza la formula n = 2k + b"""
 
    if n == 0 or n == 1: return str(n)
 
    k = n / 2
 
    E = binario1(k)
 
    b = n % 2
 
    return str(E) + str(b)
 
 
def binario2(n):
 
    """y este va recorriendo 1 bit hacia la derecha en cada iteracion"""
 
    if n == 0: return str(n)
 
    b = ''
 
    while n > 0:
 
        b = str(n % 2) + b
 
        n >>= 1
 
        #de esta forma el numero se va dividiendo entre 2 para llegar a 0
 
        #y terminar el bucle
 
        #tambien podria ser de esta forma
 
        #n /= 2 
 
    return b

 

Siéntente libre de comentar que te parecieron y si conoces algún otro te invito a publicarlo, gracias 



N-ésima permutación lexicográfica

En este post tenemos dos funciones en python para obtener la n-ésima permutación lexicográfica de un conjunto de elementos.

 

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
from functools import reduce
 
def factorial(n):
    """calcula el factorial de un numero"""
    #si n es mayor a uno realiza el calculo
    if n > 1: return reduce(lambda x, y: x * y, range(1, n + 1))
    #si no simplemente regresa 1
    else: return 1
 
def n_permutacion(n, lista):
    """obtiene la n-esima permutacion lexicografica de los elementos de una lista"""
    
    #creamos una funcion lambda para ir removiendo
    #los elementos que ya fijamos, por lo tanto los demas van cambiando
    remover = lambda lista, aremover: [i for i in lista if i != aremover]
    
    #cuando ya no hay elementos en la lista significa que los elementos
    #ya quedaron ordenados y terminamos, regresando [] (vacio)
    if not lista:
        return []
        
    #obtenemos div (divisor) y mod (modulo de n (numero de permutacion)
    #entre la longitud de la lista - 1)
    div, mod = divmod(n, factorial(len(lista)-1))
    #el primer elemento es igual al elemento que hay
    #en la posicion div de la lista   
    elemento = lista[div]
    #concatenamos el elemento actual con todos lo demas elementos
    #que nos valla regresando esta funcion, hasta que regrese []
    #notese que el modulo va disminuyendo y se va pasando como parametro
    return [elemento]+n_permutacion(mod, remover(lista, elemento))


 

Créditos:

http://pyeuler.wikidot.com/problems-21-30



Código en python para hacer "La criba de Eratóstenes"

Bueno como ya es de saberse en cada uno de los post donde exponga algún código de python sera de la versión 3.1 ó >, entonces no cabe la necesidad de estar mencionando la versión del lenguaje en el título del post.

Les presento un par de algoritmos muy parecidos ya que los dos usan la llamada criba de Eratóstenes para "cribar" los números primos de una sequencia de números. Ambos usan una sequencia 1..2000000.

La criba de Eratóstenes

 

 

Nota:

Si conoces algún algoritmo más eficiente tienes la libertad de comentarlo, gracias

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#inicializamos el tamano de la sequencia de numeros
n = 2000000
#se usa un conjunto porque es mas eficiente
#(no hay numeros repetidos)
noprimos = set()
 
#iteramos desde 2 hasta la raiz cuadrada de n
#y desde lo que lleva i, hasta n / i
#esto nos permite obtener todos los multiplos de i
#y agregarlos a el conjunto noprimos
for i in range(2, int(n ** .5) + 1):
    if i not in noprimos:
        for j in range(i, int(n / i) + 1): noprimos.add(i * j)
        
#por ultimo creamos una lista con todos los numeros
#primos desde 2 hasta n
primos = [p for p in range(2, n + 1) if p not in noprimos]

Créditos:

http://es.wikipedia.org/wiki/Criba_de_Eratóstenes

 

y aquí esta el otro que a mi parecer es más eficiente

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#inicializamos la criba como una lista con n elementos True
 
criba = [True] * n
 
#iteramos desde 2 hasta la raiz cuadrada de n
#y desde lo que lleva i, por i, hasta n
for i in range(2, int(n ** .5) + 1):
    for j in range(i * i, n + 1, i):
        #esto nos permite poner False en la posicion j - i de la criba
        #porque j es un multiplo de i y por lo tanto no es primo
        criba[j - 1] = False
 
#por ultimo "cribamos" todos los numeros primos desde 2
#hasta la longitud de la criba
primos = [p for p in range(2, len(criba) + 1) if criba[p - 1])]


Créditos:

http://www.s-anand.net/euler.html



Función en python 3 para obtener una lista de factores primos de un número

El día de hoy estuve buscando con un algoritmo para obtener una lista de factores primos de un número y me tope con esté que me pareció muy interesante

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def factorizar(n):
    #almacenamos los resultados
    #de la factorizacion en una lista
    l = []
    num1 = n
    #mientras podamos dividir por 2
    #el dos es un factor
    while num1 % 2 == 0:
        l.append(2)
        num1 /= 2
    #ahora probamos con los impares
    #empezando por el 3
    cuenta = 3
    raiz = int(math.sqrt(num1))
    while cuenta <= raiz and num1 > 1:
        if num1 % cuenta == 0:
            l.append(cuenta)
            num1 /= cuenta
        else:
            cuenta += 2
    if num1 > 1:
        l.append(num1)
    return l

Créditos

http://latecladeescape.com/recetas-algoritmicas/descomposicion-en-factores-primos.html



Script en bash para actualizar y limpiar el sistema con apt-get

Ya tengo algún tiempo con este pequeño script el cual en pocas palabras lo que hace es actualizarme la lista de paquetes en ubuntu e instalarme opcionalmente nuevos paquetes así como eliminarme paquetes en desuso y tratar de corregirme aquellos con dependecias incumplidas.

Pueden apreciarlo aquí:

 

#!/bin/bash

# Actualiza el sistema y remueve paquetes no necesarios
update() {
    echo -e "\n********** ACTUALIZANDO EL SISTEMA **********\n"
    echo -e "1. ACTUALIZANDO LA LISTA DE PAQUETES...\n"
    sudo apt-get update 1> /dev/null
    echo -e "2. ACTUALIZANDO...\n"
    sudo apt-get upgrade
    echo -e "\n3. CHECANDO DEPENDENCIAS INCUMPLIDAS...\n"
    sudo apt-get check  1> /dev/null
    echo -e "4. CORRIGIENDO DEPENDENCIAS INCUMPLIDAS...\n"
    sudo apt-get install -fy 1> /dev/null
    echo -e "********** ELIMINADO PAQUETES BASURA **********\n"
    echo -e "5. DESINSTALANDO PAQUETES EN DESUSO...\n"
    sudo apt-get autoremove
    echo -e "\n6. BORRANDO ARCHIVOS DESCARGADOS...\n"
    sudo apt-get autoclean 1> /dev/null
    echo -e "7. BORRANDO ARCHIVOS ANTIGUOS DESCARGADOS...\n"
    sudo apt-get clean 1> /dev/null
}

sudo true
update
echo -e "********** ^^ LISTO ^^ **********"
sleep 1
clear

#mas info en [man apt-get] o [apt-get --help] (mas breve)

 

Por último les recomiendo que cualquier script que hagan, lo guarden en un directorio que este incluido en el $PATH esto es en la variable de entorno para las rutas. Para que lo puedan ejecutar desde la terminal, p.e. yo nombre a mi script "update", entonces cada vez que lo quiero ejecutar voy a la terminal y escribo:

update 

y me da la sig. salida:

user@host:~$ update
[sudo] password for user:

********** ACTUALIZANDO EL SISTEMA **********

1. ACTUALIZANDO LA LISTA DE PAQUETES...

2. ACTUALIZANDO...

Leyendo lista de paquetes... Hecho
Creando árbol de dependencias      
Leyendo la información de estado... Hecho
0 actualizados, 0 se instalarán, 0 para eliminar y 0 no actualizados.

3. CHECANDO DEPENDENCIAS INCUMPLIDAS...

4. CORRIGIENDO DEPENDENCIAS INCUMPLIDAS...

********** ELIMINADO PAQUETES BASURA **********

5. DESINSTALANDO PAQUETES EN DESUSO...

Leyendo lista de paquetes... Hecho
Creando árbol de dependencias      
Leyendo la información de estado... Hecho
0 actualizados, 0 se instalarán, 0 para eliminar y 0 no actualizados.

6. BORRANDO ARCHIVOS DESCARGADOS...

7. BORRANDO ARCHIVOS ANTIGUOS DESCARGADOS...

********** ^^ LISTO ^^ **********

Recomendación:

Ejecuta este comando hasta que en todas las secciones te aparezca

 0 actualizados, 0 se instalarán, 0 para eliminar y 0 no actualizados.

Esto significa que ya no hay paquetes por actualizar, instalar, eliminar y actualizar, y que por lo tanto 0 paquetes se actualizaron.

 

Dudas?, comentarios?



Bienvenidos a mi nuevo Blog de programación

Soy estudiante de Ingeniería en Software y además estudio por mi cuenta los lenguajes de programación: python, perl y bash (porque estos no me los enseñan en la escuela :()

Mi intención es compartir lo más relevante de python (en especial) que valla aprendiendo y aprender más en base a las sugerencias y críticas constructivas que puedan surjir.

Te agradezco si quieres colaborar conmigo.

Saludos

Jorge Luna

(pythonista)




Copyright(c) 2017 - PythonBlogs.com
By using this website, you signify your acceptance of Terms and Conditions and Privacy Policy
All rights reserved