A brief study in optimization (Part 2)

Ok so we know what a triangle square number is.

Wait, What?

You again. Go back and read part 1, I'll wait.

Ok, I'm done. What's the next step?

Well today, we're going to write a quick program to try and generate some triangle square numbers. It will be the starting point for our explorations. (Don't leave a comment about how ugly the design is. That's the point.) I'm going to use Python 3 for these examples, because it's available to everyone, and the syntax is pretty easy to follow along with.

I don't want to install anything. Your blog has like 2 articles on it, and it's not even all that good.

You don't need to install Python on your system. One option is repl.it, but there are loads of other options. I'd recommend biting the bullet and installing Python and IPython, to make your life that much easier, but it's your call.

Anyway, Can I get back to business?

Sure.

Thanks. Today's approach is going to be to generate a list of triangle numbers less than 100,000, a list of square numbers less than 100,000 and then look at both lists to find numbers that appear in both places. First, let's generate the list of triangle numbers.

n = 1
current_triangle = 0
triangle_numbers = []
while current_triangle < 100000:
    current_triangle = current_triangle + n
    n = n + 1
    triangle_numbers.append(current_triangle)

Next we need to generate a list of square numbers. The logic will be pretty similar:

n = 1
current_square = 0
square_numbers = []
while current_square < 100000:
    current_square = n * n
    n = n + 1
    square_numbers.append(current_square)

Now that we've generated the lists of triangle and square numbers, we need to go through and find numbers that are the same in both: (This is a really naive merge algorithm. We'll look at better options coming up later in the series.)

triangle_square_numbers = []
for triangle in triangle_numbers:
    for square in square_numbers:
        if triangle == square:
            triangle_square_numbers.append(triangle)
            break

print(triangle_square_numbers)

Run all of this code, and you'll see that there are 4 triangle square numbers less than 100,000. [1, 36, 1225, 41616] You may also notice that it's painfully slow.

Yeah, man, what gives?

We'll do the analysis of this algorithm next time.

Wait, You're going to leave us hanging? I know you wrote all of these at the same time!

Yeah, but people don't want to be overloaded. See you next time.