Seu trabalho é escrever um programa (ou dois programas separados) em qualquer idioma que:
- Pode pegar um quadro de Sudoku completo como entrada (em qualquer formato lógico) e compactá-lo em uma sequência de caracteres
- Pode pegar a string compactada como entrada e descompactá-la para obter exatamente o mesmo quadro de Sudoku completo (saída em qualquer formato lógico de 9 linhas)
Nota: Use as regras do Sudoku para sua vantagem; essa é a ideia por trás desse desafio.
Regras do Sudoku na Wikipedia
Regras
- Somente caracteres ASCII imprimíveis (32 - 126) são permitidos na saída compactada (por exemplo, sem caracteres multibyte ).
- Você pode assumir que a entrada é uma placa de Sudoku 3x3 válida (regras normais, sem variações).
- Não vou impor um prazo, mas não crio um algoritmo de força bruta. Ou então, os remetentes devem poder testar seus envios antes da postagem (Obrigado Jan Dvorak).
Se você tiver alguma dúvida ou preocupação, peça esclarecimentos ou faça sugestões nos comentários.
Condições vencedoras
Pontuação = soma do número de caracteres de todos os dez casos de teste
Menor pontuação ganha.
Casos de teste
Você pode usá-los para testar o desempenho do seu programa.
9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1
7 2 4 8 6 5 1 9 3
1 6 9 2 4 3 8 7 5
3 8 5 1 9 7 2 4 6
8 9 6 7 2 4 3 5 1
2 7 3 9 5 1 6 8 4
4 5 1 3 8 6 9 2 7
5 4 2 6 3 9 7 1 8
6 1 8 5 7 2 4 3 9
9 3 7 4 1 8 5 6 2
1 5 7 6 8 2 3 4 9
4 3 2 5 1 9 6 8 7
6 9 8 3 4 7 2 5 1
8 2 5 4 7 6 1 9 3
7 1 3 9 2 8 4 6 5
9 6 4 1 3 5 7 2 8
5 4 1 2 9 3 8 7 6
2 8 9 7 6 1 5 3 4
3 7 6 8 5 4 9 1 2
8 3 5 4 1 6 9 2 7
2 9 6 8 5 7 4 3 1
4 1 7 2 9 3 6 5 8
5 6 9 1 3 4 7 8 2
1 2 3 6 7 8 5 4 9
7 4 8 5 2 9 1 6 3
6 5 2 7 8 1 3 9 4
9 8 1 3 4 5 2 7 6
3 7 4 9 6 2 8 1 5
6 2 8 4 5 1 7 9 3
5 9 4 7 3 2 6 8 1
7 1 3 6 8 9 5 4 2
2 4 7 3 1 5 8 6 9
9 6 1 8 2 7 3 5 4
3 8 5 9 6 4 2 1 7
1 5 6 2 4 3 9 7 8
4 3 9 5 7 8 1 2 6
8 7 2 1 9 6 4 3 5
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 8 9 7 2
6 4 8 9 7 2 5 3 1
9 7 2 5 3 1 6 4 8
1 4 5 7 9 2 8 3 6
3 7 6 5 8 4 1 9 2
2 9 8 3 6 1 7 5 4
7 3 1 9 2 8 6 4 5
8 5 9 6 4 7 3 2 1
4 6 2 1 3 5 9 8 7
6 2 4 8 7 3 5 1 9
5 8 7 4 1 9 2 6 3
9 1 3 2 5 6 4 7 8
5 2 7 4 1 6 9 3 8
8 6 4 3 2 9 1 5 7
1 3 9 5 7 8 6 4 2
2 9 1 8 5 4 3 7 6
3 4 8 6 9 7 5 2 1
6 7 5 1 3 2 4 8 9
7 1 2 9 4 5 8 6 3
4 8 3 2 6 1 7 9 5
9 5 6 7 8 3 2 1 4
2 4 6 7 1 3 9 8 5
1 8 5 4 9 6 7 3 2
9 3 7 8 2 5 1 4 6
6 7 8 5 4 2 3 9 1
4 9 3 1 6 8 2 5 7
5 1 2 3 7 9 4 6 8
8 2 4 9 5 7 6 1 3
7 5 9 6 3 1 8 2 4
3 6 1 2 8 4 5 7 9
8 6 1 2 9 4 5 7 3
4 7 5 3 1 8 6 9 2
3 9 2 5 6 7 8 1 4
2 3 6 4 5 9 7 8 1
1 5 4 7 8 3 2 6 9
9 8 7 6 2 1 3 4 5
5 2 9 1 7 6 4 3 8
6 4 8 9 3 2 1 5 7
7 1 3 8 4 5 9 2 6
Agradecemos a http://www.opensky.ca/~jdhildeb/software/sudokugen/ por alguns desses
Se você encontrar algum problema com os casos de teste, informe-me.
code-challenge
compression
sudoku
kukac67
fonte
fonte
fudge
sub - rotina na minha segunda resposta que ganha 12 pontos). Um teste mais justo seria exigir que (a) as soluções de teste funcionem, (b) pontue em 1.000 grades Sudoku geradas aleatoriamente e divida a resposta por 100. Acredito que o melhor que se pode fazer com dados aleatórios é de 110, com base em 10 x log-base-95 (6670903752021072936960)Respostas:
Haskell, 107 pontos
O caso de teste resulta:
O código não é bonito, mas funciona. A base do algoritmo é que, embora a enumeração de todas as soluções demore muito, a enumeração de todas as soluções em um único bloco é bastante rápida - na verdade, é mais rápida que a conversão subsequente em base95. A coisa toda é executada em segundos no intérprete na minha máquina básica. Um programa compilado seria concluído imediatamente.
O trabalho pesado é realizado pela
solution2ix
função que, para cada bloco 3x3, gera todas as permutações possíveis, sujeitas a restrições da esquerda e de cima, até encontrar a solução codificada, lembrando apenas o índice da permutação. Em seguida, combina os índices usando alguns pesos pré-computados e o esquema de Horner.Na outra direção, a
ix2solution
função primeiro decompõe o índice em nove valores. Em seguida, para cada bloco, indexa a lista de permutações possíveis com seu respectivo valor e extrai as restrições para os próximos blocos.assignments
é uma recursão desenrolada simples, mas feia, usando a mônada da lista. Ele gera a lista de permutações, dado um conjunto de restrições.A potência real vem dos limites apertados nos comprimentos da lista de permutações:
9!
. Esse valor nunca é usado, exceto para encontrar um limite superior para o comprimento da saída.6*5*4*6!
é sete vezes pior que a contagem real encontrada pela enumeração:12096
O produto de todos esses limites é
71025136897117189570560
~ =95^11.5544
, o que significa que nenhum código tem mais de 12 caracteres e quase metade deles deve ter 11 caracteres ou menos. Decidi não distinguir entre uma corda mais curta e a mesma corda preenchida à direita com espaços. Espaços em qualquer outro lugar são significativos.O limite teórico da eficiência da codificação para códigos sem prefixo - logaritmo da base 95 de
6670903752021072936960
- é11.035
, o que significa que mesmo um algoritmo ideal não pode evitar a produção de saídas de comprimento 12, embora as produza em apenas 3,5% de todos os casos. Permitir que o comprimento seja significativo (ou equivalente, adicionar espaços à direita) adiciona alguns códigos (1% da quantidade total), mas não o suficiente para eliminar a necessidade de códigos de comprimento 12.fonte
Python, 130 pontos
O algoritmo funciona codificando cada posição no quadro, uma de cada vez, em um grande número inteiro. Para cada posição, calcula os valores possíveis, considerando todas as atribuições codificadas até o momento. Portanto, se [1,3,7,9] são os valores possíveis para uma determinada posição, são necessários 2 bits para codificar a escolha.
O bom desse esquema é que, se uma posição tiver apenas uma única opção restante, não haverá espaço para codificação.
Quando temos o grande número inteiro, escrevemos na base 95.
Provavelmente existem ordens de codificação melhores do que a lexicográfica, mas não pensei muito nisso.
Codificador:
Decodificador:
Execute-o assim:
fonte
perl - pontuação
115113103113Saída:
Saída:Nenhuma dessas linhas tem um espaço final. Observe que a primeira linha está vazia.
Esse algoritmo funciona da seguinte maneira. Para comprimir:
Comece com uma string 'atual' vazia que representa a grade do Sudoku
Considere adicionar cada um dos dígitos 1 .. 9 a essa sequência e determinar qual é viável.
Obtenha o próximo dígito na grade de respostas (e adicione-o ao atual)
Se apenas um é viável, não há nada para codificar
Se mais de uma for viável, conte o número de opções viáveis, classifique-as e codifique esse dígito como o índice na matriz classificada. Registre o dígito e o número viável como uma tupla de 2 em uma matriz.
Quando tudo estiver pronto, codifique cada uma das 2 tuplas (na ordem inversa) em um número baseado em variável armazenado como um número grande.
Expresse o bigint na base 95.
Para decodificar:
Comece com uma string 'atual' vazia que representa a grade do Sudoku
Decodifique o número base95 para um bigint
Considere adicionar cada um dos dígitos 1 .. 9 a essa sequência e determinar qual é viável.
Se apenas um é viável, não há nada para codificar; adicione essa opção à grade
Se mais de uma for viável, conte o número de opções viáveis, classifique-as e codifique esse dígito como o índice na matriz classificada.
Decodifique o bigint da base variável usando o número de opções viáveis como base e o módulo como o índice na matriz e faça a saída desse dígito como um valor de célula.
Para determinar o número de opções viáveis, é utilizado o Games :: Sudoku :: Solver. Isso é principalmente para maior clareza, pois existem resolvedores de Sudoku de 3 linhas neste site.
Para fazer todos os 10 levou 8 segundos no meu laptop.
A
fudge
operação classifica a matriz de maneira diferente para atingir o valor mínimo para os casos de teste. Conforme documentado, isso é um fudge. O fudge reduz a pontuação de 115 para 103. É feito à mão para garantir que o código bigint para o primeiro teste seja 0. A pior pontuação para qualquer sudoku é 12, dando uma pontuação de 120. Portanto, acho que isso não conta. como codificação embutida; em vez disso, otimiza para os dados de teste. Para vê-lo funcionar sem isso, mudesort fudge
para ossort
dois lugares.O código a seguir:
fonte
CJam, 309 bytes
Esta é apenas uma solução rápida de linha de base. Sinto muito por ter feito isso em um idioma de golfe, mas na verdade era a maneira mais simples de fazer isso. Amanhã vou adicionar uma explicação do código real, mas descrevi o algoritmo abaixo.
Codificador
Decodificador
Teste aqui.
A entrada do codificador (no STDIN) e a saída do decodificador (no STDOUT) estão na forma de uma matriz CJam aninhada. Por exemplo
As 10 saídas de teste são:
O algoritmo é muito simples:
fonte
Python 2.7, 107 caracteres no total
TL; enumeração de força bruta de DR de quadrados 3x3 com restrições superior + esquerda
casos de teste:
função auxiliar para imprimir sudoku
gera todos os quadrados possíveis, dadas as restrições acima e à esquerda
consulte o comentário do código para obter mais detalhes
extrai todos os quadrados do quadro sudoku como tuplas
consulte o comentário do código para obter mais detalhes
converte quadrados de volta ao quadro de sudoku
basicamente um inverso da função acima
dados quadrados à esquerda, restrições de retorno
consulte o comentário do código para obter mais detalhes
dados quadrados acima, restrições de retorno
consulte o comentário do código para obter mais detalhes
faz uma corda
esta é uma lista codificada de dependências para cada quadrado
consulte o comentário do código para obter mais detalhes
esta é uma lista codificada do número máximo de opções possíveis para cada quadrado
consulte o comentário do código para obter mais detalhes
estes combinam as funções acima e convertem um quadro em uma lista de números inteiros
e de volta para um quadro
ok, isso é todas as funções
para cada quadro, faça um barbante e imprima
agora imprima o comprimento total de todas as strings
e sem restringir, para provar que não é uma compressão unidirecional
saída:
fonte
Mathematica, pontuação:
1309Atualizar:
Após a publicação desta resposta, inspirou uma nova brecha: "Otimizando para os casos de teste fornecidos" . No entanto, deixarei esta resposta como está, como um exemplo da brecha. Sinta-se livre para votar. Eu não vou me machucar.
Isso codifica uma célula por vez na ordem de varredura e, para cada célula, descarta seu valor adequadamente para as células subseqüentes, usando as regras básicas do Sudoku. Assim, por exemplo, quando uma célula é codificada e tem apenas quatro possibilidades, um dígito base 4 é adicionado ao número inteiro grande. Ele também codifica os casos de teste diretamente como números inteiros pequenos, ainda compactando e descompactando corretamente todas as placas Sudoku válidas com um comprimento médio comprimido de ~ 12,5 caracteres, 1,5 a mais do que o ideal 11.035, com código relativamente simples e sem o uso de um solucionador de Sudoku.
Casos de teste codificados:
Isso não resulta em codificação perfeita (média ~ 11), pois as regras básicas não descartam algumas opções para as quais, de fato, não há solução. O desempenho pode ser perfeito (ou seja, o número inteiro grande sempre seria menor que o número possível de placas Sudoku), verificando se não há solução para algumas das opções atuais usando um solucionador de Sudoku e eliminando-as também.
fonte
J, 254 pontos
Compressão DescompressãoA E / S padrão é um pouco desajeitada em J, uma vez que
jconsole
é realmente um REPL, então tomei a liberdade de gravar a saída compactada no arquivo.Localiza o índice anagrama de cada linha, trata os nove números resultantes como um número base (9!) E, finalmente, converte-o na base-95, adiciona 32 e converte-o em ASCII, como na solução de Martin Büttner. O índice de anagramas de uma permutação de 1n é simplesmente o índice da permutação na lista lexicamente classificada de todas essas permutações, por exemplo,
5 4 3 2 1
possui o índice de anagramas 5! - 1 = 119 .Todas as operações têm inversões fáceis, então a descompressão é simples.
Como um bônus, os exemplos estão em um formato muito amigável para J, portanto, a entrada / saída para sudokus descompactado é exatamente a mesma apresentada nos exemplos (embora a entrada para o codificador exija uma nova linha à direita).
Cordas compactadas para as caixas de teste:
fonte
Python 3, 120 pontos
Este programa lista todos os blocos 3x3 possíveis e lembra qual deles estava realmente presente no Sudoku original e, em seguida, reúne todos esses números em uma representação da base 95. Embora isso esteja muito próximo da codificação, ele comprime e descompacta os exemplos em cerca de 5 segundos cada um na minha máquina.
As principais funções são
compress(sudoku)
edecompress(text)
.Saídas:
fonte
Python 2.5, 116 pontos
Código:
Resultados:
Muito devagar. Levou 517 segundos para executar e verificar na minha máquina.
O encconfig pega uma placa sudoku e um dígito de 1 a 9, lista as coordenadas xy onde esse dígito aparece e gera um número no intervalo (6 ** 6) que representa essas coordenadas. (a "configuração de dígitos")
decconfig é a função reversa. É necessário um número no intervalo (6 ** 6), um dígito e um quadro de sudoku (o padrão é esvaziar). Emite a placa sudoku sobreposta à configuração de dígitos. Se uma das posições na configuração de dígitos já estiver ocupada no quadro de sudoku inserido, o dígito nessa posição será substituído pelo novo dígito.
compatible pega uma placa sudoku e uma configuração de dígitos (definida por conf e dig), sobrepõe a configuração de dígitos sobre a placa sudoku e verifica se há conflitos. Em seguida, retorna Verdadeiro ou Falso, dependendo do resultado.
codificar é a função de compactação. Ele pega uma placa sudoku e gera um número que a representa. Isso é feito primeiro copiando as posições dos 1s para um tabuleiro vazio e fazendo uma lista de todas as configurações do número 2 que são compatíveis com a configuração 1 (que não ocupam nenhum dos lugares já ocupados pelo 1's). Ele encontra a ordem da configuração 2 real da placa na lista e a armazena, depois copia essa configuração na nova placa, que agora contém apenas os 1 e 2. Em seguida, lista todas as configurações do número 3 que são compatíveis com as posições dos 1 e 2 e assim por diante.
decodificar é a função reversa.
Python 2.5.
fonte
C #, 150 bytes
Saída comprimida:
Como funciona:
Ele gera todas as permutações possíveis de 123456789 e as lembra. Em seguida, compara as permutações com as linhas do sudoku. Quando uma permutação correspondente para uma linha de doação é encontrada, ele se lembra do índice dessa permutação. Após cada linha, ele removerá todas as permutações onde houver pelo menos um caractere na mesma posição da linha atual. Isso garante que cada número seja único em sua coluna. Depois, remove todas as permutações que não funcionam mais de acordo com os critérios da caixa. Como a última linha é trivial, gera 8 números. Testei qual seria o valor máximo de cada um desses números e gerei uma máscara de contagem de dígitos para cada posição deles. {6, 5, 3, 5, 3, 1, 2, 1, 1}. O primeiro é obviamente o mais longo, com 362880 permutações. Usando a digitmask, construo um BigInteger com um 1 à esquerda para torná-lo com 28 dígitos. Isso resulta em um total de 11 bytes. Em seguida, esses bytes são convertidos em base64. Para salvar um caractere, removo o sinal = no final.
A reconstrução funciona de forma semelhante.
Ele reconstrói o BigInteger a partir da string base64 e depois o transforma em uma string novamente e a divide novamente usando a máscara de contagem de dígitos mencionada. Essas cadeias são analisadas de volta para os índices.
Em seguida, o algoritmo faz quase o mesmo; em vez de encontrar a linha nas permutações, apenas usa o índice para obter a linha, o resto funciona da mesma maneira.
Provavelmente isso poderia ser um pouco melhor para realmente usar os 94 caracteres possíveis em vez de apenas 64, mas não tenho o brainz para fazer isso.
Fonte : Copie e cole para fazer rodar com os 10 exemplos. .dotNet-Fiddle me diz que isso excede o limite de memória, portanto você precisa executá-lo em sua máquina para enviar texto.
fonte
Perl - 290 caracteres = 290 pontos
Este programa não usa codificação embutida e compacta de maneira confiável uma grade com exatamente 29 caracteres (teoricamente, seria possível encontrar alguns menores).
Veja como funciona:
Primeiro converta a matriz 9 x 9 em 60 números. Isso pode ser feito, pois a última coluna, a última linha e o quadrado final de cada célula 3 x 3 podem ser eliminados.
Em seguida, converta usando bigint em um único número inteiro, usando 9 ^ 60 elementos.
Em seguida, converta o bigint para a base 95.
Compressor e descompressor:
fonte
PHP, 214
Essa solução limpa primeiro a coluna direita e a linha inferior, bem como o canto inferior direito de cada bloco 3x3. Em seguida, tenta limpar uma célula. Se existir uma solução simples, a célula permanecerá em branco.
Em seguida, a grade do sudoku é formatada em uma sequência de caracteres da esquerda para a direita e de cima para baixo, excluindo a coluna direita, a linha inferior e o canto inferior direito. Os zeros à esquerda são contados (que sejam
z
) e removidos. Os zeros à direita também são removidos.A cadeia de caracteres é formatada em um número inteiro base 10, 11 ou 12 (seja essa base
b
),A
representando dois zeros eB
três.Isso é convertido em um número inteiro base-95 e precedido pelo dígito base-95 que representa
z << 2 | (b - 10)
.Ligar
php sudoku-compress.php enc
para codificar ephp sudoku-compress.php dec
decodificar. O codificador assume o formato fornecido na pergunta, com uma nova linha obrigatória à direita.Saídas de teste:
fonte
Java, 330 Pontos
Antes de ser ridicularizado por uma pontuação tão alta, deixe-me esclarecer que tentei resolver isso de uma maneira diferente, sabendo que provavelmente não seria tão ideal quanto algumas das melhores respostas aqui. Fiquei mais ou menos curioso para me aproximar e, para minha surpresa, não percebi o quão pior seria. Aqui está o resumo da minha abordagem aqui:
Desenvolva um algo para resolver um quebra-cabeça Sudoku.
Desenvolver um algo embaralhado que ainda possa ser solucionado. Isso é feito de maneira aleatória, ao remover pistas que podem ser determinadas trivialmente antes da mão. Eu poderia chegar a cerca de 22 pistas de forma confiável antes que demorasse muito tempo.
Uma vez embaralhado, o quebra-cabeça pode ser representado por um trio de números inteiros de um dígito para cada pista, no meu caso 22 trigêmeos de 3. Pensei que eu pudesse combiná-los em um único número de 66 dígitos e então a base95 codificar isso, então eu tenho algo que pode ser facilmente decodificado.
A sequência codificada acabou sendo mais longa do que eu esperava, geralmente com cerca de 33 caracteres. Nesse ponto, tentei uma maneira alternativa do que usar o Java BigInteger, onde criei um grande número a partir de uma máscara de 81 bits representando as 81 células de uma grade em que 1 significa que existe uma pista para essa célula. Em seguida, combinei essa máscara de bit com representações de 4 bits de cada valor de célula em ordem seqüencial, arredondado para bytes e descobri que obtive aproximadamente o mesmo comprimento de sequência codificada após a codificação base95.
Então, basicamente, eu estou postando meu código, caso alguém esteja interessado em uma abordagem diferente que não funcionou tão bem.
Class Puzz
Meu caso de teste
Saída de teste
fonte
C ++ 241, pontuação: 82 * 10 = 820
Adiciona '!' ao início da cadeia codificada para determinar qual operação executar.
Golfe 241 caracteres
312 caracteres não jogados
fonte