# Generate the Abacaba sequence

This challenge is about printing the abacaba sequence of a specific depth.

Here is a diagram of the first 5 sequences (a(N) is the abacaba sequence of depth N, upper/lowercase is just to show the pattern, this is not needed in the output of your program):

a(0) = A
a(1) = aBa
a(2) = abaCaba
...


As you can probably tell, the n'th abacaba sequence is the last one with the n'th letter and itself again added to it. (a(n) = a(n - 1) + letter(n) + a(n - 1))

Your task is to make a program or function that takes an integer and prints the abacaba sequence of that depth. The output has to be correct at least for values up to and including 15.

• Wouldn't the sequence be undefined after 𝑎₂₅? – LegionMammal978 Jan 9 '16 at 13:04
• @nicael I know, I was just wondering how 𝑎(∞) would be defined. – LegionMammal978 Jan 9 '16 at 13:29
• Also known as the ruler sequence (but with letters instead of numbers), for something more easily Google-able. – user253751 Jan 10 '16 at 6:00
• For what it's worth, any valid solution to this problem is also the solution to the Towers of Hanoi puzzle for N disks. – Jeff Zeitlin Apr 2 '19 at 11:59
• Can we use 1-based indexing instead of 0-based indexing? – Esolanging Fruit Apr 3 '19 at 17:21

# Befunge-93, 41 bytes

1-011v $< v::+&_:#^!_:1+v >:0\:^,+""$%:<


Try it online!

Probably some room for improvement here.

### Explanation

The sequence is generated using its recursive definition. First, we initialize the stack with the 4 values (1, input+2), (0, -1). Each pair (a, b) on the stack is an "instruction" used in generating the sequence, which, when executed, gets popped and does the following:

• if a == 0:
• if b == -1, terminate
• if b == 0, do nothing
• if b != -1 and b != 0, print b+96 as an ASCII character
• if a != 0, push (b-1, b-1), (0, b-1), (b-1, b-1)

The top two items on the stack are continuously run as a sequence-building instruction until the program terminates.

Worth noting that &+ is used the first time around to get the input, as well as every subsequent time as a decrement (because when there is no more input, & returns -1)

# Lua, 69 bytes

f=function(n)return n<1 and"a"or f(n-1)..string.char(97+n)..f(n-1)end


Try it online!

# C++ (gcc), 58 53 bytes

string f(int n){return n--?f(n)+char(98+n)+f(n):"a";}


- 5 bytes saved by ceilingcat

Try it online!

# k4, 23 bytes

{.Q.a x{x,(1+|/x),x}/0}


      x{           }/0  / do {func} x times, passing output of last iteration as input (first input is 0)
(1+|\x)       / 1 + max x
x,       ,x     / join x either side
.Q.a                   / index into alphabet


executed with inputs [0,4) we get:

  {.Q.a x{x,(1+|/x),x}/0}'[0 1 2 3]


# Matlab, 54 bytes

Just a straight forward recursive implementation.

function s=f(n);s='';if n>-1;k=f(n-1);s=[k,n+97,k];end


I first thought I could do better by using anonymous functions, but it turned out to be way longer, but I thougt I still share it:

i=@(b,c)c{2-b}();
a=@(n,f)i(n<0,{@()'',@()[f(n-1,f)),n+97,f(n-1,f)]});
ba=@(n)a(n,a);


# J, 30 28 bytes (Try it online!)

I just found out that a(0) = "a", which chopped of 2 bytes.

u:97+(0:($:@<:,],$:@<:)@.*)


Usage:

   u:97+(0:($:@<:,],$:@<:)@.*) 2
abacaba


How it works:

