A sequência de comutação

11

Introdução

A sequência de comutação é definida da seguinte forma:

Comece com npessoas em círculo ( 6neste exemplo).

 1  2
6    3
 5  4

A partir de pessoa 1, a pessoa que está à esquerda da pessoa "escolhida" é removida.

 1
6    3
 5  4

A pessoa removida pode "alternar" o método de remoção:

  • Se a pessoa removida for par (o que é neste caso), a próxima pessoa removida estará à direita da próxima pessoa "escolhida".
  • Se a pessoa removida for ímpar, a próxima pessoa removida estará à esquerda da próxima pessoa "escolhida".

A próxima pessoa escolhida também depende da pessoa removida anteriormente.

  • Se a pessoa removida for par, a próxima pessoa escolhida estará à direita da pessoa escolhida anterior.
  • Se a pessoa removida for estranha, veja acima, mas substitua "direita" por "esquerda".

Então a próxima pessoa escolhida é então 6.

Agora removemos a pessoa à direita de 6, que é 5:

 1
6    3
    4

Como 5é estranho, a pessoa removida está agora à esquerda. A nova pessoa escolhida é 1.

Agora removemos 3:

 1
6
    4

Continuamos esse processo, até termos 1 número - neste exemplo, o número final é 1. Então, portanto S(6) = 1.

Os primeiros números são:

 n | S(n)
---------
 1 | 1
 2 | 1
 3 | 3
 4 | 1
 5 | 5
 6 | 1
 7 | 3
 8 | 6
 9 | 5
10 | 6
11 | 9

Tarefa

Sua tarefa é criar um programa (ou uma função) que retorne S(n)(o nnúmero th na sequência de comutação) quando fornecido n, usando a menor quantidade de bytes.

Exemplos de entradas e saídas:

1  -> 1
10 -> 6
13 -> 13

Você está garantido para obter um número inteiro positivo.

Isso é , então o código mais curto em bytes vence!

Nota: Não há sequência OEIS (o quê?), Para poupar o trabalho de pesquisar.

clismique
fonte
7
Nenhum acerto nos oeis, para salvar as pessoas da pesquisa.
Xnor
Obviamente 2nunca permanece, mas permanece 7?
Jonathan Allan
1
@ JonathanAllan Acabei de verificar os primeiros 1000 termos, e o resultado é atualmente "não". Não tenho certeza - devo colocar isso como um "desafio secundário" que as pessoas podem tentar provar ou algo assim? É por pontos de brownie, por isso não diminui o desafio.
Clismique 29/10/16
Talvez será óbvio quando alguém surge com um método diferente, seguindo suas instruções ...
Jonathan Allan
3
Como você espera que as pessoas resolvam isso sem um OEIS? Alguém empurrou um OEIS, por favor?
Erik the Outgolfer

Respostas:

4

Python 2, 183 94 bytes

-4 bytes graças ao Artyer (use input()e printnão defe return)
-1 byte graças ao FlipTack (use print-~p[0]ao invés de print p[0]+1)

p=range(input())
d=i=1
while p[1:]:m=p.pop(i)%2;i-=m+m-(d<0);d=-m|1;i+=d;i%=len(p)
print-~p[0]

repl.it

Isso segue apenas as instruções dadas, notei algum padrão, talvez ele possa ser explorado?

As únicas alterações são:

  • usar a 0indexação baseada (para que as pessoas sejam ímpares e vice-versa) - economiza 5 bytes na lógica do golfe e é corrigido no final com+1
  • usar da 1esquerda e da -1direita (para usar um intervalo - assim como todo mundo está voltado para o exterior)
  • alterar a lógica da etapa em que o próximo indivíduo escolhido é considerado responsável pela poplista, fazendo com que o índice "ponteiro" já esteja na primeira à direita na lista (ou à esquerda na terminologia original).

Ungolfed:

def circle(n):
    people = range(n) # p
    direction = 1 # d
    removeIndex = 1 # i
    while n > 1:
        removingMod2 = people.pop(removeIndex) % 2 # m
        removeIndex -= removingMod2 + removingMod2 - (direction == -1)
        direction = -removingMod2 or 1
        removeIndex += direction
        n -= 1
        removeIndex %= n
    return people[0] + 1
Jonathan Allan
fonte
A última linha pode ser print-~p[0]?
FlipTack
Por que sim, pode!
Jonathan Allan