Nonogram adalah gim puzzle Jepang yang tujuannya adalah untuk menggambar hitam putih sesuai daftar wilayah yang berdekatan, seperti:

Tentukan besaran nonografis dari baris atau kolom menjadi jumlah wilayah hitam yang berdekatan di baris atau kolom itu. Misalnya, baris atas memiliki besaran nonografis 1, karena ada satu wilayah 2 kotak di baris itu. Baris ke-8 memiliki besaran nonografis 3 karena memiliki 2, 2, 1.

Baris atau kolom kosong memiliki besaran nonografis 0.

Tugas Anda adalah menulis sebuah program yang mengambil kisi solusi untuk nonogram, dan menghasilkan kisi solusi dengan sesedikit mungkin kuadrat yang diisi di mana setiap baris dan kolom memiliki magnutide nonografis yang sama dengan kisi solusi yang diberikan.

Misalnya, kisi nonogram dengan semua kuadrat yang diisi memiliki besaran nonografis 1 pada setiap baris atau kolom:

Besaran nonografis yang sama dapat dicapai hanya dengan memiliki garis diagonal melalui grid, mengurangi jumlah kotak yang diisi secara dramatis:

Program Anda akan menerima input yang terdiri dari 50.000 baris dari file ini ( file teks tar.gz 1,32 MB; 2,15 MB membuka ritsleting), masing-masing mewakili kisi solusi nonogram 16 × 16 tunggal dengan kuadrat yang diisi secara acak (80% hitam), dan mengeluarkan 50.000 baris lagi, masing-masing berisi kisi solusi yang dioptimalkan untuk kisi input yang sesuai.

Setiap kisi direpresentasikan sebagai string base64 dengan 43 karakter (kotak pengkodean dari kiri ke kanan, lalu atas ke bawah), dan program Anda harus mengembalikan hasilnya dalam format yang sama. Misalnya, kotak pertama dalam file adalah E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=, dan dirender sebagai:

Kotak dimulai dengan Epeta mana 000100, jadi enam sel pertama di baris atas semuanya putih kecuali yang keempat. Karakter selanjutnya adalah /yang dipetakan 111111, jadi 6 sel berikutnya semuanya hitam - dan seterusnya.

Program Anda harus benar-benar mengembalikan kisi solusi dengan besaran nonografis yang benar untuk masing-masing 50.000 kasus uji. Diperbolehkan mengembalikan kisi yang sama dengan input jika tidak ada yang lebih baik ditemukan.

Program untuk mengembalikan kuadrat terisi total paling sedikit (dalam bahasa apa pun) adalah pemenangnya, dengan kode yang lebih pendek menjadi tiebreak.

Papan skor saat ini:

1. 3.637.260 - Sleafar, Jawa
2. 7.270.894 - flawr, Matlab
3. 10.239.288 - Joe Z., Bash

Python 2 & PuLP - 2.644.688 kotak (diminimalkan secara optimal); 10.753.553 kotak (dimaksimalkan secara optimal)

Minimal bermain golf hingga 1152 byte

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

(NB: garis yang indentasi dimulai dengan tab, bukan spasi.)

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

Ternyata masalah seperti mudah dikonversi ke Integer Linear Programme, dan saya membutuhkan masalah dasar untuk belajar bagaimana menggunakan PuLP — antarmuka python untuk berbagai pemecah LP — untuk proyek saya sendiri. Ternyata PuLP juga sangat mudah digunakan, dan pembangun LP yang tidak diserang bekerja dengan sempurna saat pertama kali saya mencobanya.

Dua hal yang baik tentang menggunakan pemecah IP cabang-dan-terikat untuk melakukan kerja keras memecahkan ini untuk saya (selain tidak harus menerapkan pemecah cabang dan terikat) adalah bahwa

• Pemecah yang dibuat khusus sangat cepat. Program ini menyelesaikan semua masalah 50000 dalam waktu sekitar 17 jam pada PC rumahan saya yang relatif rendah. Setiap instance membutuhkan waktu 1-1,5 detik untuk menyelesaikannya.
• Mereka menghasilkan solusi optimal yang dijamin (atau memberi tahu Anda bahwa mereka gagal melakukannya). Dengan demikian, saya dapat yakin bahwa tidak ada yang akan mengalahkan skor saya di kotak (meskipun seseorang mungkin mengikatnya dan mengalahkan saya di bagian golf).

