title: Write a brainfuck translator

text:
# Question
Title: Write a brainfuck translator
In any programming or scripting language *x*, write a program that takes a valid brainfuck sourcecode from stdin and output, to stdout, the sourcecode of a program, written in language *x*, that would output the exact same thing as the brainfuck program would do.

Your program must work for any valid brainfuck program, including the empty file.

Your score would be equal to the byte count of your sourcecode, plus the byte count of your output given the following input:

```
+++++ [-]
+++++ +++++ [
    > +++++ ++
    > ++ +++ ++++ +
    > +++
    <<< -
]
> ++ . H
> + . e
++ +++ ++. l
. l
+++ . o
> ++ . space
< +++++ +++ . w
----- --- . o
+++ . r
---- - - . l
----- --- . d
> + . exclamation mark
------lol; useless code :-)--------------------------[.............................................][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][]<-<<><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><

```

For example, for an input of `[-]`, the output of `*p=0;` is much more favourable than `while(*p) *p--;`

If you happen to use non-ASCII characters, the byte count must be calculated using the UTF-8 encoding.

Lowest score wins. However, creative solutions that attempt to minimise the output shall be encouraged by upvotes.

# Answer
> 12 votes
## Perl - 177 (source) + 172 (output) = 349

```
#!perl -p0
y/-+><.,[]
-~/p-w/d;s/(.)\K\1+|rs|wv[^v]*(?=w)/$+&&length$&/ge;$_="eval'r$_'=~".'s/.(\d*)/(qw(--$ ++$ -- ++ print+chr$ $$i=ord+getc; while($$i){ })[$&&v63].q($i;))x($++1)/ger'

```

Counting the shebang as 2 bytes, one for each option. First, each of the eight commands is translated onto the range `p-w`, while at the same time removing all other characters. This string is then run-length encoded and output with a minimal decoder/interpreter. A few things are optimized away: the string `><` obviously does nothing, and a for loop that follows directly after another may be removed entirely, as it will never be entered.

Output for the test program:

```
eval'rq4vpwq9vrq6rq9rq2s2pwrq1trqtq6t1q2trq1tsq7tp7tq2tp5tp7trqtp32vt44wsps1'=~s/.(\d*)/(qw(--$ ++$ -- ++ print+chr$ $$i=ord+getc; while($$i){ })[$&&v63].q($i;))x($++1)/ger

```

A sample run:

```
$ perl brainfusk.pl < in.bf | perl
Hello world!

```

---

## Perl - 232 (source) + 21 (output) = 253

```
#!perl -p0
y/-+><.,[]
-~/0-7/d;$_="eval'2$_'=~".'s/./qw(--$ ++$ -- ++ print+chr$ $$i=ord+getc; while($$i){ })[$&].q($i;)/ger';
/5/||fork?(wait,$?||exit):($SIG{ALRM}=sub{exit 1},alarm 9,$S=select(open 1,'>',\$o),eval,print$S "print\"\Q$o\E\"")

```

This one is based on FIQ's observation that if the original program doesn't contain an input statement, the output will be static, and therefore can be reduced to a single `print` statement. If you like this one, be sure to give his answer a +1.

So what we can do is pipe `stdout` to a variable, `eval` the code we would have output, and wrap the result in a `print`.

...that won't always work, though. Whenever the code to be translated would have resulted in an infinite loop, (e.g. `+[.]`), this *cannot* be reduced to a single `print` statement, for obvious reasons. So instead, we launch the `eval` in a child process with a short timeout, and if it doesn't finish executing within that time we output the translated program as before.

Structured and commented:

```
if(!/5/) { # no `,` in program

  if(fork) { # parent process

    # wait for child
    wait;
    # no child error, terminate without output
    $?||exit

  } else { # child process

    # alarm handler, exit with error
    $SIG{ALRM}=sub{exit 1};
    # set an alarm in 9 seconds
    alarm 9;
    # redirect STDOUT to variable $o
    $S=select open 1,'>',\$o;
    # execute translated code
    eval;
    # wrap the result in a print statement
    print$S "print\"\Q$o\E\""
  }
}

```

Output for sample program:

```
print"Hello\ world\!"

```

Output for `,[.]`:

```
eval'25647'=~s/./qw(--$ ++$ -- ++ print+chr$ $$i=ord+getc; while($$i){ })[$&].q($i;)/ger

```

Output for `+[.]` (after 9 seconds):

```
eval'21647'=~s/./qw(--$ ++$ -- ++ print+chr$ $$i=ord+getc; while($$i){ })[$&].q($i;)/ger

```

# Answer
> 14 votes
# Brainfuck, 5 + 540 = 545 bytes

5 bytes of code, 540 from output of given test file (assuming got the count right from my paste of that code).

```
,[.,]

```

Assuming EOF is 0.

# Answer
> 5 votes
# PHP, 553 + 27 = 580 bytes

(553 bytes with all whitespaces, i.e. newlines and spaces, removed)

I suck badly at golfing PHP, so this approach can be heavily optimized. I mostly wanted to show my approach to the solution in something not BF.

```
<?php
echo "<?php ";
$x = 'if (!$b) $c = $_GET[c];
$x=$y=$n[0]=$p=0;$o[0]=1;$d="";
while($a=$c[$x++]){
    if($o[$p]){
        if($a=="-")$m[$y]--;
        if($a=="+")$m[$y]++;
        $m[$y]=$m[$y]%256;
        if($a=="<")$y--;
        if($a==">")$y++;
        if($a=="."){
            $e=chr($m[$y]);
            if ($b) echo $e;
            else $d.=addslashes($e);
        }
        if($a==",")$m[$y]=($b=$_GET[i])?ord($b):0;
    }if($a=="["){
        $p++;
        $n[$p]=$x-1;
        $o[$p]=$o[$p-1]?$m[$y]:0;
    }
    if($a=="]"){
        if($o[$p])$x=$n[$p];
        $p--;
        if($p=-1)$p=0;
    }
}
if (!$b) echo "echo \'$d\';";';
if (strstr($_GET['c'],",")) {
    $x = '$b=1;'.$x;
    echo '$c="'.addslashes($_GET[c]).'";'.$x;
    return;
}
eval($x);

```

Error reporting must be off, otherwise PHP will hate you. Usage: throw this up as a page, and run it with script.php?c=CODE (if the resulting script requires input, you run it as out.php?i=INPUT). Remember to url escape the input!

What this does is basically this - if the BF script contains ",", it pretty much embeds itself as the resulting script with an attached $b=1; at the top. If it does NOT contain ",", it optimizes it down to "echo '\<BF output\>'". Conveniently, the test script in the OP does NOT require any input. The addslashes() is just there for escaping ' and \\.

# Answer
> 4 votes
# C++, 695 + 510 = 1205 bytes

Code:

```
#include<iostream>
#include<utility>
#include<vector>
#define D "\n#define "
using namespace std;using S=string;int main(){vector<pair<S,S>>m={{"--------","(*p)-=8;"},{"<>",""},{"[]","F;"},{"+","A;"},{"-","B;"},{">","C;"},{"<","D;"},{"[","F{"},{"]","}"},{".","E;"},{",","std::cin>>*p;"}};S s;char c;while(cin>>c)if(S("+-><[].,").find(c)<8)s+=c;for(int i=0;i<s.length();i++)if(s.substr(i,4)=="[][]")s=s.replace(i--,4,"[]");cout<<"#include<iostream>" D"A ++*p" D"B --*p" D"C p++" D"D p--" D"E std::cout<<*p" D"F while(*p)\nint main(){char*p=new char[1<<19]();";while(s.size())for(auto p:m)if(s.substr(0,p.first.length())==p.first){s=s.substr(p.first.length());cout<<p.second;break;}cout<<"}";}

```

Output:

```
#include<iostream>
#define A ++*p
#define B --*p
#define C p++
#define D p--
#define E std::cout<<*p
#define F while(*p)
int main(){char*p=new char[1<<19]();A;A;A;A;A;F{B;}A;A;A;A;A;A;A;A;A;A;F{C;A;A;A;A;A;A;A;C;A;A;A;A;A;A;A;A;A;A;C;A;A;A;D;D;D;B;}C;A;A;E;C;A;E;A;A;A;A;A;A;A;E;E;A;A;A;E;C;A;A;E;D;A;A;A;A;A;A;A;A;E;(*p)-=8;E;A;A;A;E;B;B;B;B;B;B;E;(*p)-=8;E;C;A;E;(*p)-=8;(*p)-=8;(*p)-=8;(*p)-=8;B;F{E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;}F;D;B;D;D;}

```

Original code:

```
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main() {
    vector<pair<string, string>> m={
    {"--------","(*p)-=8;"},
    {"<>",""},
    {"[]","F;"},
    {"+","A;"},
    {"-","B;"},
    {">","C;"},
    {"<","D;"},
    {"[","F{"},
    {"]","}"},
    {".","E;"},
    {",","std::cin>>*p;"}};
    string s;
    char c;
    while (cin >> c)
        if (string("+-><[].,").find(c) < 8)
            s += c;
    for(int i = 0; i < s.length(); i++)
        if(s.substr(i, 4) == "[][]")
            s = s.replace(i--, 4, "[]");
    cout << "#include<iostream>\n"
            "#define A ++*p\n"
            "#define B --*p\n"
            "#define C p++\n"
            "#define D p--\n"
            "#define E std::cout<<*p\n"
            "#define F while(*p)\n"
            "int main(){char*p=new char[1<<19]();";
    while (s.size())
        for (auto p : m)
            if (s.substr(0, p.first.length()) == p.first) {
                s = s.substr(p.first.length());
                cout << p.second;
                break;
            }
    cout << "}";
}

```

# Answer
> 3 votes
# Brainfuck, 109 + 407 = 516

```
>+[>+++++++[-<------>]<-[-[-[-[--------------[--[>+++++[-<------>]<+[--[[-]<[-]>]]]]]]]]<[.[-]]>>,[-<+<+>>]<]

```

Try it online!

It only removes non BF ops and does not look at other optimizations.

# Answer
> 2 votes
## Python - 514 + 352 = 866

Code:

```
import sys,zlib,base64
s,i="import sys\na,i=[0]*300000,0\n",0
for c in sys.stdin.read():
 if c in"+-><,.[]":
  s+=" "*i+{'+':"a[i]+=1\n",'-':"a[i]-=1\n",'>':"i+=1\n",'<':"i-=1\n",',':"a[i]=(lambda x:0if x==''else ord(x))(sys.stdin.read(1))\n",".":"sys.stdout.write(chr(a[i]))\n","[":"while a[i]!=0:\n","]":"pass\n"}[c]
  i+={'[':1,']':-1}.get(c,0)
print('import zlib,base64\nexec(zlib.decompress(base64.b64decode("'+base64.b64encode(zlib.compress(bytes(s,"utf8"),9)).decode("utf8")+'")).decode("utf8"))')

```

Output:

```
import zlib,base64
exec(zlib.decompress(base64.b64decode("eNrLzC3ILypRKK4s5krUybSNNojVMjYAAR0DrsTozFhtW0OCdHlGZk6qAoinaGtgxQVm6QLFFQoSi4uJNoVc2zJBggowWTIZVDGEEvMzddFJ1FDMxBYUwFjTKy5JyS8t0SsvyixJ1UjOKNIASWpqomrAp5DceMBnJjn2Ee0ZojToUiGlEfIFzA5yaGqHELXtp5XfMukVwMOFRi/u8IXZqOSo5KjkqOSIlAQ3k9BLy1HBUcFRwVFBOgpmIrfeMhGE9ihrpLEAudg3NA==")).decode("utf8"))

```

# Answer
> 1 votes
# Lua - 319 + 21 = 340

This is most likely the shortest code of all, but it doesn't accept input, so it is kinda cheaty. I got a idea for another version with input, see the end of this comment.

```
loadstring("o=\"\";d={"..string.rep("0,",30000).."}p=1;"..io.read():gsub("[^%+%-<>%.,%[%]]+",""):gsub(".",{["+"]="d[p]=d[p]+1;",["-"]="d[p]=d[p]-1;",[">"]="p=p+1;",["<"]="p=p-1;",["."]="o=o..string.char(d[p])",[","]="d[p]=io.read()",["["]="while d[p]~=0 do ",["]"]="end;"}))()print("print("..string.format("%q",o)..")")

```

# Lua - 376 + 366 = 742

This version is to prove that lua can do better than 2584 :D

```
print('loadstring("d={"..string.rep("0,",30000).."}p=1;"..('..string.format("%q",io.read():gsub("[^%+%-<>%.,%[%]]+",""):gsub("%[[^%+%-<>%,%[%]]*%]",""):match("(.*[.,]).-"))..'):gsub(".",{["+"]="d[p]=d[p]+1;",["-"]="d[p]=d[p]-1;",[">"]="p=p+1;",["<"]="p=p-1;",["."]="io.write(string.char(d[p]))",[","]="d[p]=string.byte(io.read())",["["]="while d[p]~=0 do ",["]"]="end;"}))()')

```

Both versions add in 30000 bytes of data. My second version is based on input/output: everything after a '.' or ',' will be removed. My second version does not allow infinite loops ( \[.,\], \[\], etc. )

My Idea is to get:

```
print("Hello world!"..string.char(string.byte(io.read())+1)

```

From your input, with a extra ',+.'

# Answer
> 1 votes
# io

