text:
Generate a sequence with unique subsequences
The string 2123132133 has the property that no subsequence of length 3 is the same as any other subsequence of length 3.
Your task is to build a program that will output as long of a string as possible that satisfies this property for sequences of length 9 with the characters from 1 to 9.
The source code of your program may not be longer than 16 kilobytes (16,384 bytes). The program that wins is the one that outputs the longest sequence of digits from 1 to 9 such that no subsequence of 9 digits is the same.

You may want to tighten up the output requirements so that the only output is the sequence such that no subsequence is the same. Otherwise, as it currently reads, it may be possible to submit a while(1){putchar('1'+rand()%9);} submission that just spews random digits forever and it could be argued that its output will contain (given enough time) "the longest sequence of digits from 1 to 9 such that no subsequence of 9 digits is the same." That would be a dick move, for sure, but easily prevented. Cheers.

I'm pretty sure that "outputs the longest sequence of digits" implies that the entire sequence of digits that a program outputs must satisfy the subsequence requirement. Thanks for your concern, though.

Related

What I'm starting with here is a De Bruijn sequence.  Stealing some reference code on the topic, here is my submission:
#!/usr/bin/env python

def de_bruijn(k, n):
    """ De Bruijn sequence for alphabet size k and subsequences of length n. """
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

seq = de_bruijn(9, 9) # cyclic
seq = seq + seq[:8]   # extended to max
print(''.join(map(lambda n: chr(49+n), seq)))

After running for ten minutes, the output is a 387,420,497 digit sequence.  This is 9^9 + 8 digits, as expected.  (Thank you @PeterTaylor for the +8 tip on the cyclic output.)

Almost. De Bruijn sequences are cyclic, so you can copy the first 8 characters to the end to get a maximum-length non-cyclic string.

Hmm, didn't know that theorem existed. Looks like your answer will be the accepted one.

Thank you, @PeterTaylor.  That makes sense.  I've extended the sequence.


text:
Find a fraction's position in the Stern-Brocot tree
The Stern-Brocot tree is a binary tree of fractions where each fraction is acquired by adding the numerators and denominators of the two fractions neighbouring it in the levels above.
It is generated by starting with 0/1 and 1/0 as "endpoint fractions", and from there, iterating by placing one fraction between each consecutive pair of fractions by adding the numerators and denominators of those fractions together, like so:
0.  0/1                                                             1/0
1.  0/1                             1/1                             1/0
2.  0/1             1/2             1/1             2/1             1/0
3.  0/1     1/3     1/2     2/3     1/1     3/2     2/1     3/1     1/0
4.  0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0

In each iteration of the Stern-Brocot tree (the nth iteration), there are 2^n + 1 elements in the sequence, to which we can ascribe a fraction from 0/2^n to 2^n/2^n. Each new iteration simply inserts one fraction "halfway" between each pair of consecutive fractions.
This makes the Stern-Brocot tree a one-to-one mapping between the positive rational numbers and the binary fractions between 0 and 1, thereby also serving as a proof that the two sets have the same cardinality.
Your task is to write a program or function that, given the numerator and denominator of a positive rational number in lowest terms, determines the binary fraction that corresponds to that fraction's position in the Stern-Brocot tree.
Examples of inputs and outputs are provided below:
2/3 -> 3/8   (4th number in iteration 3)
4/7 -> 9/32  (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2   (middle number in the first iteration)

Inputs you don't need to support, but are included for reference:
0/1 -> 0/1   (0/1 is considered the left number)
1/0 -> 1/1   (1/0 is considered the rightmost number)

The shortest program in any language to achieve this goal wins.

Are there any input/output requirements? e.g. Is just a function sufficient as in your reference solution, or does it need to be a stand-alone program? Does fraction output format matter?

A function is sufficient. I'll make that clearer in the problem description.

It's a bit late for me to be thinking about it; I'll probably try to clarify it tomorrow.

Ok, I think the bijection you have in mind is to assign to each depth in the tree a constant denominator 2^(depth+1) and numerators 1, 3, 5, 7, ... from the left.

That is indeed the case. I'm still trying to put it in elegant words, though.

An alternative way of constructing it is to first number the nodes of the tree in breadth-first order starting at 1 (i.e. 1/1 => 1, 1/2 => 2, 2/1 => 3, 1/3 => 4, etc.). If the number so generated for a node is n, then 2^lg n (binary log) is the highest bit set in n, and the desired binary fraction is (2*(n - 2^lg n) + 1) / 2^(lg n + 1). (Anyone attempting an assembler solution in an instruction set with a get-highest-set-bit will probably want to use this approach).

GolfScript (49 48 46 chars)
{0\@{}{@2*2$2$>!+@@{{\}3$)*}:j~1$-j}/\)\,?}:f;

or
{0:x;\{}{.2$<!2x*+:x){\}*1$-{\}x)*}/x@)@,?}:g;

Both are functions which take the numerator and denominator on the stack and leave the numerator and denominator on the stack. Online demo.
The core idea is expressed in pseudocode in Concrete Mathematics section 4.5 (p122 in my edition):
while m != n do
    if m < n then (output(L); n := n - m)
             else (output(R); m := m - n)

If the string of Ls and Rs is interpreted as a binary value with L=0 and R=1 then twice that value plus one is the numerator, and the denominator is one bit longer.
As a point of interest to Golfscripters, this is one of those rare occasions when I've found unfold useful. (Ok, I only use it as a loop counter, but that's better than nothing).

Python 3, 98 83 bytes
f=lambda a,b,n=1,d=2:a>b and f(a-b,b,n*2+1,d*2)or a<b and f(a,b-a,n*2-1,d*2)or(n,d)

Try it online!
Explanation: The sequence of turns starting from 1 down to the given fraction in the Stern-Brocot tree is identical to the sequence of turns starting from the given fraction going to 1 in the Calkin-Wilf tree. This makes it much simpler to get the sequence.
Improvement given by Bubbler. Original solution here.

Welcome to Code Golf, and nice answer!

Quick suggestions: You don't need parens in while and if clauses, and a!=b is equivalent to a-b being nonzero (and hence truthy). Also, a,n=a-b,n+1 can be shortened to a-=b;n+=1. This gives 91 bytes.

A recursive lambda also works here. Check out Tips for golfing in Python for more tips like this.

Ruby (69 chars) CoffeeScript (59 chars)
This is a function which takes numerator and denominator as arguments and returns an array containing the numerator and denominator after the bijection.
g=(a,b,x=0,y=1)->c=a>=b;a&&g(a-b*c,b-a*!c,2*x+c,2*y)||[x,y]

Online demo
It uses the same approach as my GolfScript solution above, but is much more readable because I can use 4 variables without having to worry about boxing and unboxing into an array. I chose CoffeeScript because it doesn't prefix variables with $ (20 chars saved over e.g. PHP), has short function definition syntax which allows default parameter values (so there's no need to wrap f(a,b,x,y) in a function g(a,b) = f(a,b,0,1)), and lets me use Booleans as integers in expressions with useful values. For those who don't know it, CoffeeScript doesn't have the standard C-style ternary operator (C?P:Q), but I'm able to substitute C&&P||Q here because P will never be falsy.
An arguably more elegant, but inarguably less short, alternative is to replace the repeated subtraction with division and modulo:
f=(a,b,x=0,y=1,p=0)->a&&f(b%a,a,(x+p<<b/a)-p,y<<b/a,1-p)||[x+p,y]

(65 chars; online demo). Writing it this way exposes the relationship with Euclid's algorithm.

You don't need the parentheses around a<b which saves you one char. Inlining c gives another two. You may also consider the syntax f=->a,b,x=0,y=1{...} for even shorter definition.

@Howard, I don't know which version of Ruby you're using, but on IDEOne I get a syntax error if I try removing those parentheses or using that function syntax.

Try c=a<b ? with an extra space after b. Otherwise the questionmark is treated as part of the b.

Ruby, 132 125
Rubied & golfed the reference solution from @JoeZ.
def t(n,d)u=k=0;v,j,f,g,b=[1,]*5;c=2
while(z=(f*d).<=>(g*n))!=0;z>0?(j,k=f,g):(u,v=f,g);b=b*2-z;f,g=u+j,v+k;c*=2;end
[b,c]end

Usage examples:
>> t(2,3)
=> [3, 8]
>> t(4,7)
=> [9, 32]
>> t(1,1)
=> [1, 2]

Mathematica, 130 114 111 chars
f=#~g~0&;0~g~q_=q;p_~g~q_:=g[#,(Sign[p-#]+q)/2]&@FromContinuedFraction[ContinuedFraction@p/.{x___,n_}:>{x,n-1}]

Example:
f[2/3]

3/8

f[4/7]

9/32

f[1]

1/2

