Você pode vencer a inteligência britânica? (Nonogram Solver)

20

É hora de embarcar em uma perigosa busca para derrotar a Inteligência Britânica. O objetivo deste desafio é escrever o código mais curto que resolverá um Nonograma.

O que é um nonograma?

Nonogram Puzzle

As regras são simples. Você tem uma grade de quadrados, que deve ser preenchida em preto ou deixada em branco. Ao lado de cada linha da grade, estão listados os comprimentos das séries de quadrados pretos nessa linha. Acima de cada coluna, estão listados os comprimentos das execuções de quadrados pretos nessa coluna. Seu objetivo é encontrar todos os quadrados pretos. Nesse tipo de quebra-cabeça, os números são uma forma de tomografia discreta que mede quantas linhas ininterruptas de quadrados preenchidos existem em qualquer linha ou coluna. Por exemplo, uma pista de "4 8 3" significaria que há conjuntos de quatro, oito e três quadrados preenchidos, nessa ordem, com pelo menos um quadrado em branco entre grupos sucessivos. [ 1 ] [ 2 ]

Portanto, a solução para o Nonogram acima seria:

Nonograma resolvido

Detalhes da implementação

Você pode representar o Nonograma da maneira que desejar e tomá-lo como entrada da maneira que julgar adequada ao seu idioma. O mesmo vale para a saída. O objetivo desse desafio é literalmente fazer o trabalho; se você puder resolver o nonograma com qualquer saída que seu programa der, isso é válido. Uma ressalva é que você não pode usar um solucionador on-line :)

Esse problema é desafiador por algoritmos (np-complete), pois não existe uma solução completamente eficiente e, como tal, você não será penalizado por não conseguir resolver os maiores, embora sua resposta seja altamente recompensada se for capaz de lidar com casos grandes (ver bônus). Como referência, minha solução funciona em aproximadamente 25x25 em 5 a 10 segundos. Para permitir flexibilidade entre idiomas diferentes, as soluções que levam menos de 5 minutos para um nonograma de 25x25 são boas o suficiente.

Você pode assumir um quebra-cabeça em um nonograma quadrado NxN.

Você pode usar este criador de quebra-cabeças sem programa on - line para testar suas soluções.

Pontuação

Você é livre para usar qualquer idioma que desejar e, como se trata de código de golfe, as entradas serão classificadas na ordem: accuracy -> length of code -> speed.No entanto, não desanime com idiomas de código de golfe, respostas em todos os idiomas que mostram tentativas de golfe de uma maneira interessante será votado!

Bônus

Na verdade, eu aprendi sobre os Nonogramas a partir de um cartão de Natal criptográfico lançado pela Inteligência Britânica aqui . A primeira parte foi basicamente um Nonogram enorme de 25x25. Se sua solução for capaz de resolver isso, você receberá elogios :)

Para facilitar sua vida em termos de entrada de dados, forneci como eu representava os dados desse quebra-cabeça específico para seu uso gratuito. As primeiras 25 linhas são as pistas da linha, seguidas por uma linha separadora '-', seguidas por 25 linhas das pistas col, seguidas por uma linha separadora '#' e, em seguida, uma representação da grade com as pistas quadradas preenchidas.

