Ein Nonogramm ist ein japanisches Puzzlespiel, bei dem das Ziel darin besteht, ein Schwarzweißbild anhand einer Liste zusammenhängender Regionen zu zeichnen.

Definieren Sie die nicht- grafische Größe einer Zeile oder Spalte als die Anzahl der zusammenhängenden schwarzen Bereiche in dieser Zeile oder Spalte. Zum Beispiel hat die oberste Reihe eine nichtografische Größe von 1, da sich in dieser Reihe ein Bereich von 2 Quadraten befindet. Die achte Reihe hat eine nichtografische Größe von 3, weil sie 2, 2, 1 hat.

Eine leere Zeile oder Spalte hat eine nichtografische Größe von 0.

Ihre Aufgabe ist es, ein Programm zu schreiben, das ein Lösungsraster für ein Nonogramm verwendet und ein Lösungsraster mit möglichst wenigen ausgefüllten Quadraten erstellt wobei jede Zeile und Spalte das gleiche nichtografische Magnutid wie das angegebene Lösungsraster hat.

Ein Nonogramm-Raster mit allen ausgefüllten Quadraten hat beispielsweise in jeder Zeile oder Spalte eine nicht-grafische Größe von 1:

Die gleiche nicht-grafische Größe könnte erreicht werden, wenn nur ein diagonaler Streifen durch das Raster gezogen wird, wodurch die Anzahl der ausgefüllten Quadrate drastisch verringert wird:

Ihr Programm erhält eine Eingabe aus 50.000 Zeilen aus dieser Datei (1,32 MB tar.gz-Textdatei; 2,15 MB entpackt), die jeweils ein einzelnes 16 × 16-Nonogramm-Lösungsraster mit zufällig (80% schwarz) ausgefüllten Quadraten darstellt Geben Sie weitere 50.000 Zeilen aus, die jeweils das optimierte Lösungsraster für das entsprechende Eingaberaster enthalten.

Jedes Raster wird als base64-Zeichenfolge mit 43 Zeichen dargestellt (wobei die Quadrate von links nach rechts und dann von oben nach unten codiert werden), und Ihr Programm muss die Ausgabe im gleichen Format zurückgeben. Das erste Raster in der Datei lautet beispielsweise E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=und wird wie folgt dargestellt :

Das Raster beginnt mit Eder Zuordnung zu 000100, sodass die ersten sechs Zellen in der oberen Reihe bis auf die vierte weiß sind. Das nächste Zeichen ist /das 111111, dem es zugeordnet ist. Die nächsten 6 Zellen sind also alle schwarz - und so weiter.

Ihr Programm muss für jeden der 50.000 Testfälle ein Lösungsraster mit den korrekten nichtografischen Größen zurückgeben. Es ist zulässig, dasselbe Raster wie die Eingabe zurückzugeben, wenn nichts Besseres gefunden wurde.

Das Programm, das die wenigsten vollständig ausgefüllten Felder (in jeder Sprache) zurückgibt, ist der Gewinner, wobei der kürzere Code der Tiebreaker ist.

Aktueller Anzeiger:

1. 3,637,260 - Sleafar, Java
2. 7.270.894 - Flawr, Matlab
3. 10.239.288 - Joe Z., Bash

Python 2 & PuLP - 2.644.688 Quadrate (optimal minimiert); 10.753.553 Quadrate (optimal maximiert)

Minimal auf 1152 Bytes golfen

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

(Hinweis: Die stark eingerückten Zeilen beginnen mit Tabulatoren und nicht mit Leerzeichen.)

Beispielausgabe: https://drive.google.com/file/d/0B-0NVE9E8UJiX3IyQkJZVk82Vkk/view?usp=sharing

Es stellt sich heraus, dass Probleme wie zum Beispiel leicht in ganzzahlige lineare Programme konvertierbar sind, und ich brauchte ein grundlegendes Problem, um zu lernen, wie man PuLP - eine Python-Schnittstelle für eine Vielzahl von LP-Solvern - für ein eigenes Projekt verwendet. Es stellt sich auch heraus, dass PuLP extrem einfach zu bedienen ist und der ungolfed LP-Builder beim ersten Versuch einwandfrei funktioniert hat.

Die zwei schönen Dinge beim Einsatz eines Branch-and-Bound-IP-Solvers, um die harte Arbeit zu erledigen, die ich für dieses Problem geleistet habe (abgesehen davon, dass ich keinen Branch-and-Bound-Solver implementieren muss), sind die folgenden

