Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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(∞) = 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.

share|improve this question
2  
Wouldn't the sequence be undefined after 𝑎₂₅? – LegionMammal978 Jan 9 at 13:04
    
@Legion OP's mentioned that "The output has to be correct at least for values up to and including 15", so it doesn't matter. – nicael Jan 9 at 13:26
3  
@nicael I know, I was just wondering how 𝑎(∞) would be defined. – LegionMammal978 Jan 9 at 13:29
2  
Also known as the ruler sequence (but with letters instead of numbers), for something more easily Google-able. – immibis Jan 10 at 6:00
1  
@CatsAreFluffy Because this is how the famous sequence is defined. – mbomb007 Mar 10 at 21:47

23 Answers 23

up vote 8 down vote accepted

Pyth, 11 bytes

u++GHG<GhQk

Simple reduction.

share|improve this answer
2  
@Loovjo Oh. Makes no sense, 0 should be the empty sequence IMO, but I'll conform to the question... – orlp Jan 9 at 12:52
1  
Yeah, simple. goes and bangs head on wall – J Atkin Feb 13 at 20:07
    
@JAtkin Open up Pyth's rev-doc.txt next to this answer, and it should readily show itself to be simple. – orlp Feb 13 at 20:19
    
Hehehe, not what I meant (I don't know pyth, so....) – J Atkin Feb 13 at 20:22

Python, 44 bytes

f=lambda n:"a"[n:]or f(n-1)+chr(97+n)+f(n-1)

Looks suspiciously might-be-golfable.

share|improve this answer

Pyth, 14 13 bytes

Thanks to Jakube for saving a byte!

VhQ=+k+@GNk;k

A solution with 14 bytes: VhQ=ks[k@GNk;k.

Explanation:

VhQ=+k+@GNk;k

               # Implicit: k = empty string
VhQ            # For N in range input + 1      
   =           # Assign k
      +@GNk    # Position N at alphabet + k
    +k         # k + above
           ;   # End loop
            k  # Print k

Try it here!

share|improve this answer
    
Shouldn't "N in range" be on the V line? hQ is just eval(input) + 1 – Loovjo Jan 9 at 12:58
    
@Loovjo Yeah, that's better and less confusing :) – Adnan Jan 9 at 13:00
    
You can shorten =k to =. Pyth will automatically assign the result to k, since k is the first variable in the expression +k+@GNk. – Jakube Jan 9 at 14:00
    
@Jakube Thank you very much! :) – Adnan Jan 9 at 14:10
    
I have a different answer for this challenge. It won't beat this solution, but it does illustrate a technique for giving the first n characters of the sequence: Vt^2Q=+k@Gx_.BhN`1)k (In this instance, it's set to give the first 2^Q-1 characters as the challenge requires, but you can see how to change that.) – quintopia Jan 9 at 22:12

Retina, 37 32 bytes

$
aa
(T`_l`l`.$
)`1(a.*)
$1$1
z

The trailing linefeed is significant. Input is taken in unary.

Try it online!

share|improve this answer
    
It does not work. – Leaky Nun Mar 31 at 4:47
    
@KennyLau yes, because Retina changed since I posted this answer. If you check out the release that was most recent when this was posted directly from GitHub, it will work with that. – Martin Büttner Mar 31 at 5:25
    
Alright........ – Leaky Nun Mar 31 at 5:25

CJam (14 bytes)

'aqi{'b+1$++}/

Online demo

share|improve this answer

05AB1E, 12 bytes (non-competitive)

Code:

'aIGDN>.bsJl

I'll be damned. I fixed a lot of bugs thanks to this challenge haha.

Explanation:

'aIGDN>.bsJl

'a             # Push the character 'a'
  I            # User input
   G           # For N in range(1, input)
    D          # Duplicate the stack
     N         # Push N
      >        # Increment
       .b      # Convert to alphabetic character (1 = A, 2 = B, etc.)
         s     # Swap the last two elements
          J    # push ''.join(stack)
           l   # Convert to lowercase
               # Implicit: print the last item of the stack
