Jako dane wejściowe zostanie wyświetlony obraz w skali szarości. Twoim zadaniem jest znalezienie statycznego lub zapętlonego wzoru w grze życia Conwaya który najbardziej przypomina obraz wejściowy.

Twój wynik może być albo obrazu nieruchomego lub zapętlenie animacji w pewnym formacie, który może być przekształcony do GIF. Wymiary obrazu wyjściowego powinny być takie same jak dane wejściowe i mogą zawierać tylko czarno-białe piksele.

Jeśli wyjściem jest animacja, każda klatka musi zostać wygenerowana z poprzedniej zgodnie z zasadami Game of Life, z jedną komórką na piksel. Animacja musi być zapętlona, ​​przy czym pierwsza klatka jest generowana z ostatniej klatki według tych samych reguł.

Jeśli wydruk jest nieruchomym obrazem, zastosowanie do niego reguł gry musi dać ten sam obraz. Oznacza to, że żadna „żywa” komórka nie może mieć więcej niż trzech lub mniej niż dwóch „żywych” sąsiadów, a żadna „martwa” komórka nie może mieć dokładnie trzech „żywych” sąsiadów. (Pamiętaj, że jest to w zasadzie taka sama animacja jak opisano powyżej, ale tylko z jedną klatką).

Dodatkowe zasady i wyjaśnienia:

• Ty (lub twój program) możesz wybrać, czy komórki „żywe” mają być reprezentowane jako białe, a „martwe” jako czarne, lub odwrotnie. Oznacza to, że możesz to zakodować na stałe lub twój program może wybrać go na podstawie obrazu wejściowego. (Ale musi być taki sam dla każdej klatki animacji.)

• Warunki brzegowe powinny być okresowe, co oznacza, że ​​komórki w skrajnej prawej kolumnie mają sąsiadów w skrajnej lewej kolumnie itp.

• W przypadku animacji liczba klatek na sekundę zależy od Ciebie (lub Twojego programu); Wyobrażam sobie, że duże szybkości klatek będą działać dobrze dla przybliżania szarych pikseli.

• Proszę zamieścić co najmniej dwa wyniki osadzone w odpowiedzi. Jeśli możesz opublikować wyniki ze wszystkich poniższych obrazów wejściowych, najlepiej jest.

• Dopuszczalne jest przeskalowanie obrazów testowych, jeśli jest to konieczne do uzyskania plików gif o wystarczająco małych rozmiarach plików. Jeśli chcesz również link do większych plików, nie ma sprawy. Jeśli chcesz się pochwalić, znajdź pliki źródłowe w wyższej rozdzielczości.

• Staraj się unikać posiadania zbyt wielu kontrolowalnych parametrów w kodzie - najlepiej, jeśli jedynym wejściem programu jest obraz. Wyjątkiem jest sytuacja, gdy chcesz mieć parametr kontrolujący liczbę klatek animacji, ponieważ wpłynie to na rozmiar pliku.

• Możesz użyć programów zewnętrznych, aby zmienić format plików wejściowych i wyjściowych i / lub skompilować ramki wyjściowe w animację, jeśli chcesz. (Nie jest to wyzwanie związane z obsługą formatu plików).

• To konkurs popularności , więc wygrywa odpowiedź z największą liczbą głosów.

Oto wybór zdjęć testowych, pochodzących głównie z innych pytań na tej stronie. (Możliwe, że później dodam dodatkowe „wejściowe” obrazy dodatkowe).

Na początek jest bardzo głupia próba odniesienia w Pythonie 2, która wykorzystuje fakt, że blok czterech kwadratów jest stabilną strukturą w Grze Życia. Po prostu przeskalowuje obraz wejściowy 4-krotnie, a następnie rysuje blok, jeśli odpowiadający mu piksel jest ciemniejszy niż 0,5.

from skimage import io
from skimage import transform
import sys

img = io.imread(sys.argv[1],as_grey=True)

source = transform.resize(img, [i/4 for i in img.shape])

