Нонограмма - это японская игра-головоломка, цель которой - нарисовать черно-белое изображение в соответствии со списком смежных регионов, например:

Определите неографическую величину строки или столбца как число смежных черных областей в этой строке или столбце. Например, верхняя строка имеет неографическую величину 1, потому что в этой строке есть одна область из 2 квадратов. Восьмой ряд имеет неографическую величину 3, потому что он имеет 2, 2, 1.

Пустая строка или столбец имеют неографическую величину 0.

Ваша задача - написать программу, которая принимает сетку решений для неграммы и создает сетку решений с наименьшим количеством заполненных квадратов. меньшим где каждая строка и столбец имеют такой же неографический размер, как и данная сетка решений.

Например, сетка неграммы со всеми заполненными квадратами имеет неографическую величину 1 в каждой строке или столбце:

Та же неографическая величина могла бы быть достигнута, если бы диагональная полоса проходила через сетку, значительно уменьшая количество заполненных квадратов:

Ваша программа получит вход, состоящий из 50000 строк из этого файла (1,32 МБ текстового файла tar.gz; 2,15 МБ разархивированного файла), каждая из которых представляет собой отдельную сетку решения неграммы 16 × 16 со случайно заполненными квадратами (80% черного цвета), и выведите еще 50000 строк, каждая из которых содержит сетку оптимизированного решения для соответствующей входной сетки.

Каждая сетка представлена ​​в виде строки base64 с 43 символами (квадраты кодируются слева направо, затем сверху вниз), и ваша программа должна будет возвращать свои выходные данные в том же формате. Например, первая сетка в файле выглядит E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=так:

Сетка начинается с Eкакой карты 000100, поэтому первые шесть ячеек в верхнем ряду все белые, кроме четвертой. Следующий символ - это то, на /что отображаются 111111следующие 6 ячеек, все черные - и так далее.

Ваша программа должна на самом деле возвращать сетку решений с правильными неографическими значениями для каждого из 50 000 тестовых случаев. Разрешается возвращать ту же сетку, что и входные данные, если ничего лучшего не было найдено.

Программа для возврата наименьшего количества заполненных квадратов (на любом языке) является победителем, с более коротким кодом, являющимся таймбрейкером.

Текущее табло:

1. 3,637,260 - Sleafar, Java
2. 7,270,894 - flawr, Matlab
3. 10,239,288 - Джо З., Баш

Python 2 & PuLP - 2 644 688 квадратов (оптимально минимизированы); 10 753 553 квадрата (оптимально максимизированы)

Минимально гольф до 1152 байтов

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

(Примечание: строки с сильными отступами начинаются с табуляции, а не пробелов.)

Пример вывода: https://drive.google.com/file/d/0B-0NVE9E8UJiX3IyQkJZVk82Vkk/view?usp=sharing

Оказывается, что подобные проблемы легко конвертируются в целочисленные линейные программы, и мне нужна была основная проблема, чтобы научиться использовать PuLP - интерфейс Python для различных программ для решения LP - для моего собственного проекта. Также оказалось, что PuLP чрезвычайно прост в использовании, и неумелый сборщик LP сработал отлично, когда я впервые попробовал его.

Две полезные вещи, связанные с использованием IP-решателя с ветвями и связями для выполнения тяжелой работы по решению этой проблемы для меня (за исключением того, что нет необходимости реализовывать решатель ветвей и границ):

• Специализированные решатели действительно быстрые. Эта программа решает все 50000 проблем за 17 часов на моем относительно недорогом домашнем ПК. Каждый экземпляр занимал от 1 до 1,5 секунд, чтобы решить.
• Они дают гарантированные оптимальные решения (или сообщают вам, что им это не удалось). Таким образом, я могу быть уверен, что никто не побьет мой результат в квадратах (хотя кто-то может связать его и победить меня в игре в гольф).

Как использовать эту программу

Сначала вам нужно установить PuLP. pip install pulpдолжен сделать трюк, если у вас установлен пипс.

Затем вам нужно поместить в файл с именем «c» следующее: https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

Затем запустите эту программу в любой поздней сборке Python 2 из того же каталога. Менее чем через день у вас будет файл с именем «s», содержащий 50 000 решенных неограммных сеток (в читаемом формате), в каждой из которых будет указано общее количество заполненных квадратов.

Если вы хотите максимизировать количество заполненных квадратов вместо этого, измените LpMinimizeна строке 8 LpMaximizeвместо этого. Вы получите очень похожий результат: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing

Формат ввода

Эта программа использует измененный формат ввода, поскольку Джо З. сказал, что нам будет разрешено перекодировать формат ввода, если мы захотим в комментарии к ОП. Нажмите на ссылку выше, чтобы увидеть, как это выглядит. Он состоит из 10000 строк, каждая из которых содержит 16 цифр. Строки с четными номерами - это величины для строк данного экземпляра, а строки с нечетными номерами - это величины для столбцов того же экземпляра, что и линия над ними. Этот файл был сгенерирован следующей программой:

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

(Эта программа перекодирования также дала мне дополнительную возможность протестировать мой собственный класс BitQueue, который я создал для того же проекта, упомянутого выше. Это просто очередь, в которую данные могут передаваться как последовательности битов ИЛИ байтов, и из которых данные могут быть вытолкнутым либо битом, либо байтом за раз. В этом случае это работало отлично.)

