Brainfuck Sorting

Question

Write a program in brainfuck that accepts input of 4 ASCII characters as numbers (from 32 to 126) and outputs the numbers or ASCII equivalent sorted in ascending order.

Requirements: Your program should prompt the user for 4 characters that will be sorted by their ASCII value. All the inputs will be distinct. Any sorting algorithm can be used. Every cell is one byte, and the shortest code wins. If there is a tie, the code that uses the least memory cells wins.

Example input:

(i"G

Example output:

"(Gi

Helpful links: How to compare 2 numbers with brainfuck

If you have any questions please ask them in the comments.

I tried to write a program that solves this problem. It works, but it's so inefficient and lenghty (500+) that I don't want to post it here. If you bothered to go through the pain I did, you'll get a +1 from me.

Answer 1

33 code bytes, 2n+3=11 n+4=8 memory cells

Edited: I can improve memory usage by keeping the count in only one cell.

>,[>,]+[<[-<]>[>]>[<-[>]<.>>]<<+]

EOF is 0, 8 bit wrapping memory (0+256=0)

How it works

• Read all numbers
• Decrement each number, keep count of how many times you do this.
• When something hits zero, print the count
• Repeat until count rolls over.

Details

Memory: 0(start padding),[input],...,count,0(padding),0 (more padding)

> (start padding)
,[>,] read input
+ count=1
[ while count !=0
    <[-<] decrement all inputs
    >[>] go to an input that was just decremented to zero, or padding
    > point to next input or more padding
    [ if not padding
         <- change the 0 to 255 so it doesn't stop the next decrement pass
         [>]<. point to and print count
         >> point to more padding
    ]
    <<+ increment count
]

The old way

>,[->+>,]<[[+<-<]>[>>]>[.[>]>]<<]

Memory plan:

0(padding),[input,count],[input,count],...,[0,0](dummy input & count)

Commented code:

> get some elbow room
,[->+>,] read each number & do an initial count/decrement pass so count is not 0
< point at last count
[ while count !=0 (didn't roll over)
    [+<-<] decrement each number and increment each count
    > point at first input
    [>>] go to the first 0-ed input (probably the dummy input) 
    > point at count or dummy count
    [ if not the dummy count
        . print it
        [>]> go to the dummy count (no other inputs will be 0 because they are all unique)
    ]
    << point at last count
]

Answer 2

94 bytes code, 2n+5 = 13 bytes memory

>>,[>>+[->>+<<],]>>[<<<<<<[>>[<+<-[>>>]>>[-[-<<+>>]+>>>]<<<-]<[-<+>>+<]<<<]>>[>>]>>-]<<<<[.<<]

EOF is zero.

Example:

$ echo -n '(i"G'|beef sort.bf ;echo
"(Gi

Answer 3

90 63 bytes code, 769 513 bytes memory

>>,[-[[>>]+[<<]>>-]>>[>>]<+<[-<<],]+[[>>]+<[<[<<]>>.>]<[<<]>>+]

This works much like the old way, but doesn't initialize memory with numbers. Instead, it keeps track of which location it is checking and prints that number.

The old way

>>>+[[->+>>+<<<]>[-<+>]>>+]<<<[<<<]>>,[[->>[>>>]+[<<<]>]>>[>>>]<<+<[-<<<]>,]>[>>[<<.>>-]>]

EOF is 0, 255+1 = 0

How it works

Step 1: Prep the memory to look like: 0,0,0,[1,0,0],[2,0,0],...,[255,0,0],0

>>>+[[->+>>+<<<]>[-<+>]>>+]<<<[<<<]

Step 2: Read the input and increment memory at (3+input*3+2). Reading space (32) results in 0,0,0,[1,0,0],...,[32,0,1],...

>>,[[->>[>>>]+[<<<]>]>>[>>>]<<+<[-<<<]>,]

Step 3: Read through the memory and output any number that has a non-zero value two cells to the right of it. Stop after 255. This prints out the characters in ascending order.

>[>>[<<.>>-]>]