# 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 𝑎₂₅? Jan 9 '16 at 13:04
• @nicael I know, I was just wondering how 𝑎(∞) would be defined. Jan 9 '16 at 13:29
• Also known as the ruler sequence (but with letters instead of numbers), for something more easily Google-able. 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. Apr 2 '19 at 11:59
• Can we use 1-based indexing instead of 0-based indexing? Apr 3 '19 at 17:21

# Husk, 12 bytes

!¡S+oṠ:o→▲"a


Try it online!

Uses 1-based indexing, which I hope is OK.

## Explanation

!             (                                          !!)
¡             iterate(                              )
S                        <*>
+                   (++)
o                         (                     )
Ṡ                         join$. : (:) o . → succ ▲ maximum "a "a" (iterate((++)<*>(join$(:).succ.maximum))"a"!!)


# APL(NARS), 24 chars, 48 bytes

{⍵<0:⍬⋄k,⎕A[⍵+1],k←∇⍵-1}


test:

  f←{⍵<0:⍬⋄k,⎕A[⍵+1],k←∇⍵-1}
f 0
A
f 1
ABA
f 2
ABACABA
f 3
f 4

• Doesn’t APL use it’s own code page with every character one byte, making this 24 bytes? Jun 25 '19 at 7:40
• @Loovjo for what I know Nars Apl has character set 2 bytes for character
– user58988
Jun 25 '19 at 7:43

# APL (Dyalog Classic), 20 19 17 bytes

⎕a[¯1↓⊥¨⍨,⍳2,⎕⍴2]


Try it online!

# PHP-r, 43 bytes

register_argc_argv must be enabled for this to work.

for($a=$b=a;$argv[1]--;$a.=++$b.$a);echo$a;  Try it online! # PHP, 51 bytes An anonymous function that prints the output directly. function($n){for($a=$b=a;$n--;$a.=++$b.$a);echo$a;}  Try it online! # 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] ("a";"aba";"abacaba";"abacabadabacaba")  # Vyxals, 11 bytes Eɽƛǐ2O;97+C  Try it Online! Eɽ # 0...2**n ƛ ; # Mapped to... ǐ2O # Count of 2 in prime factorisation 97+C # Add 97 and get charcodes  # Pip, 14 bytes a?z@aWRREa-1'a  Takes the integer as a command-line argument. Try it here! Or, here's a 15-byte equivalent in Pip Classic: Try it online! ### Explanation A recursive full program. a? ; Is the argument truthy (non-zero)? ; If so: z@a ; Get the letter of the lowercase alphabet at index a WR ; and wrap it in two copies of RE ; the result of a recursive call a-1 ; with argument a-1 ; Otherwise: 'a ; Return the letter a  # Python 3.8 (pre-release), 43 bytes a=lambda n:'a'[n:]or(b:=a(n-1))+chr(97+n)+b  Try it online! # 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( 97+ NB. add_to_all(97, (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;}


### 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. Jun 29 '19 at 4:36

## 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