38
\$\begingroup\$

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.

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

51 Answers 51

1
2
1
\$\begingroup\$

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"!!)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Doesn’t APL use it’s own code page with every character one byte, making this 24 bytes? \$\endgroup\$
    – Loovjo
    Jun 25 '19 at 7:40
  • \$\begingroup\$ @Loovjo for what I know Nars Apl has character set 2 bytes for character \$\endgroup\$
    – user58988
    Jun 25 '19 at 7:43
1
\$\begingroup\$

APL (Dyalog Classic), 20 19 17 bytes

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

Try it online!

yet another apl answer

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
1
\$\begingroup\$

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")
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 43 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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);
\$\endgroup\$
0
\$\begingroup\$

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`yyyyyyyyyyyyyyy@.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)
\$\endgroup\$
0
\$\begingroup\$

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("", ^)
\$\endgroup\$
0
\$\begingroup\$

Canvas, 8 bytes

ø⁸╵zm{+│

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)

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 35 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 29 '19 at 4:36
0
\$\begingroup\$

Clojure, 63 bytes

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

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Stax, 7 bytes

ö▬⌐ç╗à╢

Run and debug it

This uses 1-based indexing.

0-based indexing costs another byte

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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