Un nonogramme est un jeu de puzzle japonais dans lequel le but est de dessiner une image en noir et blanc selon une liste de régions contiguës, comme ceci:

Définissez la grandeur nonographique d'une ligne ou d'une colonne comme étant le nombre de régions noires contiguës dans cette ligne ou cette colonne. Par exemple, la ligne supérieure a une magnitude nonographique de 1, car il y a une région de 2 carrés dans cette ligne. La 8e rangée a une magnitude nonographique de 3 car elle en a 2, 2, 1.

Une ligne ou une colonne vide a une magnitude nonographique de 0.

Votre tâche consiste à écrire un programme qui prend une grille de solution pour un nonogramme, et produit une grille de solution avec aussi peu de carrés remplis que possible où chaque ligne et colonne a le même magnutide nonographique que la grille de solution donnée.

Par exemple, une grille non graphique avec tous les carrés remplis a une magnitude nonographique de 1 sur chaque ligne ou colonne:

La même grandeur nonographique pourrait être obtenue simplement en ayant une bande diagonale à travers la grille, ce qui réduit considérablement le nombre de carrés remplis:

Votre programme recevra une entrée composée de 50 000 lignes de ce fichier ( fichier texte tar.gz de 1,32 Mo; 2,15 Mo décompressé), chacune représentant une seule grille de solution de nonogrammes 16 × 16 avec des carrés remplis de manière aléatoire (noir à 80%), et produire encore 50 000 lignes, chacune contenant la grille de solution optimisée pour la grille d'entrée correspondante.

Chaque grille est représentée sous la forme d'une chaîne base64 avec 43 caractères (encodage des carrés de gauche à droite, puis de haut en bas), et votre programme devra renvoyer sa sortie dans le même format. Par exemple, la première grille du fichier est E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=, et s'affiche comme suit:

La grille commence par la Ecorrespondance avec 000100, donc les six premières cellules de la rangée supérieure sont toutes blanches sauf la quatrième. Le caractère suivant est celui /qui correspond 111111, donc les 6 cellules suivantes sont toutes noires - et ainsi de suite.

Votre programme doit en fait renvoyer une grille de solution avec les amplitudes nonographiques correctes pour chacun des 50 000 cas de test. Il est permis de renvoyer la même grille que l'entrée si rien de mieux n'a été trouvé.

Le programme qui renvoie le moins de carrés remplis au total (dans n'importe quelle langue) est le gagnant, le code plus court étant le bris d'égalité.

Tableau de bord actuel:

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

Python 2 et PuLP - 2 644 688 carrés (minimisés de manière optimale); 10 753 553 carrés (optimisé au maximum)

Golf minimalement à 1152 octets

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: les lignes fortement en retrait commencent par des tabulations, pas des espaces.)

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

Il s'avère que des problèmes comme ceux-ci sont facilement convertibles en programmes linéaires entiers, et j'avais besoin d'un problème de base pour apprendre à utiliser PuLP - une interface python pour une variété de solveurs LP - pour mon propre projet. Il s'avère également que PuLP est extrêmement facile à utiliser, et le générateur de LP non golfé a parfaitement fonctionné la première fois que je l'ai essayé.

Les deux bonnes choses à propos de l'utilisation d'un solveur IP de branche et de liaison pour faire le travail difficile de résoudre ce problème pour moi (à part le fait de ne pas avoir à implémenter un solveur de branche et lié) sont que

• Les solveurs spécialement conçus sont vraiment rapides. Ce programme résout tous les 50000 problèmes en environ 17 heures sur mon PC domestique relativement bas de gamme. Chaque instance a pris de 1 à 1,5 seconde pour être résolue.
• Ils produisent des solutions optimales garanties (ou vous disent qu'ils ne l'ont pas fait). Ainsi, je peux être sûr que personne ne battra mon score dans les carrés (bien que quelqu'un puisse le lier et me battre sur la partie golf).

Comment utiliser ce programme

Tout d'abord, vous devrez installer PuLP. pip install pulpdevrait faire l'affaire si vous avez installé pip.

Ensuite, vous devrez mettre les éléments suivants dans un fichier appelé "c": https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

Ensuite, exécutez ce programme dans n'importe quelle version Python 2 tardive du même répertoire. En moins d'une journée, vous aurez un fichier appelé "s" qui contient 50 000 grilles de nonogrammes résolues (dans un format lisible), chacune avec le nombre total de carrés remplis répertoriés en dessous.

Si vous souhaitez plutôt maximiser le nombre de carrés remplis, remplacez la LpMinimizeligne 8 par à la LpMaximizeplace. Vous obtiendrez une sortie très semblable à celle-ci: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing

Format d'entrée

Ce programme utilise un format d'entrée modifié, car Joe Z. a déclaré que nous serions autorisés à ré-encoder le format d'entrée si nous le souhaitons dans un commentaire sur l'OP. Cliquez sur le lien ci-dessus pour voir à quoi il ressemble. Il se compose de 10 000 lignes, chacune contenant 16 chiffres. Les lignes numérotées paires sont les magnitudes des lignes d'une instance donnée, tandis que les lignes numérotées impaires sont les magnitudes des colonnes de la même instance que la ligne au-dessus d'elles. Ce fichier a été généré par le programme suivant:

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

(Ce programme de ré-encodage m'a également donné une opportunité supplémentaire de tester ma classe BitQueue personnalisée que j'ai créée pour le même projet mentionné ci-dessus. être sauté soit un bit soit un octet à la fois. Dans ce cas, cela a parfaitement fonctionné.)

J'ai ré-encodé l'entrée pour la raison spécifique que pour construire un ILP, les informations supplémentaires sur les grilles qui ont été utilisées pour générer les amplitudes sont parfaitement inutiles. Les grandeurs sont les seules contraintes, et donc les grandeurs sont tout ce à quoi j'avais besoin d'accéder.

Générateur ILP non golfé

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

Il s'agit du programme qui a réellement produit "l'exemple de sortie" lié ci-dessus. D'où les cordes extra longues à la fin de chaque grille, que j'ai tronquées lors du golf. (La version golfée devrait produire une sortie identique, moins les mots "Filled squares for ")

Comment ça fonctionne

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)

