# Hungry Image Snake - Hole #3

Hole #1

Joe the snake is hungry.

He eats pictures, one pixel at a time.

He really likes bright pixels.

## The Challenge

Program Joe to eat the most bright pixels he can find, given that he can only move up, down, left or right.

## Specifications

• Joe must start at the upper left pixel of the image.
• Joe can only move horizontally or vertically by 1 each move
• Joe has only enough time to move 1/3 of the amount of pixels in the picture (1/3 as many moves as pixels). If the number of pixels is not a multiple of 3, round down to the nearest integer.
• Joe may cross his path, though that counts as 0 brightness
• Brightness is based on the sum of r,g and b, so rgb(0,0,0) has a brightness of 0 while rgb(255,255,255) has maximum brightness.

## Input

You may input the image however you like.

## Output

• an image showing the end result of your picture (with black being eaten pixels).

## Scoring

• The average brightness of pixels Joe eats / The average brightness of the pixels in the picture*

*you may hardcode this in your program

Your total score will be the average of the scores for the following images:

Test images:

• Fun Markdown fact - You can turn images into links to their originals: [![image description](SE URL for downsized image)](URL for original image). – Calvin's Hobbies Oct 21 '14 at 2:57
• It might be an idea to ask people to include an example "eaten" image in their answers. – Nathaniel Oct 21 '14 at 5:51
• 1 image is broken: upload.wikimedia.org/wikipedia/en/thumb/f/f4/The_Scream.jpg/… – Ferrybig Feb 12 '16 at 18:35

# C++, Score: 1.42042 1.46766

This is essentially a slightly more sophisticated version of the two existing solutions: Of the four possible moves, it selects the one that maximizes brightness. However, instead of only looking at the brightness of the target pixel, it looks at the weighted sum of pixel-brightness in the neighborhood of the target pixel, where pixels closer to the target have a greater weight.

EDIT: Using nonlinear brightness in neighborhood calculation improves the score slightly.

Compile with g++ joe.cpp -ojoe -std=c++11 -O3 -lcairo. Requires cairo.

Run with joe <image-file> [<radius>]. <image-file> is the input PNG image. <radius> (optional argument) is the radius of the summed-over neighborhood, in pixels (smaller is faster, larger is (roughly) better.) Outputs the score and an image named out.<image-file>.

#include <cairo/cairo.h>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

using namespace std;

int main(int argc, const char* argv[]) {
auto* img = cairo_image_surface_create_from_png(argv[1]);
int width = cairo_image_surface_get_width(img),
height = cairo_image_surface_get_height(img),
stride = cairo_image_surface_get_stride(img);
unsigned char* data = cairo_image_surface_get_data(img);

double* brightness = new double[width * height];
double total_brightness = 0;
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
const unsigned char* p = data + stride * y + 4 * x;
total_brightness += brightness[y * width + x] = p[0] + p[1] + p[2];
}
}

const int r = argc > 2 ? stoi(argv[2]) : 64, R = 2 * r + 1;
double* weight = new double[R * R];
for (int y = -r; y <= r; ++y) {
for (int x = -r; x <= r; ++x)
weight[R * (y + r) + (x + r)] = 1.0 / (x*x + y*y + 1);
}

auto neighborhood = [&] (int x, int y) {
double b = 0;
int x1 = max(x - r, 0), x2 = min(x + r, width - 1);
int y1 = max(y - r, 0), y2 = min(y + r, height - 1);
for (int v = y1; v <= y2; ++v) {
const double *B = brightness + width * v + x1;
const double *W = weight + R * (v - (y - r)) + (x1 - (x - r));
for (int u = x1; u <= x2; ++u, ++B, ++W)
b += (*W) * (*B) * (*B);
}
return b;
};

