C

cat >a.c <<. #define _(a...) {return({a;});} #define F(i,x,n,a...) for(I i=(x),n_=(n);i<n_;i++){a;} #define i(a...) F(i,0,a) #define j(a...) F(j,0,a) #define k(a...) F(k,0,a) #define I(a...) F(i,a) #define S static #define O const #define mc __builtin_memcpy #define sl __builtin_strlen typedef void V;typedef char C;typedef int I; #include<sys/syscall.h> #define M1(x) #x #define M2(x) M1(x) #define h(x,a...) ".globl "#x";"#x":"a"mov $"M2(SYS_##x)",%rax;syscall;ret;" asm(".globl _start;_start:pop %rdi;mov %rsp,%rsi;call main;"h(write)h(exit));I write(I,C*,I);V exit(I); V*memcpy(V*x,O V*y,I n)_(C*a=x;O C*b=y;i(n,a[i]=b[i])a)I strlen(O C*s)_(I r=0;while(*s++)r++;r) S O C A0=32,A1=126+1,AN=A1-A0;S C o0[1<<20],*o=o0; S V rpt(C*a,I n,I m){m*=n;while(2*n<m){mc(a+n,a,n);n+=n;}mc(a+n,a,m-n);} S I fd(C*s,I n,I p)_(i(p,j(n,*o++=s[j+(i<=j)]))p) S I fc(C*s,I n,I p)_(mc(o,s,n+1);rpt(o,n+1,p*AN);I(A0,A1,j(p,o[j]=i;o+=n+1))p) S I fi(C*s,I n,I p)_(p++;i(p,j(n+2,o[i*(n+2)+j]=s[j-(i<j)]))rpt(o,p*(n+2),AN);I(A0,A1,j(p,o[j]=i;o+=n+2))p) I main(I c,C**v)_(S C s[32];I n=sl(v[1]);mc(s,v[1],n);s[n]=10;S typeof(fd)*f[]={fd,fc,fi}; i(3,o=o0;I g=f[i](s,n,n);j(g*(i?AN:1),C*b=o;k(3,f[k](o0+(n+i)*j,n+i-1,j%g))write(1,b,o-b);o=b)) exit(0);0) . clang -O3 -march=native -nostdlib -ffreestanding a.c && strip a.out -R .comment time ./a.out abcdefghijklmnop >/dev/null 

Try it online!

for the record, here's why this answer didn't win the bounty: https://chat.stackexchange.com/transcript/message/56646474#56646474

C++ ('C with operator overloading')

^{edit: no longer outputs any duplicates if the set of characters allowed for insertions and substitutions doesn't intersect with the string's character set! (further improvement will probably require something smarter)
edit2: now even less duplicates: doesn't consider cases like inserting abcd -> abbcd twice
edit3: tiny optimization in bufprint. I don't know how to optimize it further :(
edit4: optimized bufprint some more; edit5: found a better bufsize}