img[:]=1
for x in xrange(source.shape[0]):
    for y in xrange(source.shape[1]):
        if source[x,y]<0.5:
            img[x*4, y*4] = 0
            img[x*4+1, y*4] = 0
            img[x*4, y*4+1] = 0
            img[x*4+1, y*4+1] = 0

io.imsave(sys.argv[2], img)

Oto kilka wyników z przykładowego kodu. Jestem pewien, że możliwe są znacznie lepsze wyniki.

Pyton

import sys, random, itertools
from PIL import Image

filename, cutoff = sys.argv[1], int(sys.argv[2]) if len(sys.argv) > 2 else 128

# load command-line arg as image
src = Image.open(sys.argv[1]).convert("L") # grayscale
(w, h), src = src.size, src.load()
# flatten
src = bytearray(src[x, y] for y in range(h) for x in range(w))
size = len(src)
neighbour_offsets = (-w-1,-w,-w+1,-1,1,w-1,w,w+1)    

shapes = set()
max_shape_x, max_shape_y = 0, 0
for shape in (((1, 1), (1, 1), "b"), # block
    ((0,1,1,0),(1,0,0,1),(0,1,1,0), "h"), # hive
    ((0,0,1,0),(0,1,0,1),(1,0,0,1),(0,1,1,0), "l"), # loaf
    ((0,1,0),(1,0,1),(0,1,0), "t"), # tub
    ((1,1,0),(1,0,1),(0,1,0), "B"), # boat
    ((1,1,0),(1,0,1),(0,1,1), "s"), # ship
    ((1,1,0,1,1),(0,1,0,1,0),(0,1,0,1,0),(1,1,0,1,1), "I"), # II
    ((0,0,0,1,1),(0,0,0,0,1),(0,0,0,1,0),(1,0,1,0,0),(1,1,0,0,0), "c"), # canoe sinking
    ((1,1,0,0),(1,0,0,1),(0,0,1,1), "a"), # aircraft carrier
    ((0,1,1,0,0),(1,0,0,1,0),(0,1,0,0,1),(0,0,1,1,0), "m"), # mango
    ((0,1,1,0),(1,0,0,1),(1,0,0,1),(0,1,1,0), "p"), # pond
    ((0,0,0,1,1),(0,0,1,0,1),(0,0,1,0,0),(1,0,1,0,0),(1,1,0,0,0), "i"), # integral
    ((1,1,0,1),(1,0,1,1), "S"), # snake
    ((1,1,0,0),(1,0,1,0),(0,0,1,0),(0,0,1,1), "f"), # fish hook
    ):
    X, Y = len(shape[0]), len(shape)-1
    max_shape_x, max_shape_y = max(X, max_shape_x), max(Y, max_shape_y)
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y) for x in range(X) if shape[y][x]), shape[:-1], shape[-1]))
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y) for x in range(X-1,-1,-1) if shape[y][x]), shape[:-1], shape[-1]))
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y-1,-1,-1) for x in range(X) if shape[y][x]), shape[:-1], shape[-1]))
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y-1,-1,-1) for x in range(X-1,-1,-1) if shape[y][x]), shape[:-1], shape[-1]))

def torus(i, *indices):
    if len(indices) == 1:
        return (i + indices[0]) % size
    return [(i + n) % size for n in indices]

def iter_neighbours(i):
    return torus(i, *neighbour_offsets)

def conway(src, dest):
    for i in range(size):
        alive = count_alive(src, i)
        dest[i] = (alive == 2 or alive == 3) if src[i] else (alive == 3)

def calc_score(i, set):
    return 255-src[i] if not set else src[i]

def count_alive(board, i, *also):
    alive = 0
    for j in iter_neighbours(i):
        if board[j] or (j in also):
            alive += 1
    return alive

def count_dead(board, i, *also):
    dead = 0
    for j in iter_neighbours(i):
        if (not board[j]) and (j not in also):
            dead += 1
    return dead

def iter_alive(board, i, *also):
    for j in iter_neighbours(i):
        if board[j] or (j in also):
            yield j

def iter_dead(board, i, *also):
    for j in iter_neighbours(i):
        if (not board[j]) and (j not in also):
            yield j

