Subscribe to The Madman Scribblings        RSS Feed
-----

BrainF*ck Number Challenge.

Icon 4 Comments
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
  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

AdamSpeight2008 Icon

08 November 2013 - 09:55 PM
Added another Simplification, thanks to the bounded nature of the cell values.
[+] would be an infinite loop.

      If SimpleInfiniteLoopRemoval AndAlso  Program.Contains("[+]") Then Debug.Print("Simple Infinite Loop ([+]) Removal") : Program=Program.Replace("[+]", "") : Simplifications += 1


0

ishkabible Icon

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.
0

ishkabible Icon

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.
0

ishkabible Icon

14 November 2013 - 02:01 PM
here it is

This can produce expressions that are as good as anything I can do by hand.
0
Page 1 of 1