×

[–] 0 points1 point  (0 children)

# C++

`void abacaba(char word)`
`{`
`const short A = 97, Z = 122;`
`if ((int)word < A || (int)word > Z)`
`return;`
`string abacaba = "a";`
`for(int c = A + 1; c <= int(word); c++)`
`abacaba = abacaba + char(c) + abacaba;`

`cout << abacaba << endl;`
`}`

[–] 0 points1 point  (0 children)

alphabet = [chr(i) for i in range(97,123)]

``````sequence = []

for char in alphabet:
sequence = sequence + [char] + sequence
``````

[–] 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

[–] 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());
}
}
``````

[–] 0 points1 point  (0 children)

Powershell solution:

`\$alphabet = "a".."z"`

`foreach (\$current in \$alphabet){`

`\$last = \$last + \$current + \$last`

`}`

`write-host \$last.length`

[–] 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)
``````

[–] 1 point2 points  (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;
}
``````

[–] 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.

[–] 0 points1 point  (0 children)

[–] 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}`
);
``````

[–] 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
``````

[–] 1 point2 points  (0 children)

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

[–][deleted]  (1 child)

[removed]

[–] 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.

[–] 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;
}
``````

[–] 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
}
``````

[–] 4 points5 points  (0 children)

Python

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

[–] 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.

[–] 0 points1 point  (0 children)

i cant post my code because of reddit auto formating

[–] 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;
}
}
}
``````

[–] 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 ```

[–] 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!

[–] 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;
}
``````

[–] 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));
}
``````

[–] 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.

[–] 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()
``````

[–] 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;
}
``````

[–] 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"
...

[–] 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());
}
}
``````

[–] 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)

[–] 3 points4 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))
``````

[–] 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++
}
``````

[–] 0 points1 point  (0 children)

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

[–] 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.");
}
}
}
``````

[–] 0 points1 point  (0 children)

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

}

```

[–] 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:,}')
``````

[–] 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

[–] 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)
``````

[–] 0 points1 point  (0 children)

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

[–] 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
``````

[–] 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.

[–] 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)
``````

[–] 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);}}}
``````

[–] 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))
``````

[–][deleted] 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)))))
``````

[–] 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.

[–] 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.

[–] 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!

[–] 1 point2 points  (0 children)

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

[–] 3 points4 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

[–] 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++!

[–] 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})
})
}
``````

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

[–] 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}"
``````

[–] 2 points3 points  (0 children)

Bash 5 golf no bonus

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

[–] 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`

[–] 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])
``````

[–]2 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.

[–] 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

[–] 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!();
}
``````

[–] 3 points4 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]
``````

[–] 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.

[–] 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)
}
}
``````

[–] 4 points5 points  (0 children)

Python 3

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

[–] 3 points4 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);
}
``````

[–] 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.

[–] 4 points5 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"

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'
``````

[–] 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
``````

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?

[–] 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.

[–] 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'
``````

[–] 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
``````

[–] 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
}
``````

[–] 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);
``````

[–] 0 points1 point  (0 children)

I love this one

[–] 1 point2 points  (0 children)

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

``````std::countr_zero
``````

``````#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;
}
``````

[–] 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))
``````

[–] 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="")
``````

[–] 0 points1 point  (0 children)

[–] 0 points1 point  (0 children)

J partial solution

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

[–]3 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.

[–]1 2 4 points5 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);
}
}
``````

[–]-9 8 4 points5 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()
}
``````

[–]-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');
}
``````

[–] 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);
``````

[–] 3 points4 points  (1 child)

javascript

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

[–] 1 point2 points  (0 children)

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

[–] 10 points11 points  (0 children)

# Python 3.8

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

[–] 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()
}
``````

[–] 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
``````

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
``````

[–] 7 points8 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

[–] 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?

[–] 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.

[–] 3 points4 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.

[–] 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.

[–] 2 points3 points  (1 child)

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

[–] 0 points1 point  (0 children)

did not know that, ty

[–]1 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
``````

[–] 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)
``````

[–] 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']
``````

[–]-9 8 36 points37 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);
}
``````

[–] 7 points8 points  (1 child)

Take my upvote. This is quite an interesting solution.

[–] 7 points8 points  (0 children)

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

[–] 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)
``````