Jembatan Kesenjangan

14

Diberi gambar hitam dan putih dengan latar belakang putih dan satu set titik-titik hitam, cat satu set piksel putih merah, sedemikian rupa sehingga ada jalur antara setiap pasangan piksel hitam.

Detail

  • Path adalah sekumpulan piksel yang terhubung (konektivitas 8-lingkungan). Piksel hitam dapat digunakan sebagai bagian dari jalur. Tujuannya adalah mencoba meminimalkan set piksel merah dalam kondisi di atas, dan menghasilkan gambar yang sesuai.

  • Anda tidak perlu menemukan solusi optimal.

  • Solusi terburuk yang sepele dan sekaligus hanya mengecat semua piksel putih merah.

  • Contoh (Piksel diperbesar untuk visibilitas):

Detail

  • Diberikan gambar piksel (dalam format apa pun yang sesuai) mengembalikan gambar lain dengan titik-titik yang terhubung seperti ditentukan di atas, serta bilangan bulat yang menunjukkan berapa banyak piksel merah yang digunakan.
  • Skor adalah produk dari (1 + jumlah piksel merah) untuk masing-masing dari 14 testcases.
  • Tujuannya adalah memiliki skor terendah.

Testcases

14 testcas ditunjukkan di bawah ini. Program python untuk memverifikasi keterhubungan output dapat ditemukan di sini.

Meta

Terima kasih kepada @Veskah, @Fatalize, @ wizzwizz4, dan @trichoplax untuk berbagai saran.

cacat
sumber
1
Tantangan bagus; Saya suka yang dengan skema penilaian yang berbeda dan kreatif. Saya menganggap program perlu bekerja pada gambar yang sewenang-wenang, bukan hanya 14 contoh spesifik ini? Jika demikian, dapatkah kita mengasumsikan ukuran maks yang wajar, seperti 512x512 per gambar Mona Lisa, atau 1024x1024?
BradC
Terima kasih untuk umpan baliknya! Ya, Anda dapat mengasumsikan ukuran maksimal (juga ukuran minimal jika perlu), selama semua 14 contoh dapat diproses.
flawr
bagaimana cara mengkonversi png ke ascii atau json atau sesuatu yang mudah diurai?
ngn
Apakah Anda harus bisa menghitung skor Anda sendiri? Sebuah program yang mencoba setiap kombinasi piksel putih yang memungkinkan untuk melukis merah, dan melihat subset mana yang memiliki piksel merah paling sedikit sambil menghubungkan semua piksel hitam akan memiliki skor terbaik, tetapi akan sangat lambat sehingga akan memakan waktu lebih lama daripada masa pakai. alam semesta untuk benar-benar menghitung skor itu.
Leo Tenenbaum
1
@ ngn Buka di GIMP, simpan sebagai format netpbm.
wizzwizz4

Jawaban:

7

C, skor 2.397x10 ^ 38

Manusia ini terlalu lama untuk dilakukan, kemungkinan besar karena pilihan bahasa saya. Saya mendapatkan algoritma yang bekerja cukup awal, tetapi mengalami banyak masalah dengan alokasi memori (tidak bisa hal-hal gratis secara rekursif karena stack overflow, ukuran kebocoran sangat besar).

Masih! Ini mengalahkan entri lain pada setiap test case, dan bahkan mungkin menjadi optimal mendapatkan solusi yang cukup dekat atau tepat banyak waktu.

Bagaimanapun, ini kodenya:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define WHITE 'W'
#define BLACK 'B'
#define RED   'R'


typedef struct image {
    int w, h;
    char* buf;
} image;

typedef struct point {
    int x, y;
    struct point *next;
    struct point *parent;
} point;

typedef struct shape {
    point* first_point;
    point* last_point;

    struct shape* next_shape;
} shape;


typedef struct storage {
    point* points;
    size_t points_size;
    size_t points_index;

    shape* shapes;
    size_t shapes_size;
    size_t shapes_index;
} storage;

