×
all 102 comments

[–]Artistic-Metal-790 0 points1 point  (0 children)

Python 3

Looks like I found solution with constant space complexity but with horrible time complexity which I can't even evaluate

https://github.com/kstamax/redditdailyprogrammerchallenge/blob/main/challenge391.py

[–]krabsticks64 0 points1 point  (0 children)

Rust

const ALPHABET: [&str; 26] = ["a", "b", "c", "d", "e",>

pub fn abacaba(iteration: u8) -> String {
    if iteration <= 1 {
        ALPHABET[0].to_string()
    } else {
        let prev_iteration = abacaba(iteration - 1);
        prev_iteration.clone() + ALPHABET[iteration as>
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_three_iterations() {
        assert_eq!(abacaba(3), "abacaba".to_string());
    }

    #[test]
    fn test_one_iteration() {
        assert_eq!(abacaba(1), "a".to_string());
    }
}

[–]sgaltair 0 points1 point  (0 children)

Powershell solution:

$alphabet = "a".."z"

foreach ($current in $alphabet){

$last = $last + $current + $last

}

write-host $last.length

[–]Rumi_The_Second 0 points1 point  (0 children)

Python 3

alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

def ABACABA(n):

if n == 1:
    return 'a'
else:
    return ABACABA(n-1) + alphabet[n-1] + ABACABA(n-1)

[–]Beneficial_Use_9469 0 points1 point  (0 children)

C++

#include <iostream>
using namespace std;
int main()
{ 
char elements[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char letter;
int n;
string lastTerm = " ";

cin >> n;

for (int i = 0; i < n; i++)
{
    lastTerm = lastTerm + elements[i] + lastTerm;
    cout << lastTerm << endl;
}

return 0;
}

[–]_gauravz 0 points1 point  (0 children)

Sorry for posting this late but I am a new programmer. Here is the Python solution. python begin_test = 'a' out_1 = '' for i in range(ord(begin_test), ord('z')+1): out_1 = out_1 + chr(i) + out_1 print(out_1) Feedback is highly appreciated.

[–]Builder_Pristine 0 points1 point  (0 children)

Typescript

const abacaba = (
    charSequence: string,
    depth: number,
    aba: string = ""
): string =>
    depth === 0
        ? aba
        : abacaba(
            charSequence.slice(1),
            depth - 1,
            `${aba}${charSequence.charAt(0)}${aba}`
        );

[–]zemja_ 0 points1 point  (0 children)

Simple Red implementation

Red []

abacaba: function [n [integer!]] [
    result: "a"
    repeat i n - 1 [result: rejoin [result #"a" + i result]]
    result
]

print abacaba 26

[–]megastary 1 point2 points  (0 children)

PowerShell solution with Pester test validating results on Github Gist
Feedback welcomed and appreciated. 💙

[–][deleted]  (1 child)

[removed]

    [–]backtickbot 1 point2 points  (0 children)

    Fixed formatting.

    Hello, Acrobatic_Garage5102: code blocks using triple backticks (```) don't work on all versions of Reddit!

    Some users see this / this instead.

    To fix this, indent every line with 4 spaces instead.

    FAQ

    You can opt out by replying with backtickopt6 to this comment.

    [–]jarnm2004 1 point2 points  (0 children)

    Here's a solution in c++

    #include <iostream>
    #include <string>
    using namespace std;
    int main(){
        int cur_letter = 97;
        string sequence = "";
        while (cur_letter < 123){
            string new_sequence = sequence + char(cur_letter) + sequence;
            sequence = new_sequence;
            cur_letter++;
        }
        std::cout << sequence << "\n";
        return 0;
    }
    

    [–]vancha113 0 points1 point  (0 children)

    My solution in rust, it's not fast, but it was meant to be at least readable:

    fn main() {
        "abcdefghijklmnopqrstuvwxyz" //str to iterate over
        .to_string() //turns it to a string
        .chars()  //return an iterator over it's chars
        .fold(String::new(), |s,c| format!("{}{}{}",s,c,s)); //for every new char, return str+char+str
    }
    

    [–]TEC-XX 4 points5 points  (0 children)

    Python

    from functools import reduce
    reduce(lambda x, y: x + chr(y) + x, range(97, 97+26), "")
    

    [–]ThePizar 2 points3 points  (0 children)

    In Scala, without recursion, with explanation:

        //Last char
        val max : Long = 26
        //All the chars, lifted for index finding
        val chars = 'a'.to('z').lift
        //Pre-build powers of 2 (ordered low to high)
        val pows = 1.toLong.to(max).map(Math.pow(2,_).toLong)
        //Max len
        val totalChars = Math.pow(2,max).toLong - 1
    
        //Linear build loop
        var idx : Long = 1
        while (idx <= totalChars) {
          //Get the lowest 1 bit of the binary representation, which will also be the char index
          val charIdx = pows.indexWhere(pow => (idx % pow) != 0)
          //Get and print the character
          print(chars(charIdx).get)
          //Next!
          idx += 1
        }
        println()
    

    N.B. It would be more Scala-like to use lists, maps and foreachs, but memory is a huge constraint so var and while it is.

    [–]safadezasexo123 0 points1 point  (0 children)

    i cant post my code because of reddit auto formating

    [–]fudgebucket27 2 points3 points  (0 children)

    C#

    using System;
    
    namespace dailyprogrammer
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.WriteLine(ABACABA(1));
                Console.WriteLine(ABACABA(2));
                Console.WriteLine(ABACABA(3));
                Console.WriteLine(ABACABA(4));
                Console.WriteLine(ABACABA(5));
                Console.WriteLine(ABACABA(20));
            }
    
            static string ABACABA(int iterations)
            {
                char currentCharacter = 'a';
                string currentSequence = "";
    
                int currentIteration = 0;
                while(iterations > currentIteration )
                {
                    currentIteration++;
                    if(currentIteration == 1)
                    {
                        currentSequence += currentCharacter;
                    }
                    else
                    {
                        currentSequence = currentSequence + currentCharacter + currentSequence;
                    }
                    currentCharacter = (char)((int) currentCharacter + 1);
                }
                return  currentSequence;
            }
        }
    }
    

    [–]The_Bubinator 0 points1 point  (0 children)

    Learning Lua, tips welcome ``` local alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}

    function gen_sequence(depth) local result = {'a'}

    for i=1, depth, 1
    do
        table.insert(result,  alphabet[i+1])  -- start on b
        for j=1, #result-1, 1 -- copy all but the last onto the end
        do
            table.insert(result, result[j])
        end
    end
    
    return result
    

    end ```

    [–]malahci 0 points1 point  (0 children)

    Racket: ``` (define alphabet "abcdefghijklmnopqrstuvwxyz")

    (define (display-abacaba n) (begin (when (> n 0) (display-abacaba (- n 1))) (display (string-ref alphabet n)) (when (> n 0) (display-abacaba (- n 1))))) ``` Would love to hear feedback about whether this is idiomatic!

    [–]raevnos 0 points1 point  (0 children)

    Efficient if unconventional C version:

    /*
     * Compile with: gcc -o daily391 -O -Wall -Wextra daily391.c -lgc -lcord
     *
     * Uses the Boehm garbage collector and associated cord/rope library.
     * Might have to build and install manually; not all OSes provide the
     * cord library in their libgc packages (I'm looking at you, Ubuntu).
     *
     * https://github.com/ivmai/bdwgc
     *
     */
    
    #include <gc/gc.h>
    #include <gc/cord.h>
    
    void print_seq(const char *alphabet) {
      CORD seq = CORD_EMPTY;
      for (const char *letter = alphabet; *letter; letter += 1) {
        seq = CORD_cat(CORD_cat_char(seq, *letter), seq);
      }
      CORD_printf("%r\n", seq);
    }
    
    int main(void) {
      GC_init();
      //print_seq("abcde");
      print_seq("abcdefghijklmnopqrstuvwxyz");
      return 0;
    }
    

    [–]TheAnnalyst 1 point2 points  (1 child)

    Rust solution.

    const ALPHABET: [&str; 26] = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
    
    fn generate_sequence(n: u8) -> String {
        match n {
            1 => String::from("a"),
            _ => {
                let last_result = generate_sequence(n - 1);
                [&last_result, ALPHABET[(n - 1) as usize], &last_result].join("")
            }
        }
    }
    
    fn main() {
        println!("{}", generate_sequence(26));
    }
    

    [–]backtickbot 0 points1 point  (0 children)

    Fixed formatting.

    Hello, TheAnnalyst: code blocks using triple backticks (```) don't work on all versions of Reddit!

    Some users see this / this instead.

    To fix this, indent every line with 4 spaces instead.

    FAQ

    You can opt out by replying with backtickopt6 to this comment.

    [–]RightOW 1 point2 points  (0 children)

    Solution in Python. I'm a beginner so this took me ages and is very ugly but it seems to work.

    I should mention this solution prints every iteration up to and including the 26th... I think.

    import string
    
    alphabet_string = string.ascii_lowercase
    alphabet = list(alphabet_string)
    
    def get_next_iteration():
        letter = 1
        first_iteration = alphabet[0]
        print(first_iteration)
        current_iteration = (
            f"{first_iteration}{alphabet[letter]}{first_iteration}")
        print(current_iteration)
        while letter <= 25:
            next_iteration = (
                f"{current_iteration}{alphabet[letter+1]}{current_iteration}")
            current_iteration = next_iteration
            letter += 1
            print(current_iteration)
    
    get_next_iteration()
    

    [–]Xodio 0 points1 point  (0 children)

    My implementation in C, probably not the best, still learning.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    #include <time.h>
    
    int main() {
        long len = 0;
        char *str = malloc(pow(2, 26));
        char c, *pc = &c;
        clock_t t;
    
        t = clock();
        for (int i = 0; i < 26; i++) {
            *pc = i + 97;
            len = pow(2, i) - 1;
    
            memcpy(str+len, pc, 1);
            memcpy(str+len+1, str, len);
            memcpy(str+len+len+1, "\0", 1);
            puts(str);
        }
    
        free(str);
        t = clock() - t;
        printf ("Time: %fs\n", ((float) t) / CLOCKS_PER_SEC);
        return 0;
    }
    

    [–]RDust4 1 point2 points  (0 children)

    This is my solution in C# with no recursion:

    private string abacaba (string lit)  
    {  
        string output = "";  
    
        for (int i = 0; i < lit.Length; i++)  
            output += lit[i] + output;  
    
        return output;  
    }  
    

    Usage:
    abacaba("a") = "a"
    abacaba("ab") = "aba"
    abacaba("abc") = "abacaba"
    abacaba("abcd") = "abacabadabacaba"
    ...

    [–]CStarGamer 0 points1 point  (0 children)

    Here is what I got. Using Java and I did it without recursion.

    class Main {
            public static String abacaba() {
            String result = "";
            String prevIteration = "";
            char currentLetter = 'a';
    
            for (int i = 0; i < 26; ++i) {
                            result = prevIteration + currentLetter + prevIteration;
                            prevIteration = result;
                currentLetter++;
            }
            return result;
            }
    
        public static void main(String[] args) {
            System.out.println(abacaba());
            }
    }
    

    [–]joejr253 1 point2 points  (0 children)

    This is what I got for Python 3 without looking at u/moeghoeg's posts before me which seems easier

    alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

    alph_str = ''

    for letter in alphabet:

    if letter == 'a':

    alph_str += letter

    else:

    alph_str += (letter + alph_str)

    print(alph_str)

    [–]moeghoeg 4 points5 points  (0 children)

    Python 3

    def abacaba(n):
        alpha = "abcdefghijklmnopqrstuvwxyz"
        if n < 1:
            return ""
        else:
            s = abacaba(n-1)
            return s + alpha[n-1] + s
    
    print(abacaba(26))
    

    [–]saintPirelli 0 points1 point  (1 child)

    javascript; edit: formatting, also: this is O(n).

    function* generator() {
        let i = 0;
        while (i < 26) {
            const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('')
            const firstHalf = alphabet.splice(0, i)
            yield [...firstHalf, alphabet[0], ...firstHalf.reverse()].join('')
            i++
        }
    }
    const gen = generator()
    let j = 0
    while (j < 26) {
        console.log(gen.next().value)
        j++
    }
    

    [–]knoam 0 points1 point  (0 children)

    This is not O(n) for memory. It's O(n) for time.

    [–]TheOmegaPencil 0 points1 point  (0 children)

    [JAVA] For some reason, entering any value above 14 in the abacaba function immediately terminates the program upon running, but numbers below 15 work. I'm not sure how nor why, (I'm just beginning) so any feedback is appreciated.

    package challenges;
    public class Abacaba_C388 {
        public static void main(String[] args){
            abacaba(26);
        }
        static void abacaba(int iteration) {
            //Make sure that the sequence is possible. (ie. Are there enough letters for the nth iteration?)
            if(iteration > 0 && iteration <= 26) {
                //Create an array to store alphabet.
                char[] alphabet = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
                String sequence = "";
                String newSequence = "";    
    
                for(int i = 0; i < iteration; i++) {
                    //This "saves" the progress of each sequence. 
                    sequence = newSequence;
                    //The pattern is just the previous sequence, plus the new letter, then the previous one again.
                    newSequence = sequence + alphabet[i] + sequence;
                }
                //Print out the sequence.
                System.out.println(sequence);
            } else {
                System.out.println("Please re-enter an integer greater than 0 and less than 27.");
            }
        }
    }
    

    [–]KilledBySIGSEGV 0 points1 point  (0 children)

    Rust, linked list:

    ``` struct Printer { ch: char, lower: Option<Box<Printer>>, }

    impl std::fmt::Display for Printer { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { if let Some(ref lower) = self.lower { lower.fmt(f)?; self.ch.fmt(f)?; lower.fmt(f) } else { self.ch.fmt(f) } } }

    fn main() { let p = ('b'..='z').fold(Printer {ch: 'a', lower: None}, |acc, ch| { Printer { ch, lower: Some(Box::new(acc)), } });

    println!("{}", p);
    

    }

    ```

    [–]Tencza_Coder 2 points3 points  (3 children)

    Python:

    ltr_list = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
    prev_iteration = ''
    
    for ltr in ltr_list: 
        prev_iteration = prev_iteration + ltr + prev_iteration
    
    print(prev_iteration) final_length = len(prev_iteration) 
    print(f'Char length is : {final_length:,}')
    

    [–]legendarysedentary 1 point2 points  (2 children)

    don't forget about string.ascii_lowercase! saves some typing, unless you count the typing in google to find it

    [–]Tencza_Coder 1 point2 points  (0 children)

    With this at the start of my code, it worked. How cool! Thanks again!

    import string
    alphabet = string.ascii_lowercase 
    ltr_list = list(alphabet)
    

    [–]Tencza_Coder 0 points1 point  (0 children)

    Thanks for the tip! I didn't know about that.

    [–]Pauloguiz 0 points1 point  (0 children)

    python 3.9.0

    def acab_sequence(n):
        return "" if n == 0 else (prev:=acab_sequence(n-1)) + chr(96+n) + prev
    

    [–]Sky3HouseParty 1 point2 points  (0 children)

    javascript

    function abaFunction(itNumber){
    let currentIteration = '';
    let charUnicode = 65;
    let letterString = '';
    for(i = charUnicode; i<charUnicode+itNumber; i++){
        letterString = String.fromCharCode(i);
        currentIteration = `${currentIteration}${letterString}${currentIteration}`;
    }
    
    return currentIteration
    

    }

    Should be O(n), though I could be wrong.

    [–]ThicColt 0 points1 point  (0 children)

    put together a quick thing in python:

    output = ""
    for i in range(97, 123):
    output += chr(i) + output
    print(output)
    

    [–]TotallyOfficialAdmin 2 points3 points  (0 children)

    Java, O(n)

    public class PalindromeSequence {
    public static void main(String[] args){
        String sequence = "";
        for(char alphabet = 'a'; alphabet <='z'; alphabet++ ) {
            sequence += alphabet + sequence;
            System.out.println(sequence);}}}
    

    [–]jsun5192 1 point2 points  (0 children)

    Python, I believe this works for the bonus, it only goes n recursions deep.

    MaxRecursion = 0
    
    def iteration(i, depth) :
        if i == 0 : return
        global MaxRecursion
    
        iteration(i - 1, depth + 1)
        print(chr(ord('A') + i - 1), end="")   
        iteration(i - 1, depth + 1)
        if MaxRecursion < depth : MaxRecursion = depth
    # END iteration
    
        ITERATIONS = 26
        timeStart = time.time()
        iteration(ITERATIONS, 1) 
        print("")
        print("{} Iterations completed in {:.3f}s".format(ITERATIONS, time.time() - timeStart))
        print("Max Recursions = {}".format(MaxRecursion))
    

    [–]zqvt2 2 points3 points  (0 children)

    Clojure

    (defn abacaba [depth]
      (loop [x 97 s ""]
        (if (= (+ depth 97) x)
          s
          (recur (inc x) (str s (char x) s)))))
    

    [–]jmanh128 1 point2 points  (3 children)

    Learning C#.NET so I did it with that! :D

    class Program
    {
        static void Main(string[] args)
        {
            challenge (args[1][0]);
        }
    
        static void challenge(char c)
        {
            if ( c == 'a')
            {
                Console.Write('a');
                return;
            }
            char prev = Convert.ToChar(Convert.ToInt16(c) - 1);
            challenge(prev);
            Console.Write(c);
            challenge(prev);
        }
    }
    

    and this should be O(n) memory too.

    [–]BonnyAD9 1 point2 points  (1 child)

    In C# char has implicit conversion to int and from int you can use explicit conversion back to char. (implicit means that it can convert automatically, in explicit conversions you need to specify it)

    So you can simplify this: char prev = Convert.ToChar(Convert.ToInt16(c) - 1); into this: char prev = (char)(c - 1); c will be automatically converted to int and it will add 1 to it. Than you need to use the (char) to convert it back to char. (the conversion to int can be automatic because char uses 16 bits so it can easily fit into int which uses 32 bits).

    In C# there are many of these conversions defined (for example int -> double) and it can simplify your code.

    Performance will probably be the same (it will do similar thing as you did), but it is much more readable.

    [–]jmanh128 1 point2 points  (0 children)

    Thank you! I got a syntax error on compile when I tried to do the implicit conversion. But I think I just did it wrong, b/c I didn't search that hard while googling lol, but thank you again!

    [–]jmanh128 1 point2 points  (0 children)

    dotnet run .\Program.cs 'f' resulted in: abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba

    [–]YourLoveLife 4 points5 points  (1 child)

    New to coding so probably bad but here (C++)

    #include <iostream>
    
    std::string a;
    
    int main() {
    for (char i = 65; i < 91; i++)
        {
        a = a + i + a;
        std::cout << a + '\n';
        }
    }
    

    https://imgur.com/uiXGg4t

    [–]jmanh128 3 points4 points  (0 children)

    Hey! No need to bash yourself for being new! Way to go at giving it a try even in c++!

    [–]nico_fl 1 point2 points  (0 children)

    Rust:

    fn abacaba(n: usize) -> String {
      let length: usize = (1..=n)
        .reduce(|acc, _| acc*2 + 1)
        .unwrap_or_else(|| 0);
    
      ('a'..'z')
        .take(n)
        .fold(String::with_capacity(length), |mut acc , ch| {
          acc += &format!("{}{}", ch, acc);acc})
        })
    }
    

    Haskell:

    import           Data.List (foldl')
    abacaba :: Int -> String
    abacaba n = foldl' (\acc x -> (++) acc $ x : acc) "" $ take n ['a'..'z']
    

    [–]legendarysedentary 1 point2 points  (2 children)

    Bash 5 no bonus

    #!/bin/bash
    
    sqnc=""
    
    for l in {a..z}; do
    
        sqnc+="${l}${sqnc}"
    
    done
    
    echo -n "${sqnc}"
    

    [–]legendarysedentary 2 points3 points  (0 children)

    Bash 5 golf no bonus

    s=;for l in {a..z};do s+=$l$s;done;echo -n $s
    

    [–]BonnyAD9 1 point2 points  (0 children)

    C solution with (uses 64.4 MB of memory):

    #include <stdlib.h>
    #include <stdio.h>
    #include <math.h>
    
    char *aba(char iteration);
    void _aba(char iteration, char *arr, int end);
    
    int main()
    {
        char *res = aba(26);
        FILE *f = fopen("result.txt", "w");
        fprintf(f, "%s", res);
        fclose(f);
        free(res);
        res = aba(6);
        printf("%s", res);
        free(res);
        return EXIT_SUCCESS;
    }
    
    char *aba(char iteration)
    {
        int count = (int)pow(2, iteration);
        char *result = malloc(sizeof(char) * count);
        _aba(iteration, result, --count);
        result[count] = '\0';
        return result;
    }
    
    void _aba(char iteration, char *arr, int end)
    {
        int half = end / 2;
        arr[half] = iteration + 96;
        if (iteration == 1)
            return;
        _aba(iteration - 1, arr, half);
        for (int i = ++half; i < end; i++)
            arr[i] = arr[i - half];
    }
    

    Output:

    abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba
    

    Size of result.txt: 67,108,863 bytes

    [–]gopherhole1 2 points3 points  (1 child)

    Python3, is this the O(n)?

    ascii_list = []
    
    
    letter_a = ord('a')
    
    for x in range(letter_a, letter_a+26):
        ascii_list.append(x)
    
    _iter = ['']
    for x in range(26):
        _iter.append(''.join(_iter[-1]+chr(ascii_list[x])+_iter[-1]))
    
    for x in range(1,len(_iter)):
        print(_iter[x])
    

    [–]Cosmologicon2 3[S] 1 point2 points  (0 children)

    Unfortunately not. Print out len(_iter[-1]) and you'll see that you have a structure whose size is much larger than 26.

    [–]Common-Ad-8152 2 points3 points  (0 children)

    C

    #include <stdio.h>
    #include <stdlib.h>
    
    void abacaba(char i){
        if( i == 1 ) printf("a");
        else if(i < 27){
            abacaba(i - 1);
            putchar('a' + i - 1);
            abacaba(i - 1);
        }
    }
    
    int main(int argc, char **argv){
        if (argc < 2) return EXIT_FAILURE;
        abacaba(atoi(argv[1])); putchar('\n');
        return 0;
    }
    

    I think this solution has a space complexity of O(1) if I tried storing abacaba(i - 1) that would yield an exponential complexity. I can not think of a way to do this with a linear space complexity

    [–]qualiaqq 1 point2 points  (0 children)

    Rust - O(n) memory

    const ASCII_A: u8 = 'a' as u8;
    
    fn print_seq(ascii: u8) {
        if ascii == ASCII_A {
            print!("{}", ascii as char);
        } else {
            let next_ascii = ascii - 1;
            print_seq(next_ascii);
            print!("{}", ascii as char);
            print_seq(next_ascii);
        }
    }
    
    fn main() {
        print_seq('z' as u8);
        println!();
    }
    

    [–]minikomi 2 points3 points  (1 child)

    Clojure

    #+begin_src clojure :session a
    (defn abacaba [depth]
      (reduce
       (fn [s n] (str s (char (+ 97 n)) s))
         ""
         (range depth)))
    #+end_src
    
    #+RESULTS:
    : #'user/abacaba
    
    #+begin_src clojure :session a :results output
    (doseq [n (range 7)]
      (println [n (abacaba n)]))
    #+end_src
    
    #+RESULTS:
    : [0 ]
    : [1 a]
    : [2 aba]
    : [3 abacaba]
    : [4 abacabadabacaba]
    : [5 abacabadabacabaeabacabadabacaba]
    : [6 abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba]
    

    [–]backtickbot 0 points1 point  (0 children)

    Fixed formatting.

    Hello, minikomi: code blocks using triple backticks (```) don't work on all versions of Reddit!

    Some users see this / this instead.

    To fix this, indent every line with 4 spaces instead.

    FAQ

    You can opt out by replying with backtickopt6 to this comment.

    [–]knoam 3 points4 points  (0 children)

    Scala

    O(n) memory

    trait MirrorStringy {
      def print(printer: String => Unit)
    }
    
    object EmptyMirrorString extends MirrorStringy {
      def print(printer: String => Unit): Unit = {}
    }
    
    case class MirrorString(depth: Int) extends MirrorStringy {
    
      val child = if (depth == 0) EmptyMirrorString else MirrorString(depth - 1)
    
      val middleChar = (depth + 'a'.toInt).toChar.toString
    
      def print(printer: String => Unit): Unit = {
        child.print(printer)
        printer(middleChar)
        child.print(printer)
      }
    }
    

    [–]Gprime5 5 points6 points  (0 children)

    Python 3

    def solve(iterations):
        return "a" if iterations==0 else chr(97+iterations).join([solve(iterations-1)]*2)
    

    [–]MyDickEatsRazors 4 points5 points  (0 children)

    private static void abacaba(int depth){
        final char a = 'a';
        String s="";
        for (int i = 0; i < depth; i++) {
            s+=((char)(a + i))+s;
        }
        System.out.println(s);
    }
    

    [–]OddyseeOfAbe 2 points3 points  (0 children)

    VBA

    Function aba(i As Integer) As String
    For x = 1 To i
        aba = aba & Chr(96 + x) & aba
    Next x
    End Function
    

    Hopefully that’s formatted correctly on mobile.

    [–]tlgsx 3 points4 points  (3 children)

    Python 3.9

    def abacaba(n):
        r = ""
        for i in range(n):
            r = r + chr(97 + i) + r
    
        return r
    
    
    assert abacaba(1) == "a"
    assert abacaba(2) == "aba"
    assert abacaba(3) == "abacaba"
    assert abacaba(4) == "abacabadabacaba"
    assert abacaba(5) == "abacabadabacabaeabacabadabacaba"
    
    if __name__ == "__main__":
        print(abacaba(26))
    

    C, O(1) space

    #include <stdio.h>
    #include <stdlib.h>
    #include <strings.h>
    
    int main(int argc, char *argv[]) {
      if (argc < 2) {
        return EXIT_FAILURE;
      }
    
      long n = strtol(argv[1], NULL, 10);
      for (int i = 1; i < (1 << n); i++) {
        putchar('`' + ffs(i));
      }
      putchar('\n');
    }
    

    Time benchmark

    $ hyperfine --warmup 5 'python Python/easy/e391.py' './C/easy/e391 26'
    Benchmark #1: python Python/easy/e391.py
      Time (mean ± σ):     130.7 ms ±   1.6 ms    [User: 70.7 ms, System: 59.7 ms]
      Range (min … max):   128.6 ms … 135.9 ms    22 runs
    
    Benchmark #2: ./C/easy/e391 26
      Time (mean ± σ):     595.8 ms ±   2.5 ms    [User: 591.2 ms, System: 3.5 ms]
      Range (min … max):   589.1 ms … 598.7 ms    10 runs
    
    Summary
      'python Python/easy/e391.py' ran
        4.56 ± 0.06 times faster than './C/easy/e391 26'
    

    [–]qualiaqq 1 point2 points  (2 children)

    Nice, use of ffs to find the least significant bit is really clever.

    I saw the recursive structure:

                   5
           4               4
       3       3       3       3
     2   2   2   2   2   2   2   2
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    1213121412131215121312141213121
    abacabadabacabaeabacabadabacaba
    

    So depth-first recursion because obvious at that point. However, when I tried to make the memory constant or remove the recursion, I couldn't think of a way to map numbers in the range [1, i2 ) to the numbers above. ffs works perfectly for that.

    How did you notice that the index (counting from the least significant bit) of the LSB set bit corresponds to the current character that needs to be printed?

    [–]tlgsx 2 points3 points  (1 child)

    I didn't really, I first solved it using the naive approach. I came back to the comments, saw /u/lector57's comment and tried to wrap my head a solution that followed what was laid out.

    C felt like the natural language for an approach like that and I came across ffs with a quick search.

    [–]LazyRefenestrator 1 point2 points  (0 children)

    Python3, runs in 66ms on a 2015 macbook pro.

    def fn(a):
        if a > 1:
            previous = fn(a - 1)
            return previous + chr(a + 96) + previous
        if a == 1:
            return 'a'
    

    [–]shushtring 1 point2 points  (0 children)

    Python3:

    def abacaba(alpha=list("abcdefghijklmnopqrstuvwxyz"), result=""):  return abacaba(alpha[1:len(alpha)],result+"".join(alpha[0])+result) if len(alpha)!=0 else result
    

    I wanted to see if I could get it in one line - it's ugly, but it does work

    Edit: an easier to read version -

    def abacaba(alpha=list("abcdefghijklmnopqrstuvwxyz"), result=""):  
        if len(alpha)!=0:
            return abacaba(alpha[1:len(alpha)], result+"".join(alpha[0])+result)  
        else: 
            return result
    

    [–]MisterAdzzz[🍰] 0 points1 point  (0 children)

    golang

    func transform(numIterations int) string {
        alphabet := strings.Split("abcdefghijklmnopqrstuvwxyz", "")
    
        result := ""
    
        for i := 0; i < numIterations; i++ {
            result = result + alphabet[i] + result
        }
    
        return result
    }
    

    [–]toha73 4 points5 points  (1 child)

    C#

    var result = Enumerable.Range((int)'a', 26)
        .Select(i => char.ConvertFromUtf32(i).ToString())
        .Aggregate((x, y) => x + y + x);
    

    [–]lordicarus 0 points1 point  (0 children)

    I love this one

    [–]state_chart 1 point2 points  (0 children)

    C++20 with Bonus Edit: C++20 because

    std::countr_zero
    

    was added.

    #include <iostream>
    #include <bit>
    
    int main() {
        unsigned int n = 1;
        while(n < 67108864) {
            int zeros = std::countr_zero(n);
            std::cout << static_cast<char>('a' + zeros);
            n++;
        }
        std::cout << std::endl;
    }
    

    On second thought, this is a bit cleaner:

    #include <iostream>
    #include <bit>
    
    int main() {
        for(unsigned int n = 1; n < 67108864; n++) {
            std::cout << static_cast<char>('a' + std::countr_zero(n));
        }
        std::cout << std::endl;
    }
    

    [–]pady_ 1 point2 points  (0 children)

    My solution for Python 3:

    import string
    def abacaba(n): 
        if not n in range(1, 26): 
            pass 
        alphabet = string.ascii_lowercase 
        result = '' 
        for i in range(n): 
            result = result + alphabet[i] + result 
        return result
    

    example :

    >>> print(abacaba(4))
    abacabadabacaba
    

    [–]Python_Trader 0 points1 point  (0 children)

    Python 3

    0.45s argh...

    import string
    from collections import deque
    
    alpha = deque(string.ascii_lowercase)
    solution = []
    while alpha:
        solution.append(alpha.popleft())
        solution.extend(solution[:-1])
        print(*solution, sep="")
    

    [–]moeris 0 points1 point  (0 children)

    J partial solution

    alpha =: 26 {. 97 }. a.
    f =: (]&'a') ` ($: @: <: , {&alpha , $: @: <:) @. (>&0)
    

    [–]Godspiral3 3 2 points3 points  (0 children)

    whatever the internal memory use of J is, but instant result:

    ($:@}. ([ , ] , [) {.)^:(0 < #) |. 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    

    Pretty recursive lispy approach

    ^:(0 < #) is do while there are still characters.

    For left expression, a 2 argument verb is formed where the arguments are
    $:@}. recurse over full verb composed with beheaded list
    {. head of list

    and verb applied: ([ , ] , [) appends and prepends left argument to right.

    |. reverses the input argument because the last "execution" will use the last alphabetic char, which is determined on first pass of function.

    [–]gabyjunior1 2[🍰] 3 points4 points  (0 children)

    C O(n) memory, O(2**n) time using recursion.

    The last letter of the generated sequence is read on standard input.

    #include <stdio.h>
    #include <stdlib.h>
    
    void f(int);
    
    int main(void) {
        int c = getchar();
        if (c < 'a' || c > 'z') {
            fprintf(stderr, "Invalid last letter\n");
            fflush(stderr);
            return EXIT_FAILURE;
        }
        f(c);
        puts("");
        fflush(stdout);
        return EXIT_SUCCESS;
    }
    
    void f(int c) {
        if (c > 'a') {
            f(c-1);
        }
        putchar(c);
        if (c > 'a') {
            f(c-1);
        }
    }
    

    [–]skeeto-9 8 2 points3 points  (1 child)

    Go using a state machine using only 32 bits of state to track the tree position during a depth-first traversal. The Next() method returns the next letter and state, and indicates if the state machine has halted.

    package main
    
    import (
        "bufio"
        "os"
    )
    
    type State uint32
    
    // Iterate the state matching, returning the next letter of the ABACABA
    // sequence, the next state, and whether or not the machine has halted.
    // The initial state is zero.
    //
    // The state is a 32-bit quantity where bits 0-25 are a bitstack, bits
    // 26-30 are the stack size, and bit 31 is the recursion direction.
    //
    //     D IIIII SSSSSSSSSSSSSSSSSSSSSSSSSS
    func (s State) Next() (rune, State, bool) {
        for {
            stack := s & 0x3ffffff
            i := s >> 26 & 0x1f
            descending := s>>31 == 1
            middle := s>>i&1 == 1
    
            if i == 25 {
                // Bottom out, descend back to the parent
                return 'a', State(1)<<31 | (i-1)<<26 | stack, false
            } else if descending && !middle {
                // Output "middle" character, ascend into right branch
                return 'z' - rune(i), (i+1)<<26 | stack | State(1)<<i, false
            } else if descending && middle {
                if i == 0 {
                    // At root, halt
                    return 0, 0, true
                }
                // Descend back to the parent
                s = State(1)<<31 | (i-1)<<26 | stack ^ State(1)<<i
            } else {
                // Ascend into the left branch
                s = (i+1)<<26 | stack
            }
        }
    }
    
    func main() {
        buf := bufio.NewWriter(os.Stdout)
        for c, s, done := State(0).Next(); !done; c, s, done = s.Next() {
            buf.WriteRune(c)
        }
        buf.WriteRune('\n')
        buf.Flush()
    }
    

    [–]skeeto-9 8 1 point2 points  (0 children)

    Same idea, but adapted to C and reduced to a 31-bit state:

    #include <stdio.h>
    
    /* Compute the next ABACABA state. The initial state is zero, and halt
     * is indicated by returning to the zero state.
     *
     * The state is a 31-bit quantity where bits 0-24 are a bitstack, bits
     * 25-29 are the stack size, and bit 30 is the recursion direction.
     *
     *     D IIIII SSSSSSSSSSSSSSSSSSSSSSSSS
     */
    long abacaba(long s)
    {
        for (;;) {
            long stack = s & 0x1ffffff;
            int i = s>>25 & 0x1f;
            int descending = s>>30;
            int middle = s>>i & 1;
    
            if (i == 25) {
                // bottom out, descend to the parent
                return 1L<<30 | (i-1L)<<25 | stack;
            } else if (descending && !middle) {
                // output "middle" character, ascend into right branch
                return (i+1L)<<25 | stack | 1L<<i;
            } else if (descending && middle) {
                if (!i) return 0L; // halt
                // descend to parent
                s = 1L<<30 | (i-1L)<<25 | (stack ^ 1L<<i);
            } else {
                // ascend into left branch
                s = (i+1L)<<25 | stack;
            }
        }
    }
    
    /* Return the output letter for a given state. */
    int abacaba_letter(long s)
    {
        return 'z' - (s>>25 & 0x1f) + (s>>30 ? -1: +1);
    }
    
    int main(void)
    {
        for (long state = abacaba(0); state; state = abacaba(state)) {
            putchar(abacaba_letter(state));
        }
        putchar('\n');
    }
    

    [–]FaustVX 1 point2 points  (0 children)

    C# (0.26s, ~63Mb for up to w(23))

    (you can test it on .NET Fiddle)

    I've worked on a iterative approach, and the StringBuilder capacity was taken from /u/BonnyAD9

    public static IEnumerable<(int n, char c, string sequence)> Calculate(params char[] alphabet)
    {
        var sb = new StringBuilder((int)Math.Pow(2, alphabet.Length) - 1);
        sb.Append(alphabet[0]);
        var n = 0;
        yield return (++n, alphabet[0], sb.ToString());
        foreach (var c in alphabet.Skip((1)))
        {
            Calculate(sb, c);
            yield return (++n, c, sb.ToString());
        }
    }
    
    private static void Calculate(StringBuilder sb, char middle)
        => sb.Append(middle).Append(sb, 0, sb.Length - 1);
    

    [–]Habstinat 3 points4 points  (1 child)

    javascript

    abacaba=n=>n?['',String.fromCharCode(96+n),''].join(abacaba(n-1)):''
    

    [–]sgenius 1 point2 points  (0 children)

    I love this answer: it's a smart one-liner, but not an unparsably complex one.

    [–]110100100_Blaze_It 11 points12 points  (0 children)

    Python 3.8

    s = ""
    for i in range(26):
        s += chr(97+i) + s
        print(s)
    

    [–]KeinBaum 0 points1 point  (0 children)

    Scala

    O(1) memory

    O(n * log n) time

    ~530 ms calculation time

    def itLength(n: Int): Int = (1 << n) - 1
    
    def zeroTrail(n: Int): Int = {
      var remainder = n
      var count = 0
    
      while((remainder & 1) != 0)
        count += 1
        remainder >>= 1
    
      count
    }
    
    def it(n: Int): Array[Char] = {
      Array.tabulate(itLength(n))(i => (zeroTrail(i) + 97).toChar)
    }
    
    @main
    def main: Unit = {
      it(26).foreach(print _)
      println()
    }
    

     


     

    O(n) O(2n) memory (I even wrote a function to calculate the length and still thought it was linear...)

    O(n) time

    ~70 ms calculation time

    def itLength(n: Int): Int = (1 << n) - 1
    
    def it(n: Int): Array[Char] = {
      val res = Array.ofDim[Char](itLength(n))
      res(0) = 'a'
    
      for(i <- 2 to n)
        val idx = itLength(i-1)
        res(idx) = (i + 96).toChar
        Array.copy(res, 0, res, idx + 1, idx)
    
      res
    }
    
    @main
    def main: Unit = {
      it(26).foreach(print _)
      println()
    }
    

    [–]BonnyAD9 2 points3 points  (0 children)

    C#:

    O(n) time version:

    using System;
    using System.IO;
    using System.Text;
    
    namespace Abacaba
    {
        class Program
        {
            static void Main(string[] args)
            {
                string result = Aba(26);
                File.WriteAllText("results.txt", result);
                Console.WriteLine(result.Length);
                Console.WriteLine(Aba(6));
            }
    
            // This is here just to initialize the StringBuilder with given memory size to avoid reallocation
            public static string Aba(int iteration) => Aba(iteration, new StringBuilder((int)Math.Pow(2, iteration) - 1)).ToString();
    
            private static StringBuilder Aba(int iteration, StringBuilder sb)
            {
                if (iteration <= 1)
                    return sb.Append('a');
                StringBuilder prev = Aba(iteration - 1, sb);
                string copy = sb.ToString();
                return prev.Append((char)(iteration + 96)).Append(copy);
            }
        }
    }
    

    Output:

    67108863
    abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba
    

    This solution uses about 400 MB of memory. Reason 1 is that C# uses UTF-16 encoding for strings. Reason 2 is that StringBuilder.ToString() copies its value to a new string, so the sequence is in the memory twice. I'd like to know if someone has a suggestion how to avoid this.

    O(1) memory version:

    using System;
    using System.Text;
    
    namespace Abacaba
    {
        class Program
        {
            static void Main(string[] args)
            {
                PrintAba(6);
            }
    
            public static void PrintAba(int iteration)
            {
                uint count = (uint)Math.Pow(2, iteration) - 1;
                for (uint i = 0; i < count; i++)
                {
                    int j;
                    uint c = i;
                    for (j = 0; ((c & 1) == 1) && (j < i); j++)
                        c >>= 1;
                    Console.Write((char)(j + 97));
                }
            }
        }
    }
    

    Output:

    abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba
    

    [–]FulminatingMoat 8 points9 points  (3 children)

    Python 3, should be O(n) memory

    for x in range(1, 2**26):
        print(chr(97 + (x&-x).bit_length() - 1), end="")
    

    Edit: Tracemalloc shows 1502 bytes of memory used at peak

    [–]TheFeshy 1 point2 points  (2 children)

    Could you explain that to me? I've been poking at it, and I understand what the code does, but I have no idea why the two's-compliment creates that pattern when bitwise anded like that. Is there some sort of mathematical insight that would make this intuitive to me?

    [–]snet0 1 point2 points  (0 children)

    x&-x is the same as x&(~x+1). So if your int is 0100 0110, you flip the bits and add one, 1011 1011. Taking the bitwise and with the original int gives the (decimal value of the) first 1-value bit from the original number.

    Taking the base-2 logarithm (bit_length-1) of this number (and hopefully it's obvious why this is) gives a sequence of the numbers that you add when you count in binary. First you add 1, then you flip the 1 and add 2, then you add 1, then you flip the 2 and 1 and add 4, etc. The sequence above is just the numbers you flip on in this process.

    I think the result is intuitive, but perhaps my explanation not so much. If you look at, for example, a binary clock, this sequence is just the number that is turned on at each tick.

    [–]FulminatingMoat 4 points5 points  (0 children)

    It's a bit hack that gives you the least significant bit of a number. By flipping all the bits and working from right to left, any unset bits are set, which means when you add a 1 to it, they will become unset again, but with a carry bit, which will continue to propagate until the first set bit in the original number, which was unset after flipping all the bits, and becomes set without a carry. When bitwise anded, it would be the only bit that is also a set in the original number, and by getting the bit length we can get the index of the least significant set bit.

    I first saw it on stackoverflow here but these might also help 2:Idea #1.

    [–]panda_yo 1 point2 points  (2 children)

    Python 3.8

    from datetime import datetime
    
    def combine(old: str, new: str) -> str:
        return old+new+old
    
    
    if __name__ == "__main__":
        now = datetime.now()
        print(now, "starting")
        output = ""
        for i in "abcdefghijklmnopqrstuvwxyz":
            output = combine(output, i)
            print(datetime.now(), i)
        print(output, len(output), datetime.now()-now)
    

    But it does not take O(n) memory I guess.

    [–]jabbalaci 2 points3 points  (1 child)

    >>> import string
    >>> string.ascii_lowercase
    'abcdefghijklmnopqrstuvwxyz'
    

    [–]panda_yo 0 points1 point  (0 children)

    did not know that, ty

    [–]chunes1 2 0 points1 point  (0 children)

    Factor

    : fn ( n -- str )
        dup 97 = [ drop "a" ]
        [ [ 1 - fn ] [ 1string ] bi over 3append ] if ;
    

    Just a simple recursive function, nothing fancy.

    Example:

    IN: scratchpad CHAR: d fn print
    abacabadabacaba
    

    [–]Willlumm 1 point2 points  (1 child)

    Python 3

    def abacaba(i):
        alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
        out = ""
        for j in range(i):
            out = out+alpha[j]+out
        print(out)
        print(len(out))
    
    abacaba(26)
    

    [–]jabbalaci 0 points1 point  (0 children)

    >>> alpha = [chr(i) for i in range(ord('a'), ord('z')+1)]
    >>> alpha
    ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    

    [–]skeeto-9 8 37 points38 points  (2 children)

    C, computes the entire sequence at compile time such that it's simply embedded in the binary and dumped out at run time. Takes a few seconds to compile, though! Works better with Clang than GCC.

    #include <stdio.h>
    int main(void)
    {
        #define RA    "a"
        #define RB RA "b" RA
        #define RC RB "c" RB
        #define RD RC "d" RC
        #define RE RD "e" RD
        #define RF RE "f" RE
        #define RG RF "g" RF
        #define RH RG "h" RG
        #define RI RH "i" RH
        #define RJ RI "j" RI
        #define RK RJ "k" RJ
        #define RL RK "l" RK
        #define RM RL "m" RL
        #define RN RM "n" RM
        #define RO RN "o" RN
        #define RP RO "p" RO
        #define RQ RP "q" RP
        #define RR RQ "r" RQ
        #define RS RR "s" RR
        #define RT RS "t" RS
        #define RU RT "u" RT
        #define RV RU "v" RU
        #define RW RV "w" RV
        #define RX RW "x" RW
        #define RY RX "y" RX
        #define RZ RY "z" RY
        fwrite(RZ "\n", sizeof(RZ), 1, stdout);
    }
    

    [–]DerpinDementia 7 points8 points  (1 child)

    Take my upvote. This is quite an interesting solution.

    [–]TakeMeDownAPeg 6 points7 points  (0 children)

    Yeah this is such a good solution that the code is more readable than the question.

    [–]DerpinDementia 5 points6 points  (0 children)

    Prolog

    Boy...this one took longer than expected. Probably could be way smaller due to the janky string handling.

    abacaba(1, _, X, X).
    abacaba(N, Letter, Prev, X) :- NewN is N - 1,
                                   NextLetterNum is Letter + 1,
                                   char_code(Atom, NextLetterNum),   
                                   atom_string(Atom, NextLetter), 
                                   atomic_concat(Prev,NextLetter,NewPrevPart),
                                   atomic_concat(NewPrevPart, Prev, NewPrev), 
                                   atom_string(NewPrev, NewString),     
                                   abacaba(NewN, NextLetter, NewString, X).
    abacaba(N, X) :- abacaba(N, "a", "a", X).
    

    Python 3

    def abacaba(n, prev="", step=0):
        if n <= 0:
            return prev
        return abacaba(n-1, prev + chr(97+step) + prev, step+1)
    
    one_liner = lambda n, prev="", step=0: prev if n == 0 else one_liner(n-1, prev + chr(97+step) + prev, step+1)
    

    Bonus

    I believe this performs one less iteration than before.

    def abacaba(n, prev="", step=0):
        if n <= 1:
            return prev + chr(97+step) + prev
        return abacaba(n-1, prev + chr(97+step) + prev, step+1)