Posts Tagged ‘prob28’

Problem 28 – Spirals

September 27, 2009

In problem 28 we construct a spiral starting with 1 in the center, and build our way outwards clockwise. Then we are supposed to find the sum of the diagonals.

I figured there should be some formula for the sum of the diagonal entries, depending on the size of the grid you want to stop at. If we only compute diagonal elements when we have a square, the square will always have sides of odd length. So we should take a number n, and compute the appropriate sum of the elements in the 2n+1 by 2n+1 grid. I’ll write down the sum for the case n=3 in the following manner:

  1^2 + (1^2+2) + (1^2+2*2) + (1^2+3*2)
+ 3^2 + (3^2+4) + (3^2+2*4) + (3^2+3*4)
+ 5^2 + (5^2+6) + (5^2+2*6) + (5^2+3*6)
+ 7^2

That seems to make a pattern pretty clear. We’re adding up odd squares (the rising diagonal coming off of the central 1) and then some offsets of those squares. The formula for the sum of squares is

\displaystyle \sum_{i=1}^{m} i^2 = \frac{m(m+1)(2m+1)}{6}

and we can write the sum of odd squares as

\displaystyle \sum_{k=1}^{m} (2k-1)^2 = \sum_{k=1}^{2m}k^2 - \sum_{k=1}^{m} (2k)^2 = \sum_{k=1}^{2m} k^2 - 4\sum_{k=1}^{m}k^2.

Pushing some symbols around, I got down to the following formula for the sum of the diagonal elements in a 2n+1 by 2n+1 square:

\frac{16}{3}n^3 + 10n^2 + \frac{26}{3}n + 1.

Of course, those thirds make me nervous. The answer is clearly supposed to be an integer. But it’s ok. Gathering up those thirds we get

\frac{2}{3}n(8n^2+13)+(10n^2+1)

for the sum. Now, if n is divisible by 3, we’ll get an integer in that first term. And if n is not divisible by 3, it is either 1 or 2 mod 3, and so 8n^2+13\equiv -1(1)+1=0\pmod{3}. So that third isn’t going to cause problems.

It’s pretty easy to code up the solution when you’ve got such a formula. By using an if-switch, I took into account the mod-3 thing above so that I was never working with floats. Here’s my code:

def solve(n):
    ret = 10*n*n + 1
    factor = 8*n*n+13
    if(n % 3 == 0):
        ret += 2*(n//3)*factor
    else:
        ret += 2*n*(factor//3)
    return ret

Then I decided it would be a fun little exercise to actually cook up some code to generate the spiral. I knew this would have slower run-time, and require more resources, but I wanted to write down the code anyway.

The way I thought about it, I’ll keep track of my current coordinates (posx,posy), starting at (0,0). To go to the next place, I look to my right, and see if that spot is filled. If it is, I just continue on in whichever direction I was going; otherwise, I move to that spot to my right. This means I need to keep track of which direction I’m facing. There are only 4 directions, and they cycle, so I’ll think of direction as an integer mod 4. If I make 0,1,2,3 correspond to Up, Right, Down, Left, then (my direction)+1 is the direction to my right. After writing down a little grid of input directions, and what they meant about where to move next, I came up some little formulas, and was good to go.

I had originally thought I’d wrap up an implementation into a class, so that you could index via [x][y], but then I realized that wouldn’t quite work, and you’d need to just index as [(x,y)]. At that point, I figured I might as well just use a dictionary type. And away I went:

def dx(dir):
    """ interpret dir as 0,1,2,3 = N,E,S,W, return what dx is in that dir """
    return (dir%2) * (2-dir)

def dy(dir):
    """ dir as 0,1,2,3 = N,E,S,W return what dy is in that dir """
    return ((dir+1)%2) * (1-dir)

def solve(n):
    """ Build up a 2n+1 by 2n+1 grid, then sum diagonals """
    grid = {}
    posx, posy = 0, 0
    idx = 1
    dir = 0 # dir in 0,1,2,3 = N,E,S,W
    while(posx <= n):
        grid[(posx,posy)] = idx
        idx += 1
        # find the position to my right
        rsposx,rsposy = posx + dx((dir+1)%4), posy + dy((dir+1)%4)
        if(grid.has_key((rsposx,rsposy))):
            # keep going the direction I was going
            posx,posy = posx + dx(dir), posy + dy(dir)
        else:
            # turn right
            posx,posy = rsposx, rsposy
            dir = (dir+1)%4
    # sum the diagonals
    ret = sum([grid[(x,x)] for x in xrange(-n,n+1)])
    ret += sum([grid[(x,-x)] for x in xrange(-n,n+1)])
    ret -= 1 # the origin got counted twice
    return ret

Only two days behind my artificial deadline too.

Advertisements