Posted: March 16th, 2009 | Author:lrei | Filed under: Uncategorized | Tags:BEST, FEUP, News, Ui | Comments Off
Seriously, if you don’t know BEST Engineering Competitions, get to know them. They are incredibly fun. I’m not the “build stuff” kind of guy, my usual approach to “hardware” involves smacking stuff – the caveman approach. But I tried it for a bit and found it surprisingly fun.
The 24hours BEST Engineering competition will be held next weekend. You can participate if you’re a student @ FEUP or FCUP.
Here’s the promo video (flash)
Go to the website for more information (Portuguese)
Right now I’m still sleep deprived having only slept 3h30 – something that happened by accident. I’m also a bit angry because my entry got arbitrarily bumped out of 3rd place by the competition judges. That sucks. Not just for the cash (100 eur) but mostly because it feels like a slap to face. I worked for 1 week non-stop (close to 20h/day for 5 days) and came all the way to Barcelona. I watched with excitement as my agent did better than most in the competition even if it was partially luck (as was for the 2 teams with better scores). And after all the sacrifice, tears and joy I don’t get to go to the final because of an arbitrary decision of a group of people. FUCK THAT. That’s why I dislike the existence of judges in a competition such as this. “Fixing” scores is cheating – regardless of weather it’s done behind the scenes or in plain view. Sigh. I guess it was too much for the final round to be 2 Portuguese teams, 1 Italian and none from the USA.
And worse, both of the entries from FEUP were from undergrads who only had 1 week to work on this while many of the other teams were from people who had masters and phds and the italian guy that got 2nd place was an associate professor and had 1 month to work on it (and said he thought it wasn’t enough in his presentation).
Oh well. At least the team that won was from FEUP (Team SpeedyGonzales) and I’m happy for them (congratulations again Alvaro, Fabio and Sara). The other team from FEUP (NetSqueak) sorta gave up so they got merged into my team and presented their results during the first part of my team’s presentation even though their agent wasn’t running in the competition.
My presentation sucked! I fell a sleep and didn’t wake up till 5 min after the competition officially started. I managed to arrive on time and do a few slides but I was way too tired to make a decent presentation.
Since I only had one week to prepare for this (from scratch) that meant 1 day to write the paper, 5 days to write code and 1 day to travel. Unfortunately my initial approach which consisted of using neural networks for motor control was a huge fail and I wasted a day with it. Still, in 4 days I managed to get probabilistic mapping, basic communication, and a bunch of behaviors (though many buggy) written. Apart from what I learned about cibermouse and robotics there’s also the experience of having an even more insane deadline than usual. It’s very much like a real time system: if you cant do it in this amount of time, it’s a fail. You have to give up on certain solutions if they don’t work because you can’t predict how much time it’s going to take you to get it to work while it’s a lot easier to estimate how long it’s going to take to implement a different solution (if you’ve done something similar before).
Honestly, a few minutes before the competition I thought I was going to be the worst entry there. There were so many bugs that remained unfixed that I had to disable a lot of my mouse’s intelligence – hell, during the first run, 2 of my agents crashed and I had to further cripple it by disabling the comunication system for the second run or risk losing points again (crashed agents collide with walls). Most of the entries had no intelligence anyway – at least not in practice. I was expecting to see some really intelligent agents but instead, the ones that did better where the ones closer to plain simple reactive. In fact, the robot that won the thing for SpeedyGonzales was a purely reactive agent (they had two wall followers, two explores and 1 simple reactive agent). Building intelligence into robots is a lot more complicated than I believed it to be. Also why the hell did so few of the entries bother to actually use the damn sensors properly to avoid collisions? Makes no sense.
I spent the past few hours at the hardrock cafe which is pretty much next door (like 30s walk) to the hotel I’m staying at. I liked it, the only other I had been to was the one in Oslo and that one was a HUGE FAIL – when I went there, it didn’t have Rock (they were wacthing football) or “Cafe” (coffee), the machine was broken or something. I was told the one in Lisbon was Bigger & Better (TM) than this one so I’ll have to check it out next time I’m in Lisbon. In the meantime I’m tempted to purchase a tshirt or something.
For the next 2 days I’ll get to see Barcelona (so far I’ve been stuck at the hotel working). So I
My “Computer Networks” (Redes de Computadores) assignment is writing an HTTP server that implements GET and conditional (if-modified-since) GET with persistent connections.
import csv
class simpsonCsv:
def __init__(self, filename):
reader = csv.reader(open(filename, "rb"))
xlist = []
ylist = []
for row in reader:
try:
x = float(row[0])
y = float(row[1])
except TypeError:
continue
except ValueError:
continue
xlist.append(float(x))
ylist.append(float(y))
self.len = len(xlist) - 1
self.xstart = xlist[0]
self.xend = xlist[self.len]
self.interval = self.xend / self.len
self.data = map(None, xlist, ylist)
def f(self, x):
for (u,v) in self.data:
if u == x:
return v
print "Bad x value (probably bad n): %s" % (x)
return None
def simpson(self, n):
"Approximate the definite integral of f from a to b by Simpson's rule."
if self.len % n != 0:
print "Error: %d mod %d is not zero but should be." % (self.len, n)
return -1
h = float(self.xend - self.xstart)/n
si = 0.0
sp = 0.0
xk = 0.0
for i in range(1, n, 2):
xk = self.xstart + i*h
si += self.f(xk)
for i in range(2, n, 2):
xk = self.xstart + i*h
sp += self.f(xk)
s = 2*sp + 4*si + self.f(self.xstart) + self.f(self.xend)
return (h/3)*s
filename = "integral_tabela_CO2_csv.csv"
s = simpsonCsv(filename)
print s.simpson(20)
print s.simpson(40)
print s.simpson(60)
print s.simpson(100)
print s.simpson(300)
print s.simpson(600)
print s.simpson(900)
print s.simpson(1800)
def simpson(f, a, b, n):
"Approximate the definite integral of f from a to b by Simpson's rule."
if n % 2 != 0:
print "Ups: n must be even!"
return -1
h = (float(b) - a)/n
si = 0.0
sp = 0.0
for i in range(1, n, 2):
xk = a + i*h
si += f(xk)
for i in range(2, n, 2):
xk = a + i*h
sp += f(xk)
s = 2*sp + 4*si + f(a) + f(b)
return (h/3)*s
def f(x):
return x**4
ni = 50
nf = 1000000
n = ni
a = -20
b = 0
s = []
qc = []
ec = []
t = 0.0
div = 0.0
i = 0.0
while n < nf:
t = simpson(f, a, b, n)
s.append(t)
n = n * 2
for i in range(0, len(s)-2):
div = (s[i+2] - s[i+1])
if div == 0:
break
t = (s[i+1] - s[i]) / div
qc.append(t)
t = div / 15
ec.append(t)
for i in range(0, len(qc)):
print "%.12f, %.12f, %.12f => qc=%.12f, e=%.12f" % (s[i], s[i+1], s[i+2], qc[i], ec[i])
# this requires numpy get it from http://numpy.sf.net
from copy import deepcopy
from numpy import *
# this function, swapRows, was adapted from
# Numerical Methods Engineering with Python, Jean Kiusalaas
def swapRows(v,i,j):
"""Swaps rows i and j of vector or matrix [v]."""
if len(v) == 1:
v[i],v[j] = v[j],v[i]
else:
temp = v[i].copy()
v[i] = v[j]
v[j] = temp
def pivoting(a, b):
"""changes matrix A by pivoting"""
n = len(b)
for k in range(0, n-1):
p = int(argmax(abs(a[k:n, k]))) + k
if (p != k):
swapRows(b, k, p)
swapRows(a,k,p)
def gauss(a, b, t=1.0e-9, verbose=False):
""" Solves [a|b] by gauss elimination"""
n = len(b)
# make copies of a and b so as not to change the values in the arguments
tempa = deepcopy(a)
tempb = deepcopy(b)
# check if matrix is singular
if abs(linalg.det(tempa)) < t:
return -1
pivoting(tempa, tempb)
for k in range(0,n-1):
for i in range(k+1, n):
if tempa[i,k] != 0.0:
m = tempa[i,k]/tempa[k,k]
if verbose:
print "m =", m
tempa[i,k+1:n] = tempa[i,k+1:n] - m * tempa[k,k+1:n]
tempb[i] = tempb[i] - m * tempb[k]
# Back substitution
for k in range(n-1,-1,-1):
tempb[k] = (tempb[k] - dot(tempa[k,k+1:n], tempb[k+1:n]))/tempa[k,k]
return tempb
def residue(a, b, c):
"""Calculates the residue of a system solved by gauss elimination"""
n = len(b)
t = a * c # t is the A with the values of x replaced (an [n x n] matrix)
s = []
for i in range(0, n):
s.append(sum(t[i])) # s is the solution
res = b - s # res is the residue
return res
#a = array([[1.0, 2.0, 0.0],[-1.0, 2.0, 3.0],[1.0, 4.0, 1.0]])
#b = array([3.0, -1.0, 4.0])
#a = array([[-1.414214, 2, 0],[1, -1.414214, 1], [0, 2, -1.414214]])
#b = array([1.0,1.0,1.0])
#a = array([[2.0, 2.0, 2.0],[1.0, 1.0, 5.0], [2.0, 5.0, 1.0]])
#b = array([6.0, 7.0, 8.0])
a = array([[1.001, 2.001, 3.001],[0.999, 2.0, 2.999], [1.002, 1.999, 2.999]])
b = array([4.003, 4.001, 3.999])
x = gauss(a, b)
print "Solution = ", x
#sol = linalg.solve(a, b)
#print "linalg Solution = ", sol
y = residue(a, b, x)
print "Residue = ", y
u = gauss(a, y)
print "Residue destribution = ", u
z = gauss(a, b+y)
print "New Solution (with added residue) = ", z
y2 = residue(a, b+y, z)
print "Residule of new solution = ", y2
if linalg.norm(y2) < linalg.norm(y):
print "New solution has a smaller residue."
else:
print "Original solution has a smaller residue."
I finally decided to take the Numerical Methods (MNUM) course. It turns out it’s a lot more fun than I thought. There is programming involved but you can chose to use whatever language you want. This is yet another nice excuse for me to use Python instead of C++ or Java. Last semester I was able to use Python to implement the game logic for Software Application Laboratory (LAS), which is mostly an OpenGL course with IPC via sockets thrown into the mix, and to write an article on dynamic languages (focusing mostly on Python) for Software Engineering (ESOF).
But back to this semester, 3 classes into the semester and the teacher is already said something like “I’m going to learn python now. I didn’t believe when I heard someone saying it was the best language in the world, but now I see there might be some truth to that claim”. That and I suspect his next laptop might be a macbook but that’s another story.
There are a few things that make Python great for Numerical Methods. In my opinion, Python’s clear, easy to understand, syntax is the most important one.It makes algorithms easier to implement. The syntax ends up being very close to language neutral pseudocode available in numerical methods books. Also Python’s datatypes as well as those provided by other libraries can be very useful.
The following code implements the stuff in chapter 2 (determining zeros) of the course. The methods implemented are Bisection, Rope and Newton. The function returns both the solution and the number of iterations necessary to get to that solution.
from math import log
def bisect(f, a, b, e):
""" Determines zero between a and b using Bisection. """
n = 0
fa = f(a)
if fa == 0.0: return (a, n)
fb = f(b)
if fb == 0.0: return (b, n)
while (abs(a-b) > e):
c = 0.5*(a+b)
fc = f(c)
if fc == 0.0: return (c, n)
n = n + 1
if fb*fc < 0.0:
a = c
fa = fc
else:
b = c
fb = fc
if fa < fb:
return (a, n)
else:
return (b, n)
def rope(f, a, b, e):
""" Determines zero between a and b using the Rope methode. """
n = 0
fa = f(a)
if fa == 0.0: return (a, n)
fb = f(b)
if fb == 0.0: return (b, n)
while (abs(a-b) > e):
c = (a*fb - b*fa) / (fb - fa)
fc = f(c)
if fc == 0.0: return (c, n)
n = n + 1
if fb*fc < 0:
a = c
fa = fc
else:
b = c
fb = fc
if fa < fb:
return (a, n)
else:
return (b, n)
# Note: must verify that for the function f and guess c
# the method will _converge_.
def newton(f, df, c, t):
""" Determines zero between a and b using Newton """
n = 0
fc = f(c)
if fc == 0.0: return (c, n)
while (True):
fc = f(c)
dfc = df(c)
if dfc == 0:
print "dfc is 0"
return (0, -1)
dc = -fc/dfc
c = c + dc
n = n + 1
if abs(dc) < t: return (c, n)
##Tests
#def f(x): return -log(x)+4.0
#def df(x): return -1.0/x
#x= bisect(f, 1, 70, 0.00000001)
#print x
#x = rope(f, 1, 70, 0.00000001)
#print x
#x = newton(f, df, 0.1, 0.0001)
#print x
Since there’s (apparently) been some discussion (I missed) @ PrintScreen about what’s the best programming language for beginners I’ll leave here my opinion:
Python
I don’t feel like copy-pasting & summarizing a bunch of text so I’ll just leave the link for a (draft) paper I co-authored which looks at the issue in some detail
This paper aims to present an overview of Dynamic Languages in comparison with the more traditional languages, namely Java and C++. The definition of the term “dynamic language” is given and what is commonly understood nowadays when the term is used. Then one lists the most common features of these languages and the advantages and disadvantages pointed by their proponents and opponents. Furthermore is enumerated some of the domains in which dynamic languages have been more successful and explain the reasons that justify it, as well as the domains in which there are few or no reports of success. Finally, some common examples of fanaticism sorrounding dynamic languages are given.
If you’re just interested in why Python is the best choice for a first language jump to chapter 3 – Dynamic Languages in Science and Education.
