Pergi dan buat itu berbintang

Dalam kontes ini Anda harus menulis sebuah program, yang menerima gambar piksel hitam dan putih, dan mencoba mengubahnya, sehingga bentuk putih membentuk domain bintang , dengan sesedikit mungkin perubahan.

Perubahan yang diizinkan adalah mengubah piksel putih menjadi piksel hitam dan mengubah piksel hitam menjadi piksel putih.

Output harus lagi terdiri dari gambar yang sama tetapi kali ini dengan semua perubahan dan dengan tanda tengah. Pixel yang diubah dari putih ke hitam harus ditampilkan dalam warna biru, yang diubah dari hitam menjadi putih harus ditampilkan dalam warna kuning, dan setidaknya satu piksel tengah harus ditampilkan dalam warna merah. (Warna yang tepat terserah Anda.) Program harus melampaui gambar yang ditentukan serta jumlah total perubahan yang dibuat.

Definisi

Domain Bintang

Himpunan piksel putih gambar mewakili domain bintang jika (dan hanya jika) ada (setidaknya) satu piksel tengah . The pusat pixel adalah salah satu piksel putih yang dapat conneced oleh garis lurus untuk semua piksel putih lainnya seperti garis-satunya melintasi piksel putih. (Karena itu piksel tengah tidak selalu unik.)

Garis lurus antara dua piksel

Diberi dua piksel (awal dan akhir, keduanya berwarna merah pada ilustrasi di bawah), garis lurus antara dua piksel terdiri dari semua piksel, yang menyentuh garis (matematis, kuning pada ilustrasi di bawah) yang mengarah dari tengah yang pertama pixel ke tengah pixel terakhir. Sebuah piksel tidak menyentuh garis jika hanya menyentuhnya di sudut, jadi untuk piksel yang termasuk dalam garis piksel, garis (matematis, kuning) harus melewati piksel yang dimaksud dengan panjang yang tidak nol. (Jika hanya menyentuh titik sudut ini dianggap sebagai panjang nol). Perhatikan contoh-contoh berikut:

piksel

Contoh

Gambar pertama harus mewakili contoh 'input' testcase dan dua gambar lainnya mewakili dua kemungkinan output yang valid untuk contoh yang diberikan:

contoh testcase solusi contoh pertama solusi contoh kedua

Area kuning (sebelumnya hitam) juga dihitung sebagai domain 'putih', sedangkan area biru (sebelumnya putih) dihitung sebagai bagian 'hitam' di luar domain, dan titik merah setiap kali mewakili satu kemungkinan piksel tengah.

Uji Kasus

Kasus uji berikut adalah png dengan ukuran masing-masing 256 x 256 piksel.

test case 1 test case 2 test case 3 test case 4 test case 5 test case 6

Mencetak gol

Silakan jalankan program Anda dengan case uji berikut dan sertakan output (gambar / jumlah perubahan) dalam jawaban Anda. Saya akan membuat leaderboard untuk setiap test case. Skor Anda akan menjadi jumlah dari setiap peringkat di leaderboard - semakin rendah skor semakin baik. Celah standar berlaku. Tidak diperbolehkan membuat program mengenali kasus uji tersebut dan menjalankan kasus khusus untuk mereka. (Tidak diperbolehkan untuk melakukan precompute dan menyimpan piksel tengah yang optimal untuk setiap kasus uji tersebut.) Program harus bekerja untuk gambar apa pun.

Papan peringkat

Name        | Score | 1     - rk | 2     - rk | 3     - rk | 4     - rk | 5     - rk | 5     - rk | Total Changes
------------+-------+------------+------------+------------+------------+------------+------------+--------------
Maltysen    |    11 | 28688 -  2 | 24208 -  2 | 24248 -  1 |  7103 -  2 | 11097 -  2 | 13019 -  2 | 108363
TheBestOne  |     7 | 0     -  1 | 13698 -  1 | 24269 -  2 |   103 -  1 |  5344 -  1 |  4456 -  1 |  47867

code-challenge graphical-output optimization image-processing cacat
sumber

Ini akan membantu jika Anda menjelaskan Gambar. 1. Mengapa Anda menghubungkan piksel merah, misalnya?

DavidC

Saya tidak begitu yakin apa yang Anda maksud. Bisakah Anda memberi sebelum dan sesudah dari salah satu kasus uji Anda?

