14
\$\begingroup\$

The ball game is a game in which a number of players sit together in a circle. Each player is first assigned a number \$ n \$, either 1, 2, or 3. The game begins with any starting player, and proceeds clockwise around the circle. The current player with the ball throws it to the next player. Who the next player is solely depends on the number \$ n \$ the current player was assigned.

If \$ n = 1 \$, the next player will be the one sat directly adjacent (one space away), traveling in the current direction.

If \$ n = 2 \$, the next player will be the one sat two spaces away, traveling in the current direction.

If \$ n = 3 \$, the direction of play is first switched (clockwise to counter-clockwise, and vice-versa). The next player will then be the one sat directly adjacent, traveling in the new direction.

Task

You are given a list of numbers \$ l \$ all in the range \$ [1 - 3] \$, denoting the numbers each player was assigned. The elements in \$ l \$ are given in clockwise order, and such that the last element of \$ l \$ is adjacent to the first element. Your task is to determine the number of players who have touched the ball, before it reaches a player who previously already touched the ball.

Example

The starting player is at the first index. X represents a visited index, O represents an index visited twice.

[1, 2, 1, 1, 2, 2, 3] ->
[X, 2, 1, 1, 2, 2, 3] ->
[X, X, 1, 1, 2, 2, 3] ->
[X, X, 1, X, 2, 2, 3] ->
[X, X, 1, X, X, 2, 3] ->
[X, X, 1, X, X, 2, X] ->
[X, X, 1, X, X, X, X] ->
[X, X, 1, O, X, X, X]
The answer is 6.

Clarifications

  • \$ l \$ can be inputted in any reasonable format, but the numbers 1, 2, and 3 must not change
  • The starting player does not have to be at the first index, but please specify where it would start
  • This is , so the shortest code in bytes wins!

Test Cases

Input (start is index 0) -> Output
[1] -> 1
[2] -> 1
[3] -> 1
[3, 2] -> 2
[2, 1] -> 1
[2, 2, 3] -> 3
[1, 1, 1, 1, 1] -> 5
[2, 2, 2, 2, 2] -> 5
[3, 3, 3, 3, 3] -> 2
[1, 3, 2, 1, 2, 3] -> 2
[1, 2, 1, 1, 2, 2, 3] -> 6
\$\endgroup\$
2
  • \$\begingroup\$ You'll want to fix before the it reaches at the end of the Task paragraph. \$\endgroup\$
    – Noodle9
    May 28, 2020 at 8:38
  • 1
    \$\begingroup\$ You have instructions, state, and an interpreter... is this game turing complete? \$\endgroup\$
    – Jonah
    May 28, 2020 at 21:56

12 Answers 12

8
\$\begingroup\$

Python 3, 67 55 bytes