• Speziell entwickelte Löser sind sehr schnell. Dieses Programm löst alle 50000 Probleme in ungefähr 17 Stunden auf meinem relativ einfachen Heim-PC. Für die Lösung jeder Instanz wurden 1-1,5 Sekunden benötigt.
• Sie produzieren garantiert optimale Lösungen (oder teilen Ihnen mit, dass sie dies nicht getan haben). So kann ich sicher sein, dass niemand meine Punktzahl in Quadraten schlagen wird (obwohl es jemand binden und mich auf dem Golf-Teil schlagen könnte).

Wie man dieses Programm benutzt

Zunächst müssen Sie PuLP installieren. pip install pulpsollte den Trick machen, wenn Sie Pip installiert haben.

Dann müssen Sie Folgendes in eine Datei mit dem Namen "c" einfügen: einfügen https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

Führen Sie dieses Programm dann in einem beliebigen späten Python 2-Build aus demselben Verzeichnis aus. In weniger als einem Tag haben Sie eine Datei mit dem Namen "s", die 50.000 gelöste Nonogramm-Gitter (in lesbarem Format) mit der Gesamtzahl der darunter aufgeführten ausgefüllten Quadrate enthält.

Wenn Sie stattdessen die Anzahl der ausgefüllten Felder maximieren möchten, ändern Sie die LpMinimizeOption in Zeile 8 in LpMaximize. Sie erhalten eine sehr ähnliche Ausgabe: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing

Eingabeformat

Dieses Programm verwendet ein modifiziertes Eingabeformat, da Joe Z. angab, dass wir das Eingabeformat neu codieren dürfen, wenn wir dies in einem Kommentar zum OP wünschen. Klicken Sie auf den Link oben, um zu sehen, wie es aussieht. Es besteht aus 10000 Zeilen mit jeweils 16 Ziffern. Die geradzahligen Linien sind die Beträge für die Zeilen einer bestimmten Instanz, während die ungeradzahligen Linien die Beträge für die Spalten derselben Instanz wie die darüber liegende Zeile sind. Diese Datei wurde vom folgenden Programm generiert:

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

(Dieses Programm zur Neucodierung gab mir außerdem die Möglichkeit, meine benutzerdefinierte BitQueue-Klasse zu testen, die ich für dasselbe oben erwähnte Projekt erstellt habe. Es handelt sich lediglich um eine Warteschlange, in die Daten als Folgen von Bits ODER Bytes übertragen werden können und aus der Daten stammen können entweder ein bisschen oder ein Byte auf einmal gepoppt werden. In diesem Fall hat es perfekt funktioniert.)

Ich habe die Eingabe aus dem speziellen Grund neu codiert, dass zum Erstellen eines ILP die zusätzlichen Informationen zu den Gittern, die zum Generieren der Größen verwendet wurden, vollkommen unbrauchbar sind. Die Größen sind die einzigen Einschränkungen, und deshalb brauche ich nur Zugriff auf die Größen.

Ungolfed ILP-Erbauer

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

Dies ist das Programm, das tatsächlich die oben verlinkte "Beispielausgabe" erzeugt hat. Daher die extra langen Saiten am Ende jedes Gitters, die ich beim Golfen abgeschnitten habe. (Die Golfversion sollte eine identische Ausgabe ohne die Wörter produzieren "Filled squares for ")

Wie es funktioniert

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)

Ich verwende ein 18x18-Raster, wobei der mittlere 16x16-Teil die eigentliche Rätsellösung ist. cellsist dieses Gitter. In der ersten Zeile werden 324 Binärvariablen erstellt: "cell_0_0", "cell_0_1" usw. Ich erstelle auch Gitter der "Räume" zwischen und um die Zellen im Lösungsteil des Gitters. rowsepsVerweist auf die 289 Variablen, die die Räume symbolisieren, die Zellen horizontal trennen, und colsepsauf Variablen, die die Räume markieren, die Zellen vertikal trennen. Hier ist ein Unicode-Diagramm:

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

Das 0s und □s sind die von den cellVariablen verfolgten Binärwerte , das |s sind die von den rowsepVariablen verfolgten Binärwerte und das -s sind die von den colsepVariablen verfolgten Binärwerte .

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

Dies ist die Zielfunktion. Nur die Summe aller cellVariablen. Da es sich um binäre Variablen handelt, entspricht dies genau der Anzahl der ausgefüllten Quadrate in der Lösung.

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

Dadurch werden die Zellen um den äußeren Rand des Gitters auf Null gesetzt (weshalb ich sie oben als Nullen dargestellt habe). Dies ist die zweckmäßigste Methode, um zu verfolgen, wie viele "Zellenblöcke" gefüllt sind, da so sichergestellt wird, dass jeder Wechsel von ungefüllt zu gefüllt (über eine Spalte oder Zeile) mit einem entsprechenden Wechsel von gefüllt zu ungefüllt (und umgekehrt) übereinstimmt ), auch wenn die erste oder letzte Zelle in der Zeile gefüllt ist. Dies ist der einzige Grund für die Verwendung eines 18x18-Rasters. Es ist nicht die einzige Möglichkeit, Blöcke zu zählen, aber ich denke, es ist die einfachste.

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