int n = (2 * width * height + 3) / 6;
int x = 0, y = 0;
double path_brightness = 0;
int O[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < n; ++i) {
if (i % 1000 == 0) cerr << (200 * i + n) / (2 * n) << "%\r";

path_brightness += brightness[width * y + x]; brightness[width * y + x] = 0;
unsigned char* p = data + stride * y + 4 * x;
p[0] = p[1] = 16 * i % 255; p[2] = 0;

auto O_end = partition(begin(O), end(O), [&] (const int* o) {
return x + o[0] >= 0 && x + o[0] < width &&
y + o[1] >= 0 && y + o[1] < height;
});
const int* o_max; double o_max_neighborhood = -1;
for (auto o = O; o != O_end; ++o) {
double o_neighborhood = neighborhood(x + (*o)[0], y + (*o)[1]);
if (o_neighborhood > o_max_neighborhood)
o_max = *o, o_max_neighborhood = o_neighborhood;
}
x += o_max[0]; y += o_max[1];
}

cout << (path_brightness * width * height) / (n * total_brightness) << endl;

cairo_surface_write_to_png(img, (string("out.") + argv[1]).c_str());

delete []brightness;
delete []weight;
cairo_surface_destroy(img);
}


## Results

Bridge    1.39945
Balls     1.77714
Scream    1.38349
Fractal   1.31727
Vortex    1.66493
-----------------
Average   1.46766


## More eye-candy

• I just tried your program on some of my own sample images, and one has very much black only around the start point, and there your program crashes due to the neighbourhood lambda returning NaN. – PlasmaHH Oct 24 '14 at 14:29
• @PlasmaHH Mind sharing the offending image? – Ell Oct 24 '14 at 14:46
• I was feeding it vacation images... 400x400 pure black does the "trick" too though. – PlasmaHH Oct 24 '14 at 15:37
• @PlasmaHH Well, a purely black image has an undefined score, it's zero over zero, which would be a NaN. It shouldn't affect the neighborhood calculation, though, or crash the program (though this may depend on the floating-point environment.) – Ell Oct 24 '14 at 15:57
• Have a look at the o_max pointer if (o_neighborhood > o_max_neighborhood) o_max = *o, o_max_neighborhood = o_neighborhood; only this code sets it. however due to nan involved, the comparison is always false, thus o_max is never set and used uninitialized. – PlasmaHH Oct 24 '14 at 20:26

# Python 3, score = 1.57

First our snake travels the image creating vertical lines with equal distance from each other.

We can extend this snake by taking two points next to each other in a vertical line and creating a loop whose endpoints are them.

|      |
|  =>  +----+
|      +----+
|      |


We organize the points into pairs and for every pair we store the size and average brightness value of the loop which gives has the greatest average brightness.

At every step we choose the pair with highest value extend its loop to achieve maximum average brightness on the extension and calculate the new optimal loop size and brightness value for the pair.

We store the (value,size,point_pair) triplets in a heap structure sorted by value so we can remove the biggest element (in O(1)) and add the new modified one (in O(log n)) efficiently.

We stop when we reachg the pixel count limit and that snake will be the final snake.

The distance between the vertical lines has very little effect in the results so a constant 40 pixel was choosen.

## Results

swirl    1.33084397946
chaos    1.76585674741
fractal  1.49085737611
bridge   1.42603926741
balls    1.92235115238
scream   1.48603818637
----------------------
average  1.57033111819


Note: the original "The Scream" picture was not available so I used an other "The Scream" picture with similar resolution.

Gif showing the snake extending process on the "swirl" image:

The code takes one (or more space separated) filename(s) from stdin and writes the resulting snake images to png files and prints the scores to stdout.

from PIL import Image
import numpy as np
import heapq as hq

def upd_sp(p,st):
vs,c=0,0
mv,mp=-1,0
for i in range(st,gap):
if p[1]+i<h:
vs+=v[p[0],p[1]+i]+v[p[0]+1,p[1]+i]
c+=2
if vs/c>mv:
mv=vs/c
mp=i
return (-mv,mp)

mrl=[]
bf=input().split()

for bfe in bf:
mr,mg=0,0
for gap in range(40,90,1500):

