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

## Java, 219 bytes

My first code golf attempt. Probably can be golf'd further, but I'm hungry and going out to lunch.

public class a{public static void main(String[]a){String b=j("a",Integer.parseInt(a[0]),1);System.out.println(b);}public static String j(String c,int d,int e){if(d>=e){c+=(char)(97+e)+c;int f=e+1;c=j(c,d,f);}return c;}}


Ungolfed:

public class a {
public static void main(String[] a) {
String string = addLetter("a", Integer.parseInt(a[0]), 1);
System.out.println(string);
}

public static String addLetter(String string, int count, int counter) {
if (count >= counter) {
string += (char) (97 + counter) + string;
int f = counter + 1;
}
return string;
}
}


Pretty straightforward brute force recursive algorithm, uses char manipulation.

• You can omit the public keyword from a and addLetter/j. Jun 9, 2016 at 21:51

# Powershell, 53,46,44,41 Bytes

1..$args[0]|%{}{$d+=[char]($_+96)+$d}{$d}  Pasting into console will generate erronous output on the second run since $d is not re-initialized.

Save 2 bytes by using += Save 3 bytes thanks to @TimmyD

• @TimmyD Actually gets it down to 41 since I won't need the (,). Apr 6, 2016 at 16:31
• No, that was my fault, I actually forgot to update it even though I said I did. Apr 6, 2016 at 19:42
• the script does not wirk with 0 and does not generate a uppercase letter Apr 2, 2019 at 8:02

# Gaia, 14 bytes

₵aØ@⟪¤ṇ3ṁ¤+ṫ⟫ₓ


Try it online!

₵a		| Push lowercase alphabet
Ø		| push lowercase string
@         ₓ	| push the input and do everything between ⟪⟫ that many times
⟪¤		| swap
ṇ		| take the last (first) character
3ṁ	| push the 3rd item on the stack
¤+	| swap and concatenate
ṫ⟫	| and palindromize

param($n)for(;$n+1){$d+=[char]($i+++97-32*!$n--)+$d}$d  Try it online! # Japt, 8 bytes ;gCåÈ+iY  Try it ;gCåÈ+iY :Implicit input of integer g :Index into ; C : Lowercase alphabet å : Cumulatively reduce, with an initial value of an empty string + : Append a copy of the current value i : Prepended with Y : The current letter  # 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 ABACABADABACABA f 4 ABACABADABACABAEABACABADABACABA  • Doesn’t APL use it’s own code page with every character one byte, making this 24 bytes? Jun 25, 2019 at 7:40 • @Loovjo for what I know Nars Apl has character set 2 bytes for character – user58988 Jun 25, 2019 at 7:43 # APL (Dyalog Classic), 20 19 17 bytes ⎕a[¯1↓⊥¨⍨,⍳2,⎕⍴2]  Try it online! yet another apl answer # 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)

# 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


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


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

# Arturo, 48 bytes

f:$->x[(0=x)?->"a"->++++f x-1to :char x+97f x-1]  Try it! f:$->x[               ; a function named f taking an argument x
(0=x)?            ; is x zero?
->"a"             ; then return "a"
->                ; otherwise,
++++          ; append three things together
f x-1         ; f(x-1)
to :char x+97 ; x converted to character
f x-1         ; f(x-1)
]                     ; end function


# Rockstar, 80 bytes

1-indexed

listen to N
X's 0
O's ""
while N-X
cast X+97 in C
let O be+C+O
let X be+1

say O


Try it (Code will need to be pasted in)

# 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(
(xx[email protected])   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. Jun 29, 2019 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.

# Stax, 7 bytes

ö▬⌐ç╗à╢
`

Run and debug it

This uses 1-based indexing.

0-based indexing costs another byte