#include <cstdio> #include <cstdint> #include <cstdlib> #include <cmath> #include <climits> #include <cstring> const char rStart = 32; //for testing purposes, I often set these to 48 and 49 const char rEnd = 126; const bool enableio = true; const int bufsize = 524288; //char printbuf[bufsize]; int printbuf[bufsize / 32][8]; //using a size of 24 bytes per fixed-length string caused a SIMD unaligned store and was slightly slower int printbufi = 0; void bufflush() { if(enableio) fwrite(printbuf, 32, printbufi, stdout); printbufi = 0; } void bufprint(const char* x) //not confusing because printbuf is the print buffer and bufprint prints using the buffer { //most of the time is spent in this function if(printbufi >= bufsize/32 - 1) bufflush(); __builtin_memcpy(&printbuf[printbufi], x, 20); //printbuf[printbufi][5] = 0x0a0a0a0a; //not necessary! it's possible to just set these newlines in the beginning and never change them again printbufi++; //bufflush(); } struct string //not null-terminated { char data[20] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }; int len; bool operator < (const string& rhs) const { return memcmp(data, rhs.data, 24) < 0; } bool operator == (const string& rhs) const { const uint64_t* p1 = (const uint64_t*)this, *p2 = (const uint64_t*)&rhs; bool eq = p1[0] == p2[0] && p1[1] == p2[1] && p1[2] == p2[2]; return eq; } string insert(int i, char c) const { string copy; copy.len = len + 1; for(int j = 0; j < i; j++) copy[j] = data[j]; for(int j = i; j < len; j++) copy[j+1] = data[j]; copy[i] = c; return copy; } string prepend(char c) const { string copy; copy.len = len + 1; for(int j = 0; j < len; j++) copy[j+1] = data[j]; copy[0] = c; return copy; } string pop_front() const { string copy; copy.len = len - 1; for(int j = 0; j < len-1; j++) copy[j] = data[j+1]; return copy; } string erase(int i) const { string copy; copy.len = len - 1; for(int j = 0; j < i; j++) copy[j] = data[j]; for(int j = i; j < len; j++) copy[j] = data[j+1]; return copy; } inline char& operator[](int i) { //if(i >= len) while(true) throw "abc"; return data[i]; } void print() const { bufprint(data); } }; void changeloop(string x, int skip = -2) //all strings exactly 1 change away { for(int i = 0; i < x.len; i++) { if(i == skip || i == skip+1) continue; char oc = x[i]; for(int nc = rStart; nc <= rEnd; nc++) { if(nc == oc) continue; x[i] = nc, x.print(); } x[i] = oc; } } void changeloop2(string x, int skip = -2) //same with different skip { for(int i = 0; i < x.len; i++) { if(i == skip) continue; char oc = x[i]; for(int nc = rStart; nc <= rEnd; nc++) { if(nc == oc) continue; x[i] = nc, x.print(); } x[i] = oc; } } void insertloop(string x, int max = INT_MAX) //all strings exactly 1 insertion away { //example: //?abcd //a?bcd //ab?cd //abc?d //abcd? //it can be observed that each character simply iterates over all possible values, and then gets set to the ith character of the string string s = x.prepend(x[0]); max = std::min(max, s.len); for(int i = 0; i < max; i++) { for(char nc = rStart; nc <= rEnd; nc++) { if(i != 0 && x[i-1] == nc) continue; s[i] = nc, s.print(); } if(i < x.len) s[i] = x[i]; } } void deleteloop(string x, int max = INT_MAX) { //example: //bcde //acde //abde //abce //abcd //erase first character, print and then copy the original character n-1 times string s = x.pop_front(); s.print(); max = std::min(max, x.len - 1); for(int i = 0; i < max; i++) { s[i] = x[i]; s.print(); } } void dist1(string x) { x.print(); changeloop(x); insertloop(x); deleteloop(x); } //options: //insert //insert, change //insert, insert //change //change, change //delete //strings with distance at most 1 from delete void dist2(string x) { string s = x.prepend(x[0]); for(int i = 0; i < x.len+1; i++) { for(char nc = rStart; nc <= rEnd; nc++) { //string s = x.insert(i, nc); if(i != s.len-1 && s[i+1] == nc) continue; s[i] = nc; //s[s.len] = 0; s.print(); //insert insertloop(s, i+1); //insert, insert. only do the second insert before this one changeloop(s, i); //insert, change. the change can be anywhere except i and i+1 } if(i < x.len) s[i] = x[i]; } //changeloop(x); //change. can always be replaced by delete->reinsert for(int i = 0; i < x.len; i++) for(int j = i+1; j < x.len; j++) { char oci = x[i], ocj = x[j]; for(int nci = rStart; nci <= rEnd; nci++) for(int ncj = rStart; ncj <= rEnd; ncj++) { if(nci == oci) continue; if(ncj == ocj) continue; x[i] = nci; x[j] = ncj; x.print(); //change, change } x[i] = oci; x[j] = ocj; } s = x.pop_front(); s.print(); changeloop(s); insertloop(s); for(int i = 0; i < x.len-1; i++) { s[i] = x[i]; //s[s.len] = 0; s.print(); changeloop2(s, i); insertloop(s); deleteloop(s, i); //deletion must be before i } } int main(int argc, char*argv[]) { if(argc < 2) { printf("input the string as a command line argument! :(\n"); return 1; } memset(printbuf, 0x0a, sizeof(printbuf)); string s; strcpy(s.data, argv[1]); s.len = strlen(argv[1]); s.data[s.len] = 10; //fix the null byte that should not be there //for(int i = 0; i < 200; i++) //{ // dist2(s); // fprintf(stderr, "%d\r", i); //} dist2(s); bufflush(); } 

This outputs many empty lines between strings (to avoid unaligned memory writes to the IO buffer). This outputs much fewer duplicates than the C answer: for abcdefghijklmnop the C answer outputs 10237362 lines, and my answer outputs only 4920334 4774446 4724312 non-empty lines, while only 4720038 are necessary. I compile with g++ a.cpp -std=c++17 -march=native -Ofast -no-pie -fno-stack-protector.

Python 3