im=Image.open(bfe)
im_d=np.asarray(im).astype(int)

v=im_d[:,:,0]+im_d[:,:,1]+im_d[:,:,2]

w,h=v.shape

fp=[]
sp=[]
x,y=0,0
d=1

go=True
while go:
if 0<=x+2*d<w:
fp+=[(x,y)]
fp+=[(x+d,y)]
sp+=[(x-(d<0),y)]
x+=2*d
continue
if y+gap<h:
for k in range(gap):
fp+=[(x,y+k)]
y+=gap
d=-d
continue
go=False

sh=[]

pl=[]

for p in fp:
pl+=[v[p[0],p[1]]]
px[p[1],p[0]]=(0,127,0)

for p in sp:
mv,mp=upd_sp(p,1)
if mv<=0:
hq.heappush(sh,(mv,1,mp+1,p))

empty=False
pleft=h*w//3
pleft-=len(fp)
while pleft>gap*2 and not empty:

if len(sh)>0:
es,eb,ee,p=hq.heappop(sh)
else:
empty=True
pleft-=(ee-eb)*2

mv,mp=upd_sp(p,ee)
if mv<=0:
hq.heappush(sh,(mv,ee,mp+1,p))

for o in range(eb,ee):
pl+=[v[p[0],p[1]+o]]
pl+=[v[p[0]+1,p[1]+o]]
px[p[1]+o,p[0]]=(0,127,0)
px[p[1]+o,p[0]+1]=(0,127,0)

pl+=[0]*pleft

sb=sum(pl)/len(pl)
ob=np.sum(v)/(h*w)

im.save(bfe[:-4]+'snaked.png')

if sb/ob>mr:
mr=sb/ob
mg=gap

print(bfe,mr)
mrl+=[mr]

print(sum(mrl)/len(mrl))


# Python 2 (score: 0.0797116)

Just a very simple and naïve greedy algorithm to get the ball rolling.

#!/usr/bin/python

from PIL import Image

OFFSETS = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def test_img(filename):
img = Image.open(filename)

joe, eaten = (0, 0), []
img_w, img_h = img.size
all_pixels = [
sum(img.getpixel((x, y)))
for x in xrange(img_w)
for y in xrange(img_h)
]
total_brightness = float(sum(all_pixels)) / len(all_pixels)

for _ in xrange(0, (img_w*img_h)/3):
max_offset, max_brightness = (0, 0), 0
for o in OFFSETS:
try:
brightness = sum(img.getpixel((joe[0] + o[0], joe[1] + o[1])))
except IndexError:
brightness = -1
if brightness >= max_brightness:
max_offset = o
max_brightness = brightness

joe = (joe[0] + max_offset[0], joe[1] + max_offset[1])
eaten.append(max_brightness)
img.putpixel(joe, (0, 0, 0))

eaten_brightness = float(sum(eaten)) / len(eaten)
print('%d of %d (score %f)' % (eaten_brightness, total_brightness, eaten_brightness / total_brightness))
img.show()

test_img('img0.jpg')
test_img('img1.png')
test_img('img2.jpg')
test_img('img3.jpg')
test_img('img4.jpg')


Output:

