GolfScript, 296 + 3628 = 3924 bytes
12.?:&{{}if}:i{&6base:c[0:x:^:h]25:e*:|"(":a")":b{["x(:x|,,?):e".a/b*"|x=(256%|x<\\|x)>++:|".a/b*"{1{c^):^=.4={;)}{5={b}i}if.c,,^)?1+:e*}do"."^)c,-"\"b"/a*+"!{e):e}i^(:^}i"+"|x="@b/a*"b"/b*"}i"++]c^==~];^):^c,=!6.?,h):h?)e*:e*}do|$)\{+}*!*.e*{c':c'@+~}i&(:&}do];255,{n'c'@)+~{'<>-+[]'1/\=}/}/"":n
Try it online!
The extra byte in the output is a newline for the code for 0, removing it requires more than one byte.
This program passes through 8 916 100 448 256 BF codes, tests if it produces only one number and stores the code. In the end the shortest code for each number is printed. This is not effitient at all, it would take millions of years to end, the estimated number of bytes in the solution assumes the shortest codes are all listed in this esolang page. This doesn't reach the memory limit or any other errors I know, it is just very slow.
12.?:& # Assign 12^12 = 8916100448256 to &, this represents the current BF code
{{}if}:i # This will be used to go from {code}{}if to {code}i
{ ... }do # Main loop, will be explained later
]; # Clean the stack
255,{ ... }/ # Go through every number
"":n # This removes the automatic newline that is printed
What is inside the 255,{ ... }/:
n # Newline
'c'@+ # For the N-th number push 'cN'
~ # Execute the string, this will push the value stored in the variable, it will be an array with the shortest code for N
{'<>-+[]'1/\=}/ # Translate the array to a BF code
Main loop:
In the main loop there is a BF interpreter that can avoid errors. There are 3 ways something can go wrong:
1 It doesn't halt. This can be avoided by putting an operation limit. Here the limit is 14889 for the numbers 78 and 178, this means that if the code doesn't halt in 14889 operations, it is not one of the optimal codes.
2 Unpaired [ ]. We test if the instruction pointer left the code while searching for the pair. If it isn't necessary to look for the pair (Eg >>]+-), it means that that instruction is not necessary and the code will be replaced by a better one later.
3 The data pointer leaves the tape. We test if it left the tape using the same strategy used above. The tape here is only 25 bytes long, if the code needs more, it means it isn't optimal. The numbers 78 and 178 need 24 cells.
This interpreter doesn't have the , and . operations, so every BF code can be represented by a base 6 number. The problem is that a number can't start with 0, but here it isn't a problem because 0 represents <, which doesn't do anything at the start.
&6base:c # Convert & to base 6 and store the resulting array in c.
[0:x:^:h] # Push [0] and assign 0 to x, ^ and h. x= data pointer ^= instruction pointer h= operation counter
25:e # Assign 25 to e, this will be the error variable, if it is 0 something went wrong
*:| # Multiply [0] and 25 to get the tape called |
"(":a")":b # Assign "(" to a and ")" to b
{[ # Start a loop and an array
In this array we will have the 6 functions written as strings for easier manipulation:
op string
0 < x(:x|,,?):e
x(:x # Decrement x
|,,?):e # Test if the result is within the tape
1 > x):x|,,?):e # Same thing as before but with ")" instead of "("
2 - |x=(256%|x<\\|x)>++:|
|x= # Get the value from the tape
(256% # Decrement mod 256
|x<\\|x)>++:| # Replace the old value in the array, the \\ is a \ but inside a string
3 + |x=)256%|x<\\|x)>++:| # Same thing as before but with ")" instead of "("
4 [ ^)c,-{1{c^):^=.4={;)}{5={(}i}if.c,,^)?1+:e*}do!{e):e}i^(:^}i
^)c,-{ }i # If it isn't the last byte of the code
1{ .c,,^)?1+:e*}do # While the pair has not been found and the next byte to be tested is within the code
c^):^= # Get next byte
.4= if # Is it a [ ?
{;)} # Increment the counter
{5={(}i} # Decrement the counter if it is a ]
!{e):e}i # If the code ends with ] it will be counted as an error and this part solves the problem
^(:^ # Move the instruction pointer to the left, later it will be moved to the right and the ] will be read
5 ] |x={1{c^(:^=.4={;(}{5={)}i}if.c,,^(?1+:e*}do}i
|x={ }i # If the current cell is not 0
1{c^(:^=.4={;(}{5={)}i}if.c,,^(?1+:e*}do # Same thing as before but with ( and ) swapped
[ always jumps to the ] and there it decides if the things inside should be executed.
This array is very repetitive, so we replace "x):x|,,?):e" by .a/b*, this copies the code for < and replaces the ( by ). The code for + is also replaced by .a/b*, but the code for ] is a bit more complex. The code for [ and ] will be replaced by:
"{1{c^):^=.4={;)}{5={b}i}if.c,,^)?1+:e*}do"."^)c,-"\"b"/a*+"!{e):e}i^(:^}i"+"|x="@b/a*"b"/b*"}i"++
"{1{c^):^=.4={;)}{5={b}i}if.c,,^)?1+:e*}do" # Repeated part
."^)c,-"\ # Make a copy of it and push ^)c,- under that long string
"b"/a*+ # Replace the b by ( and concatenate the result with the ^)c,-
"!{e):e}i^(:^}i"+ # Add this to the end of the string
"|x="@ # Push |x= and get that original string
b/a*"b"/b* # Replace the ) by ( and the b by )
"}i"++ # Push }i and concatenate the 3 parts
Now comes the part that executes these functions, remember that this array was created inside the loop, this means it will be recreated every time it reads a byte from the code.
] # End the array
c^= # Get current instruction
=~ # Get the function for it and execute it
]; # Clean the stack, this replaces the ; that would have to be in every function
^):^ # Go to next instruction
c,=! # Is it NOT the last instruction?
6.?,h):h?) # Increment h and test if it is within the operation limit. It actually uses 6^6=46656 instead of 14889 to save 2 bytes.
e*:e # Updates e
*}do # Repeats everything if there were no errors
Now we just have to test if the output is valid and store it if it is.
|$ # Sort the tape
) # Separate the last number
\{+}* # Add all other numbers in the array
! # Is the sum 0?
* # This will be the only non-zero cell or 0 if the output is invalid
.e* # Change it to 0 if there was an error
{ }i # If it isn't 0 it is the code for some number, let this number be N
c # Push the code
':c'@+~ # Store it in the variable cN
&(:&}do # Go to the next code and repeat untill it gets to 0
The codes are tested in decreasing order, that way the shortest solutions will automatically replace the longer ones. The longest code is number 6774727080140 and that's why we started at such a big number.
Here are some versions of the code using other constants so we can see the output (only the found codes are outputted):
Starting at 216, this tests every 3 byte code.
From 6774727080145 to 6774727080135, includes the solution for 117.
30 codes starting at a random number
