def Adventure():

hljs.initHighlightingOnLoad(); var _gaq = _gaq || []; _gaq.push(['_setAccount', 'UA-34045861-1']); _gaq.push(['_trackPageview']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })(); .desc a:hover { border-bottom: 1px dotted orange}

[hellositong-blog]

Programming Resolutions

Last year was the first year in a long time that I did not make any resolutions over the year. I'd like to get back to it this year, with a few that I should be able to keep. 1. Articulation: 100 posts about programming things I've encountered and want to share. 2. Get involved: Contribute a couple patches or a bug fix to an open source project. 3. Push myself: Do a weekend project and get it on the front page of HN. 4. Read more books: I need to expand my knowledge beyond just reading the news and blogs. Here's to a great 2013!

[hellositong-blog]

Project Euler 6

You are asked to find the difference between the square of the sum and the sum of the squares of the first 100 natural numbers. So: (1 + 2 + ... + 99 + 100)^2 - (1^2 + 2^2 + ... + 99^2 + 100^2). This is trivially easy to brute force on a computer, especially with the range(1,101) function in python. Two loops will get you a solution in practically no time. Alternatively, a reduce and a map & reduce will get you there in no time too. However, this problem is actually probably faster to just do by hand. To the best of my knowledge, this is the first one of the Project Euler problems that is like this. You just need to be familiar with two famous series in mathematics. I have the 1 + 2 + ... + 99 + 100 series internalized, it is simply n(n+1)/2. I had to look up the 1^2 + 2^2 + ... + 99^2 + 100^2 power series, but the formula is n(n+1)(2n+1)/6. Here's the code I wrote since I wanted something I could save in my Project Euler folder.

# Two famous series def sum_of_squares(n): return (n)*(n+1)*(2*n+1)/6 def square_of_sum(n): return (n*(n+1)/2)**2 def main(n): return sum_of_squares(n) - square_of_sum(n)

[hellositong-blog]

HTML Checkbox Form Gotcha

I've been working on implementing a toy web app on Flask. It's been very straightforward so far, the work I did on my WSGI server was a good stepping stone into this WSGI framework. I just stumbled upon something I will refer to as a HTML Checkbox Form Gotcha. HTMLCFG? So basically, I am building the login page for the web app and I have a checkbox that I wanted to be a boolean for whether the user was registering for the first time or just logging in normally.

<input name="register" type="checkbox" value="true" />

Then, I would use the following code in Flask access the state of the checkbox:

if request.form['register']: # do stuff

However, I kept getting a HTTP 400 Bad Request. After some sleuthing, it turns out that POST requests don't include unchecked checkboxes. So there is no request.form['register'] entry if the checkbox isn't checked by the user before submission. Here's how I ended up working around it.

registering = False if 'register' in request.form: # do register logic else: # do normal login logic

[hellositong-blog]

Project Euler 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? I've found that I usually want to solve these problems using a more functional programming style. For instance, my solution uses uses a recursive prime_factorization helper function and reduce. But then again, it also uses iterative loops, but only because I didn't feel like keeping track of the laundry list of factors recursively :). Anyways, the format of my solution is as such: - Initial notes about the problem - General solution for any positive integer n.

# 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 # Basically 2520 = product of the prime factors of the above numbers # So... 2520 = 2*3*2*5*7*2*3 # A general solution would check if the prime factorization of some 'n' # is already in the set of prime factorizations from the 'n-1' term. def prime_factorization(num, divisor=2): """Given an non-neg int num, return the prime factorization in a list.""" if num < 2: return [num] elif num % divisor: divisor += 1 return prime_factorization(num, divisor) else: return prime_factorization(num/divisor, divisor) + [divisor] def product(a, b): """Returns a * b.""" return a * b def super_product(num): """Given an integer num, find the smallest positive number that is divisible by all integers [1, num]. """ factors = [] while num > 1: pf = prime_factorization(num) for factor in pf: try: factors.remove(factor) except ValueError: continue factors += pf num -= 1 return reduce(product, factors)