char getpx(image* img, int x, int y) {
    if (0>x || x>=img->w || 0>y || y>=img->h) {
        return WHITE;
    } else {
        return img->buf[y*img->w+x];
    }
}

storage* create_storage(int w, int h) {
    storage* ps = (storage*)malloc(sizeof(storage));

    ps->points_size = 8*w*h;
    ps->points = (point*)calloc(ps->points_size, sizeof(point));
    ps->points_index = 0;

    ps->shapes_size = 2*w*h;
    ps->shapes = (shape*)calloc(ps->shapes_size, sizeof(shape));
    ps->shapes_index = 0;

    return ps;
}

void free_storage(storage* ps) {
    if (ps != NULL) {
        if (ps->points != NULL) {
            free(ps->points);
            ps->points = NULL;
        }
        if (ps->shapes != NULL) {
            free(ps->shapes);
            ps->shapes = NULL;
        }
        free(ps);
    }
}


point* alloc_point(storage* ps) {
    if (ps->points_index == ps->points_size) {
        printf("WHOAH THERE BUDDY SLOW DOWN\n");
        /*// double the size of the buffer
        point* new_buffer = (point*)malloc(ps->points_size*2*sizeof(point));
        // need to change all existing pointers to point to new buffer
        long long int pointer_offset = (long long int)new_buffer - (long long int)ps->points;
        for (size_t i=0; i<ps->points_index; i++) {
            new_buffer[i] = ps->points[i];
            if (new_buffer[i].next != NULL) {
                new_buffer[i].next += pointer_offset;
            }
            if (new_buffer[i].parent != NULL) {
                new_buffer[i].parent += pointer_offset;
            }
        }

        for(size_t i=0; i<ps->shapes_index; i++) {
            if (ps->shapes[i].first_point != NULL) {
                ps->shapes[i].first_point += pointer_offset;
            }
            if (ps->shapes[i].last_point != NULL) {
                ps->shapes[i].last_point += pointer_offset;
            }
        }

        free(ps->points);
        ps->points = new_buffer;
        ps->points_size = ps->points_size * 2;*/
    }
    point* out = &(ps->points[ps->points_index]);
    ps->points_index += 1;
    return out;
}

shape* alloc_shape(storage* ps) {
    /*if (ps->shapes_index == ps->shapes_size) {
        // double the size of the buffer
        shape* new_buffer = (shape*)malloc(ps->shapes_size*2*sizeof(shape));
        long long int pointer_offset = (long long int)new_buffer - (long long int)ps->shapes;
        for (size_t i=0; i<ps->shapes_index; i++) {
            new_buffer[i] = ps->shapes[i];
            if (new_buffer[i].next_shape != NULL) {
                new_buffer[i].next_shape += pointer_offset;
            }
        }
        free(ps->shapes);
        ps->shapes = new_buffer;
        ps->shapes_size = ps->shapes_size * 2;
    }*/
    shape* out = &(ps->shapes[ps->shapes_index]);
    ps->shapes_index += 1;
    return out;
}

