14
\$\begingroup\$

In this contest you have to write a program, that accepts a black and white pixel image, and tries to alter it, such that the white shape forms star domain, with as few changes as possible.

Allowed changes are turning white pixels into black ones and turning black pixels into white ones.

The output must again consist of the same image but this time with all the changes and with a/the center marked. The pixels that were changed from white to black must be displayed in blue, the ones that were changed from black to white must be displayed in yellow, and at least one center pixel must be displayed in red. (Exact colours are up to you.) The program must ouput the specified image as well as the total number of changes that were made.

Definitions

Star Domain

The set of white pixels of the image represent a star domain if (and only if) there is (at least) one center pixel. The center pixel is one of the white pixels that can be conneced by a straight line to all of the other white pixels such that the line only traverses white pixels. (The center pixel is therefore not necessarily unique.)

Straight line between two pixels

Given two pixel (start and end, both red in the illustration below), the straigth line between the two pixels consists of all the pixels, that touch the (mathematical, yellow in the illustration below) line that leads from the center of the first pixel to the center of the last pixel. A pixel is not touching the line if it only touches it by a corner, so for a pixel to belong to the pixel line the (mathematical, yellow) line has to cross the pixel in question with a nonzero length. (If it only touches the corner point this is considered as length zero). Consider the following examples:

pixels

Example

The first image should represent an example testcase 'input' and the two other images represent two valid possible outputs for the given example:

example testcase first example solution second example solution

The yellow areas (formerly black) count to the 'white' domain as well, while the blue areas (formerly white) count to the 'black' part outside of the domain, and the red dot each time represents one possible center pixel.

Test Cases

The follwoing test cases are png's with each a size of 256 x 256 pixels.

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

Scoring

Please run your program with the following test cases and include the output (image / number of changes) in your answer. I will make a leaderboard for each test case. Your score will be the sum of each ranking in the leaderboard -the lower the score the better. Standard loopholes apply. It is not allowed to make the program recognize those test cases and run a special case for them. (It is not allowed to precompute and save the optimal center pixels for each of those test cases.) The program should work for any images.

Leaderboard

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  
\$\endgroup\$
  • 2
    \$\begingroup\$ It would help if you were to explain Fig. 1. Why are you connecting red pixels, for instance? \$\endgroup\$ – DavidC Jan 9 '15 at 15:45
  • 4
    \$\begingroup\$ I'm not really sure what you mean. Can you give a before and after of one of your test cases? \$\endgroup\$ – Yimin Rong Jan 9 '15 at 16:54
  • \$\begingroup\$ How close does a line have to be to a pixel corner for it to be considered to pass through? \$\endgroup\$ – TheNumberOne Jan 9 '15 at 17:49
  • \$\begingroup\$ I added some examples and tried to clarify the text, I hope it is clear now! \$\endgroup\$ – flawr Jan 9 '15 at 23:59
  • \$\begingroup\$ Is there anyone else intending to make an attempt this challenge? I am somewhat confused, since quite a few people did upvote this challenge but we've only got one (not very serious) answer so far. Any criticism? \$\endgroup\$ – flawr Jan 11 '15 at 22:00
4
\$\begingroup\$

Java 8, 47,867 changes total.

Uses the average of the image as the center point. It then draws all possible rays to the center and gives it the best radius to color. It then colors all invalid points black.

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

Results

Image 1 - 0 changes, Image 2 - 13,698 changes

12

Image 3 - 24,269 changes, Image 4 - 103 changes

34

Image 5 - 5,344 changes, Image 6 - 4,456 changes

56

Without invalid pixels removed, 42,782 changes total

Green pixels are the first layer of invalid pixels.

Image 1 - 0 changes, Image 2- 9,889 changes

12

Image 3 - 24,268 changes, Image 4 - 103 changes

34

Image 5 - 4,471 changes, Image 6- 4,050 changes

56

All white pixels in all the pictures can have a line drawn to them from the center pixel if the line does not have to originate/end at the centers but rather anywhere on the pixel.

args[0] contains input file name.

args[1] contains output file name.

Prints to stdout number of changes.

\$\endgroup\$
  • \$\begingroup\$ Looks great! Can you explain what you mean by 'invalid pixels'? I didn't quite understand that. Also in the image 2 on the bottom right I could not follow why your program 'diggs' into the black wall but then still colour the white dots black again, but i think this has to do with the'invalid pixels' does it? \$\endgroup\$ – flawr Jan 12 '15 at 9:34
  • \$\begingroup\$ The few invalid pixels cause a cascade effect that make many more invalid. I will modify the last few images to show the first layer of invalid pixels as green. \$\endgroup\$ – TheNumberOne Jan 12 '15 at 20:09
3
\$\begingroup\$

Python - PIL - 216,228 108,363 changes total

Whoo! Cut it in half thanks to @AJMansfield! This algorithm skips all the worrying about with calculating lines and optimization and what not. It just changes all whites to black except for one. If there are no whites, it makes one black a white. It check if there are more whites or black and changes every single one of the other kind to it except for one. If there are no black it makes (0, 0) the center.

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")

Results

Image 1 - 28688 changes, Image 2 - 24208 changes

Image 3 - 24248 changes, Image 4 - 7103 changes

Image 5 - 11097 changes, Image 6 - 13019 changes

Takes file name from raw_input and writes to out.png and prints number of changes.

\$\endgroup\$
  • \$\begingroup\$ Note that the pixels that were changed from black to white should be yellow in your output. Thos that were changed from white to black should be blue, and the center (in your case your only 'white' pixel should be red in your output. Other than that, thank you for participating=) PS: It should always be possible to make a star domain, even when you have a full black image as input, you can change one pixel to white (red). \$\endgroup\$ – flawr Jan 10 '15 at 0:14
  • \$\begingroup\$ It can be impossible if there are no white or black pixels (i.e. full color). In any case I'm making the other changes. \$\endgroup\$ – Maltysen Jan 10 '15 at 0:23
  • \$\begingroup\$ Oh. Black & white image. My bad. \$\endgroup\$ – Maltysen Jan 10 '15 at 0:29
  • \$\begingroup\$ I think it might be more efficient to do the opposite strategy, and change all black pixels to white ones. Did you try that? \$\endgroup\$ – AJMansfield Jan 11 '15 at 21:27
  • \$\begingroup\$ @AJMansfield I think this would only be more efficient for the given test case, so perhaps this could already be considered as conditioning the algorithm for the given testcases. \$\endgroup\$ – flawr Jan 11 '15 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.