A pixmap shall be turned from black to white, turning all pixels to white in the process.  But for optical reasons this shall *not* happen linearly, starting at the top and continuing line by line to the bottom:

```python
for y in range(height):
  for x in range(width):
     setBit(x, y)
```

Instead it shall be done by a systematic dithering routine which selects the coordinates on which pixels are to be set in a precise pattern so that the geometrical distance between two consecutive pixels is large and a specific optical effect results.

The following diagrams show the order of the coordinates the algorithm shall produce:

2×2:
```
1 3
4 2
```
4×4:
```
 1  9  3 11
13  5 15  7
 4 12  2 10
16  8 14  6
```
8×8:
```
 1  33   9  41   3  35  11  43 
49  17  57  25  51  19  59  27 
13  45   5  37  15  47   7  39 
61  29  53  21  63  31  55  23 
 4  36  12  44   2  34  10  42 
52  20  60  28  50  18  58  26 
16  48   8  40  14  46   6  38 
64  32  56  24  62  30  54  22 
```
The pattern continues like that for each square pixmap with a width and height of a power of two (16, 32, 64, …).

But the width and the height of the pixmap can be arbitrary positive numbers.  If the pixmap's width and/or height are not a power of two, the coordinates the algorithm  would produce outside of the pixmap are skipped:

3×3:
```
1 6 3
8 5 9
4 7 2   
```
6×5:
```
 1 16  6 21  3 18
25 10 28 13 26 11
 8 23  5 20  9 24
29 14 27 12 30 15
 4 19  7 22  2 17
```
Write an algorithm which produces the coordinates of the dithering for a given width and height.

To pass the Python test cases, write a *generator* ```dithering()``` which yields coordinate tuples:
```python
g = dithering(6, 5)
for i in range(7):
  print g.next()
```
Will print:
```
(0, 0)
(4, 4)
(4, 0)
(0, 4)
(2, 2)
(2, 0)
(2, 4)
```

Difficulty: interview

Starter code:

def dithering(width, height):
	

Solutions:
def dithering(width, height, x=0, y=0, c=1):
    if width <= c and height <= c:
        if x < width and y < height: yield x, y
        return
    for u, v in (0,0), (c,c), (c,0), (0,c):
        for p, q in dithering(width, height, x+u, y+v, c+c): yield p, q

def dithering(width, height):
    size =  1
    while width > size or height > size:
        size *= 2
    if size == 1:
        yield (0,0)
    else:
        for (x, y) in  dithering(size/2, size/2):
            for t in ((x,y), (x+size/2, y+size/2), (x+size/2, y), (x, y+size/2)):
                if t[0] < width and t[1] < height:
                    yield t


from math import *
def dithering(x,y):
    def di2(x):
        if x==1:
            for i in [(0,0),(1,1),(1,0),(0,1)]: yield i
        else:
            for i,j in di2(x-1):
                for a,b in di2(1): 
                    yield i+a*(2**(x-1)),j+b*(2**(x-1))
    for i in di2(int(ceil(log(max(x,y),2)))):
        if i[0]<x and i[1]<y: yield i

from math import ceil,log2

def dithering(width, height):
    """yields coordinates in the given pixmap"""
    pow2dim = max(ceil(log2(x)) for x in [width,height])
    pos = [0]*(pow2dim)
    for _ in range((2**pow2dim)**2):
        x,y=0,0
        for idx in range(pow2dim):
            if pos[idx] in [1,2]:
                x += 2**(pow2dim - idx - 1)
            if pos[idx] in [1,3]:
                y += 2**(pow2dim - idx - 1)
        if x < width and y < height:
            yield x,y
        for idx in range(pow2dim):
            pos[idx] = (pos[idx] + 1) % 4
            if pos[idx] > 0:
                break