7 3 1 1 7
1 1 2 2 1 1
1 3 1 3 1 1 3 1
1 3 1 1 6 1 3 1
1 3 1 5 2 1 3 1
1 1 2 1 1
7 1 1 1 1 1 7
3 3
1 2 3 1 1 3 1 1 2
1 1 3 2 1 1
4 1 4 2 1 2
1 1 1 1 1 4 1 3
2 1 1 1 2 5
3 2 2 6 3 1
1 9 1 1 2 1
2 1 2 2 3 1
3 1 1 1 1 5 1
1 2 2 5
7 1 2 1 1 1 3
1 1 2 1 2 2 1
1 3 1 4 5 1
1 3 1 3 10 2
1 3 1 1 6 6
1 1 2 1 1 2
7 2 1 2 5
-
7 2 1 1 7
1 1 2 2 1 1
1 3 1 3 1 3 1 3 1
1 3 1 1 5 1 3 1
1 3 1 1 4 1 3 1
1 1 1 2 1 1
7 1 1 1 1 1 7
1 1 3
2 1 2 1 8 2 1
2 2 1 2 1 1 1 2
1 7 3 2 1
1 2 3 1 1 1 1 1
4 1 1 2 6
3 3 1 1 1 3 1
1 2 5 2 2
2 2 1 1 1 1 1 2 1
1 3 3 2 1 8 1
6 2 1
7 1 4 1 1 3
1 1 1 1 4
1 3 1 3 7 1
1 3 1 1 1 2 1 1 4
1 3 1 4 3 3
1 1 2 2 2 6 1
7 1 3 2 1 1
#
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 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 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 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 1 1 0 0 1 0 0 0 1 1 0 0 1 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 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 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 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 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 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 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 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 0 0 0 0 0 0 0 0 0

E aqui está uma versão ligeiramente diferente para sua conveniência; uma tupla separada por vírgula (linha, col), em que cada elemento é uma lista de listas.