llama@llama:~/Code/python/ppcg40069hungrysnake$./hungrysnake.py 15 of 260 (score 0.060699) 9 of 132 (score 0.074200) 16 of 300 (score 0.055557) 4 of 369 (score 0.010836) 79 of 400 (score 0.197266)  • I think your scoring is off. It is the average of Joe's brightness eaten over the average brightness for the whole picture... A random Joe should get a score of roughly 1. – Stretch Maniac Oct 21 '14 at 1:57 • @StretchManiac Hmm, I don't see anything wrong. sum of brightnesses of eaten pixels / amount of eaten pixels is the right formula, correct? Maybe it's just a really terrible algorithm ;) – Doorknob Oct 21 '14 at 2:01 • @Doorknob it is The average brightness of pixels Joe eats / The average brightness of the pixels in the picture* – hmatt1 Oct 21 '14 at 2:04 • For the orange and black swirly (not blue) one, I got an average brightness of 68.0846... Which doesn't seem to match any of yours. Perhaps sum(getPixel(...)) doesn't return what you want? (I'm kinda a python newbie). BTW, there are 6 pictures, but you only have 5 outputs. Could you also label the pictures somehow? – Stretch Maniac Oct 21 '14 at 2:32 • @StretchManiac How are you calculating your brightness? Mine just sums the R, G, and B values. Sorry, I missed the swirly one that comes second-to-last (the one you mentioned in your comment, I think). I'll add that in the morning (I have to sleep now). – Doorknob Oct 21 '14 at 2:42 ## Java (score: 0.6949) A simple algorithm which eats the brightest pixel out of the four pixels surrounding the current pixel. In the case of a tie, the pixel eaten is random, leading to differing scores and resulting images each execution. As such, the scores below are the averages over 50 executions on each image. To run it, either edit the three arguments (existing as class constants) in the source, or pass them via command line in the form java HungryImageSnake <source> <iterations> <printScores> where <source> is the source file of the image to eat, <iterations> is the number of times to eat the image (taking the average score and saving the best score over all iterations), and <printScores> is true to print each iteration's score or false to not. import javax.imageio.ImageIO; import java.awt.Graphics; import java.awt.image.BufferedImage; import java.io.File; import java.io.IOException; import java.util.Random; public class HungryImageSnake { private static final String SOURCE = "tornado.jpg"; private static final int ITERATIONS = 50; private static final boolean PRINT_SCORES = true; public static void main(String[] args) { try { String source = args.length > 0 ? args[0] : SOURCE; int iterations = args.length > 1 ? Integer.parseInt(args[1]) : ITERATIONS; boolean printScores = args.length > 2 ? Boolean.parseBoolean(args[2]) : PRINT_SCORES; System.out.printf("Reading '%s'...%n", source); System.out.printf("Performing %d meals...%n", iterations); BufferedImage image = ImageIO.read(new File(source)); double totalScore = 0; double bestScore = 0; BufferedImage bestImage = null; for (int i = 0; i < iterations; i++) { HungryImageSnake snake = new HungryImageSnake(image); while (snake.isHungry()) { snake.eat(); } double score = snake.getScore(); if (printScores) { System.out.printf(" %d: score of %.4f%n", i + 1, score); } totalScore += score; if (bestImage == null || score > bestScore) { bestScore = score; bestImage = snake.getImage(); } } System.out.printf("Average score: %.4f%n", totalScore / iterations); String formattedScore = String.format("%.4f", bestScore); String output = source.replaceFirst("^(.*?)(\\.[^.]+)?$", "$1-b" + formattedScore + "$2");
ImageIO.write(bestImage, source.substring(source.lastIndexOf('.') + 1), new File(output));
System.out.printf("Wrote best image (score: %s) to '%s'.%n", bestScore, output);
} catch (IOException e) {
e.printStackTrace();
}
}

private int x;
private int y;
private int movesLeft;
private int maximumMoves;
private double eatenAverageBrightness;
private double originalAverageBrightness;
private BufferedImage image;

public HungryImageSnake(BufferedImage image) {
this.image = copyImage(image);
int size = image.getWidth() * image.getHeight();
this.maximumMoves = size / 3;
this.movesLeft = this.maximumMoves;
int totalBrightness = 0;
for (int x = 0; x < image.getWidth(); x++) {
for (int y = 0; y < image.getHeight(); y++) {
totalBrightness += getBrightnessAt(x, y);
}
}
this.originalAverageBrightness = totalBrightness / (double) size;
}

public BufferedImage getImage() {
return image;
}

public double getEatenAverageBrightness() {
return eatenAverageBrightness;
}

public double getOriginalAverageBrightness() {
return originalAverageBrightness;
}

public double getScore() {
return eatenAverageBrightness / originalAverageBrightness;
}

