35
\$\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\$
  • 3
    \$\begingroup\$ Wouldn't the sequence be undefined after 𝑎₂₅? \$\endgroup\$ – LegionMammal978 Jan 9 '16 at 13:04
  • 3
    \$\begingroup\$ @nicael I know, I was just wondering how 𝑎(∞) would be defined. \$\endgroup\$ – LegionMammal978 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\$ – Jeff Zeitlin Apr 2 '19 at 11:59
  • 3
    \$\begingroup\$ Can we use 1-based indexing instead of 0-based indexing? \$\endgroup\$ – Esolanging Fruit Apr 3 '19 at 17:21

45 Answers 45

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\$
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\$
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\$
  • \$\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\$ – Shieru Asakoto Jun 29 '19 at 4:36
0
\$\begingroup\$

APL (Dyalog Classic), 20 19 17 bytes

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

Try it online!

yet another apl answer

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

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.