32
\$\begingroup\$

A Brainfuck derivative

Let's define a simple Brainfuck-like programming language. It has a two-directional tape of cells, and each cell holds one bit. All bits are initially 0. There is a moving head on the tape, initially at position 0. A program is a string over the characters <>01!, executed from left to right, with the following semantics:

  • < moves the head one step to the left.
  • > moves the head one step to the right.
  • 0 puts 0 in the current cell.
  • 1 puts 1 in the current cell.
  • ! flips the current cell.

There are no loops, so a program of n characters terminates after exactly n steps. A program is boring if all cells contain 0 at the end of execution, and exciting if there is at least one 1. Note that the size of the tape is not specified, so depending on the implementation, it may be two-way infinite or circular.

An example program

Consider the program 1>>>!<<<<0>!>>>!. On an infinite tape, execution proceeds as follows:

 v 00000000000000 Put 1 v 00000100000000 Move by >>> v 00000100000000 Flip v 00000100100000 Move by <<<< v 00000100100000 Put 0 v 00000100100000 Move by > v 00000100100000 Flip v 00000000100000 Move by >>> v 00000000100000 Flip v 00000000000000 

At the end, all cells are 0, so this program is boring. Now, let's run the same program on a circular tape of length 4.

v 0000 Put 1 v 1000 Move by >>> v 1000 Flip v 1001 Move by <<<< (wrapping around at the edge) v 1001 Put 0 v 1000 Move by > (wrapping back) v 1000 Flip v 0000 Move by >>> v 0000 Flip v 0001 

This time, there is a cell with value 1, so the program is exciting! We see that whether a program is boring or exciting depends on the size of the tape.

The task

Your input is a non-empty string over <>01! that represents a program in the above programming language. An array of characters is also an acceptable input format. The program is guaranteed to be boring when run on an infinite tape. Your output shall be the list of tape lengths on which the program is exciting. Note that you only need to test the program on tapes that are shorter than the program length.

The solution with the lowest byte count in each language is the winner. Standard rules apply.

Test cases

> : [] 110 : [] 1>0<! : [1] 0>>1>0<<>! : [1] 1>>>!<<<<0>!>>>! : [2, 4] !<!<><<0>!>!<><1!>>0 : [2] >>!>><>001>0<1!<<!>< : [1, 2, 3] 1!><<!<<<!!100><>>>! : [1, 3] !!1>!>11!1>>0<1!0<!<1><!0<!<0> : [3, 4] <><<>>!<!!<<<!0!!!><<>0>>>>!>> : [1, 2, 4] 0>>><!<1><<<0>!>>!<<!!00>!<>!0 : [3] 0000!!!!><1<><>>0<1><<><<>>!<< : [] !>!>!>!>!>1>!>0<!<!<!<0<!<0<!<!<!<1>!>0<<! : [1, 2, 5, 7] <!!>!!><<1<>>>!0>>>0!<!>1!<1!!><<>><0<<!>><<!<<!>< : [1, 2, 4, 5] !>1<<11<1>!>!1!>>>0!!>!><!!00<><<<0<<>0<<!<<<>>!!> : [1, 2, 3, 5, 6] 
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can we choose any distinct and consistent characters instead of <>01!? \$\endgroup\$ Commented Feb 23, 2018 at 18:15
  • 1
    \$\begingroup\$ Is an array of instructions an acceptable input? \$\endgroup\$ Commented Feb 23, 2018 at 18:21
  • \$\begingroup\$ @Mr.Xcoder No, you should use these exact characters. \$\endgroup\$ Commented Feb 23, 2018 at 18:24
  • \$\begingroup\$ @Arnauld An array of characters is close enough to a string, I'll allow it. \$\endgroup\$ Commented Feb 23, 2018 at 18:26

14 Answers 14

6
\$\begingroup\$

Haskell, 119 bytes

t#'<'=last t:init t (h:t)#c|c<'#'=1-h:t|c>'='=t++[h]|1<2=read[c]:t f p=[n|n<-[1..length p],sum(foldl(#)(0<$[1..n])p)>0] 

Try it online!

Function # is the interpreter for a single command c. The whole program p is run by folding # with the starting tape into p. f executes p for every tape and keeps those where the sum of the cells is at least 1.