f=lambda x,*l:x and-~f(*l[x%3-1::1-x//3*2],0,*l[x%2:1])

Try it online!

Use @Leo's idea of keeping the current player at a fixed index and transforming the list instead. Be sure to check out and upvote his answer!

If the current list is [x, a, b, c, d], where x is the move of the current player, then we want to rotate the list appropriately, and replace x with 0:

  • If x == 1, the new list is [a, b, c, d, 0]
  • If x == 2, the new list is [b, c, d, 0, a]
  • If x == 3, the new list is [d, c, b, a, 0]
  • If x == 0, this player has already been visited, thus we stop the algorithm.

Python 2, 90 85 bytes

f=lambda l,d=1,p=0,*t:(p in t)^1and-~f(l,[d,-d][l[p]>2],(-~l[p]%4*d-d+p)%len(l),p,*t)

Try it online!

Not every elegant, but does the job.

This recursive function keeps track of the current direction d, the position p, and the list of seen position t.

\$\endgroup\$
0
5
\$\begingroup\$

Husk, 16 bytes

←LU¡Γ!Moëṙ1ṙ2↔IΘ

Try it online!

Takes a list of numbers where the ball is currently at the first element and keeps rotating/reflecting the list to keep the ball in the first position while setting any visited element to 0. Returns how many different lists were created this way (-1).

For a more detailed explanation of the code (hard to do, but I'll try):

←LU¡Γ!Moëṙ1ṙ2↔IΘ
        ëṙ1ṙ2↔I  List of four functions [rotate by 1, rotate by 2, reflect, do nothing]
      Mo       Θ Make each of these functions prepend a 0 to the list before doing anything

    Γ!           Use the first element of the input list as an index into the list
                 of functions, and apply that function to the rest of the input list.
                 Note that indexing with a 0 returns the last function (do nothing)

   ¡             Iterate this process and keep all the results produced
  U              Discard all results after the first repeated one
←L               Return the number of results minus one

I'm a bit sad for all the bytes I'm taking to do ←LU, but I couldn't find a shorter alternative (damn 1-based indexing!)

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 94 92 91 bytes

Saved a byte thanks to ceilingcat!!!

c;s;i;d;p;f(l,n)int*l,n;{p=1;for(s=i=0;c=l[i];l[i]=!++s,i=(i+p*d+n)%n)d=c>2?p*=-1,1:c;p=s;}

Try it online!

Inputs an array of int along with its length and returns the number of players touched before a repetitive touch.

How?

Passes the ball around setting the last place the ball was to \$0\$ and incrementing the counter \$s\$. When we arrive back at a \$0\$ we're done and return \$s\$.

Commented code

c;s;i;d;p;f(l,n)int*l,n;{
    p=1;                /* polarity is initialised to 1 forwards. 
                           -1 is backwards */
    for(s=i=0;          /* initialise counter and index */
        c=l[i];         /* stop looping when we hit a zero
                           and cache the current value in c */
        ++s,            /* after loop bump our count */
        l[i]=0,         /* and zero last player */
        i=(i+p*d+n)%n)  /* and move index d places
                           in polarity p direction
                           adding n so we never go negative
                           when we make it all mod n */
       d=c>2?p*=-1,1:c; /* if number is 3 reverse polarity p
                           and set d to 1 otherwise set d to 
                           the number */
    p=s;                /* return s */
}
\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Recycling positive ints as zeros, nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Jun 18, 2020 at 10:53
2
\$\begingroup\$

JavaScript (ES6), 67 bytes

a=>(d=1,g=x=>(n=a[x%=w=a.length])&&!(a[x]=0)+g(x+=n-3?n*d:d=w-d))``

Try it online!

Commented

a => (                    // a[] = input array
  d = 1,                  // d = direction
  g = x =>                // g is a recursive function taking the current position x
    ( n =                 //   n is the player number at the current position
      a[                  //
        x %=              //   take the wrap-around into account by computing
          w = a.length    //   x modulo w, where w is the length of a[]
      ]                   //
    ) &&                  //   stop the recursion if a[x] is equal to 0
    !(a[x] = 0) +         //   otherwise, set it to 0 and increment the final result
    g(                    //   do a recursive call:
      x +=                //     update the position:
        n - 3 ? n * d     //       add n * d to x if n is not equal to 3
              : d = w - d //       otherwise, reverse the direction and add it to x
    )                     //   end of recursive call
)``                       // initial call to g with a zero'ish value for x
\$\endgroup\$
2
\$\begingroup\$

R, 97 87 85 bytes

function(p,i=1)sum(while(m<-p[i]){p[i]=0
i=(i+`if`(m>2,T<--T,m*T)-1)%%sum(p|1)+1},!p)

Try it online!

Edit: -10 bytes by tracking direction of travel (instead of flipping list of players)

Edit 2: re-arranged to cull 2 more characters

touches=function(p,         # p=player numbers
    i=1)                    # i=current player
    sum(
        while(m<-p[i]){     # while m=number of current player is non-zero
            p[i]=0          # set his number to zero
            i=i+            # calculate new player:
            `if`(m>2,       # if m is 3...
                T<--T,      # flip the direction of travel T and move by this
                m*T)        # otherwise move ahead by T*m
            -1)%%sum(p|1)+1 # -1, modulo number of players, +1
        }                   # (R indices are 1-based)
        !p)                 # sum of null (the return value of 'while')
                            # and the final number of zeros
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 22 21 bytes

[ć©_#0š„RÀS¤ºª®è.V¼}¾

Try it online or verify all test cases.

Explanation:

[                # Loop indefintely:
 ć               #  Extract head; pop and push remainder-list and first item separately
  ©              #  Store this first item in variable `®` (without popping)
   _             #  Check if its 0
    #            #   And if it is, stop the infinite loop
 0š              #  Prepend a 0 at the start of the list
   „RÀ           #  Push string "RÀ"
      S          #  Convert it to a list of characters: ["R","À"]
                 #  (NOTE: The `ª` already implicitly converts it to a list of
                 #   characters, so this usually isn't necessary; but without it the
                 #  `„RÀ¤` would act like a dictionary string and become "R cry")
       ¤         #  Push its last item (without popping): "À"
        º        #  Double it by mirroring: "ÀÀ"
         ª       #  Append it to the list: ["R","À","ÀÀ"]
          ®è     #  Index `®` into this list (0-based and with wraparound,
                 #  so the 3 will index into the first item "R")
            .V   #  Execute it as 05AB1E code
                 #   "R": Reverse the list
                 #   "À": Rotate the list once towards the left
                 #   "ÀÀ": Rotate the list twice towards the left
              ¼  #  Increase the counter_variable by 1
}¾               # After the infinite loop: push the counter_variable
                 # (after which it is output implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

J, 39 bytes

1-~&#[:({.(|.*1*@+2*[)0,}.)^:a:]+_4*=&3

Try it online!

I solved this independently before looking at other answers, but have stumbled on the same high-level approach used by Leo and Surculose Sputum.

A few details appear to be different:

  1. ]+_4*=&3 I start by transforming all 3s in the list into -1s, so that I don't have to special case any code. J automatically treats a negative rotation as the reverse direction.
  2. Instead of reversing the list when I hit a -1, I multiply all numbers on the list by -1. I avoid special casing here too by always multiplying all numbers on the list by the following quantity: "double current value, add 1, take sign num" 1*@+2*[. The quantity will be 1 for all values greater than 0, and -1 when the value is -1.
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -pa, 66 bytes

while($_=$F[$i]){$F[$i]=0;$.*=-1if/3/;$i+=$.+$.*/2/;$i%=@F;$\++}}{

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 81 bytes

s=>s.map(_=>(t=s[r=p%q])?s[p+=t>2?w*=-1:t*w,r]=!++n:0,q=s.length,n=0,p=3*q,w=1)|n

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 30 bytes

W⊟θ≔⁺⎇⁼ι²⟦⊟θ⁰⟧⟦⁰⟧⎇⁼ι³⮌θθθI⊕№θ⁰

Try it online! Link is to verbose version of code. Based on @Leo's idea explained better by @SurculoseSputum. Takes input in reverse order. Explanation:

W⊟θ

Let the current list be [e, d, c, b, a]. Remove the last element a, which represents the current player. Then if it is non-zero, meaning that they have not played yet:

≔⁺⎇⁼ι²⟦⊟θ⁰⟧⟦⁰⟧⎇⁼ι³⮌θθθ

Create two lists depending on the value of a:

  1. [0] and the rest of the list [e, d, c, b]
  2. [b, 0] (obtained by popping b from the list) and the rest of the list [e, d, c]
  3. [0] and the reverse of the rest of the list [b, c, d, e]

Concatenate them together to create the new state of the list.

I⊕№θ⁰

Print 1 more than the number of 0s in the list (because we popped a so that's no longer in the list).

\$\endgroup\$
0
\$\begingroup\$

perl -M5.010 -a, 84 bytes

$:=1;{($;=$F[$,])?do{$:=-$:,$;=1 if$;==3;$"++;$F[$,]=0;$,=($,+$;*$:)%@F;redo}:say$"}

Try it online!

This just follows the rule of the game, labelling any visited player as 0, and terminating when it encounters a player labelled 0. Steps are counted and printed at the end.

The code in the header section of TIO is just there to make it work on multiple inputs; leave it off for a single line of input.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 63 bytes

f=->a,d=1{x,*a=a;x ?1+f[[p,*a].rotate((2-x%2)*d*=1-x/3*2),d]:0}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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