Minimal expression for a number in brainf***

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 4064 Views - Last Post: 14 November 2013 - 05:52 PM

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Minimal expression for a number in brainf***

Posted 04 November 2013 - 04:03 PM

So I had a thought today but the problem appears to be a more complex that I had initially thought. Would it be possible to construct an algorithm that when given a number N computed a minimal expression in brainfuck that would leave the memory pointer on a cell that had value N? If so what would the algorithm look like? What would it's running time be?

note that when I say "a minimal expression" I mean an expression with a less than or equal number of characters to all other expressions that meat the given criteria.

if we call this function F then some base cases are known

F(0) = ""
F(1) = "+"
F(2) = "++"
F(3) = "+++"
...
but as you get to higher characters smaller expressions start appearing than just a string of '+'s

for instance

"++++++[>+++++<-]>+" is much smaller than 31 characters but never the less computes 31 (I *think* this is a minimal expression for 31 but am unsure)
the above expression corresponds to 6 * 5 + 1 and it seems pretty minimal to me. For numbers of the form X*Y where X and Y are very close you get pretty good results with this. Numbers close to such numbers you also get pretty good results. For larger numbers nesting this method might be in order. This would lead to a decent heuristic but I see no obvious reason why such a heuristic would lead to ideal results.

A more complex problem would be the minimal expression which would print a desired string but that is much harder obviously.

Any thoughts?

This post has been edited by macosxnerd101: 05 November 2013 - 03:37 PM
Reason for edit:: Renamed title


Is This A Good Question/Topic? 0
  • +

Replies To: Minimal expression for a number in brainf***

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2511
  • View blog
  • Posts: 3,983
  • Joined: 21-June 11

Re: Minimal expression for a number in brainf***

Posted 04 November 2013 - 04:24 PM

The Halting Problem can be reduced to this, so it's impossible.
Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10681
  • View blog
  • Posts: 18,290
  • Joined: 19-March 11

Re: Minimal expression for a number in brainf***

Posted 04 November 2013 - 04:45 PM

View Postsepp2k, on 04 November 2013 - 06:24 PM, said:

The Halting Problem can be reduced to this, so it's impossible.


Party pooper. :)
Was This Post Helpful? 0
  • +
  • -

#4 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Minimal expression for a number in brainf***

Posted 04 November 2013 - 05:11 PM

Would you mind elaborating how it can be reduced?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12147
  • View blog
  • Posts: 45,157
  • Joined: 27-December 08

Re: Minimal expression for a number in brainf***

Posted 05 November 2013 - 10:39 PM

Quote

(I *think* this is a minimal expression for 31 but am unsure)

You can't determine this in polynomial time. It's an exponential time, based on the number of symbols.

Quote

Would you mind elaborating how it can be reduced?

Are you familiar with a deterministic vs. non-deterministic Turing Machine? In the Non-Deterministic TM, if a string w is in L, then the NDTM will halt in O(p(|w|)) time, where p(|w|) represents a polynomial on the length of the string. If w is not in the language, the NDTM may or may not halt at all. If it does, it may not take polynomial time.

Another way to ask this- how do you determine minimality? Turing showed that on more than 4 states, the Halting cannot be decided.
Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Minimal expression for a number in brainf***

Posted 06 November 2013 - 12:43 AM

The creating of the minimal length BrainF**k code for a number would make a good challenge.

This post has been edited by AdamSpeight2008: 06 November 2013 - 12:43 AM

Was This Post Helpful? 0
  • +
  • -

#7 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Minimal expression for a number in brainf***

Posted 06 November 2013 - 10:44 AM

View PostAdamSpeight2008, on 06 November 2013 - 08:43 AM, said:

The creating of the minimal length BrainF**k code for a number would make a good challenge.


This was the initial idea but it seems too hard. I'm thinking about making it a competition or something to see who can get the best for 0 to 255.
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10681
  • View blog
  • Posts: 18,290
  • Joined: 19-March 11

Re: Minimal expression for a number in brainf***

Posted 06 November 2013 - 10:57 AM

So the challenge is to write a program that plays code golf in brainfuck?
Was This Post Helpful? 0
  • +
  • -

#9 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Minimal expression for a number in brainf***

Posted 06 November 2013 - 12:10 PM

