#!/usr/bin/python
# -*- coding: utf-8 -*-
"""Midpoint circle algorithm.

Thanks to <https://en.wikipedia.com/wiki/Midpoint_circle_algorithm> I 
finally understand how to rasterize circles efficiently!

"""
import itertools

def mid(r):
    # `e` is always x² + y² - r²
    x, y, e = r, 0, 0
    while x > y:
        if e > 0:
            e -= x + x - 1
            assert e <= 0
            x -= 1

        yield x, y

        # For efficiency you could fold this into the above update of
        # `e` in the decrementing-`x` case.
        e += y + y + 1
        y += 1

def aa_circle(n):
    "ASCII art, not antialiased."
    xs = [x for x, y in mid(n)]
    ys = sorted(mapreduce(identity, max, mid(n)).values())

    for x in itertools.chain(ys, reversed(xs), xs[1:], reversed(ys)):
        n = (40 - 2*x) / 2
        print '  ' * n + '##' * x * 2 + '  ' * n

def mapreduce(map_func, reduce_func, items):
    result = {}
    for item in items:
        k, v = map_func(item)
        if k not in result:
            result[k] = []
        result[k].append(v)
    return dict((k, reduce_func(v)) for k, v in result.items())

def identity(x):
    return x

if __name__ == '__main__':
    for ii in range(20):
        aa_circle(ii)