Nonogram to japońska gra logiczna, w której celem jest narysowanie czarno-białego obrazu według listy przyległych regionów, takich jak:

Zdefiniuj nieograficzną wielkość wiersza lub kolumny, aby była liczbą sąsiadujących czarnych obszarów w tym rzędzie lub kolumnie. Na przykład górny rząd ma nieograficzną wielkość 1, ponieważ w tym rzędzie jest jeden obszar 2 kwadratów. Ósmy rząd ma nieograficzną wielkość 3, ponieważ ma 2, 2, 1.

Pusty wiersz lub kolumna ma nieograficzną wielkość 0.

Twoim zadaniem jest napisanie programu, który pobiera siatkę rozwiązania dla nonogramu i tworzy siatkę rozwiązania z jak najmniejszą liczbą wypełnionych kwadratów, w których każdy wiersz i kolumna ma ten sam nonograficzny magnutid jak podana siatka rozwiązania.

Na przykład siatka nonogramowa z wypełnionymi wszystkimi kwadratami ma nieograficzną wielkość 1 w każdym rzędzie lub kolumnie:

Tę samą nieograficzną wielkość można osiągnąć, po prostu ukośnym paskiem przechodzącym przez siatkę, co dramatycznie zmniejsza liczbę wypełnionych kwadratów:

Twój program otrzyma dane wejściowe składające się z 50 000 wierszy z tego pliku (1,32 MB pliku tekstowego tar.gz; 2,15 MB rozpakowanego), z których każdy reprezentuje pojedynczą siatkę rozwiązania 16 x 16 nonogram z losowo (80% czarnymi) wypełnionymi kwadratami, oraz wyprowadza kolejne 50 000 linii, z których każda zawiera zoptymalizowaną siatkę rozwiązań dla odpowiedniej siatki wejściowej.

Każda siatka jest reprezentowana jako ciąg base64 z 43 znakami (kodowanie kwadratów od lewej do prawej, a następnie od góry do dołu), a Twój program będzie musiał zwrócić swój wynik w tym samym formacie. Na przykład pierwsza siatka w pliku to E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=i renderuje jako:

Siatka zaczyna się od Emapowania 000100, więc wszystkie sześć pierwszych komórek w górnym rzędzie są białe, z wyjątkiem czwartej. Następną postacią jest /mapa 111111, na którą kolejne 6 komórek jest czarnych - i tak dalej.

Twój program musi faktycznie zwrócić siatkę rozwiązania o prawidłowej wielkości nieograficznej dla każdego z 50 000 przypadków testowych. Dopuszczalne jest zwrócenie tej samej siatki co danych wejściowych, jeśli nie znaleziono nic lepszego.

Zwycięzcą jest program zwracający najmniejszą liczbę wypełnionych kwadratów (w dowolnym języku), przy czym krótszym kodem jest rozstrzygający.

Aktualna tablica wyników:

1. 3,637,260 - Sleafar, Java
2. 7 270 894 - flawr, Matlab
3. 10 239 288 - Joe Z., Bash

Python 2 i PuLP - 2 644 648 kwadratów (optymalnie zminimalizowane); 10 753 553 kwadraty (optymalnie zmaksymalizowane)

Minimalnie grał w golfa do 1152 bajtów