shape floodfill_shape(image* img, storage* ps, int x, int y, char* buf) {
    // not using point allocator for exploration stack b/c that will overflow it

    point* stack = (point*)malloc(sizeof(point));
    stack->x = x;
    stack->y = y;
    stack->next = NULL;
    stack->parent = NULL;

    point* explored = NULL;
    point* first_explored;
    point* next_explored;

    while (stack != NULL) {
        int sx = stack->x;
        int sy = stack->y;
        point* prev_head = stack;
        stack = stack->next;
        free(prev_head);

        buf[sx+sy*img->w] = 1; // mark as explored

        // add point to shape
        next_explored = alloc_point(ps);
        next_explored->x = sx;
        next_explored->y = sy;
        next_explored->next = NULL;
        next_explored->parent = NULL;

        if (explored != NULL) {
            explored->next = next_explored;
        } else {
            first_explored = next_explored;
        }
        explored = next_explored;

        for (int dy=-1; dy<2; dy++) {
        for (int dx=-1; dx<2; dx++) {
            if (dy != 0 || dx != 0) {
                int nx = sx+dx;
                int ny = sy+dy;
                if (getpx(img, nx, ny) == WHITE || buf[nx+ny*img->w]) {
                    // skip adding point to fringe
                } else {
                    // push point to top of stack
                    point* new_point = (point*)malloc(sizeof(point));
                    new_point->x = nx;
                    new_point->y = ny;
                    new_point->next = stack;
                    new_point->parent = NULL;

                    stack = new_point;
                } 
            }
        }
        }
    }

    /*if (getpx(img, x, y) == WHITE || buf[x+y*img->w]) {
        return (shape){NULL, NULL, NULL};
    } else {
        buf[x+y*img->w] = 1;

        shape e  = floodfill_shape(img, ps, x+1, y,   buf);
        shape ne = floodfill_shape(img, ps, x+1, y+1, buf);
        shape n  = floodfill_shape(img, ps, x,   y+1, buf);
        shape nw = floodfill_shape(img, ps, x-1, y+1, buf);
        shape w  = floodfill_shape(img, ps, x-1, y,   buf);
        shape sw = floodfill_shape(img, ps, x-1, y-1, buf);
        shape s  = floodfill_shape(img, ps, x,   y-1, buf);
        shape se = floodfill_shape(img, ps, x+1, y-1, buf);

        point *p = alloc_point(ps);
        p->x = x;
        p->y = y;
        p->next = NULL;
        p->parent = NULL;

        shape o = (shape){p, p, NULL};
        if (e.first_point != NULL) {
            o.last_point->next = e.first_point;
            o.last_point = e.last_point;
        }
        if (ne.first_point != NULL) {
            o.last_point->next = ne.first_point;
            o.last_point = ne.last_point;
        }
        if (n.first_point != NULL) {
            o.last_point->next = n.first_point;
            o.last_point = n.last_point;
        }
        if (nw.first_point != NULL) {
            o.last_point->next = nw.first_point;
            o.last_point = nw.last_point;
        }
        if (w.first_point != NULL) {
            o.last_point->next = w.first_point;
            o.last_point = w.last_point;
        }
        if (sw.first_point != NULL) {
            o.last_point->next = sw.first_point;
            o.last_point = sw.last_point;
        }
        if (s.first_point != NULL) {
            o.last_point->next = s.first_point;
            o.last_point = s.last_point;
        }
        if (se.first_point != NULL) {
            o.last_point->next = se.first_point;
            o.last_point = se.last_point;
        }

        return o;
    }*/

    shape out = {first_explored, explored, NULL};

    return out;
}

shape* create_shapes(image* img, storage* ps) {
    char* added_buffer = (char*)calloc(img->w*img->h, sizeof(char));
    shape* first_shape = NULL;
    shape* last_shape = NULL;
    int num_shapes = 0;
    for (int y=0; y<img->h; y++) {
        for (int x=0; x<img->w; x++) {
            if (getpx(img, x, y) != WHITE && !(added_buffer[x+y*img->w])) {
                shape* alloced_shape = alloc_shape(ps);
                *alloced_shape = floodfill_shape(img, ps, x, y, added_buffer);

                if (first_shape == NULL) {
                    first_shape = alloced_shape;
                    last_shape = alloced_shape;
                } else if (last_shape != NULL) {
                    last_shape->next_shape = alloced_shape;
                    last_shape = alloced_shape;
                }

                num_shapes++;
            }
        }
    }

    free(added_buffer);

    return first_shape;
}

void populate_buf(image* img, shape* s, char* buf) {
    point* p = s->first_point;

    while (p != NULL) {
        buf[p->x+p->y*img->w] = 1;
        p = p->next;
    }
}

