Project Euler with Python
Hello to the Education group! Thought you might be interested in some mathy Python stuff I've been doing lately. I took my Coder School students through a lesson from my book, creating fractal trees using recursion, and a few of them finished that with enough time to look at a use of recursion to do something other than draw stuff. We looked at Project Euler problem #18 <https://projecteuler.net/problem=18>. We used the same recursive method we used to make trees to search through a tree of numbers. Here's a recursive function for finding the maximum path through the triangle: def maxPath(r,c): if r == 14: #if it's in the last row return cell[r][c] #return the value of that cell else: #return the cell + the max of the maxPaths of the lower two cells return cell[r][c] + max(maxPath(r+1,c),maxPath(r+1,c+1)) I'm still tickled that recursive functions work. I picture it as a recipe for baking a loaf of bread containing the step "Bake a loaf of bread." Anyway, it worked! Problem #67 <https://projecteuler.net/problem=67> is the same idea but with a much bigger array. My method didn't scale well from 15 rows to 100 but the site predicted that and hinted that "a clever method is needed." I thought of a better method (clever? idk), and it worked on problem 18, so I copied the big honking array into a txt file and changed the parameters to handle 100 rows. Got the right answer in 4 hundredths of a second. Let me know if you're dying to see that solution, too. Maybe a Project Euler-based math course or eBook is in order. I'm so fascinated by the mathematical nature of the step from brute force to more elegant solutions and I'm sure there are lots of common factors (pun intended) that could serve as topics of discussion. It's interesting to make Python tools that seem to be needed repeatedly on PE like a prime number generator, a function to create a list of the permutations of the digits of a number, and so on. I'm interested in any feedback the group has. Peter Farrell
participants (1)
-
Peter Farrell