from pulp import*
x=0
f=open("c","r")
g=open("s","w")
for k,m in enumerate(f):
 if k%2:
    b=map(int,m.split())
    p=LpProblem("Nn",LpMinimize)
    q=map(str,range(18))
    ir=q[1:18]
    e=LpVariable.dicts("c",(q,q),0,1,LpInteger)
    rs=LpVariable.dicts("rs",(ir,ir),0,1,LpInteger)
    cs=LpVariable.dicts("cs",(ir,ir),0,1,LpInteger)
    p+=sum(e[r][c] for r in q for c in q),""
    for i in q:p+=e["0"][i]==0,"";p+=e[i]["0"]==0,"";p+=e["17"][i]==0,"";p+=e[i]["17"]==0,""
    for o in range(289):i=o/17+1;j=o%17+1;si=str(i);sj=str(j);l=e[si][str(j-1)];ls=rs[si][sj];p+=e[si][sj]<=l+ls,"";p+=e[si][sj]>=l-ls,"";p+=e[si][sj]>=ls-l,"";p+=e[si][sj]<=2-ls-l,"";l=e[str(i-1)][sj];ls=cs[si][sj];p+=e[si][sj]<=l+ls,"";p+=e[si][sj]>=l-ls,"";p+=e[si][sj]>=ls-l,"";p+=e[si][sj]<=2-ls-l,""
    for r,z in enumerate(a):p+=lpSum([rs[str(r+1)][c] for c in ir])==2*z,""
    for c,z in enumerate(b):p+=lpSum([cs[r][str(c+1)] for r in ir])==2*z,""
    p.solve()
    for r in ir:
     for c in ir:g.write(str(int(e[r][c].value()))+" ")
     g.write('\n')
    g.write('%d:%d\n\n'%(-~k/2,value(p.objective)))
    x+=value(p.objective)
 else:a=map(int,m.split())
print x

(Uwaga: mocno wcięte linie zaczynają się od tabulatorów, a nie spacji.)

Przykładowe dane wyjściowe: https://drive.google.com/file/d/0B-0NVE9E8UJiX3IyQkJZVk82Vkk/view?usp=sharing

Okazuje się, że takie problemy można łatwo przekształcić w całkowite programy liniowe i potrzebowałem podstawowego problemu, aby nauczyć się korzystać z PuLP - interfejsu python dla różnych programów LP - do własnego projektu. Okazuje się również, że PuLP jest niezwykle łatwy w użyciu, a niegodziwy konstruktor LP działał idealnie przy pierwszym uruchomieniu.

Dwie miłe rzeczy związane z zatrudnieniem rozgałęzionego solwera IP do ciężkiej pracy w rozwiązaniu tego problemu (oprócz konieczności implementacji rozgałęzionego i związanego solwera) to:

• Skonstruowane specjalnie do tego celu solwery są naprawdę szybkie. Ten program rozwiązuje wszystkie 50000 problemów w ciągu około 17 godzin na moim stosunkowo niskim komputerze domowym. Każde wystąpienie zajęło od 1-1,5 sekundy do rozwiązania.
• Tworzą gwarantowane optymalne rozwiązania (lub mówią, że tego nie zrobili). Dlatego mogę być pewien, że nikt nie pokona mojego wyniku w kwadracie (chociaż ktoś może go powiązać i pokonać mnie w części golfowej).

Jak korzystać z tego programu

Najpierw musisz zainstalować PuLP. pip install pulppowinien załatwić sprawę, jeśli masz zainstalowany pip.

Następnie musisz umieścić w pliku o nazwie „c”: https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

Następnie uruchom ten program w dowolnej późniejszej wersji Pythona 2 z tego samego katalogu. W niecały dzień otrzymasz plik o nazwie „s”, który zawiera 50 000 rozwiązanych nieogramowych siatek (w czytelnym formacie), z których każda zawiera podaną liczbę wypełnionych kwadratów.

Jeśli zamiast tego chcesz zmaksymalizować liczbę wypełnionych kwadratów, zmień LpMinimizelinię 8 na LpMaximizezamiast. Otrzymasz wynik bardzo podobny do tego: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing

Format wejściowy

Ten program używa zmodyfikowanego formatu wejściowego, ponieważ Joe Z. powiedział, że będziemy mogli ponownie zakodować format wejściowy, jeśli chcemy w komentarzu do OP. Kliknij powyższy link, aby zobaczyć, jak to wygląda. Składa się z 10000 linii, z których każda zawiera 16 cyfr. Linie parzyste to wielkości wierszy danego wystąpienia, a linie nieparzyste to wielkości kolumn tego samego wystąpienia, co linia nad nimi. Ten plik został wygenerowany przez następujący program:

from bitqueue import *