### 659 + 553 = 1212

Things like `File standardInput readBufferOfLength(1)` really kill the byte count but I can't get around it. I didn't do optimizations for repeated symbols or lack of input in the BF program, but will continue to work on it, also working on one making use of io's metaprogramming capabilities.

```
"v :=Vector clone setSize(30000)
p :=0
z :=getSlot(\"method\")
j :=z(p=p+1)
k :=z(p=p-1)
a :=z(v at(p))
l :=z(v atPut(p,a+1))
m :=z(v atPut(p,a-1))
n :=z(a asCharacter print)
u :=getSlot(\"while\")
o :=z(v atPut(p,File standardInput readBufferOfLength(1)))"println
z :=getSlot("method")
g :=z(a,b,if(a,a,b))
v :=z(e,f,if((x :=s)==e,nil,f .. g(w(x),"")))
s :=z(File standardInput readBufferOfLength(1))
w :=z(c,c switch(">",v("<","j"),"<","k","+","l","-","m",".","n",",","o","[",v("]","u(a>0,"),"]",")"))
while((c :=s)!=nil,if((t :=w(c))!=nil,t println))

```

Testing

```
cat test.bf | io bftrans.io > out.io && io out.io && echo && echo  $(cat out.io | wc -c) " + " $(cat bftrans.io | wc -c) " = "$(($(cat bftrans.io | wc -c) + $(cat out.io | wc -c)))

```

Yields

```
Hello world!
659  +  553  = 1212

```

# Answer
> 0 votes
# Lua - 328 + 2256 = 2584

(Oh I just realized you need to add the length of the result too, poor score, it looks like)

```
print((("l,m,p=loadstring,{0},1 z,y,x,w,v,u=l'io.write(string.char(@))',l'@=io.read(1):byte()',l'p=p-1',l'p=p+1 @=@or 0',l'@=(@+1)%256',l'@=(@-1)%256'"..io.read"*a":gsub("[^.,<>[%]+-]",""):gsub(".",{["."]="z()",[","]="y()",["<"]="x()",[">"]="w()",["["]="while @~=0 do ",["]"]="end ",["+"]="v()",["-"]="u()"})):gsub("@","m[p]")))

```

Taken from this answer of mine.

---
Tags: code-golf, brainfuck, metagolf
---


title: Drawing convex polyiamonds

text:
# Question
Title: Drawing convex polyiamonds
# Description

OEIS sequence A096004 gives the

> Number of convex triangular polyominoes \[polyiamonds\] containing n cells.

It begins:

```
1, 1, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 5

```

For example, a(8)=3 with the following three convex polyiamonds:

```
Input: 8
Output:
  *---*---*---*---*
 / \ / \ / \ / \ /
*---*---*---*---*

    *---*---*
   / \ / \ /
  *---*---*
 / \ / \ /
*---*---*

    *---*
   / \ / \
  *---*---*
 / \ / \ / \
*---*---*---*

```

---

# Requirements

The goal of this challenge is to write a program that takes in an integer *n* (in any reasonable format) and outputs ASCII art of all convex polyiamonds with *n* cells (in any orientation), with each polyiamond separated by two newlines.

Your program must be able to handle up to a(30) in under 60 seconds.

---

# Scoring

This is a challenge, so fewest bytes wins.

# Answer
# Charcoal, 89 bytes

```
ＮθＦ⊕θＦ⊕ιＦ⊕κＦ⊕λ¿∧¬‹ι⁺⁺κλμ⁼⁻×ιιθΣＥ⟦κλμ⟧×νν«⸿Ｇ↙⊕⊗μ↘⊕⊗⁻ι⁺κμ→⊕×⁴κ↗⊕⊗⁻ι⁺κλ↖⊕⊗λ“⌈∨¿ZH↖↖⸿T u≡9”Ｄ⎚

```

Try it online! Link is to verbose version of code. Thanks to @LevelRiverSt for explaining the OEIS formula. Explanation:

```
Ｎθ

```

Input `n`. (Using the OEIS formula names rather than the Charcol names here.)

```
Ｆ⊕θＦ⊕ιＦ⊕κＦ⊕λ

```

Loop `p` from `0` to `n`, `d` from `0` to `p`, `c` from `0` to `d` and `b` from `0` to `c` inclusive. This satisfies the condition `b<=c<=d<=p`.

```
¿∧¬‹ι⁺⁺κλμ⁼⁻×ιιθΣＥ⟦κλμ⟧×νν«

```

Check the other two conditions: `b+c+d<=p` and `n=p*p-b*b-c*c-d*d`. Sadly the power function doesn't vectorise yet otherwise that would save 2 bytes.

```
⸿

```

Leave a blank line between polyiamonds.

```
Ｇ↙⊕⊗μ↘⊕⊗⁻ι⁺κμ→⊕×⁴κ↗⊕⊗⁻ι⁺κλ↖⊕⊗λ“⌈∨¿ZH↖↖⸿T u≡9”

```

Draw the polyiamond. Five of the sides are calculated, and the sixth is inferred and the polygon filled using the compressed string `/ \` `*---` `\ /` `--*-`, which results in the desired pattern. (The pattern doesn't start with `*---` because the blank line causes the pattern to be offset.)

```
Ｄ⎚

```

Output and clear the canvas ready for the next polyiamond. This is quicker than positioning the cursor.
> 2 votes

# Answer
# Ruby, 202 bytes

```
->n{(r=[*0..n]).product(r,r,r).map{|i|p,b,c,d=i;b>c||c>d||b+c+d>p||p*p-b*b-c*c-d*d!=n||0.upto(p-d<<1){|j|s=" "*j+"*---\\ / "[j%2*4,4]*p*2;(k=b*4-j)>0&&s[0,k]=" "*k;puts s[0,[p*4+1-j,p*4+1-c*4+j].min]}}}

```

Try it online!

Uses formula per the OEIS sequence: search for solutions where `n = p**2 - b**2 -c**2 - d**2`.

`n =`the number of triangular tiles

`p =`the side length of a large equilateral triangle (pointing downwards)

`b,c,d =`the side length of three smaller equilateral triangles, which are removed from the corners of the large equilateral triangle to get the required shape.

Some additional conditions (per OEIS) are needed to avoid duplicates: `b<=c<=d` and `b+c+d<=p`
> 6 votes

---
Tags: code-golf, ascii-art, geometry, polyomino
---


title: Compose two Brainfuck programs

text:
# Question
Title: Compose two Brainfuck programs
Given 2 brainfuck code snippets `A` and `B`, output some brainfuck code `C` which has the same behavior as running `B` with the input of `A`s result. Note that `C` must work for any input that match the following assumptions, as if it were given to `A`.

You can assume:

1. Finite input.
2. both A and B halt.
3. EOF is consistently 0 or consistently -1.
4. Consistently allow or disallow cells to left
5. Unbounded tape (otherwise the requirement may be impossible)
6. Consistently 8-bit wrapping or unbounded integer
7. No stream(input or output for A or B) contain the byte representing EOF
8. Code A and B can contain characters that possibly appear in your C, and `+-[]<>,.`

E.g. (EOF=0)

```
A = ,[..,]
B = ,[...,]
C = ,[......,]

A = >,[>,]<[.<]
B = ,[...,]
C = >>>>,[[-<+<+<+>>>]>>>,]<<<<[.<]

A = >,[>,]<[.<]
B = ,[...,]
C = >,[>,]<[...<]

A = ,.
B = ,.
C = ,>,[,]<.

A = ,.
B = ,.
C = ,.

```

are valid tests

Shortest code in each language win. Winner in Brainfuck will be accepted.

# Answer
> 8 votes
## brainfuck, 526 bytes

```
-<+++++<+<+++++<-[+++++++[<++++++++>-]<--->>]<<--<--<+..<<<<,[[<+>>+<-]----[>-<-
---]>[+[++[++++++++++++++[++[[-]<]<<<[>-->>>-.>>>.<<<.>.>.<<.+>>--..>.<..<.>.>..
<++.<.>..>.<..<.>--.>>.<<.>.<..<.>.>.<.<.>++.<<.>.>.>.<.<.>..>.<..<.>>>.<<--.++<
<<]>>>>[<]<]>[<<<<[>]>[+>>>>>.>.<<<.>.<.>>>.<.[.<.>>>]<++[<<.<.>>.<<--.<<.>.>.++
>>>-]<<<<.>.>>.<.<<<.>>..>>.<<<.>--.>.<++...<<.>>--..>>.<.<..<.>.>>.<<++...>.<..
<.>>>.<<--...++<<[.>]<<<--.<<.>>++.<.>>>.<<--.++<<<]]<]>[<<<.>>]<]>[>>.>.<<<.>.>
>>.[<]]<]>[>>.>.<..<.>>>.[<]<<<+>->>]<<.[-]>,]

```

Formatted:

```
-<+++++<+<+++++<-[+++++++[<++++++++>-]<--->>]
<<--<--<+..<<<<
,
[
  [<+> >+<-]
  ----[>-<----]>
  [
    not question mark
    +
    [
      not greater than
      ++
      [
        not less than
        ++++++++++++++
        [
          not period
          ++
          [
            not comma
            [-]<
          ]
          <<<
          [
            comma B
            >-->>> -.>>>.<<<.>.>.<<.+>>--..>.<..<.>.>..<++.<.>..>.<..<.>--.>>.<<
            .>.<..<.>.>.<.<.>++.<<.>.>.>.<.<.>..>.<..<.>>>.<<--.++<<<
          ]
          >>>>[<]<
        ]
        >
        [
          period
          <<<<
          [
            B
            >
          ]
          >
          [
            A
            +>>> >>.>.<<<.>.<.>>>.<.[.<.>>>]<++[<<.<.>>.<<--.<<.>.>.++>>>-]<<<<.
            >.>>.<.<<<.>>..>>.<<<.>--.>.<++...<<.>>--..>>.<.<..<.>.>>.<<++...>.<
            ..<.>>>.<<--...++<<[.>]<<<--.<<.>>++.<.>>>.<<--.++<<<
          ]
        ]
        <
      ]
      >
      [
        less than
        <<<.>>
      ]
      <
    ]
    >
    [
      greater than
      >>.>.<<<.>.>>>.[<]
    ]
    <
  ]
  >
  [
    question mark
    >>.>.<..<.>>>.[<]
    <<<+>->>
  ]
  <<.[-]>,
]

```

With respect to A, B, and C: EOF = 0, cells left of start disallowed, 8-bit wrapping cells.

Expects A followed by `?` followed by B.

Try it online

(This answer can be made compliant with a brainfuck interpreter that doesn't allow going left of the start at the cost of one byte by transliterating `y/<>/></` and prepending a `>`.)

The basic idea is to use a series of string replacements in order to simulate the tapes of A and B using 2-cell nodes, with special attention given to replacing `.` in A and `,` in B so that the intermediate data stream is kept in a block of cells to the left of the simulated tape. The string replacement scheme is:

* Insert `>>` before A
* In both A and B, replace `>` with `>[-]+>` and `<` with `<<`
* In A, replace `.` with `>[-]-[>>]+[[>+<-]<[>+<-]<]>+[->>+]<[>>>-<<+[<<]<+>>>[>>]+<<<-]>[+<->]+</`
* Insert `>[>>]+>` after A and before B
* In B, replace `,` with `,[,]>,<<[<<]<[[>]>>[>>]<+<[<<]<[<]>-]>[>]>>[>>]+<*`

# Answer
> 6 votes
# brainfuck, 1287 bytes

```
++++++++++++++++[->+++>+++>++++>++++>++++++>++++++<<<<<<]>----->--->---->-->----->--->+<<<.....<<.>>....<<.>>.<<..>...>>>>[>+>,->[-]++++[-<-------->]+<[>>]>[<<-<-<<<..>.<.....>>.<<<.....>>.<<<<.>>..>>.<<<.>>>>.<<<...>>>.<<.<<<..>>>>.<<<..>>.....<<<..>>>>>.<<<<<.>>>>.<<<.>.....<<.>>>>>.<<<<.>>..>>>>>>>>]<<<-------------[>>]>[<<-<<<<..<<.>..>>.<<<.>.<<.>>>....<<<.>>>>.<<<.>.....<<.>>>>>.<<<<<.>>>>.<<<..>>.....<<<..>>>>>.<<<<..>..<<.>>>..<<<.>>>>.<<<.>.....<<.>>>>>.<<<<.>.<<..>>>>.<<<..>>.....<<<..>>>>>.<<<<..>..>>>.<<<.>>.<<<.>>.<<<.>>.>>>.<<....<<<.>>>>.<<<.>.....<<.>>>>>.<<<<<.>>>>.<<<..>>.....<<<..>>>>>.<<.....<<.>>>.<<<.>.....<<.>>>>>.<<<<.>.<<..>>>>.<<<..>>.....<<<..>>>>>.<<<<.>..>>>>>>>>>]<<<--------------[>>]>[<<-<<<<<...>>.<<<<.>>>>>.<<<<.>..>>>>>>>>>]<<<--[>>]>[<<-<<<<.......>.<<<<.>>>>>.<<<<.>..>>>>>>>>>]<<<<[+++++++[->++++++++<]>--.<]<]>>,[<+>>++++[-<--------->]+<+[>>]>[<<-<<<.<<<.>>>>.<<..<<.>>.>.<.....>>.<<<<<.>>>>.<<<.>.....<<.>>>>>.<<<<.>>...>.<<<.>...>>.<<.....>>>.<<....<<<.>>>>.<<<.>>.....<<<.>>>>>.<<<<.>..<<.>>>...>.<.....>>.<<<<<.>>>>.<<<.>.....<<.>>>>>.<<<<.>>...>>.<<..<<.>>>.<<.....>>>.<<....<<<.>>>>.<<<.>>.....<<<.>>>>>.<<<..>>>>>>>>>]<<<----------------[>>]>[<<-<<<<<.....>>>>>>>>>]<<<--[>>]>[<<-<<<<.....>>>>>>>>]<<<<[+++++++[->++++++++<]>--.<]>,]