bool expand_frontier(image* img, storage* ps, shape* prev_frontier, shape* next_frontier, char* buf) {
    point* p = prev_frontier->first_point;
    point* n = NULL;

    bool found = false;

    size_t starting_points_index = ps->points_index;

    while (p != NULL) {
        for (int dy=-1; dy<2; dy++) {
        for (int dx=-1; dx<2; dx++) {
            if (dy != 0 || dx != 0) {
                int nx = p->x+dx;
                int ny = p->y+dy;
                if ((0<=nx && nx<img->w && 0<=ny && ny<img->h) // in bounds
                        && !buf[nx+ny*img->w]) {               // not searched yet
                    buf[nx+ny*img->w] = 1;
                    if (getpx(img, nx, ny) != WHITE) {
                        // found a new shape!
                        ps->points_index = starting_points_index;
                        n = alloc_point(ps);
                        n->x = nx;
                        n->y = ny;
                        n->next = NULL;
                        n->parent = p;
                        found = true;
                        goto __expand_frontier_fullbreak;
                    } else {
                        // need to search more
                        point* f = alloc_point(ps);
                        f->x = nx;
                        f->y = ny;
                        f->next = n;
                        f->parent = p;
                        n = f;
                    }
                }
            }
        }}

        p = p->next;
    }
__expand_frontier_fullbreak:
    p = NULL;
    point* last_n = n;
    while (last_n->next != NULL) {
        last_n = last_n->next;
    }

    next_frontier->first_point = n;
    next_frontier->last_point = last_n;

    return found;
}

void color_from_frontier(image* img, point* frontier_point) {
    point* p = frontier_point->parent;

    while (p->parent != NULL) { // if everything else is right,
                                // a frontier point should come in a chain of at least 3
                                // (f point (B) -> point to color (W) -> point in shape (B) -> NULL)
        img->buf[p->x+p->y*img->w] = RED;
        p = p->parent;
    }
}

int main(int argc, char** argv) {
    if (argc < 3) {
        printf("Error: first argument must be filename to load, second argument filename to save to.\n");
        return 1;
    }

    char* fname = argv[1];
    FILE* fp = fopen(fname, "r");

    if (fp == NULL) {
        printf("Error opening file \"%s\"\n", fname);
        return 1;
    }

    int w, h;
    w = 0;
    h = 0;
    fscanf(fp, "%d %d\n", &w, &h);

    if (w==0 || h==0) {
        printf("Error: invalid width/height specified\n");
        return 1;
    }

    char* buf = (char*)malloc(sizeof(char)*w*h+1);
    fgets(buf, w*h+1, fp);
    fclose(fp);

    image img = (image){w, h, buf};

    int nshapes = 0;
    storage* ps = create_storage(w, h);

    while (nshapes != 1) {
        // main loop, do processing step until one shape left
        ps->points_index = 0;
        ps->shapes_index = 0;

        shape* head = create_shapes(&img, ps);
        nshapes = 0;
        shape* pt = head;
        while (pt != NULL) {
            pt = pt->next_shape;
            nshapes++;
        }
        if (nshapes % 1024 == 0) {
            printf("shapes left: %d\n", nshapes);
        }
        if (nshapes == 1) {
            goto __main_task_complete;
        }


        shape* frontier = alloc_shape(ps);
        // making a copy so we can safely free later
        point* p = head->first_point;
        point* ffp = NULL;
        point* flp = NULL;
        while (p != NULL) {
            if (ffp == NULL) {
                ffp = alloc_point(ps);
                ffp->x = p->x;
                ffp->y = p->y;
                ffp->next = NULL;
                ffp->parent = NULL;
                flp = ffp;
            } else {
                point* fnp = alloc_point(ps);
                fnp->x = p->x;
                fnp->y = p->y;
                fnp->next = NULL;
                fnp->parent = NULL;

                flp->next = fnp;
                flp = fnp;
            }

            p = p->next;
        }
        frontier->first_point = ffp;
        frontier->last_point = flp;
        frontier->next_shape = NULL;

        char* visited_buf = (char*)calloc(img.w*img.h+1, sizeof(char));
        populate_buf(&img, frontier, visited_buf);

        shape* new_frontier = alloc_shape(ps);
        new_frontier->first_point = NULL;
        new_frontier->last_point = NULL;
        new_frontier->next_shape = NULL;

        while (!expand_frontier(&img, ps, frontier, new_frontier, visited_buf)) {
            frontier->first_point = new_frontier->first_point;
            frontier->last_point = new_frontier->last_point;
            new_frontier->next_shape = frontier;
        }

        free(visited_buf);
        color_from_frontier(&img, new_frontier->first_point);
__main_task_complete:
        img = img;
    }

    free_storage(ps);

    char* outfname = argv[2];
    fp = fopen(outfname, "w");

    if (fp == NULL) {
        printf("Error opening file \"%s\"\n", outfname);
        return 1;
    }

    fprintf(fp, "%d %d\n", img.w, img.h);
    fprintf(fp, "%s", img.buf);

    free(img.buf);

    fclose(fp);

    return 0;
}