from math import ceil,log2
def dithering(width, height):
    size=ceil(log2(max(width,height)))
    grid=[(0,0),(1,1),(1,0),(0,1)]
    add=2
    for i in range(size-1):
        g=[]
        for gg in grid:
            g.append(gg)
            g.append((gg[0]+add,gg[1]+add))
            g.append((gg[0]+add,gg[1]))
            g.append((gg[0],gg[1]+add))
        grid=g; add*=2
    for i in range(len(grid)-1,-1,-1):
        if grid[i][0]>=width or grid[i][1]>=height:
            del grid[i]
    return iter(grid)

from itertools import cycle
from math import log2, ceil

def dithering(h,w):
    
    def rec(x,y,d,sendIt=True):
        d >>= 1
        if d:
            for g in cycle( rec(x+d*dx,y+d*dy,d,i) for i,(dx,dy) in enumerate([(0,0),(1,1),(1,0),(0,1)]) ):
                yield next(g)
        else:
            yield x,y
    
    for x,y in rec(0, 0, 2 ** ceil(log2(max(w,h))) ):
        if 0<=x<h and 0<=y<w:
            yield x,y

def gen_id():
    i = 1
    while True:
        yield i
        i += 1

def dithering(width, height):
    """yields coordinates in the given pixmap"""
    result = []
    pix_map = []
    max_step = 1
    while max_step <= max(width - 1, height - 1):
        max_step *= 2
    for i in range(height):
        temp_list = [0] * width
        pix_map.append(temp_list)
    start = (0, 0)
    recursion(result, 1, max_step, start, pix_map)
    for i in result:
        yield i

def recursion(result, step, max_step, start, pix_map):
    if step * 2 <= max_step:
        recursion(result, step * 2, max_step, (start[0], start[1]), pix_map)
        recursion(result, step * 2, max_step, (start[0] + step, start[1] + step), pix_map)
        recursion(result, step * 2, max_step, (start[0], start[1] + step), pix_map)
        recursion(result, step * 2, max_step, (start[0] + step, start[1]), pix_map)

    if len(pix_map) > start[0] and len(pix_map[start[0]]) > start[1] and pix_map[start[0]][start[1]] == 0:
        pix_map[start[0]][start[1]] = num_gen.__next__()
        result.append((start[1], start[0]))
    if len(pix_map) > start[0] + step and len(pix_map[start[0]]) > start[1] + step and pix_map[start[0] + step][start[1] + step] == 0:
        pix_map[start[0] + step][start[1] + step] = num_gen.__next__()
        result.append((start[1] + step, start[0] + step))
    if len(pix_map) > start[0] and len(pix_map[start[0]]) > start[1] + step and pix_map[start[0]][start[1] + step] == 0:
        pix_map[start[0]][start[1] + step] = num_gen.__next__()
        result.append((start[1] + step, start[0]))
    if len(pix_map) > start[0] + step and len(pix_map[start[0]]) > start[1] and pix_map[start[0] + step][start[1]] == 0:
        pix_map[start[0] + step][start[1]] = num_gen.__next__()
        result.append((start[1], start[0] + step))

num_gen = gen_id()

def dithering(width, height, x=0, y=0, c=1):
    if width <= c and height <= c:
        if x < width and y < height: yield (x, y)
        return
    for u, v in (x,y), (x+c,y+c), (x+c,y), (x,y+c):
        for p, q in dithering(width, height, u, v, c+c): yield p, q

def dithering(width, height):
    def rec(v, x, y):
        if not (x < width and y < height): return
        if not (x+v < width or y+v < height): yield x,y; return
        for k in rec(2*v, x, y): yield k
        for k in rec(2*v, x+v, y+v): yield k
        for k in rec(2*v, x+v, y): yield k
        for k in rec(2*v, x, y+v): yield k
    for k in rec(1, 0, 0): yield k

import math

def dithering(width, height):
    d = int(math.pow(2, math.ceil(math.log(max(width, height), 2))))
    return (
        (x, y)
        for x, y in _dithering(d)
        if x < width and y < height
    )

def _dithering(d):
    if d == 1:
        yield (0, 0)
        return

    fac = d//2
    for x, y in _dithering(d>>1):
        yield x, y
        yield x+fac, y+fac
        yield x+fac, y
        yield x, y+fac