11
\$\begingroup\$

Intro

The Switching sequence is defined like so:

Start with n people standing in a circle (6 for this example).

 1  2
6    3
 5  4

Starting from person 1, the person that is to the left of the "chosen" person is removed.

 1
6    3
 5  4

The removed person can "switch" the removal method up:

  • If the removed person is even (which it is in this case), the next removed person will be to the right of the next "chosen" person.
  • If the removed person is odd, the next removed person will be to the left of the next "chosen" person.

The next chosen person is also dependent on the previously removed person.

  • If the removed person is even, the next chosen person will be to the right of the previous chosen person.
  • If the removed person is odd, see above, but replace "right" with "left".

So the next chosen person is then 6.

Now we remove the person to the right of 6, which is 5:

 1
6    3
    4

Because 5 is odd, the removed person is now to the left. The new chosen person is 1.

We now remove 3:

 1
6
    4

We continue this process, until we're left with 1 number - in this example, the final number is 1. So therefore S(6) = 1.

The first few numbers are:

 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

Task

Your task is to make a program (or a function) that returns S(n) (the nth number in the Switching sequence) when given n, using the least amount of bytes.

Example inputs and outputs:

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

You are guaranteed to get a positive integer.

This is , so shortest code in bytes wins!

Note: There is no OEIS sequence (what?), to save you the trouble of searching.

\$\endgroup\$
  • 7
    \$\begingroup\$ No hits on oeis, to save people the search. \$\endgroup\$ – xnor Oct 29 '16 at 6:17
  • \$\begingroup\$ Obviously 2 never remains, but does 7? \$\endgroup\$ – Jonathan Allan Oct 29 '16 at 6:54
  • 1
    \$\begingroup\$ @JonathanAllan I just checked for the first 1000 terms, and the result is currently "no". I'm not sure though - should I put that as a "side challenge" thing that people can attempt to prove or something? It's for brownie points, so it doesn't detract from the challenge. \$\endgroup\$ – clismique Oct 29 '16 at 6:56
  • \$\begingroup\$ Maybe it will be obvious once someone comes up with a method other than by following your instructions... \$\endgroup\$ – Jonathan Allan Oct 29 '16 at 7:00
  • 3
    \$\begingroup\$ How do you expect people solving this without an OEIS? Someone push an OEIS, please? \$\endgroup\$ – Erik the Outgolfer Oct 29 '16 at 7:12
4
\$\begingroup\$

Python 2, 183 94 bytes

-4 bytes thanks to Artyer (use input() and print rather than def and return)
-1 byte thanks to FlipTack (use print-~p[0] rather than 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

This just follows the instructions given, I've noticed some pattern, maybe it could be exploited?

The only changes are:

  • to use 0 based indexing (so even people are odd and vice-versa) - this is saves 5 bytes in the golfed logic and is corrected at the end with +1
  • to use 1 as left and -1 as right (to use a range - just like everyone is facing outwards instead)
  • to change the logic of the step where the next chosen individual is found to account for poping from the list making the "pointer" index already step one to the right in the list (or to the left in original terminology).

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
\$\endgroup\$
  • \$\begingroup\$ Can the last line be print-~p[0]? \$\endgroup\$ – FlipTack Jan 29 '17 at 9:32
  • \$\begingroup\$ Why yes it can! \$\endgroup\$ – Jonathan Allan Jan 29 '17 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.