Diuji pada: Arch Linux, GCC 9.1.0, -O3

Kode ini mengambil input / output dalam file kustom yang saya sebut "cppm" (karena itu seperti versi singkat dari format PPM klasik). Skrip python untuk mengkonversi ke / dari itu di bawah ini:

from PIL import Image

BLACK='B'
WHITE='W'
RED  ='R'


def image_to_cppm(infname, outfname):
    outfile = open(outfname, 'w')
    im = Image.open(infname)

    w, h = im.width, im.height
    outfile.write(f"{w} {h}\n")
    for y in range(h):
        for x in range(w):
            r, g, b, *_ = im.getpixel((x, y))
            if r==0 and g==0 and b==0:
                outfile.write(BLACK)
            elif g==0 and b==0:
                outfile.write(RED)
            else:
                outfile.write(WHITE)
    outfile.write("\n")
    outfile.close()
    im.close()

def cppm_to_image(infname, outfname):
    infile = open(infname, 'r')

    w, h = infile.readline().split(" ")
    w, h = int(w), int(h)

    im = Image.new('RGB', (w, h), color=(255, 255, 255))

    for y in range(h):
        for x in range(w):
            c = infile.read(1)
            if c==BLACK:
                im.putpixel((x,y), (0, 0, 0))
            elif c==RED:
                im.putpixel((x,y), (255, 0, 0))

    infile.close()
    im.save(outfname)
    im.close()


if __name__ == "__main__":
    import sys
    if len(sys.argv) < 3:
        print("Error: must provide 2 files to convert, first is from, second is to")

    infname = sys.argv[1]
    outfname = sys.argv[2]

    if not infname.endswith("cppm") and outfname.endswith("cppm"):
        image_to_cppm(infname, outfname)
    elif infname.endswith("cppm") and not outfname.endswith("cppm"):
        cppm_to_image(infname, outfname)
    else:
        print("didn't do anything, exactly one file must end with .cppm")

Penjelasan algoritma

Cara kerja algoritma ini adalah memulai dengan menemukan semua bentuk yang terhubung dalam gambar, termasuk piksel merah. Kemudian mengambil yang pertama dan memperluas pixel satu perbatasan pada suatu waktu sampai bertemu bentuk lain. Kemudian warna semua piksel dari menyentuh ke bentuk asli (menggunakan daftar tertaut itu dibuat sepanjang jalan untuk melacak). Akhirnya, ia mengulangi prosesnya, menemukan semua bentuk baru yang dibuat, sampai hanya ada satu bentuk yang tersisa.

Galeri gambar

Testcase 1, 183 piksel

testcase 1

Testcase 2, 140 piksel

testcase 2

Testcase 3, 244 piksel

testcase 3

Testcase 4, 42 piksel

testcase 4

Testcase 5, 622 piksel

testcase 5

Testcase 6, 1 piksel

testcase 6

Testcase 7, 104 piksel

testcase 7

Testcase 8, 2286 piksel

testcase 8

Testcase 9, 22 piksel

testcase 9

Testcase 10, 31581 piksel

testcase 10

Testcase 11, 21421 piksel

testcase 11

Testcase 12, 5465 piksel

testcase 12

Testcase 13, 4679 piksel

testcase 13

Testcase 14, 7362 piksel

testcase 14

