Page 1 of 1
Super Brainfuck
Posted: Mon Jun 20, 2016 6:03 am
by Hippo
I have a question to solvers:
Did you codded compiler or interpretter?
My codes so far are compilers. I still don't know how the fast version would look like ...
Brainfuck challenges
Posted: Wed Jun 22, 2016 12:00 pm
by a.goth
Did I miss something? How are the Brainfuck challenges solved with a compiler?
Re: Brainfuck challenges
Posted: Wed Jun 22, 2016 4:40 pm
by Hippo
a.goth wrote:Did I miss something? How are the Brainfuck challenges solved with a compiler?
My (single threaded) code used w instruction extensively (compiled to shvm) and than after end of bf code was found it went to the "entry point of the compiled code".
BTW: Now I am working on "Accelerator" ... it would be more interpretter than compiller (I am not sure there would be compiller portion at the end).
My code transformation so far reduced the code set to +()>().,[], I am going to get rid of >() somehow, and I am planning to remove [] cycles (at least easy ones ... and quiestion is what are the easy ones).
Symplifying cycles depending on inputs is almost nonsense, but even nested cycles could quickly become unmanageable. So I am ready to resign optimisation at some complexity level ... testing cases gave the bounds where to stop optimisation.
So maybe cycles including inputs would be compiled at the end. ... I am afraid that optimisation overhead could be too huge to be paid off at small test examples the challenge provides.
Brainfuck challenges
Posted: Thu Jun 23, 2016 7:43 pm
by a.goth
Oh yeah, now that you mention it. Initially, I had also considered to solve the Brainfuck challenges that way. The idea was to translate Brainfuck programs into SuperHack using the following substitutions:
Code: Select all
Brainfuck command | SuperHack equivalent
------------------+---------------------
(Program Start) | %0
(Program End) | !
> | }
< | {
+ | 1+
- | 1-
. | xp
, | 1[,
Finally, each [] loop can be coded idiomatically, using s\/?x commands.
Consider the following trivial Brainfuck program for a better understanding:
This is translated into the following SuperHack program:
Code: Select all
/x?\ \ /x?\ \
%0 1+ / s\ }1[, x?\s\ {1- / s\ 1+xp{1- x?\s\ !
\ / \ /
I found it very inconvenient to translate nested loops in this manner and I feared that the compilation could violate the cycle limit. That is why I had rejected this idea and instead began an interpreter. Maybe I revive the idea, but I would be curious to see the source code of your compiler. In fact, I am pretty impressed that your compiler uses less than 10,000 cycles.
Furthermore, I believe that you need a small, fast interpreter to solve challenge 'Super Fast Brainfuck'. Therefore, I plan to solve challenge 'Tiny Brainfuck' first and then start to optimize the solution. Maybe you want to discuss this challenge with me? Consequently, I have not thought much about optimization. I am sorry!
Posted: Thu Jun 23, 2016 8:53 pm
by Hippo
Unfortunately I have only solutions not longer than 330 instructions so I should publish it in another thread, but You have already solved it so we can continue talk there.
Essentially your proposal is fine, {} is better than mine solution, +, is faster than 1[,.
My code is almost unraedable to me now.
No, I don't think I need help here, I just point to an interesting Challenge.
Drop top of stack
Posted: Mon Jun 27, 2016 2:40 pm
by a.goth
That is right, if the program starts with %00 instead of %0, then you can replace 1[, by +,. Or you can use a different arithmetic operation. Nice trick.
I will post my solution of challenge 'Small Brainfuck' within the next few days in the appropriate thread.
And yes, the SuperHack challenges are really interesting.