J'utilise une grille 18x18, la partie centrale 16x16 étant la véritable solution du puzzle. cellsest cette grille. La première ligne crée 324 variables binaires: "cell_0_0", "cell_0_1", etc. Je crée également des grilles des "espaces" entre et autour des cellules dans la partie solution de la grille. rowsepspointe sur les 289 variables qui symbolisent les espaces qui séparent les cellules horizontalement, tandis que colsepspointe également sur les variables qui marquent les espaces qui séparent les cellules verticalement. Voici un diagramme 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

Les 0s et □s sont les valeurs binaires suivies par les cellvariables, les |s sont les valeurs binaires suivies par les rowsepvariables et les -s sont les valeurs binaires suivies par les colsepvariables.

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

Telle est la fonction objective. Juste la somme de toutes les cellvariables. Puisque ce sont des variables binaires, c'est exactement le nombre de carrés remplis dans la solution.

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

Cela met simplement les cellules autour du bord extérieur de la grille à zéro (c'est pourquoi je les ai représentées comme des zéros ci-dessus). Il s'agit du moyen le plus rapide de suivre le nombre de "blocs" de cellules remplis, car il garantit que chaque changement de non rempli à rempli (se déplaçant sur une colonne ou une ligne) correspond à un changement correspondant de rempli à non rempli (et vice versa). ), même si la première ou la dernière cellule de la ligne est remplie. C'est la seule raison d'utiliser une grille 18x18 en premier lieu. Ce n'est pas la seule façon de compter les blocs, mais je pense que c'est la plus simple.

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

C'est la vraie chair de la logique de l'ILP. Fondamentalement, cela nécessite que chaque cellule (autre que celles de la première ligne et colonne) soit le xor logique de la cellule et le séparateur directement à sa gauche dans sa ligne et directement au-dessus dans sa colonne. J'ai obtenu les contraintes qui simulent un xor dans un programme entier {0,1} à partir de cette merveilleuse réponse: /cs//a/12118/44289

Pour expliquer un peu plus: cette contrainte xor fait que les séparateurs peuvent être 1 si et seulement s'ils se trouvent entre des cellules qui sont 0 et 1 (marquant un changement de non rempli à rempli ou vice versa). Ainsi, il y aura exactement deux fois plus de séparateurs à 1 valeur dans une ligne ou une colonne que le nombre de blocs dans cette ligne ou cette colonne. En d'autres termes, la somme des séparateurs sur une ligne ou une colonne donnée est exactement le double de la magnitude de cette ligne / colonne. D'où les contraintes suivantes:

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

Et c'est à peu près tout. Le reste demande simplement au solveur par défaut de résoudre l'ILP, puis formate la solution résultante pendant qu'elle l'écrit dans le fichier.

Java, 6.093.092 4.332.656 3.637.260 carrés (minimisé), 10.567.550 10.567.691 10.568.746 carrés (maximisé)

Les deux variantes du programme effectuent à plusieurs reprises des opérations sur la grille source, sans modifier l'amplitude.

Minimizer

rétrécir()

Si un carré noir a 2 voisins blancs et 2 voisins noirs dans un angle de 90 °, il peut être remplacé par un carré blanc.

moveLine ()

Dans les configurations comme ci-dessus, la ligne noire peut être déplacée vers la droite. Cette opération est répétée pour les 4 directions de ligne dans le sens horaire et antihoraire, pour ouvrir de nouvelles possibilités de rétrécissement.

Maximizer

Décommentez la ligne main()et commentez la ligne au-dessus pour cette version.

grandir()

Si un carré blanc a 2 voisins blancs et 2 voisins noirs dans un angle de 90 °, il peut être remplacé par un carré noir.

moveLine ()

Identique à Minimizer.

La source

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 carrés

Comme solution de référence de dernière place:

cp nonograms_b64.txt solutions_b64.txt

Étant donné que votre programme est autorisé à renvoyer la même grille s'il ne peut pas trouver une meilleure solution, l'impression de l'intégralité du fichier textuellement est également valide.

Il y a un total de 10 239 288 carrés noirs dans le fichier de test, ce qui est assez proche des 10 240 000 que vous attendez de 80% des carrés remplis sur 50 000 grilles de 256 carrés chacune. Comme d'habitude avec mes questions sur la batterie de test, j'ai sélectionné le nombre de cas de test en espérant que les scores optimaux seront autour de la plage de 2 millions, bien que je soupçonne que les scores seront plus proches de 4 ou 5 millions cette fois-ci. .

Si quelqu'un peut créer une solution qui maximise les carrés noirs plutôt que de les minimiser et parvient à obtenir plus de 10 240 000, je pourrais envisager de lui donner une prime.

Matlab, 7270894 carrés (~ 71% de l'original)

L'idée est une simple recherche gourmande répétée: pour chaque carré noir, essayez de le mettre au blanc sans changer les grandeurs non géographiques. Répétez cette opération deux fois. (Vous pourriez obtenir de bien meilleurs résultats avec plus de répétitions, mais pas gratuitement: cela se traduit par un temps d'exécution plus long. Maintenant, c'était environ 80 minutes. Je le ferais, si nous n'avions pas à calculer tous les tests 50k ...)

Voici le code (chaque fonction dans un fichier séparé, comme d'habitude.)

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