\$\endgroup\$
4
  • \$\begingroup\$ n<-[1..length p] ... 0<$[1..n] seems quite long, there must be a shorter way. \$\endgroup\$ Commented Feb 23, 2018 at 20:49
  • \$\begingroup\$ I can't see a shorter way. The problem I see is that you actually need the value of n as the result, so if you constructed 0<$[1..n] a different way (say with scanr(:)), you'd need to take the length of it. (I also tried using 1 (to replace length with sum) or False (to use or for the test) instead of 0, but it didn't come out shorter.) \$\endgroup\$ Commented Feb 24, 2018 at 2:07
  • \$\begingroup\$ @ØrjanJohansen: yes, I tried n<-init$scanr(:)[]$0<$p ... n which is 2 bytes shorter, but it returns a list of starting tapes instead of their length, e.g.[[0],[0,0,0]]. With a little bit of rule bending so could see the tapes as unary numbers, so maybe it's ok. \$\endgroup\$ Commented Feb 24, 2018 at 11:05
  • \$\begingroup\$ init$ can be replaced by putting a [0] as initial list, but it still didn't get short enough. I think unary is only allowed for languages without a more natural number representation. \$\endgroup\$ Commented Feb 24, 2018 at 19:56
4
\$\begingroup\$

Stax, 56 54 43 38 35 bytesCP437

è¥%►BΣ░ÜY⌂y(â&.═ªê►V½▲y▌)▀♫♂╣ª?√»!# 

42 bytes when unpacked,

%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a 

Run and debug online!

-2 bytes per comment by @recursive

Explanation

I will use the version with a prefix i(i.e. i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a) to explain and I will explain why the i can be removed

i Suppress implicit eval This prevents the test case "110" from being interpreted as a number However, this can be removed because a program containing only numbers cannot be exciting and the output will be empty anyway. This is based on the fact that the program is boring on non-circular tapes %f Filter range [1..n] with the rest of this program Where n is the length of the input Implicit output the array after filtering, one element per line z( Initialize the tape y{ F Run the program |a Any cell is non-zero 

Code for running the program:

{|(} Block to rotate left by one element {|)} Block to rotate right by one element {B!s+} Block to perform logical not on the element at index 0 {0_]e&} Block to obtain current instruction, Convert it to a number And assign to element at index 0 4l Pack the 4 blocks in an array s"<>! "I Find the index of current instruction in string, if not found, the index will be -1 And when indexed with -1, it wraps around to the 4th element. @! And execute the corresponding block. 
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I added a test case of all digits to validate your i check. \$\endgroup\$ Commented Feb 23, 2018 at 21:45
  • \$\begingroup\$ 0]* can be replaced with z(. Also, if you change the string to "<>!", then 0 and 1 will give index -1, so that way your block list only needs 4 blocks, instead of 5. This will work since the 0 and 1 handlers are identical anyway. \$\endgroup\$ Commented Feb 28, 2018 at 7:31
  • \$\begingroup\$ @recursive Good point taken. \$\endgroup\$ Commented Feb 28, 2018 at 8:26
3
\$\begingroup\$

CJam, 57 56 49 46 bytes

-7 thanks to @MartinEnder

{:T,({)0a*T{i23%")!+(+ W0tW1t)\+"3/=~}/:+},:)} 

Try it online!

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

Perl 5, 83 82 79 77 bytes

Includes +3 for -F

Give instructions as one line on STDIN

#!/usr/bin/perl -F 1~~@$m&&say$m until++$m>map{*r=\$$m[($n+=/>/-/</)%$m];$r=/\d/?$&:$r^/!/}@F 

Try it online!

\$\endgroup\$
1
2
\$\begingroup\$

Perl 5 (-F), 101 bytes

map{$,=@a=(0)x$_;map{$,+=/>/-/</;$a[$,%@a]=$&if/0|1/;$a[$,%@a]=!$a[$,%@a]if/!/}@F;say if@a~~/1/}1..@F 

Try it online!

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

Red, 243 bytes

func[p][repeat n length? p[b: copy[]insert/dup b 0 n i: 1 parse p[any["<"(i: i - 1 if i < 1[i: n])|">"(i: i + 1 if i > n[i: 1])|"0"(b/(i): 0)|"1"(b/(i): 1)|"!"(b/(i): either b/(i) = 0[1][0])| skip]]s: 0 foreach c b[s: s + c]if s > 0[print n]]] 

Try it online!

Prety verbose and straightforward implementation. Red's 1-indexing doesn't allow me to reduce the byte count by using modular arithmetic for looping through the circular tapes.

Ungolfed

f: func[p][ repeat n length? p[ b: [] insert/dup b 0 n i: 1 parse p[ some [ "<" (i: i - 1 if i < 1[i: n]) | ">" (i: i + 1 if i > n[i: 1]) | "0" (b/(i): 0) | "1" (b/(i): 1) | "!" (b/(i): either b/(i) = 0 [1][0]) | skip ] ] s: 0 foreach c b[s: s + c] if s > 0 [print n] ] ] 
\$\endgroup\$
2
\$\begingroup\$

Python 2, 139 135 133 132 131 bytes

-3 bytes thanks to Mr. Xcoder

def f(p):i=0;exec"i+=1;s=[0]*i\nfor c in p:c=ord(c)-61;s=c>-2and s[c:]+s[:c]or[[s.pop(0)^1,0,1][c%7]]+s\nif 1in s:print i\n"*len(p) 

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 131 bytes? \$\endgroup\$ Commented Feb 23, 2018 at 21:30
2
\$\begingroup\$

Retina, 121 bytes

.+ $.&*0¶$& \G0 0$`¶ {ms`^.(?=.*¶¶(0|1)) $1 "¶¶!"&mT`d`10`^. "¶¶>"&`(.)(.*)¶ $2$1¶ "¶¶<"&`(.*)(.)¶ $2$1¶ )`¶¶. ¶¶ G`1 %`. 

Try it online! Explanation:

.+ $.&*0¶$& \G0 0$`¶ 

Create an array of tapes of each length up to the length of the input program.

{ 

Loop until the program is consumed.

ms`^.(?=.*¶¶(0|1)) $1 

If the next character in the program is a 0 or 1, change the first character on each line to that character.

"¶¶!"&mT`d`10`^. 

If it is a ! then toggle the first character on each line.

"¶¶>"&`(.)(.*)¶ $2$1¶ "¶¶<"&`(.*)(.)¶ $2$1¶ 

If it is a > or < then rotate the line. (Easier than moving the head.)

)`¶¶. ¶¶ 

Delete the instruction and end the loop.

G`1 

Keep only the exciting lines.

%`. 

Count the length of each line.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 126 118 bytes

Saved 3 bytes thanks to @user71546

Takes input as an array of 1-character strings.

f=(s,l=0,p=0,t=[])=>s[l++]?s.map(c=>1/c?t[p%l]=+c:c>'='?p++:c>';'?p+=l-1:t[p%l]^=1)&&+t.join``?[l,...f(s,l)]:f(s,l):[] 

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Replacing t.some(x=>x)? by +t.join``? instead check the array as digits (and 0 indicates an all-zero tape), but 3 bytes less. \$\endgroup\$ Commented Feb 26, 2018 at 1:08
  • \$\begingroup\$ [] can be t, it's unused on this path \$\endgroup\$ Commented Jan 18, 2023 at 17:04
  • \$\begingroup\$ Init value of p doesn't matter \$\endgroup\$ Commented Jan 18, 2023 at 17:05
2
\$\begingroup\$

APL (Dyalog Unicode), 79 64 54 bytes (Adám's SBCS)

⍸⊂{∨/⍎⍕(↓',',⍨5 3⍴'0@11@1~@1 1⌽¯1⌽')['01!<'⍳⌽⍺]⍵}¨0=,\ 

Try it online!

-15 thanks to Adám (forgot about monadic ).
-10 thanks to ngn.

\$\endgroup\$
8
  • \$\begingroup\$ 64 \$\endgroup\$ Commented Mar 8, 2018 at 22:11
  • \$\begingroup\$ @Adám Hm, looks like that's not optimal (for example you don't need the ). I'll look into it and update. :) \$\endgroup\$ Commented Mar 9, 2018 at 12:27
  • \$\begingroup\$ But if you remove the you'll need a ;, no? \$\endgroup\$ Commented Mar 9, 2018 at 12:34
  • \$\begingroup\$ @Adám no, why would you? \$\endgroup\$ Commented Mar 9, 2018 at 12:35
  • \$\begingroup\$ Because rank-2 arrays need two index parts. \$\endgroup\$ Commented Mar 9, 2018 at 12:41
1
\$\begingroup\$

MATL, 46 39 bytes

f"@:~G"@59>?@61-YS}@33=?t1)~}@U]1(]]a?@ 