def check(board):
    for i in range(size):
        alive = count_alive(board, i)
        if board[i]:
            assert alive == 2 or alive == 3, "alive %d has %d neighbours %s" % (i, alive, list(iter_alive(board, i)))
        else:
            assert alive != 3, "dead %d has 3 neighbours %s" % (i, list(iter_alive(board, i)))

dest = bytearray(size)

if False:
    # turn into contrast
    for i in range(size):
        mx = max(src[i], max(src[j] for j in iter_neighbours(i)))
        mn = min(src[i], min(src[j] for j in iter_neighbours(i)))
        dest[i] = int((0.5 * src[i]) + (128 * (1 - float(src[i] - mn) / max(1, mx - mn))))
    src, dest = dest, bytearray(size)

try:
    checked, bad, score_cache = set(), set(), {}
    next = sorted((calc_score(i, True), i) for i in range(size))
    while next:
        best, best_score = None, sys.maxint
        current, next = next, []
        for at, (score, i) in enumerate(current):
            if score > cutoff:
                break
            if best and best_score < score:
                break
            if not dest[i] and not count_alive(dest, i):
                do_nothing_score = calc_score(i, False)
                clean = True
                for y in range(-max_shape_y-1, max_shape_y+2):
                    for x in range(-max_shape_x-1, max_shape_x+2):
                        if dest[torus(i, y*w+x)]:
                            clean = False
                            break
                    if not clean:
                        break
                any_ok = False
                for (X, Y), shape, mask, label in shapes:
                    for y in range(Y):
                        for x in range(X):
                            if mask[y][x]:
                                pos, ok = torus(i, -y*w-x), True
                                if (pos, label) in bad:
                                    continue
                                if clean and (pos, label) in score_cache:
                                    score = score_cache[pos, label]
                                else:
                                    paint = torus(pos, *shape)
                                    for j in paint:
                                        for k in iter_alive(dest, j, *paint):
                                            if count_alive(dest, k, *paint) not in (2, 3):
                                                ok = False
                                                break
                                        if not ok:
                                            break
                                        for k in iter_dead(dest, j, *paint):
                                            if count_alive(dest, k, *paint) == 3:
                                                ok = False
                                                break
                                        if not ok:
                                            break
                                    if ok:
                                        score = 0
                                        any_ok = True
                                        for x in range(X):
                                            for y in range(Y):
                                                score += calc_score(torus(pos, y*w+x), mask[y][x])
                                            score /= Y*X
                                        if clean:
                                            score_cache[pos, label] = score
                                    else:
                                        bad.add((pos, label))
                                if ok and best_score > score and do_nothing_score > score:
                                    best, best_score = (pos, shape, label), score
                if any_ok:
                    next.append((score, i))
        if best:
            pos, shape, label = best
            shape = torus(pos, *shape)
            sys.stdout.write(label)
            sys.stdout.flush()
            for j in shape:
                dest[j] = True
            check(dest)
            next += current[at+1:]
        else:
            break
except KeyboardInterrupt:
    pass
print

if True:
    check(dest)
    anim = False
    while dest != src:
        if anim:
            raise Exception("animation!")
        else:
            anim = True
        sys.stdout.write("x"); sys.stdout.flush()
        conway(dest, src)
        dest, src = src, dest
        check(dest)

# canvas
out = Image.new("1", (w, h))
out.putdata([not i for i in dest])

# tk UI
Tkinter = None
try:
    import Tkinter
    from PIL import ImageTk
    root = Tkinter.Tk()
    root.bind("<Button>", lambda event: event.widget.quit())
    root.geometry("%dx%d" % (w, h))
    show = ImageTk.PhotoImage(out)
    label = Tkinter.Label(root, image=show)
    label.pack()
    root.loop()
except Exception as e:
    print "(no Tkinter)", e
    Tkinter = False

if len(sys.argv) > 3:
    out.save(sys.argv[3])

if not Tkinter:
    out.show()

Proszę zezować:

Kod stempluje najbielsze piksele najlepiej dopasowaną standardową martwą naturą . Istnieje argument odcięcia, więc możesz zdecydować, czy dojdzie do zaokrąglenia do progu czarno-białego. Eksperymentowałem z „żywą bielą”, a wynik jest taki sam.