Я перекодировал входные данные по той конкретной причине, что для построения ILP дополнительная информация о сетках, которые использовались для генерации величин, совершенно бесполезна. Величины - единственные ограничения, и поэтому величины - это все, к чему мне нужен был доступ.

Ungolfed 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

Это программа, которая фактически создала «пример вывода», связанный выше. Отсюда и очень длинные струны в конце каждой сетки, которые я обрезал при игре в гольф. (Версия для гольфа должна давать идентичный результат, без слов "Filled squares for ")

Как это устроено

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)

Я использую сетку 18x18, с центральной частью 16x16, которая является настоящим решением головоломки. cellsэто сетка. Первая строка создает 324 двоичных переменных: «cell_0_0», «cell_0_1» и т. Д. Я также создаю сетки "пробелов" между и вокруг ячеек в части решения сетки. rowsepsуказывает на 289 переменных, которые символизируют пространства, которые разделяют ячейки по горизонтали, а colsepsтакже указывает на переменные, которые отмечают пространства, которые разделяют ячейки по вертикали. Вот диаграмма 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

В 0ы и □с являются двоичные значения отслеживаемых cellпеременных, то |s являются двоичные значения отслеживали с помощью rowsepпеременных, и -s являются двоичные значения отслеживали с помощью colsepпеременных.

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

Это целевая функция. Просто сумма всех cellпеременных. Поскольку это бинарные переменные, это как раз количество заполненных квадратов в решении.

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

Это просто устанавливает ячейки вокруг внешнего края сетки в ноль (вот почему я представлял их как нули выше). Это наиболее целесообразный способ отследить, сколько «блоков» ячеек заполнено, поскольку он гарантирует, что каждому изменению с незаполненного на заполненный (перемещение по столбцу или строке) соответствует соответствующее изменение с заполненного на незаполненный (и наоборот). ), даже если первая или последняя ячейка в строке заполнена. Это единственная причина использования сетки 18x18. Это не единственный способ подсчета блоков, но я думаю, что это самый простой.

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

Это настоящее мясо логики ILP. В основном это требует, чтобы каждая ячейка (кроме тех, которые находятся в первой строке и столбце) была логическим xor ячейки и разделителя непосредственно слева от ее строки и непосредственно над ней в ее столбце. Я получил ограничения, которые имитируют xor в целочисленной программе {0,1} из этого замечательного ответа: /cs//a/12118/44289

Чтобы объяснить немного больше: это ограничение xor делает так, чтобы разделители могли быть 1, если и только если они лежат между ячейками, которые являются 0 и 1 (отмечая изменение от незаполненного к заполненному или наоборот). Таким образом, в строке или столбце будет ровно вдвое больше однозначных разделителей, чем количество блоков в этой строке или столбце. Другими словами, сумма разделителей в данной строке или столбце ровно в два раза больше этой строки / столбца. Отсюда следующие ограничения:

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

И это в значительной степени так. Остальные просто запрашивают решение по умолчанию для решения ILP, а затем форматируют полученное решение, когда оно записывает его в файл.

Ява, 6 093 092 4 326 656 3 637 260 квадратов (минимизировано), 10 567 550 10 567 691 10 568 746 квадратов (максимально)

Оба варианта программы многократно выполняют операции с исходной сеткой, не меняя величины.

Minimizer

сокращаться, сжиматься()

Если черный квадрат имеет 2 белых соседа и 2 черных соседа под углом 90 °, его можно заменить белым квадратом.

moveLine ()

В конфигурациях, подобных выше, черная линия может быть перемещена вправо. Это делается повторно для всех четырех направлений линии по часовой стрелке и против часовой стрелки, чтобы открыть новые возможности сжатия.

Maximizer

Раскомментируйте строку main()и закомментируйте строку над ней для этой версии.

расти ()

Если белый квадрат имеет 2 белых соседа и 2 черных соседа под углом 90 °, его можно заменить черным квадратом.

moveLine ()

Так же, как в минимизаторе.

Источник

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);
    }
}

Баш - 10 239 288 квадратов

В качестве справочного решения последнего места:

cp nonograms_b64.txt solutions_b64.txt

Поскольку вашей программе разрешено возвращать ту же сетку, если она не может найти лучшего решения, распечатка всего файла дословно также допустима.

Всего в тестовом файле находится 10 239 288 черных квадратов, что довольно близко к 10 240 000 000, которые можно ожидать от 80% квадратов, заполненных из 50 000 сеток по 256 квадратов в каждом. Как обычно с моими вопросами о тестовых батареях, я выбрал количество тестовых случаев с ожиданием того, что оптимальные оценки будут около 2 миллионов, хотя я подозреваю, что на этот раз оценки будут ближе к 4 или 5 миллионам ,

Если кто-то может создать решение, которое максимизирует черные квадраты, а не минимизирует их и сможет получить более 10 240 000, я мог бы рассмотреть вопрос о предоставлении ему награды.

Matlab, 7 270 894 квадрата (~ 71% оригинала)

Идея - это простой повторный жадный поиск: для каждого черного квадрата попробуйте, если вы можете установить его на белый, не меняя неографических величин. Повторите это дважды. (Вы могли бы добиться лучших результатов с большим количеством повторений, но не бесплатно: это приводит к соответственно более длительному времени выполнения. Теперь это было около 80 минут. Я сделал бы это, если бы нам не пришлось вычислять все тестовые случаи 50k ...)

Здесь код (каждая функция в отдельном файле, как обычно.)

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