Arxiu de la categoria: Python

Geometria computacional

Fa un parell d’anys vaig estar treballant amb el TSP (Travelling salesman problem), i vaig fer una ruta visitant arbres singulars de Barcelona. La unió dels arbres es feia amb línies rectes.

Partint d’aquella idea, vull fer un camí que uneixi tots els punts, però amb suavitat. Per això es fa servir la interpolació (com les cubic-splines, per exemple). Vaig amb la idea de fer dibuixos d’un sol traç (single line drawing, dibuixos que tessel·len tota una superfície amb suavitat. Hi ha artistes que estan fent dibuixo seguint aquesta idea. I això es podria traslladar a la CNC per fer coses xules i divertides.

Bot de Twitter de català revifat

Comença un nou curs, i projectes nous. Durant 10 anys he estat recopilant informació de paraules que m’agrades, i que malauradament estan caient en desús. A més, el Jordi Badia acaba de publicar el llibre Salvem els Mots que precisament va sobre aquesta problemàtica.

Ja feia temps que em rondava fer un bot de Twitter. Així doncs, el que he fet és agafar la informació que tinc, i estructurar-la en una base de dades (recordem: informació > coneixement). I utilitzant el paquet Tweepy de Python, i registrant-te a Tweeter com a desenvolupador, després d’un procés més o menys ràpid, ja tinc el meu bot de Twitter en marxa.

Es tracta de moment d’enviar un missatge dia si dia no, amb un contingut humorístic i picant, relacionat amb paraules i expressions del català que ens agradaria recuperades i normalitzades. El compte de Twitter és @CatalaRevifat

Referències:

Segments de ciclisme amb la API de Strava

De la API de Strava m’interessa sobretot la part de segments, que són trossos de rutes en què la gent es cronometra i es publica els rankings. Malauradament, sense una subscripció Premium no es pot accedir a tota la informació. Jugant una estona amb la API de Strava he arribat a poder veure els segments que hi ha en una zona geogràfica, i poder veure els punts d’aquest segment, que es poden representar en qualsevol mapa.

Per accedir a la informació d’un segment:

$ curl -X GET https://www.strava.com/api/v3/segments/229781 -H 'Authorization: Bearer *******************'

I el resultat:

{"id":229781,"resource_state":3,"name":"Hawk Hill","activity_type":"Ride","distance":2684.82,"average_grade":5.8,"maximum_grade":10.9,"elevation_high":247.2,"elevation_low":92.0,"start_latlng":[37.833112,-122.483436],"end_latlng":[37.828072,-122.498139],"elevation_profile":"https://d3o5xota0a1fcr.cloudfront.net/v6/charts/KO5P7GCFLK5P5NF5GNUX3D6IVFLIEYRYD6JRBEGMXHOCPENJUQZXD5IIEJOYINQE2HX3XLZMYRTF5GHG5JLQ====","start_latitude":37.833112,"start_longitude":-122.483436,"end_latitude":37.828072,"end_longitude":-122.498139,"climb_category":1,"city":"San Francisco","state":"CA","country":"United States","private":false,"hazardous":false,"starred":false,"created_at":"2009-09-21T20:29:41Z","updated_at":"2021-03-13T09:01:33Z","total_elevation_gain":155.2,

"map":{"id":"s229781","polyline":"}g|eFnpqjVl@En@Md@HbAd@d@^h@Xx@VbARjBDh@OPQf@w@d@k@XKXDFPF\\CbGT`AV`@v@|@NTNb@?XOb@cAxAWLuE@eAFMBoAv@eBt@q@b@}@tAeAt@i@dAC`AFZj@dBA~@Yh@MbAVn@b@b@\\d@Ef@Qd@_@d@eB|@c@h@YfBI|AMpA?VF\\\\t@f@t@h@j@|@b@hCb@b@XTd@Bl@GtA?jAL`ALp@Tr@RXd@Rx@Pn@^Zh@Tx@Zf@`@FTCzDy@f@Yx@m@n@Op@VJr@","resource_state":3},

"effort_count":556805,"athlete_count":49100,"star_count":5022,"athlete_segment_stats":{"pr_elapsed_time":null,"pr_date":null,"pr_activity_id":null,"effort_count":0},"xoms":{"kom":"5:37","qom":"6:42","destination":{"href":"strava://segments/229781/leaderboard","type":"overall","name":"All-Time"}},"local_legend":{"athlete_id":54312907,"title":"Dalton Nonweiler","profile":"https://dgalywyr863hv.cloudfront.net/pictures/athletes/54312907/14907176/5/large.jpg","effort_description":"86 efforts in the last 90 days","effort_count":"86","effort_counts":{"overall":"86 efforts","female":"41 efforts"},"destination":"strava://segments/229781/local_legend?categories%5B%5D=overall"}}

Veiem que la polilínia està codificada en una cadena de text. La podem decodificar i obtenir-ne les coordenades:

$ pip3 install polyline

$ python3
>> import polyline
>> #polyline.decode(summary_polyline)
>> polyline.decode("gxu{Fem|Kc@fAq@fAoApAMR[ZMXw@v@a@VQZi@j@sAhAk@hA_@f@oDxCiAhA_@j@a@~@{@pCC`@EFD^H`B?`@BNNZV@JGDMEqA@q@H]NOFSLo@t@eB^i@d@i@t@m@n@Yz@EHBR\\`AdDFdEJ`@RNHIVGf@ATH`At@VXDl@GJU@WY[e@YSKC_@GgA@YMKMc@eBYeBSWg@AUTSVa@|@[tAAPDb@Nr@@TCb@[bACd@BNJ^Xh@N^BNB`@Nn@DJTNZ\\Rn@?\\c@zAA^B\\JZHHh@NZDVHTRHJBNAb@I|@B\\Th@PTVf@F`@Cl@Sj@WJ{Ae@{@OKBSPOr@IvA[z@UTw@JWE_@]QUUKKCu@Hs@NMEIIi@kAOUGE]OUMGIGY?y@XiB@]E]U[SGU?c@XcA`Aw@|@i@~@WbASPK?IC_Au@q@_@SAI@g@Lo@XK?YB[MYOQSQYi@Y_@AK@CDg@X]Bg@KUMi@e@[k@GU@MHQb@a@DIFU@WIYg@u@]y@IqAP{ABq@Is@e@iB}@wAw@oBk@aAa@g@g@w@Km@Q{AYkB_AmCc@eB?]H]NWxAiBZq@JYFm@@m@C[G]OWa@k@eAu@o@k@iBkCm@k@SKc@CK@]LS@e@]]]E@GDEH@`@PZJd@CHEFI?OSMe@Uk@")

[(41.40436, 2.11683), (41.40454, 2.11647), (41.40479, 2.11611), (41.40519, 2.1157), (41.40526, 2.1156), (41.4054, 2.11546), (41.40547, 2.11533), 
...
(41.41868, 2.11667), (41.41859, 2.11653), (41.41853, 2.11634), (41.41855, 2.11629), (41.41858, 2.11625), (41.41863, 2.11625), (41.41871, 2.11635), (41.41878, 2.11654), (41.41889, 2.11676)]

Referències:

Introducció a Jupyter Notebooks

Ja feia temps que tenia ganes de mirar què és això de Jupyter Notebook, que se n’està parlant i cada cop se’n parlarà més. Aquest és el primer exemple que faig, la solució de l’equació de 2n grau amb python i la llibreria sympy, que he agafat d’una pàgina que m’agrada molt: arachnoid.com.

El següent pas serà mirar Jupyter Lab, que és una interfície més moderna, i tinc ganes de jugar amb widgets i sliders per poder fer coses més interactives. Ara que estic programant bastant amb Python per preparar exemples per les classes de CNED a la UPC, fer-ho amb les Notebooks de Jupyter seria una manera molt puntera de fer classes interactives.

Referències:

Ruta pels arbres singulars de Barcelona (minimitzant la distància)

El problema del viatjant de comerç (traveling salesman problem) és un problema clàssic de l’algorísmica: es tracta de passar per una sèrie de punts, sense repetir-ne cap, i minimitzant la distància recorreguda. Fa unes poques setmanes vaig importar els arbres singulars de Barcelona a OpenStreetMaps, i crec que és una bona activitat didàctica per conèixer els arbres de la ciutat fer una ruta per uns quants d’aquests arbres.

Per fer-ho més interessant, podem plantejar-nos el problema de fer un recorregut que minimitzi la distància, passant per tots els arbres, i que retorni al punt de partida. Vaig estar cercant diferents implementacions amb Python que resolguin el problema, fins que en vaig trobar una que satisfeia la meva restricció de tornar al punt de partida.

Sobre aquesta solució he fet alguna modificació per tal de generar un fitxer JSON amb la solució. Finalment, hem de pintar sobre un mapa OSM els nostres punts (nodes); traçar una línia recta entre els punts; i afegir un label-text informatiu sobre aquests punts. El resultat es pot veure en la imatge.

Evidentment hem fet unes simplificacions: la distància mínima entre dos punts és la línia recta, però per la ciutat no podem anar en línia recta, i a més poden haver-hi pujades i baixades. Però com a exercici didàctic crec que és interessant.

Aquí Catalunya són populars les Curses d’Orientació. Crec que es podria aprofitar aquestes activitats en el lleure i afegir-hi una capa de coneixement, com ara conèixer els arbres, conèixer monuments, etc. Crec que per als joves i infants pot ser una activitat engrescadora.

Referències:

Llibre: Elementary Mechanics Using Python

Tinc un nou repte pel que queda de 2019 i per al primer semestre del 2020. He començat a llegir el llibre Elementary Mechanics Using Python: A Modern Course Combining Analytical and Numerical Techniques, de Anders Malthe-Sørenssen. És tot un curs de física, i combina de manera bastant entenedora els exemples clàssics de moviment, forces, energia,… amb les seves solucions numèriques, utilitzant les llibreries matemàtiques i de fer gràfiques de Python.

Es tracta d’implementar tots els exemples del llibre a codi Python. No he vist cap enllaç per descarregar tot el codi, en qualsevol cas, els exemples vull adaptar-los i fer-me’ls meus. He començat per l’exemple del pes suspès d’una molla, que com tothom sap la solució del moviment és sinusoidal al voltant del punt d’equilibri, la velocitat és zero en els punts màxim i mínim, i la velocitat és màxima en el punt d’equilibri. Aquest exemple s’explica en l’apartat 5.7, que parla de forces, i no n’hi ha prou en copiar i enganxar el codi, sinó que l’he hagut d’adaptar. Aquesta és la meva solució:

# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt
import numpy as np

# Initialize
m = 1.0
# kg
k = 100.0 # N/m
v0 = 1.0
# in m/s
time = 2.0 # s
g = 9.8 # m/s^2

# Numerical setup
dt = 0.0001 # s
n = int(round(time/dt))
t = np.zeros(n,float)
y = np.zeros(n,float)
v = np.zeros(n,float)
# Initial values
y[0] = 0.0
v[0] = v0
# Simulation loop
for i in range(n-1):
\tF = -k*y[i] – m*g
\ta = F/m
\tv[i+1] = v[i] + a*dt
\ty[i+1] = y[i] + v[i+1]*dt
\tt[i+1] = t[i] + dt

fig = plt.figure()
fig.suptitle(u”Objecte suspès d’una molla”)
plot1 = fig.add_subplot(211)
#plot1.set_xlabel(‘t [s]’)
plot1.set_ylabel(‘y [m]’)
plot1.xaxis.grid()
plot1.plot(t,y)
plot2 = fig.add_subplot(212)
plot2.set_xlabel(‘t [s]’)
plot2.set_ylabel(‘v [m/s]’)
#plot1.grid(axis=’y’)
#plt.grid(b=True, which=’minor’, color=’#666666′, linestyle=’-‘)
plot2.xaxis.grid()
plot2.plot(t,v)

for i in range(10, n-1, 400):
\tplot1.plot(t[i],y[i],’ob’)
\tplot2.plot(t[i],v[i],’ob’)

plt.show()

Aquests són els capítols i temes que es tracten en el llibre:

4. Motion in One Dimension .
5. Forces in One Dimension .
6. Motion in Two and Three Dimensions
7. Forces in Two and Three Dimensions
8. Constrained Motion
9. Forces and Constrained Motion
10. Work
11. Energy
12. Momentum, Impulse, and Collisions
13. Multiparticle Systems
14. Rotational Motion
15. Rotation of Rigid Bodies
16. Dynamics of Rigid Bodies

Elementary Mechanics Using Python

Ja he acabat el llibre Elementary Mechanics Using Python, i en el fitxer adjunt tenim tot el codi Python i els gràfics generats. Ha estat una bona repassada d’un curs de Mecànica general: forces, energia, treball, sòlid rígid. He escollit un dels gràfics a l’atzar, tots els exercicis han estat interessants de programar. En el fitxer exercicis.txt s’ha documentat la feina feta i s’ha relacionat tots els exercicis realitzats. De totes maneres, la manera com s’ha anomentat els scripts i els gràfics resultants fan que s’ubiquin ràpidament en l’apartat del llibre corresponent.

Els scripts s’han fet amb python2, tot i que fàcilment es poden portar a python3. En el llibre s’ha utilitzat la llibreria pylab que representa que simplifica la feina de realitzar els gràfics i utilitzar els mòduls matemàtics. Tanmateix, nosaltres hem preferit utilitzar les llibreries numpy i matplotlib directament, és una aproximació més general.

Curs d’Intel.ligència Artificial a edx.org

Estic fent el curs ColumbiaX: CSMM.101x d’Intel·ligència Artificial de edx.org. De fet. ja l’estic acabant. Ja estem a la última setmana, i per sort meva, l’últim projecte ja el tinc entregat i m’ha portat menys feina del que em pensava, sense especials contratemps. Ara només em falta fer l’examen final que serà el 23 d’abril, Sant Jordi.

Els projectes que s’han realitzat, tots ells amb Python, són:

  • Projecte 1: Search Algorythms. BFS, DFS,… Es va resoldre el 8-puzzle
  • Projecte 2: Adversarial Search and Games. S’ha resolt el joc del 2048, que de fet jo hi havia jugat bastant. Aquest projecte em va costar bastant, i efectivament vaig arribar a 2048 en una ocasió, combinant diferents heurístiques.
  • Projecte 3: Machine Learning. Hi havia tres problemes diferents: I. Perceptron Learning Algorithm; II. Linear Regression; III. Classification
  • Projecte 4: Constraint Satisfaction Problems. Aquí vam resoldre el joc del sudoku amb els algorismes del AC-3 i del backtracking.
  • Projecte 5: NLP, Natural Language Processing. Un projecte molt interessant. Hi havia un train data de 25000 comentaris de pel·lícules, valorades del 0 al 10. I després també hi havia un test data de 25000 comentaris que s’havien de valorar després d’entrenar el sistema.

El resum de les setmanes ha sigut el següent:

  • Week 1: Introduction to AI
  • Week 2: Intelligent Agents and Uniformed Search
  • Week 3: Heuristic Search
  • Week 4: Adversarial Search and Games
  • Week 5: Machine Learning I
  • Week 6: Machine Learning II
  • Week 7: Machine Learning III
  • Week 8: CSP
  • Week 9: Reinforcement Learning
  • Week 10: Logical Agents
  • Week 11: AI Applications: NLP

Per sort ja s’està acabant perquè m’ha agafat més temps del que tenia i del que volia dedicar-li. Però realment ha sigut interessant i exigent, i m’he hagut de posar les piles amb el Python. Realment el tema de les estructures de dades, i les diferents llibreries que s’han utilitzat amb Python, són molt potents.

Intentaré seguir llegint coses sobre Intel·ligència Artificial (IA) i Machine Learning (ML).

NOTA: encara no tinc acabat el projecte de la màquina de dards, i de fet me n’adono que el problema d’esbrinar on ha tocat el dard i quina puntuació té, a part d’un problema de CV (Computer Vision), també és un problema de ML (Machine Learning).