Thu Oct 31

First order of business : discuss your midterm projects : what you have done so far and where are you going next.

It might be fun to see an example of something with a bit more substance than we've been doing : tubes.py that implements a series of tubes, adventofcode 2017 #19). (Me having too much fun. 🙂 )

This is the sort of thing that could be a final project ... or is perhaps even a bit bigger than that. Notice though that (a) it doesn't use any python syntax or concepts that you haven't already seen, (b) it's complexity is managed by many functions and tests, (c) it has a reference to a URL where I looked something up that I didn't know, and (d) there's an executive summary at the top, similar to the discussion that I would like to see from you for your projects.

While I've been emphasizing functions and testing - and for good reasons - the collatz problem is actually small enough that it can be done pretty cleanly in a "all-in-one-let-it-rip" style, without functions or tests.

Here is a shorter version, including saving the known results (called "memoization", mentioned in class last time).

This version runs in under 3 seconds on my laptop - ten times faster than the one I showed Tuesday. Not because its fewer lines of code, but because it remembers earlier results and takes shortcuts, like the network of lines in the xkcd colltaz cartoon.

""" collatz.py """
start_max = 1000000
seen_max =  10000000
seen_length = [0]*(seen_max + 1)    # sequence lengths already seen
(longest, longest_start) = (0, 0)
print("Collatz search up to {} ...".format(start_max))
for start in range(1, start_max + 1):
    c = start
    length = 0
    while c != 1:
        if c < seen_max and seen_length[c] != 0:     # Seen this c before?
            length = length + seen_length[c]         #   Fill in its length,
            c = 1                                    #   and jump to the end.
        else:                                        # Otherwise,
            length += 1                              #   take one step.
            if c % 2 == 0:
                c = c // 2
            else:
                c = 3 * c + 1
    seen_length[start] = length                      # Remember this one.
    if length > longest:                             # Longest so far?
        (longest, longest_start) = (length, start)   #   Save it.
print("Longest sequence starts at {} and has {} steps.".format(
    longest_start, longest))

$ time python collatz.py
Collatz search up to 1000000 ...
Longest sequence starts at 837799 and has 524 steps.
real    0m2.906s
user    0m2.848s
sys 0m0.048s

objects

Next topic : defining your own objects

We started looking at thewe with the class notes for next Tues](objects).

Please start reading chapter 10 which covers this.

In class I wrote the attached person.py code.

attachments

		last modified	size
	person.py	Wed Dec 18 2024 01:42 am	594B