Lubang # 1

Joe si ular lapar.

Dia makan gambar, satu pixel pada satu waktu.

Dia sangat menyukai piksel yang cerah.

Tantangan

Program Joe untuk memakan piksel paling terang yang bisa dia temukan, mengingat dia hanya bisa bergerak ke atas, bawah, kiri atau kanan.

Spesifikasi

• Joe harus mulai dari piksel kiri atas gambar.
• Joe hanya bisa bergerak secara horizontal atau vertikal dengan 1 setiap gerakan
• Joe hanya memiliki cukup waktu untuk memindahkan 1/3 dari jumlah piksel dalam gambar (1/3 bergerak sebanyak piksel). Jika jumlah piksel bukan kelipatan 3, bulatkan ke bilangan bulat terdekat.
• Joe dapat melintasi jalannya, meskipun itu dianggap sebagai 0 kecerahan
• Kecerahan didasarkan pada jumlah r, g dan b, sehingga rgb (0,0,0) memiliki kecerahan 0 sedangkan rgb (255.255.255) memiliki kecerahan maksimum.

Memasukkan

Anda dapat memasukkan gambar sesuka Anda.

Keluaran

• gambar yang menunjukkan hasil akhir gambar Anda (dengan piksel hitam yang dimakan).
• Jumlah kecerahan yang dimakan (sebutkan kisaran apa dalam jawaban Anda)

Mencetak gol

Program Anda akan dinilai pada:

• Rata-rata kecerahan piksel yang dimakan Joe / Kecerahan rata-rata piksel dalam gambar *

* Anda dapat meng-hardcode ini di program Anda

Skor total Anda akan menjadi rata-rata skor untuk gambar berikut:

Gambar uji:

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

C ++, Skor: 1.42042 1.46766

Ini pada dasarnya adalah versi yang sedikit lebih canggih dari dua solusi yang ada: Dari empat kemungkinan gerakan, ia memilih yang memaksimalkan kecerahan. Namun, alih-alih hanya melihat kecerahan piksel target, ini terlihat pada jumlah kecerahan piksel tertimbang di lingkungan piksel target, di mana piksel yang lebih dekat ke target memiliki bobot lebih besar.

EDIT: Menggunakan kecerahan nonlinear dalam perhitungan lingkungan meningkatkan skor sedikit.

Kompilasi dengan g++ joe.cpp -ojoe -std=c++11 -O3 -lcairo. Membutuhkan cairo.

Jalankan dengan joe <image-file> [<radius>]. <image-file>adalah input gambar PNG. <radius>(argumen opsional) adalah jari-jari dari lingkungan yang dijumlahkan, dalam piksel (lebih kecil lebih cepat, lebih besar (kira-kira) lebih baik.) Output skor dan gambar bernama 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);
}

Hasil

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

Lebih banyak eye-candy

Python 3, skor = 1,57

Pertama-tama ular kami melakukan perjalanan gambar menciptakan garis-garis vertikal dengan jarak yang sama satu sama lain.

Kita dapat memperluas ular ini dengan mengambil dua titik di samping satu sama lain dalam garis vertikal dan membuat satu lingkaran yang titik akhirnya adalah mereka.

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

Kami mengatur poin menjadi pasangan dan untuk setiap pasangan kami menyimpan ukuran dan nilai kecerahan rata-rata dari loop yang memberi memiliki kecerahan rata-rata terbesar.

Pada setiap langkah kami memilih pasangan dengan nilai tertinggi memperpanjang loop-nya untuk mencapai kecerahan rata-rata maksimum pada ekstensi dan menghitung ukuran loop optimal dan nilai kecerahan untuk pasangan.

Kami menyimpan kembar tiga (nilai, ukuran, point_pair) dalam struktur tumpukan yang diurutkan berdasarkan nilai sehingga kami dapat menghapus elemen terbesar (di O (1)) dan menambahkan yang baru dimodifikasi (di O (log n)) secara efisien.

Kita berhenti ketika kita mencapai batas jumlah piksel dan ular itu akan menjadi ular terakhir.

Jarak antara garis vertikal memiliki efek yang sangat kecil dalam hasil sehingga dipilih 40 piksel konstan.

Hasil

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

Catatan: gambar asli "The Scream" tidak tersedia sehingga saya menggunakan gambar "The Scream" lainnya dengan resolusi yang sama.

Gif menunjukkan proses perpanjangan ular pada gambar "swirl":

Kode mengambil satu (atau lebih spasi terpisah) nama file dari stdin dan menulis gambar ular yang dihasilkan ke file png dan mencetak skor ke 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 (skor: 0,0797116)

Hanya algoritma serakah yang sangat sederhana dan naif untuk mendapatkan bola bergulir.

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

Keluaran:

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)

Jawa (skor: 0,6949)

Algoritma sederhana yang memakan piksel paling terang dari empat piksel yang mengelilingi piksel saat ini. Dalam kasus seri, piksel yang dimakan adalah acak, mengarah ke skor yang berbeda dan menghasilkan gambar setiap eksekusi. Dengan demikian, skor di bawah ini adalah rata-rata lebih dari 50 eksekusi pada setiap gambar.

Untuk menjalankannya, edit tiga argumen (ada sebagai konstanta kelas) di sumber, atau berikan melalui baris perintah dalam bentuk di java HungryImageSnake <source> <iterations> <printScores>mana <source>file sumber gambar untuk dimakan, <iterations>adalah berapa kali memakan gambar (mengambil skor rata-rata dan menyimpan skor terbaik di atas semua iterasi), dan <printScores>benar untuk mencetak skor setiap iterasi atau salah untuk tidak.

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

Skor rata-rata, berdasarkan gambar, lebih dari lima puluh iterasi:

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

Skor terbaik, berdasarkan gambar, lebih dari lima puluh iterasi yang sama:

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

Gambar dengan skor tertinggi:

Seperti terlihat dari gambar, jauh lebih sedikit dari sepertiga piksel benar-benar dimakan, karena ular kadang-kadang terjebak di antara piksel yang sudah dimakannya, di mana ia tetap terjebak di dalam area mati sampai keacakan gerakannya membawanya ke bagian yang dapat dimakan dari gambar.

Juga sebagai hasil dari piksel pemakan ular, nilainya bias ke bawah, karena nol-kecerahan piksel mati sekali lagi diperhitungkan dalam rata-rata. Saya akan berharap untuk melihat skor yang jauh lebih tinggi jika algoritma skor dimodifikasi untuk hanya dibagi dengan jumlah gerakan yang menyebabkan memakan piksel baru, daripada semua gerakan (termasuk yang ular memakan piksel yang sudah mati yang dimakan sebelumnya sebelum dimakan). ).

Tentu saja, pendekatan yang lebih baik adalah membuat semacam heuristik kecerahan untuk setiap piksel dan menemukan jalur width * height / 3piksel dengan kecerahan rata-rata tertinggi, tetapi saya ragu pendekatan ini akan optimal dalam jangka waktu, terutama pada gambar yang lebih besar, karena jumlahnya permutasi yang mungkin akan sangat besar. Saya dapat mengambil beberapa bentuk pendekatan ini nanti dan mempostingnya dalam jawaban yang terpisah jika demikian.

Python 2, Nilai: 1,205

Saya mengumpulkan solusi Python cepat beberapa waktu lalu tetapi lupa mempostingnya. Ini dia. Ia menemukan blok terkaya dalam gambar, kemudian melakukan perjalanan ke setiap blok, memakan semua blok terbaik yang ada.

Hasil

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

Contoh Gambar

Python 2.7 Code

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)