text:
Convert Fractran into Brainfuck
Background
Fractran is an esoteric Turing-complete programming language invented by John Conway. A Fractran program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.
The reason that Fractran is Turing-complete is because it simulates a register machine. The number's prime factorization stores the contents of the registers, while the division and multiplication is a way to conditionally add and subtract from the registers. I would recommend reading the Wikipedia article (linked to above).
The Challenge
Your task is to write the shortest program possible that can take a valid Fractran program from STDIN as its only input and generates a valid BF program to STDOUT that simulates the Fractran program. There are two ways that you could simulate a Fractran program with BF.
NOTE: Your answer is not a BF program. Your answer is the code that generates the BF program from any given Fractran program. The goal is to get the BF program to be the equivalent of the Fractran program. (technically you could do the competition in BF, but it would be hard)
Option 1
Your program should output a BF program that does the following:

Takes exactly 1 number from STDIN in the form of the corresponding ASCII character (due to the way that BF input works), which is the input to the Fractran program.
Prints exactly 1 number to STDOUT in the form of the corresponding ASCII character, which is the output to from the Fractran program.

This option is meant to represent the exact input and output from a Fractran virtual machine.
Option 2
The BF code that your program produces should do the following:

Take input by having the prime factorization of the number already encoded in memory (prior to running the program). If the input is 28 (2*2*7), then there will be a value of 2 in the second cell and a value of 1 in the seventh cell (the pointer starts on cell 0). All other cells will be zero.
Give output by having the prime factorization of the output encoded in memory when the program terminates. If the output is 10, then there must be a value of 1 in each of cells 2 and 5. All other prime-numbered cells must have a value of zero. The content of other cells do not matter.

This option represents the computing model behind the Fractran language.
Rules and Requirements

Input (top your program) will be a list of fractions on STDIN. There will be one fraction per line with a comma between the numerator and denominator. An empty line represents the end of input. The fractions will always be reduced to lowest terms.
Your program's output should be a single-line, valid BF program to STDOUT. This program should be able to simulate that particular Fractran program according to one of the two options. For any input, the BF program generated should be able to produce the same output as the Fractran program.
You must state which option you chose.
You can choose the bounds on the BF memory and tape, and whether they are wrapping
CODE GOLF.  Also, the size of the outputted BF programs does not matter, only the size of the program that is doing the converting.
Programs should only consist of printable ASCII

If I am ambiguous anywhere, do not hesitate to ask. This is a very complicated challenge to describe.
In addition, please post your program's generated BF code for the following input, as to provide an easy way to check if your program is working:
33,20
5,11
13,10
1,5
2,3
10,7
7,2

This program calculates the number of 1s in the binary expansion of a number. However, the input and output are formatted strangely (as with all Fractran programs). Input is of the form 2^A, while output is of the form 13^B.

So basically you want a fractran interpreter in brainfuck. Everything else is fairly trivial.

@CMP I want a program that outputs the BF version of a Fractran program. The code that does this conversion does not have to be in BF. The BF program itself is single-purpose.

Are there limits on the brainfuck interpreter we use? Must we use byte sized cells, or can we use int cells? Bounded memory? Wrapping memory? Wrapping cells? Anything we want that makes it work?

Anything you want to make it work, but please specify in your answer.

@PhilNotPi I know you want single purpose, but the most straightforward way is implementing an interpreter, and having the main program output that interpreter, somehow encoding the original program in memory somewhere.

@CMP Ok, that can work.

The "instant accepted answer" criterion is impossible because Fractran can't handle input in the format specified. Clarifying details like that, and like CMP's questions about interpreter variants, is the purpose of the sandbox thread in meta.

@PeterTaylor Yeah, that was a stupid mistake. Also, I probably should have put this in the sandbox thread. But, what can I do now? Should I delete the question and move it to the sandbox?

I would say no. The question looks pretty good to me. Unfortunately it does look like IO constraints make it impossible to have a real fractran self-interpreter.

But holy cow, it looks like a self interpreter does exist. This thread has details: http://stackoverflow.com/questions/1749905/code-golf-fractran. I have no idea how they work, and I assume they require significant re-encoding of input, but wow.

Just to let everyone know, I now have a working 371 character Perl solution for you to beat.

I'm confused by your example program's claim that it calculates the number of 1s in the binary expansion.  When I run it with 2 I get 13 (2->7->10->13).

Can we assume the input fractions are in lowest terms?

@KeithRandall Actually, it does compute the number of ones. The output will not be the actual number N though, but rather 13^N. (edited the question, pretty important info to leave out!). Fractran inputs and outputs are always formatted in strange ways.  Also, you can assume that they will be lowest terms.

It's probably possible to solve this with BF...