Cara menggunakan program ini

Pertama, Anda harus menginstal PuLP. pip install pulpharus melakukan trik jika Anda telah menginstal pip.

Kemudian, Anda harus meletakkan yang berikut ini dalam file bernama "c": https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

Kemudian, jalankan program ini di Python 2 build apa pun dari direktori yang sama. Dalam waktu kurang dari sehari, Anda akan memiliki file bernama "s" yang berisi 50.000 grid nonogram yang diselesaikan (dalam format yang dapat dibaca), masing-masing dengan jumlah total kotak yang diisi tercantum di bawahnya.

Jika Anda ingin memaksimalkan jumlah kuadrat yang diisi, ganti LpMinimizebaris on ke 8 LpMaximizesebagai gantinya. Anda akan mendapatkan hasil sangat banyak seperti ini: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing

Masukkan format

Program ini menggunakan format input yang dimodifikasi, karena Joe Z. mengatakan bahwa kami akan diizinkan untuk menyandikan ulang format input jika kami suka dalam komentar di OP. Klik tautan di atas untuk melihat seperti apa bentuknya. Ini terdiri dari 10.000 baris, masing-masing berisi 16 angka. Garis bernomor genap adalah magnitudo untuk baris dari instance yang diberikan, sedangkan garis bernomor ganjil adalah magnitudo untuk kolom dengan instance yang sama dengan garis di atasnya. File ini dihasilkan oleh program berikut:

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

(Program pengodean ulang ini juga memberi saya kesempatan ekstra untuk menguji kelas BitQueue kustom yang saya buat untuk proyek yang sama yang disebutkan di atas. Ini hanyalah antrian yang datanya dapat didorong sebagai urutan bit ATAU byte, dan dari mana data dapat muncul sedikit atau byte pada suatu waktu. Dalam hal ini, itu bekerja dengan sempurna.)

Saya mengkodekan ulang input untuk alasan spesifik bahwa untuk membangun ILP, informasi tambahan tentang grid yang digunakan untuk menghasilkan besaran sama sekali tidak berguna. Magnitudo adalah satu-satunya kendala, dan magnitudo itulah yang saya butuhkan untuk mengakses.

Pembangun ILP tak berkerumun

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

Ini adalah program yang benar-benar menghasilkan "contoh keluaran" yang ditautkan di atas. Oleh karena itu string ekstra panjang di ujung setiap kotak, yang saya terpotong saat bermain golf. (Versi golf harus menghasilkan output yang identik, minus kata-kata "Filled squares for ")

Bagaimana itu bekerja

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)

Saya menggunakan kisi 18x18, dengan bagian tengah 16x16 menjadi solusi puzzle yang sebenarnya. cellsapakah kotak ini. Baris pertama menciptakan 324 variabel biner: "cell_0_0", "cell_0_1", dan seterusnya. Saya juga membuat kisi-kisi "ruang" antara dan di sekitar sel di bagian solusi kisi. rowsepsmenunjuk ke 289 variabel yang melambangkan ruang yang memisahkan sel secara horizontal, sementara colsepsjuga menunjuk ke variabel yang menandai ruang yang memisahkan sel secara vertikal. Berikut diagram 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

The 0s dan □s adalah nilai-nilai biner dilacak oleh cellvariabel, yang |s adalah nilai-nilai biner dilacak oleh rowsepvariabel, dan -s adalah nilai-nilai biner dilacak oleh colsepvariabel.

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

Ini adalah fungsi tujuan. Hanya jumlah dari semua cellvariabel. Karena ini adalah variabel biner, ini persis jumlah kuadrat yang diisi dalam solusi.

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

Ini hanya mengatur sel di sekitar tepi luar grid ke nol (itulah sebabnya saya mewakili mereka sebagai nol di atas). Ini adalah cara paling bijaksana untuk melacak berapa banyak "blok" sel yang terisi, karena memastikan bahwa setiap perubahan dari tidak terisi menjadi terisi (bergerak melintasi kolom atau baris) dicocokkan dengan perubahan yang sesuai dari terisi ke tidak terisi (dan sebaliknya ), bahkan jika sel pertama atau terakhir di baris terisi. Ini adalah alasan utama untuk menggunakan kisi 18x18 di tempat pertama. Ini bukan satu-satunya cara untuk menghitung blok, tetapi saya pikir ini adalah yang paling sederhana.

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

