Pr. Euler 18, recursion problem
I am trying to solve project euler problem 18 with brute force(I will move on to a better solution after I have done that for problem 67). http://projecteuler.net/index.php?section=problems&id=18 However I can't get the recursive function right. I always have to use return right? Unless I am printing? So I canät stack to diffferent recursive calls after each other like so: recur_left(t, p) recur_right(t,p+1) Some stuff I have tried: def recur(tree, pos): if not tree: return [] else: return [[tree[0][pos]] + recur(tree[1:], pos)] + \ [[tree[0][pos]] + recur(tree[1:], pos+1)] >>> recur([[1],[2,3],[4,5,6]],0) [[1, [2, [4], [4]], [2, [5], [5]]], [1, [3, [5], [5]], [3, [6], [6 SO it is kind of working, just not exactly like I want. A more easily parseable/readable result would be nice, I want to be able to sum() over each path preferrably. So the result should be: [[1,2,4],[1,2,5],[1,3,5],[1,3,6]] I know conceptually what has to be done. Base case: empty tree, return [] Else: recur to the left and to the right. -- http://mail.python.org/mailman/listinfo/python-list
If an OS was to be written in Python, how'w it look?
If an OS was to be written in Python and the hardware optimized for it, what changes would be made to the hardware to accomodate Python strenghs and weaknesses? Some tagged architecture like in Lisp machines? http://en.wikipedia.org/wiki/Tagged_architecture What else? -- http://mail.python.org/mailman/listinfo/python-list
Re: Pr. Euler 18, recursion problem
On Oct 6, 8:13 am, Aidan <[EMAIL PROTECTED]> wrote: > process wrote: > > I am trying to solve project euler problem 18 with brute force(I will > > move on to a better solution after I have done that for problem 67). > >http://projecteuler.net/index.php?section=problems&id=18 > > > However I can't get the recursive function right. > > > I always have to use return right? Unless I am printing? So I canät > > stack to diffferent recursive calls after each other like so: > > recur_left(t, p) > > recur_right(t,p+1) > > > Some stuff I have tried: > > > def recur(tree, pos): > > if not tree: > > return [] > > else: > > return [[tree[0][pos]] + recur(tree[1:], pos)] + \ > > [[tree[0][pos]] + recur(tree[1:], pos+1)] > > >>>> recur([[1],[2,3],[4,5,6]],0) > > [[1, [2, [4], [4]], [2, [5], [5]]], [1, [3, [5], [5]], [3, [6], [6 > > > SO it is kind of working, just not exactly like I want. > > A more easily parseable/readable result would be nice, I want to be > > able to sum() over each path preferrably. > > > So the result should be: > > [[1,2,4],[1,2,5],[1,3,5],[1,3,6]] > > > I know conceptually what has to be done. > > Base case: empty tree, return [] > > Else: recur to the left and to the right. > > This is just my opinion, but I felt the non-brute force solution to this > problem was actually simpler than trying to define a brute force > recursive solution I tried to implement a brute force algorithm at > first, until I had an epiphany with regard to how simple the problem > actually was. Then I faced palmed. But let's say you have [[1],[1,10],[1,2,300],[10,1,1,1]]. you must check all solutions right? there is no pattern. if you start from the bottom and eliminate paths that seem to be losing can you regain that later up in the pyramid if it turns out one side gets bigg again? -- http://mail.python.org/mailman/listinfo/python-list
Trying to install module, No module named scipy_distutils.core (but i have scipy)
trying to install PyKF-0.1 (Kalman Filters) http://pykf.sourceforge.net/ I have Numpy, Scipy, Matplotlib installed an have successfully installed other packages using them. $ setup.py Traceback (most recent call last): File "./setup.py", line 2, in from scipy_distutils.core import setup ImportError: No module named scipy_distutils.core #!/usr/bin/env python from scipy_distutils.core import setup version = "0.1" setup( version=version, author="Chris Fonnesbeck", author_email="[EMAIL PROTECTED]", description="Version %s of PyKF" % version, license="GNU GPL", name="PyKF", url="pykf.sourceforge.net", packages=["PyKF"], ) -- http://mail.python.org/mailman/listinfo/python-list
Re: Is try-except slow?
On Sep 3, 2:36 am, John Machin <[EMAIL PROTECTED]> wrote: > On Sep 3, 9:44 am, ssecorp <[EMAIL PROTECTED]> wrote: > > > or why does this take so god damn long time? > > Because your code does so many god damn unnecessary things. Apart from > the fact (as pointed out already by Robert) that you are needlessly > finding the sizes (Y, X) that are already available: > > (1) You are executing a try block Y*X (approx) times instead of the Y+X > +2 times it would take if you were to do preliminary probes to find Y > and X > (2) You are doing range(1, 1000) Y times instead of once [see question > below] > (3) You are doing the method lookup im.getpixel Y*X times instead of > once > (4) you are doing the method lookup row.append Y*X times instead of Y > times > > > and if I run into an IndexError it break out of the inner loop right? > > so having range up to 1000 or 1000 wouldn't matter if biggest > > working x is 800? > > > def getPixels(fileName): > > im = PIL.Image.open(fileName) > > colors = [] > > for y in range(1, 1000): > > Are you sure that both occurrences of range(1, 1000) shouldn't be > range(1000)? > > > row = [] > > for x in range(1, 1000): > > try: > > color = im.getpixel((x,y)) > > row.append(color) > > except IndexError: > > break > > colors.append(row) > > return numpy.array(colors) > > and it appears that you haven't bothered to read the manual section on > Image.getpixel: > """ > Note that this method is rather slow; if you need to process larger > parts of an image from Python, you can either use pixel access objects > (see load), or the getdata method. > """ how could I do getpixel once when x and y s changing? anyway I rewrote and saw I did a lot of stupid stuff. this is fast: def getPixels5(fileName): im = PIL.Image.open(fileName) colors = [] r, c = im.size for y in range(0, c): row = [] for x in range(0, r): color = im.getpixel((x,y)) row.append(color) colors.append(row) return numpy.array(colors) but I don't need it anuyway apparently since there already was such methods :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Is try-except slow?
is this faster btw? I guess big doesn't help, it's only retrieved once anyway? But is rows retrieved in every loop? the python interpreter aint too smart? def getPixels(fileName): im = PIL.Image.open(fileName) colors = [] r, c = im.size big = range(0, c) rows = range(0, r) for y in big: row = [] for x in rows: color = im.getpixel((x,y)) row.append(color) colors.append(row) return numpy.array(colors) -- http://mail.python.org/mailman/listinfo/python-list
which of these 2 quicksorts is faster?
qsort can handle bigger lists it seems, making less recursive calls before finishing(quicksort blows the stack when sorting range(100,-1000,-1). qsort does more work though right? is there a way to speed up that? is the built-in sort not defined recursively? def quicksort(lista): if len(lista) != 0: return quicksort([x for x in lista[1:] if x < lista[0]]) + [lista[0]] + \ quicksort([x for x in lista[1:] if x >= lista[0]]) else: return [] def qsort(lista): l = len(lista) if len(lista) != 0: return qsort([x for x in lista[:l/2]+lista[l/2+1:] if x < lista[l/2]]) + \ [lista[l/2]] + \ qsort([x for x in lista[:l/2]+lista[l/2+1:] if x >= lista[l/2]]) else: return [] -- http://mail.python.org/mailman/listinfo/python-list
Re: which of these 2 quicksorts is faster?
On Sep 10, 12:29 pm, Fredrik Lundh <[EMAIL PROTECTED]> wrote: > process wrote: > > qsort can handle bigger lists it seems, making less recursive calls > > before finishing(quicksort blows the stack when sorting > > range(100,-1000,-1). > > qsort does more work though right? is there a way to speed up that? > > > is the built-in sort not defined recursively? > > what makes you think you can write a better sort than the built-in > algorithm by typing in some toy quick-sort implementations from a > "sorting for dummies" article? > > Where did I write that I was trying to do that? I am merely trying to learn. Get some social skills dude. -- http://mail.python.org/mailman/listinfo/python-list
Is len O(n) or O(1) ?
Python uses arrays for lists right? def quicksort(lista): if lista == []: lista else: return quicksort([x for x in lista[1:] if x < lista[0]]) + [lista[0]] + \ quicksort([x for x in lista[1:] if x >= lista[0]]) or def quicksort(lista): if len(lista) == 0 lista else: return quicksort([x for x in lista[1:] if x < lista[0]]) + [lista[0]] + \ quicksort([x for x in lista[1:] if x >= lista[0]]) wait first one raises TypeError unsupported operand types. -- http://mail.python.org/mailman/listinfo/python-list
Re: Is len O(n) or O(1) ?
ok but if len is O(1) then it doesnt matter? compared to if not lista: return [] i mean. -- http://mail.python.org/mailman/listinfo/python-list
I tried erlang-ish [1|2] in python and something came out...
In erlang you can cons like this: [1|2]. i tried this in python and it didnt raise an error but i dont know what the result do >>> [1|2] [3] >>> [2|2] [2] >>> a = [2|2] >>> a [2] >>> [2|3] [3] >>> [2|1] [3] >>> -- http://mail.python.org/mailman/listinfo/python-list
Why no tailcall-optimization?
Why doesn't Python optimize tailcalls? Are there plans for it? I know GvR dislikes some of the functional additions like reduce and Python is supposedly about "one preferrable way of doing things" but not being able to use recursion properly is just a big pain in the a**. -- http://mail.python.org/mailman/listinfo/python-list
Pyflix, confused about super() call
Anyone using Pyflix for the Netflix prize.
How can it call super to itself in its init-method?
-
#!/usr/bin/env python
'''Sample baseline averaging algorithms.'''
import numpy as N
from pyflix.algorithms import Algorithm
class MovieAverage(Algorithm):
'''Baseline algorithm that computes the average of all the votes
for a movie
and predicts that for every user.
This algorithm returns an RMSE score of 1.0528 on the scrubbed
dataset.
'''
def __init__(self, training_set):
self._movie_averages = {}
super(MovieAverage,self).__init__(training_set)
def __call__(self, movie_id, user_id):
try: return self._movie_averages[movie_id]
except KeyError:
avg =
N.average(self._training_set.movie(movie_id).ratings())
self._movie_averages[movie_id] = avg
return avg
class UserAverage(Algorithm):
'''Baseline algorithm that computes the average of all the votes
for a user
and predicts that for every movie.
This algorithm returns an RMSE score of 1.0688 on the scrubbed
dataset.
'''
def __init__(self, training_set):
self._user_averages = {}
super(UserAverage,self).__init__(training_set)
def __call__(self, movie_id, user_id):
try: return self._user_averages[user_id]
except KeyError:
avg =
N.average(self._training_set.user(user_id).ratings())
self._user_averages[user_id] = avg
return avg
class DoubleAverage(MovieAverage,UserAverage):
'''Returns the average of L{MovieAverage} and L{UserAverage}.
This algorithm returns an RMSE score of 1.0158 on the scrubbed
dataset.
'''
def __call__(self, movie_id, user_id):
return (MovieAverage.__call__(self,movie_id,user_id) +
UserAverage.__call__(self,movie_id,user_id)) / 2
--
http://mail.python.org/mailman/listinfo/python-list
what does ` ` do in ' '.join([`x * x` for x in range(1, 6)])?
' '.join([`x * x` for x in range(1, 6)]) exactly what does this symbol do and what does it stand for? -- http://mail.python.org/mailman/listinfo/python-list
What is not objects in Python?
I have heard some criticism about Python, that it is not fully object- oriented. What is not an object in Python? Why isn't len implemented as a str.len and list.len method instead of a len(list) function? -- http://mail.python.org/mailman/listinfo/python-list
Python 2.6, GUI not working on vista?
i just downloaded 2.6 and when running the gui nothing happens. anyone else with the same problem? -- http://mail.python.org/mailman/listinfo/python-list
Inheritance but only partly?
Let's say I have a class X which has 10 methods. I want class Y to inherit 5 of them. Can I do that? Can I do something along the lines of super(Y, exclude method 3 4 7 9 10) ? -- http://mail.python.org/mailman/listinfo/python-list
Recursion, generate all pyramid-paths, not working
http://projecteuler.net/index.php?section=problems&id=18 def recur(tree, pos): if not tree: return [] else: return [[tree[0][pos]] + recur(tree[1:], pos)] + \ [[tree[0][pos]] + recur(tree[1:], pos+1)] i have a list with [[1],[2,3],[4,5,6],[7,8,9,10]] it i a pyramid so first is 1 then 23 then 456 thrn 78910 from one can go to 2 or 3. from 2 to 4or5, from 3 to 5 or 6. i want to generate every path and compute the cost. But I can't get the recursion right. It generates all the paths kind of but not in a matter i want to. also having to return after each other doesnt do anything right? like so: return [[tree[0][pos]] + recur(tree[1:], pos)] return [[tree[0][pos]] + recur(tree[1:], pos+1)] -- http://mail.python.org/mailman/listinfo/python-list