Dies ist das eigentliche Fleisch der Logik der ILP. Grundsätzlich ist es erforderlich, dass jede Zelle (mit Ausnahme der Zelle in der ersten Zeile und Spalte) das logische xor der Zelle und des Trennzeichens direkt links in der Zeile und direkt darüber in der Spalte ist. Ich habe die Einschränkungen, die ein xor innerhalb eines {0,1} Integer-Programms simulieren, aus dieser wunderbaren Antwort erhalten: /cs//a/12118/44289

Um ein bisschen mehr zu erklären: Diese xor-Einschränkung bewirkt, dass die Trennzeichen genau dann 1 sein können, wenn sie zwischen den Zellen 0 und 1 liegen (ein Wechsel von ungefüllt zu gefüllt oder umgekehrt). Somit gibt es in einer Zeile oder Spalte genau doppelt so viele einwertige Trennzeichen wie die Anzahl der Blöcke in dieser Zeile oder Spalte. Mit anderen Worten, die Summe der Trennzeichen in einer bestimmten Zeile oder Spalte ist genau doppelt so groß wie diese Zeile / Spalte. Daher die folgenden Einschränkungen:

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

Und das war's auch schon. Der Rest fordert den Standardlöser lediglich auf, das ILP zu lösen, und formatiert dann die resultierende Lösung, während sie in die Datei geschrieben wird.

Java, 6.093.092 4.332.656 3.637.260 Quadrate (minimiert), 10.567.550 10.567.691 10.568.746 Quadrate (maximiert)

Beide Varianten des Programms führen wiederholt Operationen am Quellgitter durch, ohne die Größe zu ändern.

Minimizer

schrumpfen()

Wenn ein schwarzes Quadrat 2 weiße Nachbarn und 2 schwarze Nachbarn in einem Winkel von 90 ° hat, kann es durch ein weißes Quadrat ersetzt werden.

moveLine ()

In Konfigurationen wie oben kann die schwarze Linie nach rechts verschoben werden. Dies geschieht wiederholt für alle 4 Linienrichtungen im und gegen den Uhrzeigersinn, um neue Schrumpfmöglichkeiten zu eröffnen.

Maximizer

Kommentieren Sie die Zeile aus main()und kommentieren Sie sie für diese Version aus.

wachsen()

Wenn ein weißes Quadrat 2 weiße Nachbarn und 2 schwarze Nachbarn in einem Winkel von 90 ° hat, kann es durch ein schwarzes Quadrat ersetzt werden.

moveLine ()

Gleich wie im Minimizer.

Quelle

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 Quadrate

Als letzte Referenzlösung:

cp nonograms_b64.txt solutions_b64.txt

Da Ihr Programm das gleiche Raster zurückgeben darf, wenn es keine bessere Lösung findet, ist es auch gültig, die gesamte Datei wörtlich auszudrucken.

Die Testdatei enthält insgesamt 10.239.288 schwarze Quadrate, was ziemlich nahe an den 10.240.000 liegt, die Sie von 80% der Quadrate erwarten, die in 50.000 Gittern mit jeweils 256 Quadraten ausgefüllt sind. Wie bei meinen Fragen zu Testbatterien üblich, habe ich die Anzahl der Testfälle mit der Erwartung ausgewählt, dass die optimalen Ergebnisse bei etwa 2 Millionen liegen, obwohl ich vermute, dass die Ergebnisse diesmal eher bei 4 oder 5 Millionen liegen werden .

Wenn jemand eine Lösung schaffen kann, die die schwarzen Quadrate maximiert, anstatt sie zu minimieren, und es schafft, über 10.240.000 zu erreichen, könnte ich in Betracht ziehen, ihr ein Kopfgeld zu geben.

Matlab, 7.270.894 Quadrate (~ 71% des Originals)

Idee ist eine einfache wiederholte gierige Suche: Versuchen Sie für jedes schwarze Quadrat, es auf Weiß zu setzen, ohne die nicht-grafischen Größen zu ändern. Wiederholen Sie dies zweimal. (Mit mehr Wiederholungen könnte man weitaus bessere Ergebnisse erzielen, aber nicht kostenlos: Das führt zu einer entsprechend längeren Laufzeit. Jetzt waren es ca. 80 Minuten. Ich würde das tun, wenn wir nicht alle 50k-Testfälle berechnen müssten ...)

Hier der Code (jede Funktion wie gewohnt in einer eigenen Datei.)

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