([[7, 3, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 1, 3, 1],
  [1, 3, 1, 1, 6, 1, 3, 1],
  [1, 3, 1, 5, 2, 1, 3, 1],
  [1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [3, 3],
  [1, 2, 3, 1, 1, 3, 1, 1, 2],
  [1, 1, 3, 2, 1, 1],
  [4, 1, 4, 2, 1, 2],
  [1, 1, 1, 1, 1, 4, 1, 3],
  [2, 1, 1, 1, 2, 5],
  [3, 2, 2, 6, 3, 1],
  [1, 9, 1, 1, 2, 1],
  [2, 1, 2, 2, 3, 1],
  [3, 1, 1, 1, 1, 5, 1],
  [1, 2, 2, 5],
  [7, 1, 2, 1, 1, 1, 3],
  [1, 1, 2, 1, 2, 2, 1],
  [1, 3, 1, 4, 5, 1],
  [1, 3, 1, 3, 10, 2],
  [1, 3, 1, 1, 6, 6],
  [1, 1, 2, 1, 1, 2],
  [7, 2, 1, 2, 5]],
 [[7, 2, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 3, 1, 3, 1],
  [1, 3, 1, 1, 5, 1, 3, 1],
  [1, 3, 1, 1, 4, 1, 3, 1],
  [1, 1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [1, 1, 3],
  [2, 1, 2, 1, 8, 2, 1],
  [2, 2, 1, 2, 1, 1, 1, 2],
  [1, 7, 3, 2, 1],
  [1, 2, 3, 1, 1, 1, 1, 1],
  [4, 1, 1, 2, 6],
  [3, 3, 1, 1, 1, 3, 1],
  [1, 2, 5, 2, 2],
  [2, 2, 1, 1, 1, 1, 1, 2, 1],
  [1, 3, 3, 2, 1, 8, 1],
  [6, 2, 1],
  [7, 1, 4, 1, 1, 3],
  [1, 1, 1, 1, 4],
  [1, 3, 1, 3, 7, 1],
  [1, 3, 1, 1, 1, 2, 1, 1, 4],
  [1, 3, 1, 4, 3, 3],
  [1, 1, 2, 2, 2, 6, 1],
  [7, 1, 3, 2, 1, 1]])
code-golf puzzle-solver gowrath
fonte
Infelizmente, meu site está fora do ar, mas costumava ter um resolvedor Nonogram razoavelmente rápido; 5-10 minutos parece excessivo.
Neil
1
codegolf.stackexchange.com/q/30081/21348 Relacionado
edc65
1
@dwana Você não precisa se preocupar com casos insolúveis. Quanto à resposta aleatória, em um nonograma de 25x25, você tem 2 ^ 625 configurações possíveis. No contexto, isso é mais do que o dobro do número de átomos no universo conhecido (ou seja, se você usasse cada átomo no universo um pouco, ainda não teria espaço suficiente para armazenar as possibilidades). Em termos de tempo, se você levou um segundo nano (generoso) para verificar a validade de cada configuração, que levaria 7 vidas do universo para o código para concluir a execução :)
gowrath
1
Ty para esclarecer casos insolúveis. (+ I tem um PC mágico do valida uma resposta em ~ 2.1546362E-186 segundos)
Dwana
1
Seu CSV não possui dicas quadradas. Aqui estão algumas JS para gerá-los:s=[].fill([].fill(0,0,25),0,25);s[3][3]=s[3][4]=s3[3][12]=s3[3][13]=s3[3][21]=s[8][6]=s[8][7]=s[8][10]=s[8][14]=s[8][15]=s[8][18]=s[16][6]=s[16][11]=s[16][16]=s[16][20]=s[21][3]=s[21][4]=s[21][9]=s[21][10]=s[21][15]=s[21][20]=s[21][21]=1;
Titus

Respostas:

5

Braquilog , 70 69 bytes

[R:C]hlL~l:L:1f=.:3aR,.z:3aC,
tL,?he##ElL,E:2a
.<2,_1<
@b:4f:la
e.h1,

Isso leva uma lista de duas listas (primeiro os indicadores de linhas, depois os da coluna). Cada indicador é ele próprio uma lista (para sessões como [3,1]em uma linha).

Esta versão leva cerca de 3 minutos para resolver o exemplo 5 por 5 do desafio.

Versão muito mais eficiente, 91 bytes

[R:C]hlL~l:L:1f:Cz:3az:Rz:3a=.:4aR,.z:4aC,
tL,?he##ElL,E:2a
.<2,_1<
:+a#=,?h
@b:5f:la
e.h1,

Experimente online!

Essa não é uma força bruta completa: a única diferença é que ela impõe restrições aos valores das células, de modo que o número de 1s em cada linha e coluna corresponda aos números dados como indicadores na entrada. A única parte da força bruta é encontrar a grade com as restrições para as quais os "blocos" de 1s correspondem ao que é dado como indicação.

Este leva cerca de 0,05 segundos no exemplo 5 por 5 do desafio. Isso ainda é muito lento para o caso de bônus, pois não tenho idéia de como expressar os blocos de unidades separados por um ou mais zeros em termos de restrições.

Explicação

Vou explicar abaixo a versão de 93 bytes. A única diferença entre os dois é a chamada para o predicado 3, que não existe na versão de 70 bytes, e a numeração dos predicados (já que há um a menos).

  • Predicado principal:

    [R:C]     Input = [R, C]
hlL       The length of R is L
~l        Create a list of length L
:L:1f     Each element of that list is a sublist of length L with cells 0 or 1 (Pred 1)
          %%% Part unique to the 93 bytes version
:Cz       Zip the rows of the list of lists with C
:3a       The sum of 1s in each row is equal to the sum of the indicators (Pred 3)
z         Transpose
:Rz       Zip the columns of the list of lists with R
:3a       The sum of 1s in each column is equal to the sum of the indicators (Pred 3)
          %%%
=.        Assign values to the cells of the list of lists which satisfy the constraints
:4aR,     The blocks of 1s must match the indicators on rows
.z        Transpose
:4aC,     The blocks of 1s must match the indicators on columns

  • Predicado 1: força as linhas a terem um comprimento específico e que cada célula seja 0 ou 1.

    tL,       L is the length given as second element of the input
?he       Take an element from the list
##ElL,    That element E is itself a list of length L
E:2a      The elements of E are 0s and 1s (Pred 2)

  • Predicado 2: restrinja uma variável a ser 0 ou 1

    .<2,      Input = Output < 2
_1<       Output > -1

  • Predicado 3: A soma de 1s em uma lista deve ser igual à soma dos indicadores (por exemplo, se o indicador for [3: 1], a lista deve ter a soma 4)

    :+a       Sum the elements of the list and sum the indicator
#=,       Both sums must be equal
?h        Output is the list

  • Predicado 4: verifique se os blocos de 1s correspondem ao indicador

    @b        Split the list in blocks of the same value
:5f       Find all blocks of 1s (Pred 5)
:la       The list of lengths of the blocks results in the indicator (given as output)

  • Predicado 5: verdadeiro para blocos de 1s, falso caso contrário

    e.        Output is an element of the input
  h1,     Its first value is 1
Fatalizar
fonte
Parece a ferramenta perfeita para o trabalho. Ansioso para a explicação.
Emigna
@Fatalize Isso é fantástico, eu estava esperando alguém usar uma linguagem de prólogo para fazer isso. Você já experimentou com o gabinete 25x25? Já
inseri
@gowrath Vou executar isso no meu computador esta tarde, vamos ver o que acontece.
Fatalize
@Fatalize Parece expirar, mas posso estar fazendo errado. Eu não confiar inteiramente em minhas habilidades de entrada de dados ou: D
gowrath
@gowrath Ele atinge o tempo limite no TIO, mas eu o executarei no intérprete offline diretamente no meu computador.
Fatalize
9

Haskell, 242 230 201 199 177 163 160 160 149 131 bytes

import Data.Lists
m=map
a#b=[x|x<-m(chunk$length b).mapM id$[0,1]<$(a>>b),g x==a,g(transpose x)==b]
g=m$list[0]id.m sum.wordsBy(<1)

Finalmente, com menos de 200 bytes, credite para @Bergi. Muito obrigado a @nimi por ajudar quase a reduzir o tamanho pela metade.

Uau. Quase com metade do tamanho agora, em parte por minha causa, mas principalmente por causa do @nimi.

A função mágica é (#). Encontra todas as soluções de um dado nonograma.

Isso é capaz de resolver todos os casos, mas pode ser super lento, já que é uma questão de complexidade O(2^(len a * len b)). Um benchmark rápido revelou 86 GB alocados para um nonograma 5x5.

Curiosidade: funciona para todos os nonogramas, não apenas os quadrados.

Como funciona:

  • a#b: Dadas as listas de listas de números inteiros que representam o número de quadrados, gere todas as grades ( map(chunk$length b).mapM id$a>>b>>[[0,1]]) e filtre os resultados para manter apenas os válidos.
  • g: Dado um nonogram potencial, soma as execuções de 1s horizontalmente.
ThreeFx
fonte
Você quer dizer O (2 ^ (len a * len b)), não O ((len a * len b) ^ 2).
Anders Kaseorg 30/08/16
@AndersKaseorg Right. Mantenha o milhão que acidentalmente impliquei lá. : D
ThreeFx
1
Mais alguns bytes: m(chunk$l b)ereplicate(l$a>>b)
Bergi
@ThreeFx 86GB: O ... Btw, você poderia explicar brevemente como compilar isso? Eu apenas comecei a aprender haskell e isso está dando erros com o ghc. Teste quero-o para fora :)
gowrath
1
import Data.Listsé suficiente, porque reexporta ambos Data.Liste Data.List.Split.
nimi
4

Pitão, 91 72 71 bytes

D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb

Um programa que recebe a entrada de uma lista do formulário em [size, [horizontal clues], [vertical clues]]que cada pista é uma lista de números inteiros (pistas vazias são a lista vazia,[] ), e imprime a cada solução, nova linha separada, sob a forma de uma grade de binário, onde 1é protegido e 0é não sombreado .

Esta é uma força bruta, por isso é aproximadamente O(2^n^2) . Começa a demorar muito tempo para quebra-cabeças maiores, mas resolve qualquer tamanho arbitrário, desde que haja tempo suficiente.

Experimente online

Como funciona

O programa gera todos os layouts possíveis, utilizando o produto cartesiano repetido [0, 1]com um comprimento igual a size^2. Isso é dividido em pedaços, fornecendo uma lista para cada linha horizontal. Cada linha é codificada no comprimento da execução, filtrada pela presença 1e achatada, deixando a pista para essa linha. Isso é verificado contra a entrada. O processo acima é repetido para a transposição dos pedaços, verificando as linhas verticais. Se houver uma ocorrência, cada parte é concatenada e as partes concatenadas são unidas em novas linhas e impressas implicitamente, com uma nova linha à direita.

D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb  Program. Input: Q
                            hQ                                           Q[0], size
                           ^  2                                          Square
                        ,01                                              [0, 1]
                       ^                                                 Cartesian product
                      V                                     )            For N in the Cartesian product:
                                 cNhQ                                    Split N into Q[0] chunks
                               =T                                        Assign that to T
                                     =Y1                                 Y=1
                                        VhQ                              For H in range [0, Q[0]-1]:
D:GHd                                                                     def :(G, H, d)
                   rH8                                                     Run-length-encode(H)
               f.)T                                                        Filter by presence of 1 in character part
            .nC                                                            Transpose and flatten, giving the clue
       @@QdG                                                               Q[d][G], the relevant input clue
     Rq                                                                    Return clue==input clue
                                               :H@TH1                     :(H, T, 1)
                                                     :H@CTH2              :(H, transpose(T), 2)
                                           =*Y*                           Y=Y*product of above two
                                                             IY           If Y:
                                                                 mjkdT     Conacatenate each element of T
                                                               jb          Join on newlines
                                                                      b    Add a newline and implicitly print

Obrigado a @ Pietu1998 por algumas dicas

TheBikingViking
fonte
Este pode ser o programa Pyth mais longo que eu já vi
Business Cat
=ZhZé igual a =hZ, e FNé igual a V.
319
@TheBikingViking O que exatamente você quer dizer com tempo suficiente? Tenho certeza de que isso não resolveria um 25x25 até agora, se você o tivesse iniciado desde a concepção do universo.
precisa saber é
1
@gowrath Eu também tenho certeza disso! Eu sou novo para Pyth, e após o período de tempo isso me levou, eu nem sequer considerar a tentar implementar um algoritmo de melhor
TheBikingViking
2