with open("nonograms_b64.txt","r") as f:
    with open("nonogram_clues.txt","w") as g:
        for line in f:
            q = BitQueue(line.decode('base64'))
            nonogram = []
            for i in range(256):
                if not i%16: row = []
                row.append(q.nextBit())
                if not -~i%16: nonogram.append(row)
            s=""
            for row in nonogram:
                blocks=0                         #magnitude counter
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print >>g, s
            nonogram = map(list, zip(*nonogram)) #transpose the array to make columns rows
            s=""
            for row in nonogram:
                blocks=0
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print >>g, s

(Ten program do ponownego kodowania dał mi również dodatkową okazję do przetestowania mojej niestandardowej klasy BitQueue, którą utworzyłem dla tego samego projektu wspomnianego powyżej. Jest to po prostu kolejka, do której dane mogą być wypychane jako sekwencje bitów LUB bajtów i z których dane mogą może być wyświetlany po jednym bajcie lub bajcie naraz. W tym przypadku działało idealnie).

Ponownie zakodowałem dane wejściowe z konkretnego powodu, że do zbudowania ILP dodatkowe informacje o siatkach, które zostały użyte do wygenerowania wielkości, są całkowicie bezużyteczne. Wielkości są jedynymi ograniczeniami, więc wielkości są wszystkim, do czego potrzebowałem dostępu.

Niegolfowany konstruktor ILP

from pulp import *
total = 0
with open("nonogram_clues.txt","r") as f:
    with open("solutions.txt","w") as g:
        for k,line in enumerate(f):
            if k%2:
                colclues=map(int,line.split())
                prob = LpProblem("Nonogram",LpMinimize)
                seq = map(str,range(18))
                rows = seq
                cols = seq
                irows = seq[1:18]
                icols = seq[1:18]
                cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
                rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
                colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)
                prob += sum(cells[r][c] for r in rows for c in cols),""
                for i in rows:
                    prob += cells["0"][i] == 0,""
                    prob += cells[i]["0"] == 0,""
                    prob += cells["17"][i] == 0,""
                    prob += cells[i]["17"] == 0,""
                for i in range(1,18):
                    for j in range(1,18):
                        si = str(i); sj = str(j)
                        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
                        prob += cells[si][sj] <= l + ls,""
                        prob += cells[si][sj] >= l - ls,""
                        prob += cells[si][sj] >= ls - l,""
                        prob += cells[si][sj] <= 2 - ls - l,""
                        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
                        prob += cells[si][sj] <= l + ls,""
                        prob += cells[si][sj] >= l - ls,""
                        prob += cells[si][sj] >= ls - l,""
                        prob += cells[si][sj] <= 2 - ls - l,""
                for r,clue in enumerate(rowclues):
                    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
                for c,clue in enumerate(colclues):
                    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""
                prob.solve()
                print "Status for problem %d: "%(-~k/2),LpStatus[prob.status]
                for r in rows[1:18]:
                    for c in cols[1:18]:
                        g.write(str(int(cells[r][c].value()))+" ")
                    g.write('\n')
                g.write('Filled squares for %d: %d\n\n'%(-~k/2,value(prob.objective)))
                total += value(prob.objective)
            else:
                rowclues=map(int,line.split())
print "Total number of filled squares: %d"%total

Jest to program, który faktycznie stworzył „przykładowe wyjście” połączone powyżej. Stąd wyjątkowo długie sznurki na końcu każdej siatki, które obciąłem podczas gry w golfa. (Wersja do gry w golfa powinna dawać identyczne wyniki, bez słów "Filled squares for ")

Jak to działa

cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)

Używam siatki 18 x 18, a środkowa część 16 x 16 jest właściwym rozwiązaniem układanki. cellsto ta siatka. Pierwszy wiersz tworzy 324 zmienne binarne: „cell_0_0”, „cell_0_1” i tak dalej. Tworzę również siatki „przestrzeni” pomiędzy i wokół komórek w części rozwiązania siatki. rowsepswskazuje na 289 zmiennych, które symbolizują spacje oddzielające komórki w poziomie, podczas gdy colsepspodobnie wskazuje na zmienne, które oznaczają spacje oddzielające komórki w pionie. Oto schemat Unicode:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - - 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

W 0y i □y to wartości binarne śledzone przez cellzmienne, |a wartości binarne są śledzone przez rowsepwartości zmiennych i -y to wartości binarne śledzone przez colsepzmiennych.