Try it online! Or verify all test cases.

How it works

f % Push indices of nonzero chars of (implicit) input string: gives % [1 2 ... n] where n is input length " % For each k in [1 2 ... n]. These are the possible tape lengths @:~ % Push array of k zeros. This is the tape, in its initial state G % Push input string " % For each char in the input string @59>? % If code point of current char exceeds 59 (so it is '<' or '>') @61- % Push code point minus 61: gives -1 for '<', or 1 for '>' YS % Circularly shift the tape by that amount. Instead of moving % the head, we shift the tape and keep the head at entry 1 } % Else @33=? % If code point of current char is 33 (so it is '!') t1) % Duplicate the array representing the tape, and get its % first entry ~ % Logical negate } % Else @U % Push current char (it is '0' or '1') converted to number ] % End 1( % Write (either 0, 1 or old value negated) at entry 1 ] % End ] % End a? % If the tape contains at least a nonzero value @ % Push tape length, k % End (implicit) % End (implicit) % Display (implicit) 
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 192 78 bytes

⊂{t/⍵⊣⍵{t[m]←('01!'⍳⍵)⊃0 1,e,⍨~e←t[m←⍺|i⊣i+←¯1 1 0⊃⍨'<>'⍳⍵]}¨⍺⊣i←⊃t←⍬⍳⍺}¨1+⍳∘≢ 