Javascript (ES6), 401 386 333 bytes

Esta é uma tentativa inicial. Não é muito eficiente, mas estava curioso para testar uma solução usando expressões regulares na representação binária das linhas e colunas.

Por exemplo, ele traduzirá a pista [3,1]na seguinte expressão regular:

/^0*1{3}0+1{1}0*$/

No momento, esta versão não está levando em consideração pistas quadradas. Provavelmente vou adicionar isso mais tarde.

Código

(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

Saída

A solução é exibida em formato binário. Tal como:

00110
01110
11100
11101
00001

Teste

Este é um teste simples na grade de exemplo.

let f =
(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

console.log(f(
  [[2],[3],[4],[2],[2]],
  [[2],[3],[3],[3,1],[1]]
));
Expandir snippet

Arnauld
fonte
boa ideia. mata meus navegadores no quebra-cabeça de natal, no entanto.
Titus
2

Haskell, 109 bytes

Isenção de responsabilidade: isso é derivado da resposta da @ ThreeFx . Ajudei-o a jogar sua resposta, mas ele parece ter perdido o interesse de incluir minhas últimas melhorias substanciais, então as coloco como nova resposta.

import Data.List
n=mapM id
a#b=[x|x<-n$(n$" #"<$a)<$b,g x==a,g(transpose x)==b]
g=map$max[0].map length.words

Exemplo de uso: [[2],[3],[3],[3,1],[1]] # [[2],[3],[4],[2],[2]]->[[" ## "," ### ","### ","### #"," #"]] .

Força bruta. Tente todas as combinações de e #, divida os pedaços de int #, conte os comprimentos e compare com a entrada.

nimi
fonte
1

PHP, 751 833 (720) 753 724 726 710 691 680 682 bytes

Eu estava ansioso para construir um incremento de sequência especializado e experimentar meu gerador cartesiano mais uma vez;
mas abandonou o cartesiano em favor do retrocesso para resolver o quebra-cabeça grande mais rapidamente.

$p=[];foreach($r as$y=>$h){for($d=[2-($n=count($h)+1)+$u=-array_sum($h)+$w=count($r)]+array_fill($i=0,$n,1),$d[$n-1]=0;$i<1;$d[0]+=$u-array_sum($d)){$o=$x=0;foreach($d as$i=>$v)for($x+=$v,$k=$h[$i];$k--;)$o+=1<<$x++;if(($s[$y]|$o)==$o){$p[$y][]=$o;$q[$y]++;}for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);if(++$i<$n)for($d[$i]++;$i--;)$d[$i]=1;}}
function s($i,$m){global$c,$w,$p;for(;!$k&&$i[$m]--;$k=$k&$m<$w-1?s($i,$m+1):$k){for($k=1,$x=$w;$k&&$x--;){$h=$c[$x];for($v=$n=$z=$y=0;$k&&$y<=$m;$y++)$n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];if($k&$v)$k=$n<=$h[$z];}}return$k?is_array($k)?$k:$i:0;}
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));
  • espera dicas em matrizes $r para dicas de linha, dicas $cde coluna e$s dicas quadradas.
  • joga invalid argument supplied for foreach se não encontrar solução.
  • para obter a contagem correta de bytes, use um físico \ne remova as outras duas quebras de linha.

