0001
0011
0111
1111

0001 1001
0111 1011
1111 0111
1111 1111

from random import randint

w,h=64,32
pixels=[[int(((x-25)**2+(y-18)**2)**.5/4)%2 for x in range(w)]for y in range(h)]

for row in pixels:
    print(" ".join(['.@'[x] for x in row]))

tiles=[[pixels[k//(w//8)*8+j//8][k%(w//8)*8+j%8] for j in range(64)] for k in range(w*h//64)]


num_tiles=len(tiles)
cset_size=20

charset=[]
indices=[]
for i in range(cset_size):
    charset.append(tiles[randint(0,len(tiles)-1)])


last_error=1e33

for iteration in range(10):
    # first, find indices
    indices=[]
    counts=[0,]*cset_size
    error_this_iteration=0
    for i in range(num_tiles):
        best_error=1e30
        for j in range(cset_size):
            this_error=0
            for p in range(64):
                delta=(tiles[i][p]-charset[j][p])
                this_error+=delta*delta
            if this_error<best_error:
                best_error=this_error
                best_index=j
        error_this_iteration+=best_error
        indices.append(best_index)
        counts[best_index]+=1
    print"total error =",error_this_iteration
    if error_this_iteration==last_error:
        break
    last_error=error_this_iteration

    #then, replace each char with the average of all the source tiles it's meant to approximate
    charset=[[0 for i in range(64)] for j in range(cset_size)]
    for i in range(num_tiles):
        index=indices[i]
        for p in range(64):
            charset[index][p]+=float(tiles[i][p])/counts[index]

    #..and replace any unused chars with random selections from the original
    for i in range(cset_size):
        if counts[i]==0:
            charset[i]=(tiles[randint(0,len(tiles)-1)])


print("")
for y in range(h):
    for x in range(w):
        i=indices[y//8*(w//8)+x//8]
        print ".@"[int(0.5+charset[i][(y%8)*8+(x%8)])],
    print