Mathematica 138
Not as streamlined as alephalpha's procedure, but it was the best I've been able to produce so far.
q_~r~k_:=Nest[#+Sign@k/(2Denominator@# )&,q,Abs@k]
g@d_:=
Module[{l=ContinuedFraction@d,p=-1},
l[[-1]]-=1;
(p=-p;# p)&/@l]
h[q_]:=Fold[r,1/2,g@q]

Testing
h[2/3]
h[4/7]
h[1]

3/8
9/32
1/2

Haskell, 125 bytes
n((a,b):(c,d):r)=(a,b):(a+c,b+d):n((c,d):r)
n a=a
z=zip[0..]
t x=[(j,2^i)|(i,r)<-z$iterate n[(0,1),(1,0)],(j,y)<-z r,x==y]!!0

Try it online!
Input and output in the form of a pair (n,d).
Brief Explanation:
n constructs the next row from the previous one by looking at each pair of fractions and inserting the new one between the first and the recursion (which will put the second fraction right there). The base case is very simple since it's basically just the identity function. The t function iterates that function indefinitely based off the initial state with just the two boundary fractions. t then indexes each row (i) and each item in the row (j) and looks for the first fraction that matches what we're looking for. When it finds it yields j as the numerator and 2^i as the denominator.

Python - 531
An ungolfed solution in Python, to serve as a last-place reference solution:
def sbtree(n, d):
    ufrac = [0, 1]
    lfrac = [1, 0]
    frac = [1, 1]
    bfrac = [1, 2]
    while(frac[0] * d != frac[1] * n):
        if(frac[0] * d > frac[1] * n):
            # push it towards lfrac
            lfrac[0] = frac[0]
            lfrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 - 1
        elif(frac[0] * d < frac[1] * n):
            # push it towards ufrac
            ufrac[0] = frac[0]
            ufrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 + 1
        frac[0] = ufrac[0] + lfrac[0]
        frac[1] = ufrac[1] + lfrac[1]
        bfrac[1] *= 2
    return bfrac

It simply does a binary search between fractions, taking advantage of the fact that the mediant of any two fractions will always between the values of those two fractions.

GolfScript, 54 characters
'/'/n*~][2,.-1%]{[{.~3$~@+@@+[\]\}*].2$?0<}do.@?'/'@,(

Input must be given on STDIN in the form specified in the task. You may try the code online.
> 4/7
9/32

> 9/7
35/64

> 5/1
31/32

JavaScript 186
f=(p1,q1,p2,q2)=>{if(p1*q2+1==p2*q1){return{p:p1+p2,q:q1+q2}}let p,q,pl=0,ql=1,ph=1,qh=0;for(;;){p=pl+ph;q=ql+qh;if(p*q1<=q*p1){pl=p;ql=q}else if(p2*q<=q2*p){ph=p;qh=q}else return{p,q}}}

could be less, but I like readable golf

source: Stack Exchange

license: 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/

sort: votes


text:
Decide Goldbach's conjcture
Your job is to write a program that determines if Goldbach's conjecture is true. The requirements are this:

If it is true: Print nothing. Run forever.
If it is false: Print the first counterexample. Halt.

Shortest code wins, but show why it works. Don't use any Prime built-in functions.
Edit: If you want, include another version that just adds a line that prints what even number you've found a solution to help explain your answer. (It should print 2,4,6,...).
Note: If the conjecture get proven or disproven conclusively, then this will become irrelevant, and I might change it to some other similar open problem.

This is (currently) impossible. It is unknown whether the conjecture is true, so we can't print an answer based off of it. Do you mean to test the conjecture on an input?

@Quincunx it is not said the program must terminate.

Without a solution to the underlying mathematical problem, we really have no way of knowing what this program's output should be. We can generally judge whether a program should or should not function correctly in theory, but we have no way of knowing whether or not it will meet the requirements until we know what (if any) the upper bounds of the conjecture are. Wikipedia says that it's been verified up to 4*10^18, which will fit into a signed 64-bit integer. But, without a solution to the problem, we have no way of knowing whether answers here need to account for numbers beyond int64.

Well then you have to account for larger numbers.

Also, why the requirement not to use any prime functions? Brute-forcing an unsolved mathematical problem is hard enough, and you want to pile on primality testing along with it?

It shouldn't be that difficult to write a prime tester. I didn't want languages with prime-testing built-in to have an advantage.

True, false, undecidable, and unknown seem to be the four possibilities. You only mention the first two.

@DavidCarraher If it's undecidable, then it's true, and you must run forever.

@ike Undecidable != true. Undecidable simply means it is impossible to prove truth or falsehood.

@Iszi See http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable

It is true but cannot be proven if it is undecidable.

There is no way to subject entrees to a test as to whether they complete successfully.

There is no automated way, however humans are smarter than turing machines. I will judge them.

And do you know that you can evaluate every language in which a submission might be made. We've had APL, fish, and a whole host of languages from the Turing tarpit in addition to postscript, forths, dc, and so on.

Well if it's a language I don't know I might need someone else to judge. That's why I asked you to explain it.

This question is asking people to code-golf a program that won't terminate. The kerfufle over possible program outcomes, and undecideability is moot: We all know these programs won't terminate. The issue about automated testing doesn't matter much: Most question posers don't have the facility, time, or inclination to test submitted solutions in off-beat languages. We just rely on the programmer's self-reported output to prove it works. Here there'll be no output - but I don't think that really is a big issue- we generally take it all on trust anyway!

This question appears to be off-topic because it's shape-shifting.

What more information do you want?

@MtnViewMark, you claim, "We all know these programs won't terminate."  Oh, do we?  ;-)

@DarrenStone As the conjecture has yet to be proven or disproven, strictly speaking, we don't - therein lies 83.6% of our problem.

We know that any modern computer will die before it hits the 4*10^18 mark.

@ike Any program that's written to validate or disprove Goldbach by brute-force would be well-served to start beyond that mark, as numbers below it have already been confirmed. Another thing to consider is that conjectures like this, strictly speaking, cannot be authoritatively proven by brute-force alone since the expected limit is infinity. Eventually, this means we must be able to process numbers like Graham's with precise accuracy - which is not only impossible with current technology, but theoretically impossible altogether!

Well if you're trying to golf it then you're better off starting from the beginning so as not to waste space.

Ruby, 94
require'Prime'
(4..1/0.0).step(2){|x|p=Prime.take x
p x if p.product(p).all?{|y|y[0]+y[1]!=x}}

VERY VERY slow and inefficient. Finds all possible sums of primes less than the number, and recalculates the primes each iteration! :D
Change .all? to .any? to see all non-counter-examples (?), which is all even numbers > 2 :P

Added requirement not to use prime functions.

@ike voted to close because of that

Ruby, 85 (incomplete)
I submit this as a partial answer to the question.
The following program will run until it determines that Goldbach's conjecture is solved. It will then exit and print nothing. I have not yet coded the counterexample-printing in the case of falseness.
require'open-uri'
while/Goldbach's conjecture/=~open('http://goo.gl/fuJLr1').read;end

Please enjoy.  :-)

aaand... what's the code length?

Befunge - 0
Works up until the 4 * 1018 iteration of the loop; after that, I am not sure:

Okay, okay; here is a valid Python solution (236 chars):
import sys
def p(a):
 for i in g():
    if a%i!=0:return 0
 return 1
def g():x=2;while 1:x+=1;yield x
for i in g():
 for x in g():
    for y in g():
     if y+x>i:break;if p(x)*p(y):x=i+1
    if x-i:print i;sys.exit()
    if x>=i:break;

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


text:
Output the correct move as per the XKCD tic-tac-toe cheetsheet!
Overview
This is the XKCD tic-tac-toe cheetsheet:

It's rather big, I know. But it's also your most valuable resource in your challenge.
The challenge
Create a program (in your language of choice) that uses the Optimal Move Cheatsheet (henceforth OMC) to output the optimal move when given a sequence of moves.
The input
Your program will be fed a series of moves in the following fashion:
A3 A2 B2 C2 ...

Where the first combination is always X, the second O, and so on. The letter is the Y coordinate (A-C, A at the top) and the number is the X coordinate (1-3, 1 at the left).
You may assume that the given combination is following the OMC's suggestion for each move at least for the player asking for a recommendation. You can also assume that the input will never be null (at least one move has been made). You must:

Figure out whether the next move is for X or O (you don't need to output this)
Use the OMC to decide the next move
Print the next move in the standard format A3

Optional:
You may also include the player's chance of winning (as a percentage) for 50 character discount on your score.

related: http://codegolf.stackexchange.com/questions/12226/build-a-perfect-ai-for-the-game-15/12234#12234

"The letter is the Y coordinate, and the number is the Y coordinate". Also, do we have to use that sheet, or can we use a different method for optimal moves? Also, your question is a bit confusing. How are we supposed to find the next move if it is already given for us? What is the "percentage chance" bit? Also, should this be tagged code-golf?

@Quincunx Ah! I forgot to fix the Y, Y thing in my edit, and now it would be a minor edit. I think, based on the premise of the question, alternate choices for optimal moves are not valid here. The "percentage chance" is probably the percentage of end-game scenarios from the current position (presuming the player takes the output move) in which the player can win. For example: A1, C3 should return A3 (100%).

In fact, it appears that all scenarios should return 100% win chance for X except for those beginning A1, B2.

Another example win percentage: A1, B2, C3, B3 should output A2 (80%) as there are five end-game scenarios from this position and four are wins for X.

@Iszi I fixed the X/Y thing. Thanks! ;)

Myself, I'd have made the positions simply 1 through 9. Top: 123, Middle: 456, Bottom: 789. But I'm not sure whether breaking the X/Y coordinates out might actually help things more than I think.

Must we assume that the incoming list of moves is from the optimal list? What if the first move is B2, not A1?

@LegoStormtroopr You don't have to, but you can.

@LegoStormtroopr It is said already that the current player can be assumed to have followed the optimal path thus far. This means that any input where X is the current player will start with A1, but any input where O is the current player may start with anything.

This is seriously making my brain hurt. I'm over 350 characters in PowerShell already, and that's just for A1 A2 and A1 A3 plus some empty top-level switches waiting to be filled in. There's got to be a better way to do this... especially for the O board!

How does the move input vs what I'm supposed to output work? I'm seriously confused. It seems like you are inputting all of the moves, but I have to figure out the next one? But all the moves follow OMC, so what is the percentage thing? How do I know which person is asking for the recommendation?

I'm not sure what's not clear here. Maybe we need to put this on hold while the bugs get worked out in the Sandbox? @Quincunx Only the moves of the current player are assumed to follow OMC. So, any input where X is next to move will start with A1. Any input where O is next to move will start with XY B2 (where XY is any of the possible first moves for X) except for B2 A1. Figuring out whose turn it is is simple. Just take the count of moves in the input, mod 2. Remainder of zero, it's X's turn - remainder of 1, it's O's.

@Quincunx The "percentage" thing is, as I mentioned earlier, the percentage of remaining end-game scenarios in which the player requesting a move can win. You do not assume the opponent will follow the OMC, only the current player.

@Undo Do we have to account for a null input - that is, X wants to know what their first move should be? Also, do we need to just figure out whose move it is, or should that be included in the output as well?

@Iszi You don't need to account for null input (assume that at least one move has been made), and you don't need to show who's move you're solving for (we assume the player already knows that.)

@Undo s/a few moves/at least one move for clarity. Otherwise, "a few" is ambiguous and can lead to confusion.

As noted here there is at least one error in the image. At A1 A3 B1 C3, the picture for O moving on B2 is the same as B3. The recommendations are still valid, but the image representing the endgame scene for O moving on B2 are inaccurate. Anyone else got time to go through that with a fine-toothed comb and make sure we don't actually have some bad recommendations?

Found another bug in the chart. In X's section, after A1 B2 C3 A2 C2 all of the recommendations except for where O moves to C1 point to X moving on C2 (already done in the previous move). The end-game boards all correctly show a win with X going across the bottom, but the last move should be C1.

I think I'm actually going to go ahead and join the VtC party on this one. Apparently, some people think the rules are a little un-clear and there also needs to be a thorough review of the chart so that errors can be addressed. Also, I think it really would be best if the squares would be labeled numerically (top row 123, middle 456, bottom 789). As it is, I've got 73 characters used up at the start of my current draft just to simplify the coordinates so they can be addressed with less characters later. I suggest working out the bugs in Sandbox and re-opening or re-posting this after edit.

Please don't delete just yet, though - at least not until a copy is in the Sandbox.


text:
Give a multiple choice test
I present to you a test! Your test is to test. The test is to test the testee with tests a tester gives you, in the shortest amount of code. Specifically, you will give a multiple choice test that you have recieved as input.
In this challenge, you must take an input like this:
1. Our site is called Programming Puzzles & Code ________.
A: Debugging
*B: Golf
C: Hockey
D: Programming
2. What is the *most* popular tag on our site?
A: [debug]
B: [program]
*C: [code-golf]
D: [number]
E: [c++]
3. We are part of the ________ Exchange network.
*A: Stack
B: Code
C: Programmer
D: Hockey
4. Is this the first question?
A: Yes
*B: No
5. Is this the last question?
*A: Yes
B: No

And here is an example of the test being taken:
1. Our site is called Programming Puzzles & Code ________.
A: Debugging
B: Golf
C: Hockey
D: Programming
answer: B
correct!

2. What is the *most* popular tag on our site?
A: [debug]
B: [program]
C: [code-golf]
D: [number]
E: [c++]
answer: C
correct!

3. We are part of the ________ Exchange network.
A: Stack
B: Code
C: Programmer
D: Hockey
answer: B
incorrect! the answer was A

4. Is this the first question?
A: Yes
B: No
answer: B
correct!

5. Is this the last question?
A: Yes
B: No
answer: B
incorrect! the answer was A

overview:
3 correct, 2 incorrect (60%)

3. We are part of the ________ Exchange network.
you chose B: Code
the answer was A: Stack

5. Is this the last question?
you chose B: No
the answer was A: Yes

Formal specification:

Input

If a line begins with a number followed by a dot and a space, it is a question with that number. Numbers will always start from 1 and go up 1 each question.
If a line begins with an optional asterisk, a letter, a colon, and then a space, it is an answer. Answers will also always be sequential. There will be only one correct answer per question.
A line will not begin in any other way than the previously mentioned ways.
Input may be accepted in any way (reading from a file, stdin, etc.) but must not be hardcoded into your program.

Output (test-taking phase)

First, print out each question sequentially. Print the question and its answers as recieved in input, but do not print the asterisk indicating correct answers.
Then, print a newline and "answer: ". Wait for user input. User input will always correspond to an answer.
If the correct answer (the one with an asterisk) is the same as the one the user input, output "correct!". Otherwise, output "incorrect! the answer was " + correct_letter.
Separate each question with a blank line, then repeat the previous output steps until there are no more questions.

Output (overview phase)

Print "overview: " and then a newline.
Print "{number of correct answers} correct, {incorrect answers} incorrect ({percent correct, rounded to the nearest whole number}%)" (of course substituting the phrases in curly braces with their respective values). Then print a blank line for spacing.
Now, for each question that was wrong, print the question (not its answers), then on a new line "you chose " + answer_you_chose, and on another line "the answer was " + correct_answer. Separate each wrong answer's overview with a blank line.

In order to reduce cheating by interpreting things literally, when given the same output here, and the same input in the test-taking phase, your program must output exactly the same thing as the sample output.

This is code-golf; shortest code wins! (And gets an A+ (green checkmark)!)

Nice challenge, but I wish the sample test to contain possibly tricky situations, like \d\. , \w:  and \* in the middle of questions/answers. (For example currently the * can be eliminated with y/*//, while the correct way is lengthy as s/^\*//.)

Do we need to allow line continuation? I mean, will there be lines not starting with “1. ” or “A: ”? If yes, please include such cases in the sample test.

@manatwork (first comment) Ok, editing (second comment) no, you do not. I will clarify.

So how are you going to test this test test?

@JoeZ. Umm... not sure what you mean... I did provide a test test case for the test to test your tester

That is true. My bad.

and the end, when printing out incorrect answers - what do you want printed if the user entered a non-option? Like say the user entered 'Q' to any of the questions above?

@Mtn I have specified that you can assume they will not.

Perl 5, 279
$y=correct;@w=(the,$n=answer,was);map{s/^\*((.+?):.+)/$a=$1/me;print"$_$n: ";chop($@=<>);print$@eq($l=$2)?++$d&&"$y!

":(/^\d.+/,$o.=$&,/^$@.+/m,$o.="
you chose: $&
@w $a

")&&"in$y! @w $l

"}@_=split/(?=^\d)/m,join"",<>;printf"overview:
$d $y, %d in$y (%d%)

$o",@_-$d,$d/@_*100

Note: The newlines are required for output formatting.
Every time I think I can't golf it any more, I learn something new! It's slowly becoming more punctuation than legible text... I think that's a good thing?
Usage: perl -e '...' test.txt or perl test.pl test.txt.
If you choose an option not presented in the list, you will get incorrect output in the overview (it will say you chose: 1. Our site is called Programming Puzzles & Code ________. for example).
Example run

Kindly show an example of input and output.

@DavidCarraher added an updated link to output via showterm.io. Thought that would be marginally better than static output, although it still doesn't capture it exactly the same as it is in the terminal.

That gives a fairly good view of how your program works.

Mathematica 144
This may be an invalid attempt. I separated the question from each answer in the input. I also indicated the correct answer by a letter in a separate field, rather than an asterisk before the alternative.
Anyway...
The Data
questions={{{"\n1. Our site is called Programming Puzzles & Code ________.\n","A: Bugging\n","B: Golf\n","C: Hockey\n","D: Programming\n"},"B"},{{"\n2. What is the most popular tag on our site? \n","A: [debug]\n","B: [program]\n","C: [code golf]\n","D: [number]\n"},"C"},{{"\n3. We are part of the _______ Exchange network. \n","A: Stack\n","B: Code\n","C: Programmer\n","D: Hockey\n"},"A"},{{"\n4. Is this the first question? \n","A: Yes\n","B: No\n"},"B"},{{"\n5. Is this the last question? \n","A: Yes\n","B: No\n"},"A"}};

Code
An answer to each question is entered through a dialog box.
Questions, answers, and feedback are printed.
f@x_:=
Print[If[((r=ChoiceDialog[Print[""<>#,"\nanswer: "];""<>#,StringTake[Rest@#,1]])==#2),
r<>"\ncorrect!", r<>"\nincorrect, the answer is "<>#2]&@@x]

Test
f /@ questions

wow, impressive! the input is not in the correct form though... still, that is very remarkable for the brevity of the code and how much it does!

Thanks. Massaging the input string into a Mathematica-friendly structure is of course possible, but it would have hidden the elegance underlying the present, ineligible solution.

Nice.  Four characters shorter: g@{a_,b_}:=Print[If[(r=ChoiceDialog[Print[""<>a,"\nanswer: "];""<>a,Rest@a~StringTake~1])==b,r<>"\ncorrect!",r<>"\nincorrect, the answer is "<>b]]

And save one more by using Print@If[...] rather than Print[If[...]].

Java - 1210
int i,o;String q;String[]s={"1. Our site is called Programming Puzzles & Code ________.\n","2. What is the most popular tag on our site?\n","3. We are part of the ________ Exchange network.\n","4. Is this the first question?\n","5. Is this the last question?\n"},b={"B","C","A","B","A"},p=new String[5];String[][]a={{"A: Debugging\n","B: Golf\n","C: Hockey\n","D: Programming\n","answer: "},{"A: [debug]\n","B: [program]\n","C: [code-golf]\n","D: [number]\n","E: [c++]\n","answer: "},{"A: Stack\n","B: Code\n","C: Programmer\n","D: Hockey\n","answer: "},{"A: Yes\n","B: No\n","answer: "},{"A: Yes\n","B: No\n","answer: "}};java.util.Map<String,Integer>m=new java.util.HashMap(){{put("A",0);put("B",1);put("C",2);put("D",3);put("E",4);}};java.util.Scanner u=new java.util.Scanner(System.in);for(i=0;i<5;i++){q=s[i];for(o=0;o<a[i].length;)q+=a[i][o++];System.out.print(q);if(b[i].equals(p[i]=u.nextLine()))q="correct!";else q="incorrect! the answer was "+b[i];System.out.println(q+"\n");}q="";o=0;for(i=0;i<5;i++)if(b[i].equals(p[i]))o++;else q+=s[i]+"you chose "+a[i][m.get(p[i])]+"the answer was "+a[i][m.get(b[i])]+"\n";System.out.println("overview:\n"+o+" correct, "+(5-o)+" incorrect ("+o*100/5+"%)\n\n"+q);

formatted: 1980
String[] s = {"1. Our site is called Programming Puzzles & Code ________.\n",
        "2. What is the most popular tag on our site?\n",
        "3. We are part of the ________ Exchange network.\n",
        "4. Is this the first question?\n",
        "5. Is this the last question?\n"};
    String[][] a = {
        {"A: Debugging\n", "B: Golf\n", "C: Hockey\n", "D: Programming\n", "answer: "},
        {"A: [debug]\n", "B: [program]\n", "C: [code-golf]\n", "D: [number]\n", "E: [c++]\n", "answer: "},
        {"A: Stack\n", "B: Code\n", "C: Programmer\n", "D: Hockey\n", "answer: "},
        {"A: Yes\n", "B: No\n", "answer: "},
        {"A: Yes\n", "B: No\n", "answer: "}};

    java.util.Map<String, Integer> m = new java.util.HashMap<String, Integer>() {
        {
            put("A", 0);
            put("B", 1);
            put("C", 2);
            put("D", 3);
            put("E", 4);
        }
    };
    String[] b = {"B", "C", "A", "B", "A"};
    String[] p = new String[5];
    java.util.Scanner u = new java.util.Scanner(System.in);
    String q;
    int i;
    int o;
    for (i = 0; i < 5; i++) {
        q = s[i];
        for (o = 0; o < a[i].length;) {
            q += a[i][o++];
        }
        System.out.print(q);
        if (b[i].equals(p[i] = u.nextLine())) {
            q = "correct!";
        } else {
            q = "incorrect! the answer was " + b[i];
        }
        System.out.println(q + "\n");
    }
    q = "";
    o = 0;
    for (i = 0; i < 5; i++) {
        if (b[i].equals(p[i])) {
            o++;
        } else {
            q += s[i] + "you chose " + a[i][m.get(p[i])] + "the answer was " + a[i][m.get(b[i])] + "\n";
        }
    }
    System.out.println("overview:\n" + " correct, " + (5 - o) + " incorrect (" + o * 100 / 5 + "%)\n\n" + q);

This certainly won’t be the shortest but it is all self-contained

Haskell, 598
import System.Environment
import System.IO
n=putStrLn
p=putStr
d#s=p$show d++s
v&(m:a)=n m>>q[]""a>>= \(r,(s,t))->n s>>n"">>b v m t&r
(r,w,s)&[]=n"overview:">>r#" correct, ">>w#" incorrect (">>((100*r)`div`(r+w))#"%)\n">>mapM_ n s
b(r,w,s)m t|null t=(r+1,w,s)|1<3=(r,w+1,s++"":m:t)
q u c(('*':a):r)=q u a(a:r)
q u c(a@(o:':':_):r)=n a>>q(([o],a):u)c r
q u c r=p"answer: ">>hFlush stdout>>(\i->(r,a(maybe i id$lookup i u)c))`fmap`getLine
a j c|j==c=("correct!",[])|1<3=("incorrect! the answer was "++[head c],["you choose "++j,"the answer was "++c])
main=getArgs>>=readFile.head>>=((0,0,[])&).lines

Way longer than I'd like. It's set wiki so have at it!
Alas, we lose 32 characters to flushing stdout. Another 38 characters could be saved if the test script were read from a fixed file named "t" rather than specified on the command line.
When run on the input given in the question:
& runhaskell 15961-Tester.hs 15961-test.txt
1. Our site is called Programming Puzzles & Code ________.
A: Debugging
B: Golf
C: Hockey
D: Programming
answer: B
correct!

2. What is the *most* popular tag on our site?
A: [debug]
B: [program]
C: [code-golf]
D: [number]
E: [c++]
answer: C
correct!

3. We are part of the ________ Exchange network.
A: Stack
B: Code
C: Programmer
D: Hockey
answer: B
incorrect! the answer was A

4. Is this the first question?
A: Yes
B: No
answer: B
correct!

5. Is this the last question?
A: Yes
B: No
answer: B
incorrect! the answer was A

overview:
3 correct, 2 incorrect (60%)

3. We are part of the ________ Exchange network.
you choose B: Code
the answer was A: Stack

5. Is this the last question?
you choose B: No
the answer was A: Yes


text:
Capitalize String
Given a string, capitalize it. By capitalization I mean conTeNT-lENgth changes to Content-Length. In the example I showed the string with 2 words with - as the word boundary. However I expect you to write the code for the string containing any number of words separated by a single character as the boundary. This boundary may change across the string.
Conditions

using regular expressions is not allowed.
there could be any number of words in a sentence(string).
each word will consist of English letters[a-zA-Z] of any case.
different words in the sentence will be separated by a single character. This character will only be any one of -, .,  , /, &, #. You can safely assume that sentence will not contain any other character except the mentioned ones.
word boundaries should be preserved in the output.
shortest code wins.

For example your program should output Begin/With.Type&Content for BeGin/wITH.tyPE&conTeNt.
Some test cases:
 "aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe"
 "type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe"
 "cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc"
 "lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT"
 "contENT/ACcEpT"
 "BeGin/wITH.tyPE&conTeNt"
 "Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with"
 "RaNgE&COnTeNT WITh CoNTENT-TypE tyPe"
 "BEgin COdE#uSeR#aGeNt.USeR"
 "TypE LENGth"

What you call capitalization is actually a transformation to camel-case.

@ArlaudPierre No, what he's given as "test cases" are more like camel case. What's being called capitalization is closer to Title Case.

Can you please provide the expected output for the test cases? It seems some built-in functions may assume that all-caps words (like /CC/ in line 2, or -AND& in line 7) should be left alone. Is this ok, for this challenge?

Does the input always begin with a word or it may start with a separator?

GolfScript, 36 27 19 characters
0\{95&+.47>32*\}%\;

A quite basic GolfScript approach which works for all input according to the specification. The examples can be tested online.

Cool. Was curious whether my solution is at least twice as a professional one. :) But I am sure you will shorten this several times before the day ends.

@manatwork Now we have a factor of two ;-) Still unhappy with all the swaps.

I knew you will not disappoint me.

Python 3,22
print(input().title())

This code will take a string as input from stdin and gives a capitalized output to stdout.
for example:
input:
BEGIN/wITH.tyPe&cOnTENt

ouput:
Begin/With.Type&Content

The following code is for multi-line inputs (if necessary)
Python 3, 46
import sys
for i in sys.stdin:print(i.title())

while 1:print(input.title()) is a shorter equivalent for the last piece of code.

@RamchandraApte I'm not sure is it allowed or not. Your code will die with an EOFError as soon as its hits the EOF

I think the general consensus for golfs is that as long as the output is correct, errors don't matter

Dang; as soon as I saw this question, I thought of this, but you beat me to it. +1

+1 I like this better than the golfscript one because it doesn't look like an obscenity.

05AB1E, 1 byte
Code:
™

Explanation:
™   # Implicit input which is converted to title case.

Try it online!

That's pretty cool :-)

JavaScript (94)
prompt().split(l='').map(function(a){return l='A'>l?a.toUpperCase():a.toLowerCase()}).join('')

Why not arrow functions? Edit: I just realised that this is from 2013

Mathematica 62
Data
tests={"aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe","type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe","cc/rEspoNCe.lEngtH#tYpEwitH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc","lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT","contENT/ACcEpT","BeGin/wITH.tyPE&conTeNt","Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with","RaNgE&COnTeNT WITh CoNTENT-TypE tyPe","BEgin COdE#uSeR#aGeNt.USeR","TypE LENGth"}

Code
StringReplace[ToLowerCase@#,WordBoundary~~x_:>ToUpperCase@x]&

Usage
f["aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe"]

"Agent Accept/Length-Type User Range.Type"

f /@ tests

{"Agent Accept/Length-Type User Range.Type",
"Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code",
"Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc",
"Length#User.Type/Begin&Length  Type/Accept#Range/Code&And-Accept/Content", "Content/Accept",
"Begin/With.Type&Content",
"Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With",
"Range&Content With Content-Type Type",
"Begin Code#User#Agent.User",
"Type Length"}

-1 That's basically regex

Mathematica can run regex directly but I used something else.  It's similar to regex, but it is not regex.

%% %%% % %%

PHP : 78 73 65 64 characters
$b=ucfirst;foreach(str_split($s)as$c)echo$b($c),!$b[0]=$c<A?u:l;

Input is passed in $s. It operates on the string as an array of characters.
It is a simple 2 state machine. It relies on lexical ordering of strings, and that the parser automatically assumes you meant to type a string in some cases.
The state is being stored in $b and is being represented as the name of the function that needs to be called on the next character. ucfirst and lcfirst are shorter to type and have identical behaviour to strtolower/strtoupper on single character strings. Also, since they only differ by one letter, we can use them efficiently to store the state. The original version needed to store the state explicitly in a boolean.
Since echo doesn't print anything for boolean false, I used a comma and the ! operator to "hide" the assignment(which in this case is truthy) in the echo statement. This allowed me to save a character by removing the {}.

Please use code block markup instead of inline code, so scripts like Code Golf UserScript Enhancement Pack can insert the size below the code. By the way, in your code all 3 space characters can be removed.

Instead of $b=ord($c)>64; try $b=$c>"@";. Or even $b=$c>=A; – AFAIR that throws a warning, but good coding practices are not a virtue here.

@manatwork thanks, didn't think of that. I am already throwing a warning for using an unset variable anyway.

Hmm… What about not using $b just as a flag, but storing the actual function name in it? $b=ucfirst;foreach(str_split($s)as$c){echo$b($c);$b[0]=$c>=A?l:u;}.

@manatwork great! I was trying to think of a way to do that with the function. My tries were all bigger.

Actually there is one more character that you can remove by reversing the ternary: $c<A?u:l.

Powershell: 37 - 43
Depending on how you want to take the input...
Prompt the user for input: 43
(Culture).TextInfo.ToTitleCase((read-host))

Take input from pipeline: 38
(Culture).TextInfo.ToTitleCase($input)

Provide input as an argument when running the script: 37
(Culture).TextInfo.ToTitleCase($args)

NOTE: The above scripts will ignore all-caps words, leaving them as-is. If this needs to be accounted for, the input should be forced to lower-case before the Title Case conversion. This adds 10 characters to the first method, and 12 to the other two.
(Culture).TextInfo.ToTitleCase((read-host).ToLower())
(Culture).TextInfo.ToTitleCase("$input".ToLower())
(Culture).TextInfo.ToTitleCase("$args".ToLower())

Does not work according to the specification. Try foo:bar.

@Mormegil Which one? The read-host version, at least, works fine for me. I tested it against all the test cases in the question and they all returned as expected except for the special cases I posted in comment to the question.

: (colon) is not listed as a word separator in rule #4, therefore, AFAICS, foo:bar should result in Foo:bar, not Foo:Bar. But that is just my (quite strict) reading of the specification.

@Mormegil Ah, but an equally strict interpretation could also be that the rule does not provide an exclusive list. That is, it says the separator "could be any one of..." as opposed to "can only be any one of...".

Fair enough. The specification is quite hazy, anyway. :-)

@Mormegil Well, this is neat. Looks like the spec was tweaked to resolve that ambiguity, while at the same time not invalidating this answer.

You can replace get-culture with culture; see http://codegolf.stackexchange.com/a/778/1308

@DankoDurbić Ah, I keep forgetting that. Thanks.

C, 83
n;main(c){c=getchar();putchar(c>96?n?c:(n=c-32):c&64?n?c+32:(n=c):(n=0,c));main();}

Takes lines on stdin, translates them to stdout. (Prefers SIGINT to EOF.)

Java - 209 characters
class C{
public static void main(String[]a){
for(String b:a){
char[]k=b.toLowerCase().toCharArray();
for(int i=-1;i<k.length;i++){if(i<0||"-. /&#".indexOf(k[i])>=0)k[++i]=(char)(k[i]-32);}
System.out.println(k);}}}

I added newlines only for readability.

Ruby: 60 51 50 47 characters
$_.downcase.chars{|c|$><<$/=$/<?0?c.upcase: c}

Sample run:
bash-4.1$ for line in "${test[@]}"; do printf '%-75s | %s\n' "$line" "$( ruby -ne '$_.downcase.chars{|c|$><<$/=$/<?0?c.upcase: c}' <<< "$line" )"; done
aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe                                    | Agent Accept/Length-Type User Range.Type
type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe             | Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code
cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc          | Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc
lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT     | Length#User.Type/Begin&Length Type/Accept#Range/Code&And-Accept/Content
contENT/ACcEpT                                                              | Content/Accept
BeGin/wITH.tyPE&conTeNt                                                     | Begin/With.Type&Content
Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with           | Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With
RaNgE&COnTeNT WITh CoNTENT-TypE tyPe                                        | Range&Content With Content-Type Type
BEgin COdE#uSeR#aGeNt.USeR                                                  | Begin Code#User#Agent.User
TypE LENGth                                                                 | Type Length

Isn't l==l.swapcase the same as l<?0 (not tested)? At least for the input allowed for this task.

Yes. Now that batman emphasized that no other separators have to be expected, indeed that is shorter. Thank you, @Howard.

Befunge 98 - 24 45
~\j:'``!3*j' -;:'``b*j:'/`!3*j' +#;:,'/`!jc#@

Writing this hurt my brain.
This takes input through ~ and if the previous character was one of the separators (or if there was no previous character), it executes
:'``!3*j' -;

This snippet takes the character, and if its ascii value is greater than or equal to a, it subtracts 32 from it, thus changing it to upper case. If it is less than a, 3*j skips the adjustment. Afterwards, it skips the next part. This part handles changing from upper case to lower case (I'm sure it can be merged with the next part; I'm just not sure how):
:'``b*j:'/`!3*j' +#;

The character is printed (,), then this checks if the character is one of the boundaries:
'/`!

It basically compares the character to the ascii value of /. If the character is not a boundary, the code pushes 12 so that it will skip the capitalization adjustment the next time around. # skips over the end program: @, and if the end of the input is reached, ~ sends the code execution back to the @, ending the program.

R, 143 116
A solution a bit long maybe but here we go:
f=function(x){a=sapply(1:nchar(x),function(y)substr(tolower(x),y,y));d=c(1,which(!a%in%letters)+1);a[d]=toupper(a[d]);cat(a,sep="")}

Slightly ungolfed and explained:
f <- function(x){
    #Split the string in characters and "lower-case" everything
    a <- sapply(1:nchar(x),function(y)substr(tolower(x),y,y))
    #Select the first character and each character following a
    #character that doesn't belong to lower case alphabet
    d <- c(1,which(!a%in%letters)+1)
    #Make those ones uppercase.
    a[d] <- toupper(a[d])
    #Output (stdout) while pasting them back together.
    cat(a,sep="")
    }

Edit: 116 characters
The main challenge here is to vectorize substr. Here's another less verbose way.
f=function(x){n=1:nchar(x);a=mapply(substr,tolower(x),n,n);d=c(T,!a%in%letters);a[d]=toupper(a[d]);cat(a[n],sep="")}

Indented:
f <- function(x){
    n <- 1:nchar(x)
    a <- mapply(substr,tolower(x),n,n)
    d <- c(T,!a%in%letters) #This has been simplified as well
    a[d] <- toupper(a[d])
    cat(a[n],sep="") #Because a is now 1 char longer than x, need to subset a
    }

Usage:
> f("aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe")
Agent Accept/Length-Type User Range.Type

You can save some characters. Since a consits of lowercase characters only, there's no need to check for matches with uppercase LETTERS.

@SvenHohenstein indeed, thanks!

Another one: You can replace TRUE with T.

Originally i had the tolower later.

OK, here's another one ;-) You can replace mapply(substr,tolower(x),n,n) with strsplit(tolower(x),"")[[1]] to save one character.

@SvenHohenstein Ahah yes indeed. Although one would argue that argument split (here an empty string) is technically treated as a regular expression! :)

Good point! Unless you specify, fixed = FALSE, it's based on regular expressions.

Don't care to count but maybe the following is slightly shorter: x<-tolower(strsplit(x,"")[[1]]); u<-which(!x%in%letters); x[u+1]<-toupper(x[u+1]); cat(x,sep="")

Down to 105 bytes by using utf8toInt : function(x,y=utf8ToInt(x)){s=which(y<64);y[-s]=y[-s]%%32+96;m=c(1,s+(s>0));y[m]=y[m]%%32+64;intToUtf8(y)}

JavaScript (string->string), 67 bytes
s=>[...s].map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='').join``

Try it:

f=s=>[...s].map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='').join``

console.log(f('aGeNT aCcEpT/LEngTh-tYPe USeR raNgE.TyPe'));
console.log(f('type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe'));
console.log(f('cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc'));
console.log(f('lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT'));
console.log(f('contENT/ACcEpT'));
console.log(f('BeGin/wITH.tyPE&conTeNt'));
console.log(f('Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with'));
console.log(f('RaNgE&COnTeNT WITh CoNTENT-TypE tyPe'));
console.log(f('BEgin COdE#uSeR#aGeNt.USeR'));
console.log(f('TypE LENGth'));

Jacob's variant - JavaScript (char[]->char[]), 55 bytes
s=>s.map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='')

Try it:

f=s=>s.map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='')

g = s => f([...s]).join``

console.log(g('aGeNT aCcEpT/LEngTh-tYPe USeR raNgE.TyPe'));
console.log(g('type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe'));
console.log(g('cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc'));
console.log(g('lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT'));
console.log(g('contENT/ACcEpT'));
console.log(g('BeGin/wITH.tyPE&conTeNt'));
console.log(g('Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with'));
console.log(g('RaNgE&COnTeNT WITh CoNTENT-TypE tyPe'));
console.log(g('BEgin COdE#uSeR#aGeNt.USeR'));
console.log(g('TypE LENGth'));

Nice answer! You can save a couple bytes by using character arrays instead of strings, by the way.

@Jacob Thank you! Can you please show how?

Just get rid of the [...s] and the .join\``. It's fairly common practice on this site - see https://codegolf.meta.stackexchange.com/a/8964/108687. If you use this, just make sure to mention in the answer that it uses character arrays.

https://tio.run/##dVLRatswFH3fVxhcZAdm6X3DGa4inEBQjKswSilEVW4VF1c2lroQxr49vcrehvcmrs45Ovccvelf2pupG0PhhiNcX8urL5eevusx1@WyL/XTIQx3v7MqW/Y/sv04Zt@y7XDO/sDEtYfDc7742pdZtrjaEpmv@ROl1D8v6NvQucPhixmcH3qg/WBzm2e6BqkSzY0YFdsKZ9WpCI8NJPsHaJNJSyuoujSQLRbf/@WGywiksiAD45zxnQt4THrh6nBKteHQKHa7pm3laii4YagQhAvM7FazksawSfhxkBxH6Cas0/A4iuLchTXZezGxF2E3knw8wESrWjhFXsBuHNOciwZ9mDnVXkir1mlciUY5dg91J8lWSHSa4ARYhfwxpFMlLaDLoyCVWxU4BcyFD06BU7OG40IS97wlOIeIbzl23qg1DZdGEBPFZJiDcmycGpPuPW7Xg6uxDDQ9FZVckUhO1GUUpAeJwdBbTR9etBTxLcGITnOibeyQYDsqNv1zo04JH6RC00VUS8J/2r0XtnMJ3x1Fimm3afwpgcYM59A3qb@BxuvrJw

@Jacob Thank you! I read the all answers. But I think it is a big cheating to define second function which do some part of my function. The conditions say that my function must return a string and accept a string so I think it isn't fair to define another function which prepare data for main function and modifies the output

Well I would say it's fine, because the extra function is only used to make defining the test cases easier. You could still call f with an array of characters, it would just make the test cases harder to write. But if you feel like it's cheating then you don't need it

Alternatively, you can use s=>s.replace(/./g,a=>l=a[\to${'A'>l?'Upp':'Low'}erCase`](),l='')` for 64 bytes, it still takes and returns a string

@Jacob I can't use regexp because of  "using regular expressions is not allowed"

I don't think .replace(/./g,a=>) counts as using a regex in the terms of this challenge, because it's just a shorter method of using .split``.map(...).join, while the usage of regex specified in the challenge description bans using regex to solve the main part of the challenge

@Jacob I added your variant :)

C# – 110
A simple finite-state-machine-based processing:
x.Aggregate(new{b=1>0,r=""},(s,c)=>new{b="-. /&#".Contains(c),r=s.r+(s.b?Char.ToUpper(c):Char.ToLower(c))}).r

(where x is the string to capitalize)
and of course, if you want to be boring (after the specification was updated), you can use
new CultureInfo(9).TextInfo.ToTitleCase(x)

or, with all the boring boilerplate:
class C{static void Main(string[]a){System.Console.WriteLine(new System.Globalization.CultureInfo(9).TextInfo.ToTitleCase(a[0]));}}

Nah, won't compile as C# is no scripting language and you need to encapsulate this in a class.

Says who?
`Microsoft (R) Roslyn C# Compiler version 1.2.20906.1
Loading context from 'CSharpInteractive.rsp'.
Type "#help" for more information.

"foobar".Aggregate(new{b=1>0,r=""},(s,c)=>new{b="-. /&#".Contains(c),r=s.r+(s.b?Char.ToUpper(c):Char.ToLower(c))}).r
"Foobar"`
But if you really care about the boring boilerplate, add 112 characters of it.

You can cut the public and string[]a from the boilerplate

Oh yeah, you’re right with public, but I need the arguments, as that is what I process…

Forth, 135
: s swap ;
: c 1 begin key dup 96 > if s if 32 - then 0 s
else dup 64 > if s 0= if 32 + then 0 s then else 1 s then then emit again ; c

Translated output is written to stdout as it reads from stdin.

"then then emit again" rhyming with forth!

Javascript 102
prompt().split(o=q='').map(function(c){o+=(q)?c.toLowerCase():c.toUpperCase(),q=('A'>c)?0:1})
alert(o)

You need no (…) around the ternary condition. Even more, you not need the second ternary: function(c){o+=q?c.toLowerCase():c.toUpperCase(),q='@'<c}.

Befunge-98 (29), C (65)
Since the method/algorithm is pretty much the same, I include both versions in the same post.  Both rely on keeping track of whether the last character was a symbol or letter, in order to know whether to lowercase a letter or not.
Befunge-98 (29)
#@~:'0` #v_,0>
',++@'% '<   ^

C (65)
c,d;main(){for(;~(c=getchar());d=c>48)putchar(c<48?c:c&95|32*d);}

AWK, 113 103 98 bytes
{OFS=""
for(n=split($0,a,"");i<=n;s=a[++i]){$i=(L?tolower(s):toupper(s))
L=!(index("-. /&#",s))}}1

Try it online!
This works fine for single line content, but for multi-line input a few more inits need to be added
AWK, 104 bytes
{OFS=i=s=L=""
for(n=split($0,a,"");i<=n;s=a[++i]){$i=(L?tolower(s):toupper(s))
L=!(index("-. /&#",s))}}1

Try it online!
It would have been nice to take advantage of AWK's automatic splitting of a record into fields and modifying said fields, but that throws away the field separators. :(
This update throws away the idea of tacking characters onto a string and then printing the string. Instead, each character becomes its own field. Without the OFS="" bit, each character/field would be separated by a space when printed, which isn't what was requested.
Realizing that "" is essentially the same thing as 0 in AWK shortens the byte-count for the multi-line version a little bit. (I know it's different... I said 'essentially' :p )

Are you sure? None of the codes seems to produce the required output neither with gawk, mawk or original-awk. (Tested on Ubuntu.)

It was written using gawk on an RHEL6 box, but then transcribed to a windows box.  There could very well be a transcription issue.  I'll try testing after work when I  can do testing and posting on the same machine.... I think I see the issue, anyway.  l=0 should be L=0

Hopefully it works now, @manatwork . Thanks for the testing. :)

Now seems to work correctly. Not checked all test cases, but seems to be possible to reduce it a bit: {for(l=split($0,a,$0="");i<=l;s=a[++i]){$0=$0(L?toupper(s):tolower(s));L=index("-. /&#",s)}}1.

I like your use of changing $0 and the 1 label to avoid the print command are things I haven't thought of doing.  I'll have to keep it in mind for future golfing :)

Python 3, 122 bytes
lambda s:''.join(chr(ord(c)+[[0,0],[0,32],[-32,0]][('@'<c<'[')-('`'<c<'{')]['@'<p<'['or'`'<p<'{'])for c,p in zip(s,'-'+s))

Try it online!
Not a great score, but I wanted to try it without builtin string operations for case changing.

Excel VBA, 13 characters
In the Immediate window
?[Proper(A1)]

Function takes input from cell A1
VBScript
Set xlapp = CreateObject("excel.application")
wscript.echo xlapp.Evaluate("Proper(""BeGin/wITH.tyPE&conTeNt"")"

Could you provide some help on usage? I get “Compile error: External name not defined”. (In Word 2013 on the Developer tab I clicked Visual Basic, then in Visual Basic for Application I copy-pasted your code in the Immediate window and pressed Enter.)

@manatwork I should have clarified it was in Excel. You can do this from Word but the path is longer as you need to automate Excel.

Cool. Works perfectly when VBA is started from Excel 2013.

Works in directly in Excel as well: =PROPER(A1), also 11 bytes

QBasic, 74 bytes
1c$=LCASE$(INPUT$(1))
IF f=0THEN c$=UCASE$(c$)
f=c$>"@
?c$;
IF""<c$GOTO 1

Bytes are counted in CP-437;  is a single byte (character code 20).
The input method here is a bit strange: characters are typed one at a time, and their capitalization is converted before they are displayed. So when you type in aGeNT, it appears on screen as Agent. Hitting Enter ends the program.

Python 3, 9 bytes
str.title

Try it online!

Perl 5 + -pF, 42 bytes
$\.=~$=?uc:lc,$==index'?/.- &#',$_ for@F}{

Try it online!

Vyxal, 20 15 bytes
f:ʀĠ•ƛḣv⇩$⇧p;f∑

Try it Online!
Or, if that's too long:
1 byte
ǐ

Try it Online!
Explained
f:ʀĠ•ƛḣv⇩$⇧p;f∑
f:               # Push two copies of the letters of the input
  ʀ              # is each letter in the first copy in the alphabet?
   Ġ             # group that on consecutive elements - this has the effect of grouping words.
    •            # reshape the other copy of the letters to have the same shape as that
     ƛ           # to each sublist L:
      ḣv⇩        #     push L[0] and [lower(x) for x in L[1:]] - on single length strings this just leaves L[0] on the stack.
         $⇧p     #     uppercase L[0] and prepend it to the other list
            ;    # close map
             f∑  # deep flatten and summate to get a single string - the `d` flag would save 3 bytes here by removing this pair and allowing structure autocompletion to save a byte.

Go, 153 bytes
import."strings"
func f(s string)(o string){c:=0<1
for i:=range s{x:=s[i:i+1]
if c{o+=ToUpper(x);c=!c}else{o+=ToLower(x)}
c=Contains("-. /&#",x)}
return}

Attempt This Online!

Julia 1.0, 9 bytes
titlecase

Try it online!

Thunno, \$2\log_{256}(96)\approx\$ 1.65 bytes
zV

Attempt This Online!
Just a built-in solution.

JavaScript (Node.js), 54 53 bytes
Exact same score as the RegEx approach would have been!
s=>Buffer(s.toLowerCase()).map(x=c=>x=x>64?c:c^32)+``

Try it online! (includes all test cases)

K (ngn/k), 36 bytes
{,/{`c$x-32*~!#x}'_(&1,~~"a{"'_x)_x}

Try it online!

_(&1,~~"a{"'_x)_x split input after each non-letter and lowecase it, e.g. "Begin/With.Type&Content" to ("begin/";"with.";"type&";"content")
{`c$x-32*~!#x}' subtract 32 from the first character in each word and 0 from the rest (in effect capitalizing the first letter and leaving the others unchanged)
,/ flatten back into a single string and (implicitly) return

T-SQL, 179
DECLARE @T VARCHAR(MAX)='foo',@X VARCHAR(2),@ INT=0WHILE @<LEN(@T)SELECT @X=SUBSTRING(@T,@,2),@+=1,@T=STUFF(@T,@,1,IIF(@X LIKE'[a-Z]_',LOWER(RIGHT(@X,1)),UPPER(RIGHT(@X,1))))PRINT @T

Try the SELECT version in SQL Server 2012 here.
Replace "foo" with the input string.  The char count is for a zero-length string.  This code traverses the string using an index, uppercasing or lowercasing the character at that position based on the previous character.

JavaScript (Node.js), 70 bytes
c=>a=>c.split``.map(b=>a="A">a?b.toUpperCase():b.toLowerCase()).join``

Try it online!
I am sure this can be golfed further.
Note :
Takes input via f(string)() , the last are required but perform nothing.

Powershell, 77 75 bytes
This solution fully meets the task rules (even ambiguous example foo:bar).
-join($args|% t*y|%{"$_"|%('ToU*r','ToL*r')[+$l];$l=!('# -./&'|% Co*s $_)})

See also the Powershell solution with builtin function ToTitleCase from @Iszi.
Explained test script:
$f = {

-join(
$args|% t*y|%{                   # for each char from input string
    "$_"|%('ToU*r','ToL*r')[+$l] # evaluate ToUpper or ToLower method depend on $l (lower) value
                                 # Note the variable $l is not defined for a first char
                                 # so it evaluates toUpper for the first char
    $l=!('# -./&'|% Co*s $_)     # golfed form for $l=!'# -./&'.Contains($_) expression
                                 # =0 if the current char is specified separator (toUpper for next char)
}                                # =1 otherwise (toLower for next char)
)                                # finally, join all chars to a result string

}

@(
    ,('foo:bar'                                                                 ,'Foo:bar')
    ,('aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe'                                ,'Agent Accept/Length-Type User Range.Type')
    ,('type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe'         ,'Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code')
    ,('cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc'      ,'Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc')
    ,('lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT' ,'Length#User.Type/Begin&Length Type/Accept#Range/Code&And-Accept/Content')
    ,('contENT/ACcEpT'                                                          ,'Content/Accept')
    ,('BeGin/wITH.tyPE&conTeNt'                                                 ,'Begin/With.Type&Content')
    ,('Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with'       ,'Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With')
    ,('RaNgE&COnTeNT WITh CoNTENT-TypE tyPe'                                    ,'Range&Content With Content-Type Type')
    ,('BEgin COdE#uSeR#aGeNt.USeR'                                              ,'Begin Code#User#Agent.User')
    ,('TypE LENGth'                                                             ,'Type Length')
) | % {
    $s,$e = $_
    $r = &$f $s
    "$($r-ceq$e): $r"
}

Output:
True: Foo:bar
True: Agent Accept/Length-Type User Range.Type
True: Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code
True: Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc
True: Length#User.Type/Begin&Length Type/Accept#Range/Code&And-Accept/Content
True: Content/Accept
True: Begin/With.Type&Content
True: Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With
True: Range&Content With Content-Type Type
True: Begin Code#User#Agent.User
True: Type Length

Zsh, 10 bytes
<<<${(C)1}

Try it online!

Swift 5.6, 52 51 bytes
import Foundation
let f=\.capitalized as(String)->_

Try it on SwiftFiddle! For some reason, this has to be typed using as; let f:(String)->_=\.capitalized doesn't work.

PHP, 28 bytes
Use of a dedicated function around since v4 makes a shorter and easier answer than elder
echo ucwords(strtolower($s));

JavaScript (Node.js), 47 bytes
s=>Buffer(s).map(x=c=>x=x>64?c|32&c/2:c&~32)+``

Try it online!
From Shaggy's

Thunno 2, 1 byte
ḟ

Try it online!
lol
Same as the Python answer - Thunno 2 is written in Python and that's exactly what the interpreter is doing behind the scenes.
(Built-in for title case)

Javascript 72 bytes
prompt().toLowerCase().split``.map((p,e)=>0==e?p.toUpperCase():p).join``

You capitalize only first letter

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


text:
Write a Number as a Fibonacci Sum
Let us define the Fibonacci sequence as
F(1) = 1

F(2) = 2

F(n) = F(n - 2) + F(n - 1)

So we have the infinite sequence 1,2,3,5,8,13,... It is well known that any positive integer can be written as a sum of some Fibonacci numbers. The only caveat is that this summation might not be unique. There is always at least one way to write a number as a sum of Fibonacci numbers but there may be many many more.
Your challenge is to write a complete program which using stdin takes in a positive integer between one and one million inclusive, and then outputs using stdout all possible summations of Fibonacci numbers which sum up to the input. In a summation, the Fibonacci numbers must not repeat and that includes the number 1. In any summation, if 1 is present, it must be present only once because in my definition of the sequence above 1 appears only once. Summations with only term are valid so if the input number is a Fibonacci number itself, then the number itself is a valid summation and must be printed. If multiple sums, then between any two sums there must be a blank line to easily distinguished between them.
Here are some samples.
./myfib 1
1

There is only one such sum and it has only term so that's all that is printed.
./myfib 2
2

Note here that 1+1 is not a valid sum because 1 repeats.
./myfib 3
1+2

3

Two sums and they are both printed with a blank line in between.
./myfib 10
2+8

2+3+5

./myfib 100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55

True code-golf. The shortest code in any language wins. Please post your code with some test cases (besides the one I gave above). In the case of ties, I pick the one with the highest upvotes after waiting at least for two weeks and probably longer. So the community please feel free to upvote any solutions you like. The cleverness/beauty of the code matters much more than who posts first.
Happy coding!

...I'm just going to bruteforce this :P If I post an answer, don't expect it to perform well :)

Well it is code-golf not fastest-code. :-D

I wrote it, and it actually runs fast :P

Not quite a duplicate, but closely related to http://codegolf.stackexchange.com/q/2677/194

You state that the input is in stdin, but your examples show command line parameter. Which is it?

@shiona Since I didn't specify, pick your favorite one. :-)

GolfScript, 54 characters
~1.{3$)<}{.@+}/<[[]]{{+}+1$%+}@/\{~)+{+}*!}+,{'+'*n.}/

Test it online or have a look at the examples:
> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55

Ruby, 118 114 (array output) or 138 134 (correct output)
i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
p (1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}

Sample run:
c:\a\ruby>fibadd
100
[[3, 8, 89], [1, 2, 8, 89], [3, 8, 34, 55], [1, 2, 3, 5, 89], [1, 2, 8, 34, 55], [3, 8, 13, 21, 55], [1, 2, 3, 5, 34, 55], [1, 2, 8, 13, 21, 55], [1, 2, 3, 5, 13, 21, 55]]

Change gets to $*[0] if you want command line arguments (>fibadd 100), +1 character though.
With the correct output:
i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
$><<(1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}.map{|o|o*?+}*'

'

Sample runs:
c:\a\ruby>fibadd
100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55
c:\a\ruby>fibadd
1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610
c:\a\ruby>obfcaps
12804
2+5+21+233+1597+10946

2+5+8+13+233+1597+10946

2+5+21+89+144+1597+10946

2+5+21+233+610+987+10946

2+5+21+233+1597+4181+6765

2+5+8+13+89+144+1597+10946

2+5+8+13+233+610+987+10946

2+5+8+13+233+1597+4181+6765

2+5+21+34+55+144+1597+10946

2+5+21+89+144+610+987+10946

2+5+21+89+144+1597+4181+6765

2+5+21+233+610+987+4181+6765

2+5+8+13+34+55+144+1597+10946

2+5+8+13+89+144+610+987+10946

2+5+8+13+89+144+1597+4181+6765

2+5+8+13+233+610+987+4181+6765

2+5+21+34+55+144+610+987+10946

2+5+21+34+55+144+1597+4181+6765

2+5+21+89+144+233+377+987+10946

2+5+21+89+144+610+987+4181+6765

2+5+21+233+610+987+1597+2584+6765

2+5+8+13+34+55+144+610+987+10946

2+5+8+13+34+55+144+1597+4181+6765

2+5+8+13+89+144+233+377+987+10946

2+5+8+13+89+144+610+987+4181+6765

2+5+8+13+233+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+10946

2+5+21+34+55+144+610+987+4181+6765

2+5+21+89+144+233+377+987+4181+6765

2+5+21+89+144+610+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+10946

2+5+8+13+34+55+144+610+987+4181+6765

2+5+8+13+89+144+233+377+987+4181+6765

2+5+8+13+89+144+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+4181+6765

2+5+21+34+55+144+610+987+1597+2584+6765

2+5+21+89+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+4181+6765

2+5+8+13+34+55+144+610+987+1597+2584+6765

2+5+8+13+89+144+233+377+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+1597+2584+6765

That last one (12804) only took about 3 seconds!

Mathematica, 89 85 chars
Shortened to 85 chars thanks to David Carraher.
i=Input[];#~Row~"+"&/@Select[If[#>i,Subsets@{##},#0[#+#2,##]]&[2,1],Tr@#==i&]//Column

Mathematica has a built-in function Fibonacci, but I don't want to use it.

Very compact. Nice.

76 chars if you don't mind printing as a list of sums:i = Input[]; #~Row~"+" & /@   Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]

84 chars: i = Input[]; #~Row~"+" & /@    Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1],     Tr@# == i &] // Column

Scala, 171
def f(h:Int,n:Int):Stream[Int]=h#::f(n,h+n)
val x=readInt;(1 to x).flatMap(y=>f(1,2).takeWhile(_<=x).combinations(y).filter(_.sum==x)).foreach(z=>println(z.mkString("+")))

You can save a few bytes by using val f:Stream[Int]=1#::f.scanLeft(2)(_+_) for the fibonacci sequence.

Also, please specify "Scala 2.10" as the programming language if you want to use readInt without an import.

You can also save a lot by using the infix operator syntax for methods: 1 to x flatMap(y=>f(1,2)takeWhile(_<=x)combinations(y)filter(_.sum==x))map(z=>println(z mkString "+"))

Python 206 181 characters
import itertools as a
i,j,v,y=1,2,[],input()
while i<1000000:v,i,j=v+[i],j,i+j
for t in range(len(v)+1):
 for s in a.combinations(v,t):
  if sum(s)==y:print "+".join(map(str,s))+"\n"

Sample Run:
25
1+3+21

1+3+8+13

1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610

Get rid of all those extra spaces.You can use one tab or space chars to indent code. Also writing the loop codes in single line when possible is shorter i.e while i<1000000:v+=[i];i,j=j,i+j

Some suggestions (I didn't want to just plagiarize your answer and post my shortened version): import itertools as z, remove the newlines after the colons, put the y=input() in with the x,y,v line, and remove the extra space after the final if statement.

I've included your suggestions in the code. Thanks :)

C#, 376 bytes
class A{IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}static void Main(){new A().C(int.Parse(Console.ReadLine()));}}

Ungolfed:
class A
{
    IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}
    void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}
    static void Main(){new A().C(int.Parse(Console.ReadLine()));}
}