cat >a.py <<. strs=[input()] def a(b): new = [] for x in range(32, 127): c = chr(x) for strn in b: for y in range(0, len(strn)): start = strn[:y] end = strn[y+1:] new.append(start + c + end) new.append(start + end) new.append(start + c + strn[y:]) new.append(strn + c) return new print(len(a(set(a(strs))))) . time python3 a.py <<<abcdefghijklmnop 

Try it online!

Optimized by ovs, thanks.

Rust

Tested with rustc 1.51.0-nightly (e22670468 2020-12-30).
Must be compiled with -O1 (or above) so functions are properly inlined, or it segfaults.

Please build with cargo build, then time the binary in target/debug/q216902. It's segfaulting in release mode at the moment, and I don't know why.

Cargo.toml

[package] name = "q216902" version = "0.1.0" authors = ["wizzwizz4"] edition = "2018" [dependencies] rlibc = "1.0.0" [profile.dev] debug-assertions = true opt-level = 1 panic = "abort" [profile.release] panic = "abort" # debug = 2 

main.rs

#![feature(asm)] #![feature(const_in_array_repeat_expressions)] #![feature(const_maybe_uninit_assume_init)] #![feature(link_args)] #![feature(naked_functions)] #![feature(test)] #![no_std] #![no_main] #[allow(unused_attributes)] #[link_args = "-nostartfiles"] extern "C" {} extern crate rlibc; use core::convert::TryInto; use core::hint::{black_box, spin_loop, unreachable_unchecked}; use core::panic::PanicInfo; use core::ptr; use core::slice; use core::sync::atomic::{AtomicUsize, fence, Ordering}; use core::mem::MaybeUninit; static PRINTABLES: [u8; 95] = *b" !\"#$%&'()*+,-./0123456789:;<=>?\ @ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_\ `abcdefghijklmnopqrstuvwxyz{|}~"; const FRAMECOUNT: usize = 4; static mut FRAMES: [Frame; FRAMECOUNT] = [ unsafe { MaybeUninit::<Frame>::uninit().assume_init() }; FRAMECOUNT ]; static FRAMELENS: [AtomicUsize; FRAMECOUNT] = [ AtomicUsize::new(0); FRAMECOUNT ]; #[repr(C)] struct iovec { iov_base: *const u8, iov_len: usize } const FRAMESIZE: usize = 256; #[repr(C)] struct Frame { iovecs: [MaybeUninit<iovec>; FRAMESIZE] } #[no_mangle] #[naked] pub unsafe extern "C" fn _start() -> ! { // Escape naked without clobbering stack pointer // https://fasterthanli.me/series/making-our-own-executable-packer/part-12 asm!( "mov rdi, rsp", "call main", options(noreturn) ); } #[no_mangle] pub extern "C" fn main(stack: *const u8) -> ! { let input: &'static [u8] = unsafe { let arg1 = *stack.offset(16).cast(); slice::from_raw_parts(arg1, cstr_strlen_cheat(arg1)) }; unsafe { spawn_printer(); } let mut frame_i = 0; let mut frame_j = 0; let mut frame = unsafe { get_frame(0) }; macro_rules! main_write { (@iovec $iov: expr) => {{ frame.iovecs[frame_j] = MaybeUninit::new($iov); frame_j += 1; if frame_j > FRAMESIZE { unsafe { unreachable_unchecked(); } } if frame_j == FRAMESIZE { unsafe { write_frame(frame, frame_i, FRAMESIZE); } frame_j = 0; frame_i += 1; frame_i %= FRAMECOUNT; frame = unsafe { get_frame(frame_i) }; } }}; (@single $slice: expr) => {{ main_write!( @iovec iovec { iov_base: &$slice[0], iov_len: $slice.len() } ); }}; ($($x: expr),*) => {{ $( main_write!(@single $x); )* }}; } macro_rules! main_writeln { ($($x: tt)*) => {{ main_write!($($x)*); main_write!(b"\n"); }}; } /////////// // No-op /// // No-op // Insert // // I. // .I. // .I // Delete ///////// // Predel // Delete // Appdel // Insert insert // // II. // I.I. // I.I // .II. // .I.I. // Insert append // Append append // Insert delete ////// (also includes Substitute) // Prepend predel // Prepend delete // I.D // Insert predel // Insert delete // .I.D. // .S. // .D.I. // Insert appdel // D.I // Append delete // .S // Insert substitute ////// // IS. // I.S. // Prepend substappend // S.I. // .SI. // .S.I. // Insert substitute // .I.S // Subsprepend append // .S.I // .SI // Substitute substitute // // SS. // .SS. // .SS // S.S // S.S. // .S.S. // .S.S // Delete delete ////////// // Del2 XX. // Del2 .XX. // Del2 .XX // Del2 X.X // Del2 X.X. // Del2 .X.X. // Del2 .X.X // Delete substitute // // DS. // .DS. // .DS // D.S // S.D // D.S. // S.D. // .D.S. // .S.D. // .D.S // .S.D /////////////////////// let len = input.len(); main_writeln!(input); // No-op main_writeln!(input[1..]); // Predel main_writeln!(input[2..]); // Del2 XX. main_writeln!(input[.. len-1]); // Appdel main_writeln!(input[.. len-2]); // Del2 .XX main_writeln!(input[1 .. len-1]); // Del2 X.X for i in 1 .. len-1 { main_writeln!(input[..i], input[i + 1..]); // Delete } for i in 1 .. len-2 { main_writeln!(input[..i], input[i+2 ..]); // Del2 .XX. main_writeln!(input[1 .. i+1], input[i+2 ..]); // Del2 X.X. main_writeln!(input[..i], input[i+1 .. len-1]); // Del2 .X.X for j in i+2 .. len-1 { // Del2 .X.X. main_writeln!(input[..i], input[i+1 .. j], input[j+1 ..]); } } for ai in 0..PRINTABLES.len() { let a = &PRINTABLES[ai .. ai+1]; main_writeln!(a, input); // I. main_writeln!(input, a); // .I for i in 1..len { main_writeln!(input[..i], a, input[i..]); // .I. } for bi in 0..PRINTABLES.len() { let b = &PRINTABLES[bi..bi + 1]; main_writeln!(a, b, input); // II. main_writeln!(a, b, input[1..]); // IS. main_writeln!(a, b, input[2..]); // SS. main_writeln!(a, input, b); // I.I main_writeln!(a, input[.. len-1], b); // Prepend substappend main_writeln!(a, input[1 ..], b); // Subsprepend append main_writeln!(a, input[1 .. len-1], b); // S.S main_writeln!(input, a, b); // Append append main_writeln!(input[.. len-1], a, b); // .SI main_writeln!(input[.. len-2], a, b); // .SS for i in 1..len { main_writeln!(a, input[..i], b, input[i..]); // I.I. main_writeln!(input[..i], a, input[i..], b); // Insert append main_writeln!(input[..i], a, b, input[i..]); // .II. } for i in 1 .. len-1 { main_writeln!(a, input[..i], b, input[i+1 ..]); // I.S. main_writeln!(a, input[1 .. i+1], b, input[i+1 ..]); // S.I. main_writeln!(input[..i], a, input[i .. len-1], b); // .I.S main_writeln!(input[..i], a, b, input[i+1..]); // .SI. for j in i+1 .. len { // .I.I. main_writeln!(input[..i], a, input[i..j], b, input[j..]); } for j in i+2 .. len { // .S.I. main_writeln!( input[..i], a, input[i+1 .. j], b, input[j..] ); } for j in i+2 .. len-1 { // .S.S. main_writeln!( input[..i], a, input[i+1 .. j], b, input[j+1 ..] ); } for j in 1..i { // Insert substitute main_writeln!(input[..j], a, input[j..i], b, input[i+1..]); } main_writeln!(input[..i], a, input[i+1 ..], b); // .S.I } for i in 1 .. len-2 { main_writeln!(input[..i], a, b, input[i+2 ..]); // .SS. main_writeln!(a, input[1 .. i+1], b, input[i+2 ..]); // S.S. main_writeln!(input[..i], a, input[i+1 .. len-1], b); // .S.S } } main_writeln!(a, input[1..]); // Prepend predel main_writeln!(a, input[2..]); // DS. main_writeln!(a, input[.. len-1]); // I.D main_writeln!(a, input[1 .. len-1]); // S.D main_writeln!(input[1..], a); // D.I main_writeln!(input[1 .. len-1], a); // D.S main_writeln!(input[.. len-1], a); // .S main_writeln!(input[.. len-2], a); // .DS for i in 1..input.len() - 1 { main_writeln!(a, input[..i], input[i+1 ..]); // Prepend delete main_writeln!(input[..i], input[i+1 ..], a); // Append delete main_writeln!(input[1 .. i+1], a, input[i+1 ..]); // Insert predel main_writeln!(input[..i], a, input[i .. len-1]); // Insert appdel main_writeln!(input[..i], a, input[i+1 ..]); // .S. for j in 1..i { // .I.D. main_writeln!(input[..j], a, input[j..i], input[i+1 ..]); } for j in i+2..len { // .D.I. main_writeln!(input[..i], input[i+1 .. j], a, input[j..]); } } for i in 1 .. len-2 { main_writeln!(input[..i], a, input[i+2 ..]); // .DS. main_writeln!(input[1 .. i+1], a, input[i+2 ..]); // D.S. main_writeln!(a, input[1 .. i+1], input[i+2 ..]); // S.D. main_writeln!(input[..i], input[i+1 .. len-1], a); // .D.S main_writeln!(input[..i], a, input[i+1 .. len-1]); // .S.D for j in i+2 .. len-1 { // .D.S. main_writeln!(input[..i], input[i+1 .. j], a, input[j+1 ..]); // .S.D. main_writeln!(input[..i], a, input[i+1 .. j], input[j+1 ..]); } } } unsafe { write_frame(frame, frame_i, frame_j); } while FRAMELENS[frame_i].load(Ordering::SeqCst) > 0 { sched_yield(); } unsafe { exit_group(0); } } /// strlen, if the string's length is >= 10 and <= 16. #[inline] unsafe fn cstr_strlen_cheat(ptr: *const u8) -> usize { for i in 10..=16 { if *ptr.offset(i) == 0 { match i.try_into() { Ok::<usize, _>(i) => return i, Err(_) => unreachable_unchecked() } } } unreachable_unchecked(); } /// Gets a frame for writing, assuming nobody else has it. #[inline] unsafe fn get_frame(i: usize) -> &'static mut Frame { loop { let count = FRAMELENS[i].load(Ordering::SeqCst); if count == 0 { break; } sched_yield(); } &mut FRAMES[i] } #[inline] unsafe fn write_frame(_frame: &'static mut Frame, i: usize, count: usize) { FRAMELENS[i].store(count, Ordering::SeqCst); } #[inline(never)] // for correctness unsafe extern "C" fn spawn_printer() { let stack_pointer: *const u8; asm!( "mov {0}, rsp", out(reg) stack_pointer ); let new_stack = stack_pointer.offset(-0x1000); let spawn_addr = (new_stack as *mut (extern "C" fn() -> !)).offset(1); ptr::write(spawn_addr, printer); clone(new_stack) } extern "C" fn printer() -> ! { loop { for i in 0..FRAMECOUNT { let mut count; loop { count = FRAMELENS[i].load(Ordering::SeqCst); if count > 0 { break; } // sched_yield(); } fence(Ordering::SeqCst); unsafe { writev((&FRAMES[i].iovecs[0]).as_ptr().cast(), count); } FRAMELENS[i].store(0, Ordering::SeqCst); } } } // https://thevivekpandey.github.io/posts/2017-09-25-linux-system-calls.html #[inline] unsafe fn writev(iovecs: *const iovec, count: usize) { asm!( "syscall", in("rax") 20, in("rdi") 1, in("rsi") iovecs, in("rdx") count, options(nostack) ); } #[inline] fn exit(code: i32) -> ! { unsafe { asm!( "syscall", in("rax") 60, in("rdi") code, options(nostack, noreturn) ); } } #[inline] unsafe fn exit_group(code: i32) -> ! { asm!( "syscall", in("rax") 231, in("rdi") code, options(nostack, noreturn) ); } #[inline] unsafe fn just_exit() -> ! { asm!( "syscall", in("rax") 231, options(nostack, noreturn) ) } #[inline] fn sched_yield() { unsafe { asm!( "syscall", in("rax") 24, options(nostack) ) } } /// Wait for signal. #[inline] fn pause() { unsafe { asm!( "syscall", in("rax") 34, options(nostack) ) } } #[inline(always)] // for correctness unsafe fn clone(new_stack: *const u8) { const CLONE_FILES: u64 = 0x400; // Keep stdout as fd 1 const CLONE_FS: u64 = 0x200; const CLONE_IO: u64 = 0x80000000; // I/O scheduling efficiency const CLONE_PARENT: u64 = 0x8000; const CLONE_SIGHAND: u64 = 0x800; const CLONE_THREAD: u64 = 0x10000; // Same thread group const CLONE_VM: u64 = 0x100; // Same memory map const flags: u64 = CLONE_FILES | CLONE_IO | CLONE_VM | CLONE_THREAD | CLONE_FS | CLONE_PARENT | CLONE_SIGHAND; asm!( "syscall", in("rax") 56, in("rdi") flags, in("rsi") new_stack, options(nostack) ); return; } #[panic_handler] fn panic(_info: &PanicInfo) -> ! { unsafe { if cfg!(debug_assertions) { // just_exit(); } // unreachable_unchecked(); asm!( "ud2", options(nostack, noreturn) ) } } 

This is cleaner code; I'm making a better version, hopefully less segfaulty in release mode. I also haven't tweaked the FRAMECOUNT and FRAMESIZE parameters for optimal speed.