share|improve this answer
    
Why is it non-competitive? – Loovjo Jan 9 at 13:31
    
@Loovjo I fixed the bugs after the challenge was posted, therefore it's non-competitive :( – Adnan Jan 9 at 13:32

JavaScript (ES6), 43 42 bytes

a=n=>n?a(--n)+(n+11).toString(36)+a(n):"a"

A byte saved thanks to @Neil!

Yet another simple recursive solution...

share|improve this answer
    
(n+11).toString(36) saves you 1 byte, and works for up to a(25)! – Neil Jan 9 at 18:08
    
@Neil Implemented. Thanks! – user81655 Jan 10 at 2:24

Ruby (1.9 and up), 38 bytes

?a is a golfier way to write "a" but looks weird when mixed with ternary ?:

a=->n{n<1??a:a[n-1]+(97+n).chr+a[n-1]}
share|improve this answer

C#, 59 bytes

string a(int n){return n<1?"a":a(n-1)+(char)(97+n)+a(n-1);}

Just another C# solution...

share|improve this answer

Haskell, 39 bytes

a 0="a"
a n=a(n-1)++toEnum(97+n):a(n-1)

Usage example: a 3 -> "abacabadabacaba".

share|improve this answer
    
Wouldn't a n=a(n-1)++[97+n]++a(n-1) work? Can't test right now. – Seeq Jan 9 at 18:36
    
@Seeq: no, [97+n] is a list of Integer and a(n-1) is a list of Char (aka String). You cannot concatenate lists with different types. toEnum makes a Char out of the Integer. – nimi Jan 9 at 18:57
    
Ah, I always thought Char was just a specialized integer in Haskell. – Seeq Jan 9 at 23:47

Python 3, 62 54 46 45 bytes

I would like to think that this code can still be golfed down somehow.

a=lambda n:["a",a(n-1)+chr(97+n)+a(n-1)][n>0]
share|improve this answer
    
Output should be in all-lowercase. The uppercase in the question is just for clarity about the repetition. – Loovjo Jan 9 at 12:56
    
Whoops. Thanks for the clarification. – Sherlock9 Jan 9 at 12:58
    
Blargle. Thanks @user81655 – Sherlock9 Jan 9 at 13:20

Java 7, 158 bytes

class B{public static void main(String[]a){a('a',Byte.valueOf(a[0]));}static void a(char a,int c){if(c>=0){a(a,c-1);System.out.print((char)(a+c));a(a,c-1);}}}

I like to lurk around PPCG and I would enjoy being able to vote/comment on other answers.

Input is given as program parameters. This follows the same format as many other answers here in that it's a straight forward recursive implementation. I would have commented on the other answer but I don't have the rep to comment yet. It's also slightly different in that the recursive call is done twice rather than building a string and passing it along.

share|improve this answer
    
Welcome to PPCG then! I hope you'll do some more than voting and commenting in the future (but don't feel like you have to). :) – Martin Büttner Apr 11 at 19:47

Mathematica, 46 bytes