```

Try it online!

Here it is! The brainfuck code that composes two brainfuck codes. Use a "!" to separate the two input code snippets. For example snippet A: `>,[>,]<[.<]`, snippet B: `,[...,]`. Input for my program: `>,[>,]<[.<]!,[...,]`. It will not terminate if no "!" is found.

This does essentially the same as my VBA Version. The code that is generated is the same as in the VBA version (note that the examples in the VBA post were made before the latest change in the brainfuck snippets).

**Explanation**

This is my source code:

```
[
Tape: "+"(43) "-"(45) "<"(60) ">"(62) "["(91) "]"(93) readA(1) printInput(0) input else exitIf exitElse
]

++++ ++++ ++++ ++++ [->+++>+++>++++>++++>++++++>++++++<<<<<<]>----->--->---->-->----->--->+

<<<.....<<.>>....<<.>>.<<..>... print init routine
>>>>[                           while readA
  >+                              set printInput = true
  >,                              read character
  ->[-]++++[-<-------->]          decrease input by 33 to check for "!"
  +                               set else flag

  # A check for "!"
  <[                              if input not "!"
    >>                              go to exitIf
  ]
  >[                              else
    <<-                             set printInput = false
    <-                              set readA = false
    <<<..>.<.....>>.<<<.....>>.<<<< print routine between A and B
    .>>..>>.<<<.>>>>.<<<...>>>.<<.<
    <<..>>>>.<<<..>>.....<<<..>>>>>
    .<<<<<.>>>>.<<<.>.....<<.>>>>>.
    <<<<.>>..>>>
    >>>>>                           go to exitElse
  ]

  # A check for "dot"
  <<<----- ----- ---              decrease input by 13 (total 46) to check for dot
  [                               if input not dot
    >>                              go to exitIf
  ]
  >[                              else
    <<-                             set printInput = false
    <<<<..<<.>..>>.<<<.>.<<.>>>.... print list storing routine
    <<<.>>>>.<<<.>.....<<.>>>>>.<<<
    <<.>>>>.<<<..>>.....<<<..>>>>>.
    <<<<..>..<<.>>>..<<<.>>>>.<<<.>
    .....<<.>>>>>.<<<<.>.<<..>>>>.<
    <<..>>.....<<<..>>>>>.<<<<..>..
    >>>.<<<.>>.<<<.>>.<<<.>>.>>>.<<
    ....<<<.>>>>.<<<.>.....<<.>>>>>
    .<<<<<.>>>>.<<<..>>.....<<<..>>
    >>>.<<.....<<.>>>.<<<.>.....<<.
    >>>>>.<<<<.>.<<..>>>>.<<<..>>..
    ...<<<..>>>>>.<<<<.>..>>>>>
    >>>>                            go to exitElse
  ]

  # A check for "less than"
  <<<----- ----- ----             decrease input by 14 (total 60) to check for "less than"
  [                               if input not "less than"
    >>                              go to exitIf
  ]
  >[                              else
    <<-                             set printInput = false
    <<<<<...>>.<<<<.>>>>>.<<<<.>..>>>>> print A move left routine
    >>>>                            go to exitElse
  ]

  # A check for "greater than"
  <<<--                           decrease input by 2 (total 62) to check for "greater than"
  [                               if input not "greater than"
    >>                              go to exitIf
  ]
  >[                              else
    <<-                             set printInput = false
    <<<<.......>.<<<<.>>>>>.<<<<.>..>>>>> print A move right routine
    >>>>                            go to exitElse
  ]

  # print remaining character
  <<<<[                           if printInput
    +++++++[->++++++++<]>--.<     print original character
  ]

<                               go to readA
]

>>,                             read next character
[                               while input
  <+                              set printInput = true

  # B check for comma
  >>++++[-<----- ---->]+<+        decrement input by 44 to check for comma
  [                               if input not comma
    >>                              go to exitIf
  ]
  >[                              else
    <<-                             set printInput = false
    <<<.<<<.>>>>.<<..<<.>>.>.<..... print B list reading routine
    >>.<<<<<.>>>>.<<<.>.....<<.>>>>
    >.<<<<.>>...>.<<<.>...>>.<<....
    .>>>.<<....<<<.>>>>.<<<.>>.....
    <<<.>>>>>.<<<<.>..<<.>>>...>.<.
    ....>>.<<<<<.>>>>.<<<.>.....<<.
    >>>>>.<<<<.>>...>>.<<..<<.>>>.<
    <.....>>>.<<....<<<.>>>>.<<<.>>
    .....<<<.>>>>>.<<<..>>>>>
    >>>>                            go to exitElse
  ]

  # B check for "less than"
  <<<----- ----- ----- -          decrease input by 16 (total 60) to check for "less than"
  [                               if input not "less than"
    >>                              go to exitIf
  ]
  >[                              else
    <<-                             set printInput = false
    <<<<<.....>>>>>                 print B move left routine
    >>>>                            go to exitElse
  ]

  # B check for "greater than"
  <<<--                           decrease input by 2 (total 62) to check for "greater than"
  [                               if input not "greater than"
    >>                              go to exitIf
  ]
  >[                              else
    <<-                             set printInput = false
    <<<<.....>>>>                   print B move right routine
    >>>>                            go to exitElse
  ]

  # print remaining character
  <<<<[                           if printInput
    +++++++[->++++++++<]>--.<     print original character
  ]

>,                              input next character
]

```

# Answer
> 5 votes
# VBA, ~~512~~ ~~489~~ 479 bytes

```
Sub f(A,B):Debug.?">>>>>->>>>->--<<<"&Replace(Replace(Replace(A,"<","<<<[+]-<<"),">",">>>>>>>[+]-<<"),".",">>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<")&">>[>>>>>]<<<<<[+<<[-]<<<]>++[-->>>>>++]+[-<<<<<+]->>"&Replace(Replace(Replace(B,"<","<<<<<"),">",">>>>>"),",","[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<"):End Sub

```

**Explanation**

The VBA code changes the brainfuck code in a way, that the output of snippet A will be stored in a list and the input of snippet B will be read from that list.

It first initializes some variables

```
>>>>>->>>>->--<<<

```

Then it reads snippet A and replaces every `<` by `<<<[+]-<<`, every `>` by `>>>>>>>[+]-<<` and every `.` by the storing routine

```
>>>>>>>[+]-<<"),".",">>->+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]--<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>+<<

```

after that it deletes the memory of snippet A and makes changes to the stored list, so it can be read as input for snippet B:

```
>>[>>>>>]<<<<<[+<<[-]<<<]>++[-->>>>>++]+[-<<<<<+]->>>>>-<<<