Python, 182 chars
Option 1, standard byte cells.  There are only 255 possible inputs (0 as an input doesn't really make sense), so I just run a Fractran interpreter 255 times in Python and generate a simple table lookup Brainfuck program encoding the results.
import sys
I=map(eval,sys.stdin)
P='+>,'
Q=''
for i in range(1,256):
 while i:j=i;i=([i*x/y for x,y in I if i%y==0]+[0])[0]
 r=j&255;P+='-[';Q=']<[-'+'+'*r+'.'+'-'*r+']>'+Q
print P+Q

Output for the example input (___ = 246 more nested conditions, I can't paste the whole result as it is too large):
+>,-[-[-[-[-[-[-[-[___]<[-+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.-------------------------------------------------------------------------------------------------------------------------------------------------------------------------]>]<[-+++++++++++++.-------------]>]<[-+++++++++++++.-------------]>]<[-+.-]>]<[-+++++++++++++.-------------]>]<[-+++++++++++++.-------------]>]<[-+++++++++++++.-------------]>]<[-+.-]>

+1 for the creativity. Also, what would happen if you fed this a Fractran program that was an infinite loop of some sort? The program would fail to produce an equivalent (infinitely-looping) BF program. Aha!

@PhiNotPi: true, I may need to detect looping and special case that...

Actually, I think that determining whether a given Fractran program is an endless loop or not is equivalent to the halting problem. Good luck with that. :)

@PhiNotPi: yes, my last comment was a joke.

An interesting approach. Only shortcoming may be if the fractran spec says it needs to handle outputs greater than 255, which I know many programs rely on, so it seems a bit weird to take only the LSB of the result.

@CMP, the question specifically states that the input for option 1 is taken from ascii.

@PhiNotPi determining whether or not a program halts, it slightly different than being able to create another program in another language such that it halts if and only if the original halts. The former is impossible, while the latter is done every day by compilers.

Python, 420 chars
This uses a sort of blend of options 1 and 2:  It assumes that brainfuck is implemented with big integers (I use a Sage implementation).  Input a fractran program, for example, 33/20,5/11,13/10,1/5,2/3,10/7,7/2.  Then, pre-load a number, for example, 2^5, at the cursor.  Then, run the output of this python script.  Wait 44 seconds.  The result, 13^2 sits where the cursor started.  I didn't wait for the answer for 2^7.
s="[->>>+<<<]+["
for l in raw_input().split(','):
 a,b=map(int,l.split('/'))
 s+="[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>["+"[->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]<"*(b-1)+"[->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]<"+"[->+>+<<]>[-<+>]<"*a+"[-]>>[-<<+>>]<<<<<->>>>]<<]<<"
print s+">+<[->-<]>[-<+>]<]>>>[-<<<+>>>]"

This is my first brainfuck script.  It can certainly be golfed further, but I've got other things to do until later tonight.
edit:  rather than golf this further, I'm working on a solution for option 2.  also, here's the output for the requested program:
[->>>+<<<]+[[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<>+<[->-<]>[-<+>]<]>>>[-<<<+>>>]

That's a nice first Brainfuck script, +1. You can compute 2^7 with my Brainfuck interpreter in less than 5 seconds by the way. Also, shouldn't it be raw_input() instead of raw_input (or is it some quirk I don't know about) ?

@copy, thanks!  you're right, raw_input() is necessary.  I'm not surprised that competent brainfuck interpreters do better than my awful naive Sage implementation.

Sage, 431 chars
This is a completely new solution.  I figured out some better ways of doing things in brainfuck, and this properly implements Option 2.  Newlines added for clarity.  This can probably be golfed further, but it involves rewriting the BF to have a lower loop depth.
exec"f=factor;
J=''.join;
Q=L(a,b):Lz:a*z+b*-z;M=Q('<>');
C=Lj,k:(Ll:'[-%s+%s+%s]%s[-%s+%s]%s'%tuple(map(M,[-j,-k,l,-l,l,-l,k])))(j+k);
print '>+[>>>+'+J(map(L(n,m):reduce(Lr,(p,e):'[-%s%s%s[[-]<<+>>]%s<<%s]'%(M(4-p),C(6-p,2),'[-'*(e-1),']'*(e-1),r),f(m),'[-<<<->>>%s]'%J(map(L(p,e):M(4-p)+Q('+-')(e)+M(p-4),f(n/m))))+'<<<'+C(3,2),[map(QQ,x.split('/'))for x in raw_input().split(',')]))+'<<<<+>[-<->]<[->+<]>]'".replace('L','lambda ')

Sample output:
Given the input 33/20,5/11,13/10,1/5,2/3,10/7,7/2
>+[>>>+[->[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<<+>>]<<[-<<[->>>>+>>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<<[-[[-]<<+>>]]<<[-<<<->>><<-->><+>>-<>>>>>>>+<<<<<<<]]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->>>>>>>[-<<<<<+>>+>>>]<<<[->>>+<<<]<<[[-]<<+>>]<<[-<<<->>>>+<>>>>>>>-<<<<<<<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<<+>>]<<[-<<[->>>>+>>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<<[[-]<<+>>]<<[-<<<->>><<->>>-<>>>>>>>>>+<<<<<<<<<]]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<<+>>]<<[-<<<->>>>-<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[-<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[[-]<<+>>]<<[-<<<->>><<+>><->]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->>>[-<+>>+<]>[-<+>]<<[[-]<<+>>]<<[-<<<->>><<+>>>+<>>>-<<<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[-<<[->>>>+>>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<<[[-]<<+>>]<<[-<<<->>><<->>>>>+<<<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<<<+>[-<->]<[->+<]>]

Perl, 326 characters
I am going to answer my own question hopefully to stimulate more answers. I am of course not eligible to win. This is option 2 with unbounded memory and cells, although it works on wrapping cells. Each fraction is converted into a single block of code. The newlines are for readability.
L:{$A=<>;
if($/eq$A){last L}
($B,$C)=eval$A;
$D=$E=$F=$G=$H=2;
while($C>1){
if($C%$H==0){
$C/=$H;
$R=">"x$H;
$L="<"x$H;
$D.=$R.'[-'.$L;
$E.=$R.'-'.$L;
if($H>2){$R.="+[->+<]]>[-<+>]<"}
else{$R.="+[-<+>]]<[->+<]>"}
$G=$R.$L.$G;
$H--}$H++}
$H=2;while($B>1){
if($B%$H==0){
$B/=$H;
$F.=">"x$H.'+'.'<'x$H;
$H--}$H++}
$I="+[-$I$D$E+$F$G]";
redo L}print$I

Here is the example output. This takes advantage of the fact that other characters are ignored as comments. This also appears to be a very short output compared to the other entries, although output size doesn't technically matter.
+[-+[-+[-+[-+[-+[-+[-2>>[-<<>>[-<<>>>>>[-<<<<<2>>-<<>>-<<>>>>>-<<<<<+2>>>+<<<>>>>>>>>>>>+<<<<<<<<<<<>>>>>+[->+<]]>[-<+>]<<<<<<>>+[-<+>]]<[->+<]><<>>+[-<+>]]<[->+<]><<2]2>>>>>>>>>>>[-<<<<<<<<<<<2>>>>>>>>>>>-<<<<<<<<<<<+2>>>>>+<<<<<>>>>>>>>>>>+[->+<]]>[-<+>]<<<<<<<<<<<<2]2>>[-<<>>>>>[-<<<<<2>>-<<>>>>>-<<<<<+2>>>>>>>>>>>>>+<<<<<<<<<<<<<>>>>>+[->+<]]>[-<+>]<<<<<<>>+[-<+>]]<[->+<]><<2]2>>>>>[-<<<<<2>>>>>-<<<<<+2>>>>>+[->+<]]>[-<+>]<<<<<<2]2>>>[-<<<2>>>-<<<+2>>+<<>>>+[->+<]]>[-<+>]<<<<2]2>>>>>>>[-<<<<<<<2>>>>>>>-<<<<<<<+2>>+<<>>>>>+<<<<<>>>>>>>+[->+<]]>[-<+>]<<<<<<<<2]2>>[-<<2>>-<<+2>>>>>>>+<<<<<<<>>+[-<+>]]<[->+<]><<2]


text:
Solving Mastermind in 6 or less moves
Your goal is to write a program that will solve any Mastermind puzzle in 6 or less moves.
Background
Mastermind is a board game. The goal of the game is to exactly guess the combination (colours and order) of 4 coloured pegs hidden by the other player. When a guess is made, the other player responds with between 0 and 4 white and or red pegs. A red peg is where the colour and location are correct. A white peg is where the colour is represented in the remaining pieces, but is in the incorrect location. If there are duplicate colours in the guess, there will only be one peg awarded per corresponding colour in the secret. (So - if the secret contained 1 Blue, and the guess had 2 blues with one in the correct location, there would be one red peg given). There are 6 different colors, and duplicates may be used.
So for instance, a game might go as follows:
(Assuming the solution is Red Green Green Blue)
1:  Blue Purple Black Green - 2 white pegs
2:  Green Red Black Blue    - 2 white pegs, 1 red peg
3:  Green Green Green Blue  - 3 red pegs
4:  Red Green Green Blue    - 4 red pegs

The rules are expanded on Wikipedia
Requirements

The program must read from stdin, and write to stdout
I will be using numbers for simplicity instead of colors. The combination to guess will be 4 numbers between 1 and 6
They must output their guesses as a series of 4 space separated numbers from 1 to 6 concluding with a newline. For instance:
1 5 2 2 \n
The program will subsequently receive as input after its guess 2 integers between 0 and 4 separated by a space and concluding with a newline. The first will be the amount of white pegs, the second the amount of red pegs.
On an input of "0 4" (4 red pegs), the program must terminate
The program must be able to solve any puzzle in less then 6 turns (your program giving output, followed by the response input is 1 turn). There is no bonus (due to complexity of proof) for being able to solve it in less.
The solution must be completely internal and included in the source. Standard Libraries only are permitted. The solution may therefore not rely on any other files (such as dictionaries), or the internet.

Example Input/Output
> is your programs output
< is the responding input
Solution is 1 5 6 6

> 1 2 3 4
< 0 1
> 4 1 6 6
< 1 2
> 1 6 5 6
< 2 2
> 1 5 6 6
< 0 4

Scoring

This is pure and simple Code Golf. The shortest solution in bytes wins.

This is my first Code Golf question. My apologies if I have done something wrong, but I've attempted as well as possible to ensure that there is absolutely no ambiguity, and prevent as much rules lawyering as possible. If I have been ambiguous or unclear, please feel free to ask questions.

In your example input/output shouldn't 1 2 3 4 return 0 1?

And in the example text, shouldn't "Green Green Green Blue" give a white peg as well (for the first Green)? EDIT - Wikipedia clarifies that no white should be given, as you wrote. But I think the white/black rules should be explicitly stated in the question.

How slow will it be allowed to work?

@Gaffi - Absolutely right - fixed

@leftaroundabout - Time was intentionally omitted as to not discourage slow, and very short implementations. Also as I don't know the speeds of some languages that people use (Brainf**k or Golfscript) for instance, and didn't want to exclude on that basis.

@ugoren - I've stated them, but please feel free to let me know if they are still unclear

Well golfscript is out since it can't do interactive IO

@gnibbler perhaps it's slow enough to pretend...

The rules for white pegs are not stated here. Suppose you chose 1234 and I guess 5611. Both my 1s are the right color in the wrong place, so from the way you stated the rules I'd say I get 2 whites. But no - Wikipedia says it's 1 white. The incorrect method is also easier to program (but Steven Rumbalski correctly implemented Wikipedia's rules).

@ugoren - I attempted to clarify the rules to match the rules of the game. Feel welcome to edit it if it's still unclear

I know it's only an (very old) example, but wouldn't 4166 be a poor guess after 1234 yielded only 1 match? Surely it would keep only one color from the previous guess. Am I missing something?

I gave that example solely as it would demonstrate the requirements and input/output well. Not as a recommended approach.

Python 2 Python 3, 359 365 338 chars
from itertools import*
from collections import*
m=h=set(product(*['123456']*4))
def f(g,k):b=sum(x==y for x,y in zip(g,k));return'%s %s'%(sum(min(g.count(c),k.count(c))for c in set(g))-b,b)
while len(m)>1:g=min(h,key=lambda g:max(Counter(f(g,k)for k in m).values()));print(*g);s=input();m=set(x for x in m if s==f(g,x))
print(*(m.pop()))

Funny, it took me many edits to realize I had a five character variable name.
I do not like the long imports.  It feels like I should be able to implement a replacement for collections.Counter that would save the import.
I also do not like the print(*(m.pop())) at the end.  It feels like it should disappear into the while loop, but I can't find a way to do it without making it longer.

TypeError: join() takes exactly one argument (2 given) on return j(sum(min(g.count(c),k.count(c))for c in set(g))-b,b). also, sum() returns an int, while j (str.join) should take an iterable

My loop structure gets rid of the final print, and I think it's slightly shorter. It also matches the requested behavior better (stopping on "4 0" rather than when you know the answer). And len(m)>1==m[1:]. Import is indeed annoying - from a,b import * would have been nice.

this program seems to exit whenever it feels it's right. one time I ran it and it stopped at 5 guesses, it wasn't correct. the next time it stopped at 4 guesses and it was correct, but I didn't even input 4 0 yet, which is in the objective criteria, and other times it will exit with an exception: print(*(m.pop())) KeyError: 'pop from an empty set'

@Blazer.  What are the test cases that caused this output?

@Blazer:  4 0 is four white pegs.  I think you have the scoring reversed.

1 2 3 4 is the answer: 3 4 3 4; 0 2; 1 5 3 3; 0 2; 2 5 1 4; 2 1; 1 2 3 4 and then it terminates. I think my previous tests were faulty. still though, it should only terminate on 0 4 (which is what I meant to say)

Haskell, 317 304
q[0,4]_=error""
q[n,m]l=(\s->all(==4-m)[g s,n+g(u(foldr((u((.drop 1).(++)).).break.(==)))$unzip s)]).c(u(/=)).zip l
u=uncurry;m=map;g=length;c=filter
f a=[head.c(($(zipWith q(take n a)$f a)).all.flip($)).sequence$replicate 4[1..6]|n<-[0..]]
main=interact$unlines.m(unwords.m show).f.m(m read.words).lines

I love writing purely functional interactive programs! But of course this style has certain limitations: it terminates now with an error, but you didn't specify that this is not ok. I'd need to refactor the whole thing into the IO monad to get a non-error exit.

Does it guarantee a correct guess in 6 moves?

Uh. I thought it was (works for the OP's example and other solutions), but exhaustive testing shows that it sometimes needs 7 guesses. I shall have to work on this yet!

Python, 385 357 chars, Solves in 5 moves
The more I change it, it grows more and more like Steven Rumbalski's... The main difference is that he works with strings rather than integers.
Implemented Knuth's algorithm (correctly now, I hope).
Borrowed the scoring function from Steven Rumbalski.
It takes a long time to generate the first guess, gets better later.
Hard-coding it (g=len(A)==1296 and [1,1,2,2] or ...)  makes life easier if you want to test it.
I don't count 4 newlines+tab pairs, which can be replaced by semicolons.
from collections import*
from itertools import*
a=B=A=list(product(*[range(1,7)]*4))
r=lambda g,k:(sum(x==y for x,y in zip(g,k)),sum(min(g.count(c),k.count(c))for c in set(g)))
while a!=4:
    g=A[1:]and min(B,key=lambda x:max(Counter(r(x,i)for i in A).values()))or A[0]
    print"%d "*4%tuple(g)
    b,a=map(int,raw_input().split())
    A=[x for x in A if r(g,x)==(a,a+b)]

"%d "*4%tuple(g)

from collections import*

a,b=map(int,raw_input())

product(*[range(1,7)]*4)

Counter(r(x,i)for i in A).values()

g=A[1:]and min(B,key=lambda x:max(Counter(r(x,i)for i in A).values()))or A[0 ] TypeError: 'set' object is not subscriptable

@Blazer, I think it did work, but maybe I didn't verify properly. At worst, I'll change set back to list (I was so happy about saving this character...)

my answer was 1 2 3 4: 1 1 2 3; 2 1; 1 2 2 4; 0 3; Traceback (most recent call last):   File "mastermind.py", line 6, in <module>     g=A[1:]and min(B,key=lambda x:max(Counter(r(x,i)for i in A).values()))or A[0] IndexError: list index out of range

@Blazer, I read the inputs flipped. Fixed now.

Great solution and code but it crashes on me!  I tried "1234" as a solution:

1 1 1 2 | < 1 1 |||  > 1 1 3 3 |  < 0 2 |||  > 1 2 1 1 |  < 0 2  |||  > 1 2 2 3 |  < 1 2 |||

At this point, after entering the last reply, the code crashes, because list 'A" gets empty!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Tips for golfing in GolfScript
What, this post doesn't exist yet?
Of course, GolfScript is made for golfing, so you might think that no specific tips are really needed.  But to make full use of GolfScript's features, you need to learn some non-obvious tricks.  This post is for collecting such helpful tips and tricks.
To start with, here are the official GolfScript reference pages.  You should really familiarize yourself with these first:

Tutorial
Syntax
Built-ins
Quick reference

In particular, I would very much suggest reading the pages in this order — the quick reference is of little use until you're already reasonably familiar with the built-ins, and the tutorial includes some important details that are not explained on the other pages.

Ps. For the sake of inspiration and personal interest, here are some questions I'd like to see nice answers to:

How to do limited transliteration in GolfScript?  {FROM?TO=}% works if you can be sure all the inputs are found in FROM (or don't mind them all being mapped to the last element of TO), but all the ways I've seen for leaving unmapped values unchanged have been more or less klugey.
How to best convert a string into an array of ASCII codes and back?  Which operations do this as a side effect?  What's the best way to dump the characters in a string onto the stack (like ~ does for arrays)?

Another question: is there a nice way to transform ... x into ... [x]? The best I can see is [.;].

@Peter: If x is a number, then []+ works and is one char shorter. And of course, if x is the only thing on stack, then just ] will do.

I'd like to ask the best ways to do: min, max, and absolute value. All my solutions seem to take way more characters than they should.

What is the best way to modify an array at a given index?

@user1502040: Answered below. (If anyone knows a better way, please share!)

Rational / Float / Complex
I've read so many times that GolfScript has only integers that I started to believe it. Well, it's not true.
2-1? # Raise 2 to the power of -1. Result: 0.5
4-1? # Raise 4 to the power of -1. Result: 0.25
+    # Add. Result: 0.75

The output is
3/4

with the standard GolfScript interpreter and
0.75

on Web GolfScript.
Similar hacks allow to cast to Rational, Float or even Complex:
{-2.?./*}:rational
{2.-1??./*}:float
{-2.-1??./*}:complex

OMGWTFHAX o_O!!!

WAT! Pretty sure this is a bug in the interpreter, but wow

Line 82 of the most recent interpreter: Gint.new(@val**b.val). It seems that the Gint constructor is missing an int cast...

What is the result of {-2.?./*}:rational if there is one?

Shuffling an array
The easiest way to shuffle an array in GolfScript is to sort it by a random sort key.  If you only need to crudely shuffle a few values, the following code will do:
{;9rand}$

Note that, even for short lists, this will not give a very good shuffle.  Due to the birthday paradox, to get a reasonably uniform shuffle, the argument to rand needs to be significantly greater than the square of the length of the list being shuffled.
Replacing the 9 above with 99 thus gives reasonably good results for lists of up to ten elements, but exhibits noticeable bias for longer lists.
The following code, which uses 99 = 387,420,489 possible values, is good for up to about 1000 items or so (and acceptable for up to about 20,000):
{;9.?rand}$

For really long lists, add one more 9 for 9999 ≈ 3.7 × 10197 values:
{;99.?rand}$

Testing:
Here's the distribution of the first element in a 10-element list shuffled using the different variants shown above, sampled over 10,000 trials:

The output of 10,{;9rand}$0= shows a very clear bias, with 0 being more than three times as likely to end up in the first position as 1:
0 16537 #######################################################
1 5444  ##################
2 7510  #########################
3 8840  #############################
4 9124  ##############################
5 12875 ##########################################
6 9534  ###############################
7 8203  ###########################
8 7300  ########################
9 14633 ################################################

With 10,{;99rand}$0=, most of the bias is gone, but a noticeable amount still remains:
0 10441 ##################################
1 9670  ################################
2 9773  ################################
3 9873  ################################
4 10134 #################################
5 10352 ##################################
6 10076 #################################
7 9757  ################################
8 9653  ################################
9 10271 ##################################

With 10,{;9.?rand}$0=, the output is basically indistinguishable from a truly random sample:
0 9907  #################################
1 9962  #################################
2 10141 #################################
3 10192 #################################
4 9965  #################################
5 9971  #################################
6 9957  #################################
7 9984  #################################
8 9927  #################################
9 9994  #################################

Ps. For really bad shuffling of numeric arrays or strings, the following code may sometimes be acceptable:
{rand}$

It will generally be ridiculously biased, but as long as all elements of the input array (or all character codes in the string) are greater than one, it has a non-zero probability of producing any permutation of the array, which may sometimes satisfy poorly written challenge requirements.

I remember I once skeptically did the math for the birthday paradox after my brother told me about it, he was right :(

Negating a number
One thing GolfScript lacks is a built-in negation operator.
The obvious ways to convert a number on the stack to its negative, like -1* or 0\-, need three chars.  However, there's a way to do it in two:
~)

This works because GolfScript uses two's complement arithmetic, so that ~x equals −x−1.
Of course, the variant (~ also works; choosing between them is generally a matter of taste.

If your program mysteriously breaks, check your variables
I just spent a while debugging an apparently correct program which used ! as a variable (on the grounds that I wasn't going to use it again). Unfortunately I did use if, and it turns out that the implementation of if calls ! to decide which branch to follow.

I ran into this a lot trying to assing n to some counter

Wrapping the top item of the stack into an array

Is there a nice way to transform ... x into ... [x]?

For full generality, the best option appears to be 4 chars. However, in certain special cases it's possible to reduce this.
1 char
] works in the special case that xis the only thing on the stack.
3 chars
[]+ works in the special case that x is an integer.
.,/ works in the special case that x is a truthy array or string. E.g. "AB".,/ gives ["AB"]; 3,.,/ gives [[0 1 2]]. However, "".,/ and [].,/ both give [].
4 chars
[.;] works unconditionally.

To address a specific subquestion:

How to best convert a string into an array of ASCII codes and back? Which operations do this as a side effect? What's the best way to dump the characters in a string onto the stack (like ~ does for arrays)?

For those who don't understand the problem, GolfScript's type system gives priority to the types in the order integer, array, string, block. This means that ordinary array operations applied to a string almost always give you a string. E.g.
'ABC123'{)}%

will leave 'BCD234' on the stack.
As a result, the best way to convert a string into an array of ASCII codes is almost certainly to dump the characters on the stack and then gather them into an array.
What's the best way to dump the characters in a string onto the stack? {}/
What's the best way to convert a string into an array of ASCII codes? [{}/] (with the usual caveat that if there's nothing else on the stack you can skip the [)
What's the best way to convert an array of ASCII codes into a string? ''+ (Note that this also flattens the array, so e.g. [65 [66 67] [[[49] 50] 51]]''+ gives 'ABC123')

What's the best way to  turn a single ASCII code into a string? []+''+? (seems rather long)

@Quincunx, it is rather long, but I know no better way. The thing to do might be to look at where the ASCII code came from and see whether you can get it to arrive already in an array.

I'd like to ask the best ways to do: min, max, and absolute value. All my solutions seem to take way more characters than they should.   –  Claudiu

min / max
To find the smallest / largest value in an array, just sort it and take the first / last element:

$0= (3 chars) - minimum element in an arry
$-1= (4 chars) - maximum element in an array

If you know the length of the array, and it's 10 elements or less, you can find the maximum in three chars by replacing -1 with the index of the last element.
If you have the values on the stack, you can just collect them into an array first.  For this, an occasionally useful trick is that [\] collects the top two elements of the stack into an array, while [@] collects the top three.  Thus, we get:

[\]$0= (6 chars) - minimum of two values on stack
[@]$0= (6 chars) - minimum of three values on stack
[\]$1= (6 chars) - maximum of two values on stack
[@]$2= (6 chars) - maximum of three values on stack

The same trick can also be used to find the median of three values, which can be occasionally useful:

[@]$1= (6 chars) - median of three values on stack

Here's another potentially useful trick for finding the min/max of two values while leaving the original values on the stack:

.2$>$ (5 chars) - find minimum of two values on stack, while leaving original values untouched
.2$<$ (5 chars) - find maximum of two values on stack, while leaving original values untouched

The way it works is that .2$ clones the top two elements on the stack in reversed order (i.e. a b → a b b a), < / > compares the copies and returns 0 or 1, and scalar $ then copies either of the two input values depending on the result of the comparison.

If you have two nonnegative integers on the stack, you can use ,\,&, (5 chars) to find their minimum and ,\,|, (5 chars) to find their maximum. This trick uses set intersection and union, respectively, over the ranges. You can save another character if it's possible to apply , to each argument separately without having to exchange them. Since this method computes a range for each argument, it's not very efficient for larger numbers, but could be very useful for smaller inputs.
An even shorter way to find the minimum of two non-negative integers on the stack is ,<, (3 chars).  Alas, this trick does not work for finding the maximum.

absolute value
The GolfScript built-in absolute value operator is abs (3 chars).  While this is two chars more than I'd prefer, it's hard to beat in general.
In some cases (e.g. for sorting by absolute value) you might find the square of a number an adequate substitute for its absolute value; this can be computed in two chars, either 2? or .*.  Thus, we get:

{.*}$0= (7 chars) - minimum element by absolute value in array
{.*}$-1= (8 chars) - maximum element by absolute value in array

Similarly, instead of e.g. testing if the absolute value of a number is less than 3 with abs 3< (6 chars, including space), you can test if its square is less than 9 with .*9< (4 chars, no space needed).

If you have two nonnegative integers on the stack, you can use ,\,&, (5 chars) to find their minimum and ,\,|, (5 chars) to find their maximum. This trick uses set intersection and union, respectively, over the ranges. You can save another character if it's possible to apply , to each argument separately without having to exchange them. Since this method computes a range for each argument, it's not very efficient for larger numbers, but could be very useful for smaller inputs.

@KirarinSnow: Thanks! I've added it to the answer.

What is the best way to modify an array at a given index?   –  user1502040

That's a good question.
There's no direct way to assign a value to an array element in GolfScript, so, one way or another, you're going to have to rebuild the whole array.
The shortest general way I know to insert a new value x at index i in an array is to split the array at the given index and append x to the first half before joining them together again:

.i<[x]+\i>+ (11 chars) - insert the value x into array at (0-based) index i

To replace the value at index i with x, we just need to shorten the second half of the array by one element:

.i<[x]+\i)>+ (12 chars) - replace the element at (0-based) index i with the value x

Alternatively, shortening the first half instead will effectively do the same, but with 1-based indexing, which may sometimes be preferable:

.i(<[x]+\i>+ (12 chars) - replace the element at (1-based) index i with the value x

In all the examples above, if x is a number, the square brackets around it may be omitted to save two characters, since it will be auto-coerced into an array by + anyway:

.i<x+\i>+ (9 chars) - insert the number x into array at (0-based) index i
.i<x+\i)>+ (10 chars) - replace the element at (0-based) index i with the number x
.i(<x+\i>+ (10 chars) - replace the element at (1-based) index i with the number x

The brackets may also be omitted if either x or the input "array" (or both) are actually strings, in which case the result will also be coerced into a string (using the usual array → string conversion rules).

Ps. As a special case, if we know that the array has between i and 2 × i elements, we can insert a new element x at the (0-based) index i with i/[x]* (6 chars).  What this actually does is split the array into chunks of up to i elements and insert x between each chunk.  Note that, in this case, the brackets are necessary even if x is a number.

Pps. An alternative approach is to use dynamically named variables.  For example,
 'foo' 42 ':x'\+~

will assign the value 'foo' to the variable x42, while
 42 'x'\+~

will retrieve it.
You can optimize this further by omitting the x prefix and just assigning directly to the numeric literals — this is perfectly legal in GolfScript, and allows you to save one char from the assignment code and shorten the retrieval code to just `~ (or nothing at all, if the index is constant!).  The down side, of course, is that assigning to a numeric literal will override the value of that literal anywhere else in your code.  Often, though, the use of number literals can be avoided (or at least restricted to the beginning of the program, before any of them are reassigned), in which case this trick is perfectly fine.

If you know that the array does not have duplicate values, you can replace a value at index i for 9 bytes: .[i=]/[x]*

Assigning to number literals
Often, instead of writing 1:x and then using/updating the variable x, you can just use and update 1 directly:
1:^;{^.p.+:^;}5*
{1.p.+:1;}5*       (4 bytes shorter)

Of course, this also works for other starting values, but will break if that value occurs anywhere else in your code.
Punctuation as variable names
If you have to use variables, it's also often wise to use punctuation that isn't already in your code -- lots of programs can do without &, |, ^, or ?. This way, for example, you can write &n instead of x n to push your variable and then push a newline.

Some assignments can have unexpected side effects, though. In particular, assigning to ! is often a bad idea, as it will break if and do (as well as while, until, and, or and xor). Similarly, or is defined by the interpreter as an alias for 1$\if, so redefining 1, $ or \ will also break it. Redefining \`` breaks p`.

Final output manipulation
By default, when your program ends, the GolfScript interpreter outputs everything on the stack, plus a final newline, exactly as if your program ended with:
]puts

What the documentation doesn't directly mention is that the interpreter literally calls the built-in puts to produce this output, and that this built-in is literally defined as:
{print n print}:puts;

Thus, you can suppress or manipulate the final output by redefining puts, print  and/or n (or   if you're feeling really twisted).  Here are some examples:
Suppress final newline:
'':n;

(Of course you can leave out the ; if you don't mind an extra empty string on the stack.)
Suppress final output completely:
:puts

This overwrites puts with whatever happens to be on top of the stack.  If that happens to be something you don't want to execute, you can use e.g. 0:puts; instead.  Note that this also suppresses p (which is defined as {`puts}:p;), but you can still use print for output if you want.

And by nothing you mean \n?

If you don't mind the trailing newline, you can also use ]; to suppress final output.

Limited transliteration
To address a specific subquestion: given a string, what's the best way to perform a tr? E.g. tr/ABC/abc/
If all of the characters in the string will be affected, this is quite easy: {'ABC'?'abc'=}% (overhead: 9 chars).
However, that breaks if some of the characters aren't transliterated and 'ABC'? gives -1.
If the transliteration is non-cyclic it can be done one replacement at a time with string splits and joins: 'AaBbCc'1/2/{~@@/\*}/ (overhead: 15 chars). This may be improvable, but there's an alternative approach which is currently better and works for cyclic transliterations.
Currently, the shortest general solutions have an overhead of 14 characters:

One approach involves an escape character: {.'ABC'?'abc0'=\or}%, where the 0 denotes a literal null byte.  (Of course, this method is not completely general: it cannot map any other character into a null byte.)

Alternatively, {.'ABC'?'abc'@),+=}% has the same overhead, but uses only printable ASCII characters.  The @),+ is a convoluted (but, apparently, the shortest) way to ensure that the replacement string always ends with the input character.

Using the last approach, for the input string 'ABCDEF' I get the result 'abc000', but the right result would be 'abcDEF'. Am I missing something?

@w0lf, that 0 is in bold because it's the escape character previously mentioned - i.e. the byte 0.

Turn a string to an array of char
You can do this by typing:
1/ after  it.
Example:
"String"1/ pushes to stack the array ['S''t''r''i''n''g'].
This is handy when you want to move chars around the string.

Can you give an example of how this might be handy? Strings already act like arrays so this doesn't seem that useful.

@Quincunx it's handy when you want to pop characters out and not their ascii value

And when would you want to do that?

@Quincunx: Rotating a string, for example. "abc"1/(+ -> "bca", but "abc"(+ -> bc97.

Removing duplicates from an array
The set operators | (union), & (intersection)  and ^ (symmetric difference) will collapse multiple array elements into one.  Thus, the simplest way to remove duplicate elements from an array is to take its union or intersection with itself:
.|

or:
.&

These operators will treat strings as arrays of characters, so they can also be used to remove duplicate characters from strings.

Filtering an array
The most general way to filter an array is to use { },, which evaluates the code block for each element of the array, and selects those elements for which the resulting value is true (i.e. it acts like grep in Perl).
However, using the array subtraction operator - is often shorter.  This operator takes two arrays, and removes every element that occurs in the second array from the first.  It does not alter the order of the elements in the first array or collapse duplicates.  A useful trick is to apply the subtraction operation twice to yield a non-collapsing array intersection operator:

a b -: remove any elements found in array b from array a
a. b --: remove any elements not found in array b from array a

In particular, this can be used to count the number of times an element occurs in an array:

a.[c]--,: count the number of times the element c occurs in the array a

In general, this method is not optimal, since either of:

a[c]/,(: count the number of times the element c occurs in the array a
a{c=},,: count the number of times the element c occurs in the array a

is one character shorter (and, if it's OK for the count to be off by one, a[c]/, saves one character more).
However, in the special case where c is a number and a is a normal array (not a string), the square brackets around c may be omitted because the - operator coerces its arguments to the same type:

a.c--,: count the number of times the number c occurs in the array (not string!) a

(If a is a string and c is a number between 0 and 9, a.c-- will count the number of times the digit c occurs in a.)

A similar trick can by used to find the most common element in an array:
:a{a\[.]-,}$0=

Again, if the input is an array of numbers, the whole [.] sequence may be omitted.  Alas, this does not work for strings without the [.].

For counting occurrences (general case), a[c]/,( and a{c=},, are one byte shorter.

Read from STDIN
GolfScript can read from stdin:
"#{STDIN.read}"

This will continue reading from STDIN until the EOF is reached. Alternatively:
"#{STDIN.gets}"

or
"#{STDIN.readline}"

Other things available:
getbyte
getc
gets([sep])
gets(limit)
gets(sep, limit)
inspect # perhaps useful for an underhanded contest
isatty
read([length])
readbyte
readchar
readline([sep])
readline(limit)
readline(sep, limit)
readlines([sep])
readlines(limit)
readlines(sep, limit)
readpartial(maxlen [, outbuf])

For each of these, they can only be used once (and also once for each change of the parameter, also once more with empty parentheses); after that, the original value is what you'll get instead of a new value.

You might want to add a remark that {"#{STDIN.readline}"p}2* does not read 2 lines but instead the string is evaluated only once.

If you initialize i to any integer, '"#{'i):i';STDIN.gets}"'++~ will give a different result every time it is evaluated. Backticks may also be worth mentioning. If we assume Linux, we can use, e.g., \head -1`instead ofSTDIN.gets`.

@Dennis: "#{var'g','gpush Gstring.new(STDIN.gets)'.cc}"; would also let you define a new GolfScript operator g that reads a line from stdin and pushes it on the stack.

Defining new built-in operators
The standard GolfScript interpreter has a rarely used feature that allows interpolated Ruby code in double quoted string literals.
One reason why this feature isn't more commonly used is that, awkwardly, the interpolated code is executed at compile time, and the output is cached by the GolfScript interpreter so that the same string literal will thereafter always yield the same value, even inside string eval.
However, one thing this feature turns out to be good for is defining new GolfScript operators implemented in Ruby code.  For example, here's how to define a new binary addition operator that works just like the standard built-in + operator:
"#{var'add','gpush a+b'.cc2}";

It doesn't really matter where you put the definition in your code; the new operator gets defined as soon as the double-quoted string containing the Ruby code is parsed.  The add operator defined above works exactly like the built-in + operator, and can be used in exactly the same way:
1 2 add          # evaluates to 3
"foo" "bar" add  # evaluates to "foobar"

Of course, defining a new addition operator is pretty useless, unless you've done something silly like erase the built-in + operator.  But you can use the same trick to define new operators that do things Golfscript cannot (easily) do natively such as, say, uniformly shuffling an array:
"#{var'shuf','gpush a.factory(a.val.shuffle)'.cc1}";

10,shuf          # evaluates to 0,1,2,...,9 in random order

or printing the contents of the whole stack:
"#{var'debug','puts Garray.new($stack).ginspect'.cc}";

4,) ["foo" debug  # prints ["" [0 1 2] 3 "foo"], leaving the stack untouched

or interactive input:
"#{var'gets','gpush Gstring.new(STDIN.gets)'.cc}";

]; { "> " print gets ~ ]p 1 } do   # simple GolfScript REPL

or even web access:
"#{
  require 'net/http'
  require 'uri'
  var'get','gpush Gstring.new(Net::HTTP.get_response(URI.parse(a.to_s)).body)'.cc1
}";

"http://example.com" get

Of course, a somewhat golfier (and riskier!) implementation of the latter would be e.g.:
"#{var'get','gpush Gstring.new(`curl -s #{a}`)'.cc1}";

While not particularly golfy in itself, this lets you extend the capabilities of GolfScript beyond what the built-in commands provide.

How does it work?
The authoritative reference on how to define new GolfScript operators in this way is, of course, the source code for the interpreter.  That said, here's a few quick tips:

To define a new operator name that runs the Ruby code code, use:
var'name','code'.cc

Inside the code, use gpop to read a value off the stack, and gpush to push one back in.  You can also access the stack directly via the array $stack.  For example, to push both a and b onto the stack, it's golfier to do $stack<<a<<b than gpush a;gpush b.

The positions of the [ array start markers are stored in the $lb array.  The gpop function takes care of adjusting these markers down if the stack shrinks below their position, but manipulating the $stack array directly does not.

The .cc string method that compiles Ruby code in a string into a GolfScript operator is just a convenience wrapper around Gblock.new().  It also has the variants .cc1, .cc2 and .cc3 that make the operator automatically pop 1, 2 or 3 arguments off the stack and assign them to the variables a, b and c.  There's also an .order method that works like .cc2, except that it automatically sorts the arguments by type priority.
All values on the GolfScript stack are (and should be!) objects of type Gint, Garray, Gstring or Gblock.  The underlying native integer or array, where needed, can be accessed via the .val method.

However, note that Gstring.val returns an array of Gints!  To turn a Gstring into a native Ruby string, call .to_s on it instead (or use it in a context that does that automatically, like string interpolation). Calling .to_gs on any GS value turns it into a Gstring, so any GS value can be stringified with .to_gs.to_s.

The gpush function doesn't auto-wrap native Ruby numbers, strings or arrays into the corresponding GS types, so you'll often have to do it yourself by explicitly calling e.g. Gstring.new().  If you push anything other than one of the GS value types onto the stack, any code that later tries to manipulate it is likely to crash.
The GS value types also have a .factory method that calls the type's constructor, which can be useful e.g. for rewrapping arrays/strings after manipulating their contents.  All the types also have a .coerce method that performs type coercion: a.coerce(b) returns a pair containing a and b coerced to the same type.

Tuck an integer literal into a block
If you have some code that pushes a block and then an integer between 100 and 255:
{2,{2+base}/n}105,%

You can save a byte by extracting the integer as a byte from the block with ) or (.
{2,{2+base}/ni}),%
{i2,{2+base}/n}(,%

(This is A005836 by tails on anarchy golf.)
The i has ASCII value 105. GolfScript code is not treated as UTF-8, so you can put a raw byte like 200 or 250 in the file. See this answer by tails for another example.

Decoding hexadecimal input
GolfScript has no hex integer literals, so, alas, you can't just parse hexadecimal input with ~.  Instead, if your code must take hex input, you'll need to parse it manually.
This 8-char loop, applied to a string, will convert lowercase hex digits to their numeric equivalents:
{39%9-}%

If you have to (also) accept uppercase hex digits, the easiest (and likely shortest) solution is to first lowercase them with 32|, for a total of 11 chars:
{32|39%9-}%

Note that the output will technically still be a string (consisting of the ASCII characters 0 – 15), but most GolfScript array functions will accept strings, too.  If you absolutely need an array, you can always use [{39%9-}/] (where the first [ is optional if the stack is otherwise empty).
To convert the output of the code above into an integer, you can simply use 16base (6 chars).  If you want an array of bytes instead, the shortest solution I've found in simply to decode each pair of hex digits with 2/{16base}% (11 chars).  All put together, the shortest code I've found to turn a hex string into a byte array is 8 + 11 = 19 chars:
{39%9-}%2/{16base}%

Note that the output of this code is indeed an array, not a string.  If needed, you can stringify it by concatenating it e.g. with ""+ or, if you don't mind an extra newline at the end, n+.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Create a multi-level 5x5x5 Labyrinth with only one solution
The aim of this challenge is to create the shortest code (in characters) that successfully do the following:
Specifications:

Must create a 5x5x5 labyrinth with exactly 1 possible solution (no more, no less)
The labyrinth must be created randomly It must be able to generate every existing solution if left running for years
The start and finish must be placed in *opposite corners
The map output must in one of the following formats:

Option output format 1 strings, printed or alerted:
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx

Option output format 2 arrays:
[[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx]]

Output Notes:

Use 0 for empty and 1 for squares
Break lines are NOT necessary
You decide what index is what, but just make sure to explain it well

*Here is an example of what I mean by opposite corners:

Clarifications:

Can NOT move in diagonal
Can NOT pass twice on the same path
Having inaccessible areas is allowed
You can go up/down more than one level in a row

Tips:

Don't see them as walls, instead see them as a 5x5x5 stack of squares that some of them are missing and you can go through the missing ones

If something is unclear, just ask me :)

Your specification of "printing in an understandable way" is still very vague. A slightly more strict rule wouldn't harm.

@leftaroundabout I think I should specify an exact output format to remove all vagueness. But I can't picture any way of expressing multidimensional things, I need help plx before someone start working

You could just ask for each level of the maze to be printed consecutively as ASCII art, with, say, an empty line between levels.

However, there's one detail I'd like a clarification on: are walls placed between squares, or does a wall fill a whole square?

@IlmariKaronen added "Don't see them as walls, instead see them as a 5x5 stack of squares that some of them are missing and you can go through the missing ones"

you say 5x5 (a 2D array) in a few places, yet the code samples and image suggest 5x5x5 (a 3D array). I assume the 3D array is what's meant?

@KaeVerens yes, sorry about that (updating)

how is it decided that the solution is a valid labyrinth? I mean, is it the number of offshoots that the right path has? is it something to do with the ratio of 1s to 0s?

When you say "The labyrinth must be created randomly", what limitations should we infer? I presume, for example, that you don't intend to allow, as a literal reading of the rules currently does, a program which chooses between two hard-coded outputs at random.

@ajax Why not accept output in {x,y,z} coordinates?

Please post a sample labyrinth.

@KaeVerens it will be very hard to test if a solution is valid indeed, I guess we will need to manually build some random generated mazes in 3d and start testing.

@DavidCarraher chosing is different than creating. I think the current definition is ok (but I will try to clarify that in the next update)

Since there are 8 corners, but the opposite corners (Start-End) are indistinguishable from (End-Start), there are 4 possible Start-Corners to consider. Or can we say, that we only consider one start corner, since the other solutions are symmetric?

Another question: exactly 1 solution prohibits circular ways. But what about dead ends that lead nowhere - they are allowed, aren't they?

@userunknown yes, there could be 1 solution with dead ends as long as they don't make a circuit to either the same way or the solution

just out of curiosity, how can a block be accessible if it's a wall. and if that's no problem why can't I just declare every block out of the main path a wall?

C++ C, about 1000 670 643 395 297 248 chars
Sample output:
00111,10011,10111,00110,11000,
11001,01010,00100,11011,10101,
10111,10101,10001,01010,00101,
11001,11110,11100,11110,10101,
11100,10010,11001,10101,00000,

How it works: The program uses Brownian Motion to generate solutions. The start point is set. Then, a random point is selected and repeatedly moved randomly until it touches one and only one point on the start branch. The point is then set, and if it also touches the end point, the program exits and the matrix displayed. Since no point can join two branches, there is only one path through the labyrinth. The program uses the rand function, and a command line integer argument as the seed, so with a sufficient rand function it should be possible to eventually generate all valid labyrinths (this algorithm will not create unconnected areas however, so it won't generate all possible labyrinths).
Brownian motion was dropped since it turned out to be unneeded and it's removal simplifies the code significantly. I do think it made nicer labyrinths though. Likewise, the seed argument was dropped, since requiring a stateless random number generator makes more sense to me than a 128-bit seed.
It is possible for the program to get stuck in an infinite loop, since it is possible for situations where any point added to the branches would create multiple paths. This is fixable, but I think that it is rare enough to not be a concern for code golf.
#define M m[*p+1][p[1]][p[2]]
#define F(a,b)for(p[a]=5;p[a]--;putchar(b))
#define f for(i=3;i--;p[i]
p[]={4,4,4},h[3],m[7][6][6]={1};
main(i){
    for(M=2;h[1]^1||(M=1)^h[2];){
        f=rand()%5)
            h[i]=0;
        f++)
            p[i]++,
            h[M]++,
            p[i]-=2,
            h[M]++;
    }
    F(0,10)
        F(1,44)
            F(2,48+!M);
}

I've added newlines and indentation to the displayed code for readability.

I think you win this one ;-) there's no way I could shrink mine that far

I really enjoyed the competition :-) I'm a bit surprised we're still the only answers, I expected a golf scripter or similar would have beaten us both by now.

Somehow, a simple path, with no forks or decision nodes, doesn't seem to qualify as a true labyrinth. Try adding some blind alleys.

@David Carraher
The algorithm does generate dead ends and branching paths as shown in the sample. Not allowing a new point to connect two already existing branches simply prevents multiple solutions or cycles in the labyrinth.

@Sir_Lagsalot Thanks for the clarification

JavaScript, 874 816 788 686 682 668 637 characters
sample output:
00000,10111,10111,01010,11000
01011,01000,01010,01111,00011
00100,11010,00111,10111,11010
01111,10001,01110,01010,01000
00000,11110,00001,10101,10110

this one works by starting from point [0,0,0] and randomly adding attaching one more 0 next to an 0 wherever allowed (allowed==the new 0 is not next to any other 0s except the originator) until there are no more possible additions.
if any new 0 is next to the exit point (x*y*z == 48) then we open up the exit.
golfed
b=[]
I=Math.random
for(i=5;i--;)for(j=5,b[i]=[];j--;)b[i][j]=[1,1,1,1,1]
b[0][0][0]=0
k=[[0,0,0]]
function q(x,y,z){J=b[x]
if(x<0||y<0||z<0||x>4||y>4||z>4||!J[y][z])return
n=6-!x||b[x-1][y][z]
n-=!y||J[y-1][z]
n-=!z||J[y][z-1]
n-=x==4||b[x+1][y][z]
n-=y==4||J[y+1][z]
n-=z==4||J[y][z+1]
n==1&&v.push([x,y,z])}while(I){F=k.length
B=k[C=0|I(v=[])*F]
x=B[0]
q(x-1,y=B[1],z=B[2])
q(x,y-1,z)
q(x,y,z-1)
q(x+1,y,z)
q(x,y+1,z)
q(x,y,z+1)
if(D=v.length){k.push(A=v[0|I()*D])
b[A[0]][A[1]][A[2]]=0
if(A[0]*A[1]*A[2]==48)b[4][4][4]=I=0}else{for(E=[];F--;)F^C&&E.push(k[F])
k=E}}for(i=25;i--;)b[H=0|i/5][i%5]=b[H][i%5].join('')
alert(b.join("\n"))

original
window.map=[];
for (i=0;i<5;++i) {
  map[i]=[];
  for (j=0;j<5;++j) {
    map[i][j]=[1,1,1,1,1];
  }
}
points=[[0,0,0]];
map[0][0][0]=0;
function spaces(x,y,z) {
  var n=6;
  if (x<0 || y<0 || z<0) return 0;
  if (x>4 || y>4 || z>4) return 0;
  if (!map[x][y][z]) return 0;
  if (!x || map[x-1][y][z]) n--;
  if (!y || map[x][y-1][z]) n--;
  if (!z || map[x][y][z-1]) n--;
  if (x==4 || map[x+1][y][z]) n--;
  if (y==4 || map[x][y+1][z]) n--;
  if (z==4 || map[x][y][z+1]) n--;
  return n;
}
do {
  var index=Math.floor(Math.random()*points.length);
  point=points[index];
  v=[];
  x=point[0];
  y=point[1];
  z=point[2];
  spaces(x-1,y,z)==1 && v.push([x-1,y,z]);
  spaces(x,y-1,z)==1 && v.push([x,y-1,z]);
  spaces(x,y,z-1)==1 && v.push([x,y,z-1]);
  spaces(x+1,y,z)==1 && v.push([x+1,y,z]);
  spaces(x,y+1,z)==1 && v.push([x,y+1,z]);
  spaces(x,y,z+1)==1 && v.push([x,y,z+1]);
  if (v.length) {
    var point=v[Math.floor(Math.random()*v.length)];
    points.push(point);
    map[point[0]][point[1]][point[2]]=0;
    if (point[0]*point[1]*point[2]==48) {
      map[4][4][4]=0;
    }
  }
  else {
    var np=[];
    for (var i=0;i<points.length;++i) {
      i!=index && np.push(points[i]);
    }
    points=np;
  }
} while(points.length);
for (i=0;i<5;++i) {
  for (j=0;j<5;++j) {
    map[i][j]=map[i][j].join('');
  }
  map[i]=map[i].join();
}
alert(map.join("\n"));

Mathematica: True Labyrinth (827 chars)
Originally, I produced a path from {1,1,1} to {5,5,5} but because there were no possible wrong turns to be made, I introduced forks or "decision points" (vertices of degree >2) where one would need to decide which way to go. The result is a true maze or labyrinth.
The "blind alleys" were far more challenging to solve than finding a simple, direct path. The most challenging thing was to eliminate cycles within the path while allowing cycles off the solution path.
The following two lines of code are only used for rendering the drawn graphs, so the code does not count, as it is not employed in the solution.
o = Sequence[VertexLabels -> "Name", ImagePadding -> 10, GraphHighlightStyle -> "Thick",
    ImageSize -> 600];

o2 = Sequence[ImagePadding -> 10, GraphHighlightStyle -> "Thick", ImageSize -> 600];

Code used:
e[c_] := Cases[EdgeList[GridGraph[ConstantArray[5, 3]]], j_ \[UndirectedEdge] k_ /; (MemberQ[c, j] && MemberQ[c, k])]

m[] :=
Module[{d = 5, v = {1, 125}},
   While[\[Not] MatchQ[FindShortestPath[Graph[e[v]], 1, 125], {1, __, 125}],

v = Join[v, RandomSample[Complement[Range[125], v], 1]]];
   Graph[e[Select[ConnectedComponents[Graph[e[v]]], MemberQ[#, 1] &][[1]]]]]

w[gr_, p_] := EdgeDelete[gr, EdgeList[PathGraph[p]]]

y[p_, u_] := Select[Intersection[#, p] & /@ ConnectedComponents[u], Length[#] > 1 &]

g = HighlightGraph[lab = m[],  PathGraph[s = FindShortestPath[lab, 1, 125]],o]
u = w[g, s]
q = y[s, u]

While[y[s, u] != {}, u =  EdgeDelete[u, Take[FindShortestPath[u,  q[[1, r = RandomInteger[Length@q[[1]] - 2] + 1]],
  q[[1, r + 1]]], 2] /. {{a_, b_} :> a \[UndirectedEdge] b}];

q = y[s, u]]

g = EdgeAdd[u, EdgeList@PathGraph[s]];

Partition[StringJoin /@ Partition[ReplacePart[Table["x", {125}],
Transpose[{VertexList[g], Table["o", {Length[VertexList@g]}]}]/. {{a_, b_} :>  a -> b}], {5}], 5]

Sample output
{{"oxooo", "xxooo", "xoxxo", "xoxxo", "xxoox"},
 {"ooxoo", "xoooo", "ooxox", "oooxx", "xooxx"},
 {"oooxx", "ooxxo", "ooxox", "xoxoo", "xxxoo"},
 {"oxxxx", "oooox", "xooox", "xoxxx", "oooxx"},
 {"xxxxx", "ooxox", "oooox", "xoxoo", "oooxo"}}
Under the hood
The picture below shows the labyrinth or maze that corresponds to the solution ({{"ooxoo",...}} displayed above:

Here is the same labyrinth inserted in a 5x5x5 GridGraph. The numbered vertices are nodes on the shortest path out of the labyrinth. Note the forks or decision points at 34, 64, and 114.
I'll include the code used for rendering the graph even though it is not part of the solution:
HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], g,
 GraphHighlightStyle ->"DehighlightFade",
 VertexLabels -> Rule @@@ Transpose[{s, s}] ]

And this graph shows only the solution to the labyrinth:
HighlightGraph[gg = GridGraph[ConstantArray[5, 3]],
   Join[s, e[s]], GraphHighlightStyle -> "DehighlightFade", VertexLabels -> Rule @@@    Transpose[{s, s}] ]

Finally, some definitions that may help reading the code:

Original solution (432 char, Produced a path but not a true maze or labyrinth)
Imagine a 5x5x5 large solid cube made up of distinct unit cubes. The following begins without unit cubes at {1,1,1} and {5,5,5}, since we know they must be part of the solution. Then it removes random cubes until there is an unimpeded path from {1,1,1} to {5,5,5}.
The "labyrinth" is the shortest path (if more than one is possible) given the unit cubes that have been removed.
d=5
v={1,d^3}
edges[g_,c_]:=Cases[g,j_\[UndirectedEdge] k_/;(MemberQ[c,j]&&MemberQ[c,k])]

g:=Graph[v,edges[EdgeList[GridGraph[ConstantArray[d,d]]],v]];

While[\[Not]FindShortestPath[g,1,d^3]!={},
    v=Join[v,RandomSample[Complement[Range[d^3],v],1]]]

Partition[Partition[ReplacePart[
   Table["x",{d^3}],Transpose[{FindShortestPath[g,1,d^3],Table["o",{Length[s]}]}]
      /.{{a_,b_}:>  a->b}],{d}]/.{a_,b_,c_,d_,e_}:>  StringJoin[a,b,c,d,e],5]

Example:
{{"ooxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxx"},
 {"xoxxx", "xoooo", "xxxxo", "xxxxo", "xxxxo"},
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"},
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"},
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}}

Technically this is not yet a true labyrinth, since there are no wrong turns that one can make. But I thought it interesting as a start since it relies on graph theory.
The routine actually makes a labyrinth but I plugged up all empty locations that could give rise to cycles.  If I find a way to remove cycles I will include that code here.

Nice update, I like that your updated solution allows cycles on non-solution paths, it makes for a more confusing labyrinth.

Thanks. I would still like to have the solution path itself be more likely to veer away from the final node from time to time. This is presently discouraged (but not fully prevented) by FindShortestPath.

I'm not too familiar with matlab, but could you do something like FindShortestPath, add a bias against each node in the shortest path, and then run FindShortestPath again taking into account the bias so that it will avoid nodes in the shortest solution? This could be done iteratively too. I'd be interested in seeing what type of path that would produce.

@Sir_Lagsalot I posted this as a question for the Mathematica SE group here (http://mathematica.stackexchange.com/questions/4084/finding-a-not-shortest-path-between-two-vertices  )


text:
Generate number in reverse polish notation
Your task is to write a function which accepts a number N and creates a string of Reverse Polish Notation which will generate that number. Valid operations are:
1-9: Push number onto stack. Only 1-9 are allowed.
+-*/%: take two numbers from top of stack and apply arithmetic operation,
    pushing the result.
d: duplicate - push a copy of the top of the stack

That's all. For - / and % which are order dependent, the operand which was pushed first goes first. ie 63/ = 2 63- = 3 and 64% = 2
Entries are judged not by brevity of code, but by the size of the generated strings. The smaller the better. I also want to encourage pushing smaller numbers rather than bigger ones. The score for a number is calculated like so:
For any number pushed, add that number to the score.
For every operand (+-*/%d) add 1.

Your final score is the sum of your score for all numbers 0 to 10,000 inclusive. Lets go ahead and limit total running time to two minutes for all 10k, on a reasonable machine, to avoid too much brute forcing.
If you can do it only pushing 1s, go ahead and subtract 10% from your score.

Is N always integer? Are intermediate non-integer results allowed?

The time limit is irrelevant if we're allowed to hard-code a lookup table...

@Howard, Lets assume integer division so all intermediate values will be integers as well.

@Peter I can't really disallow that, but it is not particularly useful if it can't calculate values outside of the given range on the fly.

Score 199503, Java solution
import java.util.HashMap;
import java.util.HashSet;

public class RPN {

    public static void main(String[] args) {
        // Loop to calculate total over all 10001 numbers as defined in puzzle
        int total = 0;
        System.out.println("n\tscore\trpn");
        for (int k = 0; k <= 10000; k++) {
            final String rpn = findRPN(k);
            final int scr = calcScore(rpn);
            System.out.println(k + "\t" + scr + "\t" + rpn);
            total += scr;
        }
        System.out.println("TOTAL: " + total);
    }

    // simple scoring calculator for a given rpn representation (ignores 10% bonus)
    private static int calcScore(String rpn) {
        int score = 0;
        for (char ch : rpn.toCharArray()) {
            if (Character.isDigit(ch)) {
                score += ch - '0';
            } else {
                score++;
            }
        }
        return score;
    }

    // hashmap caching intermediate results and all results for 0<=n<=10000
    final static int max = 6000000;
    final static HashMap<Integer, String> rpns = new HashMap<Integer, String>();

    // maximum score expected for numbers 0<=n<=10000
    final static int maxScore = 26;

    private static void preCalculate() {
        // hashmap which contains all numbers with a given score
        final HashMap<Integer, HashSet<Integer>> perScore = new HashMap<Integer, HashSet<Integer>>();

        // numbers are build by combining those with lower score
        for (int sc = 1; sc <= maxScore; sc++) {
            final HashSet<Integer> currentScore = new HashSet<Integer>();
            perScore.put(sc, currentScore);

            // 1-9 can be reached directly by pushing
            if (sc < 10 && !rpns.containsKey(sc)) {
                rpns.put(sc, Integer.toString(sc));
                currentScore.add(sc);
            }

            if (sc > 2) {
                // score is increased by 2 if appending "d+" or "d*" to an existing rpn
                for (int n : perScore.get(sc - 2)) {
                    String rpn_n = rpns.get(n);
                    consider(n * 2, currentScore, rpn_n, "d+");
                    consider(n * (long)n, currentScore, rpn_n, "d*");
                }
            }

            // another possibility to get score sc is to take two operands
            // with scores sc1 and sc2 and add another operator
            // with the requirement that sc1 + sc2 + 1 = sc
            for (int sc2 = 1; sc2 <= sc - 2; sc2++) {
                int sc1 = sc - sc2 - 1;
                HashSet<Integer> l1 = perScore.get(sc1);
                HashSet<Integer> l2 = perScore.get(sc2);

                // try all combinations of operators from list 1 and list 2
                // with each operator + - * / and %
                for (int n : l1) {
                    String rpn_n = rpns.get(n);
                    for (int m : l2) {
                        String prefix = rpn_n + rpns.get(m);

                        // Commutative operators - only need to consider them once
                        if (n < m) {
                            consider(n + m, currentScore, prefix, "+");
                            consider(n * (long)m, currentScore, prefix, "*");
                        }

                        // Non-commutative operators.
                        consider(n - m, currentScore, prefix, "-");
                        // div and mod only possible if m!=0
                        if (m != 0) {
                            consider(n / m, currentScore, prefix, "/");
                            consider(n % m, currentScore, prefix, "%");
                        }
                    }
                }
            }
        }
    }

    private static void consider(long value, HashSet<Integer> currentScore, String prefix, String suffix) {
        if (value < -max || value > max) return;
        Integer r = Integer.valueOf((int)value);
        if (!rpns.containsKey(r)) {
            rpns.put(r, prefix + suffix);
            currentScore.add(r);
        }
    }

    private static String findRPN(int number) {
        if (rpns.isEmpty()) {
            preCalculate();
        }

        // if number is negative try 1(-n+1)-
        if (number < 0) {
            return "1" + findRPN(-number + 1) + "-";
        }

        // if number not in precalculated list try number/2
        if (!rpns.containsKey(number)) {
            if (number % 2 == 0) {
                return findRPN(number / 2) + "d+";
            } else {
                return findRPN(number / 2) + "d+1+";
            }
        }

        // otherwise use cached result
        return rpns.get(number);
    }
}

The solution is pretty much optimized to get a good score within the defined range of numbers (i.e. 0 to 10000). It sacrifices non-optimal solutions outside the range for (hopefully) optimal representations within. Nevertheless it will still work for other numbers too.
I think the score given by that solution is very close to optimal although I'm not able to prove it.
Output:
n   score   rpn
0   3   11-
1   1   1
2   2   2
3   3   3
4   4   4
5   5   5
6   5   3d+
7   7   7
8   6   4d+
9   5   3d*
10  7   5d+
11  8   3d*2+
12  7   3d+d+
...
9990    19  5d+d*d*3d*-1-
9991    17  5d+d*d*3d*-
9992    18  5d*d+d*2-d+d+
9993    19  5d+d*d*3d+-1-
9994    17  5d+d*d*3d+-
9995    17  5d+d*d*5-
9996    16  5d+d*d*4-
9997    15  5d+d*d*3-
9998    14  5d+d*d*2-
9999    13  5d+d*d*1-
10000   11  5d+d*d*
TOTAL: 199503

There's a lot of shared code which could be factored out to improve readability. (If you don't want to do it yourself but you don't mind me doing it, I'll edit, but I don't want to edit without prior permission).

@PeterTaylor Please feel free to edit the solution. I also thought about the refactoring but didn't find a nice way which lazily evaluates the string concatenations.

I applied this algorithm to only push 1s for the bonus and I got a score of 238157 - 10% = 214341.3

I tend to agree with you that this is optimal, but I also can't quite prove it. Perhaps increasing the max for intermediate values could improve scores in very few cases, but also opens up to overflow issues. I think your logic is pretty sound. d- d/ d% are all useless, but I wonder if there is any reason to do something like 1d+d1+*, where the result of the d is not used immediately.

@CMP, I increased the max for intermediate values from 6m to 15m and saw no improvement, so the only real possibility for improvement would be if one or two can shave off a character with % (currently necessary for 1 point).

JavaScript, 217597
var minNum = new Uint32Array(10001), minMA = ['11-','1','2'];
minNum[0] = 3;
minNum[1] = 1;
minNum[2] = 2;
for(var tr=2,i=2,sum=0;i<=1e4;i++){
  var minVal=i<10?i:9e9,j,minMethod=i<10?''+i:'';
  if(tr*tr*tr==i){
    if(minNum[tr]+4<minVal) minVal=minNum[tr]+4,minMethod=minMA[tr]+"dd**";
    tr++;
  }
  for(j=1;j<10&&j<i;j++) if(minVal>minNum[i-j]+minNum[j]+1) minVal=minNum[i-j]+minNum[j]+1,minMethod=minMA[i-j]+minMA[j]+'+';
  if(i>2) for(j=2;j<10&&i>j;j++) if(i%j==0){
    if(minVal>minNum[i/j]+minNum[j]+1) minVal=minNum[i/j]+minNum[j]+1,minMethod=minMA[i/j]+minMA[j]+'*';
    if(minVal>minNum[i/j]+2*(j-1)){
      minVal=minNum[i/j]+2*(j-1);
      for(minMethod=minMA[i/j],dd='',pp='',k=j-1;k-->0;dd+='d',pp+='+'); minMethod+=dd+pp;
    }
  }
  for(j=10;j<Math.sqrt(i);j++) if(i%j==0){
    if(minVal>minNum[i/j]+minNum[j]+1) minVal=minNum[i/j]+minNum[j]+1,minMethod=minMA[i/j]+minMA[j]+'*';
    if(minVal>minNum[i/j]+2*(j-1)){
      minVal=minNum[i/j]+2*(j-1);
      for(minMethod=minMA[i/j],dd='',pp='',k=j-1;k-->0;dd+='d',pp+='+'); minMethod+=dd+pp;
    }
  }
  if(Math.sqrt(i)==~~Math.sqrt(i)) if(minVal>minNum[Math.sqrt(i)]+2) minVal=minNum[Math.sqrt(i)]+2,minMethod=minMA[Math.sqrt(i)]+'d*';
  minNum[i] = minVal; minMA[i] = minMethod;
  console.log(i,minVal,minMethod);
}
for(i=0;i<=10000;i++){
  sum+=minNum[i];
}
console.log("Score : "+sum);

Quite trivial solution... does not use -, /, and % at all.. :P
I can add the case for n^5, n^7, ..., but that doesn't reduce the score quite well (only ~400).
This problem reminds me of some PE problems... (not saying that this is a part of a PE problem)
2 2 "2"
3 3 "3"
4 4 "4"
5 5 "5"
6 5 "3d+"
7 7 "7"
8 6 "2dd**"
9 5 "3d*"
10 7 "3d*1+"
11 8 "3d*2+"
12 7 "3d+d+"
13 9 "3d+d+1+"
...
9990 25 "3d+d*1+3dd***5*d+"
9991 27 "3d+d*1+3dd***5*d+1+"
9992 27 "4d*d*3d+d*3+*2dd**+"
9993 26 "4d*d*3d+d*3+*3d*+"
9994 27 "4d*d*3d++1+3d+d*2+*"
9995 27 "3d+d*1+3dd***d+1+5*"
9996 23 "7d+d*5d*d+1+*"
9997 24 "4d*d*3*1+3d+d+1+*"
9998 26 "4d*d*3*1+3d+d+1+*1+"
9999 25 "3d*1+d*1+7d*d+1+*"
10000 11 "3d*1+d*d*"
Score : 217597

Here's my baseline solution in C#:
string Make(int n)
{
  if(n < 0) return "1" + Make(-n) + "1+-";
  if(n == 0) return "11-";
  if(n == 1) return "1";
  if(n % 2 == 0) return Make(n / 2) + "d+";
  return Make(n / 2) + "d+1+";
}

public void CalcTotal()
{
  var total = Enumerable.Range(0, 10001).Sum(x => Make(x).Length);
  Console.WriteLine(total);
}

Gets a score of 346491 - 10% = 311841.9

Irrelevant for scoring, but for negative numbers you can do better with "1" + Make(-n) + "1+-"; (and maybe better still as Howard's solution).

true. Howard definitely blew this out of the water already, but that is a good optimization. I just threw this together as an intuitive direct solution.