descrição

1) das dicas de linha
geram possíveis linhas que satisfazem as dicas quadradas
e lembram suas contagens para cada índice de linha.

2) retroceder nas combinações de linhas:
se a combinação atender às dicas da coluna, procure uma combinação mais profunda ou retorne com êxito,
mais tente a próxima possibilidade para esta linha

3) solução de impressão

O último golfe teve um impacto severo no desempenho;
mas removi as atribuições de criação de perfil para os benchmarks finais.

Substitua $n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];
porif(($p[$y][$i[$y]]>>$x&1)-$v){$k=($v=!$v)||$n==$h[$z++];$n=1;}else$n++;
para desfazer a última etapa do golfe.

exemplos

Para o pequeno exemplo ( 17 a 21 em torno de 12 8 7 6,7 5,3 ms), use

$r=[[2],[3],[3],[3,1],[1]];$c=[[2],[3],[4],[2],[2]];$s=[0,0,0,0,0];

para o quebra-cabeça de natal:

  • matou meu pequeno servidor doméstico com a solução antiga
  • matou o navegador com saídas de teste
  • agora resolvido em 50 37,8 45,5 em torno de 36 segundos

coloque os dados da pergunta em um arquivo christmas.nonograme use este código para importar:

$t=r;foreach(file('christmas.nonogram')as$h)if('-'==$h=trim($h))$t=c;elseif('#'==$h){$t=s;$f=count($h).b;}else
{$v=explode(' ',$h);if(s==$t)for($h=$v,$v=0,$b=1;count($h);$b*=2)$v+=$b*array_shift($h);${$t}[]=$v;}

demolir