If[#<1,"a",(a=#0[#-1])<>Alphabet[][[#+1]]<>a]&

Simple recursive function. Another solution:

a@0="a";a@n_:=(b=a[n-1])<>Alphabet[][[n+1]]<>b
share|improve this answer

Perl, 33 bytes

map$\.=chr(97+$_).$\,0..pop;print

No real need for un-golfing. Builds the string up by iteratively appending the next character in sequence plus the reverse of the string so far, using the ASCII value of 'a' as its starting point. Uses $\ to save a few strokes, but that's about as tricky as it gets.

Works for a(0) through a(25) and even beyond. Although you get into extended ASCII after a(29), you'll run out of memory long before you run out of character codes:

a(25) is ~64MiB. a(29) is ~1GiB.

To store the result of a(255) (untested!), one would need 2^256 - 1 = 1.15x10^77 bytes, or roughly 1.15x10^65 1-terabyte drives.

share|improve this answer
    
We need those atom-shudder yottabyte drives, now! – CalculatorFeline Mar 10 at 20:10

Japt, 20 17 bytes

97oU+98 r@X+Yd +X

Test it online!

How it works

         // Implicit: U = input integer
65oU+66  // Generate a range from 65 to U+66.
r@       // Reduce each item Y and previous value X in this range with this function:
X+Yd     // return X, plus the character with char code Y,
+X       // plus X.

         // Implicit: output last expression

Non-competing version, 14 bytes

97ôU r@X+Yd +X

The ô function is like o, but creates the range [X..X+Y] instead of [X..Y). Test it online!

I much prefer changing the 97 to 94, in which case the output for 5 looks like so:

^_^`^_^a^_^`^_^b^_^`^_^a^_^`^_^c^_^`^_^a^_^`^_^b^_^`^_^a^_^`^_^
share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
@TimmyD Actually gets it down to 41 since I won't need the (,). – Jonathan Leech-Pepin Apr 6 at 16:31
    
No, that was my fault, I actually forgot to update it even though I said I did. – Jonathan Leech-Pepin Apr 6 at 19:42

K5, 18 bytes

"A"{x,y,x}/`c$66+!

Repeatedly apply a function to a carried value ("A") and each element of a sequence. The sequence is the alphabetic characters from B up to some number N (`c$66+!). The function joins the left argument on either side of the right argument ({x,y,x}).

In action:

 ("A"{x,y,x}/`c$66+!)'!6
("A"
 "ABA"
 "ABACABA"
 "ABACABADABACABA"
 "ABACABADABACABAEABACABADABACABA"
 "ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA")
share|improve this answer
    
I think the sequence should be lowercase, but that costs no bytes. – zyabin101 Jan 9 at 18:05

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);
share|improve this answer

JavaScript, 65 571 bytes

n=>eval('s="a";for(i=0;i<n;i++)s+=(i+11).toString(36)+s')

Demo:

function a(n){
  return eval('s="a";for(i=0;i<n;i++)s+=(i+11).toString(36)+s')
}
alert(a(3))

1 - thanks Neil for saving 8 bytes

share|improve this answer
    
(i+11).toString(36) saves you 6 bytes. – Neil Jan 9 at 18:14
    
@Neil Haha, that's a clever hack – nicael Jan 9 at 18:16
    
Oh, and if you move the assignment s="a"; to before the for then it becomes the default return value and you can drop the trailing ;s for another 2 byte saving. – Neil Jan 9 at 18:18
    
@Neil Nice, didn't know about that. – nicael Jan 9 at 18:19
    
I think you can save a byte by incrementing i inline and dropping the increment in the for loop. So... for(i=0;i<n;)s+=(i+++11)... – Not that Charles Mar 11 at 4:46

Mathematica, 36 bytes

Fold[##<>#&,"",Alphabet[][[;;#+1]]]&

No numbers cuz those suck

share|improve this answer

MATL, 14 bytes

0i:"t@whh]97+c

This uses version 8.0.0 of the language/compiler, which is earlier than the challenge.

Example

>> matl
 > 0i:"t@whh]97+c
 >
> 3
abacabadabacaba

Explanation

The secuence is created first with numbers 0, 1, 2, ... These are converted to letters 'a', 'b', 'c' at the end.

0         % initiallize: a(0)
i:        % input "N" and create vector [1, 2, ... N]
"         % for each element of that vector
  t       % duplicate current sequence
  @       % push new value of the sequence
  whh     % build new sequence from two copies of old sequence and new value
]         % end for
97+c      % convert 0, 1, 2, ... to 'a', 'b', 'c'. Implicitly print

Edit

Try it online!

share|improve this answer

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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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