Generate the Abacaba sequence

Question

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
a(3) = abacabaDabacaba
a(4) = abacabadabacabaEabacabadabacaba
...
a(25) = abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaiabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabajabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaia...

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.

@nicael I know, I was just wondering how 𝑎(∞) would be defined. — LegionMammal978, Jan 9, 2016 at 13:29
Also known as the ruler sequence (but with letters instead of numbers), for something more easily Google-able. — user253751, 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. — Jeff Zeitlin, Apr 2, 2019 at 11:59

JamesENL · Accepted Answer · 2016-03-11 05:18:17Z

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;
            string = addLetter(string, count, f);
        }
        return string;
    }
}

Pretty straightforward brute force recursive algorithm, uses char manipulation.

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 31, 2016 at 13:25

Jonathan Leech-Pepin

2731 silver badge6 bronze badges

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

Add a comment |

Giuseppe · Accepted Answer · 2019-04-01 20:39:23Z

1

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

answered Apr 1, 2019 at 20:39

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

Add a comment |

mazzy · Accepted Answer · 2019-04-02 09:07:42Z

1

PowerShell, 54 bytes

param($n)for(;$n+1){$d+=[char]($i+++97-32*!$n--)+$d}$d

Try it online!

edited Apr 2, 2019 at 9:07

answered Apr 2, 2019 at 8:03

mazzy

7,0752 gold badges10 silver badges22 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 1, 2019 at 21:20

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 25, 2019 at 7:38

user58988

1

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

Add a comment |

ngn · Accepted Answer · 2019-06-25 09:02:51Z

1

APL (Dyalog Classic), 20 19 17 bytes

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

Try it online!

yet another apl answer

edited Jun 25, 2019 at 9:02

answered Jun 25, 2019 at 8:55

ngn

15.2k2 gold badges42 silver badges87 bronze badges

Add a comment |

Shieru Asakoto · Accepted Answer · 2019-06-25 14:23:51Z

1

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!

edited Jun 25, 2019 at 14:23

answered Jun 25, 2019 at 10:55

Shieru Asakoto

6,17814 silver badges40 bronze badges

Add a comment |

negative seven · Accepted Answer · 2019-06-27 12:59:49Z

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)

Dorian · Accepted Answer · 2019-09-30 07:41:59Z

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

Mahmoud Sagr · Accepted Answer · 2019-09-30 13:59:31Z

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!

edited Sep 30, 2019 at 13:59

answered Sep 22, 2019 at 14:06

Mahmoud Sagr

113 bronze badges

Add a comment |

scrawl · Accepted Answer · 2019-09-30 17:23:42Z

1

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")

answered Sep 30, 2019 at 17:23

scrawl

1,3195 silver badges12 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2021-09-04 00:54:02Z

1

Vyxal `s`, 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

answered Sep 4, 2021 at 0:54

emanresu A

35.6k5 gold badges83 silver badges200 bronze badges

Add a comment |

DLosc · Accepted Answer · 2021-09-04 02:05:30Z

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

Jakque · Accepted Answer · 2021-09-05 10:41:34Z

1

Python 3.8 (pre-release), 43 bytes

a=lambda n:'a'[n:]or(b:=a(n-1))+chr(97+n)+b

Try it online!

answered Sep 5, 2021 at 10:41

Jakque

2,6385 silver badges12 bronze badges

Add a comment |

chunes · Accepted Answer · 2023-06-27 04:51:05Z

1

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

edited Jun 27 at 4:51

answered Jun 27 at 4:41

chunes

22.8k3 gold badges21 silver badges51 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2023-06-27 10:08:19Z

1

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)

answered Jun 27 at 10:08

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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);

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 9, 2016 at 15:43

flawr

43.7k7 gold badges102 silver badges247 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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,
     (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)

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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("", ^)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 9, 2016 at 17:10

Blue

28.5k8 gold badges50 silver badges99 bronze badges

Add a comment |

dzaima · Accepted Answer · 2019-04-01 20:29:55Z

0

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)

answered Apr 1, 2019 at 20:29

dzaima

20.2k2 gold badges40 silver badges75 bronze badges

Add a comment |

Jo King · Accepted Answer · 2019-04-02 03:07:36Z

0

Perl 6, 35 bytes

{('a',{$_~chr(++$+97)~$_}...*)[$_]}

Try it online!

answered Apr 2, 2019 at 3:07

Jo King♦

47.1k5 gold badges124 silver badges184 bronze badges

Add a comment |

Nick Kennedy · Accepted Answer · 2019-04-02 22:16:51Z

0

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.

answered Apr 2, 2019 at 22:16

Nick Kennedy

19.1k3 gold badges16 silver badges40 bronze badges

Add a comment |

user87487user87487 · Accepted Answer · 2019-06-25 04:30:15Z

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, 2019 at 4:36

NikoNyrh · Accepted Answer · 2019-06-25 14:08:43Z

0

Clojure, 63 bytes

#(loop[r""i 0](if(= i %)r(recur(str r(char(+ i 97))r)(inc i))))

answered Jun 25, 2019 at 14:08

NikoNyrh

2,6319 silver badges8 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 28, 2019 at 12:42

zmerch

6413 silver badges5 bronze badges

Add a comment |

recursive · Accepted Answer · 2019-09-30 17:44:02Z

0

Stax, 7 bytes

ö▬⌐ç╗à╢

Run and debug it

This uses 1-based indexing.

0-based indexing costs another byte

answered Sep 30, 2019 at 17:44

recursive

10.4k19 silver badges36 bronze badges

Add a comment |

57 Answers 57

Java, 219 bytes

Powershell, 53,46,44,41 Bytes

Gaia, 14 bytes

PowerShell, 54 bytes

Japt, 8 bytes

APL(NARS), 24 chars, 48 bytes

APL (Dyalog Classic), 20 19 17 bytes

PHP -r, 43 bytes

PHP, 51 bytes

Befunge-93, 41 bytes

Explanation

05AB1E (legacy), 9 bytes

Lua, 69 bytes

C++ (gcc), 58 53 bytes

k4, 23 bytes

Vyxal s, 11 bytes

Pip, 14 bytes

Explanation

Python 3.8 (pre-release), 43 bytes

Arturo, 48 bytes

Rockstar, 80 bytes

Matlab, 54 bytes

J, 30 28 bytes (Try it online!)

Pyke, 11 bytes (noncompeting)

Canvas, 8 bytes

Perl 6, 35 bytes

Jelly, 9 bytes

JavaScript, 169 bytes

Live demo:

Explanation:

Clojure, 63 bytes

Mumps (InterSystems), 46 bytes

Stax, 7 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfstringsequence or ask your own question.

Linked

Related

PHP `-r`, 43 bytes

Vyxal `s`, 11 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
string
sequence
or ask your own question.