The method B returns an IEnumerable that represents the entire (infinite) Fibonacci set.  The second method, given a number n, looks at the first n Fibonacci numbers (huge overkill here), finds all possible subsets (the power set), and then filters down to subsets whose sum is exactly n, and then prints.

APL (75)
I←⎕⋄{⎕←⎕TC[2],1↓,'+',⍪⍵}¨S/⍨I=+/¨S←/∘F¨↓⍉(N⍴2)⊤⍳2*N←⍴F←{⍵,+/¯2↑⍵}⍣{I<⊃⌽⍺}⍳2

Less competitive than I'd like, mostly because of the output format.
Output:
⎕:
      100

 3 + 8 + 89

 3 + 8 + 34 + 55

 3 + 8 + 13 + 21 + 55

 1 + 2 + 8 + 89

 1 + 2 + 8 + 34 + 55

 1 + 2 + 8 + 13 + 21 + 55

 1 + 2 + 3 + 5 + 89

 1 + 2 + 3 + 5 + 34 + 55

 1 + 2 + 3 + 5 + 13 + 21 + 55

Explanation:

I←⎕: read input, store in I.
⍳2: starting with the list 1 2,
{⍵,+/¯2↑⍵}: add the sum of the last two elements to the list,
⍣{I<⊃⌽⍺}: until I is smaller than the last element of the list.
F←: store in F (these are the fibonacci numbers from 1 to I).
N←⍴F: store the amount of fibonacci numbers in N.
↓⍉(N⍴2)⊤⍳2*N: get the numbers from 1 to 2^N, as bits.
S←/∘F¨: use each of these as a bitmask on F, store in S.
I=+/¨S: for each sub-list in S, see if the sum of it is equal to I.
S/⍨: select these from S. (Now we have all lists of fibonacci numbers that sum to I.)
{...}¨: for each of these:

