triangle-check.py

#!/usr/bin/python
# -*- encoding: utf-8 -*-
from __future__ import division

from math import ceil

def triangles(n):
    radius = 2 ** int(ceil(n / 2))
    skip = 1 + (n % 2)
    counts = {}
    for y in range(0, radius+1, skip):
        for x in range(radius - y, -1, -2):
            # print x, y, skip
            counts["N"] = counts.get("N", 0) + x // 2;
            counts["E"] = counts.get("E", 0) + y // 2;
            counts["S"] = counts.get("S", 0) + min(x // 2, y);
            counts["W"] = counts.get("W", 0) + min(x, y // 2);
            counts["NW"] = counts.get("NW", 0) + min(x, y) // skip;
            counts["SE"] = counts.get("SE", 0) + min(x, y) // skip;
            counts["SW"] = counts.get("SW", 0) + y // skip;
            counts["NE"] = counts.get("NE", 0) + min(radius - x - y, y) // skip;
    
    counts["total"] = sum(counts.values())
    return counts

def compute(n):
    if n % 2 == 0:
        k = n / 2
        e = 2**k
        return {
            "SW": e * (e + 2) * (2*e + 5) / 24,
            "NE": e * (2*e*e + 3*e - 8) / 48,
            "W": (2 * e**3 + 3*e*e - 6*e - 12 + 4*(-1)**k) / 72,
            "S": (2 * e**3 + 3*e*e - 6*e - 12 + 4*(-1)**k) / 72,
            "NW": e * ( e*e + 3*e + 2 ) / 24,
            "SE": e * ( e*e + 3*e + 2 ) / 24,
            "N": e * (e+1) * (e+2) / 24,
            "E": e * (e+1) * (e+2) / 24,
            "total": (50 * e*e*e + 147 * e*e + 60 * e - 48 + 16*(-1)**k) / 144,
        }
    else:
        k = (n - 1) / 2
        e = 2**k
        r = {
            "SW": e * (e+1) * (e+2) / 6,
            "N": e * (e+1) * (e+2) / 6,
            "E": e * (e+1) * (e+2) / 6,
            
            "NE": e * (e+2) * (2*e-1) / 24,
            "SE": e * (e+2) * (2*e-1) / 24,
            "NW": e * (e+2) * (2*e-1) / 24,
            
            "total": (140 * e*e*e + 318 * e*e + 60 * e - 48 + 16*(-1)**k) / 144
        }
        if k % 2 == 0:
            r["S"] = r["W"] = (e-1)**2 + (e - 4)*(e - 1)*(2*e - 5) / 18
            # r["total"] = (70 * e*e*e + 159 * e*e + 30 * e - 16) / 72
        else:
            r["S"] = r["W"] = (e+1) * ( 2*e*e + e - 4 ) / 18
            # r["total"] = (70 * e*e*e + 159 * e*e + 30 * e - 32) / 72
        
        return r

for i in range(3, 30):
    t = triangles(i)
    computed = compute(i)
    print i, ":", repr(t)
    for dir in computed.keys():
        if t[dir] != computed[dir]: print dir + " mismatch! " + str(computed[dir])