Ini adalah daging asli dari logika ILP. Pada dasarnya ia mensyaratkan bahwa setiap sel (selain yang ada di baris dan kolom pertama) menjadi karakter logis dari sel dan pemisah langsung ke kiri di barisnya dan langsung di atasnya dalam kolomnya. Saya mendapat kendala yang mensimulasikan xor dalam program integer {0,1} dari jawaban yang luar biasa ini: /cs//a/12118/44289

Untuk menjelaskan lebih banyak: batasan xor ini membuatnya sehingga separator bisa 1 jika dan hanya jika mereka terletak di antara sel-sel yang 0 dan 1 (menandai perubahan dari tidak terisi menjadi terisi atau sebaliknya). Dengan demikian, akan ada tepat dua kali lebih banyak pemisah bernilai 1 dalam satu baris atau kolom daripada jumlah blok di baris atau kolom itu. Dengan kata lain, jumlah pemisah pada baris atau kolom tertentu persis dua kali lipat besarnya baris / kolom itu. Karenanya kendala berikut:

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

Dan itu sudah cukup. Sisanya hanya meminta solver default untuk menyelesaikan ILP, lalu memformat solusi yang dihasilkan saat ia menulisnya ke file.

Jawa, 6.093.092 4.332.656 3.637 kotak (diminimalkan), 10.567.550 10.567.691 10.568.746 kotak (dimaksimalkan)

Kedua varian program berulang kali melakukan operasi pada kisi sumber, tanpa mengubah besarnya.

Minimizer

menyusut()

Jika kotak hitam memiliki 2 tetangga putih dan 2 tetangga hitam di sudut 90 °, itu bisa diganti dengan kotak putih.

moveLine ()

Dalam konfigurasi seperti di atas, garis hitam dapat dipindahkan ke kanan. Hal ini dilakukan berulang kali untuk semua 4 arah searah jarum jam dan berlawanan arah jarum jam, untuk membuka kemungkinan menyusut baru.

Maximizer

Batalkan komentar pada baris main()dan komentari baris di atas untuk versi ini.

tumbuh()

Jika kotak putih memiliki 2 tetangga putih dan 2 tetangga hitam di sudut 90 °, itu bisa diganti dengan kotak hitam.

moveLine ()

Sama seperti di Minimizer.

Sumber

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 kotak

Sebagai solusi referensi tempat terakhir:

cp nonograms_b64.txt solutions_b64.txt

Karena program Anda diizinkan untuk mengembalikan kotak yang sama jika tidak dapat menemukan solusi yang lebih baik, mencetak seluruh file kata demi kata juga valid.

Ada total 10.239.288 kotak hitam di file tes, yang cukup dekat dengan 10.240.000 yang Anda harapkan dari 80% kotak yang diisi dari 50.000 kotak dengan masing-masing 256 kotak. Seperti biasa dengan pertanyaan baterai tes saya, saya telah memilih jumlah test case dengan harapan bahwa skor optimal akan berada di sekitar kisaran 2-juta, meskipun saya menduga skor akan lebih dekat ke 4 atau 5 juta kali ini di sekitar .

Jika ada yang bisa membuat solusi yang memaksimalkan kotak hitam daripada meminimalkannya dan mengelola untuk mendapatkan lebih dari 10.240.000, saya mungkin mempertimbangkan untuk memberikannya hadiah.

Matlab, 7.270.894 kotak (~ 71% dari aslinya)

Ide adalah pencarian serakah berulang yang sederhana: Untuk setiap kotak hitam, coba jika Anda dapat mengaturnya menjadi putih tanpa mengubah besaran nonografis. Ulangi ini dua kali. (Anda dapat mencapai hasil yang jauh lebih baik dengan lebih banyak pengulangan, tetapi tidak gratis: Ini menghasilkan runtime yang lebih lama. Sekarang ini sekitar 80 menit. Saya akan melakukan itu, jika kita tidak perlu menghitung semua 50k testcases ...)

Berikut kodenya (masing-masing fungsi dalam file terpisah, seperti biasa.)

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