A idéia para esse desafio de código é simples: dada uma matriz de números inteiros, vamos classificá-la aplicando movimentos no estilo Rubik. Isso significa que você pode selecionar uma única linha ou coluna e girar seus elementos em qualquer direção:
[1, 3, 2, 4] => [3, 2, 4, 1] (rotate left for rows/up for columns)
[1, 3, 2, 4] => [4, 1, 3, 2] (rotate right for rows/down for columns)
Portanto, dada uma matriz de números inteiros de qualquer dimensão, classifique seus elementos aplicando apenas essas transformações no estilo Rubik. Uma matriz
será considerado classificado se seus elementos estiverem em conformidade com a seguinte restrição:
I / O
- A entrada será uma matriz de números inteiros positivos sem valores repetidos.
- Saída serão os movimentos necessários para classificá-la. Como esse não é um desafio de código de golfe e você não precisa se preocupar com o tamanho, o formato proposto para cada movimento é
#[UDLR]
onde#
está o número da linha ou coluna a ser movida (indexada a 0) e[UDLR]
é um caractere único nesse intervalo que especifica se o movimento é Para cima / Para baixo (para colunas) ou Esquerda / Direita (para linhas). Isso1U
significa "mover a 1ª coluna para cima", mas1R
"mover a 1ª linha para a direita". Movimentos serão separados por vírgulas, de modo que uma solução será expressa como este:1R,1U,0L,2D
.
Pontuação
Tentar classificar uma matriz dessa maneira pode ser caro, pois existem muitas combinações possíveis de movimentos e também existem muitas listas possíveis de movimentos que podem classificá-lo, portanto, o objetivo é escrever um código que classifique o N * N matrizes abaixo. A pontuação será o maior tamanho N que você pode resolver em um período razoável de tempo 1 sem erros (quanto maior o tamanho da matriz resolvida, melhor). Em caso de empate, o desempate será o número de movimentos no caminho encontrado (quanto menor o caminho, melhor).
Exemplo: se um usuário A encontrar uma solução para N = 5 e B encontrar uma solução para N = 6, B vencerá independentemente do comprimento dos dois caminhos. Se ambos encontrarem soluções para N = 6, mas a solução encontrada por A tiver 50 etapas e a solução de B tiver 60 etapas, A vencerá.
As explicações sobre como seu código funciona são altamente incentivadas e publique as soluções encontradas para que possamos testá-las . Você pode usar Pastebin ou ferramentas semelhantes se as soluções forem muito grandes. Além disso, será apreciada uma estimativa do tempo gasto pelo seu código para encontrar suas soluções.
Casos de teste
As seguintes matrizes ( link Pastebin para uma versão mais passível de cópia) foram criadas a partir de matrizes já classificadas, embaralhando-as com movimentos aleatórios de 10K no estilo Rubik:
Casos de Teste de Texto Simples:
[[8, 5, 6], [11, 10, 1], [3, 15, 13]]
[[21, 10, 12, 16], [17, 6, 22, 14], [8, 5, 19, 26], [13, 24, 3, 1]]
[[1, 13, 8, 16, 5], [9, 40, 21, 26, 22], [11, 24, 14, 39, 28], [32, 19, 37, 3, 10], [30, 17, 36, 7, 34]]
[[34, 21, 40, 22, 35, 41], [18, 33, 31, 30, 12, 43], [19, 11, 39, 24, 28, 23], [44, 1, 36, 5, 38, 45], [14, 17, 9, 16, 13, 26], [8, 3, 47, 6, 25, 4]]
[[20, 36, 17, 1, 15, 50, 18], [72, 67, 34, 10, 32, 3, 55], [42, 43, 9, 6, 30, 61, 39], [28, 41, 54, 27, 23, 5, 70], [48, 13, 25, 12, 46, 58, 63], [52, 37, 8, 45, 33, 14, 68], [59, 65, 56, 73, 60, 64, 22]]
[[85, 56, 52, 75, 89, 44, 41, 68], [27, 15, 87, 91, 32, 37, 39, 73], [6, 7, 64, 19, 99, 78, 46, 16], [42, 21, 63, 100, 4, 1, 72, 13], [11, 97, 30, 93, 28, 40, 3, 36], [50, 70, 25, 80, 58, 9, 60, 84], [54, 96, 17, 29, 43, 34, 23, 35], [77, 61, 82, 48, 2, 94, 38, 66]]
[[56, 79, 90, 61, 71, 122, 110, 31, 55], [11, 44, 28, 4, 85, 1, 30, 6, 18], [84, 43, 38, 66, 113, 24, 96, 20, 102], [75, 68, 5, 88, 80, 98, 35, 100, 77], [13, 21, 64, 108, 10, 60, 114, 40, 23], [47, 2, 73, 106, 82, 32, 120, 26, 36], [53, 93, 69, 104, 54, 19, 111, 117, 62], [17, 27, 8, 87, 33, 49, 15, 58, 116], [95, 112, 57, 118, 91, 51, 42, 65, 45]]
Por favor, peça mais se você resolver todos eles. :-) E muito obrigado às pessoas que me ajudaram a refinar esse desafio enquanto estavam na sandbox .
1 Uma quantidade razoável de tempo: qualquer quantidade que não comprometa nossa paciência durante o teste de sua solução. Observe que o TIO executa o código apenas por 60 segundos; qualquer quantidade de tempo acima desse limite nos fará testar o código em nossas máquinas. Exemplo: meu algoritmo bastante ineficiente leva alguns milissegundos para resolver matrizes de ordem 3x3 e 4x4, mas eu o testei apenas com uma matriz 5x5 e demorou 317 segundos para resolvê-lo (em mais de 5 milhões de movimentos, muito engraçado se considerarmos que a matriz a resolver foi embaralhada apenas 10 mil vezes). Tentei reduzir o número de movimentos para menos de 10K, mas me rendi depois de 30 minutos executando o código.
O(input size)
? Para uma matriz 5x5 seriaO(25)
? Isso parece ser extremamente rápido, então eu ficaria muito interessado em ver esse algoritmo ou implementação seu. EDIT: Você percebe que inserimos a matriz 'codificada' e produzimos os movimentos, certo? Não o contrário.Respostas:
Nim
Experimente online!
Uma tentativa rápida de implementar o algoritmo da solução de quebra-cabeça Torus a partir de um artigo publicado nos Algorithms 2012, 5, 18-29 que mencionei nos comentários.
Aceita a matriz de entrada na forma achatada, como uma linha de números delimitados por espaço.
Aqui também está um validador no Python 2 . São necessárias duas linhas como entrada: a matriz codificada original da mesma forma que o código principal e a sequência de movimentos proposta. A saída do validador é a matriz resultante da aplicação desses movimentos.
Explicação
Na primeira parte do algoritmo, ordenamos todas as linhas, exceto a última.
proc triangle
Na Fig. 2, os autores apresentam 8 padrões possíveis e as seqüências correspondentes de movimentos, mas no meu código todos os casos foram realmente cobertos por apenas 5 padrões, de modo que não. 1, 5 e 6 não são usados.
Na segunda parte, a última linha, exceto os dois últimos elementos, é ordenada executando "rotações de três elementos" em uma linha (
proc line
), que consiste em duas rotações de triângulo cada (consulte a Fig. 3 do artigo).proc swap
Atualização: Adicionado novo
proc rotations
que reverte a direção dos movimentos, se isso resultar em menos etapas.fonte
7L,7L,7L,7L,7D,7D,7D,7D
que pode ser reduzido e o8R,8R,8R,8R,8R,8R,8R
que pode ser convertido8L,8L
para uma matriz 9x9.Python 2 , tamanho 100 em <30 segundos no TIO
Experimente online! O link inclui três pequenos casos de teste com saída de movimentação completa, além de um teste silencioso de 100x100 para mostrar que o código funciona (a saída de movimentação excederia os limites do TIO). Explicação: O código tenta executar uma classificação de inserção na matriz, construindo-a em ordem crescente à medida que avança. Para todas as linhas, exceto a última linha, há vários casos:
As rotações acima são realizadas em qualquer direção, minimizando o número de etapas; um quadrado tamanho 2 é sempre resolvido usando movimentos para a esquerda e para cima, independentemente da descrição acima.
Antes de a linha inferior ser concluída, ela é rotacionada para minimizar a distância total fora do lugar, mas também para garantir que a paridade da linha inferior seja uniforme, pois não pode ser alterada pela parte final do algoritmo. Se houver mais de uma rotação com a mesma distância mínima, é escolhida a rotação com o menor número de movimentos.
O algoritmo para a linha inferior baseia-se em uma sequência de 7 operações que troca os elementos em três colunas. A sequência é aplicada a cada um dos números restantes da linha inferior para, por sua vez, trazê-los para o local desejado; se possível, o elemento nesse local é movido para o local desejado, mas se for necessária uma troca direta, o elemento é simplesmente movido para a coluna disponível mais próxima, esperançosamente permitindo que seja corrigido da próxima vez.
fonte