Alice e Bob gostam de jogar um jogo de cartas, com um baralho numerado com números inteiros não negativos consecutivos.
Alice tem uma maneira muito particular de embaralhar o convés, no entanto. Primeiro, ela pega a carta do topo do baralho e a coloca no fundo do baralho. Então ela remove a próxima carta e começa uma pilha com ela. Então, novamente, ela muda a carta do topo para o fundo e coloca a nova carta do topo na pilha. Ela repete esse processo até esvaziar o baralho, quando a pilha é o novo baralho.
deck | pile
-----------+-----------
3 1 4 0 2 |
1 4 0 2 3 |
4 0 2 3 | 1
0 2 3 4 | 1
2 3 4 | 0 1
3 4 2 | 0 1
4 2 | 3 0 1
2 4 | 3 0 1
4 | 2 3 0 1
| 4 2 3 0 1
4 2 3 0 1 |
Figura 1: Alice realiza seu embaralhamento no baralho de 5 cartas "3, 1, 4, 0, 2". As costas das cartas estão todas voltadas para a esquerda.
Um dia, Bob anuncia que está tirando férias de uma semana. Alice, não tendo ninguém para jogar, convoca sua amiga Eve. Agora, Eve é uma trapaceira desavergonhada, então quando ela vê o embaralhamento peculiar de Alice, ela percebe que pode empilhar o baralho de antemão para sua vantagem!
Quando Eve chega em casa após o primeiro dia, ela faz algumas análises sobre o jogo e descobre que suas melhores chances são quando as cartas estão na ordem de 0, 1, 2, 3, 4, 5, ... Ela não o fez. No entanto, ela pega quantas cartas havia no baralho, então ela traça um esquema estanque para escrever um código em seu braço que, quando executado, pega o tamanho do baralho e exibe a ordem em que Eve precisa colocar as cartas, para que quando Alice embaralha o baralho, o baralho final está na ordem 0, 1, 2, 3, ...
Para Eve, não importa realmente em que idioma está o código (ela conhece todos), ou se o código é uma função que usa um argumento inteiro e retorna uma matriz ou um programa completo que recebe entradas por meio de um argumento de linha de comando ou STDIN e escrevendo os resultados para STDOUT. Ela, no entanto, precisa do código o mais curto possível, para minimizar a chance de Alice vê-lo e pegá-lo.
Por mais imoral que possa ser, vocês podem ajudar Eve?
Exemplos de entradas e saídas:
in out
1 0
2 0 1
5 2 4 0 3 1
10 2 9 4 8 0 7 3 6 1 5
52 6 51 25 50 12 49 24 48 1 47 23 46 11 45 22 44 5 43 21 42 10 41 20 40 2 39 19
38 9 37 18 36 4 35 17 34 8 33 16 32 0 31 15 30 7 29 14 28 3 27 13 26
fonte
shuffle(shuffle(range(5))) == range(5)
... #Respostas:
GolfScript,
151413 bytesExperimente online.
Exemplo
Como funciona
fonte
{}/
vez do operador de mapa para salvar um caractere.](
como os dois primeiros caracteres efetivamente coloca uma matriz vazia sob a entrada, economizando mais tarde[]\
.Julia, 83
O último elemento no vetor retornado é o topo do baralho.
fonte
Mathematica,
927746 bytesEspera a entrada na variável
n
:É literalmente jogar o shuffle para trás, movendo-se sobre uma carta e colocando a carta de baixo por cima.
EDITAR: Não há necessidade de acompanhar a pilha de saída, basta percorrer os números inteiros.
fonte
Python 2.7 - 57
Bonito e simples, basta inverter o shuffle. Bastante próximo de como o Golfscript faz isso.
fonte
J (13 caracteres) e K (9)
Como se vê, é um processo simples de desfazer a reprodução aleatória, e os curtidos de APL têm o advérbio fold
/
para ajudá-los a tornar isso o mais curto possível.J leva 13 caracteres com
(_1|.,)/@i.@-
, enquanto K precisa apenas de 9:|(1!,)/!:
. O APL seria similarmente conciso.Aqui está um rastreio passo a passo da versão J.
Você pode notar que no J, invertemos a matriz de números inteiros primeiro, mas no K o fazemos depois: isso ocorre porque a dobra K é mais como a
foldl
, em comparação com os J'sfoldr
.fonte