Jawa

Podejście oparte na wykrywaniu krawędzi. Wymaga tego pliku tekstowego w uruchomionym katalogu.

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.*;

import javax.imageio.ImageIO;


public class StillLifer{
    private static List<boolean[][]>patterns=new ArrayList<>();
    private static boolean[][] copy(boolean[][]b,int x,int y){
        boolean[][]r=new boolean[6][6];
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                r[i][j]=b[y+i][x+j];
            }
        }
        return r;
    }
    private static void paste(boolean[][]from,boolean[][]to,int x,int y){
        for(int i=0;i<from.length;i++)for(int j=0;j<from[0].length;j++){
            to[y+i][x+j]=from[i][j];
        }
    }
    private static boolean[][]findClosest(boolean[][]b){
        boolean[][]c=null;
        int d=999999;
        for(boolean[][]k:patterns){
            int d2=editDistance(b,k);
            if(d2<d){
                c=k;
                d=d2;
            }
        }
        return c;
    }
    private static boolean[][]decode(String s){
        char[]a=s.toCharArray();
        boolean[][]r=new boolean[6][6];
        int k=0;
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                r[i][j]=a[k++]=='1';
            }
        }
        return r;
    }
    private static class EdgeDetectEntry{
        int l;
        int x;
        int y;
        public EdgeDetectEntry(int m,int x,int y){
            this.l=m;
            this.x=x;
            this.y=y;
        }
    }
    private static Random rand;
    private static int w,h;
    private static BufferedImage img;
    private static boolean[][]grid;
    private static File file;
    private static int editDistance(boolean[][]from,boolean[][]to){
        int w=from.length;
        int h=from[0].length;
        int k=0;
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
                k+=from[y][x]^to[y][x]?1:0;
            }
        }
        return k;
    }
    private static int colorDistance(Color from,Color to){
        return from.getRed()-to.getRed();
    }
    private static int edgeDetectWeight(int x,int y){
        int k=0;
        Color c=new Color(img.getRGB(x, y));
        for(int x2=Math.max(0,x-1);x2<Math.min(w,x+2);x2++){
            for(int y2=Math.max(0,y-1);y2<Math.min(h,y+2);y2++){
                int l=colorDistance(c,new Color(img.getRGB(x2, y2)));
                k+=l*l;
            }
        }
        return k;
    }
    private static void save() throws Exception{
        int bk=Color.BLACK.getRGB();
        int wt=Color.WHITE.getRGB();
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
                img.setRGB(x,y,grid[y][x]?wt:bk);
            }
        }
        String k=file.getName().split("\\.")[0];
        ImageIO.write(img,"png",new File(k="out_"+k+".png"));
    }
    private static String rle(boolean[][]grid){
        StringBuilder st=new StringBuilder();
        for(boolean[]row:grid){
            for(int j=0;j<row.length;j++){
                int k=1;
                for(;j<row.length-1&&row[j]==row[j+1];j++)k++;
                if(k!=1)st.append(Integer.toString(k,36));
                st.append(row[j]?'@':'-');
            }
        }
        return st.toString();
    }
    private static int getVal(boolean[][]grid,int x,int y){
        if(x<0)x+=w;
        if(y<0)y+=h;
        if(x==w)x=0;
        if(y==h)y=0;
        return grid[y][x]?1:0;
    }
    private static boolean newState(boolean[][]grid,int x,int y,String rule){
        String[]r=rule.split("/");
        int k=0;
        for(int a=-1;a<=1;a++)for(int b=-1;a<=1;a++)k+=(a|b)==0?0:getVal(grid,x+a,y+b);
        String s=Integer.toString(k);
        return grid[y][x]?r[1].contains(s):r[0].contains(s);
    }
    private static boolean[][] next(boolean[][]grid,String rule){
        boolean[][]r=new boolean[h][w];
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
                r[y][x]=newState(grid,x,y,rule);
            }
        }
        return r;
    }
    private static void loadPatterns() throws Exception{
        Scanner reader=new Scanner(new File("lib.txt"));
        while(reader.hasNext()){
            String line=reader.nextLine();
            if(line.startsWith("--"))continue;
            patterns.add(decode(line));
        }
        reader.close();
    }
    public static void main(String[]a) throws Exception{
        loadPatterns();
        Scanner in=new Scanner(System.in);
        img=ImageIO.read(file=new File(in.nextLine()));
        in.close();
        w=img.getWidth();
        h=img.getHeight();
        grid=new boolean[h][w];
        final int npix=w*h;
        rand=new Random(npix*(long)img.hashCode());
        List<EdgeDetectEntry> list=new ArrayList<>();
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
                list.add(new EdgeDetectEntry(edgeDetectWeight(x,y),x,y));
            }
        }
        list.sort((one,two)->{int k=two.l-one.l;if(k>0)return 1;if(k<0)return -1;return 0;});
        for(int i=Math.max(Math.min(3,npix),npix/5);i>0;i--){
            EdgeDetectEntry e=list.get(i);
            grid[e.y][e.x]=rand.nextDouble()<0.9;
        }
        grid=next(grid,"/2345678");
        boolean[][]d=new boolean[h][w];
        for(int i=0;i<w/6;i++){
            for(int j=0;j<h/6;j++){
                paste(findClosest(copy(grid,i*6,j*6)),d,i*6,j*6);
            }
        }
        grid=d;
        assert(rle(next(grid,"3/23")).equals(rle(grid)));
        save();
    }
}