prob += sum(cells[r][c] for r in rows for c in cols),""

To jest funkcja celu. Tylko suma wszystkich cellzmiennych. Ponieważ są to zmienne binarne, jest to dokładnie liczba wypełnionych kwadratów w rozwiązaniu.

for i in rows:
    prob += cells["0"][i] == 0,""
    prob += cells[i]["0"] == 0,""
    prob += cells["17"][i] == 0,""
    prob += cells[i]["17"] == 0,""

To po prostu ustawia komórki wokół zewnętrznej krawędzi siatki na zero (dlatego przedstawiłem je jako zera powyżej). Jest to najbardziej celowy sposób śledzenia liczby „bloków” komórek, które są wypełnione, ponieważ zapewnia, że ​​każdej zmianie z niewypełnionej na wypełnioną (przechodzącej przez kolumnę lub wiersz) odpowiada odpowiednia zmiana z wypełnionej na niewypełnioną (i odwrotnie ), nawet jeśli pierwsza lub ostatnia komórka w wierszu jest wypełniona. Jest to jedyny powód, dla którego warto zastosować siatkę 18x18. To nie jedyny sposób na liczenie bloków, ale myślę, że jest najprostszy.

for i in range(1,18):
    for j in range(1,18):
        si = str(i); sj = str(j)
        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
        prob += cells[si][sj] <= l + ls,""
        prob += cells[si][sj] >= l - ls,""
        prob += cells[si][sj] >= ls - l,""
        prob += cells[si][sj] <= 2 - ls - l,""
        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
        prob += cells[si][sj] <= l + ls,""
        prob += cells[si][sj] >= l - ls,""
        prob += cells[si][sj] >= ls - l,""
        prob += cells[si][sj] <= 2 - ls - l,""

To jest prawdziwe mięso logiki ILP. Zasadniczo wymaga, aby każda komórka (inna niż w pierwszym rzędzie i kolumnie) była logicznym xor komórki i separatora bezpośrednio po lewej stronie w swoim rzędzie i bezpośrednio nad nią w kolumnie. Dostałem ograniczenia, które symulują xor w programie liczb całkowitych {0,1} z tej wspaniałej odpowiedzi: /cs//a/12118/44289

Aby wyjaśnić nieco więcej: to ograniczenie xor sprawia, że ​​separatory mogą mieć wartość 1 wtedy i tylko wtedy, gdy znajdują się między komórkami, które są 0 i 1 (oznaczając zmianę z niewypełnionego na wypełnione lub odwrotnie). Zatem w wierszu lub kolumnie będzie dokładnie dwa razy więcej separatorów 1-wartościowych niż liczba bloków w tym wierszu lub kolumnie. Innymi słowy, suma separatorów w danym rzędzie lub kolumnie jest dokładnie dwa razy większa niż wielkość tego rzędu / kolumny. Stąd następujące ograniczenia:

for r,clue in enumerate(rowclues):
    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
for c,clue in enumerate(colclues):
    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""

I to tyle. Reszta prosi tylko domyślny solver o rozwiązanie ILP, a następnie formatuje powstałe rozwiązanie, zapisując je do pliku.

Java, 6 093 092 4 332 656 3 637 260 kwadratów (zminimalizowane), 10 567 550 10 567 691 10 568 746 kwadratów (zmaksymalizowane)

Oba warianty programu wielokrotnie wykonują operacje na siatce źródłowej, bez zmiany wielkości.

Minimizer

kurczyć się()

Jeśli czarny kwadrat ma 2 białych sąsiadów i 2 czarnych sąsiadów pod kątem 90 °, można go zastąpić białym kwadratem.

moveLine ()

W konfiguracjach takich jak powyżej czarna linia może być przesunięta w prawo. Odbywa się to wielokrotnie dla wszystkich 4 kierunków linii zgodnie z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara, aby otworzyć nowe możliwości kurczenia się.

Maksymalizator

Odkomentuj linię main()i skomentuj linię powyżej tej wersji.

rosnąć()

Jeśli biały kwadrat ma 2 białych sąsiadów i 2 czarnych sąsiadów pod kątem 90 °, można go zastąpić czarnym kwadratem.

