No jogo Flood Paint, o objetivo do jogo é fazer com que todo o tabuleiro fique da mesma cor no menor número de turnos possível.
O jogo começa com um quadro que se parece com isso:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 3[3]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
Atualmente, o número (representando uma cor) no centro do tabuleiro é 3. A cada turno, o quadrado no centro muda de cor e todos os quadrados da mesma cor que são alcançáveis a partir do centro, movendo-se horizontal ou verticalmente ( ou seja, na região de inundação da praça central) mudará de cor com ela. Portanto, se o quadrado central mudar de cor para 5:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 5[5]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
então o 3 que estava à esquerda do centro 3 também mudará de cor. Agora há um total de sete 5 alcançáveis a partir do centro e, portanto, se mudarmos de cor para 4:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 4 4 4 4 1 4
6 2 4 4[4]1 1 6 6
5 5 1 2 4 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
a região pintada aumenta novamente de tamanho dramaticamente.
Sua tarefa é criar um programa que use uma grade de 19 por 19 cores de 1 a 6 como entrada, na forma que você escolher:
4 5 1 1 2 2 1 6 2 6 3 4 2 3 2 3 1 6 3
4 2 6 3 4 4 5 6 4 4 5 3 3 3 3 5 4 3 4
2 3 5 2 2 5 5 1 2 6 2 6 6 2 1 6 6 1 2
4 6 5 5 5 5 4 1 6 6 3 2 6 4 2 6 3 6 6
1 6 4 4 4 4 6 4 2 5 5 3 2 2 4 1 5 2 5
1 6 2 1 5 1 6 4 4 1 5 1 3 4 5 2 3 4 1
3 3 5 3 2 2 2 4 2 1 6 6 6 6 1 4 5 2 5
1 6 1 3 2 4 1 3 3 4 6 5 1 5 5 3 4 3 3
4 4 1 5 5 1 4 6 3 3 4 5 5 6 1 6 2 6 4
1 4 2 5 6 5 5 3 2 5 5 5 3 6 1 4 4 6 6
4 6 6 2 6 6 2 4 2 6 1 5 6 2 3 3 4 3 6
6 1 3 6 3 5 5 3 6 1 3 4 4 5 1 2 6 4 3
2 6 1 3 2 4 2 6 1 1 5 2 6 6 6 6 3 3 3
3 4 5 4 6 6 3 3 4 1 1 6 4 5 1 3 4 1 2
4 2 6 4 1 5 3 6 4 3 4 5 4 2 1 1 4 1 1
4 2 4 1 5 2 2 3 6 6 6 5 2 5 4 5 4 5 1
5 6 2 3 4 6 5 4 1 3 2 3 2 1 3 6 2 2 4
6 5 4 1 3 2 2 1 1 1 6 1 2 6 2 5 6 4 5
5 1 1 4 2 6 2 5 6 1 3 3 4 1 6 1 2 1 2
e retorne uma sequência de cores que o quadrado central mudará a cada turno, novamente no formato de sua escolha:
263142421236425431645152623645465646213545631465
No final de cada sequência de movimentos, os quadrados na grade 19 por 19 devem ter a mesma cor.
Seu programa deve ser totalmente determinístico; Soluções pseudo-aleatórias são permitidas, mas o programa deve gerar sempre a mesma saída para o mesmo caso de teste.
O programa vencedor executará o menor número total de etapas para resolver todos os 100.000 casos de teste encontrados neste arquivo (arquivo de texto compactado, 14,23 MB). Se duas soluções seguirem o mesmo número de etapas (por exemplo, se ambas encontraram a estratégia ideal), o programa mais curto vencerá.
BurntPizza escreveu um programa em Java para verificar os resultados do teste. Para usar este programa, execute sua submissão e canalize a saída para um arquivo chamado steps.txt
. Em seguida, execute este programa com steps.txt
e o floodtest
arquivo no mesmo diretório. Se sua entrada for válida e produzir soluções corretas para todos os arquivos, ela deverá passar em todos os testes e retornarAll boards solved successfully.
import java.io.*;
import java.util.*;
public class PainterVerifier {
public static void main(String[] args) throws FileNotFoundException {
char[] board = new char[361];
Scanner s = new Scanner(new File("steps.txt"));
Scanner b = new Scanner(new File("floodtest"));
int lineNum = 0;
caseloop: while (b.hasNextLine()) {
for (int l = 0; l < 19; l++) {
String lineb = b.nextLine();
if (lineb.isEmpty())
continue caseloop;
System.arraycopy(lineb.toCharArray(), 0, board, l * 19, 19);
}
String line = s.nextLine();
if (line.isEmpty())
continue;
char[] steps = line.toCharArray();
Stack<Integer> nodes = new Stack<Integer>();
for (char c : steps) {
char targetColor = board[180];
char replacementColor = c;
nodes.push(180);
while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (board[n] == targetColor) {
board[n] = replacementColor;
if (n % 19 > 0)
nodes.push(n - 1);
if (n % 19 < 18)
nodes.push(n + 1);
if (n / 19 > 0)
nodes.push(n - 19);
if (n / 19 < 18)
nodes.push(n + 19);
}
}
}
char center = board[180];
for (char c : board)
if (c != center) {
s.close();
b.close();
System.out.println("\nIncomplete board found!\n\tOn line " + lineNum + " of steps.txt");
System.exit(0);
}
if (lineNum % 5000 == 0)
System.out.printf("Verification %d%c complete...\n", lineNum * 100 / 100000, '%');
lineNum++;
}
s.close();
b.close();
System.out.println("All boards solved successfully.");
}
}
Além disso, um placar, já que os resultados não são realmente classificados por pontuação e aqui isso realmente importa muito:
- 1.985.078 - smack42, Java
- 2.075.452 - usuário1502040, C
- 2.098.382 - tigrou, C #
- 2.155.834 - CoderTao, C #
- 2.201.995 - MrBackend, Java
- 2.383.569 - CoderTao, C #
- 2.384.020 - Herjan, C
- 2.403.189 - Origineil, Java
- 2.445.761 - Herjan, C
- 2.475.056 - Jeremy List, Haskell
- 2.480.714 - SteelTermite, C (2.395 bytes)
- 2.480.714 - Herjan, Java (4.702 bytes)
- 2.588.847 - BurntPizza, Java (2.748 bytes)
- 2.588.847 - Gero3, node.js (4.641 bytes)
- 2.979.145 - Teun Pronk, Delphi XE3
- 4.780.841 - BurntPizza, Java
- 10.800.000 - Joe Z., Python
Respostas:
Java - 1.985.078 etapas
https://github.com/smack42/ColorFill
Outra entrada tardia. O arquivo de resultados que contém as 1.985.078 etapas pode ser encontrado aqui .
Algumas informações básicas:
Eu descobri esse desafio alguns anos atrás, quando comecei a programar meu próprio clone do jogo Flood-it.
Algoritmo DFS e A * "melhor do que incompleto"
Desde o início, eu queria criar um bom algoritmo de resolução para este jogo. Com o tempo, pude melhorar meu solucionador incluindo várias estratégias que faziam pesquisas incompletas diferentes (semelhantes às usadas nos outros programas aqui) e usando o melhor resultado dessas estratégias para cada solução. Até reimplementei o algoritmo A * do tigrou em Java e o adicionei ao meu solucionador para obter soluções melhores em geral do que o resultado do tigrou.
exaustivo algoritmo DFS
Então me concentrei em um algoritmo que sempre encontra as soluções ideais. Eu gastei muito esforço para otimizar minha estratégia exaustiva de busca em profundidade. Para acelerar a pesquisa, incluí um mapa de hash que armazena todos os estados explorados, para que a pesquisa possa evitá-los novamente. Embora esse algoritmo funcione bem e resolva todos os quebra-cabeças de 14x14 com rapidez suficiente, ele usa muita memória e corre muito lentamente com os quebra-cabeças de 19x19 neste desafio de código.
Algoritmo Puchert A *
Há alguns meses, fui contactado por Aaron e Simon Puchert para resolver o problema do Flood-It . Esse programa usa um algoritmo do tipo A * com uma heurística admissível (em contraste com a de tigrou) e move a poda de maneira semelhante à pesquisa por ponto de salto. Percebi rapidamente que este programa é muito rápido e encontra as soluções ideais !
Obviamente, tive que reimplementar esse ótimo algoritmo e adicioná-lo ao meu programa. Fiz um esforço para otimizar meu programa Java para rodar tão rápido quanto o programa C ++ original dos irmãos Puchert. Então decidi tentar os 100.000 casos de teste desse desafio. Na minha máquina, o programa funcionou por mais de 120 horas para encontrar as etapas de 1.985.078, usando minha implementação do algoritmo Puchert A * .
Essa deve ser a melhor solução possível para esse desafio, a menos que haja alguns erros no programa que resultem em soluções abaixo do ideal. Qualquer feedback é bem-vindo!
edit: adicionou partes relevantes do código aqui:
classe AStarPuchertStrategy
parte da classe AStarSolver
parte da classe AStarNode
fonte
C # - 2.098.382 etapas
Eu tento muitas coisas, a maioria delas falha e simplesmente não funcionou até recentemente. Eu tenho algo interessante o suficiente para postar uma resposta.
Certamente, existem maneiras de melhorar isso ainda mais. Acho que é possível seguir os passos de 2 milhões.
Demorou aproximadamente
7 hours
para gerar resultados. Aqui está um arquivo txt com todas as soluções, caso alguém queira vê-las: results.zipMais detalhes sobre como funciona:
Ele usa o algoritmo A * Pathfinding .
O difícil é encontrar um bom
heuristic
. Seheuristic
subestimar o custo, ele funcionará quase como o algoritmo Dijkstra e, devido à complexidade de uma placa 19x19 com 6 cores, será executada para sempre. Se superestimar o custo, convergirá rapidamente para uma solução, mas não dará bons resultados (algo como 26 movimentos foram 19 possíveis). Encontrar o perfeitoheuristic
que fornece a quantidade exata exata de etapas para alcançar a solução seria o melhor (seria rápido e forneceria a melhor solução possível). É (a menos que eu esteja errado) impossível. Na verdade, é necessário resolver primeiro o quadro, enquanto é isso que você está realmente tentando fazer (problema de galinha e ovo)Eu tentei muitas coisas, aqui está o que funcionou para o
heuristic
:node
um representa um conjunto de quadrados contíguos da mesma cor. Usando issograph
, posso calcular facilmente a distância mínima exata do centro para qualquer outro nó. Por exemplo, a distância do centro para o canto superior esquerdo seria 10, porque pelo menos 10 cores as separam.heuristic
: jogo o tabuleiro atual até o fim. Para cada etapa, escolho a cor que minimizará a soma das distâncias da raiz até todos os outros nós.O número de movimentos necessários para atingir esse fim é o
heuristic
.Estimated cost
(usado por A *) =moves so far
+heuristic
Não é perfeito, pois superestima um pouco o custo (portanto, é encontrada uma solução não ideal). De qualquer forma, é rápido calcular e fornecer bons resultados.
Consegui obter uma grande melhoria de velocidade usando o gráfico para executar todas as operações. No começo, eu tinha uma
2-dimension
matriz. Eu a inundo e recalculo o gráfico quando necessário (por exemplo: para calcular a heurística). Agora tudo é feito usando o gráfico, calculado apenas no início. Para simular etapas, o preenchimento de inundação não é mais necessário; em vez disso, mesclo nós. Isso é muito mais rápido.fonte
code blocks
para enfatizar o texto. Temos itálico e negrito para isso.Python - 10.800.000 etapas
Como uma solução de referência de último local, considere esta sequência:
Andar de bicicleta por todos os
n
tempos das cores significa que todos osn
passos quadrados terão a mesma cor que o quadrado central. Cada quadrado fica a no máximo 18 passos do centro, então 18 ciclos garantirão que todos os quadrados sejam da mesma cor. Provavelmente, terminará em menos que isso, mas o programa não precisa parar assim que todos os quadrados tiverem a mesma cor; é apenas muito mais benéfico fazer isso. Esse procedimento constante é de 108 etapas por caso de teste, para um total de 10.800.000.fonte
1 2 3 4 5 6 ...
vez de sua solução atual que dá123456...
.Java - 2.480.714 etapas
Cometi um pequeno erro antes (coloquei uma frase crucial antes de um loop em vez de no loop:
fonte
C - 2.075.452
Sei que estou extremamente atrasado para a festa, mas vi esse desafio e queria experimentar.
O algoritmo é baseado na Pesquisa em árvore Monte-Carlo com amostragem Thompson e em uma tabela de transposição para reduzir o espaço de pesquisa. Demora cerca de 12 horas na minha máquina. Se você deseja verificar os resultados, pode encontrá-los em https://dropfile.to/pvjYDMV .
fonte
hash ^= zobrist_table[i][(int)solution[i]];
parahash ^= zobrist_table[i%len][(int)solution[i]];
para corrigir a falha do programa.Java -
2.434.1082.588.847 etapasAtualmente vencendo (~ 46K à frente de Herjan) em 26/4Welp, o MrBackend não apenas me derrotou, como também encontrei um bug que produzia uma pontuação enganosamente boa. Está consertado agora (também estava no verificador! Ack), mas infelizmente não tenho tempo no momento para tentar recuperar a coroa. Tentará mais tarde.
Isso se baseia na minha outra solução, mas, em vez de pintar com a cor mais comum nas bordas de preenchimento, pinta com a cor que resultará na exposição de bordas com muitos quadrados adjacentes da mesma cor. Chame de LookAheadPainter. Vou jogar depois, se necessário.
EDIT: escrevi um verificador, sinta-se à vontade para usá-lo, ele espera um arquivo steps.txt contendo as etapas que o seu programa produz, bem como o arquivo floodtest: Edit-Edit: (Veja OP)
Se alguém encontrar um problema, informe-o!
fonte
C - 2.480.714 etapas
Ainda não é o ideal, mas agora é mais rápido e tem melhor pontuação.
fonte
Java -
2.245.5292.201.995 etapasPesquisa em árvore paralela e em cache na profundidade 5, minimizando o número de "ilhas". Como a melhoria da profundidade 4 para a profundidade 5 foi muito pequena, acho que não há muito sentido em melhorar muito mais. Mas, se precisar de melhorias, meu instinto diz trabalhar com o cálculo do número de ilhas como uma diferença entre dois estados, em vez de recalcular tudo.
Atualmente, gera para stdout, até eu conhecer o formato de entrada do verificador.
fonte
24
que resultaria em um tempo de execução muito mais eficiente.Minha última entrada: C - 2.384.020 etapas
Desta vez, uma opção de 'verificar todas as possibilidades' ... Essa pontuação é obtida com a profundidade definida em 3. A profundidade 5 deve fornecer ~ 2,1 milhões de passos ... MUITO LENTO. O Depth 20+ fornece a menor quantidade de etapas possível (apenas verifica todas as partidas e as vitórias mais curtas) ... Tem a menor quantidade de etapas, embora eu odeie, já que é apenas um pouquinho melhor, mas o desempenho é uma merda. Eu prefiro minha outra entrada C, que também está neste post.
Outra IA aprimorada escrita em C - 2.445.761 etapas
Baseado no SteelTermite:
fonte
Java -
2.610.7974.780.841 etapas(Fill-Bug corrigido, a pontuação agora é drasticamente pior -_-)
Esta é a submissão do meu algoritmo de referência básico, simplesmente cria um histograma dos quadrados nas bordas da área pintada e pinta com a cor mais comum. Executa os 100k em alguns minutos.
Obviamente não vai ganhar, mas certamente não é o último. Provavelmente farei outra submissão para coisas inteligentes. Sinta-se livre para usar esse algoritmo como ponto de partida.
Remova o comentário das linhas comentadas para a saída completa. O padrão é imprimir o número de etapas executadas.
Golfe a 860 caracteres (sem incluir as novas linhas de formatação), mas poderia ser mais reduzido se eu quisesse:
fonte
Haskell - 2.475.056 etapas
O algoritmo é semelhante ao sugerido por MrBackend nos comentários. A diferença é: sua sugestão encontra o caminho mais barato para o quadrado do custo mais alto, o meu avidamente reduz a excentricidade do gráfico a cada passo.
fonte
C # - 2.383.569
É um percurso profundo de possíveis soluções que escolhe aproximadamente o caminho da melhor melhoria (semelhante / mesmo que a entrada C de Herjan), exceto que eu inverti inteligentemente a ordem de geração de soluções candidatas depois de ver a Herjan postar os mesmos números. Demora mais de 12 horas a correr.
fonte
Java - 2.403.189
Esta deveria ser minha tentativa de uma força bruta. Mas! Minha primeira implementação da escolha "melhor" de profundidade única rendeu:
O código usado para ambos é o mesmo com a força bruta armazenando um "instantâneo" dos outros movimentos possíveis e executando o algoritmo sobre todos eles.
Se estiver sendo executado com a abordagem "multi", ocorrerão falhas aleatórias. Eu configurei as 100 primeiras entradas do quebra-cabeça em um teste de unidade e posso obter 100% de aprovação, mas não 100% do tempo. Para compensar, apenas acompanhei o número do quebra-cabeça atual no momento da falha e iniciei um novo Thread pegando onde o último parou. Cada thread gravou seus respectivos resultados em um arquivo. O conjunto de arquivos foi condensado em um único arquivo.
Node
representa um bloco / quadrado do quadro e armazena uma referência a todos os seus vizinhos. Acompanhe trêsSet<Node>
variáveis:Remaining
,Painted
,Targets
. Cada iteração procuraTargets
agrupar todos oscandidate
nós por valor, selecionandotarget value
o número de nós "afetados". Esses nós afetados tornam-se os destinos para a próxima iteração.A fonte está espalhada por muitas classes e os snippets não são muito significativos longe do contexto do todo. Minha fonte pode ser navegada via GitHub . Eu também brinquei com uma demonstração do JSFiddle para visualização.
No entanto, meu método de cavalo de batalha de
Solver.java
:fonte
C # -
2.196.4622.155.834Essa é efetivamente a mesma abordagem de 'procurar o melhor descendente' que meu outro solucionador, mas com algumas otimizações que apenas com paralelismo permitem que ela chegue à profundidade 5 em pouco menos de 10 horas. No decorrer do teste, também encontrei um bug no original, de modo que o algoritmo ocasionalmente pegava rotas ineficientes para o estado final (não era responsável pela profundidade dos estados com pontuação = 64; descoberto enquanto brincava com resultados de profundidade = 7)
A principal diferença entre esse e o solucionador anterior é que ele mantém os estados do jogo de inundação na memória, para que não precise regenerar 6 ^ 5 estados. Com base no uso da CPU durante a execução, tenho certeza de que isso mudou da CPU vinculada para a largura de banda da memória. Muito divertido. Tantos pecados.
Edit: Por razões, o algoritmo de profundidade 5 nem sempre produz o melhor resultado. Para melhorar o desempenho, vamos fazer as profundidades 5 ... e 4 ... e 3 e 2 e 1, e ver qual é o melhor. Raspou outros movimentos de 40k. Como a profundidade 5 é a maior parte do tempo, adicionar 4 a 1 apenas aumenta o tempo de execução de ~ 10 horas a ~ 11 horas. Yay!
fonte
Delphi XE3 2.979.145 etapas
Ok, então esta é a minha tentativa. Eu chamo a parte alterada de blob, a cada turno ele fará uma cópia da matriz e testará todas as cores possíveis para ver qual cor dará a maior blob.
Executa todos os quebra-cabeças em 3 horas e 6 minutos
Pensando em um método backtracing de força bruta também.
Talvez divertido para este fim de semana ^^
fonte
Javascript / node.js - 2.588.847
O algoritmo é um pouco diferente da maioria aqui, pois utiliza regiões pré-calculadas e estados de diferença entre os cálculos. É executado em menos de 10 minutos aqui se você estiver preocupado com a velocidade por causa do javascript.
fonte
Código C que é garantido para encontrar uma solução ideal por força bruta simples. Funciona para grades de tamanho arbitrário e todas as entradas. Leva muito, muito tempo para ser executado na maioria das grades.
O preenchimento é extremamente ineficiente e depende de recursão. Pode ser necessário aumentar sua pilha se for muito pequena. O sistema de força bruta usa uma string para armazenar os números e um add-to-carry simples para percorrer todas as opções possíveis. Isso também é extremamente ineficiente, pois repete a maioria dos passos quatrilhões de vezes.
Infelizmente, não pude testá-lo em todos os casos, pois vou morrer de velhice antes que termine.
Tanto quanto posso dizer, este é o atual vencedor. A competição exige que:
Verifica
Como sempre encontra o menor número de etapas para concluir todos os quadros e nenhum dos outros, atualmente está à frente. Se alguém puder criar um programa mais curto, poderá ganhar, então apresento a seguinte versão otimizada para o tamanho. A execução é um pouco mais lenta, mas o tempo de execução não faz parte das condições vencedoras:
fonte