Niektóre wyniki:

C ++

Proste pikselowanie z wykorzystaniem średniej z każdej siatki 8x8 w celu wybrania siatki wyjściowej 8x8 („tekstury kolorów”). Każda siatka wyjściowa 8x8 ma separator 2-komorowy u góry i po prawej stronie. Siatki zostały zaprojektowane od 4 martwych komórek do 18 martwych komórek w pozostałych 6x6 pikselach.

Program działa jak filtr od binarnego PGM do binarnego PBM. Domyślnie obrazy są „ciemne”; czerń to śmierć, a biel to życie; -iodwraca to. -g [value]dodaje gamma, która jest używana do zważenia średnich przed wybraniem tekstur kolorów.

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>

// colors 4 through 18 have 4 through 18 live cells
// colors 1-3 are repetitions of 0 or 4 used
// as artificially weighted bins
unsigned char gol_colors[]={
      0,  0,  0,  0,  0,  0,  0,  0 // Color  0
   ,  0,  0,  0,  0,  0,  0,  0,  0 // Color  1
   ,  0,  0,  0, 16, 40, 16,  0,  0 // Color  2
   ,  0,  0,  0, 16, 40, 16,  0,  0 // Color  3
   ,  0,  0,  0, 16, 40, 16,  0,  0 // Color  4
   ,  0,  0,  0, 24, 40, 16,  0,  0 // Color  5
   ,  0,  0,  0, 16, 40, 80, 32,  0 // Color  6
   ,  0,  0,  0, 48, 72, 40, 16,  0 // Color  7
   ,  0,  0,  8, 20,  8, 64,160, 64 // Color  8
   ,  0,  0,  8, 20,  8, 64,160, 96 // Color  9
   ,  0,  0, 12, 20,  8, 64,160, 96 // Color 10
   ,  0,  0, 12, 20,  8,192,160, 96 // Color 11
   ,  0,  0,204,204,  0,  0, 48, 48 // Color 12
   ,  0,  0,204,204,  0,192,160, 64 // Color 13
   ,  0,  0,  0,108,168,168,108,  0 // Color 14
   ,  0,  0, 96,144,104, 40,172,192 // Color 15
   ,  0,  0,204,204,  0,  0,204,204 // Color 16
   ,  0,  0,216,216,  0,216,212,  8 // Color 17
   ,  0,  0,204,164, 40, 80,148,204 // Color 18
};

enum { gol_bins = sizeof(gol_colors)/(sizeof(*gol_colors))/8 };

bool inverted=false;

bool applygamma=false;
double gammasetting=0.0;