moveLine ()

Taki sam jak w Minimizerze.

Źródło

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Arrays;
import java.util.Base64;
import java.util.function.Function;

public class Main {
    private static final int SIZE = 16;
    private static final int SIZE_4 = SIZE + 4;
    private static final int E = 0;
    private static final int N = 1;
    private static final int W = 2;
    private static final int S = 3;

    private static final Base64.Decoder decoder = Base64.getMimeDecoder();
    private static final Base64.Encoder encoder = Base64.getMimeEncoder();
    private static int sourceBlack = 0;
    private static int targetBlack = 0;

    private static class Nonogram {
        private final boolean[] cells = new boolean[SIZE_4 * SIZE_4];
        private final int[] magnitudes;

        public Nonogram(String encoded) {
            super();
            byte[] decoded = decoder.decode(encoded);
            for (int i = 0; i < decoded.length; ++ i) {
                for (int j = 0; j < 8; ++ j) {
                    if ((decoded[i] & (1 << (7 - j))) != 0) {
                        int k = i * 8 + j;
                        cells[getPos(k / SIZE, k % SIZE)] = true;
                        ++ sourceBlack;
                    }
                }
            }
            magnitudes = calcMagnitudes();
        }

        private int getPos(int row, int col) {
            return (row + 2) * SIZE_4 + col + 2;
        }

        private int move(int pos, int dir, int count) {
            switch (dir) {
                case E: return pos + count;
                case N: return pos - count * SIZE_4;
                case W: return pos - count;
                case S: return pos + count * SIZE_4;
                default: return pos;
            }
        }

        private int move(int pos, int dir) {
            return move(pos, dir, 1);
        }

        private int[] calcMagnitudes() {
            int[] result = new int[SIZE * 2];
            for (int row = 0; row < SIZE; ++ row) {
                for (int col = 0; col < SIZE; ++ col) {
                    int pos = getPos(row, col);
                    if (cells[pos]) {
                        if (!cells[move(pos, W)]) {
                            ++ result[row + SIZE];
                        }
                        if (!cells[move(pos, N)]) {
                            ++ result[col];
                        }
                    }
                }
            }
            return result;
        }

        private boolean isBlack(int pos) {
            return cells[pos];
        }

        private boolean isWhite(int pos) {
            return !cells[pos];
        }

        private boolean allBlack(int pos, int dir, int count) {
            int p = pos;
            for (int i = 0; i < count; ++ i) {
                if (isWhite(p)) {
                    return false;
                }
                p = move(p, dir);
            }
            return true;
        }

        private boolean allWhite(int pos, int dir, int count) {
            int p = pos;
            for (int i = 0; i < count; ++ i) {
                if (isBlack(p)) {
                    return false;
                }
                p = move(p, dir);
            }
            return true;
        }

        private int findWhite(int pos, int dir) {
            int count = 0;
            int p = pos;
            while (cells[p]) {
                ++ count;
                p = move(p, dir);
            }
            return count;
        }

        @SafeVarargs
        private final void forEach(Function<Integer, Boolean>... processors) {
            outer:
            for (;;) {
                for (Function<Integer, Boolean> processor : processors) {
                    for (int row = 0; row < SIZE; ++ row) {
                        for (int col = 0; col < SIZE; ++ col) {
                            if (processor.apply(getPos(row, col))) {
                                continue outer;
                            }
                        }
                    }
                }
                return;
            }
        }

        private boolean shrink(int pos) {
            if (cells[pos] && cells[move(pos, W)] != cells[move(pos, E)] &&
                    cells[move(pos, N)] != cells[move(pos, S)]) {
                cells[pos] = false;
                return true;
            }
            return false;
        }

        private boolean grow(int pos) {
            if (!cells[pos] && cells[move(pos, W)] != cells[move(pos, E)] &&
                    cells[move(pos, N)] != cells[move(pos, S)]) {
                cells[pos] = true;
                return true;
            }
            return false;
        }

