Trou n ° 1

Joe le serpent a faim.

Il mange des images, un pixel à la fois.

Il aime vraiment les pixels lumineux.

Le défi

Programmez Joe à manger les pixels les plus brillants qu'il puisse trouver, étant donné qu'il ne peut que se déplacer vers le haut, le bas, la gauche ou la droite.

Caractéristiques

• Joe doit commencer au pixel supérieur gauche de l'image.
• Joe ne peut se déplacer horizontalement ou verticalement que de 1 à chaque mouvement
• Joe n'a que le temps de déplacer 1/3 du nombre de pixels dans l'image (1/3 autant de mouvements que de pixels). Si le nombre de pixels n'est pas un multiple de 3, arrondissez à l'entier le plus proche.
• Joe peut croiser son chemin, bien que cela compte pour 0 luminosité
• La luminosité est basée sur la somme de r, g et b, donc rgb (0,0,0) a une luminosité de 0 tandis que rgb (255,255,255) a une luminosité maximale.

Contribution

Vous pouvez saisir l'image comme vous le souhaitez.

Sortie

• une image montrant le résultat final de votre photo (avec du noir mangé en pixels).
• La quantité de luminosité consommée (veuillez préciser quelle plage dans votre réponse)

Notation

Votre programme sera noté sur:

• La luminosité moyenne des pixels que Joe mange / La luminosité moyenne des pixels de l'image *

* vous pouvez coder en dur cela dans votre programme

Votre score total sera la moyenne des scores des images suivantes:

Images de test:

http://upload.wikimedia.org/wikipedia/en/thumb/f/f4/The_Scream.jpg/800px-The_Scream.jpg

C ++, Score: 1.42042 1.46766

Il s'agit essentiellement d'une version légèrement plus sophistiquée des deux solutions existantes: des quatre mouvements possibles, il sélectionne celui qui maximise la luminosité. Cependant, au lieu de ne regarder que la luminosité du pixel cible, il examine la somme pondérée de la luminosité des pixels au voisinage du pixel cible, où les pixels plus proches de la cible ont un poids plus important.

EDIT: L' utilisation de la luminosité non linéaire dans le calcul du voisinage améliore légèrement le score.

Compilez avec g++ joe.cpp -ojoe -std=c++11 -O3 -lcairo. Nécessite le Caire.

Courez avec joe <image-file> [<radius>]. <image-file>est l'image PNG d'entrée. <radius>(argument facultatif) est le rayon du voisinage additionné, en pixels (plus petit est plus rapide, plus grand est (à peu près) meilleur.) Produit la partition et une image nommée 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);
}

Résultats

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

Plus de bonbons pour les yeux

Python 3, score = 1,57

D'abord, notre serpent parcourt l'image en créant des lignes verticales à égale distance les unes des autres.

Nous pouvons étendre ce serpent en prenant deux points l'un à côté de l'autre sur une ligne verticale et en créant une boucle dont les points d'extrémité sont eux.

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

Nous organisons les points en paires et pour chaque paire, nous stockons la taille et la valeur de luminosité moyenne de la boucle qui donne la luminosité moyenne la plus élevée.

À chaque étape, nous choisissons la paire avec la valeur la plus élevée, étendez sa boucle pour obtenir une luminosité moyenne maximale sur l'extension et calculons la nouvelle taille de boucle et la valeur de luminosité optimales pour la paire.

Nous stockons les triplets (value, size, point_pair) dans une structure de tas triée par valeur afin que nous puissions supprimer le plus grand élément (dans O (1)) et ajouter le nouveau modifié (dans O (log n)) efficacement.

Nous nous arrêtons lorsque nous atteignons la limite de nombre de pixels et ce serpent sera le serpent final.

La distance entre les lignes verticales a très peu d'effet sur les résultats, donc un pixel constant de 40 pixels a été choisi.

Résultats

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

Remarque: l'image originale "The Scream" n'était pas disponible, j'ai donc utilisé une autre image "The Scream" avec une résolution similaire.

Gif montrant le processus d'extension du serpent sur l'image "tourbillon":

Le code prend un (ou plusieurs noms séparés par des espaces) de stdin et écrit les images de serpent résultantes dans des fichiers png et imprime les scores sur 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=[]
        px=im.load()

        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)

Juste un algorithme gourmand très simple et naïf pour faire rouler la balle.

#!/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')

Sortie:

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)

Java (score: 0,6949)

Un algorithme simple qui mange le pixel le plus brillant des quatre pixels entourant le pixel actuel. Dans le cas d'une égalité, le pixel mangé est aléatoire, ce qui entraîne des scores différents et des images résultantes à chaque exécution. En tant que tel, les scores ci-dessous sont les moyennes de plus de 50 exécutions sur chaque image.

Pour l'exécuter, modifiez les trois arguments (existants en tant que constantes de classe) dans la source, ou passez-les via la ligne de commande sous la forme java HungryImageSnake <source> <iterations> <printScores>où se <source>trouve le fichier source de l'image à manger, <iterations>est le nombre de fois où manger l'image (en prenant le score moyen et la sauvegarde du meilleur score sur toutes les itérations), et il <printScores>est vrai d'imprimer le score de chaque itération ou faux de ne pas.

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;
    }
}

Scores moyens, par image, sur cinquante itérations:

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

Meilleurs scores, par image, sur les mêmes cinquante itérations:

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

Images des parcours avec le score le plus élevé:

Comme le montrent les images, bien moins d'un tiers des pixels sont réellement mangés, car le serpent est parfois coincé parmi les pixels qu'il a déjà mangés, auxquels il reste coincé dans la zone morte jusqu'à ce que le caractère aléatoire de ses mouvements le ramène à une partie comestible de l'image.

Également à la suite de la restauration des pixels par le serpent, les scores sont biaisés vers le bas, car la luminosité zéro des pixels morts est à nouveau prise en compte dans la moyenne. Je m'attendrais à voir des scores beaucoup plus élevés si l'algorithme de notation était modifié pour ne diviser que par le nombre de mouvements qui ont conduit à manger de nouveaux pixels, plutôt que tous les mouvements (y compris ceux où le serpent mange un pixel maintenant mort qu'il a déjà mangé auparavant) ).

Bien sûr, une meilleure approche serait de créer une sorte d'heuristique de luminosité pour chaque pixel et de trouver le chemin des width * height / 3pixels avec la luminosité moyenne la plus élevée, mais je doute que cette approche soit optimale en temps d'exécution, en particulier sur des images plus grandes, comme le nombre des permutations possibles seraient très importantes. Je pourrais peut-être essayer une certaine forme de cette approche plus tard et la publier dans une réponse distincte si c'est le cas.

Python 2, score: 1,205

J'ai mis au point une solution Python rapide il y a quelque temps, mais j'ai oublié de la publier. C'est ici. Il trouve les blocs les plus riches de l'image, puis se déplace vers chaque bloc, mangeant tous les meilleurs blocs auxquels il vient.

Résultats

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

Exemple d'image

Code Python 2.7

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)