unsigned int corrected(unsigned int i, unsigned int r) {
   return static_cast<unsigned int>(r*std::pow(i/static_cast<double>(r), gammasetting));
}

int main(int argc, char** argv) {
   std::vector<unsigned short> pgm_data;
   unsigned pgm_width;
   unsigned pgm_height;
   unsigned pgm_vpp;

   std::vector<unsigned char> pbm_data;
   unsigned pbm_width;
   unsigned pbm_height;

   unsigned int doublings=0;

   std::vector<std::string> args(argv+1, argv+argc);
   for (unsigned int i=0, e=args.size(); i<e; ++i) {
      if (args[i]=="-i") { inverted=true; continue; }
      if (args[i]=="-g") {
         if (i+1==e) continue;
         std::stringstream ss;
         ss << args[++i];
         if (ss >> gammasetting) applygamma = true;
         continue;
      }
   }

   std::string line;
   std::getline(std::cin, line);
   if (line!="P5") return 1;
   enum { nothing, have_w, have_h, have_bpp } readstate = nothing;
   while (std::cin) {
      std::getline(std::cin, line);
      if (line.empty()) continue;
      if (line[0]=='#') continue;
      std::stringstream ss; ss << line;
      for(;;) {
         switch (readstate) {
         case nothing: if (ss >> pgm_width) readstate = have_w; break;
         case have_w:  if (ss >> pgm_height) readstate = have_h; break;
         case have_h:  if (ss >> pgm_vpp) readstate = have_bpp; break;
         }
         if (readstate==have_bpp) break;
         if (ss) continue;
         break;
      }
      if (readstate==have_bpp) break;
   }
   if (readstate!=have_bpp) return 1;
   // Fill pgm data
   pgm_data.resize(pgm_width*pgm_height);
   for (unsigned i=0, e=pgm_width*pgm_height; i<e; ++i) {
      int v = std::cin.get();
      if (v==std::char_traits<char>::eof()) return 1;
      pgm_data[i] = static_cast<unsigned int>(std::char_traits<char>::to_char_type(v))&0xFFU;
   }
   pbm_width  = pgm_width/8*8;
   pbm_height = pgm_height/8*8;
   pbm_data.resize(pbm_width*pbm_height/8);
   for (unsigned x=0, xe=pbm_width/8; x<xe; ++x) {
      for (unsigned y=0, ye=pbm_height/8; y<ye; ++y) {
         // Calculate the average of this 8x8 area
         unsigned int total=0;
         for (unsigned int xd=0; xd<8; ++xd) {
            for (unsigned int yd=0; yd<8; ++yd) {
               unsigned int c = x+xd+(y+yd)*pgm_width;
               unsigned int pv = pgm_data[x*8+xd+(y*8+yd)*pgm_width];
               // Apply gamma prior to averaging
               if (applygamma) pv=corrected(pv, pgm_vpp);
               total += pv;
            }
         }
         total /= 64;
         // Invert average if inverting colors (white on black)
         if (inverted) total=pgm_vpp-total;
         total *= gol_bins;
         total /= (pgm_vpp+1);
         // Fill 8x8 areas with gol color texture
         for (unsigned int yd=0; yd<8; ++yd) {
            pbm_data[x+(y*8+yd)*pbm_width/8] = gol_colors[total*8+yd];
         }
      }
   }
   // Now, write a pbm
   std::cout
      << "P4\n"
      << "# generated by pgm2gol\n"
      << pbm_width << " " << pbm_height << "\n";
   for (unsigned i=0, e=pbm_data.size(); i<e; ++i) {
      unsigned char data=pbm_data[i];
      if (!inverted) { data=pbm_data[i]^0xFF; }
      std::cout.put(data);
   }
}

Wybrane wyniki (uwaga: wszystkie PBM zostały przekonwertowane na PNG przy użyciu programu zewnętrznego do przesyłania):

Escher, gamma 2.2

Mona Lisa, gamma 2.2

Ocean, odwrócona gamma 2.2

Szczeniak, gamma 2.2

Zdrada obrazów, odwrócona gamma 2.2

Dla porównania Mona Lisa gamma 2.2, odwrócona