Try it online! (non-flattened result)

Try it online! (flattened)

After some time spent banging my head against the wall, I decided to make a Tradfn instead of a Dfn. This is the result. Smarter people than me may be able to golf the heck out of this.

Surprise, surprise, someone smarter than me did golf the heck out of this. Thank you Adám for 114 bytes.

He said:

Notice that it is your exact program, except using indexing instead of the inner :Ifs and collapsing :For-loops to {_}¨ while giving a left argument to replace the global.

The function assumes ⎕IO←0.


How?

(This explanation uses an "ungolfed" version to facilitate reading)

⊂{ ⍝ Enclose i←⊃t←⍬⍳⍺ ⍝ Assign a vector of 0s to t (the tape), then assign the first 0 to i. t/⍵⊣⍵{ ⍝ Use ⍵ as left argument for the nested function, then compress the result into t. If there is a 1 anywhere in t, the result will be a vector of the result. If not, the result is an empty vector. i+←¯1 1 0⊃⍨'<>'⍳⍵ ⍝ Map the string '<>' to the argument (which is the BF program). That yields 0 for <, 1 for >, and 2 for anything else. ⍝ The resulting vector will then be used as the argument for ⊃ to add -1 (index 0), 1 (index 1) or 0 (index 2) to the variable i. e←t[m←⍺|i] ⍝ Assign i mod ⍺ (left arg) to m, and use it to index t. Then, assign the value to e. t[m]←('01!'⍳⍵)⊃0 1,e,⍨~e ⍝ Map the string '01!' to ⍵. As before, this yields 0 for 0, 1 for 1, 2 for ! and 3 for anything else. ⍝ Then, concatenate (not e) with e, then concatenate that with the vector 0 1. This is used as argument to be picked from, and it is assigned to t[m]. }¨⍺ ⍝ Do that for each argument }¨1+⍳∘≢ ⍝ And do that for each possible tape length from 1 to the length of the input. 
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Save one byte by making t←l⍴0 be t←l⍴i←0, and removing the line above it. You can also save another by changing t[i|⍨≢t]←1-t[i|⍨≢t] to t[i|⍨≢t]←~t[i|⍨≢t]. \$\endgroup\$ Commented Mar 8, 2018 at 18:24
  • 2
    \$\begingroup\$ @Zacharý right, and further save an additional 112 bytes. Exactly same code, just golfed a bit. \$\endgroup\$ Commented Mar 8, 2018 at 20:09
  • \$\begingroup\$ Yeah, it's just goled "a bit". Don't you need the s? \$\endgroup\$ Commented Mar 8, 2018 at 22:55
  • \$\begingroup\$ @Zacharý What s? It is a tacit function. \$\endgroup\$ Commented Mar 9, 2018 at 10:34
  • \$\begingroup\$ @Zacharý I would consider this one pretty Adám'd, wouldn't you? \$\endgroup\$ Commented Mar 9, 2018 at 13:42
0
\$\begingroup\$

Jelly, 41 bytes

JR0ṁð3“1⁺¦01¦¬1¦ṙ1 ṙ- ”s“10!<>”,yẎvЀ⁸Ẹ€T 

Try it online!

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

C (clang), 171 bytes

l,i;f(S){for(char*p,t[l=strlen(S)];l;memchr(t,1,l)&&printf("%d ",l),l--)for(memset(t,i=0,l),p=S;*p;p++)*p==60?i=i?i-1:l-1:*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1);} 

Try it online!

Had to use clang, since using char*p,t[l=strlen(S)] as the initialisation expression for some reason makes GCC think I want to declare strlen instead of calling it.

Pretty straight-forward: Runs the program on circular tapes of decreasing length, outputting any length that resulted in a 1 somewhere on the tape.

Tried shortening the tangle of the ternary operators, but ended up needing more parenthesis than was healthy.

\$\endgroup\$
1
  • \$\begingroup\$ Suggest i=0,bzero(t,l) instead of memset(t,i=0,l) and *p-62?t[i]=*p^33?*p-48:t[i]^1:(i=~i+l?i+1:0) instead of *p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1) \$\endgroup\$ Commented Dec 20, 2018 at 1:09

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.