Seberapa dekat suatu garis dengan sudut piksel agar dapat dilewati?

TheNumberOne

Saya menambahkan beberapa contoh dan mencoba mengklarifikasi teks, saya harap sudah jelas sekarang!

flawr

Adakah orang lain yang ingin mencoba tantangan ini? Saya agak bingung, karena beberapa orang memang menjawab tantangan ini, tetapi sejauh ini kami hanya punya satu (tidak terlalu serius) jawaban. Adakah kritik?

flawr

Jawaban:

Java 8, 47.867 perubahan total.

Menggunakan rata-rata gambar sebagai titik tengah. Ini kemudian menarik semua sinar yang mungkin ke tengah dan memberinya radius terbaik untuk warna. Kemudian warna semua poin tidak valid hitam.

import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class MakeItStarry {

    private static final int RGB_RED = Color.RED.getRGB();
    static int[][] originalImage;

    static final int WHITE = 0;
    static final int BLACK = 1;
    static final int RGB_WHITE = Color.WHITE.getRGB();
    static final int RGB_BLACK = Color.BLACK.getRGB();
    static final int RGB_BLUE = Color.BLUE.getRGB();
    static final int RGB_YELLOW = Color.YELLOW.getRGB();

    public static void main(String[] args) throws Exception{
        originalImage = convert(ImageIO.read(new File(args[0])));
        Point center = findCenter(originalImage);
        int[][] nextImage = starry(originalImage, center);
        BufferedImage result = difference(originalImage, nextImage);
        result.setRGB(center.x, center.y, RGB_RED);
        String fileType;
        String fileName;
        if (args[1].split("\\.").length > 1){
            fileType = args[1].split("\\.")[1];
            fileName = args[1];
        } else {
            fileType = "PNG";
            fileName = args[1] + ".PNG";
        }
        ImageIO.write(result, fileType, new File(fileName));
        System.out.println(cost);
    }

    static int cost;

    private static BufferedImage difference(int[][] image1, int[][] image2) {
        cost = 0;
        int height = image1[0].length;
        int width = image1.length;
        BufferedImage result = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        for (int x = 0; x < width; x++){
            for (int y = 0; y < width; y++){
                if (image1[x][y] == image2[x][y]){
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_WHITE);
                    } else {
                        result.setRGB(x, y, RGB_BLACK);
                    }
                } else {
                    cost++;
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_BLUE);
                    } else {
                        result.setRGB(x, y, RGB_YELLOW);
                    }
                }
            }
        }
        return result;
    }

    private static int[][] starry(int[][] image, Point center) {
        int width = image.length;
        int height = image[0].length;
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                result[x][y] = BLACK;
            }
        }
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++) {
                Point endPoint = new Point(x, y, image);
                List<Point> line = Point.lineTo(center, endPoint, image);
                List<Point> newLine = starRay(line);
                newLine.stream().filter(point -> result[point.x][point.y] == BLACK).forEach(point -> {
                    result[point.x][point.y] = point.color;
                });
            }
        }
        int distance = 0;
        while (distance < height || distance < width){//This removes pixels that can't see the center.
            for (int x = Math.max(center.x - distance,0); x < center.x + distance && x < width; x++){
                for (int y = Math.max(center.y - distance, 0); y < center.y + distance && y < height; y++){
                    Point point = new Point(x, y, result);
                    if (Point.distance(center, point) != distance){
                        continue;
                    }
                    if (point.color == WHITE){
                        List<Point> line = Point.lineTo(center, point, result);
                        for (Point p : line){
                            if (p.color == BLACK){
                                point.color = BLACK;
                                break;
                            }
                        }
                        result[point.x][point.y] = point.color;
                    }
                }
            }//All white pixels can technically see the center but only if looking from the edge.
            distance++;
        }
        return result;
    }

    private static List<Point> starRay(List<Point> line) {
        int numOfWhites = 0;
        int farthestGoodPoint = 0;
        int blackCost = 0;
        int whiteCost = 0;
        for (int i = 0; i < line.size(); i++){
            if (line.get(i).color == WHITE){
                numOfWhites++;
                whiteCost++;
                if (numOfWhites + whiteCost > blackCost){
                    blackCost = 0;
                    whiteCost = 0;
                    farthestGoodPoint = i;
                }
            } else {
                blackCost++;
                numOfWhites = 0;
            }
        }
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < line.size(); i++){
            Point p = line.get(i);
            if (i <= farthestGoodPoint){
                result.add(new Point(p.x, p.y, WHITE));
            } else {
                result.add(new Point(p.x, p.y, BLACK));
            }
        }
        return result;
    }

    private static Point findCenter(int[][] image) {
        double totalx = 0;
        double totaly = 0;
        int counter = 0;
        int width = image.length;
        int height = image[0].length;
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image[x][y] == WHITE){
                    totalx += x;
                    totaly += y;
                    counter++;
                }
            }
        }
        return new Point((int)(totalx/counter), (int)(totaly/counter), image);
    }

    private static int[][] convert(BufferedImage image) {
        int width = image.getWidth();
        int height  = image.getHeight();
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image.getRGB(x, y) == RGB_WHITE){
                    result[x][y] = WHITE;
                } else {
                    result[x][y] = BLACK;
                }
            }
        }
        return result;
    }


    private static class Point {

        public int color;
        public int y;
        public int x;

        public Point(int x, int y, int[][] image) {
            this.x = x;
            this.y = y;
            this.color = image[x][y];
        }

        public Point(int x, int y, int color) {
            this.x = x;
            this.y = y;
            this.color = color;
        }

        public static List<Point> lineTo(Point point1, Point point2, int[][] image) {
            List<Point> result = new ArrayList<>();
            boolean reversed = false;
            if (point1.x > point2.x){
                Point buffer = point1;
                point1 = point2;
                point2 = buffer;
                reversed = !reversed;
            }
            int rise = point1.y - point2.y;
            int run = point1.x - point2.x;
            if (run == 0){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int x = point1.x;
                for (int y = point1.y; y <= point2.y; y++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            if (rise == 0){
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int y = point1.y;
                for (int x = point1.x; x <= point2.x; x++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            int gcd = gcd(rise, run);
            rise /= gcd;
            run /= gcd;
            double slope = (rise + 0.0) / run;
            if (Math.abs(rise) >= Math.abs(run)){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double x = point1.x;
                for (double y = point1.y + .5; y <= point2.y; y++){
                    int px = (int) Math.round(x);
                    if (Math.abs(Math.abs(px - x) - .5) < Math.abs(1.0 / (rise * 4))){
                        x += 1/slope;
                        continue;
                    }
                    result.add(new Point(px, (int) Math.round(y - .5), image));
                    result.add(new Point(px, (int) Math.round(y + .5), image));
                    x += 1/slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            } else {
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double y = point1.y;
                for (double x = point1.x + .5; x <= point2.x; x++){
                    int py = (int) Math.round(y);
                    if (Math.abs(Math.abs(py - y) - .5) < Math.abs(1.0 / (run * 4))) {
                        y += slope;
                        continue;
                    }
                    result.add(new Point((int) Math.round(x - .5), py, image));
                    result.add(new Point((int) Math.round(x + .5), py, image));
                    y += slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
        }

        private static List<Point> reversed(List<Point> points) {
            List<Point> result = new ArrayList<>();
            for (int i = points.size() - 1; i >= 0; i--){
                result.add(points.get(i));
            }
            return result;
        }

        private static int gcd(int num1, int num2) {
            if (num1 < 0 && num2 < 0){
                return -gcd(-num1, -num2);
            }
            if (num1 < 0){
                return gcd(-num1, num2);
            }
            if (num2 < 0){
                return gcd(num1, -num2);
            }
            if (num2 > num1){
                return gcd(num2, num1);
            }
            if (num2 == 0){
                return num1;
            }
            return gcd(num2, num1 % num2);
        }

        @Override
        public String toString(){
            return x + " " + y;
        }

        public static int distance(Point point1, Point point2) {
            return Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y);
        }
    }
}

Hasil

Gambar 1 - 0 perubahan, Gambar 2 - 13.698 perubahan

Gambar 3 - 24.269 perubahan, Gambar 4 - 103 perubahan

Gambar 5 - 5.344 perubahan, Gambar 6 - 4.456 perubahan

Tanpa piksel yang tidak valid dihapus, 42.782 mengubah total

Piksel hijau adalah lapisan pertama piksel yang tidak valid.

Gambar 1 - 0 perubahan, Gambar 2- 9.889 perubahan

Gambar 3 - 24.268 perubahan, Gambar 4 - 103 perubahan

Gambar 5 - 4,471 perubahan, Gambar 6- 4,050 perubahan

Semua piksel putih di semua gambar dapat memiliki garis yang diambil dari piksel tengah jika garis tidak harus berasal / berakhir di tengah, melainkan bagian mana pun pada piksel.

args[0] berisi nama file input.

args[1] berisi nama file output.

Mencetak ke stdoutsejumlah perubahan.

TheNumberOne
sumber

Tampak hebat! Bisakah Anda menjelaskan apa yang Anda maksud dengan 'piksel tidak valid'? Saya tidak begitu mengerti itu. Juga pada gambar 2 di kanan bawah saya tidak bisa mengikuti mengapa program Anda 'diggs' ke dalam dinding hitam tetapi kemudian masih mewarnai titik-titik putih hitam lagi, tetapi saya pikir ini ada hubungannya dengan 'piksel tidak valid' bukan?

flawr

Beberapa piksel yang tidak valid menyebabkan efek kaskade yang membuat lebih banyak lagi yang tidak valid. Saya akan memodifikasi beberapa gambar terakhir untuk menunjukkan lapisan pertama piksel yang tidak valid sebagai hijau.

TheNumberOne

Python - PIL - 216.228 108.363 perubahan total

Whoo! Potong menjadi dua terima kasih ke @AJMansfield! Algoritma ini melompati semua yang mengkhawatirkan dengan menghitung garis dan optimasi dan apa yang tidak. ~~Itu hanya mengubah semua putih menjadi hitam kecuali satu. Jika tidak ada putih, itu membuat satu hitam menjadi putih.~~ Itu memeriksa apakah ada lebih banyak putih atau hitam dan mengubah setiap satu dari jenis lain untuk itu kecuali satu. Jika tidak ada hitam itu menjadikan (0, 0) pusat.

import Image
from itertools import product

img = Image.open(raw_input())
img = img.convert("RGB")

pixdata = img.load()
changed=0

m=False
count=0
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y]==(0, 0, 0):
        count+=1

colors=[(0, 0, 0), (255, 255, 0)] if img.size[0]*img.size[1]-count>count else [(255, 255, 255), (0, 0, 255)]
m=False
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y] == colors[0]:
        if m:
            pixdata[x, y] = colors[1]
        else:
            pixdata[x, y] = (255, 0, 0)
            m=True
        changed+=1

if not m:
    pixdata[0, 0]==(255, 0, 0)
    changed+=1
if colors[0]==(255, 255, 255):
    changed-=1

print changed
img.save("out.png", "PNG")

Hasil

Gambar 1 - 28688 perubahan, Gambar 2 - 24208 perubahan

Gambar 3 - 24248 perubahan, Gambar 4 - 7103 perubahan

Gambar 5 - 11097 perubahan, Gambar 6 - 13019 perubahan

Mengambil nama file dari raw_input dan menulis ke out.png dan mencetak sejumlah perubahan.

Maltysen
sumber

Perhatikan bahwa piksel yang diubah dari hitam menjadi putih harus berwarna kuning pada output Anda. Thos yang diubah dari putih menjadi hitam harus biru, dan tengah (dalam kasus Anda, piksel 'putih' Anda hanya merah dalam output Anda. Selain itu, terima kasih atas partisipasi Anda =) PS: Seharusnya selalu memungkinkan untuk membuat domain bintang, bahkan ketika Anda memiliki gambar hitam penuh sebagai input, Anda dapat mengubah satu piksel menjadi putih (merah).

flawr

Ini bisa mustahil jika tidak ada piksel putih atau hitam (yaitu warna penuh). Bagaimanapun saya sedang membuat perubahan lain.

Maltysen

Oh Gambar hitam putih. Salahku.

Maltysen

Saya pikir mungkin lebih efisien untuk melakukan strategi yang berlawanan, dan mengubah semua piksel hitam menjadi putih. Apakah kamu mencobanya?

AJMansfield

@ AJMansfield Saya pikir ini hanya akan lebih efisien untuk test case yang diberikan, jadi mungkin ini sudah bisa dianggap sebagai pengkondisian algoritma untuk testcases yang diberikan.

flawr