        private boolean moveLine(boolean clockwise, int dir, int sourcePos) {
            int from = (dir + (clockwise ? 1 : 3)) % 4;
            int to = (dir + (clockwise ? 3 : 1)) % 4;
            int opp = (dir + 2) % 4;
            if (isBlack(sourcePos) && isWhite(move(sourcePos, from)) && isWhite(move(sourcePos, dir))) {
                int toCount = findWhite(move(move(sourcePos, dir), to), to) + 1;
                if (allWhite(move(sourcePos, to), to, toCount + 1)) {
                    int lineCount = 1;
                    int tmpPos = move(sourcePos, opp);
                    while (isBlack(tmpPos) && isWhite(move(tmpPos, from)) && allWhite(move(tmpPos, to),  to, toCount + 1)) {
                        ++ lineCount;
                        tmpPos = move(tmpPos, opp);
                    }
                    if (allBlack(tmpPos, to, toCount + 1)) {
                        tmpPos = sourcePos;
                        for (int j = 0; j < lineCount; ++ j) {
                            cells[tmpPos] = false;
                            cells[move(tmpPos, to, toCount)] = true;
                            tmpPos = move(tmpPos, opp);
                        }
                        return true;
                    }
                }
            }
            return false;
        }

        public Nonogram minimize() {
            for (int i = 0; i < 5; ++ i) {
                forEach(pos -> shrink(pos), pos -> moveLine(true, E, pos), pos -> moveLine(true, N, pos),
                        pos -> moveLine(true, W, pos), pos -> moveLine(true, S, pos));
                forEach(pos -> shrink(pos), pos -> moveLine(false, E, pos), pos -> moveLine(false, N, pos),
                        pos -> moveLine(false, W, pos), pos -> moveLine(false, S, pos));
            }
            return this;
        }

        public Nonogram maximize() {
            for (int i = 0; i < 5; ++ i) {
                forEach(pos -> grow(pos), pos -> moveLine(true, E, pos), pos -> moveLine(true, N, pos),
                        pos -> moveLine(true, W, pos), pos -> moveLine(true, S, pos));
                forEach(pos -> grow(pos), pos -> moveLine(false, E, pos), pos -> moveLine(false, N, pos),
                        pos -> moveLine(false, W, pos), pos -> moveLine(false, S, pos));
            }
            return this;
        }

        public String toBase64() {
            if (!Arrays.equals(magnitudes, calcMagnitudes())) {
                throw new RuntimeException("Something went wrong!");
            }
            byte[] decoded = new byte[SIZE * SIZE / 8];
            for (int i = 0; i < decoded.length; ++ i) {
                for (int j = 0; j < 8; ++ j) {
                    int k = i * 8 + j;
                    if (cells[getPos(k / SIZE, k % SIZE)]) {
                        decoded[i] |= 1 << (7 - j);
                        ++ targetBlack;
                    }
                }
            }
            return encoder.encodeToString(decoded);
        }

        @Override
        public String toString() {
            StringBuilder b = new StringBuilder();
            for (int row = 0; row < SIZE; ++ row) {
                for (int col = 0; col < SIZE; ++ col) {
                    b.append(cells[getPos(row, col)] ? '#' : ' ');
                }
                b.append('\n');
            }
            return b.toString();
        }
    }

    public static void main(String[] args) throws Exception {
        try (BufferedWriter writer = new BufferedWriter(new FileWriter("solutions_b64.txt"));
                BufferedReader reader = new BufferedReader(new FileReader("nonograms_b64.txt"))) {
            String line;
            while ((line = reader.readLine()) != null) {
                writer.write(new Nonogram(line).minimize().toBase64() + "\n");
                //writer.write(new Nonogram(line).maximize().toBase64() + "\n");
            }
        }
        System.out.printf("%d -> %d", sourceBlack, targetBlack);
    }
}

Bash - 10 239 288 kwadratów

Jako rozwiązanie referencyjne na ostatnim miejscu:

cp nonograms_b64.txt solutions_b64.txt

Ponieważ program może zwrócić tę samą siatkę, jeśli nie może znaleźć lepszego rozwiązania, wydrukowanie całego pliku jest również poprawne.

