BrainF*ck Number Challenge.
This stems from ishkabible who brought up an interesting challenge and an extremely difficult one at.
(We're talking about the grey-beards stroking their beards hard!)
Computer Science Thread:- Minimal Expression For A Number In-Brainf*ck
The basic premise is what is the minimal length of BrainF*ck code need to produce a specific value in the range 0 to 255. Cell Values are bounded to 0 and 255 and don't wraparound.
The instruction of ., aka Input and Output are not used in this challenge, so only the following instruction can be use. +-<>[]
Examples
Note: These haven't be proven to be optimal solutions.
Loop Penatly Cost?
From the chart abouve you can see that using a loop isn't beneficial till n=15.
So what it the minimal cost incurred by using a loop?
[->++<]
That would be 7c which produce add two times the value in the current cell to the value in the cell to the right. Also clear the current cell to Zero.
My Conjecture
A quick and simple look the bounds produces.
I conjecture that the upper bound for any of the code is in the range 32 to 64, but strong suspect it to be nearer 28 to 32.
Valid BrainF*ck?
Is there a simple way to check that a BF program is valid by having balanced brackets?
Yep. '[' => +1 , ']' => -1
If any point the value is less than negative, or the resulting value isn't zero then it's invalid.
Simplify
I thought I'd start by writing function to simplify a valid BF program by removing redundant code from the program. This isn't producing optimal code as it doesn't rewrite section of the program with short versions.
Finding The Matching Bracket Position
A fairly complex recursive function to locate the position of the matching brace. (assumes balanced braces).
What's Next?
Next task would be to design and write a program that can generate valid BrainF*ck programs, using the reduced instruction set. Then evaluate them.
I have a few ideas to try out, but do you have any thoughts on potential routes to take?
This stems from ishkabible who brought up an interesting challenge and an extremely difficult one at.
(We're talking about the grey-beards stroking their beards hard!)
Computer Science Thread:- Minimal Expression For A Number In-Brainf*ck
The basic premise is what is the minimal length of BrainF*ck code need to produce a specific value in the range 0 to 255. Cell Values are bounded to 0 and 255 and don't wraparound.
The instruction of ., aka Input and Output are not used in this challenge, so only the following instruction can be use. +-<>[]
Examples
n c 0 3 [-] or empty 1 1 + 2 2 ++ 3 3 +++ 4 4 ++++ 5 5 +++++ 6 6 ++++++ 7 7 +++++++ 8 8 ++++++++ 9 9 +++++++++ 10 10 ++++++++++ 11 11 +++++++++++ 12 12 ++++++++++++ 13 13 +++++++++++++ 14 14 ++++++++++++++ or +++++++[>++<-] 15 12 ++++[>+++<-] First one to benefit from a loop. .... 253 30 ++++++[>++++++<-]>[-<+++++++>]+ (6*6*7)+1 highest prime below 255 254 31 ++++++[>++++++<-]>[-<+++++++>]++ 255 32 ++++++[>++++++<-]>[-<+++++++>]+++
Note: These haven't be proven to be optimal solutions.
Loop Penatly Cost?
From the chart abouve you can see that using a loop isn't beneficial till n=15.
So what it the minimal cost incurred by using a loop?
[->++<]
That would be 7c which produce add two times the value in the current cell to the value in the cell to the right. Also clear the current cell to Zero.
My Conjecture
A quick and simple look the bounds produces.
Bounds ------ Upper = O(n) ' eg just use addition Lower = O(1) ' 0 and 1 (which is still O(n)
I conjecture that the upper bound for any of the code is in the range 32 to 64, but strong suspect it to be nearer 28 to 32.
Valid BrainF*ck?
Is there a simple way to check that a BF program is valid by having balanced brackets?
Yep. '[' => +1 , ']' => -1
If any point the value is less than negative, or the resulting value isn't zero then it's invalid.
Dim Valid = Program.Aggregate(Of Integer)(0, Function(depth, pc) If(depth < 0, depth, If(pc = "["c, depth + 1, If(pc = "]"c, depth - 1, depth)))) = 0
Simplify
I thought I'd start by writing function to simplify a valid BF program by removing redundant code from the program. This isn't producing optimal code as it doesn't rewrite section of the program with short versions.
Public Function Simplify(Program As String, Optional SimpleInfiniteLoopRemoval As Boolean = True, Optional TrailingLoopRemoval As Boolean = True) As String Dim Simplifications = 0 Do Debug.Indent Simplifications = 0 ' Loop at the stert. If Program(0)="[" Then Debug.Print("Starts With A Loop Removal") Dim m =MatchBracketPos(Program,0) Program=Program.Remove(0,m+1) Simplifications+=1 End If ' Nutralising calculations If Program.Contains("+-") Then Debug.Print("PlusMinus Removal") : Program=Program.Replace("+-", "") : Simplifications += 1 If Program.Contains("-+") Then Debug.Print("MinusPlus Removal") : Program=Program.Replace("-+", "") : Simplifications += 1 ' Nutralising position changes If Program.Contains("<>") Then Debug.Print("LeftRight Removal") : Program=Program.Replace("<>", "") : Simplifications += 1 If Program.Contains("><") Then Debug.Print("RightLeft Removal") : Program=Program.Replace("><", "") : Simplifications += 1 ' Simple Infinite Loop Removal If SimpleInfiniteLoopRemoval AndAlso Program.Contains("[]") Then Debug.Print("Simple Infinite Loop Removal") : Program=Program.Replace("[]", "") : Simplifications += 1 ' Loop straight after another won't be entered. If TrailingLoopRemoval AndAlso Program.Contains("][") Then Debug.Print("Trailing Loop Removal") Dim s = Program.IndexOf("][") + 1 Program=Program.Remove(s,(MatchBracketPos(Program,s)-s)+1) Simplifications+=1 End If Debug.Unindent If Simplifications>0 Then Debug.Print("{0} Simplifications ",Simplifications) ' Continue doing simplification until none are possible Loop Until Simplifications = 0 Return Program End Function
Finding The Matching Bracket Position
A fairly complex recursive function to locate the position of the matching brace. (assumes balanced braces).
Public Function MatchBracketPos(p As String, s As Integer) As Integer Dim JMP As Func(Of Integer, Integer, Char, Char, Integer, Integer) = Function(PCx As Integer, NStep As Integer, PushC As Char, PullC As Char, Depth As Integer) If P(PCx) = PushC Then Return JMP(PCx + NStep, NStep, PushC, PullC, Depth + 1) If P(PCx) = PullC Then If Depth = 1 Then Return PCx Return JMP(PCx + NStep, NStep, PushC, PullC, Depth - 1) End if return JMP(PCx + NStep, NStep, PushC, PullC, Depth) End Function Return JMP(s,+1,"["c,"]"c,0) End Function
What's Next?
Next task would be to design and write a program that can generate valid BrainF*ck programs, using the reduced instruction set. Then evaluate them.
I have a few ideas to try out, but do you have any thoughts on potential routes to take?
4 Comments On This Entry
Page 1 of 1
ishkabible
11 November 2013 - 09:24 AM
The actual setup I've been working with is a little different from yours. I've been using bi-directionaly infinite memory (using infinite list in haskell) and big integers (that is range of -inf to +inf). That is short of exhausting memory You can't actually run into an error.
ishkabible
14 November 2013 - 01:33 PM
Ok here is the idea I have been working on and I've gotten decent results.
You enumerate all the ways a number can be expressed using multiplication, constants, and incrementation. You take that and you score them. I calculate that a increment is 1 + the cost of what it is you increment. Multiplication is 6 + the cost of the 2 arguments. A constant is it's own score. You can then translate this expression into brainfuck pretty easily. My factorization method wasn't giving all the factors but even with what it did give I got 35c on 255 and 33c on 251 so it's pretty competitive with humans. I think once I get the factors right it will be near perfect. So there is my algorithm; it seems to work pretty well. It's rather in efficient for numbers larger than 300 or so.
You enumerate all the ways a number can be expressed using multiplication, constants, and incrementation. You take that and you score them. I calculate that a increment is 1 + the cost of what it is you increment. Multiplication is 6 + the cost of the 2 arguments. A constant is it's own score. You can then translate this expression into brainfuck pretty easily. My factorization method wasn't giving all the factors but even with what it did give I got 35c on 255 and 33c on 251 so it's pretty competitive with humans. I think once I get the factors right it will be near perfect. So there is my algorithm; it seems to work pretty well. It's rather in efficient for numbers larger than 300 or so.
ishkabible
14 November 2013 - 02:01 PM
Page 1 of 1
Search My Blog
Recent Entries
Recent Comments
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
← March 2017 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- .net
- .net4
- bf
- brainfuck
- Codeplex
- Coding
- custom Control
- custom controls
- DIC CodeAID VS Gallery
- Dice
- Die
- DLL
- Englishify
- Extension
- Extension Method
- ExtMethods
- F#
- Functional
- Functional Programming
- Graph
- Graphs
- Language Intergrated Query.
- Library
- LINQ
- LINQ Codes
- LISP interpreter
- Macro
- My Games
- Nemerle.
- net
- podcast
- Project
- Project Cider
- RadixSort Generics (Of T)
- restricted textbox
- Rolling
- rss
- rss feed
- Scribblings
- shadowtext
- Tips
- Transparent Textbox
- vb
- vb.net
- VB.net +LINQ Extension Method
- vb.net 1-Liners
- vb.net visual basic vs2010 .net4
- vs2010
- Weird
- XM
- xml
- XML Literals