u:97+(0:($:@<:,],$:@<:)@.*) n NB. pseudocode:
NB. input as n
NB. function as generate_tree
u:                             NB.   convert_to_ASCII(
(xxyyyyyyyyyyyyyyy@.z)   NB.       if z then y or x:
*    NB.         z: n>0?
0:                       NB.         x: 0
($:@<:,],$:@<:)       NB.         y:
ppppp,q,rrrrr        NB.           concat(p,q,r):
$:@<: NB. p:$:@                  NB.               generate_tree(
<:                NB.                 n-1)
]              NB.             q: n
$:@<: NB. r: generate_tree(n-1)  ## Pyke, 11 bytes (noncompeting) G@QVk?tQG@:  Try it here! G@ - s = alphabet[input] QV - repeat input times: ?tQ - input -= 1 G@ - alphabet[^] k : - s = s.replace("", ^)  # Canvas, 8 bytes ø⁸╵ｚｍ｛＋│  Try it here! 7 bytes taking the index starting with 1, or hacky 6 bytes by taking input "with a trailing newline" (which together can sum up to 5 bytes) # Perl 6, 35 bytes {('a',{$_~chr(++$+97)~$_}...*)[$_]}  Try it online! # Jelly, 9 bytes ‘R;ṭ¥/ịØa  Try it online! It would be 8 were it not for the requirement for the sequence to start with zero = a. # JavaScript, 169 bytes x=function(n){var r="";for(var i=1;i<=Math.pow(2,n)-1;i++){for(var j=i;j>=0;j--){if(!(i%Math.pow(2,j))){r+="ABCDEFGHIJKLMNOPQRSTUVWXYZ".slice(0,n)[j];break;}}}return r;}  ### Try it online! ### Live demo: x=function(n){var r="";for(var i=1;i<=Math.pow(2,n)-1;i++){for(var j=i;j>=0;j--){if(!(i%Math.pow(2,j))){r+="ABCDEFGHIJKLMNOPQRSTUVWXYZ".slice(0,n)[j];break;}}}return r;} console.log(x(prompt("Input depth of ABACABA Pattern"))) ### Explanation: x = function(n){ // created function, and yes, I omitted var var r = ""; // declaring variable to be returned for (var i = 1; i <= Math.pow(2, n) - 1; i++){ // this loop creates each letter in the pattern; "Math.pow(2, n) - 1" is the length of the pattern at depth n for (var j = i; j >= 0; j--){ // this loop finds the greatest power of 2 that i is divisible by, since that can be used to find the correct character for that index if (! (i % Math.pow(2, j) ) ){ // the modulo part checks the divisibility of 2^j; the "!" replaces "=== 0" r += "ABCDEFGHIJKLMNOPQRSTUVWXYZ".slice(0,n)[j]; // appending character to r break; // exits loop once greatest power of 2 i is divisible by is found } } } return r; }  • The x= can be omitted if you do not refer to it anywhere else, and also I think "ABCDEFGHIJKLMNOPQRSTUVWXYZ".slice(0,n)[j] can be (j+10).toString(36) because (1) .slice(0,n) is not necessary here, and (2) (j+10).toString(36) returns j+10 in base 36, which should be equivalent to your code. – Shieru Asakoto Jun 29 '19 at 4:36 # APL (Dyalog Classic), 20 19 17 bytes ⎕a[¯1↓⊥¨⍨,⍳2,⎕⍴2]  Try it online! yet another apl answer ## Clojure, 63 bytes #(loop[r""i 0](if(= i %)r(recur(str r(char(+ i 97))r)(inc i))))  ## Mumps (InterSystems), 46 bytes S Q="",A=65 R N F I=0:1:N{S Q=Q_$C(A+I)_Q} W Q


InterSystems' version of Mumps (some say M, InterSystems likes to call it "Cache Object Script") allows delineating loops with braces which helps keep things on a single line; GT.M would be a few characters longer.

# 05AB1E (legacy), 9 bytes

AćsI£vDyý


Try it online!

Also runs with the new 05AB1E version.

code:

A       push the lowercase alphabet
ć       extract first character of that ["bcdefg....", "a"]
s       swap both strings ["a", "bcdefg...."]
I£      drop all letters of the alphabet after the index defined by input
v       for each character
D     duplicate last stack entry
yý    join by current letter
implicitly close for-loop and print top of stack


# Stax, 7 bytes

ö▬⌐ç╗à╢
`

Run and debug it

This uses 1-based indexing.

0-based indexing costs another byte