5
\$\begingroup\$

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.

\$\endgroup\$
  • 11
    \$\begingroup\$ Meh, language-specific challenge. I can see how this would be a challenge in Brainfuck and fairly trivial in "normal" languages, but still... \$\endgroup\$ – Martin Ender Jul 5 '14 at 20:50
  • \$\begingroup\$ How about allowing more esoteric languages? \$\endgroup\$ – Knerd Jul 10 '14 at 17:27
  • \$\begingroup\$ @Knerd I'll allow it, but it's not the main focus of this question. \$\endgroup\$ – qwr Jul 10 '14 at 19:44
  • \$\begingroup\$ @qwr then you should edit your question :) \$\endgroup\$ – Knerd Jul 10 '14 at 20:36
  • \$\begingroup\$ I get why this should be language-specific. Sorting in BF is very different from normal languages. \$\endgroup\$ – MilkyWay90 Jun 15 at 17:02
18
+100
\$\begingroup\$

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
]
\$\endgroup\$
  • \$\begingroup\$ Huh. That's smart. +1 \$\endgroup\$ – seequ Jul 10 '14 at 15:47
  • 2
    \$\begingroup\$ This answer is incredible. \$\endgroup\$ – qwr Jul 14 '14 at 4:32
6
\$\begingroup\$

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

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

EOF is zero.

Example:

$ echo -n '(i"G'|beef sort.bf ;echo
"(Gi
\$\endgroup\$
  • \$\begingroup\$ What sort did you implement? Bubble sort, I guess? \$\endgroup\$ – seequ Jul 5 '14 at 22:47
  • \$\begingroup\$ @TheRare Yes. Bubble sort is the easiest to implement with BrainFuck. \$\endgroup\$ – jimmy23013 Jul 5 '14 at 22:49
  • \$\begingroup\$ @TheRare Maybe I'm wrong. Counting sort can be easier. \$\endgroup\$ – jimmy23013 Jul 5 '14 at 23:00
6
\$\begingroup\$

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.

>[>>[<<.>>-]>]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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