,'+',⍪⍵: add a + in front of each number,
1↓: take the first + back off,
⎕TC[2]: add an extra newline,
⎕←: and output.

Haskell - 127
After many iterations I ended up with the following code:
f=1:scanl(+)2f
main=getLine>>=putStr.a f "".read
a(f:g)s n|n==f=s++show f++"\n\n"|n<f=""|n>f=a g(s++show f++"+")(n-f)++a g s n

I could have saved maybe one character by cheating and adding an extra "0+" in front of every output line.
I want to share another version (length 143) I came up with while trying to golf the previous solution. I've never abused operators and tuples quite this much before:
f=1:scanl(+)2f
main=getLine>>=(\x->putStr$f€("",read x))
o%p=o++show p;(f:g)€t@(s,n)|n==f=s%f++"\n\n"|n<f=""|n>f=g€(s%f++"+",n-f)++g€t

Test cases, 256:
256
2+3+5+13+34+55+144

2+3+5+13+89+144

2+3+5+13+233

2+8+13+34+55+144

2+8+13+89+144

2+8+13+233

2+21+34+55+144

2+21+89+144

2+21+233

and 1000:
1000
2+3+8+21+34+89+233+610

2+3+8+55+89+233+610

2+3+8+144+233+610

2+3+8+377+610

