from pygame.locals import *
import pygame, sys, random

fn = sys.argv[1]

screen = pygame.display.set_mode((1900,1000))
pic = pygame.image.load(fn)
pic.convert()
W,H = pic.get_size()
enough = W*H/3
screen.blit(pic, (0,0))

ORTH = [(-1,0), (1,0), (0,-1), (0,1)]
def orth(p):
    return [(p[0]+dx, p[1]+dy) for dx,dy in ORTH]

def look(p):
    x,y = p
    if 0 <= x < W and 0 <= y < H:
        return sum(pic.get_at(p))
    else:
        return -1

# index picture
locs = [(x,y) for x in range(W) for y in range(H)]
grid = dict( (p,sum(pic.get_at(p))) for p in locs )
rank = sorted( grid.values() )
median = rank[ len(rank)/2 ]
dark = dict( (k,v) for k,v in grid if v < median )
good = dict( (k,v) for k,v in grid if v > median )
pictotal = sum(rank)
picavg = 1.0 * pictotal/(W*H)
print('Indexed')

# compute zone values:
block = 16
xblocks, yblocks = (W-1)/block, (H-1)/block
zones = dict( ((zx,zy),0) for zx in range(xblocks) for zy in range(yblocks) )
for x,y in locs:
    div = (x/block, y/block)
    if div in zones:
        colsum = sum( pic.get_at((x,y)) )
        zones[div] += colsum

# choose best zones:
zonelist = sorted( (v,k) for k,v in zones.items() )
cut = int(xblocks * yblocks * 0.33)
bestzones = dict( (k,v) for v,k in zonelist[-cut:] )

# make segment paths:
segdrop = [(0,1)] * (block-1)
segpass = [(1,0)] * block
segloop = [(0,-1)] * (block-1) + [(1,0)] + [(0,1)] * (block-1)
segeat = ( segloop+[(1,0)] ) * (block/2)
segshort = [(1,0)] * 2 + ( segloop+[(1,0)] ) * (block/2 - 1)

def segtopath(path, seg, xdir):
    for dx,dy in seg:
        x,y = path[-1]
        newloc = (x+dx*xdir, y+dy)
        path.append(newloc)

# design good path:
xdir = 1
path = [(0,0)]
segtopath(path, segdrop, xdir)
shortzone = True
while True:
    x,y = path[-1]
    zone = (x/block, y/block)
    if zone in bestzones:
        if shortzone:
            seg = segshort
        else:
            seg = segeat
    else:
        seg = segpass
    segtopath(path, seg, xdir)
    shortzone = False
    # check end of x block run:
    x,y = path[-1]
    zone = (x/block, y/block)
    if not ( 0 <= x < xblocks*block ):
        del path[-1]
        segtopath(path, segdrop, xdir)
        shortzone = True
        xdir = xdir * -1
    if len(path) > enough:
        break
print('Path Found')

# show path on picture:
loc = path.pop(0)
eaten = 1
joetotal = grid[loc]
i = 0
while eaten <= enough:
    loc = path[i]
    i += 1
    pic.set_at(loc, (0,0,0))
    joetotal += grid[loc]
    eaten += 1
    if i % 1000 == 0:
        screen.blit(pic, (0,0))
        pygame.display.flip()
        for event in pygame.event.get():
            if event.type == QUIT: sys.exit(0)

# save picture and wait:
screen.blit(pic, (0,0))
pygame.display.flip()
pygame.image.save(pic, 'output/'+fn)
joeavg = 1.0 * joetotal/eaten
print '%s: %7.5f/%7.5f = %7.5f' % (fn, joeavg, picavg, joeavg/picavg)
while True:
    for event in pygame.event.get():
        if event.type == QUIT: sys.exit(0)

from pygame.locals import *
import pygame, sys, random

fn = sys.argv[1]

screen = pygame.display.set_mode((1900,1000))
pic = pygame.image.load(fn)
pic.convert()
W,H = pic.get_size()
enough = W*H/3
screen.blit(pic, (0,0))

ORTH = [(-1,0), (1,0), (0,-1), (0,1)]
def orth(p):
    return [(p[0]+dx, p[1]+dy) for dx,dy in ORTH]

def look(p):
    x,y = p
    if 0 <= x < W and 0 <= y < H:
        return sum(pic.get_at(p))
    else:
        return -1

# index picture
locs = [(x,y) for x in range(W) for y in range(H)]
grid = dict( (p,sum(pic.get_at(p))) for p in locs )
rank = sorted( grid.values() )
median = rank[ len(rank)/2 ]
dark = dict( (k,v) for k,v in grid if v < median )
good = dict( (k,v) for k,v in grid if v > median )
pictotal = sum(rank)
picavg = 1.0 * pictotal/(W*H)
print('Indexed')

# compute zone values:
block = 16
xblocks, yblocks = (W-1)/block, (H-1)/block
zones = dict( ((zx,zy),0) for zx in range(xblocks) for zy in range(yblocks) )
for x,y in locs:
    div = (x/block, y/block)
    if div in zones:
        colsum = sum( pic.get_at((x,y)) )
        zones[div] += colsum

# choose best zones:
zonelist = sorted( (v,k) for k,v in zones.items() )
cut = int(xblocks * yblocks * 0.33)
bestzones = dict( (k,v) for v,k in zonelist[-cut:] )

# make segment paths:
segdrop = [(0,1)] * (block-1)
segpass = [(1,0)] * block
segloop = [(0,-1)] * (block-1) + [(1,0)] + [(0,1)] * (block-1)
segeat = ( segloop+[(1,0)] ) * (block/2)
segshort = [(1,0)] * 2 + ( segloop+[(1,0)] ) * (block/2 - 1)

def segtopath(path, seg, xdir):
    for dx,dy in seg:
        x,y = path[-1]
        newloc = (x+dx*xdir, y+dy)
        path.append(newloc)

# design good path:
xdir = 1
path = [(0,0)]
segtopath(path, segdrop, xdir)
shortzone = True
while True:
    x,y = path[-1]
    zone = (x/block, y/block)
    if zone in bestzones:
        if shortzone:
            seg = segshort
        else:
            seg = segeat
    else:
        seg = segpass
    segtopath(path, seg, xdir)
    shortzone = False
    # check end of x block run:
    x,y = path[-1]
    zone = (x/block, y/block)
    if not ( 0 <= x < xblocks*block ):
        del path[-1]
        segtopath(path, segdrop, xdir)
        shortzone = True
        xdir = xdir * -1
    if len(path) > enough:
        break
print('Path Found')

# show path on picture:
loc = path.pop(0)
eaten = 1
joetotal = grid[loc]
i = 0
while eaten <= enough:
    loc = path[i]
    i += 1
    pic.set_at(loc, (0,0,0))
    joetotal += grid[loc]
    eaten += 1
    if i % 1000 == 0:
        screen.blit(pic, (0,0))
        pygame.display.flip()
        for event in pygame.event.get():
            if event.type == QUIT: sys.exit(0)

# save picture and wait:
screen.blit(pic, (0,0))
pygame.display.flip()
pygame.image.save(pic, 'output/'+fn)
joeavg = 1.0 * joetotal/eaten
print '%s: %7.5f/%7.5f = %7.5f' % (fn, joeavg, picavg, joeavg/picavg)
while True:
    for event in pygame.event.get():
        if event.type == QUIT: sys.exit(0)