@macosxnerd101/sepp2k: I can't seem to find the appropriate readings for this. In particular I do not see how this reduces to the halting problem. More over I don't understand how Mac's explanations of NTMs vs TMs explains how this problem can be reduced to the halting problem. I was unable to find any reading at all on Mac's last comment about minimality and the 4 states stuff. Mind providing some terms to look up/some links?

Quote

So the challenge is to write a program that plays code golf in brainfuck?

Yep! I was even going to call it meta code colf. This is where the original idea came from. I was wondering if we could write programs to preform optimal code golf and I eventually thought of this as an interesting problem to solve. I struggled to even come up with half a solution so I thought I'd come here to ask about it.

This post has been edited by ishkabible: 06 November 2013 - 12:11 PM

Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12147
  • View blog
  • Posts: 45,157
  • Joined: 27-December 08

Re: Minimal expression for a number in brainf***

Posted 06 November 2013 - 12:15 PM

You may find this thread relevant.
Was This Post Helpful? 0
  • +
  • -

#11 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: Minimal expression for a number in brainf***

Posted 06 November 2013 - 05:47 PM

Ya I still don't see a hard connection. Certainly the two tasks are related in that a "minimal" expression that meets some criteria is desired but as far as I can see the desired criteria and language are very different. Without some over arching theory that describes both I can't say I'm satisfied. It doesn't seem to be the case that any of the answers gave any evidence of the theory being applicable to this. I tried reducing this problem to the regular expressions problem but to little success.

This post has been edited by ishkabible: 06 November 2013 - 05:48 PM

Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12147
  • View blog
  • Posts: 45,157
  • Joined: 27-December 08

Re: Minimal expression for a number in brainf***

Posted 06 November 2013 - 07:47 PM

Quote

Certainly the two tasks are related in that a "minimal" expression that meets some criteria is desired but as far as I can see the desired criteria and language are very different.

The approach is the same though. A "minimal" regular expression is a simplification from an original regular expression without sacrificing meaning. The same goes with your BF string. You want to reduce the length without changing meaning (value).

Either way, the question still becomes- how do you assert (prove) an expression is minimal? This actually reduces further to the SAT (satisfiability) problem, which you can read more on here.
Was This Post Helpful? 0
  • +
  • -

#13 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Minimal expression for a number in brainf***

Posted 07 November 2013 - 05:49 PM

Exhaustive search.
Upper:= O(N) ; Just use addition.
Lower:= O(1) ; 0 and 1 


Assuming that the memory cell values are bounded to contain value 0 to 255 and don't wrap around.

The BF language can be reduced for this task to 6 characters + - < > [ ] since [ ] are matched can be reduce to only 5.

The use of the brackets has a cost of at least 7 characters.
 [->+ +<]  ; Mem[Ptr+1] = 2 * Mem[Ptr]                 (7c)
 [->+ ++<] ; Mem[Ptr+1] = 3 * Mem[Ptr]                 (8c)
 [->+ <]   ; Mem[Ptr+1] = Mem[Ptr] ; Mem[Ptr]=0; Move  (6c)



I think (not verified yet) that the first value to benefit from a reduction in code length from bracket usage is 15 ++++ +[>+ ++<- ] (13c). Yeah 14 can utilize brackets ++++[>+++<-]++ but that's 14c.

I've a strong feeling that the maximum needed for any value between 0..255 somewhere in the range [ 32c ... 64c ], more likely it being 32c.

The highest prime number below 255 is 251 which can be coded as
((6*6)*7)+1 => ++++ ++[> ++++ ++<- ][++ ++++ +>-< ] (29c)
And 256 can be coded in 29c 8*8*4 ==> ++++++++[>++++++++<->][> -<++++]

Edited: To correct the codes

This post has been edited by AdamSpeight2008: 07 November 2013 - 06:18 PM

Was This Post Helpful? 1
  • +
  • -

#14 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Minimal expression for a number in brainf***

Posted 07 November 2013 - 06:37 PM

My current best (just using my brain) for the value 255 is 35c
++++ [>++ ++<- ]>+[ <+++ ++++ ++++ ++++ >-]


Was This Post Helpful? 1
  • +
  • -

#15 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Minimal expression for a number in brainf***

Posted 08 November 2013 - 07:17 PM

Isn't the reduced alphabet Deterministic?
Does the Non-Deterministic come from the get input instruction ,? Since that input can be anything?

Zero => [-] ; aka Clear


This post has been edited by AdamSpeight2008: 08 November 2013 - 07:19 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2