2+3+8+987

5+8+21+34+89+233+610

5+8+55+89+233+610

5+8+144+233+610

5+8+377+610

5+8+987

13+21+34+89+233+610

13+55+89+233+610

13+144+233+610

13+377+610

13+987

Some efficiency data since someone had this stuff:
% echo "12804" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  0.09s user 0.00s system 96% cpu 0.100 total
% echo "128040" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  2.60s user 0.01s system 99% cpu 2.609 total

CJam, 42 40 bytes
-2 bytes by converting each list from base 1 to calculate its sum instead of using :+. (This saves no bytes by itself, but this method works on the empty set, so it no longer needs to be discarded from the list of lists.)
XY{_2$+}qi:T*]La\{1$f++}/{1bT=},{'+*}%N*

Try it online!
This takes a long time to calculate for large numbers because it generates input + 2 Fibonacci numbers (to ensure that every number less than or equal to the input is included)...but hey, it saves 4 bytes over using a proper while loop.

05AB1E, 19 bytes (Non-competing)
ÅFævy©O¹Qi®'+ý}})ê»

Try it online!
Calculates all possible sums for any given n. Example output for 1000:
1+1+3+8+144+233+610
1+1+3+8+21+34+89+233+610
1+1+3+8+377+610
1+1+3+8+55+89+233+610
1+1+3+8+987
13+144+233+610
13+21+34+89+233+610
13+377+610
13+55+89+233+610
13+987
2+3+8+144+233+610
2+3+8+21+34+89+233+610
2+3+8+377+610
2+3+8+55+89+233+610
2+3+8+987
5+8+144+233+610
5+8+21+34+89+233+610
5+8+377+610
5+8+55+89+233+610
5+8+987

You need 2 newlines between each line of output.

Husk, 22 20 bytes
ṁȯeøJ'+msufo=¹ΣṖt↑İf

Try it online!
-2 bytes with an empty list trick.
Explanation
moJ'+msufo=¹ΣṖt↑İf
               ↑İf Take input number of fibonacci numbers
              t    remove first 1
             Ṗ     get it's powerset
        fo         filter the sublists by the following:
          =¹Σ      sum equals input?
       u           uniquify it
mo                 map each sublist to
     ms            it's elements as strings
  J'+              Joined by '+'

You need 2 newlines between each line of output.

@Shaggy Should work now. (I kinda followed the 05AB1E answer on the output)

I've let them know, too, so.

Japt, 21 bytes
õ!gM Åà f@¶XxÃ®q+ÃqR²

Try it