[hellositong-blog]

On generators and len

So one of the WSGI server specifications is that if a WSGI application doesn't supply the Content-Length response header, it is the job of the WSGI server to try to determine the Content-Length of the response body (if possible). This is straightforward enough for the average WSGI app, which will return the response body in a list object. However, WSGI apps also have the option of using a generator to return the response body (since the specification only requires that the app return is an iterable).

So can we apply the len function to the output of a generator?

The answer is no. Generators are simple constructs that just yield values when you iterate on them, immediately passing output along. And since generators keep no memory of past generated values, they have no idea what the length of their output is or will be. Therefore they don't have a len attribute.

So how do we send the client the Content-Length if the app is a generator?

Well, in HTTP/1.1, some servers and clients support the chunked transfer coding. This allows servers to send response bodies in chunks, as they are available. Each chunk will have it's own Content-Length. I hope to support chunked transferring in whiskey, so I can always provide a Content-Length. I'll be sure to post about my implementation.

[hellositong-blog]

Become a better programmer

Hacker School Winter 2013 applications are open TODAY! If you're interested, I'll save you the time and say you SHOULD apply. Let me know if you're interested and have questions :)

[hellositong-blog]

Removing punctuation from a text string

I was working on a side project last week. It's called Linguist and one of the components of the project requires me to have a large corpus of English word frequencies. After some research, I decided I could focus on all the words in the Scrabble Official Word List (OWL) and wrangle out the word counts using all English books on Project Gutenberg. This was a bit more strenuous of an undertaking than I had anticipated, as Project Gutenberg's English library is quite sizable. So, obviously, I first need a quick way to remove all punctuation from these ebooks so I can iterate through them to build my word count dictionary.

So what's a fast way to do that in Python?

Let's consider using: string.replace, sets, regex, and string.translate. We'll use A Christmas Carol as our benchmark text, since it's December.

f = open('A_Christmas_Carol.txt', 'r') book = f.read() f.close()

Methods

# sets punctuation_set = set(string.punctuation) def set_method(book): return ''.join(char for char in book if char not in punctuation_set) # regex punctuation_regex = re.compile('[{0}]'.format(re.escape(string.punctuation))) def regex_method(book): return punctuation_regex.sub('', book) # string.replace def replace_method(book): for punctuation in string.punctuation: book = book.replace(punctuation, '') return book # string.translate def translate_method(book): return book.translate(None, string.punctuation)

Results

sets : 0.0455198287964 seconds. regex : 0.0134680271149 seconds. replace : 0.0041608810424 seconds. translate: 0.0006558895111 seconds.

So, when you're looking at stripping punctuation from gigabytes of text files, it's safe to say that you should be using string.translate.

[hellositong-blog]

Furthermore HTTP has become quite popular lately and browsers are no longer the only clients that are using HTTP. For instance, many revision control system use it.

Flask Quickstart Guide

[hellositong-blog]

from constants import *

Is this pythonic? According to the Python documentation on Language Constructs You Should Not Use, the following tops the list:

from module import *

However, here's a problem I'm running into. I want some constants to be use-able over a couple different modules, but I don't want to call constants.FOO every time I need to use them. So, what's a guy to do? Well, I'm going to throw "caution" to the wind and just create a "constants.py" file and attach a "from constants import *" to the files I need these constants in. I feel like this situation falls under category 3 of the When It Is Just Fine section. What do you think?

[hellositong-blog]

Project Euler 3

I've updated the method on this solution after discussing and optimizing with James. Here is his code in Python:

n = 600851475143 pfact = 0 i = 2 while i < n+1: while n % i == 0: n = n/i pfact = i i += 1 print pfact