W pliku testowym znajduje się łącznie 10 239 288 czarnych kwadratów, co jest bardzo zbliżone do 10 240 000, których można oczekiwać od 80% kwadratów wypełnionych z 50 000 siatek z 256 kwadratami każdy. Jak zwykle w przypadku pytań dotyczących akumulatora testowego, wybrałem liczbę przypadków testowych z oczekiwaniem, że optymalne wyniki będą w okolicach 2 milionów, chociaż podejrzewam, że tym razem wyniki będą bliższe 4 lub 5 milionów .

Jeśli komuś uda się stworzyć rozwiązanie maksymalizujące czarne kwadraty zamiast je minimalizować i uda się uzyskać ponad 10 240 000, mogę rozważyć przyznanie mu nagrody.

Matlab, 7270894 kwadraty (~ 71% oryginału)

Pomysł jest prostym, powtarzającym się chciwym wyszukiwaniem: dla każdego czarnego kwadratu spróbuj ustawić go na biały bez zmiany wielkości nieograficznych. Powtórz to dwa razy. (Można osiągnąć znacznie lepsze wyniki przy większej liczbie powtórzeń, ale nie za darmo: Daje to odpowiednio dłuższy czas działania. Teraz było to około 80 minut. Zrobiłbym to, gdybyśmy nie musieli obliczać wszystkich 50 000 przypadków testowych ...)

Tutaj kod (jak zwykle każda funkcja w osobnym pliku).

function D = b64decode(E)
% accepts a string of base 64 encoded data, and returns a array of zeros
% and ones
F = E;
assert( mod(numel(E),4)==0 && 0 <= sum(E=='=') && sum(E=='=') <= 2,'flawed base 64 code')

F('A' <= E & E<= 'Z') = F('A' <= E & E<= 'Z') -'A';       %upper case
F('a' <= E & E<= 'z') = F('a' <= E & E<= 'z') -'a' + 26;  %lower case
F('0'<= E & E <= '9') = F('0'<= E & E <= '9') -'0' + 52;  %digits
F( E == '+') = 62;
F( E == '/') = 63;
F( E == '=') = 0;

D=zeros(1,numel(E)*3*8/4);

for k=1:numel(E);
    D(6*(k-1)+1 + (0:5)) = dec2bin(F(k),6)-'0';
end

if E(end) == '=';
    D(end-7:end) = [];
    if E(end-1) == '=';
        D(end-7:end) = [];
    end
end
end

function E = b64encode(D)
assert(mod(numel(D),8)==0,'flawed byte code');
N=0;
while mod(numel(D),6) ~= 0;
    D = [D,zeros(1,8)];
    N = N+1;
end
dict = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';

E=zeros(1,numel(D)/6)+'=';
for k=0:numel(E)-N-1;
    E(k+1) = dict(bin2dec( [D(6*k+(1:6))+'0',''] ) + 1);
end

E = [E,''];
end


function [B,T,O] = reduce_greedy(N)
% reduce greedily
NM = nomographic_magnitude(N);
B = N; %current best
M = N;
T = nnz(N); %current number of filled squares
O = T;

for r=1:2;  %how many repetitions
    I = find(B);
    for k=1:numel(I);
        M = B;
        M( I(k) ) = 0;
        %check whether we have a valid solution
        if all(NM == nomographic_magnitude(M))
            if T > nnz(M); %did we actually reduce the number of filled squares?
                B = M;
                T = nnz(M);
            end
        end
    end
end


%% main file
string_in = fileread('nonograms_b64.txt');
string_out = string_in;
tic
total_new = 0;  %total number of black squares
total_old = 0;
M = 50000;
for k=1:M;
    disp(k/M); %display the progress
    line = string_in(45*(k-1)+(1:44));
    decoded = b64decode(line);        
    nonogram = reshape(decoded,16,[]) ;%store nonogram as a matrix
    [B,T,O] = reduce_greedy(nonogram);
    disp([nnz(B),nnz(nonogram)])
    total_new = total_new + T;
    total_old = total_old + O;
    string_in(45*(k-1)+(1:44)) = b64encode(B(:).');
end
toc
F = fopen('nonograms_b64_out.txt','w');
fprintf(F,string_out);
%%
disp([total_new,total_old])