```

Then snippet B will be read, every `<` will be replaced by `<<<<<`, every `>` will be replaced by `>>>>>` and every `,` will be replaced by the list reading routine:

```
[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<

```

**Brainfuck source code**

This is my source for the brainfuck portions of the code. I will explain that in detail later.

```
[
Tape: tempMem data out/in dataAnchors outAnchors (all repeating)
dataAnchors of Snippet A: -1 = memory has been used, -2 = active memory cell for copying to out/in
dataAnchors of Snippet B: -1 = active memory cell for copying from out/in
outAnchors of Snippet A: -1 = start of list, -2 = next output position
outAnchors of Snippet B: -1 = character has been read (or start of input)
]

### Init
>>              two blank data cells (for non wrapping pointer)
>>>-            set start of input
>> >>-          set first "used" flag
>--             set end of input
<<<             return to first usable data cell

### A move right routine
>>>>>           move to the next data cell
>>[+]-          clear and set "used" flag
<<              return to data cell

### A move left routine
<<<[+]-         clear and set "used" flag of previous data cell
<<              go to data cell

### A print routine
>>-             set flag
<<[             while value greater 0
  -               decrement value
  <+              increment tempMem
  >>>>+[-<<<<<+]  find start of input
  +[-->>>>>++]--  find end of input
  <<+             increment input
  >>+[-<<<<<+]-   find start of input
  <++[-->>>>>++]--find flag
  <<              go to active data cell
]
<[->+<]         move stored value back to data
>>>>+[-<<<<<+]  find start of input
+[-->>>>>++]    find end of input
>>>>>-          set new end of input
[-<<<<<+]-      return to start of input
<++[-->>>>>++]- return to and delete data flag
<<              go to data cell

### After snippet A: Delete memory of A and configure out/in list
>>[>>>>>]<<<<< go to last used data
[+<<[-]<<<]    delete each data
>++[-->>>>>++] find and delete end of input flag
+[-<<<<<+]-    go to start of input
>>             go to first data cell

### B move right routine
>>>>>          go to next data cell

### B move left routine
<<<<<          go to previous data cell

### B reading routine
[-]                      set cell = 0
>>-                      set flag
>[>>>>>]+[-<<<<<+]-      find start of input
>>>[                     if value greater 0
  -                        decrement value
  <<<[<<<<<]>>>>           go to initial start of input (combined with next)
  +[->>>>>+]-              find mem cell flag
  <<+                      increment mem cell
  >>>[>>>>>]+[-<<<<<+]->>> return to input cell
]
>>-                      set new start of input
[<<<<<]>>>>              go to initial start of input (combined with next)
+[->>>>>+]               find and delete mem cell flag
<<                       go to mem cell

```

Output for test case 1: `f ",[..,]",",[...,]"`

```
>>>>>->>>>->--<<<,[>>->+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]--<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>+<<>>->+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]--<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>+<<,]>>[>>>>>]<<<<<[+<<[-]<<<]>++[-->>>>>++]+[-<<<<<+]->>>>>-<<<[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<[...[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<]

```

Try it online!

Output for test case 2: `f ">,[>,]<[.<]",",[...,]"`

```
>>>>>->>>>->--<<<>>>>>>>[+]-<<,[>>>>>>>[+]-<<,]<<<[+]-<<[>>->+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]--<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>+<<<<<[+]-<<]>>[>>>>>]<<<<<[+<<[-]<<<]>++[-->>>>>++]+[-<<<<<+]->>>>>-<<<[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<[...[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<]

```

Try it online!

Output for test case 3: `f ",.",",."`

```
>>>>>->>>>->--<<<,>>->+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]--<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>+<<>>[>>>>>]<<<<<[+<<[-]<<<]>++[-->>>>>++]+[-<<<<<+]->>>>>-<<<[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<.

```

Try it online!

**Complex test case:** Snippet A: Build alphabet triangle `>+++++[<+++++>-]<+[>>[>[.>]]>++++++++++.--[<++++++++>-]<[+.<]<-]>>,>[.>]++++++++++.[<[.<]>,>[.>]<]` Try it online!

Snippet B: Sort input in ascending order `>>,[>>,]<<[[-<+<]>[>[>>]<[.[-]<[[>>+<<-]<]>>]>]<<]` Try it online!

Result:

```
>>>>>->>>>->--<<<>>>>>>>[+]-<<+++++[<<<[+]-<<+++++>>>>>>>[+]-<<-]<<<[+]-<<+[>>>>>>>[+]-<<>>>>>>>[+]-<<[>>>>>>>[+]-<<[>>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<>>>>>>>[+]-<<]]>>>>>>>[+]-<<++++++++++>>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<--[<<<[+]-<<++++++++>>>>>>>[+]-<<-]<<<[+]-<<[+>>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<<<<[+]-<<]<<<[+]-<<-]>>>>>>>[+]-<<>>>>>>>[+]-<<,>>>>>>>[+]-<<[>>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<>>>>>>>[+]-<<]++++++++++>>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<[<<<[+]-<<[>>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<<<<[+]-<<]>>>>>>>[+]-<<,>>>>>>>[+]-<<[>>-<<[-<+>>>>+[-<<<<<+]+[-->>>>>++]--<<+>>+[-<<<<<+]-<++[-->>>>>++]--<<]<[->+<]>>>>+[-<<<<<+]+[-->>>>>++]>>>>>-[-<<<<<+]-<++[-->>>>>++]-<<>>>>>>>[+]-<<]<<<[+]-<<]>>[>>>>>]<<<<<[+<<[-]<<<]>++[-->>>>>++]+[-<<<<<+]->>>>>>>>>>>>[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<[>>>>>>>>>>[-]>>->[>>>>>]+[-<<<<<+]->>>[-<<<[<<<<<]>>>>+[->>>>>+]-<<+>>>[>>>>>]+[-<<<<<+]->>>]>>-[<<<<<]>>>>+[->>>>>+]<<]<<<<<<<<<<[[-<<<<<+<<<<<]>>>>>[>>>>>[>>>>>>>>>>]<<<<<[.[-]<<<<<[[>>>>>>>>>>+<<<<<<<<<<-]<<<<<]>>>>>>>>>>]>>>>>]<<<<<<<<<<]

```

Try it online!

# Answer
> 5 votes
# Brainfuck, 785 bytes

```
--->---->--->----->-->----->>++++[-<++++>]<[-<++++++<++++<+++<++++++<++++<+++>>>>>>]<<...<<<<.>.>>>>>>>,[[-<+<+>>]+++++++[-<------>]+<--[--[-[-------------[--[[-]>[-]<<.>]>[-<<<<.<..>..>.<<<<<.>>.<<.>.>>>>>>>]<]>[-<<<<.<..<<..<..>.>>>>>>>]<]>[-<<<<.<..>>.<..<<.<<.>.>>>>>>>>>+<<]<]>[->>>+<[>-<<<<<.>>>>>]>[-<<<<<<<...>.<<<<<.>>.>.<<..>>>>.<..<<.<..>>>>..<<<<<.>>>>.<.<<.>.<.>>>>.<<<<<.>>>>.<.<<.>.<.>.>>...<.>>.<<<<<.>>>>..<.<.<.>>>>.<<<<<.>>>>...<.<<....>>>>.<<<<..>.<.>>.>...>.<..<<.<.>.>>...<<<<.>>>>>.<<<<<.>...>>.>...<<.>.<<..<.>.>>>>>>>>>>>]<<<<]<]>[->>>+<[>-<<<<<<.<<<<<.>>.>>.<.<<..>>>>.<<<<..>.<..>>>>.<<<<.>.>>.>.<<<<<.>.>>.>.<<.<.>>>>.<<<<<.>>>>..>.<.<<.>>..>.<..<<.<.>>.<<.>>>>.<<<<..>.<.>>>>.<<<<.>.<.>.>>..>.<.<<.>>..>.<..<<.<<.>.>>>>>>>>>>]>[-<<<<<.>>>>>>]<<<<]<<[-]>>,]

```

Try it online!

To split A from B I opted for `/`.

Explaination:

The actual code that generates this is just a read-loop with a flag for A/B and a switch that reduces the input to look for `>`, `<`, `/`, `,`, and `.` and otherwise just output the input. It is actually just a transpiler where the transpiled code lives within a data structure such that it don't interfere with the stored data from A or each other. The `/` just moves the active cell to the first unused cell. I originally cleaned it up, but that makes the program and output larger.

The program result has the following memory model:

```
|0|input*|cz|d0|c0|d2|c0|...

```

The `c` is crumble. `cz` is always `0` It points out where in my emulated BF data the pointer is. The active value is -1 while all visited cells will have `1`. In operations like `aprint` and `bread` some `c` get special meaning.

A-code print skips all cells 1 byte to leave room for one more byte input which is copies with a backup in the next bytes crumble to copy back.

B-code read fetches input from input. Here being destructive is ok and when you "read" the last byte you get 0 as EOF regardless of the implementation.

I started out as Extended BrainFuck code making EBF result. Most of the debugging was done on the result files and then updates to the source that generated it. Then i just run the operations independent to get BF output, but I noticed Dorian's answer, which beat me in length so I continued golfing EBF source for smaller BF output. The original source is quite readable and simple compared to other stuff I've done with it:

```
:bck
:i
:t
:z
:r
:rc
:rz

;;; outputs a header with most of the result logic
{cinit
  |"
    ;; memory model of the result
    ML/i/z/d/c
    PTR=1/1/2
    :iz:i:z:d:c:d2:c2

    ;; moves pointer back. Bad things will happen to
    ;; A output if out of bounds
    {backward @d2 $c2++ $c-- $d
    }

    ;; moves pointer forward
    {forward $c++ $c2[-]- $d2 @d
    }

    ;; stores the current cell in input a the start of bf data
    {aprint
      $c2(-)+                 ; mark next cell as used even if it maybe
      $c[$c2]                 ; go to the end of used data
      $c((->+)$d(->+)@d2)     ; as long as c is something move d and c one place right
      @i$c+[->>+]@c           ; go to active cell, zero it
      $d(-                    ; copy:
        $c2+                  ; backup in c2
        $z[<<]@z              ; back to i
        $i+ $c[>>]@c          ; increement and back to zero carry
      )
      $c2-(- $d+)+            ; copy backup in c2 back to d
      $c-                     ; mark active cell
      $d                      ; move to d
    }

    ;; removes all the data from A. And initializes for B
    {aend
      $c[$c2]
      $c((-)<(-)<@c)@z
      $c-$d
    }

    ;; instead of read b fetched from input area
    {bread
      (-)>+@c2          ; clear d and c
      $c[$z]            ; go to z
      $i<[<] @iz        ; go to iz
      $i(-$iz+)         ; switch places between i and iz
      $iz(-             ; copy from iz to d
         $z[>]@z        ; move to z
         $c[$c2]        ; move to the current c
         $d2+           ; increase d
         $c[$z]         ; back to z
         $i[$iz]        ; back to iz
         @i             ; but since we shave switched correct
      )
      $z[>]@z           ; go back to z
      $c[$c2]-          ; move to active cell and make it -1
      $d2 @d            ; go to d
    }

    $c-$d               ; init. Go to c t mark it active, then go to d
    "
  (-)
}

{cmain
  &cinit
  $t,(
    (-$i+$bck+) ; pour to i and bck

    ;; switch ( $i ) cases '<>,./' using $t
    $t+++++++(-$i------)+$i--; ,
    ($i--; .
      ($i-; /
        ($i-------------; <
          ($i--; >
            ((-) $t(-)  $bck.)
              $t (- |"&forward "(-) )
          ) $t (- |"&backward "(-) )
        ) $t (- |"&aend "(-) $r+ )
      ) $t (- $rc+$r[$rc-$bck.$rc]@r$rc[- |"&aprint "(-) $rz])
    ) $t (- $rc+$r[$rc-|"&bread "(-)]@r$rc[-$bck.$rz])
    $bck (-) ; clear backup
      $t,    ; read into t
  )
}

&cmain

```

# Answer
> 4 votes
## sed, 165 bytes

```
s > >[-]+> g
s < << g
1s \. >[-]-R+[[>+<-]<[>+<-]<]>+[->>+]<[>+>>-<L+>R+<<<-]>[<+>-]+< g
1s .* R&<R+>
2s , ,[,]>,<L[[>]R<+L[<]>-]>[>]R+< g
s L <[<<]< g
s R >>[>>] g

```

For flavors with EOF = 0, cells left of start disallowed, 8-bit wrapping cells.

Expects program A on the first line and B on the second line.

Try it online

This uses 2-cell nodes to simulate the tapes of A and B, with A's output occupying contiguous cells to the left of the leftmost node.

Alternative 173-byte solution:

```
1i>>
s > >[-]+> g
s < << g
1s \. >[-]-[>>]+[[>+<-]<[>+<-]<]>+[->>+]<[>>>-<<+[<<]<+>>>[>>]+<<<-]>[<+>-]+< g
1a>[>>]+>
2s , ,[,]>,<<[<<]<[[>]>>[>>]<+<[<<]<[<]>-]>[>]>>[>>]+< g

```

Try it online

Originally my design was based on a doubly infinite tape, which required significantly more work to move left (moving data when passing beyond the leftmost cell previously encountered) and to transition from A to B (clearing the data instead of just traveling past the rightmost cell previously encountered).

Thanks to Sylwester and Dorian for tricks and ideas.

---
Tags: code-golf, code-generation, brainfuck
---


title: The Time Anagram

text:
# Question
Title: The Time Anagram
Originally posted (and deleted) by *@Tlink*, which was most likely inspired from this StackOverflow question.
Since it was a shame it got deleted, because it seemed like a good challenge in general, I figured I'd repost it with proper formatting and rules. (I've tried contacting *@Tlink* and get his/her permission to post it, but (s)he doesn't respond any more, which is why I decided to post it myself now.)

**Input:** Six digits.

**Output:** Either the first or last valid time in the 24-hour format (`00:00:00` through `23:59:59`). (You can choose yourself whether you output the first or last valid time.)

**Example:**

When the inputs are `1,8,3,2,6,4`, the following times can be created:

```
12:36:48    12:38:46    12:46:38    12:48:36
13:26:48    13:28:46    13:46:28    13:48:26
14:26:38    14:28:36    14:36:28    14:38:26
16:23:48    16:24:38    16:28:34    16:28:43
16:32:48    16:34:28    16:38:24    16:38:42
16:42:38    16:43:28    16:48:23    16:48:32
18:23:46    18:24:36    18:26:34    18:26:43
18:32:46    18:34:26    18:36:24    18:36:42
18:42:36    18:43:26    18:46:23    18:46:32
21:36:48    21:38:46    21:46:38    21:48:36
23:16:48    23:48:16

```

So we'll output either `12:36:48` or `23:48:16` in this case, being the first / last respectively.

## Challenge rules:

* State whether you output the first or last valid time in your answer.
* I/O is flexible. Input can be six separated integers; a string containing the six digits; an integer list/array; a single (possibly octal) number; etc. Output can be a correctly ordered list/array of digits; a String in the format `HH:mm:ss`/`HHmmss`/`HH mm ss`; every digit printed with new-line delimiter; etc. Your call.
* You are allowed to take the digits in any order you'd like, so they can already be sorted from lowest to highest or vice-versa.
* If no valid time can be created with the given digits (i.e. `2,5,5,5,5,5`), make so clear in any way you'd like. Can return `null`/`false`; `"Not possible"`; crash with an error; etc. (You cannot output an invalid time like `55:55:52`, or another valid time like `00:00:00`.) Please state how it handles inputs for which no valid time can be created.
* You are not allowed to output all possible valid times. Only the earliest/latest should be outputted/returned.
* `24` for hours (i.e. `24:00:00`), or `60` for minutes/seconds (i.e. `00:60:60`) are not valid. The ranges are `[00-23]` for hours and `[00-59]` for minutes and seconds.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

## Test cases:

```
Input:          Earliest output:     Latest output:

1,2,3,4,6,8     12:36:48             23:48:16
2,5,5,5,5,5     None possible        None possible
0,0,0,1,1,1     00:01:11             11:10:00
1,1,2,2,3,3     11:22:33             23:32:11
9,9,9,9,9,9     None possible        None possible
2,3,5,5,9,9     23:59:59             23:59:59
1,2,3,4,5,6     12:34:56             23:56:41
0,0,0,0,0,0     00:00:00             00:00:00
1,5,5,8,8,8     18:58:58             18:58:58
1,5,5,5,8,8     15:58:58             18:58:55
1,1,1,8,8,8     18:18:18             18:18:18

```

# Answer
# C (gcc), ~~186~~ 174 bytes

```
D[7]={0,1,10,100,1e3,1e4,1e5};G(O,L,F,T,I,M,E){if(!F)O=L<24e4&L%10000<6e3&L%100<60?L:1e9;else{for(T=1e9,I=0;I++<F;M=G(O/10,L*10+E,F-1),T=T>M?M:T,O=(O/10)+E*D[F])E=O%10;O=T;}}

```

Try it online!

-12 bytes thanks to Kevin Cruijssen

Probably not optimal, but it works. Oddly enough for some reason with 7 arguments the gcc implementation on TIO requires that you actually supply them or it segfaults. On my machine that is unnecessary however.

Format: G(X,0,6) -\> Y where X is the 6-digit number whose digits are to be used and Y is the 6 digit number which when taken as a time (by inserting : appropriately) is minimal.
> 9 votes

# Answer
# Haskell, ~~114~~ ~~96~~ 86 bytes

```
import Data.List
f l=minimum[x|x@[a,b,c,d,e,f]<-permutations l,a:[b]<"24",c<'6',e<'6']

```

Now with less strict output. Takes input as a string of digits and compares permutations against limits with list comparison. With minutes and seconds only the first digit is checked. Crashes and burns if no permutation is a valid time.

Try it online!
> 6 votes

# Answer
# Python 2, ~~131~~ ~~115~~ ~~112~~ ~~109~~ ~~105~~ 88 bytes

```
lambda s:min(d for d in permutations(s)if(2,4)>d[:2]>d[4]<6>d[2])
from itertools import*

```

Try it online!

I/O are lists of integers

Throws an error if no times are possible

---

Alternative:

# Python 2, 88 bytes

```
lambda s:max(d*((2,4)>d[:2]>d[4]<6>d[2])for d in permutations(s))
from itertools import*

```

Try it online!

Returns the latest time

Returns an empty tuple for invalid times

---

Saved

* -21 bytes, thanks to ovs
> 5 votes

# Answer
# Japt, 17 bytes

Takes input as a string of digits and outputs the first valid time; loops infinitely if there's no valid time.

```
á
@øXr':}a@ÐX ¤¯8

```

Try it

> **Warning:** Extremely slow - add `*1000` after the second `X` to speed it up somewhat. And don't forget that an invalid input will create an infinite loop and may crash your browser.

---

## Explanation

```
                   :Implicit input of string U
á                  :Get all permutations of U
\n                 :Reassign that array to U
      }a           :Loop until true and then return the argument that was passed
        @          :By default that argument is an integer X which increments on each loop so first we'll pass X through a function
         ÐX        :  new Date(X)
            ¤      :  Get the time
             ¯8    :  Slice to the 8th character to get rid of the timezone info
@                  :The function that tests for truthiness
  Xr':             :  Remove all colons in X
 ø                 :  Does U contain the resulting string?

```
> 5 votes

# Answer
# JavaScript (ES6), ~~93~~ ~~89~~ 88 bytes

Expects an array of 6 digits, sorted from lowest to highest. Returns either the 6-digit string of the first valid time, or `false` if no solution exists.

```
f=(a,t='')=>t<24e4&/..([0-5].){2}/.test(t)?t:a.some((v,i)=>s=f(a.filter(_=>i--),t+v))&&s

```

Try it online!

### Commented

We recursively try all permutations of the input until we find one that passes a hybrid test using both arithmetic and a regular expression.

```
f = (                       // f = recursive function taking
  a, t = ''                 // a[] = input array and t = current time
) =>                        //
  t < 24e4 &                // if t is less than 240000
  /..([0-5].){2}/.test(t) ? // and it matches "hhMmSs" with M and S in [0-5]:
    t                       //   return t
  :                         // else:
    a.some((v, i) =>        //   for each digit v at position i in a[]:
      s = f(                //     save in s the result of a recursive call with:
        a.filter(_ => i--), //       a copy of a[] with the current digit removed
        t + v               //       the current digit appended to t
      )                     //     end of recursive call
    ) && s                  //   end of some(); if truthy, return s

```
> 5 votes

# Answer
# 05AB1E, ~~20~~ 15 bytes

Input as sorted string.
Output is the smallest time as a string.
In case of no solution, an empty list is the output.

```
œʒ2ô•3Èñ•2ô‹P}н

```

Try it online!
> 5 votes

# Answer
# Retina, ~~77~~ ~~74~~ ~~69~~ ~~65~~ 62 bytes

```
$
:
6+Lv$`(.)(.*):
$%`$2:$1$%'
O`
0L`([01].|2[0-3])([0-5].){2}

```

Try it online! Outputs the earliest time, or the empty string if no time can be found. Edit: Saved ~~5~~ 8 bytes thanks to @TwiNight. Explanation:

```
$
:
6+Lv$`(.)(.*):
$%`$2:$1$%'

```

Generate all the permutations. The `:` works its way though the string as the permutations are generated, ending up at the start.

```
O`

```

Sort the times into order.

```
0L`([01].|2[0-3])([0-5].){2}

```

Output the first valid time.
> 5 votes

# Answer
# Red, 157 124 bytes

Thanks to Kevin Cruijssen for reminding me to read the descritions more carefully!

```
func[s][a: 0:0:0 loop 86400[b: to-string a a: a + 1 if b/1 =#"0"[insert b"0"]if s = sort replace/all copy b":"""[return b]]]

```

Try it online!

Takes a sorted string as input. Returns `none` if it's not possible to make time.

## Explanation:

```
f: func[s][                                    ; the argument is a sorted string of digits
    a: 0:0:0                                   ; time object, set to 00:00:00 h
    loop 86400 [                               ; loop through all seconds in 24 h
        b: to-string a                         ; convert the time to string
        a: a + 1                               ; add 1 second to the current time
        if b/1 = #"0" [                        ; prepend "0" if necessary
            insert b "0"                       ; (Red omits the leading 0)
        ]
        if s = sort replace/all copy b ":" ""[ ; compare the input with the sorted time
            return b                           ; return it if they are equal
        ]
    ]
]

```
> 4 votes

# Answer
# Ruby, ~~68 67 62 56~~ 55 bytes

```
->*b{b.permutation.find{|a,b,c,d,e|c<6&&e<6&&a*9+b<22}}

```

Try it online!

Input: **Sorted** array of digits (as integers).

Output: Array of digits or `nil` if no solution found
> 3 votes

# Answer
# Japt, ~~39~~ 23 bytes

Pretty sure there's a shorter way to do this, but I wanted to try using Date objects in Japt.

```
á ®¬ò q':Ãf@T<ÐXiSiKÅ
Ì

á                     // Get all permutations of the input array.
  ®¬ò q':Ã            // [1,2,3,4,5,6] -> "12:34:56"
          f@          // Filter the results, keeping those that
            T<        // are valid dates
              ÐXiSiKÅ // when made into a date object.
Ì                     // Return the last remaining item, if any.

```

Takes input as a sorted array of numbers, returns the latest valid time or empty output if none exists.
Lost 10 ~~pounds~~ bytes thanks to Shaggy.

Try it here.
> 3 votes

# Answer
# Python 2, 78 bytes

```
lambda s:min(x for x in range(62**3)if x%100<60>x/100%100<s==sorted('%06d'%x))

```

Try it online!

Arnauld saved a byte. Thanks!

Expects a list like `['1','2','3','4','6','8']` in sorted order:

> You are allowed to take the digits in any order you'd like, so they can already be sorted from lowest to highest or vice-versa.

Outputs an integer like `123648` for 12:36:48. I hope that's acceptable.
> 3 votes

# Answer
# Jelly, 15 bytes

```
Œ!s€2Ḍf«¥“ç;;‘Ṃ

```

Try it online!

Posted after a request. The approach is the same as the one of the other answer, however this answer was developed independently.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 63 bytes

```
FirstCase[Permutations@#,{a:0|1|2,b_,c_,_,d_,_}/;a*b-4<6>d>=c]&

```

Try it online!

Takes a **sorted** list of digits as input. Returns `Missing[NotFound]` for invalid inputs.

### Explanation

```
Permutations@#

```

Find all of the permutations of the input. Since the input is sorted, it is guaranteed that all valid times are in increasing order.

```
FirstCase[ ... ]

```

Find the first list that matches...

```
{a:0|1|2,b_,c_,_,d_,_}

```

The first element, labeled `a`, is 0, 1, or 2, and label the second, third, and fifth elements `b`, `c`, and `d` respectively...

```
... /;a*b-4<6>d>=c

```

... such that `a*b` is less than 10, and `d` and `c` are less than 6, with `d >= c`.

The trick is that for all numbers `00` to `24`, the product of the two digits is at most 9, and the possible invalid numbers `25` to `29` (since we force the first digit to be 0, 1, or 2) have the product of least 10.
> 2 votes

# Answer
# Jelly, 17 bytes

I'm almost certain this is not the shortest approach... will look at this again later :)

```
Œ!s2Ḍ<ẠʋÐṀ“ð<<‘ṢḢ

```

**Try it online!**
> 2 votes

# Answer
## Perl 5 with `-palF`, 73 bytes

```
$"=",";($_)=grep@F~~[sort/./g]&/([01]\d|2[0-3])([0-5]\d){2}/,glob"{@F}"x6

```

Try it online!

Outputs like `HHmmss` and outputs a blank line for invalid entries.

Every answer I've made recently has used `glob`ing for permutations... Weird!
> 2 votes

# Answer
## Bash + GNU sed, 83, 72, 69 bytes

* Accepts input as 6 separate arguments;
* Returns the earliest time (if found);
* Returns nothing (empty output) if no valid combination exist.

`seq 0 86399|sed "s/^/date +%T -ud@/e;h;`printf s/%d//\; $@`/\w/d;x;q"`

**How it works**

Pre-generate all the possible time strings, for the timestamps in range 0 to 86399, using GNU-sed **e**(xecute) command + `date`.

`%seq 0 86399|sed "s/^/date +%T -ud@/e;h;"`

```
00:00:00
00:00:01
...
23:59:59

```

Generate `sed` script with 6 sequential substitution commands, for an each input digit.

`%echo sed `printf s/%d//\; $@``

```
sed s/1//;s/2//;s/3//;s/4//;s/6//;s/8//;

```

Then, apply substitutions, remove any input lines which have at least one digit left, print the first matching line (original time string is extracted from the hold space with `x`).

```
%echo 23:45:12|sed 's/1//;s/2//;s/3//;s/4//;s/6//;s/8//;'
:5:2 //non-matching, delete

%echo 12:36:48|sed 's/1//;s/2//;s/3//;s/4//;s/6//;s/8//;'
:: //matching, print and stop

```

**Test**

```
%./timecomb 1 2 3 4 6 8
12:36:48
%./timecomb 2 5 5 5 5 5
%./timecomb 0 0 0 1 1 1
00:01:11
%./timecomb 1 1 2 2 3 3
11:22:33
%./timecomb 9 9 9 9 9 9
%./timecomb 2 3 5 5 9 9
23:59:59
%./timecomb 1 2 3 4 5 6
12:34:56
%./timecomb 0 0 0 0 0 0
00:00:00
%./timecomb 1 5 5 8 8 8
18:58:58
%./timecomb 1 5 5 5 8 8
15:58:58
%./timecomb 1 1 1 8 8 8
18:18:18

```

Try It Online !
> 2 votes

# Answer
# Pyth, 37 bytes

```
j\:hf&&<shT24<s@T1 60<seT60mcs`Md2S.p

```

**Test suite**

Explanation:
```
j\:hf&&<shT24<s@T1 60<seT60mcs`Md2S.pQ # Code with implicit variables
   h                                   # The first element of
                                   .pQ # The list of all permutations of the input list
                                  S    # Sorted
                           mcs`Md2     # Mapped to three two digit long strings
    f                                  # Filtered on whether
       <shT24                          #  The first number is less than 24
      &      <s@T1 60                  #  AND the second number is less than 60
     &               <seT60            #  AND the third number is less than 60
j\:                                    # Joined by a colon

```
> 2 votes

# Answer
# Kotlin, ~~396~~ ~~391~~ 389 bytes

No clue how to make this smaller. I'm thinking it is double of what's possible. Produces earliest time. Thanks to Kevin for 7 bytes!

```
fun p(d:Array<Int>)={val s=Array(6,{0})
val f=Array(6,{1>0})
val t=Array(3,{0})
val o=Array(3,{60})
fun r(i:Int){if(i>5){var l=0>1
var e=!l
for(p in 0..2){t[p]=s[p*2]*10+s[p*2+1]
l=l||(e&&t[p]<o[p])
e=e&&t[p]==o[p]}
if(t[0]<24&&t[1]<60&&t[2]<60&&l)for(p in 0..2)o[p]=t[p]}
else
for(p in 0..5)if(f[p]){f[p]=0>1
s[i]=d[p]
r(i+1)
f[p]=1>0}}
r(0)
if(o[0]>23)0
else "${o[0]}:${o[1]}:${o[2]}"}()

```

Try it online!
> 2 votes

# Answer
# MATL, ~~31~~ 30 bytes

```
Y@3Xy[X1]X*!Y*t[4XX]6*<!AY)1Y)

```

Try it online!

Input is 6 integers, output is the minimum hour, minutes, and seconds in an array. Crashes for inputs where no such time is possible.

*(-1 byte thanks to @Luis Mendo.)*
> 2 votes

# Answer
# Perl 6, 43 bytes

```
*.permutations.first:{24e4>.join&&6>.[2&4]}

```

Try it online!

Expects a sorted input array. Returns `Nil` for invalid input.
> 1 votes

# Answer
# Stax, 15 bytes

```
╝a╣=→aá≈#8(⌂≈58

```

Run and debug it

It takes a string of sorted digits for input. It returns the first permutation that satisfies a few criteria.

* lexicographically less than "24"
* all three pairs of characters are lexicographically less than "6"
> 1 votes

# Answer
# Retina, ~~58~~ 47 bytes

```
+,V^2`[0-5][6-9]{2}
G`([01].|2[0-3])([0-5].){2}

```

Try it online!

Input is 6 digits in sorted order. Output is 6 digits representing earliest valid time, or empty string if no valid time exists.

EDIT: I was an idiot, -9 bytes

## Explanation

**Algorithm**

For brevity, let's define a low digit as 0-5, and a high digit as 6-9.

First, rearrange the digits so that "low-ness" or "high-ness" of each position is correct. The correct arrangement, for each number of high digits in the input:

```
# of highs  arrangment
0           LLLLLL
1           LLLLLH
2           LLLHLH
3           LHLHLH
4+          Not possible

```

Since the any rearrangement would fail the final check in the input has 4+ high digits, we can ignore that case completely.

Then, sort the lows and the highs individually. Combine with the rearrangement, this gives the lowest value that satisfies the minute and second constraints. So this gives the earliest valid time, if one exists.

Finally, check if that we have valid time. If not, discard the string.

---

**Program**

```
+,V^2`[0-5][6-9]{2}

```

Matches `LHH` and swaps the first two digits in that (becomes `HLH`), and repeat that until no more `LHH` exists. This gives the correct arrangement.

Actually, I lied. No sorting is needed because 1) swapping only happens between adjacent digits and only between a low and a high; and 2) the input is sorted. So the lows and the highs individually are already in sorted order.

```
G`([01].|2[0-3])[0-5].[0-5].

```

Only keeps the string if it is a valid time
> 1 votes

---
Tags: code-golf, date
---


title: Perfect Squares below \$n\$

text:
# Question
Title: Perfect Squares below \$n\$
> *A perfect square is an integer that is the square of an integer; in* *other words, it is the product of some integer with itself.*

**Calculate the number of perfect squares below a number \\$n\\$ where \\$n\\$ will be taken as an input**

---

**Examples:**

There are 9 perfect squares below 100: 1, 4, 9, 16, 25, 36, 49, 64, 81

**Constraints:** \\$0\<n\<10^6\\$

---

Since this is a golfing challenge, the entry with least amount of bytes will win.

Best of Luck!

# Answer
# Panacea, 3 bytes

```
<qc

```

Explanation:

```
<     decrement
 q    square root
  c   floor

```
> 1 votes

# Answer
# brainfuck, ~~161~~ 160 bytes

```
,>>>>>>+[-<<<<<+[>+>+>+<<<-]>[-<+>]>[>[>+<<<+>>-]>[<+>-]<<-]>[-]<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<[>>[-]>+<<<-]>>>[<<<+>>>-]<[>>+<<-]<<->-]<[-]>>>>]<<<<<-.

```

Try it online!

Finally, a challenge simple enough that I could attempt some brainfuckery.

Credits to https://esolangs.org/wiki/Brainfuck\_algorithms for the squaring algorithm and the comparison algorithm ideas, Fatih Erikli's brainfuck visualizer, and to El Brainfuck for quick runs.

*(Also to user202729 for noticing an unnecessary space in the code and for a link with a bash I/O wrapper.)*

Calculates \\$ i^2 \\$ for each \\$ i \\$ starting from 1, and checks if \\$ i^2 \< n \\$. Returns the last \\$ i \\$ for which that's true.

~~Input and output are usually ASCII characters representing numbers. For eg., in the TIO link, input `d` (ASCII 100) returns character tab `\t` (ASCII 9).~~  Now links to a version that takes and returns numeric I/O directly. Assumes a wrapping implementation (for the comparison algorithm).

```
, n input
> i = 0
> isqr/temp0
> icopy1/ncopy/temp1
> icopy2/temp2
> temp3
> exitflag (is isqr lt n)
+[-                 while exitflag not 0
  <<<<<
  +                 increment i
  [>+>+>+<<<-]      make 3 copies of i (destructively)
  >[-<+>]           use one of them (temp0) to restore i

  Squaring by multiplying icopy1 with icopy2:
  >[                while icopy1 not 0
    >[>+<<<+>>-]    copy icopy2 to temp3 and add it to isqr
    >[<+>-]         restore icopy2 from temp3
    <<-             decrement icopy1
  ]
  >[-]              reset temp2 (icopy2) to 0

  Comparing n and isqr:
  <<<<[>>>+>+<<<<-] copy n to ncopy and temp2
  >>>>[<<<<+>>>>-]  restore n from temp2
  <[                while ncopy
    >+              increment temp2 as flag
    <<[>>[-]>+<<<-] if isqr gt 0 reset temp2 (destroys isqr & copies to temp3)
    >>>[<<<+>>>-]   restore isqr from temp3
    <[>>+<<-]       set exitflag to 1 if temp2 was not reset
    <<->-           decrement isqr & decrement ncopy
    ]
  <[-]              reset isqr (would have been set to negative of n minus isqr)
  >>>>              check the flag and exit if isqr gt n
]
<<<<<-.              decrement i by 1 and output

!

```
> 5 votes

# Answer
# brainfuck, 49 bytes

Use byte-value input/output. Can only process numbers up to maximum cell value. Requires a tape that has at least 3 cells to the left and 2 cells to the right of the initial memory pointer.

```
+>>,[<[<<]<[[<+>>+<-]++<[>+<-]<<+>]>>>->-]<<<<<-.

```

Try it online!

(with nice Bash wrapper that converts decimal input/output to byte input/output)

---

Based on the identity \\$1 + 3 + 5 + \dots + (2n-1) = n^2\\$ (so it subtracts 1, then 3, then 5, then 7, ... from the input \\$n\\$ until it is \\$\le 0\\$, then count number of subtraction)

Explanation:

```
# Mem layout: {r t A a c x}. Ptr initially at {a}.
# {t} == 0. r == result. a == 1, then increase to 3, 5, ...
# {c} counts from {a} to 0.
# {x} is the input, gradually decremented.

+        # a=1
>>,      # read x
[        # while x:
  <        # goto c
  [<<]<    # if c, goto {t}, else goto {a}
  [        # if not c:
    [<+>>+<-]    # A=c=a; a=0
    ++<[>+<-]    # a=2+A; A=0
    <<+>         # r+=1
  ]
  # now mem pointer is at {t} regardless of initial
  # value of {c}, and c!=0
  >>>-     # c-=1
  >-       # x-=1
]
<<<<<-.  # print r-1

```

Compilable Python code works the same way -- explanation in reverse.
> 3 votes

# Answer
# Brain-Flak, 58 bytes

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

```

Try it online!
> 3 votes

# Answer
# Jelly, 3 bytes

```
’Æ½

```

Try it online!

Simply takes the floor of the square root of \\$n-1\\$. Assumes \\$0\\$ should be counted and assumes that we ought to find the number of perfect squares strictly lower than \\$n\\$. (This is just an illustration of why such trivial challenges are discouraged)
> 2 votes

# Answer
# Japt, 4 bytes

*Port of Mr. XCoder Jelly Implementation*

```
´U¬f

```

Try it online!
> 1 votes

# Answer
# JavaScript, 25 bytes

```
f=n=>--n&&!(n**.5%1)+f(n)

```

Try it online
> 1 votes

# Answer
# Dodos, ~~121~~ 120 bytes

Also based on the identity \\$1 + 3 + 5 + \dots + (2n-1) = n^2\\$ . Thanks to H.PWiz for saving some bytes.

```
	dip f 1
f
	+ 1 > - A f F
F
	> - i r
	+ 1 1 >
i
	i I
I
	>
	>
r
	>
	> - A
A
	+ >
	+
-
	- dip
1

	dip + _
_
+
	dot
>
	dab

```

Try it online!

Fortunately there are no scroll bar in the code...

---

```
_       Returns an empty list.
1       Append 1.
-       Assume x<y, given (x, y) return (0, y-x).
> - A   Get the first element of a list (return 0 for empty list).
r       Reverse a list of 2 elements.
i       Incremential: Given (x, y) return (x, y) if x<y else (y, y).
f       Main function.

```

Writing Dodos code is similar to Haskell that all functions are (effectively) pure.

Bonus Haskell code (ungolfed) which this solution bases on.
> 1 votes

# Answer
# MATL \- 4 bytes

Using the same approach as others

```
qX^k

```

Try it at MATL Online

**Explanation**

```
      Implicitly grab input
q     Subtract 1
X^    Compute the square root
k     Round down
      Implicitly display the result

```
> 1 votes

# Answer
# Brain-Flak, 76 bytes

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

```

Try it online!

## Explanation

Uses a simple counting method. It has 3 counters, the number, the slice and the result. We decrement the number until it reaches zero, each time we do we also decrement the slice if it is non-zero. If the slice is zero we increment the result and set the slice to one less than twice the result.

This computes the square root via the sum of consecutive odds.
> 1 votes

# Answer
# JavaScript (Node.js), ~~14~~ 12 bytes

*-2 bytes by @Shaggy*

```
_=>--_**.5|0

```

Try it online!
> 0 votes

# Answer
# Neim, 7 bytes

```
Λq)<

```

Try it online!
> 0 votes

# Answer
# Noether, 9 bytes

```
I1-0.5^_P

```

**Try it in the interpreter!**

## Explanation:

This is just an implementation of the formula \\$\left\lfloor{\sqrt{n-1}}\right\rfloor\\$:

```
I         - Push the user input onto the stack
 1        - Push 1 onto the stack
  -       - Pop two numbers a and b off the stack and push the result of a-b
   0.5    - Push 0.5 onto the stack
      ^   - Pop two numbers a and b off the stack and push the result of a^b
       _  - Pop the number on the top of stack, floor it and push the result
        P - Print the item on the top of the stack

```
> 0 votes

# Answer
# Java 8, 22 bytes

```
n->(int)Math.sqrt(n-1)

```

Lambda using the formula \\$\left\lfloor{\sqrt{n-1}}\right\rfloor\\$. Trivial implementation. Try it online here.
> 0 votes

# Answer
# C (gcc), 18 bytes

```
f(n){n=sqrt(n-1);}

```

Trivial implementation of the formula \\$\left\lfloor{\sqrt{n-1}}\right\rfloor\\$. Try it online here.
> 0 votes

---
Tags: code-golf, math
---


title: Tell me the Lunar Phase!

text:
# Question
Title: Tell me the Lunar Phase!
## Challenge

Given an image of the Moon as input, output the phase of the Moon.

## Phases of the Moon

Your program will be supplied one of these images in png format and you must output the phase exactly as given:

```
new moon

```

hexdump

```
waxing crescent

```

hexdump

```
first quarter

```

hexdump

```
waxing gibbous

```

hexdump

```
full moon

```

hexdump

```
waning gibbous

```

hexdump

```
third quarter

```

hexdump

```
waning crescent

```

hexdump

## Input

The input will be the path to a 240 px by 240 px png file and will be the one of the images above.

The image bytes are guaranteed to be the same.

## Winning

Shortest code wins

# Answer
# Node.js, 145 bytes

```
p=>'third/waning/first/full/waxing/new'.split`/`[(s=require('fs').statSync(p).size)%418%6]+' '+'quarter/crescent/gibbous/moon'.split`/`[s%12%9%4]

```

Try it online! (generates dummy files with the same sizes)

### How?

We just look at the size of the file and convert it to indices in two lookup tables.

First part:

```
 phase | file size | mod 418 | mod 6 | mapped to
-------+-----------+---------+-------+-----------
   0   |    3451   |    107  |    5  | new
   1   |    6430   |    160  |    4  | waxing
   2   |    5144   |    128  |    2  | first
   3   |    7070   |    382  |    4  | waxing
   4   |    5283   |    267  |    3  | full
   5   |    7067   |    379  |    1  | waning
   6   |    4976   |    378  |    0  | third
   7   |    6337   |     67  |    1  | waning

```

Second part:

```
 phase | file size | mod 12 |  mod 9 |  mod 4 | mapped to
-------+-----------+--------+--------+--------+-----------
   0   |    3451   |     7  |     7  |    3   | moon
   1   |    6430   |    10  |     1  |    1   | crescent
   2   |    5144   |     8  |     8  |    0   | quarter
   3   |    7070   |     2  |     2  |    2   | gibbous
   4   |    5283   |     3  |     3  |    3   | moon
   5   |    7067   |    11  |     2  |    2   | gibbous
   6   |    4976   |     8  |     8  |    0   | quarter
   7   |    6337   |     1  |     1  |    1   | crescent

```
> 9 votes

# Answer
# Python 2, ~~223~~ 222 bytes

<sup>-1 byte thanks to OMᗺ</sup>

```
lambda p:'new moonzzfull moonzzfirst quarterzzwaxing crescentzzwaning gibbouszzwaxing gibbouszthird quarterzwaning crescent'.split('z')[sum(n*Image.open(p).getpixel((n*48,99))[2]for n in[1,2,3,4])%13]
from PIL import Image

```

`getpixel((x,y))` \- will return the RGBA pixel at `x,y`
`getpixel((n*48,99))[2]for n in[1,2,3,4]` \- will return the blue channel of the middle line, where `n*48 ... for n in 1,2,3,4` will be 4 points where the sunlight may cover
`n*getpixel(...)` \- will generate a different value for each column
`sum(...)%13` \- these values are added together and `%13` is used to get an unique value to each phase, that will be used as index for the phase list
The pixels are approximately inside the red circles:
> 7 votes

# Answer
## Ruby, 131 bytes

```
->f{f=open(f,'rb').read;%w[first third waxing new full waning][f[699].ord%7]+' '+%w[x moon gibbous quarter crescent][f[998].ord%5]}

```

Byte offsets found by brute force -- taking the 699th byte of the file modulo 7, for instance, gives an index into the first lookup table.
> 5 votes

# Answer
# Python 2, ~~196~~ 165 bytes

```
lambda f:'first quarter|new moon|waning crescent|waxing gibbous|third quarter|full moon|waxing crescent|waning gibbous'.split('|')[sum(map(ord,open(f).read()))%41%9]

```

Try it online!
> 2 votes

# Answer
# PHP (\>=5.4), ~~199~~ 197 bytes

(-2 bytes by more golfing)

```
<?$s=strlen(file_get_contents($argv[1])).'';echo strtr([waning_crescent,waning_gibbous,new_moon,0,waxing_crescent,waxing_gibbous,full_moon,first_quarter,third_quarter][($s[0]+$s[3])%11-2],'_',' ');

```

To run it:

```
php -d error_reporting=0 -d short_open_tag=1 <filename> <image_path>

```

Example:

```
php -d error_reporting=0 -d short_open_tag=1 lunar_phase.php https://upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Moon_phase_6.svg/240px-Moon_phase_6.svg.png

```

**Notes:**

* The `-d error_reporting=0` option is used to not output notices/warnings.
* The `-d short_open_tag=1` is required to allow short tags.
* If you are using a `https` URL like the example above, OpenSSL should also be enabled.

---

# How?

Gets file size (bytes) and creates a unique number for it by this formula:

`((<first_bytes_digit> + <fourth_bytes_digit>) % 11) - 2`

This formula generates numbers from 0 to 8 with only a 3 missing.

```
┌─────────────────┬───────┬─────────┬─────┬────────────────────────┐
│      Phase      │ Bytes │ 1st+4th │ %11 │ -2 (position in array) │
├─────────────────┼───────┼─────────┼─────┼────────────────────────┤
│ new moon        │  3451 │ 3+1=4   │   4 │                      2 │
│ waxing crescent │  6430 │ 6+0=6   │   6 │                      4 │
│ first quarter   │  5144 │ 5+4=9   │   9 │                      7 │
│ waxing gibbous  │  7070 │ 7+0=7   │   7 │                      5 │
│ full moon       │  5283 │ 5+3=8   │   8 │                      6 │
│ waning gibbous  │  7067 │ 7+7=14  │   3 │                      1 │
│ third quarter   │  4976 │ 4+6=10  │  10 │                      8 │
│ waning crescent │  6337 │ 6+7=13  │   2 │                      0 │
└─────────────────┴───────┴─────────┴─────┴────────────────────────┘

```

---

# Previous approaches:

### PHP (\>=5.4), 251 bytes

```
<?foreach([4,8,16,20]as$w){$a+=imagecolorat(imagecreatefrompng($argv[1]),$w*10,120)>1e7;$a&&$w<5?$b=-2:0;}$x=explode('_','full moon_waning gibbous_third quarter_waning crescent_new moon_waxing crescent_first quarter_waxing gibbous');echo$x[$a*++$b+4];

```

To run it:

```
php -d error_reporting=0 -d short_open_tag=1 <filename> <image_path>

```

Example:

```
php -d error_reporting=0 -d short_open_tag=1 lunar_phase.php https://upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Moon_phase_6.svg/240px-Moon_phase_6.svg.png

```

**Notes:**

* The `-d error_reporting=0` option is used to not output notices/warnings.
* The `-d short_open_tag=1` is required to allow short tags.
* PHP must have GD and it should be enabled.
* If you are using a `https` URL like the example above, OpenSSL should also be enabled.

---

### How?

Checks for the color of 4 pixels in the image at `40,120`, `80,120`, `160,120` and `200,120` and decides on the moon phase from those colors.
> 1 votes

---
Tags: code-golf, image-processing
---


# Question
Title: Given N, output n-th element of ['A', 'B', 'AB', 'C', 'D', 'CD', 'ABCD', 'E', ...]?
Consider the following list:

```
expected = [
'A',
'B',
'AB',
'C',
'D',
'CD',
'ABCD',
'E',
'F',
'EF',
'G',
'H',
'GH',
'EFGH',
'ABCDEFGH',
'I',
'J',
'IJ',
'K',
'L',
'KL',
'IJKL',
'M',
'N',
'MN',
'O',
'P',
'OP',
'MNOP',
'IJKLMNOP',
'ABCDEFGHIJKLMNOP',
...
]

```

Here's one way to look at it - you're learning how to write Chinese characters and want to learn increasingly big chunks of them, rehearsing them as you go. You start with A, then go with B, then there's already a sequence that is a pair of two so you combine it. Then you go with C and D, make another pair, practice it. Then you rehearse: ABCD. Then the same goes with E up to H, then rehearse: ABCDEFGH. The list is infinite.

The goal is to generate and print out an n-th element of this list, indexes going up from zero. Assume that after 'Z', you get 'A' again.

The winning criteria is source code length.

# Answer
# Python 2, 53 bytes

```
x,y=0,1
exec"x^=y-x;y+=x/y;"*input()
print range(x,y)

```

Try it online!

Similar to this construction with the transformation `x = u-v`, `y = u`
> 8 votes

# Answer
# JavaScript (ES6), 59 bytes

We can save 2 bytes by making the sequence 1-indexed and using a simplification similar to the one used by KSab:

```
n=>(x=g=y=>n?g(y+=y==(x^=y-x),n--):x<y?[x++,...g(y)]:[])(1)

```

Try it online!

---

# JavaScript (ES6), 61 bytes

Returns a list of non-wrapping integers.

```
n=>(g=v=>n?g(u&-u^v?v*2:!!u++,n--):v?[u-v,...g(v-1)]:[])(u=1)

```

Try it online!

Based upon a construction by Donald Knuth. Related OEIS entry: A182105.

### How?

This is a two-stage recursive function.

We first build the sequence \\$(u\_n,v\_n)\\$ defined as \\$(u\_1,v\_1)=(1,1)\\$ and:

$$(u\_{n+1},v\_{n+1})=\begin{cases}(u\_{n}+1,1),&\text{if }(u\_{n}\operatorname{AND}-u\_{n})=v\_{n}\\\(u\_{n},2v\_{n}),&\text{otherwise}\end{cases}$$

During the second pass, we build the list \\$\[u\_n-v\_n,u\_n-v\_n+1,\dots,u\_n\]\\$ and eventually return it.

---

# JavaScript (ES6), 97 bytes

Returns wrapping uppercase letters.

```
n=>(s=i='',g=v=>(s+=String.fromCharCode(65+i++%26),n--)?g(u&-u^v?v*2:!!u++):s.substr(u-v,v))(u=1)

```

Try it online!

Or **91 bytes** in lowercase.
> 6 votes

# Answer
# Python 2, 60 bytes

```
u=v=1
exec"v=u/v%2or 2*v;u+=1/v;"*input()
print range(u-v,u)

```

Try it online!

Based on Arnauld's use of Knuth's construction. The condition `u&-u==v` can be replaced with a simpler condition `u/v%2>0`, or alternatively `u&v>0`, since `v` is always a power of 2 that `u` is divisible by.
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~80~~ 71 bytes

```
Range@#2+#-#2&@@Nest[If[#~BitAnd~-#==#2,{#+1,1},{#,2#2}]&@@#&,{1,1},#]&

```

Try it online!

Returns a list of integers instead of a wrapping string of alphabet. 0-indexed.

Uses OEIS A182105, thanks to @Arnauld.

### Printing the list indefinitely, 54 bytes

```
Do[j=Range@i;#∣i&&Print@j[[-#;;]]&/@(2^j/2),{i,∞}]

```

Try it online!

1-indexed. The TIO version has `lim` instead of  to prevent crashes.
> 2 votes

# Answer
# Python 2, ~~93~~ ~~89~~ 82 bytes

```
def f(n):r=[];C=1;exec"p=C%2or 2*p;r+=[p];C=r.count(p);"*n;return range(C*p-p,C*p)

```

Try it online!

Returns a list of integers. Similar to Arnauld's Javascript approach.
> 2 votes

# Answer
# Jelly, 16 bytes

```
1;ẎṀ+ƊẎQṭƊƊ¡ị@‘Ṿ

```

Try it online! TIO link works well up to and including \\$13\\$.

Full program. Prints `,`-separated list of integers.
> 1 votes

# Answer
# Charcoal, ~~45~~ ~~42~~ 35 bytes

```
ＦＮ⊞υ⎇∧›Ｌυ¹⁼Ｌ§υ±¹Ｌ§υ±²⁺⊟υ⊟υ§αＬ⭆υκ⮌⊟υ

```

Try it online! Link is to verbose version of code. 1-indexed. I couldn't find a simple formula to generate the result so I simply followed the procedure given in the question. Explanation:

```
ＦＮ

```

Repeat the given number `n` times.

```
⊞υ

```

Push the next element to the predefined empty array `u`, calculated as...

```
⎇∧›Ｌυ¹⁼Ｌ§υ±¹Ｌ§υ±²

```

... if there is more than one element in `u` and the last two elements have the same length...

```
⁺⊟υ⊟υ

```

... then append the penultimate element to the last element (which builds up the result in reverse order)...

```
§αＬ⭆υκ

```

... otherwise the next letter can be found by counting how many letters we've added so far and cyclically indexing into the predefined uppercase alphabet. (Taking either the sum of length or length of sum fails when the list is empty, and mapping the list into a string saves two bytes over special-casing an empty list.)

```
⮌⊟υ

```

Take the last element of `u`, which is the reversed `n`th element of the desired list, and implicitly print the reverse.
> 1 votes

---
Tags: code-golf, sequence, alphabet
---


title: Rail fence cipher

text:
# Question
Title: Rail fence cipher
Write two programs:
\- One which reads a string and a key and encodes the string into a rail-fence cipher using that key. \- Similarly, write a program for the reverse function: deciphering a rail fence using a key.

For those who don't know what rail fence cipher is, it is basically a method of writing plain text in a way it creates linear pattern in a spiral way. Example - when "FOOBARBAZQUX" rail-fenced using key of 3.

```
F . . . A . . . Z . . . .
  O . B . R . A . Q . X
    O . . . B . . . U

```

Reading the above spiral line-by-line, the cipher text becomes "FAZOBRAQXOBU".

Read more at - Rail fence cipher - Wikipedia.

Code in any language is welcome.

Shortest answer in bytes wins.

# Answer
> 9 votes
## Python 133 bytes

```
def cipher(t,r):
 m=r*2-2;o='';j=o.join
 for i in range(r):s=t[i::m];o+=i%~-r and j(map(j,zip(s,list(t[m-i::m])+[''])))or s
 return o

```

Sample usage:

```
>>> print cipher('FOOBARBAZQUX', 3)
FAZOBRAQXOBU

>>> print cipher('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 4)
AGMSYBFHLNRTXZCEIKOQUWDJPV

>>> print cipher('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 5)
AIQYBHJPRXZCGKOSWDFLNTVEMU

>>> print cipher('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 6)
AKUBJLTVCIMSWDHNRXEGOQYFPZ

```

Note: the results from even rail counts are different than for the code you provided, but they seem to be correct. For example, 6 rails:

```
A         K         U
 B       J L       T V
  C     I   M     S   W
   D   H     N   R     X
    E G       O Q       Y
     F         P         Z

```

corresponds to `AKUBJLTVCIMSWDHNRXEGOQYFPZ`, and not `AKUTBLVJICMSWXRDNHQYEOGZFP` as your code produces.

The basic idea is that each rail can be found directly by taking string slices `[i::m]`, where `i` is the rail number (`0`-indexed), and `m` is `(num_rails - 1)*2`. The inner rails additionally need to be interwoven with `[m-i::m]`, achieved by zipping and joining the two sets of characters. Because the second of these can potentially be one character shorter, ~~it is padded with a character assumed not to appear anywhere (`_`), and then that character is stripped off if necessary~~ it is converted to a list, and padded with an empty string.

---

A slightly more human readable form:

```
def cipher(text, rails):
  m = (rails - 1) * 2
  out = ''
  for i in range(rails):
    if i % (rails - 1) == 0:
      # outer rail
      out += text[i::m]
    else:
      # inner rail
      char_pairs = zip(text[i::m], list(text[m-i::m]) + [''])
      out += ''.join(map(''.join, char_pairs))
  return out

```

# Answer
> 2 votes
## APL ~~52~~ 41

```
i←⍞⋄n←⍎⍞⋄(,((⍴i)⍴(⌽⍳n),1↓¯1↓⍳n)⊖(n,⍴i)⍴(n×⍴i)↑i)~' '

```

If the input text string i and the key number n are preinitialised the solution can be shortened by 9 characters. Running the solution against the examples given by primo gives identical answers:

```
FOOBARBAZQUX
3
FAZOBRAQXOBU

ABCDEFGHIJKLMNOPQRSTUVWXYZ
4
AGMSYBFHLNRTXZCEIKOQUWDJPV

ABCDEFGHIJKLMNOPQRSTUVWXYZ
5
AIQYBHJPRXZCGKOSWDFLNTVEMU

ABCDEFGHIJKLMNOPQRSTUVWXYZ
6
AKUBJLTVCIMSWDHNRXEGOQYFPZ

```

On further reflection there appears to be a shorter index based solution:

```
i[⍋+\1,(y-1)⍴((n←⍎⍞)-1)/1 ¯1×1 ¯1+y←⍴i←⍞]

```

# Answer
> 1 votes
# Python 2, 124 + 179 = 303 bytes

Encode:

```
lambda t,k:''.join(t[i+j]for r in R(k)for i in R(k-1,len(t)+k,2*k-2)for j in[r-k+1,k+~r][:1+(k-1>r>0)]if i+j<len(t))
R=range

```

Try it online!

Decode:

```
lambda t,k:''.join(t[dict((b,a)for a,b in enumerate(i+j for r in R(k)for i in R(k-1,len(t)+k,2*k-2)for j in[r-k+1,k+~r][:1+(k-1>r>0)]if i+j<len(t)))[m]]for m in R(len(t)))
R=range

```

Try it online!

# Answer
> 0 votes
# Java 10, ~~459~~ ~~451~~ ~~445~~ ~~439~~ ~~327~~ 325 bytes

```
(s,k,M)->{int l=s.length,i=-1,f=0,r=0,c=0;var a=new char[k][l];for(;++i<l;a[r][c++]=M?s[i]:1,r+=f>0?1:-1)f=r<1?M?f^1:1:r>k-2?M?f^1:0:f;for(c=i=0;i<k*l;i++)if(a[r=i/l][i%l]>0)if(M)System.out.print(a[r][i%l]);else a[r][i%l]=s[c++];if(!M)for(r=c=i=0;i++<l;f=r<1?1:r>k-2?0:f,r+=f>0?1:-1)if(a[r][c]>1)System.out.print(a[r][c++]);}

```

-14 bytes thanks to *@ceilingcat*.
-112 bytes combining the two functions with an additional mode-flag as input.

The function takes a third input `M`. If this is `true` it will encipher, and if it is `false` it will decipher.

Try it online.

### Explanation:

```
(s,k,M)->{              // Method with character-array, integer, and boolean parameters
                        // and no return-type
  int l=s.length,       //  Length of the input char-array
      i=-1,             //  Index-integer, starting at -1
      f=0,              //  Flag-integer, starting at 0
      r=0,c=0;          //  Row and column integers, starting both at 0
  var a=new char[k][l]; //  Create a character-matrix of size `k` by `l`
  for(;++i<l            //  Loop `i` in the range (-1, `l`):
      ;                 //    After every iteration:
       a[r][c++]=       //     Set the matrix-cell at `r,c` to:
         M?s[i++]       //      If we're enciphering: set it to the current character
         :1,            //      If we're deciphering: set it to 1 instead
       r+=f>0?          //     If the flag is 1:
           1            //      Go one row down
          :             //     Else (flag is 0):
           -1)          //      Go one row up
    f=r<1?              //   If we're at the first row:
       M?f^1            //    If we're enciphering: toggle the flag (0→1; 1→0)
       :1               //    If we're deciphering: set the flag to 1
      :r>k-2?           //   Else-if we're at the last row:
       M?f^1            //    If we're enciphering: toggle the flag (0→1; 1→0)
       :0               //    If we're deciphering: set the flag to 0
      :                 //   Else (neither first nor last row):
       f;               //    Leave the flag unchanged regardless of the mode
  for(c=i=0;            //  Reset `c` to 0
            i<k*l;i++)  //  Loop `i` in the range [0, `k*l`):
    if(a[r=i/l][i%l]>0) //   If the current matrix-cell is filled with a character:
      if(M)             //    If we're enciphering:
        System.out.print(a[r][i%l]);}
                        //     Print this character
      else              //    Else (we're deciphering):
        a[r][i]=s[c++]; //     Fill this cell with the current character
  if(!M)                //  If we're deciphering:
    for(r=c=i=0;        //   Reset `r` and `c` both to 0
        i++<l           //   Loop `i` in the range [0, `l`)
        ;               //     After every iteration:
         f=r<1?         //      If we are at the first row:
            1           //       Set the flag to 1
           :r>k-2?      //      Else-if we are at the last row:
            0           //       Set the flag to 0
           :            //      Else:
            f,          //       Leave the flag the same
         r+=f>0?        //      If the flag is now 1:
             1          //       Go one row up
            :           //      Else (flag is 0):
             -1)        //       Go one row down
      if(a[r][c]>1)     //    If the current matrix-cell is filled with a character:
        System.out.print(a[r][c++]);}
                        //     Print this character

```

# Answer
> 0 votes
# MATL, 70 bytes (total)

```
f'(.{'iV'})(.{1,'2GqqV'})'5$h'$1'0'$2'0K$hYX2Get2LZ)P2LZ(!tg)i?&S]1Gw)

```

Try it on MATL Online
Try multiple test cases

Takes a flag as third input, `F` to encipher the string, `T` to decipher it (thanks to Kevin Cruijssen for that idea).

This started as a Julia answer until I realized strict typing got in the way too much, especially for decipherment. Here's the Julia code I had for encipherment (backported to v0.6 for TIO):

### Julia 0.6, 191 bytes

```
!M=(M[2:2:end,:]=flipdim(M[2:2:end,:],2);M)
s|n=replace(String((!permutedims(reshape([rpad(replace(s,Regex("(.{$n})(.{1,$(n-2)})"),s"\1ø\2ø"),length(s)*n,'ø')...],n,:),(2,1)))[:]),"ø","")

```

Try it online!

### Explanation:

The rail fence operation

```
F . . . A . . . Z . . . .
  O . B . R . A . Q . X
    O . . . B . . . U

```

can be seen as reading r = 3 characters of input, then reading r-2 characters and prefixing and suffixing that with dummy values (nulls), then reading r characters again, etc., creating a new column every time:

```
F.A.Z.
OBRAQX
O.B.U.

```

then reversing every second column (since the *zag* part of zigzag goes up instead of down, which makes a difference when r \> 3), then reading this matrix along the rows, and removing the dummy characters.

Decipherment didn't seem to have any obvious patterns like this, but when searching around about this I came across this post, which told me that (a) this was a well known and (possibly?) published algorithm for rail ciphers, and (b) decipherment was a simple reuse of the same method, giving it the indices of the string and getting the *indices of* those indices after encipherment, and reading the ciphertext at those places.

Since decipherment needs to do things by working on indices, this code does encipherment also by sorting the indices of the string, and then in this case just indexing at those rearranged indices.

```
              % implicit first input, say 'FOOBARBAZQUX'
f             % indices of input string (i.e. range 1 to length(input)
'(.{'iV'})(.{1,'2GqqV'})'5$h
              % Take implicit second input, say r = 3
              % Create regular expression '(.{$r})(.{1,$(r-2)})'
              % matches r characters, then 1 to r-2 characters
              %  (to allow for < r-2 characters at end of string)
'$1'0'$2'0K$h % Create replacement expression, '$1\0$2\0'
YX            % Do the regex replacement
2Ge           % reshape the result to have r rows (padding 0s if necessary)
t2LZ)         % extract out the even columns of that
P             % flip them upside down
2LZ(          % assign them back into the matrix
!             % transpose
tg)           % index into the non-zero places (i.e. remove dummy 0s)
i?            % read third input, check if it's true or false
&S]           % if it's true, decipherment needed, so get the indices of the
              %  rearranged indices
1Gw)          % index the input string at those positions

```

---
Tags: code-golf, cryptography, cipher
---


# Question
Title: Remove entries from array to sort it and maximize sum of elements
*This challenge is from an admission test to a closed number cyber security course. Anyway it doesn't have to do with cyber security, it's just to test the students logical and coding skills.*

## Task

Write a program that removes entries from an array so that the remaining values are sorted in a strictly decreasing order and their sum is the maximized among all other possible decreasing sequences.

## Input and Output

**Input** will be an array of integer values **strictly greater** than `0` and all **different from each other**. You are free to choose whether to read input from file, command line or stdin.

**Output** will be a **descending-sorted** subarray of the input one, whose sum is greater than any other possible descending-sorted subarray.

***Note:*** *`[5, 4, 3, 2]` is a subarray of `[5, 4, 1, 3, 2]`, even if `4` and `3` are not adjacent. Just because the `1` was popped.*

## Bruteforce solution

The simplest solution of course would be iterate among all possible combinations of the given array and search for a sorted one with the greatest sum, that would be, in **Python**:

```
import itertools

def best_sum_desc_subarray(ary):
    best_sum_so_far = 0
    best_subarray_so_far = []
    for k in range(1, len(ary)):
        for comb in itertools.combinations(ary, k):
            if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
                best_subarray_so_far = list(comb)
                best_sum_so_far = sum(comb)
    return best_subarray_so_far

```

Unfortunately, since checking if the array is sorted, and calculating the sum of it's elements is and since this operation will be done times for from to , the asymptotic time complexity will be

## Challenge

Your goal is to achieve a better time complexity than the bruteforce above. The solution with the smallest asymptotic time complexity is the winner of the challenge. If two solutions have the same asymptotic time complexity, the winner will be the one with the smallest asymptotic spatial complexity.

***Note:*** *You can consider reading, writing and comparing **atomic** even on large numbers.*

***Note:*** *If there are two or more solutions return either of them.*

## Test cases

```
Input:  [200, 100, 400]
Output: [400]

Input:  [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]

Input:  [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]

Input:  [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]

Input:  [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]

Input:  [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]

Input:  [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]

```

# Answer
> 5 votes
# Haskell, \\$O(n \log n)\\$ time, \\$O(n)\\$ space

```
{-# LANGUAGE MultiParamTypeClasses #-}

import qualified Data.FingerTree as F

data S = S
  { sSum :: Int
  , sArr :: [Int]
  } deriving (Show)

instance Monoid S where
  mempty = S 0 []
  mappend _ s = s

instance F.Measured S S where
  measure = id

bestSubarrays :: [Int] -> F.FingerTree S S
bestSubarrays [] = F.empty
bestSubarrays (x:xs) = left F.>< sNew F.<| right'
  where
    (left, right) = F.split (\s -> sArr s > [x]) (bestSubarrays xs)
    sLeft = F.measure left
    sNew = S (x + sSum sLeft) (x : sArr sLeft)
    right' = F.dropUntil (\s -> sSum s > sSum sNew) right

bestSubarray :: [Int] -> [Int]
bestSubarray = sArr . F.measure . bestSubarrays

```

### How it works

`bestSubarrays xs` is the sequence of subarrays of `xs` that are on the efficient frontier of {largest sum, smallest first element}, ordered from left to right by increasing sum and increasing first element.

To go from `bestSubarrays xs` to `bestSubarrays (x:xs)`, we

1. split the sequence into a left side with first elements less than `x`, and a right side with first elements greater than `x`,
2. find a new subarray by prepending `x` to the rightmost subarray on the left side,
3. drop the prefix of subarrays from the right side with smaller sum than the new subarray,
4. concatenate the left side, the new subarray, and the remainder of the right side.

A finger tree supports all these operations in \\$O(\log n)\\$ time.

# Answer
> 3 votes
# Perl

This should be O(n^2) in time and O(n) in space

Give numbers separated by space on one line to STDIN

```
#!/usr/bin/perl -a
use strict;
use warnings;

# use Data::Dumper;
use constant {
    INFINITY => 9**9**9,
    DEBUG    => 0,
};

# Recover sequence from the 'how' linked list
sub how {
    my @z;
    for (my $h = shift->{how}; $h; $h = $h->[1]) {
        push @z, $h->[0];
    }
    pop @z;
    return join " ", reverse @z;
}

use constant MINIMUM => {
    how  => [-INFINITY, [INFINITY]],
    sum  => -INFINITY,
    next => undef,
};

# Candidates is a linked list of subsequences under consideration
# A given final element will only appear once in the list of candidates
# in combination with the best sum that can be achieved with that final element
# The list of candidates is reverse sorted by final element
my $candidates = {
    # 'how' will represent the sequence that adds up to the given sum as a
    # reversed lisp style list.
    # so e.g. "1, 5, 8" will be represented as [8, [5, [1, INFINITY]]]
    # So the final element will be at the front of 'how'
    how  => [INFINITY],
    # The highest sum that can be reached with any subsequence with the same
    # final element
    sum  => 0,
    # 'next' points to the next candidate
    next => MINIMUM,   # Dummy terminator to simplify program logic
};

for my $num (@F) {
    # Among the candidates on which an extension with $num is valid
    # find the highest sum
    my $max_sum = MINIMUM;
    my $c = \$candidates;
    while ($num < $$c->{how}[0]) {
        if ($$c->{sum} > $max_sum->{sum}) {
            $max_sum = $$c;
            $c = \$$c->{next};
        } else {
            # Remove pointless candidate
            $$c = $$c->{next};
        }
    }

    my $new_sum = $max_sum->{sum} + $num;
    if ($$c->{how}[0] != $num) {
        # Insert a new candidate with a never before seen end element
        # Due to the unique element rule this branch will always be taken
        $$c = { next => $$c };
    } elsif ($new_sum <= $$c->{sum}) {
        # An already known end element but the sum is no improvement
        next;
    }
    $$c->{sum} = $new_sum;
    $$c->{how} = [$num, $max_sum->{how}];
    # print(Dumper($candidates));
    if (DEBUG) {
        print "Adding $num\n";
        for (my $c = $candidates; $c; $c = $c->{next}) {
            printf "sum(%s) = %s\n", how($c), $c->{sum};
        }
        print "------\n";
    }
}

# Find the sequence with the highest sum among the candidates
my $max_sum = MINIMUM;
for (my $c = $candidates; $c; $c = $c->{next}) {
    $max_sum = $c if $c->{sum} > $max_sum->{sum};
}

# And finally print the result
print how($max_sum), "\n";

```

# Answer
> 1 votes
This answer expands on Ton Hospel's one.

The problem can be solved with dynamic programming using the recurence

$$ T(i) = a\_i + \max \left\[ \\{0\\} \cup \\{ T(j) | 0 \leq j \< i \wedge a\_i \leq a\_j \\} \right \] $$

where \\$(a\_i)\\$ is the input sequence and \\$T(i)\\$ the maximally achievable sum of any decreasing sub-sequence ending with index \\$i\\$. The actual solution may then be retraced using \\$T\\$, as in the following rust code.

```
fn solve(arr: &[usize]) -> Vec<usize> {
    let mut tbl = Vec::new();
    // Compute table with maximum sums of any valid sequence ending
    // with a given index i.
    for i in 0..arr.len() {
        let max = (0..i)
            .filter(|&j| arr[j] >= arr[i])
            .map(|j| tbl[j])
            .max()
            .unwrap_or(0);
        tbl.push(max + arr[i]);
    }
    // Reconstruct an optimal sequence.
    let mut sum = tbl.iter().max().unwrap_or(&0).clone();
    let mut limit = 0;
    let mut result = Vec::new();

    for i in (0..arr.len()).rev() {
        if tbl[i] == sum && arr[i] >= limit {
            limit = arr[i];
            sum -= arr[i];
            result.push(arr[i]);
        }
    }
    assert_eq!(sum, 0);
    result.reverse();
    result
}

fn read_input() -> Vec<usize> {
    use std::io::{Read, stdin};
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    s.split(|c: char| !c.is_numeric())
        .filter(|&s| !s.is_empty())
        .map(|s| s.parse().unwrap())
        .collect()
}

fn main() {
    println!("{:?}", solve(&read_input()));
}

```

Try it online!

---
Tags: array, subsequence, fastest-algorithm
---