public boolean isHungry() {
return movesLeft > 0;
}

public void eat() {
if (!isHungry()) {
return;
}
int[][] options = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
shuffleArray(options); // prevent snake from getting stuck in corners
int[] bestOption = null;
int bestBrightness = 0;
for (int[] option : options) {
int optionX = this.x + option[0];
int optionY = this.y + option[1];
if (exists(optionX, optionY)) {
int brightness = getBrightnessAt(optionX, optionY);
if (bestOption == null || brightness > bestBrightness) {
bestOption = new int[]{ optionX, optionY };
bestBrightness = brightness;
}
}
}

image.setRGB(bestOption[0], bestOption[1], 0);
this.movesLeft--;
this.x = bestOption[0];
this.y = bestOption[1];
this.eatenAverageBrightness += bestBrightness / (double) maximumMoves;
}

private boolean exists(int x, int y) {
return x >= 0 && x < image.getWidth() && y >= 0 && y < image.getHeight();
}

private int getBrightnessAt(int x, int y) {
int rgb = image.getRGB(x, y);
int r = (rgb >> 16) & 0xFF;
int g = (rgb >> 8) & 0xFF;
int b = rgb & 0xFF;
return r + g + b;
}

private static <T> void shuffleArray(T[] array) {
Random random = new Random();
for (int i = array.length - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
T temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}

private static BufferedImage copyImage(BufferedImage source){
BufferedImage b = new BufferedImage(source.getWidth(), source.getHeight(), source.getType());
Graphics g = b.getGraphics();
g.drawImage(source, 0, 0, null);
g.dispose();
return b;
}
}


Average scores, by image, over fifty iterations:

Bridge - 0.7739
Spheres - 0.5580
Scream - 0.8197
Fractal - 0.3850
Vortex - 0.9158


Best scores, by image, over the same fifty iterations:

Bridge - 0.8996
Spheres - 0.8741
Scream - 0.9183
Fractal - 0.5720
Vortex - 1.1520


The highest scoring runs' images:

As is evident from the images, far less than a third of the pixels are actually eaten, as the snake occasionally gets stuck among pixels it has already eaten, at which it remains stuck within the dead area until the randomness of its movements bring it to an edible portion of the image.

Also as a result of the snake re-eating pixels, the scores are biased downward, as the zero-brightness of the dead pixels is again factored into the average. I would expect to see far higher scores if the scoring algorithm was modified to only divide by the number of moves that led to eating new pixels, rather than all moves (including those where the snake eats a now-dead pixel that it has eaten before).

Of course, a better approach would be to create some sort of brightness heuristic for each pixel and find the path of width * height / 3 pixels with the highest average brightness, but I doubt this approach will be optimal in run time, especially on larger images, as the number of possible permutations would be very large. I may take a shot at some form of this approach later and post it in a separate answer if so.

• If anyone is bothered by how large my answer is (due to the images in it), let me know and I'll remove the images in favor of links or another less-spacy alternative. Or, if anyone would like the full resolution originals of any "eaten" images, let me know in a comment as well. – FThompson Oct 21 '14 at 10:10

# Python 2, Score: 1.205

I put together a quick Python solution some time ago but forgot to post it. Here it is. It finds the richest blocks in the image, then travels to each block, eating all the best blocks it comes to.

### Results

bridge.jpg: 591.97866/515.41501 =                               1.14855
BallsRender.png: 493.24711/387.80635 =                          1.27189
Mandel_zoom_04_seehorse_tail.jpg: 792.23990/624.60579 =         1.26838
Red_Vortex_Apophysis_Fractal_Flame.jpg: 368.26121/323.08463 =   1.13983
The_Scream.jpg: 687.18565/555.05221 =                           1.23806
swirl.jpg: 762.89469/655.73767 =                                1.16341

AVERAGE                                                         1.205


### Python 2.7 Code

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

fn = sys.argv[1]

screen = pygame.display.set_mode((1900,1000))
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)