La secuencia de cambio

11

Introducción

La secuencia de cambio se define así:

Comience con npersonas paradas en círculo ( 6para este ejemplo).

 1  2
6    3
 5  4

A partir de la persona 1, la persona que está a la izquierda de la persona "elegida" se elimina.

 1
6    3
 5  4

La persona eliminada puede "cambiar" el método de eliminación:

  • Si la persona eliminada es par (que es en este caso), la próxima persona eliminada estará a la derecha de la siguiente persona "elegida".
  • Si la persona eliminada es impar, la siguiente persona eliminada estará a la izquierda de la siguiente persona "elegida".

La siguiente persona elegida también depende de la persona eliminada previamente.

  • Si la persona eliminada es par, la siguiente persona elegida estará a la derecha de la persona elegida anterior.
  • Si la persona eliminada es extraña, vea más arriba, pero reemplace "derecha" con "izquierda".

Entonces la siguiente persona elegida es entonces 6.

Ahora eliminamos a la persona a la derecha de 6, que es 5:

 1
6    3
    4

Porque 5es extraño, la persona eliminada está ahora a la izquierda. La nueva persona elegida es 1.

Ahora eliminamos 3:

 1
6
    4

Continuamos este proceso, hasta que nos quedemos con 1 número; en este ejemplo, el número final es 1. Entonces por lo tanto S(6) = 1.

Los primeros números son:

 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

Tarea

Su tarea es hacer un programa (o una función) que devuelva S(n)(el nnúmero th en la secuencia de conmutación) cuando se proporciona n, utilizando la menor cantidad de bytes.

Ejemplo de entradas y salidas:

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

Tiene garantizado obtener un número entero positivo.

Este es el , por lo que gana el código más corto en bytes.

Nota: No hay una secuencia OEIS (¿qué?), Para ahorrarle la molestia de buscar.

clismique
fuente
77
No hay resultados en oeis, para salvar a las personas de la búsqueda.
xnor
Obviamente 2nunca se queda, pero lo hace 7?
Jonathan Allan
1
@ JonathanAllan Acabo de comprobar los primeros 1000 términos, y el resultado es actualmente "no". Sin embargo, no estoy seguro: ¿debería poner eso como un "desafío secundario" que la gente puede intentar probar o algo así? Es para puntos de brownie, por lo que no resta valor al desafío.
clismique
Tal vez sea obvio una vez que a alguien se le ocurra un método que no sea seguir sus instrucciones ...
Jonathan Allan
3
¿Cómo espera que la gente resuelva esto sin un OEIS? Alguien empuje un OEIS, por favor?
Erik the Outgolfer

Respuestas:

4

Python 2, 183 94 bytes

-4 bytes gracias a Artyer (use input()y en printlugar de defy return)
-1 byte gracias a FlipTack (use en print-~p[0]lugar 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

Esto solo sigue las instrucciones dadas, he notado algún patrón, ¿tal vez podría explotarse?

Los únicos cambios son:

  • usar 0indexación basada (por lo que incluso las personas son extrañas y viceversa): esto ahorra 5 bytes en la lógica de golf y se corrige al final con+1
  • usar 1como izquierda y -1derecha (para usar un rango, al igual que todos están mirando hacia afuera)
  • para cambiar la lógica del paso donde se encuentra que el siguiente individuo elegido tiene en cuenta popde la lista haciendo que el índice de "puntero" ya sea el primer paso a la derecha de la lista (o a la izquierda en la terminología original).

Sin golf:

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
fuente
¿Puede ser la última línea print-~p[0]?
FlipTack
¡Por qué sí que puede!
Jonathan Allan