$p=[];  // must init $p to array or `$p[$y][]=$o;` will fail
foreach($r as$y=>$h)
{
    // walk $d through all combinations of $n=`hint count+1` numbers that sum up to $u=`width-hint sum`
    // (possible `0` hints for $h) - first and last number can be 0, all others are >0
    for(
        $d=[2-
            ($n=count($h)+1)+               // count(0 hint)=count(1 hint)+1
            $u=-array_sum($h)+$w=count($r)  // sum(0 hint) = width-sum(1 hint)
        ]                           // index 0 to max value $u-$n+2
        +array_fill($i=0,$n,1)      // other indexes to 1
        ,$d[$n-1]=0;                // last index to 0
                                    // --> first combination (little endian)
        $i<1;   // $i:0 before loop; -1 after increment; >=$n after the last combination
        $d[0]+=$u-array_sum($d) // (see below)
    )
    {
        // A: create row (binary value) from 1-hints $h and 0-hints $d
        $o=$x=0;
        foreach($d as$i=>$v)
            for($x+=$v,$k=$h[$i];$k--;)
                $o+=1<<$x++;
        // B: if $o satisfies the square hints
        if(($s[$y]|$o)==$o)
        {
            $p[$y][]=$o;    // add to possible combinations
            $q[$y]++;       // increase possibility counter
        }
        // C: increase $d
            // find lowest index with a value>min
                // this loop doesn´t need to go to the last index:
                // if all previous values are min, there is nothing left to increase
        for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);
        if(++$i<$n)             // index one up; increase $d if possible
            for($d[$i]++        // increase this value
            ;$i--;)$d[$i]=1;    // reset everything below to 1
            // adjust $d[0] to have the correct sum (loop post condition)
    }
}

// search solution: with backtracking on the row combinations ...
function s($i,$m)
{
    global $c,$w,$p;
    for(;
        !$k // solution not yet found
        &&$i[$m]    // if $i[$m]==0, the previous iteration was the last one on this row: no solution
            --;     // decrease possibility index for row $m
        $k=$k&$m<$w-1? s($i,$m+1) : $k      // if ok, seek deeper while last row not reached ($m<$w-1)
    )
    {
        // test if the field so far satisfies the column hints: loop $x through columns
        for($k=1,$x=$w;$k&&$x--;)   // ok while $k is true
        {
            $h=$c[$x];
            // test column hints on the current combination: loop $y through rows up to $m
            for($v=$n=$z=   // $v=temporary value, $n=temporary hint, $z=hint index
                $y=0;$k&&$y<=$m;$y++)
                // if value has not changed, increase $n. if not, reset $n to 1
                // (or 0 for $k=false; in that case $n is irrelevant)
                $n=$n*  
                    // $f=false (int 0) when value has changed, true (1) if not
                    ($f=($p[$y][$i[$y]]>>$x&1)==$v)
                    +$k=$f?:    // ok if value has NOT changed, else
                        ($v=!$v)        // invert value. ok if value was 0
                        || $n==$h[$z    // value was 1: ok if temp hint equals current sub-hint
                        ++]             // next sub-hint
                ;
            // if there is a possibly incomplete hint ($v==1)
            // the incomplete hint ($n) must be <= the next sub-hint ($c[x][$z])
            // if $n was <$h[$z] in the last row, the previous column hints would not have matched
            if($k&$v)$k=$n<=$h[$z];
        }
        // ok: seek deeper (loop post condition)
        // not ok: try next possibility (loop pre condition)
    }
    return$k?is_array($k)?$k:$i:0;  // return solution if solved, 0 if not
}

// print solution
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));
Titus
fonte
1
O exemplo grande mata meu pequeno servidor doméstico (500 - Erro interno do servidor). As combinações estão prontas após 15 segundos, mas o produto cartesiano possui 1,823E + 61 membros. (As linhas 7 e 22 têm apenas uma solução entre si.) O algoritmo deve ser aprimorado.
Titus
Eu acho que isso pode ser acelerado se você usar o retorno recursivo. No entanto, um ótimo trabalho!
precisa saber é o seguinte
@gowrath: o backtracking dá um pouco e até salva bytes ... números inteiros com aritmética de bits dão cerca de 50% de velocidade, mas aumentam o tamanho (ainda precisamos descobrir quanto custa) ... Ainda estou nele.
Titus
@gowrath: persegui meu bug; estava no incremento (onde mais?): $dtem que estar na ordem correta paraforeach
Tito