21
\$\begingroup\$

Starting with a binary list (just 1s and 0s) we are going to roll a ball over it. The ball has a position and a direction. At every step the ball does the following:

  • If the number at it's position is 1, then flip the direction. It "bounces".
  • Flip the number, if it's 0 replace it with 1, if it's 1 replace it with 0.
  • Move 1 step in the direction.

We start execution with the ball at the first position heading to the right. When the ball is out of the range of the list either to the left or the right we stop execution.

For an example here is each step being run with [0,0,0,1,0] to start.

[0,0,0,1,0]
 ^>
[1,0,0,1,0]
   ^>
[1,1,0,1,0]
     ^>
[1,1,1,1,0]
       ^>
[1,1,1,0,0]
    <^
[1,1,0,0,0]
       ^>
[1,1,0,1,0]
         ^>
[1,1,0,1,1]
           ^>

Task

Given a starting list as input output the list after the ball has rolled over it.

This is the goal is to minimize the size of the source code as measured in bytes.

Test cases

[0,0,0,0,0] -> [1,1,1,1,1]
[0,0,0,1,0] -> [1,1,0,1,1]
[0,0,1,1,0] -> [1,0,0,1,1]
[0,1,0,1,0] -> [0,1,0,1,1]
[1,1,1,1,1] -> [0,1,1,1,1]
[1,0,1,0,0] -> [0,0,1,0,0]
[0,1,0,1] -> [0,1,0,1]
Improve this question
\$\endgroup\$
9
  • 4
    \$\begingroup\$ A exercise for the more mathematically inclined is to prove that this procedure will always halt for any starting configuration. \$\endgroup\$
    – Wheat Wizard ♦
    Feb 10, 2022 at 12:52
  • 1
    \$\begingroup\$ The procedure halts because (stop reading if you don't want spoilers): ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ Simple induction really. Assume length N array halts. The only way a length N+1 array can then not halt is if the ball bounces infinitely between the first element and the tail. This is impossible, since the first element will eventually be zero, and the ball will continue to the left. \$\endgroup\$
    – AnttiP
    Feb 10, 2022 at 13:27
  • 3
    \$\begingroup\$ Uhh, ackchyually isn't it exactly simple induction? We only assume that the previous array size halts. Strong induction would assume that arrays of length N,N-1,N-2,...,3,2,1 halt. Or is there a joke I'm not getting? \$\endgroup\$
    – AnttiP
    Feb 10, 2022 at 13:37
  • 4
    \$\begingroup\$ A simpler proof that this procedure always halts(ROT13): Rnpu fgrc vf erirefvoyr, naq gurer ner bayl svavgryl znal fgngrf. \$\endgroup\$
    – Nitrodon
    Feb 10, 2022 at 18:54
  • 2
    \$\begingroup\$ Is the input guaranteed to be nonempty? \$\endgroup\$
    – alephalpha
    Feb 11, 2022 at 2:03

19 Answers 19

Reset to default
8
\$\begingroup\$

tinylisp, 130 118 98 bytes

(load library
(d B(q((L R)(i R(i(h R)(reverse(B(c 0(t R))L))(B(c 1 L)(t R)))(reverse L
(q((L)(B()L

Try it online!

-12 bytes thanks to Razetime. See the edit history for a library-less version.

-20(!) bytes thanks to DLosc. Maybe I'm not very good at golfing in tinylisp...

B does the rolling.

(def roll_ball
  (lambda (Left Right Dir)				; takes left, right direction
    (if (equal? Dir 1)					; if direction is 1,
      (reverse (roll_ball Right Left 0))		; reverse the result of roll_ball with left and right lists flipped			
      (if (nil? Right)					; if we're at the end of the list,
        (reverse Left)					; reverse the left list and return
        (if (equal? (head Right) 1)			; otherwise, if the head is 1
          (roll_ball Left (cons 0 (tail Right)) 1)	; recurse, flipping the direction and changing the first element of Right to 0
          (roll_ball (cons 1 Left) (tail Right) 0)	; otherwise, recurse on L, and add 1 to the Left 
        )))))

tinylisp, 69 62 bytes

(load library
(d F(q((L)(i(h L)(c 0(t L))(concat(map not(t L))(q(1

Try it online!

Port of tsh's answer.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ (load library does have a reverse which reduces -8 Try it online! \$\endgroup\$
    – Razetime
    Feb 11, 2022 at 2:54
  • \$\begingroup\$ For the library version, I think you can eliminate the D parameter. Calling (B List1 List2 1) should be the same as calling (reverse (B List2 List1 0)), and then at that point D is always 0 and therefore isn't needed: Try it online! \$\endgroup\$
    – DLosc
    Feb 11, 2022 at 18:07
  • \$\begingroup\$ @DLosc ah I see. Put a little differently, the "list" we're traveling down also stores the direction we're headed. \$\endgroup\$
    – Giuseppe
    Feb 11, 2022 at 18:33
7
\$\begingroup\$

x86-64 machine code, 19 bytes

6A 01 58 99 80 34 17 01 75 02 F7 D8 01 C2 39 F2 72 F2 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI the address of an array of 8-bit integers and its length in RSI, and modifies it in place.

In assembly:

f:  push 1      # Push 1 onto the stack.
    pop rax     # Pop it into RAX.
    cdq         # Sign extend EAX into EDX, making EDX 0.
                    # EDX will hold the current index into the array
                    #  and EAX will hold the current direction (±1).
r:  xor BYTE PTR [rdi+rdx], 1   # Flip the current number.
    jnz s           # Jump if the new value is not 0.
    neg eax         #  Otherwise, the old value was 1; invert the direction.
s:  add edx, eax    # Advance in the current direction.
    cmp edx, esi    # Compare the current index with the length.
    jb r            # Jump back if the index is lesser, as unsigned integers;
                    #  this will stop if it goes off either end,
                    #  equaling the length or overflowing to all 1s.
    ret             # Return.
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I was very confused by your explanation of cdq -- do you mean Sign extend EAX into EDX:EAX? \$\endgroup\$
    – Gavin S. Yancey
    Feb 11, 2022 at 0:54
  • \$\begingroup\$ @GavinS.Yancey It would indeed be described as that from a different perspective: the full number is indeed in EDX:EAX, whereas the reason I described it as "into EDX" is that it leaves EAX unchanged and only modifies EDX. \$\endgroup\$
    – m90
    Feb 11, 2022 at 9:54
7
\$\begingroup\$

JavaScript (Node.js), 36 bytes

i=>i.map((n,j)=>i[0]?j>0&n:i[j+1]^1)

Try it online!

I don't have any proof of its correctness. It just passed all testcases. So it works.

Improve this answer
\$\endgroup\$
4
  • 3
    \$\begingroup\$ How did you arrive at this? \$\endgroup\$
    – Jonah
    Feb 11, 2022 at 2:36
  • \$\begingroup\$ Just prove by induction. \$\endgroup\$
    – alephalpha
    Feb 11, 2022 at 2:52
  • 4
    \$\begingroup\$ Proof: [->1,...a] -> [<-0,...a], [->0,0,...a] -> [1,->0,...a] -> (by induction) [1,(...a)^1,1->], [->0,1,...a] -> [1,->1,...a] -> [1<-,0,...a] -> [0,->0,...a] -> (by induction) [0,(...a)^1,1->]. \$\endgroup\$
    – alephalpha
    Feb 11, 2022 at 3:07
  • 2
    \$\begingroup\$ @Jonah First, open any exists answers' TIO, for example, the one from Arnauld's answer. Then, generate a complex enough input, and prepend the input with leading 0 or 1. After run it, try to find out the pattern by hand. And finally.... \$\endgroup\$
    – tsh
    Feb 11, 2022 at 3:13
5
\$\begingroup\$

R, 69 68 66 bytes

Or R>=4.1, 59 bytes by replacing the word function with a \.

Edit: -1 byte thanks to @Giuseppe.

function(v,a=0){while((F=F+(T=(-T)^a))&&!is.na(a<-v[F]))v[F]=!a;v}

Try it online!

The T=(-T)^a trick abuses the fact that going left may only last for one step.

R, 41 bytes

Or R>=4.1, 34 bytes by replacing the word function with a \.

function(v)"if"(v,c(0,v[-1]),c(!v[-1],1))

Try it online!

Port of @tsh'sanswer (with explanation by @Jonah).

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 68 bytes \$\endgroup\$
    – Giuseppe
    Feb 10, 2022 at 15:07
  • \$\begingroup\$ @Giuseppe nice one squeezing it all into while condition to avoid parens - thanks! \$\endgroup\$
    – pajonk
    Feb 10, 2022 at 19:37
5
\$\begingroup\$

J, 18 bytes

{.{(1-0,~}.),:0,}.

Try it online!

Based on tsh's JS answer.

how

  • {.{...,:... If the input begins with 1...
  • 0,}. Change the 1 to a 0 (we're just bouncing off the first element and halting)
  • 1-0,~}. Otherwise, remove the first element, append a 0, and then, for each element, return the opposite of its right neighbor.

why does this work?

This is an induction argument suggested by alephalpha in the comments of tsh's answer.

  • Consider the 1 element case. Clearly, a 1 becomes 0 and a 0 becomes 1. Also note that in the 0 case we're traveling right when we halt, and in the 1 case we're traveling left. Let's go ahead and add "begins with 0 exits right" to our induction hypothesis.
  • Assuming the hypothesis, consider the two cases:

    • 1 [n element input] Clearly true as we bounce off first element.

    • 0 [n element input] We now consider the two cases for the n element input:

      Begins with 1:
>
0 1 ...
  >
1 1 ...
< 
1 0 ...
  >
0 0 ... By induction, this will exit right,
        so the initial element is proven 0, as needed.

Begins with 0:
>
0 0 ...
  >
1 0 ... By induction, this will exit right,
        so the initial element is proven 1, as needed.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 3, 57 bytes

-13 bytes thanks to Wheat Wizard, -5 thanks to ophact, -2 thanks to loopy walt and -1 thanks to pxeger

def f(x):
 i=c=0
 while-~i*x[i:]:c^=x[i];x[i]^=1;i+=1-2*c

Try it online!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Brain-Flak, 90 bytes

(([]){(){}((()[{}])<{{}(<>)}{}>)<>([])}()){({}({})([{}()]))}{}{{}<>([]){{}({}<>)<>([])}}<>

Try it online!

36 bytes to simulate the ball rolling, and 54 to ensure that the input is in the right direction.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 3, 84 bytes

Not a great score, but somewhat interesting.

This takes a list of bits encoded as an integer and a length argument and outputs a new list of bits encoded as an integer. It’s a literal implementation, not induction based.

Improvements are welcome, I haven’t gotten any of my attempts to make it smaller working. Maybe c would be a better language to port this answer to.

Thanks to pxeger for -5!

def f(x,l,b=1,d=1):
 a=1<<l;c=a>>b;d*=x&c<1or-1
 return f(x^c,l,b+d,d)if c&a-1else x

Try it online!

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ -5 bytes with some twiddling: Try it online! \$\endgroup\$
    – pxeger
    Feb 14, 2022 at 16:54
2
\$\begingroup\$

05AB1E, 24 bytes

[ā<¾å_#D¾è©_¾ǝ®XαDUi¼ë.¼

Try it online or verify all test cases.

Explanation:

[           # Start an infinite loop:
 ā<         #  Push a list in the range [0,length) (without popping the list)
            #  (which will use the implicit input-list in the first iteration)
   ¾å_      #  If this list does not contain value `¾` (so we're out of bounds):
            #  (`¾` is 0 by default)
      #     #   Stop the infinite loop
 D          #  Duplicate the current list
  ¾è        #  Get the value at index `¾`
    ©       #  Store it in variable `®` (without popping)
     _      #  Invert the bit (with an ==0 check)
      ¾ǝ    #  Insert it back into the list at the same position `¾`
  ®Xα       #  Get the absolute difference between `®` and `X`
            #  (`X` is 1 by default)
     DU     #  Store this as new value `X`
       i    #  If this absolute difference `X` is 1:
        ¼   #   Increment `¾` by 1
       ë    #  Else:
        .¼  #   Decrement `¾` by 1 instead
            # (after which the list is output implicitly as result)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 55 bytes

f=(n,d=1,a=0,C=n[a])=>C<2?f((n[a]^=1,n),d=C?-d:d,a+d):n

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 59 58 bytes

f(a,l)int*a;{for(int i=0,d=1;i<l+0u;)i+=d*=(a[i]^=1)*2-1;}

Try it online!

-1 thanks to l4m2, making the numbers unsigned for the bounds check.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ i<l&&~i => i<l+0u \$\endgroup\$
    – l4m2
    Feb 10, 2022 at 14:28
2
\$\begingroup\$

JavaScript (ES6), 48 bytes

f=(a,d,i=0)=>1/a[i]?f(a,d^=!(a[i]^=1),i+1-2*d):a

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

If[#>0,{0,##2},1-{##2,0},{}]&@@#&

Try it online!

A port of @tsh's JavaScript answer.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

Ż¬;1ƊḢ?

Try it online!

Port of Jonah's excellent J solution.

     Ḣ     Remove the first element of the input.
Ż     ?    If it's 1, prepend 0 to the remaining elements, else
 ¬         negate the remaining elements
  ;1Ɗ      and append a 1.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

ḢCɓŻṙ⁹^

Try it online!

Another port of tsh's idea:

ḢC         h = 1 - input.pop(0)
  ɓŻ       input.prepend(0)
    ṙ⁹          .rotate_left(h)
      ^         .xor(h)

I've rearranged it a bunch of ways looking for a 6-byte formulation, but I can't find one.

In J, this is something like {.(-.@[|.=)0,}. (15 bytes).

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I also tried a bunch of stuff along those lines, and couldn't quite get it to tie! For some reason I got stuck on throwing the negated head back on after the xor, instead of just keeping the Ż. Really does feel like there should be a 6-byter... \$\endgroup\$
    – Unrelated String
    Feb 13, 2022 at 5:30
2
\$\begingroup\$

Retina 0.8.2, 35 24 bytes

1T`d`10`0.*|1
^1(.*)
$+1

Try it online! Link includes test cases. Explanation: Uses @tsh's method (see @Jonah's explanation).

1T`d`10`0.*|1

Invert the first bits, or all of the bits if the first bit is a 0.

^1(.*)
$+1

If the first bit is now a 1 then move it to the end.

Previous 35-byte version actually performed the steps given in the question:

^
>
{`>0
1>
>1
<0
0<
<1
}`1<
0>
\D

Try it online! Link includes test cases. Explanation:

^
>

Mark the initial position and direction of the ball.

{`
}`

Repeat until the ball goes out of range.

>0
1>
>1
<0
0<
<1
1<
0>

Flip the number at the current position and update the position and direction of the ball. (I don't know any shorter way of describing this in Retina; even T`>1<`<0>`>1|1< is three bytes longer than replacing >1 and <1 manually.)

\D

Delete the marker.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 49 bytes

a->i=d=1;while(i>0&&i<=#a,i+=d=-d+2*a[i]=!a[i]);a

Try it online!

Pari/GP, 48 bytes, does not work for empty input

a->i=d=1;until(i<1||i>#a,i+=d=-d+2*a[i]=!a[i]);a

Try it online!

Pari/GP, 44 bytes, does not work for empty input

a->if(a[1],a[1]=0;a,[!a[i%#a+1]|i<-[1..#a]])

Try it online!

A port of @tsh's JavaScript answer.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 3, 172 bytes

d=1
c=0
l=[int(i)for i in input()]
while c>-1 and c<len(l):
    (d:=not(d))if(l[c]==1)else(d:=d)
    l[c]=not l[c]
    if d==1:
        c+=1
    else:
        c-=1
print(l)

I just passed all of the test cases

And if a bit gets changed, it becomes a boolean (False is 0 and True is 1)

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to CG&CC! Feel free to add a link to an online interpreter like Try It Online, and to check out our tips for golfing in Python. Just converting to a function and removing unnecessary whitespace brings this down to 128 bytes, but see if you can get it down to 72! \$\endgroup\$
    – Unrelated String
    Mar 13, 2022 at 23:49
0
\$\begingroup\$

Charcoal, 18 bytes

Ｉ⎇§θ⁰Ｅθ∧κι⊞Ｏ⁻¹Φθκ¹

Try it online! Link is to verbose version of code. Explanation: Uses @tsh's method (see @Jonah's explanation).

   θ                Input array
  § ⁰               First element
 ⎇                  If nonzero then
      θ             Input array
     Ｅ              Map over elements
        κ           Current index
       ∧            Logical And
         ι          Current element
                    Else
             ¹      Literal integer `1`
            ⁻       Vectorised subtract
               θ    Input array
              Φ     Filtered by
                κ   Current index
          ⊞Ｏ     ¹  Append literal integer `1`
Ｉ                   Cast to string
                    Implicitly print
Improve this answer
\$\endgroup\$

Your Answer

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

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