The awesome thing about this code (besides that it's so short), is that it naturally pulls out all the prime factors of a number in two while loops. It's pitfall is when you are given large prime number to begin with (such as 600851475149), these loops would have to count up to the prime number before it found it. My solution's pitfall is if you are given a number that has numerous small prime factors, such as 2^32, which only has the prime factor 2. However, by merging the ideas of my and James' solution, we can come up with a much more optimal solution that avoids both of our pitfalls:

largestPrimeFactor = function(num) { i = 2 if(isPrime(num)){ return(num) } while(i < num){ while(num % i == 0) { # Used to be if(num % i == 0) num = num/i # redefine num by pulling out the lowest prime factor if(isPrime(num)){ return(num) } } i = i + 1 } }

So, 2^32 and 600581475149 both run instantly instead of never.

[hellositong-blog]

Favorite term of the day

In parallel computing, a problem in which all the sub-processes are completely independent and do not rely on each other is called an "Embarrassingly Parallel Problem". So I guess the routine eureka exclamation in this field is: "Ah! Turns out this is an embarrassingly parallel problem!" *facepalm*.

[hellositong-blog]

What I've learned about UDP and TCP (today)

User Datagram Protocol (UDP) is a type of internet protocol that is well suited for sending no more than a few one-time packets. There is no handshake process, and all forms of communication must be built into the client and server sides respectively. Generally processes that utilize the UDP structure accept that packets may be lost in delivery or translation and prefer lost data over delayed data. Usually these are applications that run on real-time such as multiplayer games (where it's okay to skip a frame since your next packet will place you in the right spot) or streaming media (better to get a hiccup than random sound clips out of place). Also, UDP gives way to a fancy ability called broadcasting, which allows you to blast a local network with the same packet all at once. This is good for updating some applications that should be synced up over the network. Transmission Control Protocol (TCP) is a type of internet protocol that is well suited for sending reliable, streams of data in an established connection between server and client. Before any data is transferred, a handshake must be completed between server and client. This is called the SYN, SYN-AWK, AWK process, where the client will send a SYNchronize packet to the server, the server will receive the packet and send back a SYNchronize-ACKnowledgement to the client, and the client will confirm the ACKnowledgement back to the server. This process establishes the connection between server and client on the specified ports. Data is then transferred around in multiple bursts, which is why TCP is not used by applications sending one-time information. Packets may still be lost, but the receiving party will determine if this happens and send re-transmission requests to the sender and reassemble the full structure of the packets later. If there is a lot of congestion in the data stream and the server cannot handle requests quickly enough, TCP applications will generally practice some prudence in sending future packets - limiting the rate of transmission as congestion occurs. The majority of network applications use follow the TCP structure.

[hellositong-blog]

You have a port number, what service does it refer to?

On Unix machines you can go into your handy dandy service list. The path is as follows:

/etc/services

For example: HTTP is port 80.

[hellositong-blog]

IP Addresses

IP Addresses are network addresses that are (for IPv4) four bytes long, with each byte separated by a period. Recall that a byte is generally 8 bits, so the byte can take a value of 0 - 255, which is a range of 2^8 = 256 values. Hence, something like this: 130.192.24.200 IP Addresses are important because when computer want to send packets of data anywhere, it needs a.) the data to send (binary strings) and b.) a destination (IP Address).

[hellositong-blog]

TypeError: this constructor takes no arguments

If you're ever creating an instance of your newly defined class object and you get this error - even though you definitely specified that you need to call the class with some parameters, I may know what your problem is. Solution to your confusion: __int__ != __init__ (Yes, I just encountered this in my code *facepalm*)

[hellositong-blog]

Unicode pain, no more!

FYI and Note To Self: This is something I have been experiencing intimately while I have been building a Wikipedia bot with some text parsing requirements. Bookmark and study this lecture on what byte strings and unicode strings really are. Do it now. Unicode sandwich.

[hellositong-blog]

Installing numpy for python 3 in Ubuntu

^ Note to self See the forum posts here