Biru
sumber
2
Kerja bagus! Tampak sangat efisien, walaupun saya bisa membayangkan beberapa bentuk dengan solusi yang sedikit lebih optimal: Testcase 3 (4 titik dalam kotak), misalnya, saya (secara manual) mendapatkan serendah 175 (a X), tidak yakin bagaimana Saya akan memaksakan itu melalui algoritma.
BradC
6

Python, 2.62 * 10 ^ 40

Algoritma ini hanya membanjiri (BFS) pesawat mulai dari bagian hitam gambar, di mana untuk setiap piksel baru kami merekam bagian hitam dari mana ia dibanjiri. Segera setelah kami memiliki dua piksel tetangga dengan bagian hitam berbeda sebagai leluhur, kami pada dasarnya menggabungkan kedua bagian hitam ini dengan menggabungkannya melalui leluhur dua tetangga yang baru saja kami temukan. Secara teori ini bisa diterapkan O(#pixels), tetapi untuk menjaga jumlah kode pada tingkat yang dapat diterima implementasi ini sedikit lebih buruk.

Keluaran

masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini

import numpy as np
from scipy import ndimage
import imageio
from collections import deque

# path to your image
for k in range(1, 15):
    fname=str(k).zfill(2) +'.png'
    print("processing ", fname)

    # load image
    img = imageio.imread("./images/"+fname, pilmode="RGB")
    print(img.shape)

    # determine non_white part
    white = np.logical_and(np.logical_and(img[:,:,0] == 255, img[:,:,1] == 255), img[:,:,2] == 255)
    non_white = np.logical_not(white)

    # find connected components of non-white part
    neighbourhood = np.ones((3,3))
    labeled, nr_objects = ndimage.label(non_white, neighbourhood)

    # print result
    print("number of separate objects is {}".format(nr_objects))

    # start flood filling algorithm
    ind = np.nonzero(labeled)
    front = deque(zip(ind[0],ind[1]))

    membership = np.copy(labeled)
    is_merge_point = np.zeros_like(labeled) > 0
    parent = np.zeros((2,) + labeled.shape) #find ancestor of each pixel
    is_seed = labeled > 0
    size_i, size_j = labeled.shape
    # flood from every seed
    while front: #while we have unexplored pixels
        point = front.popleft()
        # check neighbours:
        for (di,dj) in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
            current = membership[point[0], point[1]]
            new_i, new_j = point[0]+di, point[1]+dj
            if 0 <= new_i < size_i and 0 <= new_j < size_j:
                value = membership[new_i, new_j]
                if value == 0:
                    membership[new_i, new_j] = current
                    front.append((new_i, new_j))
                    parent[:, new_i, new_j] = point
                elif value != current: #MERGE!
                    is_merge_point[point[0], point[1]] = True
                    is_merge_point[new_i, new_j] = True
                    membership[np.logical_or(membership == value, membership == current)] = min(value, current)

    # trace back from every merger
    ind = np.nonzero(is_merge_point)
    merge_points = deque(zip(ind[0].astype(np.int),ind[1].astype(np.int)))
    for point in merge_points:
        next_p = point
        while not is_seed[next_p[0], next_p[1]]:
            is_merge_point[next_p[0], next_p[1]] = True
            next_p = parent[:, next_p[0], next_p[1]].astype(np.int)

    # add red points:
    img_backup = np.copy(img)
    img[:,:,0][is_merge_point] = 255 * img_backup[:,:,0]
    img[:,:,1][is_merge_point] = 0   * img_backup[:,:,1]
    img[:,:,2][is_merge_point] = 0   * img_backup[:,:,2]

    #compute number of new points
    n_red_points = (img[:,:,0] != img[:,:,1]).sum()
    print("#red points:", n_red_points)

    # plot: each component should have separate color
    imageio.imwrite("./out_images/"+fname, np.array(img))

Skor

(1+183)*(1+142)*(1+244)*(1+42)*(1+1382)*(1+2)*(1+104)*(1+7936)*(1+26)*(1+38562)*(1+42956)*(1+6939)*(1+8882)*(1+9916)
= 26208700066468930789809050445560539404000
= 2.62 * 10^40
cacat
sumber
- Ini, saya percaya, adalah optimal. Bagus sekali .-- Oke, ini tidak optimal. Saya tidak mengerti mengapa tidak.
wizzwizz4
@ wizzwizz4 Lihat kasus mudah dari empat sudut persegi: Solusi optimal akan menjadi X. Sementara dalam teori algoritma saya bisa menemukan solusi ini, sangat tidak mungkin. Jauh lebih mungkin menemukan solusi dengan tiga jalur yang masing-masing menghubungkan dua titik.
flawr
@ wizzwizz4 Ya, memperbesar contoh teks wikipedia, dan Anda akan melihat banyak tempat kecil di mana jalur penghubung yang berbeda akan menghemat satu atau dua piksel merah; mereka akan bertambah.
BradC
Tapi ini seperti gelembung sabun di pasak, yang merupakan solusi yang sah untuk masalah pohon Steiner .
wizzwizz4
1
@ wizzwizz4 Perbedaannya, maka, pastilah bahwa kita tidak menghubungkan titik , kita menghubungkan set poin, jadi kita tidak harus memutuskan titik mana pada setiap set untuk terhubung secara optimal. Memperbesar lagi contoh teks, peningkatan yang dapat Anda lihat sebagian besar terkait dengan bagian mana dari setiap bentuk yang terhubung.
BradC
5

Python 3: 1.7x10 ^ 42 1.5x10 ^ 41

Menggunakan Pillow, numpydan scipy.

Gambar diasumsikan berada di imagesfolder yang berada di direktori yang sama dengan skrip.

Penafian : Butuh waktu lama untuk memproses semua gambar.

Kode

import sys
import os

from PIL import Image
import numpy as np
import scipy.ndimage


def obtain_groups(image, threshold, structuring_el):
    """
    Obtain isles of unconnected pixels via a threshold on the R channel
    """
    image_logical = (image[:, :, 1] < threshold).astype(np.int)
    return scipy.ndimage.measurements.label(image_logical, structure=structuring_el)


def swap_colors(image, original_color, new_color):
    """
    Swap all the pixels of a specific color by another color 
    """
    r1, g1, b1 = original_color  # RGB value to be replaced
    r2, g2, b2 = new_color  # New RGB value
    red, green, blue = image[:, :, 0], image[:, :, 1], image[:, :, 2]
    mask = (red == r1) & (green == g1) & (blue == b1)
    image[:, :, :3][mask] = [r2, g2, b2]
    return image


def main(image_path=None):
    images = os.listdir("images")
    f = open("results.txt", "w")

    if image_path is not None:
        images = [image_path]

    for image_name in images:
        im = Image.open("images/"+image_name).convert("RGBA")
        image = np.array(im)

        image = swap_colors(image, (255, 255, 255), (255, 0, 0))

        # create structuring element to determine unconnected groups of pixels in image
        s = scipy.ndimage.morphology.generate_binary_structure(2, 2)

        for i in np.ndindex(image.shape[:2]):
            # skip black pixels
            if sum(image[i[0], i[1]]) == 255:
                continue
            image[i[0], i[1]] = [255, 255, 255, 255]
            # label the different groups, considering diagonal connections as valid
            groups, num_groups = obtain_groups(image, 255, s)
            if num_groups != 1:
                image[i[0], i[1]] = [255, 0, 0, 255]
            # Show percentage
            print((i[1] + i[0]*im.size[0])/(im.size[0]*im.size[1]))

        # Number of red pixels
        red_p = 0
        for i in np.ndindex(image.shape[:2]):
            j = (im.size[1] - i[0] - 1, im.size[0] - i[1] - 1)
            # skip black and white pixels
            if sum(image[j[0], j[1]]) == 255 or sum(image[j[0], j[1]]) == 255*4:
                continue
            image[j[0], j[1]] = [255, 255, 255, 255]
            # label the different groups, considering diagonal connections as valid
            groups, num_groups = obtain_groups(image, 255, s)
            if num_groups != 1:
                image[j[0], j[1]] = [255, 0, 0, 255]
            # Show percentage
            print((j[1] + j[0]*im.size[0])/(im.size[0]*im.size[1]))
            red_p += (sum(image[j[0], j[1]]) == 255*2)

        print(red_p)
        f.write("r_"+image_name+": "+str(red_p)+"\n")

        im = Image.fromarray(image)
        im.show()
        im.save("r_"+image_name)
    f.close()


if __name__ == "__main__":
    if len(sys.argv) == 2:
        main(sys.argv[1])
    else:
        main()

Penjelasan

Solusi sepele. Kita mulai dengan mengubah warna semua piksel putih dalam gambar menjadi merah. Dengan melakukan ini, dijamin bahwa semua elemen (semua pulau piksel hitam) terhubung.

Kemudian, kami mengulangi semua piksel dalam gambar mulai dari sudut kiri atas dan bergerak ke kanan dan ke bawah. Untuk setiap piksel merah kami temukan kami mengubah warnanya menjadi putih. Jika setelah perubahan warna ini masih ada hanya satu elemen (sebuah elemen yang sekarang merupakan pulau piksel hitam dan merah), kita membiarkan piksel putih dan beralih ke piksel berikutnya. Namun, jika setelah perubahan warna dari merah ke putih jumlah elemen lebih besar dari satu, kita meninggalkan piksel merah dan beralih ke piksel berikutnya.

Memperbarui

Seperti dapat dilihat (dan diharapkan) koneksi yang diperoleh dengan hanya menggunakan metode ini menunjukkan pola reguler dan dalam beberapa kasus, seperti pada gambar 6 dan 11, ada piksel merah yang tidak perlu.

Pixel merah ekstra ini dapat dengan mudah dihapus dengan mengulangi lagi gambar dan melakukan operasi yang sama seperti yang dijelaskan di atas tetapi dari sudut kanan bawah ke sudut kiri atas. Lulus kedua ini jauh lebih cepat karena jumlah piksel merah yang harus diperiksa.

Hasil

Gambar yang dimodifikasi setelah pass kedua terdaftar dua kali untuk menunjukkan perbedaan.

18825

Jumlah piksel merah: 18825

334

Jumlah piksel merah: 334

1352

Jumlah piksel merah: 1352

20214

Jumlah piksel merah: 20214

masukkan deskripsi gambar di sini

Jumlah piksel merah: 47268

63 masukkan deskripsi gambar di sini

Jumlah piksel merah: 63 27

17889

Jumlah piksel merah: 17889

259

Jumlah piksel merah: 259

6746

Jumlah piksel merah: 6746

586

Jumlah piksel merah: 586

9 masukkan deskripsi gambar di sini

Jumlah piksel merah: 9 1

126

Jumlah piksel merah: 126

212

Jumlah piksel merah: 212

683

Jumlah piksel merah: 683

Perhitungan skor:

(1 + 6746) * (1 + 126) * (1 + 259) * (1 + 17889) * (1 + 334) * (1 + 586) * (1 + 18825) * (1 + 925) * (1 + 9) * (1 +683) * (1 + 1352) * (1 + 20214) * (1 + 212) * (1 + 63) * (1 + 47268) = 1778700054505858720992088713763655500800000 ~ 1.7x10 ^ 42

Perhitungan skor yang diperbarui setelah menambahkan pass kedua:

(1+ 18825) * (1+ 1352) * (1+ 20214) * (1+ 47268) * (1+ 27) * (1+ 17889) * (1+ 6746) * (1+ 5846) * (1+ 586) * (1 + 1) * (1+ 126) * (1+ 212) * (1+ 334) * (1 + 259) * (1 + 683) = 155636254769262638086807762454319856320000 ~ 1.5x10 ^ 41

Ioannes
sumber
Kerja bagus. Sepertinya kita mungkin perlu menilai yang ini dalam notasi ilmiah: 1,7x10 ^ 42
BradC