Podemos representar um cubo de Rubik como uma rede da seguinte maneira (quando resolvido):
WWW
WWW
WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
YYY
YYY
YYY
Cada letra representa a cor correspondente ( W
é branca, G
verde etc.)
Foi demonstrado que existem exatamente (~ quintilhões) permutações diferentes nas quais um cubo de Rubik pode estar.
Sua tarefa é pegar um número inteiro entre e e gerar a permutação correspondente, da maneira mostrada acima. Você pode escolher como as permutações são ordenadas, mas o algoritmo usado deve ser mostrado para gerar uma permutação exclusiva e correta para cada entrada possível.
Regras de permutação inválidas
Retirado desta página
Para começar, o centro de cada face 3x3 deve permanecer o mesmo, pois o quadrado central no cubo de Rubik não pode ser girado. O cubo inteiro pode ser girado, mudando onde uma face parece estar, mas isso não afeta a rede do cubo.
Se dissermos que cada permutação tem paridade, com base na paridade do número de swaps para atingir essa permutação, podemos dizer
Cada peça de canto tem três orientações possíveis. Pode ser orientado corretamente (0), no sentido horário (1) ou no sentido anti-horário (2). A soma das orientações dos cantos sempre permanece divisível por 3
Cada rotação legal no Cubo de Rubik sempre vira um número par de arestas, portanto não pode haver apenas uma peça orientada incorretamente.
Considerando a permutação de todos os cantos e arestas, a paridade geral deve ser uniforme, o que significa que cada movimento legal sempre executa o equivalente a um número par de trocas (ignorando a orientação)
Por exemplo, as três redes a seguir são saídas inválidas:
WWW
WWW
WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
YYY
YYY
YYY
(Too many whites/not enough reds)
WRW
WRW
WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
YYY
GGY
YYY
(There are two red/green center squares and no white/yellow center squares.
In all valid permutations, the center squares are all different colours)
WWW
WWW
WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBOYOO
YYY
YYY
YYB
(The yellow/orange/blue corner is rotated into an impossible permutation)
Regras
- Você deve provar, da maneira que desejar, que o algoritmo é válido. Você não precisa enumerar todas as permutações, desde que prove a validade do seu algoritmo.
- Você deve incluir algum tipo de prova de validade em sua resposta. Essa prova pode provar a validade de qualquer método de prova aceito, exceto para enumerar todas as possibilidades.
- Você pode optar por usar um método de entrada alternativo, se desejar, desde que:
- A entrada é limitada
- Cada entrada corresponde a uma saída única
- Você explica claramente o formato de entrada e como ele corresponde a cada saída
- Você pode alterar os caracteres usados para usar 6 caracteres ASCII diferentes, entre 33 (
!
) e 126 (~
), em vez deWGRBOY
- Você pode produzir da maneira que desejar, contanto que forme uma representação clara de um cubo onde todas as 6 faces possam ser exibidas, incluindo qualquer rede de cubos válida, uma única linha alinhada ou uma renderização em 3D. Se você não tiver certeza sobre um formato específico, não hesite em perguntar nos comentários.
Este é um código-golfe, portanto o código mais curto, em bytes, em cada idioma vence.
Exemplo de saídas válidas
YYY
YYY
YYY
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
WWW
WWW
WWW
(The `W` and `Y` faces have been swapped)
ZZZ
+++
+}}
+[[}77ZZ7bbb
bb[}[[7}}+Z7
bb[}++[}}+Z7
7bb
[7Z
[7Z
(To start with, the colours have been mapped W -> +, G -> b, R -> [, B -> }, O -> Z and Y -> 7.
Then, the moves L, R, U and F' have been applied, in that order.
Notice that each centre square is different, and corresponds to the same colour as in the mapping)
fonte
Respostas:
Carvão ,
334297 bytesExperimente online! Link é a versão detalhada do código. Explicação:
Entrada o número inteiro na variável
q
.Divida
q
por 3⁷, colocando o restantee
. Então, considerandoe
como um número na base 3, coloque um dígito no sufixo parae
que seus dígitos (na base 3) totalizem um múltiplo de 3. Isso permitee
definir as rotações dos cantos.Divida
q
por 8 !, colocando o restantez
. (8! É armazenado temporariamented
para salvar um byte.) Isso permitez
definir as posições dos cantos.Divida
q
por 2¹¹, colocando o restanteh
. Então, considerandoh
como um número na base 2, coloque um dígito no sufixo parah
que seus dígitos (na base 2) totalizem um múltiplo de 2. Isso permiteh
definir as inversões das arestas.Faça um loop sobre uma representação em cadeia dos centros.
Pule para a posição de cada centro e imprima-a.
Acompanhe a paridade das posições dos cantos na variável
w
.Crie uma matriz de posições de canto.
Crie uma matriz de cores de canto.
Faça um loop duas vezes, uma vez para cantos, uma vez para bordas, a seguir denominados "cubos".
Faça um loop sobre a matriz de cores do cubo.
Extraia a próxima posição do cubo
z
, atualizando a paridade emw
. Use essa paridade para a última mas uma aresta. Isso garante que a soma da paridade das arestas e cantos seja uniforme.Imprima o cubo nessa posição, ajustado para a próxima rotação ou gire conforme apropriado.
Remova a rotação ou inverta
e
.Crie uma matriz de posições da aresta. Isso será usado pela segunda vez no loop.
Crie uma matriz de cores de borda.
Substituir as variáveis de canto
z
ee
com as variáveis bordo correspondenteq
eh
de modo que as bordas são permutadas e invertidas durante a segunda passagem do loop.fonte
Ruby ,
570408 bytesExperimente online!
Versão original, com matrizes de números mágicos em vez de cordas mágicas
Experimente online!
Uma função anônima que, na sua forma atual, recebe uma entrada de dois números inteiros, o que parece ser permitido: "você pode escolher um método de entrada alternativo". O primeiro é a permutação no intervalo de 0 a
12!*8!/2 - 1
e o segundo é a orientação das peças no intervalo de 0 a2**11 * 3*7 - 1
. A saída no estado resolvido é a seguinte sequência:Golfe adicional
Existem aproximadamente 10 caracteres a serem salvos ajustando o formato de saída para a seguinte forma. Mas isso reduziria a legibilidade, então não o farei no momento
Explicação
Permutação
Internamente, o estado resolvido é representado pela série de números octais na matriz
a
. A entradag
é dividida pelos números12..1
com o módulo sendo usado para selecionar e remover uma arestaa
e inseri-laz
. Uma vez feito isso, apenas os cantos permanecema
, entãog
é dividido pelos números8..1
com o módulo sendo usado para remover um cantoa
e colocá-lo emz
.Como não há informações suficientes para determinar a ordem dos dois últimos cantos, o valor de
g
será dividido em zero no momento em que os atingir, para que eles sempre sejam adicionados àz
ordem original. Uma verificação é feita para determinar se a permutação geral é par ou ímpar e, se necessário, os dois últimos cantos são trocados para tornar a permutação uniforme.Orientação
Existem várias maneiras diferentes de decidir se um canto ou aresta está na orientação correta, se não estiver em seu local resolvido. Para os fins desta resposta, um canto é considerado em sua orientação correta se aparecer
0
ou1
na face superior ou inferior. Portanto, girar a face superior ou inferior não altera a orientação do canto. Girar as outras faces altera a orientação, mas de maneira que a soma da paridade geral permaneça inalterada. As arestas são consideradas na orientação correta se mostrarem a2
ou4
para a frente / trás ou a3
ou5
para a esquerda / direita. Isso significa que a rotação da parte superior ou inferior em um quarto de volta vira as quatro arestas, mas a rotação das outras faces mantém o status de inversão inalterado.A entrada contém informações explícitas para todos, exceto a primeira aresta e o último canto. Os 11 bits menos significativos
h%2048
são somados e o módulo usado para determinar a orientação da primeira aresta.h
é multiplicado por 2 adicionando-o a si mesmo e o valor para a orientação da primeira aresta é adicionado como o bit menos significativo. A orientação do último canto é encontrada subtraindo progressivamente a orientação dos outros cantos dej
. Para o último canto (ondei/19
=1
) o valor dej%3
é adicionado ah
(que será reduzido a zero) e isso determina a orientação do último canto.A sequência
b
é pré-inicializada com o texto para os centros das faces.h
é dividido por2
doze vezes e depois por3
oito, com os módulos utilizados para determinar a orientação das peças. Em cada caso, o número inz
é convertido em uma sequência com o número apropriado de dígitos (2 ou 3) e a sequência é duplicada. Isso permite que a rotação correta dos dígitos, conforme encontrada pelo módulo, seja extraída da string por indexação e anexada ab
Exibição
Por fim, os adesivos brutos são copiados
b
para um formato legível por humanos,s
usando os números mágicos na tabela de índice.fonte